Papers
Scaling Memcache at Facebook
Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, Venkateshwaran Venkataramani · NSDI 2013, 2013
O problema: um grafo social é leitura demais para o banco aguentar sozinho
O Facebook precisava servir uma rede social inteira — perfis, feeds, grafos de amizade — para mais de um bilhão de usuários, com uma proporção de leituras muito maior que a de escritas. Bater direto no banco de dados relacional para cada leitura não escalava: o volume de consultas cresceria junto com o número de usuários e de conexões entre eles, muito mais rápido do que o hardware de banco conseguiria acompanhar. A solução adotada não foi trocar o banco por outra coisa, mas colocar uma camada de cache em memória na frente dele, usando o memcached — um servidor de cache chave-valor simples e já conhecido — como peça básica. O artigo descreve como esse bloco simples foi esticado, com engenharia em cima dele (não mudanças no próprio memcached), até sustentar uma escala de bilhões de requisições por segundo e trilhões de itens armazenados. A dificuldade central não era o cache em si, mas orquestrar milhares de servidores de cache, mantê-los consistentes o suficiente com o banco de dados, e sobreviver a falhas de rede e de máquinas sem transformar cada pequena falha em uma avalanche de tráfego direto ao banco.
A ideia central: cache de leitura sob demanda, com invalidação disparada pela escrita
O padrão usado é o de cache 'look-aside' preenchido sob demanda: quando uma aplicação precisa de um dado, ela primeiro consulta o memcached; se o item não está lá (miss), ela busca no banco de dados e, em seguida, grava o resultado no cache para que a próxima leitura seja servida direto da memória. O cache nunca é escrito antecipadamente — ele só se popula conforme o uso real acontece. Para escrita, a aplicação grava no banco e depois invalida (remove) a entrada correspondente no cache, em vez de tentar atualizar o valor cacheado diretamente; a próxima leitura recarrega o dado atualizado do banco. Essa invalidação é disparada observando as próprias operações de escrita que chegam ao banco, para identificar quais chaves de cache correspondem aos dados alterados e apagá-las de forma direcionada, sem precisar limpar o cache inteiro. O resultado é um sistema onde o memcached absorve a esmagadora maioria das leituras e o banco de dados só é consultado em misses de cache ou em escritas — reduzindo drasticamente a carga de leitura que o banco relacional precisa suportar.
Um trade-off específico: leases para evitar manadas e escritas atrasadas, ao custo de uma rodada extra
Um problema prático de cache sob demanda em larga escala é a 'manada de bois' (thundering herd): quando uma entrada popular é invalidada, muitas requisições simultâneas dão miss ao mesmo tempo e todas correm para recalcular o mesmo valor no banco, gerando um pico de carga desnecessário. Outro problema relacionado é o de escritas atrasadas: uma requisição antiga, que buscou um valor já obsoleto antes de uma invalidação, pode terminar de processar depois e gravar no cache um dado velho por cima de um mais novo. O paper resolve os dois com um mecanismo de 'lease': ao registrar um miss, o memcached entrega um token (lease) de validade limitada ao cliente que vai recalcular o valor; só o cliente com o token válido mais recente tem permissão de escrever o resultado de volta no cache, e escritas com token expirado ou invalidado são descartadas. Isso troca simplicidade e uma latência mínima adicional (a ida extra para obter e validar o token) por uma garantia mais forte contra picos de recomputação redundante e contra a corrupção do cache por escritas fora de ordem.
Crescendo além de um cluster: pools regionais e um pool de emergência para falhas
À medida que o Facebook cresceu, um único cluster de servidores memcached deixou de ser suficiente, e o sistema precisou operar em três escalas: dentro de um cluster, entre clusters de uma mesma região, e entre regiões geograficamente distantes. Dentro de uma região, múltiplos clusters compartilham dados por meio de pools regionais, evitando que cada cluster precise manter sua própria cópia completa de tudo. Entre regiões, réplicas geograficamente distantes do banco de dados trazem um desafio adicional: a replicação entre regiões não é instantânea, então o sistema usa marcadores específicos para sinalizar quando uma região secundária ainda pode estar com dados desatualizados em relação à região primária, evitando que uma leitura local pareça consistente sem realmente estar. Para lidar com falhas de servidores de cache individuais sem sobrecarregar o banco de dados, o sistema mantém um 'gutter pool': um conjunto pequeno de servidores de reserva que absorve temporariamente o tráfego que iria para uma máquina de cache que caiu, servindo como um segundo nível de cache emergencial até que o servidor original volte ao ar.
Legado: o padrão de cache look-aside virou default em sistemas modernos
O artigo não propôs um novo algoritmo acadêmico, mas documentou e generalizou, a partir de uma implantação real em escala massiva, um padrão de engenharia que hoje é praticamente onipresente: usar um cache em memória como camada de leitura na frente de um banco de dados relacional, preenchido sob demanda e invalidado (não atualizado) nas escritas. Esse padrão de 'cache-aside' é ensinado hoje como uma opção básica de design de sistemas ao lado de write-through e write-behind, e aparece em praticamente qualquer arquitetura que combine um banco de dados com Redis ou Memcached na frente. Problemas que o paper trouxe à tona — a manada de bois em cache miss, a necessidade de invalidação direcionada em vez de limpeza total, e a dificuldade de manter consistência razoável entre regiões distantes — continuam sendo preocupações centrais no design de qualquer camada de cache distribuída de propósito geral, independentemente da tecnologia específica usada. A contribuição do paper foi menos 'inventar cache' e mais mostrar, com números e mecanismos concretos de uma implantação real, como um bloco simples pode ser operado de forma confiável numa escala de bilhões de operações por segundo.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.