Sistemas de arquivos

A visão geral: duas metades de um mesmo assunto

Para o computador, um arquivo é só uma fila longa de bytes (um byte é um número pequeno, de 0 a 255). O computador não sabe se os bytes são uma foto, uma música ou uma lista de nomes. O significado é decidido pelos programas que escrevem e leem.

O assunto tem duas metades. A primeira é o trabalho do sistema operacional: arquivos, nomes, pastas, colocar os bytes no disco, espaço livre e segurança contra quedas. A segunda é o trabalho de quem projeta o interior de um arquivo: registros, índices, árvores B, ordenação e compressão. As duas obedecem à mesma lei: o disco é lento, então contamos os acessos ao disco.

Palavras que você vai encontrar

Armazenamento secundário: disco, flash e o custo de um acesso

A memória (RAM) é como a mesa onde você trabalha: pequena, mas tudo o que está nela fica a um segundo de distância. O disco, também chamado de armazenamento secundário, é como uma biblioteca do outro lado da cidade: enorme, mas cada viagem demora. Um acesso típico à memória leva cerca de 100 nanossegundos. Um acesso típico a um disco magnético leva cerca de 10 milissegundos. É uma razão de 100.000 para 1.

Por causa dessa distância, o trabalho que o processador faz entre dois acessos ao disco é quase de graça. O que decide a velocidade de um programa de arquivos é quantos acessos ao disco ele faz. Índices, árvores B e ordenação externa nascem desse único fato.

Dentro de um disco magnético

   um disco com 2 pratos (4 superfícies)

   superfície = um círculo plano com material magnético
   trilha     = um anel em uma superfície
   setor      = uma fatia de uma trilha (em geral 512 bytes)
   cilindro   = a mesma trilha em todas as superfícies,
                empilhadas como os anéis de uma lata

        trilha 5 da superfície 0   --+
        trilha 5 da superfície 1   --+-- cilindro 5
        trilha 5 da superfície 2   --+
        trilha 5 da superfície 3   --+

O disco gira e um braço com a cabeça de leitura anda para dentro e para fora. O braço lê todas as trilhas de um cilindro sem se mover, então vale a pena gravar um arquivo ao longo de um cilindro antes de passar ao seguinte.

A capacidade de um disco é o produto: tamanho do setor x setores por trilha x trilhas por cilindro x número de cilindros. Por exemplo, 512 bytes x 32 setores x 4 trilhas x 100 cilindros = 6.553.600 bytes, ou seja, 6,25 MiB (1 MiB = 2^20 = 1.048.576 bytes). A BIOS dos primeiros PCs só endereçava 1.024 cilindros, 16 cabeças e 63 setores, e desse limite vem a antiga barreira de 504 MiB.

As três partes de um acesso

Uma volta completa leva 60.000 / rpm milissegundos, onde rpm é o número de voltas por minuto. Um disco de 5.400 rpm precisa de 60.000 / 5.400 = 11,1 ms por volta, então o atraso rotacional médio (meia volta) é cerca de 5,6 ms. Um disco mais rápido, de 10.000 rpm, reduz isso na mesma proporção.

Seek e rotação são mecânicos, por isso lentos. A transferência é rápida. Então ler blocos vizinhos paga seek e rotação uma vez só, mas ler blocos espalhados paga os dois toda vez. Considere 100 blocos, seek de 10 ms, atraso rotacional de 5 ms e transferência de 0,2 ms por bloco. Lê-los em sequência custa 10 + 5 + 100 x 0,2 = 35 ms. Lê-los um a um em lugares aleatórios custa 100 x (10 + 5 + 0,2) = 1.520 ms. É cerca de 43 vezes mais, com os mesmos dados.

Blocagem: vários registros por bloco

Uma leitura de disco sempre traz um bloco inteiro, não um registro. Se um bloco guarda 20 registros (o fator de blocagem), um arquivo de 6.000 registros ocupa 300 blocos. Uma busca sequencial por uma chave que existe examina cerca de metade do arquivo em média, então faz cerca de 150 leituras, não 3.000. A blocagem divide as leituras pelo fator de blocagem, mas a busca continua linear.

Memória flash (SSD)

Um SSD não tem braço nem giro, então não tem seek. Mas a flash NAND tem uma regra estranha: lê e escreve em páginas pequenas, porém só consegue apagar um bloco de apagamento inteiro (muitas páginas juntas), e cada bloco de apagamento aguenta um número limitado de apagamentos.

• Uma página que já tem dados não pode ser reescrita no lugar. O disco grava a nova versão em uma página livre e marca a antiga como inválida.
• A flash translation layer (FTL) é um pequeno programa dentro do SSD. Ela guarda uma tabela do bloco lógico que o sistema de arquivos pede para a página real, e assim o SSD parece um disco comum.
• A coleta de lixo copia as páginas válidas de um bloco de apagamento quase todo inválido e apaga esse bloco.
• O nivelamento de desgaste (wear levelling) espalha as escritas por todos os blocos para que nenhum se gaste primeiro.
• O comando TRIM avisa ao SSD quais blocos o sistema de arquivos liberou, para que ele não copie páginas mortas à toa.

Fita magnética

Na fita, cada bloco é seguido de uma lacuna (gap) vazia, porque a fita precisa de espaço para parar e voltar à velocidade. O comprimento usado é S = n x (b + g), onde n é o número de blocos, b é o comprimento de dados de um bloco e g é a lacuna. Exemplo: 1.000 registros de 100 bytes, a 1.000 bytes por polegada, com lacuna de 0,4 polegada. Um registro por bloco: b = 0,1 polegada, S = 1.000 x 0,5 = 500 polegadas. Dez registros por bloco: n = 100, b = 1 polegada, S = 100 x 1,4 = 140 polegadas. A blocagem deixa a fita 3,6 vezes mais curta, porque há dez vezes menos lacunas.

Arquivos, atributos e operações

