Facebook Haystack: armazenamento de fotos

01 · CONTEXTO

Fotos: escritas uma vez, lidas muitas vezes

O paper do Haystack reporta que o Facebook guardava mais de 260 bilhões de imagens, o que equivale a mais de 20 petabytes. Cada foto enviada gera quatro imagens de tamanhos diferentes. Os usuários enviavam um bilhão de fotos novas por semana, e o serviço entregava mais de um milhão de imagens por segundo no pico.

A carga é de dados escritos uma vez, lidos com frequência, nunca modificados e raramente apagados. A equipe construiu um armazenamento próprio porque sistemas de arquivos tradicionais têm desempenho ruim nessa carga. As fotos são acessadas com mais intensidade logo depois do envio.

02 · O PROBLEMA

Por que o desenho com NFS não bastava

O desenho NFS guardava cada foto em um arquivo próprio em appliances NAS comerciais. Ler uma foto exigia várias operações de disco: traduzir o nome em inode, ler o inode e ler o arquivo.

Com milhares de arquivos por diretório, era comum passar de dez operações de disco para recuperar uma imagem. Com centenas de imagens por diretório, o sistema ainda incorria em geral em três operações de disco por imagem.

1. O servidor web monta a URL de cada imagem, apontando o navegador para um local de download.

2. Se a CDN tem a imagem em cache, responde na hora; senão, usa a URL para buscar a foto nos sistemas de armazenamento do site.

3. O servidor Photo Store extrai da URL o volume e o caminho do arquivo, lê por NFS e devolve o resultado à CDN.

4. As requisições da cauda longa quase sempre falham na CDN e chegam ao armazenamento, onde as operações de disco para metadados limitavam a taxa de leitura.

Cachear mais não resolveu. O cache de file handles em memcache trouxe só uma melhoria pequena, porque fotos menos populares têm menos chance de estar em cache. O armazenamento acaba processando a cauda longa de fotos menos populares, que não estão na CDN e provavelmente falham nos caches; por isso, focar só em cache tem impacto limitado para reduzir operações de disco.

03 · A IDEIA

Menos metadados por foto, tudo na memória

O Haystack reduz drasticamente a memória usada para metadados de sistema de arquivos, o que torna prático mantê-los todos em memória principal. A técnica central é simples: ele guarda várias fotos em um único arquivo e, portanto, mantém arquivos muito grandes.

Na abordagem NAS, cada arquivo exige ao menos um inode, que tem centenas de bytes. A equipe decidiu reduzir o metadado por foto para que ter memória suficiente fosse muito mais econômico do que comprar mais appliances NAS.

O Haystack busca alta vazão e baixa latência exigindo no máximo uma operação de disco por leitura. Mesmo assim, há casos de canto em que o sistema de arquivos exige mais de uma operação de disco, quando os dados cruzam extents ou limites de RAID.

04 · ARQUITETURA

Directory, Cache e Store

A arquitetura tem três componentes centrais: Store, Directory e Cache. O Store guarda as fotos e é o único componente que gerencia os metadados de sistema de arquivos. O Directory mantém o mapeamento de volumes lógicos para físicos e outros metadados de aplicação. O Cache funciona como a CDN interna e protege o Store dos pedidos das fotos mais populares.

1. Ao visitar uma página, o servidor web usa o Directory para montar a URL de cada foto.

2. O Directory decide se o pedido vai à CDN ou ao Cache, o que permite ajustar a dependência de CDNs.

3. Se a CDN não localiza a foto, remove o próprio endereço da URL e contata o Cache.

4. Em caso de falta no Cache, ele remove o próprio endereço da URL e pede a foto à máquina Store indicada.

5. A máquina Store consulta os metadados em seus mapeamentos em memória; se a foto não foi apagada, vai ao deslocamento certo do arquivo de volume, lê o needle inteiro e verifica o cookie e a integridade dos dados.

6. O objetivo do desenho é exigir no máximo uma operação de disco por leitura.

O Cache só guarda uma foto se o pedido vier direto do usuário e não da CDN, entre as condições descritas. A razão: a experiência com o desenho NFS mostrou que cache depois da CDN é ineficaz.

O cookie elimina ataques que tentam adivinhar URLs válidas de fotos.

05 · O STORE

Volumes, needles e o mapeamento em memória

Um volume físico pode ser pensado como um arquivo muito grande. Uma máquina Store representa um volume físico como um superbloco seguido de uma sequência de needles, e cada needle representa uma foto.

Cada máquina Store mantém uma estrutura em memória para cada um de seus volumes. O ponto-chave do desenho é obter nome do arquivo, deslocamento e tamanho de uma foto sem operações de disco.

As escritas são feitas por anexação. A máquina anexa de forma síncrona as imagens de needles aos arquivos de volume e atualiza os mapeamentos em memória. Como o Haystack não permite sobrescrever needles, uma foto só é modificada ao se adicionar um needle atualizado com a mesma chave e chave alternativa, e a versão mais recente de um needle em um volume físico é a de maior deslocamento.

Na exclusão, a máquina marca o flag de apagado no mapeamento em memória e, de forma síncrona, no arquivo de volume.

06 · ÍNDICE E FALHAS

Índice, compactação e recuperação

Reconstruir o mapeamento lendo todos os volumes é demorado, e os arquivos de índice permitem montá-lo rapidamente, encurtando o reinício. A escrita do needle é síncrona, mas o registro no arquivo de índice é assíncrono.

Esse atalho tem consequências. Needles sem registro de índice correspondente são chamados de órfãos, e no reinício a máquina examina cada órfão em sequência, cria o registro de índice correspondente e o anexa ao arquivo de índice. Os registros do índice não refletem fotos apagadas, então a máquina pode recuperar uma foto já apagada; se o needle está marcado como apagado, ela atualiza o mapeamento em memória e avisa o Cache que o objeto não foi encontrado.

A compactação é uma operação online que recupera o espaço usado por needles apagados e duplicados. Ela copia needles para um arquivo novo, pulando duplicados e apagados. Ao longo de um ano, cerca de 25% das fotos são apagadas.

1. O usuário envia primeiro os dados a um servidor web.

2. Em seguida, o servidor web pede ao Directory um volume lógico habilitado para escrita.

3. Por fim, o servidor atribui um id único à foto e a envia a cada volume físico mapeado ao volume lógico; cada máquina anexa o needle ao seu volume.

4. Uma tarefa em segundo plano, o pitchfork, verifica periodicamente a saúde de cada máquina Store.

5. Se uma máquina Store, aqui a B, falha de forma consistente nas checagens, o pitchfork marca como somente leitura todos os volumes lógicos dela.

Ao guardar uma foto em um volume lógico, ela é escrita em todos os volumes físicos correspondentes, e o Haystack replica cada foto em locais geograficamente distintos. Se uma máquina é perdida, outra entra no lugar e os dados são copiados para manter a redundância. Em casos mais pesados, o bulk sync redefine os dados de uma máquina Store com os arquivos de volume fornecidos por uma réplica. Ele acontece raramente, mas resulta em horas de tempo médio de recuperação.