# Reiser4

Reiser4 é um sistema de arquivos, uma versão específica do ReiserFS, sendo em 2007 a última versão disponível do poderoso Reiser.

## Origem

Em 2001 criado por Hans Reiser o sistema de arquivos Reiser4 teve sua primeira aparição e inicialmente mantido pela empresa (Namesys) para gerenciar os trabalhos do projeto.Esse sistema de arquivo está disponível como padrão em muitas das distribuições Linux. O Reiser4 foi o primeiro sistema de arquivos com suporte a “journaling”( um recurso que ajuda a manter a integridade dos dados em caso de erros no sistema causados por desligamento incorreto ou determinadas falhas de hardware) incluído no núcleo Linux 2.4+. São seus patrocinadores as empresas Novell e Linspire, embora a Novell tenha anunciado em Outubro de 2006 que o sistema de arquivos selecionado por omissão no Suse Linux passou a ser o ext3.

## Semântica Básica
### Ficheiros

Um ficheiro é algo que tenta parecer com uma sequência de bytes.
É possível ler e escrever os bytes, determinar quantos e a partir de onde se podem ler. Também pode-se eliminar bytes no fim do ficheiro. A eliminação no início e meio do ficheiro não é permitida pela semântica do Unix. As interacções com os ficheiros são feitas através de plugins de ficheiros, interfaces que as delimitam. Para cada ficheiro existe uma pluginid. Cada forma de interagir com uma plugin é chamada de método, portanto cada plugin é composta por tais métodos. Cada método é composto de funções de bibliotecas (library). Para implementar um ficheiro Unix regular, com a sua Metadata [ver em tipos de items 2.3.1], é usado um file plugin (unix_file) para o corpo do ficheiro, um directory plugin (unix_file_dir) para encontrar file plugins para cada Metadata e uma especial file plugin para cada Metadata.

### Nome e Objeto

Um nome é um meio de seleção de um objeto. Um Objeto é algo que atua como se fosse uma simples entidade, dependente do contexto. Namespace é o mapeamento de nomes a objetos, como, por exemplo, sistemas de ficheiros, bases de dados, motores de busca ou nomes de variáveis nas shells. Quanto mais poder tiverem os namespaces, mais poder expressivo terá o Sistema Operativo.
Reiser4 procura criar uma storage layer (camada de armazenagem) eficiente para qualquer, e eventualmente unificado, namespace, e uma semantic layer (camada semântica) com algumas vantagens sobre state of the art. A Namesys prevê mais expressão semântica na storage layer. A busca por objectos é feita por camadas. A camada semântica pega os nomes e converte-os em chaves (Keys) através de objectids. A camada de armazenagem (que contém o código para correr a árvore) pega as chaves e procura os bytes que guardam as partes do objecto. Cada elemento da árvore tem uma chave única, apesar de as chaves duplicadas serem permitidas. O seu uso significa que todos os duplicados devem ser examinados e verificado se realmente contêm o que é procurado. Por isto, são raros nos sistemas que procuram alta performance. Permitindo duplicados, as chaves podem ser mais compactas. Reiser4 trata apenas nomes hierárquicos (Hierarchical names). Os não-hierárquicos estão planeados para o SSN ReiserFS. (Semi-Structured Naming Reiserfs).

### Diretórios

Nomes hierárquicos são implementados em Reiser4 pelo uso de diretorios. O 1º componente é o nome da diretorio. Os componentes são separados por "/". Os seguintes componentes são interpretados e usados para seguir para a sub-directorio seguinte até devolver um conjunto de chaves. Em Reiser4, este conjunto contém exactamente um membro, mas em SSN Reiserfs isso poderá mudar. Reiser4 necessita de interagir com a interface do Unix para os sistemas de ficheiros, daí a necessidade de existir uma chave que o VFS (sistema de ficheiros virtual) compreenda. As directorias podem devolver uma lista de nomes, que não precisa de ser a lista de nomes que consegue resolver. É possível ocultar nomes em Reiser4 e as diretorios podem resolver mais nomes do que podem listar, especialmente se forem pseudo files (não existentes na camada de armazenagem).
* Ordenação das Diretorios
Em Unix, nem a ordem com que os ficheiros são criados nem a ordem lexicográfica se impõem à ordem de listagem. Após os sistemas de ficheiros os retornarem, são as aplicações que os ordenam. Em Reiser4, a plugin ordena os nomes dos ficheiros com menos de 15 letras lexicograficamente, e para os com mais, ordena pelas primeiras 8 letras e depois pelo hash do nome completo. Hans Reiser planeia implementar a ordenação pedida pelo utilizador nas próximas versões.
* Diretórios também são Ficheiros
Em Reiser4, (mas não em Reiser3) um objeto tanto pode ser um ficheiro como uma directorio. Se for acedido como ficheiro, devolve uma sequência de bytes; se for acedido como directorio ("/"), devolve o resultado normal (listagem de nomes, ficheiros contidos etc.).
* Entradas escondidas
Um ficheiro pode existir e não ser visível através da forma usual.