Quando você escreve fopen("clientes.dat", "r") em C, duas coisas diferentes se encontram. O arquivo físico é a fila real de bytes que o sistema operacional guarda no disco. O arquivo lógico é o nome que o seu programa usa para ele, por exemplo a variável fp do tipo FILE *. A operação abrir liga um ao outro. O mesmo programa pode ser ligado a outro arquivo físico só trocando o nome.

O que há dentro: bytes e tipos de arquivo

UNIX e Windows tratam um arquivo regular como uma sequência de bytes simples. O sistema não sabe o que os bytes significam, então campos, registros e linhas são decididos pela aplicação. É o modelo mais flexível, e por isso venceu. O sistema conhece só poucos tipos de arquivo: regulares, diretórios e arquivos especiais que representam dispositivos (especial de caracteres para teclados, especial de blocos para discos). Entre os regulares, o único formato que o kernel precisa mesmo entender é o executável, que ele reconhece pelo número mágico no começo do arquivo. Uma extensão como .txt é só um costume que os programas podem seguir ou ignorar.

Atributos

Além dos bytes, um arquivo tem fatos sobre ele, chamados atributos ou metadados: tamanho, dono, permissões, número de links e três marcas de tempo. Esses fatos ficam no i-node do arquivo, não nos bytes dele.

Operações e o deslocamento atual

Todo arquivo aberto tem um deslocamento atual (offset): o lugar onde acontece a próxima leitura ou escrita. read e write o empurram para a frente. lseek só muda o offset. Não faz entrada nem saída, por isso é barato. O custo real aparece na próxima leitura, quando o sistema transforma o offset em um bloco e o busca no disco (a menos que já esteja no cache).

Modos de abertura do fopen

Descritores, entradas de arquivo aberto e i-nodes

tabela do processo       tabela de arquivos     tabela de i-nodes
(uma por processo)        abertos (do sistema)   (um por arquivo)

 fd 3 ------------+--->  entrada A: offset 2 ---+
 fd 4 (dup do 3) -+                            +--> i-node de f
 fd 5 ----------------->  entrada B: offset 0 ---+

Há três níveis. Um descritor é um número pequeno na tabela do processo. Ele aponta para uma entrada de arquivo aberto, que guarda o offset atual e o modo de abertura. Esta aponta para o i-node, que tem os atributos e os blocos. dup e fork copiam o descritor, então as duas cópias compartilham uma entrada e um offset. Um open separado do mesmo arquivo cria uma entrada nova com offset próprio.

// o arquivo contém os bytes 0123456
int a = open("f", O_RDONLY);
int b = dup(a);                 // mesma entrada de arquivo aberto que a
int c = open("f", O_RDONLY);    // entrada nova, offset 0
char buf[2], x, y;
read(a, buf, 2);                // buf = '0','1'; o offset compartilhado agora é 2
read(b, &x, 1);                 // x = '2', porque o offset é compartilhado
read(c, &y, 1);                 // y = '0', porque c tem offset próprio

É por isso que um processo pai e um filho, depois do fork, escrevem um depois do outro no mesmo arquivo de saída em vez de escrever por cima um do outro.

Duas camadas de buffer

• O buffer da biblioteca C fica na memória do seu processo. fwrite coloca os bytes ali para evitar uma chamada de sistema por chamada. fflush ou fclose os envia ao kernel. Se o processo for morto antes (por exemplo por SIGKILL), esses bytes se perdem.
• O cache do kernel (page cache) recebe os bytes no write e sobrevive à morte do processo. fsync o força até o disco. Esses bytes só se perdem se a máquina inteira falhar antes.

Arquivos esparsos e mapeamento em memória

Se você cria um arquivo vazio, faz lseek até o offset 40.960 e escreve um byte, o arquivo vira um arquivo esparso. O tamanho lógico (mostrado por ls -l) é 40.961 bytes, mas com blocos de 4 KB só o bloco que guarda esse último byte é alocado, então du mostra um bloco. A parte pulada é um buraco (hole), e ler dentro dele devolve zeros sem tocar o disco. Copiar um arquivo esparso byte a byte pode encher um disco.

Com mmap um processo pode mapear um arquivo na memória: uma faixa de endereços corresponde aos bytes do arquivo, e o sistema carrega as páginas quando são tocadas (paginação por demanda). Não há cópia entre o cache do kernel e um buffer do programa, e o acesso aleatório fica simples. Mas o programa deixa de decidir quando os dados chegam ao disco, a não ser que chame msync.

Alocação: contígua, encadeada, FAT, i-nodes

Um arquivo pode precisar de muitos blocos. Alocação é a escolha de quais blocos do disco pertencem a qual arquivo, e como o sistema lembra disso. Há quatro respostas clássicas.

1. Alocação contígua

O arquivo fica em uma fila de blocos vizinhos. A entrada de diretório precisa de só dois números: o bloco inicial e o número de blocos. O endereço do bloco k é início + k, uma soma. Por isso o acesso aleatório e a leitura sequencial são muito rápidos. Os problemas: um arquivo que precisa crescer pode não achar espaço depois dele, e quando arquivos são apagados o espaço livre se parte em buracos. É a fragmentação externa: o espaço livre total pode bastar, mas nenhum buraco é grande o bastante para um arquivo novo. O remédio, a compactação, é caro.

2. Alocação encadeada

Cada bloco carrega o número do próximo bloco, e o diretório guarda o número do primeiro. Qualquer bloco livre serve, então não há fragmentação externa. Mas para chegar ao bloco lógico k (contando de 0) o sistema precisa ler os blocos 0, 1, ... até k, porque todos os ponteiros estão no disco: são k + 1 leituras. Além disso, o ponteiro ocupa alguns bytes de cada bloco, então a parte de dados deixa de ser uma potência de dois, o que atrapalha programas que leem blocos inteiros.

3. FAT (tabela de alocação de arquivos)

