Timeline do Facebook

01 · CONTEXTO

De dias de atividade para décadas

As páginas de perfil anteriores do Facebook mostravam alguns dias ou semanas de atividade. Com a Timeline, o time precisou pensar em anos e até décadas: era preciso varrer, agregar e ranquear posts, compartilhamentos, fotos e check-ins para destacar os eventos mais significativos ao longo de anos de atividade.

O cronograma era muito agressivo. Uma das prioridades foi eliminar o risco técnico, mantendo o sistema o mais simples possível e usando tecnologias já provadas dentro da empresa. O time construiu sobre quatro tecnologias centrais: o MySQL/InnoDB no armazenamento, o Multifeed (a tecnologia que alimenta o News Feed) no ranking, o Thrift na comunicação e o memcached no cache.

O ponto de design mais interessante não é nenhuma dessas peças, e sim a forma como os dados foram organizados para elas. É o assunto da próxima seção.

02 · O PROBLEMA

Por que o modelo normalizado não servia

Antes da Timeline, os dados eram altamente normalizados, o que exigia muitas idas ao banco; por isso o desenho dependia de cache para manter tudo rápido. Quando um dado não estava no cache, era improvável que estivesse agrupado no disco, e isso gerava muito IO aleatório, potencialmente lento.

Ranquear anos de atividade nesse modelo teria exigido manter todo o conjunto de dados em cache, inclusive o de baixo valor, que nem era exibido. A análise do High Scalability resume assim: dado o volume e o quanto dele é frio, guardar tudo em cache não é um bom desenho.

1. O navegador pede o perfil à camada web.

2. Com dados normalizados, o desenho dependia do cache para manter tudo rápido.

3. Quando o dado não estava no cache, era improvável que estivesse agrupado no disco, o que gerava IO aleatório potencialmente lento.

4. Para ranquear anos de atividade seria preciso manter todo o conjunto de dados em cache, inclusive o de baixo valor.

03 · DESNORMALIZAR

Linhas que já carregam o ranking

A resposta foi uma desnormalização massiva, para que todos os dados necessários ao ranking estivessem disponíveis em poucas requisições eficientes em IO. Cada linha do banco passou a conter a informação sobre a ação e metadados de ranking suficientes para ser selecionada ou descartada sem buscas adicionais.

Os dados ficam ordenados por (usuário, tempo) em disco, e o InnoDB faz um bom trabalho ao lê-los em fluxo com uma consulta por faixa de chave primária. O High Scalability resume o ganho da desnormalização: ela reduz o IO aleatório ao reduzir as idas ao banco.

04 · LEITURA

Agregador local e dois tipos de cache

Sobre o banco foi construído o agregador da Timeline. Ele começou como versão modificada do agregador do Multifeed e hoje roda localmente em cada servidor de banco, o que permite esgotar a capacidade dos discos sem mandar pela rede dados que não serão exibidos. Seus geradores de histórias vão de agrupar check-ins próximos a ranquear atualizações de status, são escritos em C++ e rodam as análises em poucos milissegundos.

1. O navegador pede a Timeline à camada web.

2. Resultados de consultas grandes, como ranquear toda a atividade de um ano, são pequenos e ficam no memcached por muito tempo sem invalidação.

3. O agregador roda localmente em cada servidor de banco.

4. Os geradores de histórias leem as linhas desnormalizadas, ordenadas por usuário e tempo, e agrupam e ranqueiam.

5. Dados que não serão exibidos não são enviados pela rede.

6. Na Atividade Recente, que muda com frequência, o cache é de linhas: buffer pool do InnoDB em RAM e Flashcache em flash.

05 · MIGRAÇÃO E EQUIPE

Chegar ao novo modelo e entregar rápido

Havia dezenas de formatos de dados legados que evoluíram ao longo dos anos, e uma linguagem própria expressava as regras de conversão, com um compilador que a transformava em PHP executável. O novo esquema adotou um modelo de dados compatível com o Multifeed, mais flexível e com mais contexto semântico.

Os dados de atividade não recente estavam em armazenamento de rede lento. Uma versão somente leitura do MySQL, em centenas de servidores, copiou esses dados em semanas em vez de meses. As tabelas de junção foram consolidadas em uma camada de bancos só com flash, consultada em paralelo por um proxy.

1. Os dados de origem estavam em formatos legados e, no caso da atividade não recente, em armazenamento de rede lento.

2. Uma versão somente leitura do MySQL em centenas de servidores extraía os dados com pressão máxima de IO.

3. Regras escritas em uma linguagem própria, compiladas para PHP, convertiam os formatos antigos.

4. As tabelas de junção ficaram em bancos só com flash, e um proxy consultava toda a camada em paralelo.

5. O resultado são linhas desnormalizadas em um modelo compatível com o Multifeed.

A Timeline começou como projeto de hackathon no fim de 2010, com dois engenheiros em tempo integral, um estagiário e um designer que construíram uma demo em uma única noite. O time completo foi dividido em design, front-end, infraestrutura e migração de dados, e as frentes andaram em paralelo: o time desenhava protótipos de UI sobre o backend antigo e fazia testes de carga simulados para validar as estimativas de capacidade. Da primeira reunião de revisão de infraestrutura ao teste de carga com 100% do backend foram apenas seis meses.