## Características

O ReiserFS tem como referência o esquema B+Trees para organizar e localizar os itens que compõem, todo o sistema de arquivos, isto é, os dados em si e as informações associadas (data de criação, permissões de acesso, proprietário, etc). Todos esses itens são classificados em diretórios, blocos de dados diretos e indiretos (direct items / indirect items) e inodes (stat data items). ReiserFS usa árvores balanceadas para tornar o processo de busca de arquivos, informações sobre segurança e outros metadados mais eficientes. Para arquivos muito pequenos, seus dados podem ser armazenados próximos aos metadados, então, ambos podem ser recuperados com um pequeno movimento do mecanismo da "cabeça" de leitura do disco. Essa propriedade vai contribuir para um melhor desempenho caso uma aplicação necessite abrir muitos arquivos pequenos rapidamente. No caso de um desligamento incorreto do sistema, o ReiserFS é capaz de recuperar a consistência do sistema de arquivos em pouco tempo e a possibilidade de perda de pastas ou partições é reduzida.No entanto, os arquivos que eventualmente estiverem sendo gravados no exato momento em que acabou a energia elétrica ficarão com seus dados corrompidos, haverá acesso aos arquivos normalmente, mas o conteúdo estará truncado ou incompleto.

## Árvores: Conceitos básicos
### Árvores

Um modo de organizar informação é a inserir em árvores. Reiser4 usa uma árvore finita com raiz (root), acíclica, com menos um apontadores (1-p) nós, e com exactamente um caminho desde a raiz até qualquer nó.

#### Grafos e Árvores

Esta árvore contém o mínimo de apontadores, suficientes para conectar todos os nós. Reiser usa grafos e árvores, sendo as árvores usadas para quando o sistema de ficheiros escolhe a organização na camada de armazenagem e os grafos para a organização escolhida pelo utilizador na camada semântica (mais complexa).

#### Chaves

A cada elemento na árvore é atribuída uma chave. O uso de chaves adiciona flexibilidade a como são ordenados os elementos, e se estas forem pequenas, um meio compacto de especificar o suficiente para encontrar o elemento, mas também limita que informação pode ser usada para encontrar elementos. Este limites são úteis, pois a camada de armazenagem escolhe as chaves apenas para organizar o armazenamento de modo a melhorar o desempenho, e a camada semântica, nomes que tenham significado para o utilizador. Esta abordagem ajuda a adição de melhoramentos em nível de armazenamento, sem comprometer com efeitos colaterais a camada semântica.

#### A escolha da subárvore

A raiz contém apontadores para as suas subárvores. Para cada apontador a uma subárvore, existe uma chave esquerda delimitadora correspondente. Os apontadores para as subárvores e as subárvores estão ordenadas por esta chave. Esta é igual à menor chave dos elementos da subárvore. Também existe uma chave direita delimitadora que é superior à maior chave na sua subárvore e é a chave esquerda delimitadora na próxima subárvore deste nó. Se não existirem chaves duplicadas, cada subárvore apenas contém elementos cuja chave é igual à chave esquerda delimitadora e menor que a sua chave direita delimitadora, e procurando dentro do nó por apontadores, é encontrado o que se procura. Caso existam chaves duplicadas, como já foi dito, todos os duplicados devem ser examinados um a um e estão ordenados pela ordem de criação.

### Nós
#### Folhas, Pecíolos e Ramos (Leaves, Twigs, and Branches)