A FAT tira todos os ponteiros de dentro dos blocos e os põe em uma tabela com uma entrada por bloco do disco. A entrada i diz qual bloco vem depois do bloco i, ou marca o fim ou um bloco livre. O bloco inteiro fica livre para dados, e o sistema segue a cadeia na memória.

entrada:  0     1     2     3     4     5     6     7
valor:    -     5     EOF   LIVRE 1     2     LIVRE -

o arquivo começa no bloco 4 (vem do diretório):
   4 --> 1 --> 5 --> 2 --> EOF       arquivo = blocos 4, 1, 5, 2

O preço: a tabela inteira precisa estar na memória, e ela é tão grande quanto o disco, não quanto o número de arquivos em uso. A largura da entrada limita o volume: FAT-12, FAT-16 e FAT-32 usam 12, 16 e 28 bits de endereço. O maior volume é o número de clusters x o tamanho do cluster. Exemplo: entradas de 12 bits e clusters de 4 KB dão 2^12 x 2^12 bytes = 16 MiB. Por isso volumes maiores exigiram clusters maiores (mais desperdício), até a entrada ser alargada.

4. I-nodes

Um i-node é uma fichinha de um arquivo: seus atributos mais os endereços dos seus blocos. Só os i-nodes dos arquivos em uso precisam estar na memória, então a memória necessária é proporcional ao número de arquivos abertos, enquanto a FAT é proporcional ao tamanho do disco. Essa é a grande vantagem.

O i-node tem alguns ponteiros diretos para blocos de dados, depois um ponteiro indireto simples (para um bloco cheio de ponteiros), um indireto duplo (um bloco de blocos de ponteiros) e um indireto triplo. Arquivos pequenos, que são a maioria, vivem inteiros nos ponteiros diretos. Um bloco guarda (tamanho do bloco / tamanho do ponteiro) números. Com blocos de 1 KB e números de 4 bytes são 256.

Como achar um byte, passo a passo. Considere blocos de 2 KB, números de 4 bytes (então 512 números por bloco) e 8 ponteiros diretos, e ache o byte no offset 3.000.000. Primeiro transforme o offset em bloco lógico: 3.000.000 div 2.048 = 1.464. Os diretos cobrem os blocos 0 a 7, o indireto simples cobre 8 a 519, e o indireto duplo começa em 520. Então o bloco está na área do indireto duplo, na posição 1.464 - 520 = 944. Divida 944 por 512: quociente 1, resto 432. Leia o bloco indireto duplo, pegue a entrada 1, leia esse bloco, pegue a entrada 432 e leia o bloco de dados.

Convenção usada neste resumo e no quiz: o i-node já está na memória e nada está em cache, e a contagem de blocos lidos inclui o bloco de dados. Então o exemplo acima lê 3 blocos: o indireto duplo, um indireto simples e o de dados. Um bloco direto custa 1 leitura, um indireto simples custa 2, um duplo 3 e um triplo 4.

O maior arquivo é o menor de três limites independentes: quanto a árvore de ponteiros alcança, quantos blocos a largura do número de bloco consegue nomear, e que número o campo de tamanho do i-node consegue guardar. Sistemas reais foram limitados por cada um deles, um de cada vez, e por isso os campos de tamanho passaram a 64 bits.

Extents, falta de i-nodes e arquivos pequenos

• Um extent (chamado de run no NTFS) registra um trecho de blocos contíguos com dois números: o início e o comprimento. Um arquivo em poucos pedaços precisa de pouquíssimos metadados. É um meio-termo entre a alocação contígua e um ponteiro por bloco. O ext4 e o NTFS usam isso.
• Um volume UNIX clássico tem duas coisas que podem acabar: blocos de dados e i-nodes. O número de i-nodes é fixado quando o disco é formatado. Um disco cheio de arquivos minúsculos pode dizer 'sem espaço' ao criar um arquivo novo mesmo com milhares de blocos livres. O comando df -i mostra os i-nodes.
• No NTFS, tudo sobre um arquivo é um atributo do seu registro na MFT, inclusive os dados. Um arquivo minúsculo (digamos 200 bytes) fica guardado dentro do registro da MFT (residente). Dados grandes vão para clusters descritos por runs (não residente).

Fragmentação: os dois tipos

A fragmentação interna é espaço dado a um arquivo e não usado por ele: a sobra do último bloco. Exemplo: clusters de 4.096 bytes, arquivos de 100, 5.000 e 8.192 bytes. Eles ocupam 1, 2 e 2 clusters, então o desperdício é 3.996 + 3.192 + 0 = 7.188 bytes. Em média meio bloco se perde por arquivo. A fragmentação externa é espaço livre cortado em pedaços entre os arquivos, pequenos demais para usar.

Diretórios e links

Você não quer lembrar que o seu dever está no i-node 48.213. Você quer chamá-lo de dever.txt. Um diretório é a coisa que junta nomes a arquivos. Em um sistema de arquivos UNIX clássico, um diretório é só uma tabela de pares: um nome e um número de i-node. Os atributos e os endereços dos blocos ficam no i-node, não na entrada do diretório.

Caminhos

Um caminho absoluto começa na raiz / e não depende de onde o processo está. Um caminho relativo é resolvido a partir do diretório de trabalho do processo. Todo diretório tem duas entradas especiais: . (o próprio diretório) e .. (o pai dele). São nomes comuns guardados no diretório. Então, se o diretório de trabalho é /home/ana, o caminho docs/../notes.txt entra em docs, volta e termina em /home/ana/notes.txt.

Como o sistema resolve um caminho

Para abrir /usr/ast/mbox o sistema percorre o caminho nome por nome. Para cada nome ele precisa de duas leituras: o bloco do diretório atual (para achar o número do i-node do próximo nome) e depois esse i-node (para saber onde estão os blocos do próximo nível).

