Conceitos
Armazenamento de muitos objetos pequenos (Haystack)
Intuição
Imagine uma biblioteca em que cada folha solta tem sua própria ficha no catálogo: o bibliotecário gasta mais tempo procurando fichas do que lendo folhas. Se as folhas forem juntadas em poucos volumes encadernados e o catálogo guardar só uma anotação curta (em que volume e em que posição cada folha está), cabe tudo na mesa dele e cada folha é achada de uma vez. A ideia é gastar o esforço lendo o conteúdo, não procurando por ele.
Como funciona
No design anterior do Facebook, cada foto era um arquivo em um sistema de arquivos POSIX acessado por NFS; ler uma foto exigia localizar o inode antes de ler os dados, e os metadados (como permissões, que fotos escritas uma vez não usam) não cabiam todos em memória. O Haystack agrupa muitas fotos em poucos arquivos enormes, os volumes físicos, e cada foto vira um registro chamado needle, anexado ao fim do arquivo depois de um superbloco. Para cada volume, a máquina Store mantém em memória um mapa do identificador da foto para o offset e o tamanho do needle, então uma leitura consulta a memória e faz no máximo uma operação de disco, sem navegar por diretórios nem inodes. Os autores estimam cerca de 10 bytes de metadado em memória por foto (40 bytes para as quatro versões redimensionadas da mesma imagem), contra os 536 bytes do xfs_inode_t citado no paper. Como o volume só recebe appends, a escrita é sequencial: uma deleção apenas marca o needle como apagado e o espaço volta numa compactação posterior, que copia o volume descartando needles apagados e duplicados; uma foto alterada é anexada de novo, e vale a versão de maior offset. Um arquivo de índice, checkpoint assíncrono do mapa, evita varrer o volume inteiro para reconstruí-lo após uma reinicialização. Um volume lógico reúne volumes físicos de máquinas diferentes que são réplicas entre si, e a escrita é enviada a todos eles. O GFS parte do mesmo princípio de manter os metadados pequenos o bastante para caber em memória, mas pelo lado oposto, com chunks fixos de 64 MB, para arquivos enormes, de modo que o master guarde pouco por chunk e o cliente faça muitas operações sequenciais com uma única consulta a ele.
Na prática
Essa abordagem serve a cargas de objetos pequenos escritos uma vez, lidos muitas vezes e raramente apagados, como as fotos do Facebook, em que se abre mão de permissões, sobrescrita e hierarquia de diretórios em troca de throughput e eficiência de memória. O custo são pontos que o próprio paper e as críticas ao design destacam: apagar exige compactação (fotos apagadas ocupam espaço por um tempo), a recuperação de falhas parece em boa parte manual e o Directory pode ser um ponto único de falha se não for replicado. A lição geral é que, antes de escalar com mais hardware, vale reduzir o custo de metadados por objeto até caberem em memória.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.