Folhas são os nós que não têm filhos. Os nós internos são os que têm filhos.
Um nó que contém itens é chamado nó formatado (formatted node).
Se um objecto é grande, não está comprimido e não precisa suportar inserções eficientes, então pode ser guardado mais eficientemente nos nós sem qualquer uso de itens. É feito por norma para objectos maiores que 16k. Objectos comprimidos são especiais porque necessitam mudar o uso de espaço quando é escrito para os seus interiores, pois a compressão pode não ser igualmente eficiente para os novos dados.
* Nós não formatados {Unformatted leaves (unfleaves)} são folhas que contêm apenas dados e nenhum tipo de informação de formato. Apenas as folhas podem conter dados não formatados. Apontadores são guardados em itens, assim como todos os nós internos são necessariamente nós formatados. Apontadores para unfleaves são diferentes na sua estrutura dos apontadores para nós formatados.
* Apontadores estendidos (Extent pointers) apontam para unfleaves. Uma extensão (extent) é um número grande de blocos consecutivos. Cada extensão é descrita como um triplo, consistindo em: file offset, início do bloco, tamanho, onde file offset é o offset do 1º bloco da extensão desde o início do ficheiro, e tamanho é o número de blocos na extensão. As extensões são alocadas e seguidas como uma única entidade, i.e., um único apontador liga um grupo de blocos. Para grandes ficheiros, alocação por extensão é muito mais eficiente que alocação por bloco.
* Apontadores para nós (Node Pointers) são apontadores para nós formatados. Ainda não existe uma versão comprimida destes apontadores. Para os apontadores estendidos não é categórico guardar as chaves delimitadoras para cada nó apontado, mas é preciso para os Node Pointers.
* Pecíolos (Twigs) são os pais das folhas. Os extent Pointers existem apenas nos pecíolos. Esta é uma decisão muito controversa.
* Ramos (Branches) são nós internos que não são pecíolos.
Como a árvore cresce para cima, é útil numerar as folhas com o nível 1, onde são guardadas os dados. A altura da árvore depende de quantos objectos existem e qual é o fanout rate (número médio de filhos) dos nós internos e dos twigs. A árvore tem a altura mínima de 2 e a raiz é sempre um nó interno.

#### Tamanho dos nós

Os nós são iguais em tamanho. Torna-se mais fácil alocar espaço inutilizado entre os nós, pois será sempre um múltiplo do tamanho dos nós. Em Reiser4, os nós são, normalmente, do tamanho de uma página, que, no caso de GNU/Linux num Intel, é de 4k.

#### A partilha de blocos permite poupar espaço

Para guardar grandes objectos, estes são divididos em menores peças. A estas peças chama-se itens. São dimensionadas para estarem no interior de um único nó. Em Reiser4, múltiplos itens são encaixados num bloco. A eficiência espacial ronda os 94% para pequenos ficheiros, diferentemente dos sistemas de ficheiros convencionais, que guardam os ficheiros num único bloco. Os ficheiros maiores que 16k são alinhados a 4k.

### Items

Os nós nas árvores são muito menores que alguns objectos que guardam ou maiores que outros, por isso são divididos em itens. Cada item tem uma chave, um offset para onde o corpo começa e o tamanho do corpo do item e um pluginid que indica que tipo de item é.

#### Tipos de Itens

Reiser4 inclui muitos tipos diferentes de itens desenhados para conter diferentes tipos de informação:
* static_stat_data: Metadata: guarda o dono, as permissões, a data do último acesso, de criação, da última modificação, tamanho, o número de links (nomes) a um ficheiro e, se existir, access control lists (ACL).
* cmpnd_dir_item: guarda as entradas nas directorias e as chaves para onde esses ficheiros se conectam.
* extent pointers;
* node pointers;
* bodies: guarda partes de ficheiros que não são suficientemente grandes para serem guardados em unfleaves.

#### Unidades (Units)

É o que se deve guardar como um todo num item, sem ter que dividir por múltiplos itens. Atravessar o conteúdo de um item é conveniente que seja em unidades:
* Para o corpo do item, as unidades são bytes
* Para itens directorias, as unidades são entradas em directorias.
* Para itens extensões, as unidades são extensões. As extensões apenas contêm extensões do mesmo ficheiro.
* Para static_stat_data, todo o stat data item é unidade indivisível de tamanho fixado.