open("/a/b/c")      i-node da raiz já está na memória

 1. ler o bloco de /      -> acha o número do i-node de a
 2. ler o i-node de a
 3. ler o bloco de a      -> acha o número do i-node de b
 4. ler o i-node de b
 5. ler o bloco de b      -> acha o número do i-node de c
 6. ler o i-node de c     -> agora está na memória

Por isso os sistemas mantêm um cache de nomes. Supomos que cada diretório cabe em um bloco.

Links físicos e links simbólicos

A contagem de links

O i-node guarda uma contagem de links: quantas entradas de diretório apontam para ele. Quando um nome é removido (unlink) a contagem diminui, e quando chega a zero (e ninguém tem o arquivo aberto) o sistema libera o arquivo. Para um diretório: um link vem do nome dele no pai, um da própria entrada ., e um da entrada .. de cada subdiretório direto. Então um diretório vazio tem contagem 2, e um diretório com 3 subdiretórios tem 2 + 3 = 5. A contagem menos 2 é o número de subdiretórios.

Por que um usuário comum não pode fazer um link físico para um diretório? Porque a contagem funciona como a regra 'libere em zero' só quando o grafo de diretórios não tem ciclos. Um ciclo manteria a contagem acima de zero para algo que ninguém alcança, e seria preciso um coletor de lixo para achá-lo. Um link simbólico pode apontar para um diretório porque não entra na contagem, e os programas que percorrem a árvore podem simplesmente se recusar a segui-lo.

Mover um arquivo

mv dentro de um sistema de arquivos chama rename: cria uma entrada no diretório novo e remove a antiga. Nenhum bloco de dados é tocado, então mover um arquivo de 4 GB é instantâneo. Entre dois sistemas de arquivos o número do i-node não vale, então o sistema precisa copiar os dados e apagar o original.

Gerenciamento de espaço livre e journaling

Quando você salva um arquivo novo, o sistema precisa achar blocos vazios. Então precisa de um registro de quais blocos estão livres. Há duas maneiras clássicas.

Mapa de bits (bitmap)

Um mapa de bits tem um bit por bloco: 1 significa usado, 0 significa livre (ou o contrário). O tamanho é fixo, qualquer que seja a ocupação do disco, e fica fácil achar blocos livres vizinhos, o que ajuda a manter arquivos contíguos. Exemplo: um disco de 2^38 bytes (256 GB) com blocos de 4 KB (2^12 bytes) tem 2^26 blocos, então o mapa tem 2^26 bits = 2^23 bytes = 8 MiB, que cabem em 2^23 / 2^12 = 2.048 blocos. Custa cerca de 0,003% do disco.

Lista encadeada de blocos livres

Os blocos livres ficam em uma lista. Cada bloco da lista guarda muitos números de blocos livres e um ponteiro para o próximo bloco da lista. Com blocos de 2 KB e números de 32 bits, um bloco da lista guarda 512 números: 511 números de blocos livres e 1 ponteiro. Para registrar 102.200 blocos livres são necessários 102.200 / 511 = 200 blocos de lista. O custo cresce com o espaço livre, não com o tamanho do disco, e a lista pode viver dentro dos próprios blocos livres, então não tira nada dos arquivos.

Qual é menor? O mapa de bits custa B bits para um disco de B blocos. A lista custa 32 bits por bloco livre. A lista só ganha se 32 x (blocos livres) < B, isto é, quando menos de 1/32 do disco (cerca de 3%) está livre. É um disco quase cheio, então o mapa de bits é a escolha comum.

Quedas: por que uma operação são várias escritas

Apagar um arquivo em um sistema UNIX sem journal exige várias escritas em lugares diferentes do disco: (1) remover a entrada do diretório, (2) liberar o i-node, (3) devolver os blocos de dados à lista de livres. A energia pode cair entre duas delas.

A ordem das escritas decide o dano. Liberar as coisas por último só pode perder espaço, o que é melhor do que deixar um nome apontando para algo já liberado. O espaço só volta depois de uma verificação completa com o fsck.

O verificador de consistência

O fsck monta duas tabelas com um contador por bloco: quantas vezes o bloco aparece em algum arquivo e quantas vezes aparece na lista de livres. Em um disco saudável todo bloco tem exatamente (1, 0) ou (0, 1).

Journaling (log de escrita antecipada)

Um journal é um diário. Antes de mexer nas estruturas de verdade, o sistema escreve no diário o que vai fazer. Só depois que a anotação está segura é que faz as mudanças reais. Quando elas terminam, a anotação pode ser jogada fora.

 1. gravar as mudanças planejadas no journal
 2. gravar um registro de COMMIT   <-- agora a operação vale
 3. aplicar as mudanças nos lugares reais
 4. liberar a anotação do journal

 queda antes do 2 : sem commit -> descartar a anotação (nada aconteceu)
 queda depois do 2: com commit -> refazer a anotação (acontece tudo)

Depois de uma queda o sistema lê o journal, refaz as transações com commit e descarta as que não têm registro de commit. É bem mais rápido do que varrer o disco inteiro.

Muitos sistemas de arquivos registram no journal só os metadados (i-nodes, diretórios, mapas de blocos): o journal fica pequeno e rápido, e as estruturas sempre voltam a um estado consistente. Mas o conteúdo de um arquivo que ainda estava no cache pode se perder. A durabilidade do conteúdo exige fsync ou um modo que também registre os dados, o que escreve cada bloco duas vezes.

Cotas (quotas)

Para impedir que um usuário encha o disco, o sistema guarda, para cada usuário, o uso atual de blocos e de i-nodes e dois limites. O limite brando (soft) pode ser ultrapassado por pouco tempo (o usuário recebe avisos). O limite rígido (hard) nunca pode ser ultrapassado: a alocação simplesmente falha.

Organização de registros: fixo, variável, RRN

