Conceitos
Cache de grafo social com líder e seguidores (TAO)
Intuição
Imagine um arquivo central enorme e milhares de pessoas pedindo informação o tempo todo, quase sempre só para consultar. Você coloca vários atendentes de balcão que respondem de cabeça o que já sabem; quando não sabem, eles não correm ao arquivo, e sim perguntam a um único responsável por aquela gaveta. Esse responsável é o único que vai ao arquivo e o único que registra mudanças daquela gaveta, então não há filas de gente buscando a mesma coisa nem duas pessoas alterando o mesmo papel ao mesmo tempo.
Como funciona
No TAO, o grafo é modelado como objetos (nós tipados, com id de 64 bits) e associações (arestas direcionadas e tipadas, identificadas por id1, atype e id2), e o armazenamento persistente continua sendo o MySQL, dividido em shards lógicos. Cada associação fica no shard do seu id1, então uma consulta de lista de associações (ordenada por tempo, da mais recente para a mais antiga) pode ser atendida por um único servidor. A camada de cache implementa a API do grafo e é dividida em um nível de líderes e várias tiers de seguidores, para evitar tiers enormes com hot spots e comunicação todos-com-todos quadrática. Os clientes falam só com seguidores; em um miss de leitura ou em qualquer escrita, o seguidor encaminha o pedido ao líder do shard, que é quem acessa o banco. Como todas as escritas de um shard passam por um único líder, ele serializa escritas concorrentes e protege o banco de thundering herds, limitando consultas sobrepostas e pendentes. Depois de uma escrita, o TAO garante a entrega eventual de invalidações ou refills a todas as tiers, embutidas no fluxo de replicação do banco, e o cliente que escreveu tem consistência read-after-write dentro da sua tier porque o líder devolve um changeset que atualiza o cache de forma síncrona. Isso difere do memcache look-aside usado antes no Facebook, em que a lógica de controle ficava em clientes que não conversam entre si e exigia remendos como leases para conter manadas e escritas atrasadas; no TAO essa coordenação mora dentro do próprio cache. O preço é que o TAO não garante atomicidade quando uma associação e sua inversa ficam em shards diferentes: uma falha pode deixar uma associação sem inversa, reparada depois por um job assíncrono.
Na prática
O desenho serve a cargas dominadas por leitura, em que cada página é montada puxando dados de um grafo de objetos e arestas e aceitar dados momentaneamente desatualizados é preferível a ficar fora do ar, como o paper descreve para o Facebook. Escolha-o quando um cache chave-valor lookaside simples começar a sofrer com listas de arestas, thundering herds e lógica de controle espalhada nos clientes, e aceite em troca consistência eventual por padrão e a possibilidade de arestas inversas temporariamente inconsistentes.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.