#### Aparência dos nós em ReiserFS 4.0

Um unformatted leaf node (nó unfleaf), que é o único nó sem um Node_Header:
A estrutura de um Item :
| Item_Body | .. separated .. | Item_Head |
| | | Item_Key | Item_Offset | Item_Length | Item_Plugin_id |
Um formatted leaf node :
| Block_Head | Item_Body0 | Item_Body1 | … | Item_Bodyn | .... Espaço Livre .... | Item_Headn | … | Item_Head1 | Item_Head0 |
O nó twig tem a seguinte estructura: :
| Block_Head | Item_Body0 Node Pointer0 | Item_Body1 Extent Pointer1 | Item_Body2 Node Pointer2 | Item_Body3 Extent Pointer3 | … | Item_Bodyn Node Pointern | … Free Space … | Item_Headn | --- | Item_Head1 | Item_Head0 |
Um ramo tem a estrutura: :
| Block_Head | Item_Body0 NodePointer0 | --- | Item_Bodyn NodePointern | ....Espaço Livre … | Item_Headn | --- | Item_Head0 |

## Conceitos de desenho de Árvore
### Três princípios

* O ratio de fanout;
* Compacticidade do empacotamento;
* A quantidade de itens que se tem que mover na árvore de um nó para outro.

#### Fanout

O ratio de fanout refere-se a quantos nós podem ser apontados por cada nó num certo nível. Se cada nó pode apontar para n nós no nível abaixo, então, começando na raiz, esta aponta para n nós internos, e assim sucessivamente até o nível m: existem n*m folhas que contêm dados. Para guardar cada vez mais, é necessário que aumente as chaves para distinguir os objectos (objectids) e depois seleccionar partes do objecto (offset). Isto significa que as chaves devem ser maiores, o que diminui o fanout (a não ser que se comprima as chaves).

#### B+Trees
##### B+Trees, e porque são melhores que B-Trees

Nas B-trees é possível guardar não só apontadores e chaves nos nós internos, como também os objectos aos quais as chaves correspondem.
Nas B+trees, apenas apontadores e chaves são guardados nos nós internos, e todos os objectos são guardados nas folhas.

##### B+Trees têm maior fanout que as B-Trees

O fanout aumenta quando existem apenas apontadores e chaves nos nós internos. Aumenta a facilidade de fazer cache de todos os nós internos, pois existem menos.

###### Princípios no Desenho da Cache

Reiser's Untie The Uncorrelated Principle of Cache Design
Tying the caching of things whose usage does not strongly correlate is bad. - Hans Reiser
Agrupando o incorrelacionado é um erro comum no desenho de caches. Em Reiser4, é possível guardar mais de um apontador por nó. Isso significa que os apontadores não estão em caches separados.
Reiser's Maximize The Variance Principle of Cache Design
If two types of things that are cached and accessed, in units that are aggregates, have different average temperatures, then segregating the two types into separate units helps caching.
Para árvores equilibradas, estas agrupamentos são nós. Este princípio aplica-se à situação em que é necessário agrupar elementos em maiores unidades para um acesso eficiente.
* Se os dados frequentemente usados forem igualmente dispersos, então uma cache substancial é necessária e o caching é menos eficiente;
* Se aumentar a variação da temperatura entre os nós, então aumenta a eficácia do uso de uma cache pequena e rápida;
* Se dois tipos de objectos têm diferentes temperaturas médias, então, separando-as em diferentes agrupamentos, aumenta a variação da temperatura no sistema;
* Conclusão: se dois tipos de objectos estiverem na mesma cache com diferentes temperaturas, então a segregação ajuda o caching.
Pointers To Nodes Have A Higher Average Temperature Than The Nodes They Point To
Usando apenas apontadores para nó e as chaves delimitadoras nos nós internos, cria-se uma concentração de apontadores. Como os apontadores tendem a ser mais frequentemente acedidos (por byte), uma alta diferença de temperatura média existe entre apontadores e objectos com dados.
* BLOB
BLOBs desequilibram uma árvore, reduzem a segregação de apontadores e dados e, por isso, reduzem o desempenho.
BLOBs, Binary Large OBjects, são métodos de armazenamento de objectos maiores que um nó, que guardam apontadores para nó contendo o objecto. Foram usados em Reiser3, mas Reiser4 retorna à clássica definição de árvore equilibrada pela altura, em que os tamanhos dos caminhos a todas as folhas são iguais. Não tenta disfarçar que algumas das folhas estão fora da árvore, mesmo que a árvore guarde apontadores para elas. Como resultado, a RAM necessária para guardar os apontadores para os nós é dramaticamente reduzida.