Suponha que um programa escreve nomes e cidades um depois do outro e o arquivo fica assim: AnaSilvaRecifeBrunoLimaNatal. Onde acaba o nome e começa a cidade? Ninguém sabe. Um arquivo é só bytes, então o programa precisa gravar a estrutura. Há quatro maneiras clássicas de separar campos:

• Campos de tamanho fixo: todo campo tem o mesmo número de bytes, completado com espaços.
• Indicador de tamanho: um número antes de cada campo diz quantos bytes ele tem.
• Delimitador: um caractere especial como | depois de cada campo.
• Palavra-chave e valor: pares como cidade=Recife.

Registros de tamanho fixo e o RRN

Se todo registro tem o mesmo tamanho, a posição de qualquer registro é calculada, não procurada. O RRN (relative record number, número relativo do registro) é o número de ordem do registro no arquivo. Neste curso o RRN começa em 0. Se o arquivo tem um cabeçalho de H bytes e cada registro tem R bytes, o registro de número RRN começa no byte

deslocamento = H + RRN x R

exemplo: H = 32, R = 100, RRN = 7
deslocamento = 32 + 7 x 100 = 732

byte 0       32        132       232
     +--------+---------+---------+---------+
     | cabeç. | RRN 0   | RRN 1   | RRN 2   | ...
     +--------+---------+---------+---------+

Um seek vai direto ao registro: tempo constante. Esta é a razão pela qual o acesso direto por RRN exige registros de tamanho fixo. Além disso, o número de registros de um arquivo é (tamanho do arquivo - cabeçalho) / tamanho do registro. Se a divisão não for exata, o arquivo está danificado. Exemplo: um arquivo de 4.032 bytes com cabeçalho de 32 e registros de 100 tem (4.032 - 32) / 100 = 40 registros.

O preço é o desperdício interno: cada campo é dimensionado para o maior valor esperado, então a sobra é preenchimento (padding). Se um registro tem campos de 30, 20 e 14 bytes (64 no total) e os valores usam 3, 6 e 11 bytes, 64 - 20 = 44 bytes são preenchimento.

Registros de tamanho variável

Aqui cada registro tem só o tamanho de que precisa, em geral com um indicador de tamanho no começo. O arquivo fica menor, mas você perde o acesso direto: o começo do próximo registro só é conhecido depois de ler o indicador do registro atual. Exemplo: registros de 1 + 4, 1 + 7 e 1 + 3 bytes começam nos offsets 0, 5 e 13. Para chegar ao 500º registro é preciso passar por 499 registros, então o tempo é proporcional a n. A solução é um índice separado com o offset de cada registro.

O registro de cabeçalho

Um registro de cabeçalho no começo do arquivo guarda fatos sobre o arquivo todo: um número mágico, uma versão, o tamanho do registro, o número de registros, e assim por diante. Ele torna o arquivo autodescritivo: quem o abre lê o cabeçalho primeiro e aprende como ler o resto. O preço é que o primeiro registro de dados não começa mais no byte 0.

Ordem dos bytes (endianness)

Um número de 4 bytes pode ser guardado com a ponta grande primeiro (big-endian) ou a ponta pequena primeiro (little-endian). Se um programa escreve um inteiro copiando seus bytes da memória, o arquivo depende da máquina. O número 258 é 0x00000102. Uma máquina big-endian escreve os bytes 00 00 01 02. Uma máquina little-endian que lê esses bytes direto em um inteiro monta 0x02010000 = 33.619.968. Um formato portável fixa a ordem dos bytes de cada campo, e os programas convertem ao ler e ao escrever. Com um formato combinado, N arquiteturas precisam de 2N conversores em vez de um para cada par.

A forma canônica de uma chave

Uma busca compara bytes. 'maria silva', 'MARIA SILVA' e 'Maria Silva ' parecem iguais para você, mas não para o computador. A forma canônica é a única maneira combinada de escrever uma chave (por exemplo, letras maiúsculas, sem acentos, sem espaços sobrando). Todo programa a aplica antes de gravar e antes de buscar.

Compressão e recuperação de espaço

O que acontece com o espaço de um registro que você apaga? Há três respostas, da preguiçosa à arrumada.

1. Marcar como apagado e não fazer mais nada. É rápido e pode ser desfeito. O espaço continua lá, desperdiçado.
2. Compactação: de tempos em tempos, reescrever o arquivo sem os registros marcados. O espaço volta, mas os endereços mudam, então os índices precisam ser reconstruídos.
3. Reaproveitar o espaço na próxima inserção, usando uma lista de registros livres.

Registros de tamanho fixo: a lista de livres como pilha

Com registros de tamanho fixo qualquer espaço livre serve para qualquer registro novo, então uma pilha basta. O cabeçalho guarda o RRN do topo. Cada espaço apagado guarda o RRN do que está abaixo dele. Apagar = empilhar. Inserir = desempilhar. A lista não ocupa espaço extra, pois vive dentro dos espaços livres. O arquivo só cresce quando a pilha está vazia.

início: topo = -1 (vazia)
remove RRN 4   -> pilha (topo primeiro): 4
remove RRN 1   -> pilha: 1, 4
insere P       -> P vai para o RRN 1, pilha: 4
remove RRN 6   -> pilha: 6, 4
insere Q       -> Q vai para o RRN 6, pilha: 4
insere R       -> R vai para o RRN 4, pilha: vazia (topo = -1)
insere S       -> pilha vazia, então S vai para o fim do arquivo

Registros de tamanho variável: qual buraco usar?

Agora os buracos têm tamanhos diferentes, então o sistema precisa escolher um que caiba. Considere uma lista de livres 50 -> 25 -> 90 -> 35 (tamanhos em bytes) e um registro novo de 30 bytes.

O best-fit deixa sobras minúsculas que nenhum registro consegue usar (se o menor registro tem 10 bytes, uma sobra de 5 é inútil). O worst-fit tenta manter a sobra útil. Nenhuma estratégia elimina a fragmentação externa, então ainda juntamos buracos vizinhos e compactamos.

