Facebook TAO: o grafo social em cache

01 · CONTEXTO

Um grafo lido o tempo todo

Cada pessoa vê conteúdo sob medida, e cada item passa por verificações de privacidade que levam em conta quem está vendo. As dependências de dados são resolvidas e a privacidade é checada a cada visualização do conteúdo e, tanto quanto possível, o grafo é puxado (pull) em vez de empurrado.

Nas medições do paper, as leituras dominam e apenas 0,2% dos pedidos envolvem escrita; o TAO sustenta um bilhão de leituras por segundo sobre um conjunto de dados mutável de muitos petabytes.

02 · ANTES DO TAO

O cache lookaside e onde ele falhava

Antes do TAO, os servidores web acessavam o MySQL diretamente para ler e escrever o grafo social, usando o memcache como cache lookaside. Nesse desenho, o mapeamento de dados e a invalidação do cache ficam em código de cliente implantado com frequência.

1. O servidor web acessa o MySQL diretamente e usa o memcache como cache lookaside.

2. O mapeamento de dados e a invalidação do cache são calculados no código do cliente, implantado com frequência.

3. Para uma lista de arestas, o cache chave-valor obriga a buscar a lista inteira, e mudar uma aresta exige recarregar a lista toda.

O paper aponta problemas fundamentais dessa arquitetura quando os dados são um grafo. Primeiro, listas de arestas: as consultas sempre buscam a lista inteira e a mudança de uma única aresta obriga a recarregá-la. Segundo, lógica de controle distribuída: ela roda em clientes que não se comunicam entre si, o que aumenta o número de modos de falha. Terceiro, consistência read-after-write cara: o MySQL do Facebook usa replicação assíncrona mestre/escravo, o que é um problema para caches em datacenters que usam réplica.

O TAO move a lógica de controle para dentro do cache. Ele continua usando MySQL para persistência, mas medeia o acesso ao banco e usa um cache próprio que entende o grafo.

03 · MODELO DE DADOS

Objetos e associações

O TAO modela o grafo com objetos e associações. Objetos são nós tipados e associações são arestas direcionadas e tipadas entre objetos. Ambos podem conter dados como pares chave-valor.

No máximo uma associação de um dado tipo pode existir entre dois objetos. Para tipos de associação que têm inverso, criações, atualizações e remoções são acopladas automaticamente a uma operação na associação inversa.

As consultas se organizam em listas de associações: todas as associações de um mesmo id1 e atype, em ordem decrescente do campo de tempo. O paper observa que, no grafo social, a maior parte dos dados é antiga, mas muitas consultas pedem o subconjunto mais novo. Cada consulta tem um limite superior por tipo, tipicamente 6.000, e para listas mais longas o cliente precisa emitir várias consultas.

04 · ARQUITETURA

Armazenamento, líderes e seguidores

O TAO se separa em duas camadas de cache e uma camada de armazenamento. Como o volume de dados excede o que cabe em um único servidor MySQL, os dados são divididos em shards lógicos. Uma associação fica no shard do seu id1, de modo que toda consulta de associação pode ser atendida por um único servidor.

Camadas de cache grandes são mais sujeitas a pontos quentes e têm crescimento quadrático de conexões todos-com-todos. O paper divide o cache em dois níveis, uma camada de líderes e várias camadas de seguidores.

1. O cliente fala com o seguidor mais próximo e nunca contacta líderes diretamente.

2. Em uma falha de leitura ou em uma escrita, o seguidor encaminha o pedido a um líder.

3. O líder lê e escreve na camada de armazenamento e não emite consultas concorrentes sobrepostas ao banco.

4. Depois de uma atualização, o líder enfileira mensagens de invalidação para os seguidores correspondentes, de forma assíncrona.

Cada shard tem um líder e todas as escritas do shard passam por ele, então esse caminho é naturalmente consistente. Os líderes serializam as escritas concorrentes que chegam dos seguidores e, por mediarem todos os pedidos de um id1, estão bem posicionados para proteger o banco de thundering herds.

Os shards são mapeados para servidores de cache dentro de uma camada com hash consistente. Para equilibrar carga entre seguidores, o TAO usa shard cloning, em que as leituras de um shard são servidas por vários seguidores. Além disso, muitos objetos têm mais de 6.000 associações do mesmo atype, e por isso o TAO não coloca em cache a lista completa.

05 · ESCALA GEOGRÁFICA

Várias regiões, um único grafo

O TAO é implantado no Facebook como uma única instância geograficamente distribuída. O grafo social é fortemente interligado e não é possível agrupar usuários de modo que pedidos entre partições sejam raros. Seria proibitivamente caro ter réplicas completas em todo datacenter; a solução do paper é escolher datacenters agrupados em poucas regiões, onde a latência interna é pequena (tipicamente menor que 1 milissegundo), e guardar uma cópia completa do grafo por região.

Como as falhas de leitura dos seguidores são 25 vezes mais frequentes que as escritas nas cargas do paper, a escolha foi uma arquitetura mestre/escravo que exige que as escritas sejam enviadas ao mestre.

1. Na região escrava, o seguidor encaminha falhas de leitura ao líder local, que consulta o banco local, seja ele mestre ou escravo. Isso significa que a latência de leitura independe da latência entre regiões.

2. Uma escrita feita na região escrava é encaminhada pelo líder local ao líder da região do banco mestre.

3. Como o TAO grava no MySQL de forma síncrona, o banco mestre é uma fonte consistente de verdade.

4. As mensagens de consistência de cache vão embutidas no fluxo de replicação do banco.

5. As mensagens são entregues na região logo depois que a transação foi replicada para o banco escravo, e chegam ao líder escravo; entregá-las antes criaria inconsistências de cache.

A região mestre é controlada separadamente para cada shard e é trocada automaticamente para se recuperar da falha de um banco. As escritas que falham durante a troca são reportadas ao cliente como falhas e não são retentadas. No Facebook, o TAO e o memcache usam o mesmo pipeline para entregar invalidações.

06 · CONSISTÊNCIA, FALHAS E NÚMEROS

O que o TAO troca por disponibilidade

O TAO fornece consistência eventual enviando de forma assíncrona mensagens de manutenção de cache do líder aos seguidores. Em operação normal, com no máximo uma falha por pedido, oferece consistência read-after-write dentro de uma única camada. A defasagem de replicação costuma ser menor que um segundo.

O banco mestre é uma fonte consistente de verdade porque o TAO grava no MySQL de forma síncrona. Leituras podem ser marcadas como críticas e então são encaminhadas à região mestre.

Diante de uma falha, o TAO contorna o servidor com problema preservando disponibilidade e desempenho ao custo da consistência.

Nas medições do paper, a taxa de acerto geral de leituras foi de 96,4%. Em um período de 90 dias, a fração de consultas TAO que falharam, medida no servidor web, foi de 4,9 × 10⁻⁶, com a ressalva de que a falha de uma consulta pode impedir o cliente de emitir outra. A latência média de escrita foi de 12,1 ms na região do mestre e de 74,4 ms na região remota, pois escritas de outras regiões incluem uma ida e volta entre regiões.