#### Dancing Trees são mais rápidas que as Balanced Trees

Árvores equilibradas têm, tradicionalmente, empregado critérios fixos para determinar quais os nós que deverão ser agrupados para poupar espaço. Este critério era satisfeito no fim de cada modificação da árvore. Este foi o critério usado em ReiserFS V3 para as folhas. Em Reiser4 são usadas as dancing trees. Dancing trees agrupam insuficientes nós, não a cada modificação, mas sim:
* Em resposta a uma descarga para o disco;
* Como resultado de uma transação que guarda os nós no disco.
Árvores equilibradas têm o inerente tradeoff entre o custo de equilíbrio e eficiência espacial. Se se considera mais nós vizinhos para agrupar e libertar um nó, com cada modificação da árvore é possível agrupar a árvore mais compactamente, com o custo de mover mais dados com cada modificação.
Em contraste, com a árvore dançante pega-se uma grande quantidade de nós imediatos (slum), passa-se tudo para o mais à esquerda possível e depois liberta-se os nós na slum que ficou vazia, quando for para guardar no disco. Representa uma extrema eficiência espacial quando as slums são consideráveis, com o custo do movimento de dados, que é menor do que o invariável critério das árvores equilibradas porque é feito com menos frequência. Comprimindo apenas quando for guardado no disco, também se comprime menos vezes e isso significa que se pode fazer mais profundamente. Comprimindo estes nós (dirty) que estão na memória, evita-se que seja efectuada mais I/O como resultado do balanceamento.
3 Procrastination tende para decisões mais inteligentes: alocar no despejar.
ReiserFS V3 associava números dos blocos aos nós assim que os criava. XFS é mais inteligente: espera até o último momento, mesmo antes de escrever no disco.

## Sistemas de Ficheiros journaled
### O problema com os sistemas sem jornal

Se a corrente eléctrica falha ou o computador bloqueia durante um processo de escrita (depois de o ficheiro ser escrito e antes da meta informação ser correctamente adicionada, o sistema de ficheiros perde o ficheiro e cria inconsistências. Também afecta as directorias, p.ex: durante a actualização da directoria). Na tentativa de recuperar a informação perdida, sistemas como o Mac OSX e Linux correrão o programa fsck, de modo, a validar todas as entradas no sistema de ficheiros e que todos os blocos estão alocados e referenciados correctamente. Não existem garantias que os ficheiros corrompidos serão recuperados e é aqui que o journaled file system (JFS) pode ajudar.

### A importância de Sistemas de Ficheiros journaled

Um sistema de ficheiros com jornal / logs, é um ficheiro que contém o seu próprio backup e capacidade de recuperação. Antes dos indexes serem actualizados, a informação sobre as mudanças são gravadas num log. Um JFS mantém o log ou jornal de que actividades tomaram lugar nas principais partes do disco. O JFS ou escreve ou relê o jornal. Com as técnicas de bases de dados, o JFS consegue restaurar um sistema de ficheiros em minutos para um estado de consistência. Alguns dos sistemas de ficheiros que suportam JSF são:
* Apple's HFS (o journaling é desligado por defeito)
* Linux Ext3, ReiserFS, XFS, e JFS
* Solaris UFS
* Windows NTFS

### O interior de um file systems

Através do trabalho de Steve Best, que trabalha para IBM e tem presença no comité open source para o JFS distribuído com o Linux, define-se:
Um bloco lógico (logical block) como sendo a mais pequena unidade de armazenagem que pode ser alocada pelo sistema de ficheiros e é medido em bytes
Um volume lógico (logical volume) pode ser um disco físico ou outro tipo de partição do disco físico.
A metadata do sistema de ficheiros é a sua representação interna estruturada – tudo o que diz respeito ao ficheiro com excepção aos dados contidos no ficheiro. A Metadata de um ficheiro é guardada no inode correspondente.
O Unix file system (UFS) usa um multi-nível index chamado de inode (information node). Um file inode guarda toda a Metadata. Também contém apontadores directos, indirectos e duplo e triplamente indirectos para blocos de dados do ficheiro. Cada inode tem um número único que o distingue.
Um directory inode é outro tipo especial de ficheiro que simplesmente contém apontadores para outros ficheiros contidos na directoria, mais as permissões, etc...
O superbloco é a informação da raiz. Fica no offset fixo desde o início da partição:

### Fixed Location Journaling

Originalmente, os sistemas de ficheiros tinham aplicações que corriam depois de cada crash. O problema era:
* Não lidavam com todas as formas de danos;
* Demoravam muito tempo.
A quantidade de dados guardados nos disco aumentava cada vez mais rápido do que a transferencia de dados, o que significava que cada vez demoravam mais.

#### Em ReiserFS V4

A solução adoptada para o Reiser4 foi de primeiro escrever cada operação atómica para um lugar no jornal, e depois, só depois de cada átomo ter chegado completamente ao jornal, era escrito no seu lugar próprio. Mas persistia um problema: escrevia-se duas vezes mais. Por um lado, se o workload era dominado por procuras, o fardo era menor. Por outro, se dominavam as escritas, o desempenho era muito diminuído. Por esta razão, metadata journaling veio dominar o uso comum, pois garante que todas as operações na sua metadata serão feitas atomicamente. Se um ficheiro está a ser escrito, os dados que estão a ser escritos podem tornar-se corruptos como resultado de operações não atómicas, mas o âmago do sistema de ficheiros será sempre consistente. O ganho no desempenho é substancial. A versão 3 de reiserFS oferecia metadata e data journaling. Normalmente, data journaling garante que os ficheiros não conterão "random garbage", independentemente do número de blocos que acabem por ser escritos e de que as aplicações vejam o resultado como dados inconsistentes.

#### Wandering Logs

Um modo de evitar que se escreva duas vezes é mudando a definição de onde é a área de log e onde serão guardados os dados, em vez de mover os dados do log para a "committed area".
Uma complicação que surge é que é necessário que um certo número de apontadores do resto do sistema de ficheiros aponte para os novos dados. Quando a transferência (commit) ocorre, também é necessário escrever esses apontadores, que tendem a estar muito concentrados. Mas para actualizar estes apontadores, é necessário fazer um commit atómico destes, e assim as ondas repercutem-se pela arvore acima. Quando chega à raiz, este pode ser escrito atomicamente no superbloco. É assim que WAFL funciona. "Empurra" as mudanças para o topo e eficientemente actualiza o sistema de ficheiros.

## Segurança
### Boa segurança requer precisão na especificação de Segurança

Um princípio geral de segurança é que uma boa segurança requer precisão de permissões.

### Eficiência Espacial motiva Segurança Imprecisa

Muitos sistema de ficheiros tornam o uso do espaço ineficiente para guardar pequenos componentes como ficheiros separados pelas mais variadas razões. Não sendo ficheiros separados significa que não tem diferentes permissões.

### Agregação é melhor implementada como herança

Para conseguir precisão na Segurança é necessário haver em Reiser hereditariedade com delimitadores específicos e suporte para ACL's.

## Considerações

Reiser4 oferece uma estrutura dramaticamente melhor para criar novas características. Os ficheiros e directorias tem tudo o que precisam para não necessitarem que os atributos de ficheiros sejam diferentes de ficheiros. A eficiência desta infra-estrutura é testada usando uma variedade de características de Segurança. A performance foi melhorada pelo uso de árvores dançantes, logs errantes, alocação na descarga, pelo repacker e encriptação no commit.

## Desvantagens

Por ter um consumo de CPU muito elevado é uma desvantagem do ReiserFS que utiliza no mínimo 7 por cento da CPU, chegando a usar até 99 por cento, quando a atividade de disco é elevada.
No dia 10 de Outubro de 2006 de Hans Reiser, seu criador, foi preso e sua condenação em 28 de Abril de 2008 pelo assassinato de sua mulher no início de Setembro de 2006. Atualmente, devido à paralisação das atividades da Namesys, o projeto ReiserFS está armazenado em kernel.org.