Para ficar claro sobre os dois tipos de desperdício em um arquivo de registros: a fragmentação interna é o desperdício dentro de uma área alocada (o preenchimento de um registro de tamanho fixo). A fragmentação externa é o desperdício entre áreas alocadas, em buracos pequenos demais para usar. Registros de tamanho fixo sofrem só a interna. Registros de tamanho variável trocam a interna pela externa.

Compressão: deixar o arquivo menor

Notação compacta. Troque um valor legível por um código binário com só os bits necessários. Para n valores diferentes são necessários teto(log2 n) bits. Para 100 valores: 2^6 = 64 é pouco e 2^7 = 128 basta, então 7 bits. O arquivo encolhe, mas um editor de texto não consegue mais lê-lo, e todo programa precisa da tabela de códigos.

Codificação por carreiras (RLE, run-length encoding). Uma carreira de bytes iguais vira um código curto: um marcador, o valor e a contagem. Na versão usada aqui uma carreira de 4 ou mais bytes iguais vira 3 bytes, e carreiras menores são copiadas como estão (um código de 3 bytes não compensa para 2 ou 3 bytes). Exemplo, com marcador FF: os bytes 41 41 41 41 41 42 43 43 viram FF 41 05 (os cinco 41), 42, 43 43, ou seja, 3 + 1 + 2 = 6 bytes em vez de 8. Dados sem repetição não encolhem. O RLE funciona bem em imagens com áreas uniformes e em registros cheios de preenchimento.

Codificação de Huffman. Dê códigos curtos aos símbolos frequentes e códigos longos aos raros. Monte uma árvore: junte os dois nós menos frequentes em um nó novo cujo peso é a soma deles, e repita até sobrar uma árvore. O código de um símbolo é o seu caminho desde a raiz (esquerda = 0, direita = 1).

frequências: A 40, B 30, C 20, D 10  (total 100)

 passo 1: C + D = 30
 passo 2: B + (CD) = 60
 passo 3: A + 60 = 100

            (100)
            /   \
          A(40)  (60)          A = 0
                 /  \          B = 10
               B(30) (30)      C = 110
                     /  \      D = 111
                  C(20) D(10)

O tamanho do arquivo codificado é a soma de frequência x comprimento do código: 40x1 + 30x2 + 20x3 + 10x3 = 190 bits (um código fixo de 2 bits precisaria de 200). Um atalho: a soma também é igual aos pesos de todos os nós internos, 30 + 60 + 100 = 190. Um código de Huffman é livre de prefixo: nenhum código é o começo de outro. Isso importa porque o decodificador precisa saber onde cada código termina. Com a propriedade do prefixo, ler da esquerda para a direita nunca é ambíguo e nenhum bit é gasto em separadores. Na árvore isso significa apenas que os símbolos ficam só nas folhas.

Esses números foram medidos neste repositório, em um arquivo de registros de tamanho fixo com muito preenchimento. O RLE tira o preenchimento e o Huffman aproveita as frequências desiguais dos bytes, e usar um depois do outro é o melhor.

Índices: primário, secundário, listas invertidas

Achar um registro lendo o arquivo todo é lento. Um livro resolve isso com um sumário no começo. Um índice é esse sumário para um arquivo de dados.

O índice simples (primário)

Um índice simples é uma lista de entradas pequenas de tamanho fixo (chave, endereço do registro), ordenada pela chave. O arquivo de dados continua na ordem em que os registros chegaram. O índice separa duas coisas: a ordem de busca (no índice) e os dados (sem mudar). O endereço pode ser um RRN ou um offset em bytes.

Por que a busca binária funciona no índice mas não no arquivo de dados: ela precisa dos itens em ordem de chave e de um jeito de saltar direto para o item do meio. Registros de tamanho variável na ordem de chegada não oferecem nenhum dos dois. O índice oferece os dois e entrega o endereço, então o registro é lido com um seek.

Uma busca binária descarta metade do que resta a cada passo. Para N entradas o pior caso é piso(log2 N) + 1 entradas examinadas. Exemplo: N = 1.000 e 2^9 = 512 < 1.000 <= 1.024 = 2^10, então no máximo 10 entradas. Na memória isso não é nada. Mas se o índice está no disco, 10 ou 17 acessos por busca ainda são muitos, e é por isso que existem as árvores B.

Mantendo o índice correto

Se o índice fica na memória e só é gravado no disco ao fechar o arquivo, há um perigo: o programa pode falhar e deixar o índice do disco velho. A solução é uma flag de desatualizado no cabeçalho do arquivo de índice. Ligue-a no disco antes da primeira alteração de uma sessão e desligue-a quando o índice for gravado. Se a flag estiver ligada ao abrir o arquivo, a última sessão não terminou bem. Como o índice pode ser montado a partir dos dados, o programa reconstrói o índice lendo o arquivo de dados.

Índices secundários

A chave primária identifica um registro. Mas as pessoas perguntam por outras coisas: todas as músicas de um compositor, todos os clientes de uma cidade. Um índice secundário é ordenado por um desses campos. Como o valor pode se repetir, a resposta é uma lista de registros.

Listas invertidas

Em uma lista invertida o índice secundário tem uma entrada de tamanho fixo por chave secundária, com a posição do primeiro elemento de uma lista encadeada. A lista fica em outro arquivo. Cada elemento guarda uma chave primária e a posição do próximo elemento (-1 significa o fim).

índice secundário        arquivo de listas (posição: chave primária, próximo)
CIDADE -> início
NATAL  -> 2              0: P40, 3
RECIFE -> 0              1: P77, -1
                         2: P10, 1
                         3: P55, -1

busca RECIFE: começa em 0 -> P40, vai a 3 -> P55, próximo -1: fim
resultado, na ordem da lista: P40, P55

