Papers
Finding a Needle in Haystack: Facebook's Photo Storage
Doug Beaver, Sanjeev Kumar, Harry C. Li, Jason Sobel, Peter Vajgel · 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2010, 2010
O problema: um arquivo por foto faz o disco gastar operações com metadados
O Facebook precisava armazenar e servir uma quantidade enorme de fotos: a página de pesquisa do paper cita mais de 260 bilhões de imagens (acima de 20 petabytes), cerca de um bilhão de uploads novos por semana e picos acima de um milhão de imagens servidas por segundo. O design anterior guardava as fotos em appliances de armazenamento acessados por NFS, essencialmente um arquivo por foto em um sistema de arquivos POSIX. O problema, segundo os autores, é que esse modelo desperdiça operações de disco com metadados. Para ler um arquivo, o sistema precisa primeiro localizar seu inode e só depois ler os dados, então uma única leitura de foto pode custar mais de um acesso ao disco. Além disso, o sistema de arquivos mantém metadados como permissões, que uma aplicação de fotos escritas uma vez e nunca alteradas simplesmente não usa, e cada inode ocupa centenas de bytes que não cabem todos na memória. A motivação do Haystack é reduzir os metadados por foto ao ponto de caberem em memória principal, deixando o disco para ler os bytes da foto e não para procurá-la.
A ideia central: empacotar milhões de fotos em arquivos grandes com índice em memória
Em vez de um arquivo por foto, o Haystack agrupa muitas fotos dentro de poucos arquivos enormes, chamados volumes físicos. Cada máquina de armazenamento (o Store) gerencia vários desses volumes; um exemplo citado é um servidor de 10 TB dividido em 100 volumes de 100 GB. Dentro de um volume, cada foto é um registro chamado needle (agulha), anexado ao final do arquivo, depois de um superbloco inicial. Para cada volume, a máquina mantém em memória um mapa que traduz o identificador da foto para o deslocamento (offset) e o tamanho do needle no arquivo. Assim, uma leitura consulta a memória, descobre onde a foto está e faz uma única leitura de disco naquele ponto, 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 que o próprio paper cita. Essa mudança permite no máximo uma operação de disco por leitura, e o artigo reporta cerca de quatro vezes mais leituras por segundo que o sistema NAS anterior. Como os dados são imutáveis e só se faz append, a escrita é sequencial e simples.
Arquitetura: Directory, Cache e Store, e os caminhos de leitura e escrita
O sistema tem três componentes. O Haystack Store é a camada persistente, com os volumes descritos acima. O Haystack Directory mantém o mapeamento de volumes lógicos para volumes físicos, distribui as escritas entre os volumes lógicos e as leituras entre os físicos, decide se um pedido vai para a CDN ou para o Cache e marca volumes como somente leitura quando enchem ou por motivos operacionais. O Haystack Cache funciona como uma tabela hash distribuída indexada pelo ID da foto: em caso de miss, busca no Store. Um volume lógico agrupa volumes físicos de máquinas diferentes, que são réplicas entre si. Na leitura, o servidor web consulta o Directory e monta uma URL que carrega as informações de CDN, Cache, máquina e volume; o pedido passa pela CDN (que pode ser pulada), pelo Cache e, se necessário, chega ao Store, que verifica o cookie (um número aleatório embutido na URL e gravado no needle, que impede adivinhar URLs) antes de devolver os dados. Na escrita, o servidor web pede ao Directory um volume lógico com escrita habilitada e envia a foto a todos os volumes físicos daquele volume lógico, cada um anexando o needle ao seu arquivo. Segundo o paper, o Cache só guarda fotos pedidas diretamente pelo usuário e vindas de máquinas com escrita habilitada, protegendo-as de leituras, já que sistemas de arquivos lidam mal com leitura e escrita simultâneas.
Deleção, atualização, compactação e tolerância a falhas
Como os arquivos de volume são apenas de anexação, o Haystack trata mudanças de forma indireta. Uma deleção apenas marca o needle como apagado, tanto no mapa em memória quanto no arquivo do volume; o espaço só é recuperado depois por um processo de compactação, que copia o volume para um novo arquivo descartando needles apagados e duplicados. Needles nunca são sobrescritos: uma foto alterada (por exemplo, rotacionada) é anexada de novo com as mesmas chaves, e a versão com maior offset no mesmo volume é a mais recente. Para evitar reconstruir o mapa em memória varrendo todo o volume após uma reinicialização, cada volume tem um arquivo de índice, que é um checkpoint do mapa. Ele é atualizado de forma assíncrona e pode ficar defasado, mas os needles ainda não indexados ficam no fim do arquivo e são fáceis de localizar. Como o hardware é comum e falha com frequência (discos, controladoras RAID, placas-mãe), uma tarefa em segundo plano chamada pitchfork verifica periodicamente a saúde das máquinas Store; se uma apresenta problema, todos os seus volumes lógicos são marcados como somente leitura, e a causa é investigada manualmente. Um mecanismo de bulk sync restaura os dados de uma máquina falha a partir de uma réplica. As fotos também são replicadas entre datacenters geograficamente distintos.
Trade-offs, limites e legado
O Haystack é um exemplo claro de especializar o armazenamento para uma carga de trabalho: ele abre mão da generalidade de um sistema de arquivos (permissões, sobrescrita, hierarquia de diretórios) para ganhar throughput e eficiência de memória em dados escritos uma vez, lidos muitas vezes e raramente apagados. Esse ganho tem custo. Críticas comuns ao design apontam que a recuperação de falhas parece em boa parte manual, que o desenho é muito ajustado a uma carga específica, que apagar exige compactação (portanto fotos apagadas ocupam espaço por um tempo) e que o Directory pode ser um ponto único de falha se não for replicado. A ideia de agrupar objetos pequenos em arquivos grandes, com índice compacto em memória e escrita por append, aparece em outros sistemas de armazenamento de objetos, mas este resumo não confirma uma lista específica de sistemas derivados, então o leitor deve tratar o Haystack sobretudo como um estudo de caso: antes de escalar com hardware, vale reduzir o custo de metadados por objeto.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.