Papers
TAO: Facebook's Distributed Data Store for the Social Graph
Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, Venkat Venkataramani · USENIX Annual Technical Conference (ATC) 2013, 2013
O problema: servir o grafo social a partir de um cache lookaside
Antes do TAO, os servidores web do Facebook liam e escreviam o grafo social diretamente no MySQL, usando o memcache como cache lookaside: o código do cliente (PHP) consultava o cache, e em caso de miss ia ao banco e repovoava o cache. Esse desenho é ótimo para iterar rápido, mas o paper aponta três falhas fundamentais quando os dados são um grafo. Primeiro, listas de arestas: um cache chave-valor não representa bem listas, então qualquer mudança ou consulta obriga a buscar ou recarregar a lista inteira, e coordenar atualizações incrementais concorrentes é complicado. Segundo, lógica de controle distribuída: como ela roda em clientes que não conversam entre si, há mais modos de falha e fica difícil evitar thundering herds. Terceiro, consistência read-after-write cara: o MySQL usa replicação assíncrona master/slave, então uma escrita demora a aparecer na réplica local, e o remédio anterior (remote markers) exigia rastrear chaves sabidamente obsoletas. A motivação de fundo é que cada página é montada puxando (pull) dados do grafo e checando privacidade para o espectador no momento da leitura, o que gera uma carga extremamente dominada por leituras. O TAO foi construído como um serviço que implementa diretamente o modelo de objetos e associações, movendo a lógica de controle para dentro do próprio cache.
Modelo de dados e API: objetos, associações e listas ordenadas por tempo
O TAO modela o grafo com objetos (nós tipados) e associações (arestas direcionadas e tipadas). Cada objeto tem um id de 64 bits único entre todos os tipos e um tipo (otype). Uma associação é identificada pela tripla origem (id1), tipo de associação (atype) e destino (id2), e existe no máximo uma associação de um dado tipo entre dois objetos. Ambos podem carregar dados como pares chave-valor, e cada associação tem um campo de tempo de 32 bits central nas consultas. Arestas bidirecionais são modeladas como duas associações, e o TAO pode mantê-las sincronizadas se o tipo tiver um tipo inverso configurado. O objetivo declarado não é suportar todas as consultas de grafo, mas oferecer expressividade suficiente para a maioria das aplicações com implementação eficiente. As consultas giram em torno de listas de associação: todas as associações de um par (id1, atype), em ordem decrescente de tempo, aproveitando a localidade por tempo de criação (a maioria dos dados é antiga, mas a maioria das consultas quer o conteúdo mais recente). As operações incluem assoc_get, assoc_count, assoc_range (por posição e limite) e assoc_time_range (por faixa de tempo). Há um limite por atype no tamanho de uma consulta, tipicamente 6.000; listas maiores exigem várias consultas. Uma omissão notável na API de objetos é o compare-and-set, cuja utilidade é reduzida pela semântica de consistência eventual.
Arquitetura: shards, camada de cache e hierarquia líder/seguidor
O TAO separa duas camadas de cache de uma camada de armazenamento. O armazenamento persistente continua sendo o MySQL, e os dados são divididos em shards lógicos; cada id de objeto embute o shard que o hospeda, e uma associação fica no shard de seu id1, de modo que qualquer consulta de associação pode ser atendida por um único servidor. A camada de cache implementa a API completa: os servidores de cache formam uma tier, e cada requisição é roteada a um único servidor por shard. Os caches entendem a semântica do que guardam, então conseguem responder consultas nunca vistas (por exemplo, uma contagem em cache igual a zero basta para responder um range vazio). Para evitar tiers enormes, que sofrem com hot spots e comunicação todos-com-todos quadrática, o cache se divide em um nível de líderes e várias tiers de seguidores. Clientes falam só com seguidores; em miss de leitura ou escrita, o seguidor encaminha ao líder, que acessa o banco. Como todas as escritas de um shard passam por um único líder, ele serializa escritas concorrentes e também protege o banco de thundering herds, limitando consultas sobrepostas e pendentes. Escritas em associações com inversa podem envolver dois shards e o TAO não garante atomicidade entre as duas atualizações: se houver falha, pode sobrar uma associação sem inversa (hanging), reparada por um job assíncrono.
Escala geográfica e consistência: eventual por padrão, forte sob demanda
Com seguidores a milhares de quilômetros dos bancos, o tempo de ida e volta na rede viraria o gargalo. Como o paper mede que misses de leitura nos seguidores são 25 vezes mais frequentes que escritas, o TAO adota uma arquitetura master/slave por shard: cada região guarda uma cópia completa do grafo, as leituras e misses são atendidos localmente, e só as escritas são encaminhadas à região master, de modo que a latência de leitura independe da latência entre regiões. Isso favorece desempenho e disponibilidade ao custo de dados potencialmente desatualizados. Em operação normal, os objetos e associações são eventualmente consistentes: após uma escrita, o TAO garante a entrega eventual de invalidações ou refills a todas as tiers, e o atraso de replicação costuma ser inferior a um segundo. Para o cliente que escreveu, há consistência read-after-write dentro de uma tier (com no máximo uma falha por requisição), pois o líder master devolve um changeset que atualiza o cache de forma síncrona. As mensagens de invalidação e refill viajam embutidas no fluxo de replicação do banco, para não gerar inconsistência ao ler de uma réplica ainda desatualizada. Para o pequeno subconjunto de leituras que exige mais, o TAO oferece leituras marcadas como críticas, que são encaminhadas à região master, onde está a fonte consistente de verdade. O paper cita autenticação como exemplo: lá, a leitura crítica é usada para que o atraso de replicação não permita usar credenciais desatualizadas.
Tolerância a falhas, hot spots e o que o paper decide sacrificar
O TAO prioriza disponibilidade e desempenho: quando algo falha, prefere continuar renderizando o Facebook mesmo com dados obsoletos. Seus servidores usam timeouts agressivos de rede, mantêm timeouts por destino, marcam um host como inativo após vários timeouts consecutivos e o lembram para abortar rapidamente requisições futuras, sondando ativamente as máquinas falhas para saber se voltaram. Ao detectar falhas, o sistema desvia de forma best effort, trocando consistência por disponibilidade. Bancos de dados são marcados como inativos em uma configuração global se caírem, forem retirados para manutenção ou ficarem muito atrás na replicação, e a região master de um shard é trocada automaticamente na falha de um banco. Escritas que falham durante essa troca são reportadas ao cliente como falhas e não são repetidas. Quanto a desempenho, o paper descreve o shard cloning, em que leituras de um shard quente são servidas por vários seguidores, e um pequeno cache no cliente para objetos muito acessados, com número de versão para omitir dados inalterados nas respostas. Para objetos de alto grau (mais de 6.000 associações do mesmo tipo), o TAO não guarda a lista completa em cache, e consultas assoc_get que retornam vazio vão sempre ao banco; a mitigação é ajustar o código cliente, por exemplo escolhendo a direção da consulta ou usando o tempo de criação do objeto para limitar a busca.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.