Adicionar um registro acrescenta um elemento ao arquivo de listas e muda um ponteiro. Nada é deslocado. O preço: os elementos de uma lista ficam espalhados pelo arquivo.

A lista guarda chaves primárias, não endereços. Isso se chama ligação tardia (late binding): o endereço só é descoberto na hora da busca, passando pelo índice primário. Uma busca secundária custa uma consulta a mais, mas quando o arquivo de dados é compactado e os registros mudam de endereço, só o índice primário precisa ser corrigido. Os índices secundários continuam corretos porque as chaves primárias não mudaram.

Combinando buscas: processamento cosequencial

Se cada lista está ordenada pela chave primária, duas listas podem ser combinadas em uma única passada. Compare o item atual de cada lista e avance a que tem a chave menor. Considere CIDADE = RECIFE -> 10, 20, 30, 40 e ANO = 2020 -> 20, 25, 40, 50, 60.

• E (matching, casamento): chaves que aparecem nas duas listas: 20 e 40. São 2 chaves.
• OU (merging, intercalação): toda chave vista, uma vez: 10, 20, 25, 30, 40, 50, 60. São 4 + 5 - 2 = 7 chaves.
• Só depois de combinar as listas é que os registros são lidos, e só os que importam.

O mini-projeto file-organisation deste repositório faz exatamente isso: 10.500 registros, um índice primário buscado com no máximo 14 sondagens, e uma busca por cidade que lê cerca de 880 espaços pelo índice, contra 10.500 de uma varredura completa.

Árvores B

Uma árvore binária de busca tem dois filhos por nó e pode ser alta: um milhão de chaves precisam de cerca de 20 níveis. No disco cada nível é um acesso, então 20 acessos são demais. O truque é fazer cada nó tão grande quanto uma página de disco e colocar centenas de chaves nele. Essa é a árvore B.

Ordem e as regras

Neste resumo a ordem m é o número máximo de filhos de um nó (os livros diferem, então diga sempre qual definição usa). As regras:

• Um nó tem no máximo m filhos e portanto no máximo m - 1 chaves. As chaves de um nó estão em ordem, e as subárvores ficam entre elas.
• Todo nó, exceto a raiz, tem pelo menos teto(m/2) filhos, portanto pelo menos teto(m/2) - 1 chaves. Ordem 8: de 4 a 8 filhos, então de 3 a 7 chaves.
• A raiz tem pelo menos 2 filhos (a menos que seja uma folha).
• Todas as folhas estão no mesmo nível.

Uma árvore com h níveis, todos os nós cheios, tem 1 + m + m^2 + ... nós, cada um com m - 1 chaves, o que dá m^h - 1 chaves. A capacidade cresce exponencialmente com a altura. Ordem 5 e 3 níveis: 5^3 - 1 = 124 chaves.

Escolhendo a ordem

No disco a ordem é o maior número de filhos que cabe em uma página. Exemplo: uma página de 4.096 bytes, cabeçalho de 12 bytes, chaves de 4 bytes e ponteiros de 4 bytes. Precisamos de 12 + 4(m - 1) + 4m <= 4.096, então 8m <= 4.088 e m <= 511. Conferindo: 12 + 4 x 510 + 4 x 511 = 4.096. Chaves menores dão ordem maior e árvore mais baixa. Por isso os índices preferem chaves curtas.

Quão alta a árvore pode ficar?

O pior caso é quando todo nó tem o mínimo. Chame c = teto(m/2). A raiz tem 1 chave e 2 filhos, e os outros nós têm pelo menos c - 1 chaves. Considere a ordem 10 (c = 5). Com 3 níveis o menor número de chaves é 1 (raiz) + 2 x 4 (dois nós) + 10 x 4 (dez nós) = 49, e com 4 níveis é 249. Então uma árvore B de ordem 10 com 100 chaves pode ter no máximo 3 níveis. Para ordem 200 e um milhão de chaves, a árvore tem no máximo 3 níveis: uma busca lê no máximo 3 nós, e 2 se a raiz ficar na memória.

Inserção: sempre em uma folha, e a divisão

Uma chave nova vai para a folha certa. Se a folha fica com chaves demais (overflow), ela é dividida: a chave do meio sobe para o pai e o resto forma dois nós. Se o pai estoura, ele também se divide. Se a divisão chega à raiz, cria-se uma raiz nova com uma única chave. Esta é a única maneira de uma árvore B crescer em altura. Por isso todas as folhas ficam no mesmo nível: a árvore cresce pelo topo, por consequência de como é construída, não por um conserto depois.

Convenção do quiz: um nó 'estoura' quando fica com uma chave a mais que o máximo (m chaves). Então a chave do meio sobe. Com um número par de chaves, o nó da esquerda fica com a primeira metade e a chave logo depois sobe.

ordem 4 (máx. 3 chaves). Insere 8 na folha [5 | 6 | 7]:

   antes:         [ 20 ]                  a folha [5 | 6 | 7] está cheia
                  /    \
          [5|6|7]      [30|40]

   a folha fica com 4 chaves: 5 6 7 8  -> overflow
   divisão: esquerda [5|6], a terceira chave 7 sobe, direita [8]

   depois:        [ 7 | 20 ]
                 /    |     \
            [5|6]   [8]   [30|40]

Remoção

1. Chave em um nó interno: troque-a pelo seu sucessor (ou antecessor), que sempre está em uma folha, e remova este. Assim toda remoção termina em uma folha.
2. Folha abaixo do mínimo: tente primeiro a redistribuição. Se um irmão adjacente tem mais que o mínimo, o separador do pai desce para a folha e a chave mais próxima do irmão sobe para ocupar o lugar dele.
3. Se nenhum irmão adjacente pode ceder uma chave, faça a concatenação: junte a folha, o separador e o irmão em um só nó. O pai perde uma chave e também pode ficar abaixo do mínimo, então o problema pode subir.

A árvore B+

Em uma árvore B+ os nós internos guardam só cópias de chaves para guiar a busca (sem dados), e todas as chaves e dados ficam nas folhas, que são ligadas em ordem. Como os nós internos não carregam dados, cabem mais separadores por página, então a árvore é mais baixa. Para uma consulta por faixa (todas as chaves de 100 a 900) você busca a primeira chave e depois segue os links das folhas sem voltar para cima: um acesso por folha. É por isso que bancos de dados usam árvores B+ para consultas por faixa e para ordenar por um campo indexado.

Ordenação externa

Como ordenar um arquivo maior que a memória? Se você carrega tudo, o programa morre. Se ordena no lugar, pulando de um ponto a outro, cada comparação é um acesso ao disco, e isso é 100.000 vezes mais lento que a memória. A ordenação externa por intercalação (external merge sort) faz duas promessas: o uso de memória não depende do tamanho do arquivo, e o arquivo é sempre lido e escrito em sequência.

Fase 1: gerar runs

Leia um pedaço do tamanho da memória, ordene-o na memória e grave-o como uma run: um arquivo ordenado. Repita até a entrada acabar. Se o arquivo tem N registros e a memória comporta M, o número de runs é teto(N / M). Exemplo: 2.000.000 registros e espaço para 150.000 dão 2.000.000 / 150.000 = 13,3, então 14 runs (13 cheias e uma menor).

Fase 2: intercalar as runs

Leia todas as runs do começo ao fim ao mesmo tempo. Grave sempre o menor dos registros da frente. Um heap de mínimo guarda uma entrada por run (o registro atual dessa run). O topo é o menor: grave-o, leia o próximo registro da mesma run e deixe-o descer até o seu lugar. Isso custa cerca de log2 k comparações por registro, em vez de k - 1 olhando todas as k frentes. Um heap de 64 itens tem 6 níveis, então um registro desce no máximo 6 passos, não 63 comparações. A memória usada é proporcional a k, não ao arquivo.

run 0:  3  8  9 ...     o heap guarda a frente de cada run:
run 1:  1  4  7 ...     [ 3 , 1 , 2 ]   menor = 1 (run 1)
run 2:  2  5  6 ...     grava 1, lê 4 da run 1:
                        [ 3 , 4 , 2 ]   menor = 2 (run 2) ...

saída: 1 2 3 4 5 6 ...

Várias passadas

Se a memória permite só k runs de cada vez (o fan-in), uma passada de intercalação junta grupos de k runs em runs mais longas. Depois de uma passada o número de runs é teto(R / k). O número de passadas é teto(log base k de R). Exemplo: 60 runs com fan-in 4: 60 -> 15 -> 4 -> 1, ou seja, 3 passadas. Não contamos a geração de runs entre as passadas de intercalação.

Cada passada lê e escreve o arquivo inteiro uma vez, e a geração de runs também. Então uma ordenação externa com 2 passadas de intercalação move o arquivo 3 vezes em cada direção: para um arquivo de 8 GB são 3 x 8 = 24 GB escritos. O número de passadas é o custo real.

A troca de um fan-in grande

Um fan-in maior significa menos passadas. Mas a memória é dividida entre os k buffers de entrada, então cada buffer é menor e é reabastecido com mais frequência. Em um disco magnético cada reabastecimento de uma run diferente é um seek. Intercalar 800 runs de uma vez pode ser mais lento do que intercalar em duas etapas (por exemplo 25 grupos de 32 runs e depois as 25 resultantes), embora o segundo jeito leia e escreva tudo duas vezes: suas leituras são mais longas e mais sequenciais.

Esses resultados vêm do mini-projeto external-sorting deste repositório (média de 7 execuções). Passar de fan-in 2 para 16 reduz as passadas de 6 para 2 e o tempo pela metade, mais ou menos. O fan-in 64 economiza mais uma passada mas não é mais rápido, porque a memória é dividida em 65 buffers pequenos. A variação entre execuções foi grande em uma máquina compartilhada, então diferenças pequenas não são diferenças de verdade.

Seleção por substituição: runs mais longas

Uma fase 1 mais esperta usa um heap de M registros. Grave o menor registro do heap e leia um registro novo no lugar dele. Se o registro novo é menor que o que acabou de ser gravado, ele não pode entrar na run atual e fica reservado para a próxima. O resultado depende do quanto a entrada já está ordenada:

Exemplo: 50.000 registros em ordem decrescente e M = 1.000 dão 50 runs. Menos runs significam uma intercalação mais barata.

Juntando tudo

Toda ideia desta área responde a uma pergunta: como manter baixo o número de acessos ao disco? Aqui está a história toda em uma tabela.

Erros para evitar

• Achar que lseek lê o disco. Ele só muda o offset.
• Achar que o ctime é a data de criação. É a última mudança do i-node.
• Achar que um link físico atravessa partições. O número do i-node só tem sentido dentro de um sistema de arquivos.
• Esquecer o bloco de dados ao contar as leituras de uma busca por i-node, ou esquecer que por suposição o i-node já está na memória.
• Começar o RRN em 1 quando o problema diz 0, ou esquecer o cabeçalho ao calcular um deslocamento.
• Esquecer o mais 1 no pior caso da busca binária, piso(log2 N) + 1.
• Misturar a ordem de uma árvore B (filhos) com o número de chaves (uma a menos).
• Achar que um journal protege o conteúdo dos seus arquivos. Um journal de metadados protege as estruturas.

Para aprender mais

• Operating Systems: Three Easy Pieces tem capítulos gratuitos sobre discos, arquivos, implementação de sistemas de arquivos, journaling e flash.
• Files are hard, de Dan Luu, mostra como é difícil gravar um arquivo com segurança.
• ext4 Data Structures and Algorithms descreve o layout real de um sistema de arquivos de produção.
• SQLite Database File Format mostra como tabelas e índices são guardados como páginas de árvore B em um único arquivo.