Facebook: escalando o Memcache (NSDI 2013)

01 · CONTEXTO

Um cache na frente de um banco que não aguentaria sozinho

O Facebook servia uma rede social em que as pessoas consomem muito mais conteúdo do que criam. Essa assimetria entre leitura e escrita é o ponto de partida do artigo: se a carga é dominada por busca de dados, um cache rende muito. O sistema descrito, construído sobre o memcached, chegou a tratar bilhões de requisições por segundo e a guardar trilhões de itens.

O padrão de base é o cache look-aside preenchido sob demanda. Na leitura, o servidor web pergunta ao cache; num miss, busca no banco e grava o par chave-valor no cache. Na escrita, ele grava no banco e envia um delete ao cache para invalidar o dado velho. A escolha por apagar em vez de atualizar tem uma razão explícita: deletes são idempotentes. E o cache não é a fonte da verdade, então pode descartar itens.

1. O usuário pede uma página. O servidor web precisa de vários dados para montá-la e começa pelo cache.

2. O servidor web pergunta ao cache pela chave. Se o item está lá, é um hit e o banco nem é consultado.

3. Se o item não está no cache, é um miss: o servidor web busca o dado no banco, que guarda a cópia autoritativa.

4. Com o dado em mãos, o servidor web grava o par chave-valor no cache. A próxima leitura da mesma chave será atendida pela memória.

5. Numa escrita, o servidor web grava no banco e depois manda um delete ao cache. O dado velho some e a próxima leitura recarrega o valor novo.

Dois objetivos guiam as escolhas do projeto. Um deles é incomum: a probabilidade de ler dado ligeiramente velho é tratada como um parâmetro a ajustar, como a responsividade. O time aceita expor dado levemente velho para proteger o armazenamento de carga excessiva.

02 · NO CLUSTER: LATÊNCIA E CARGA

Milhares de servidores, uma página que pede centenas de itens

Uma página popular carregava, em média, 521 itens distintos do memcache, e os itens se espalham pelos servidores por hashing consistente. O resultado é que os servidores web acabam falando com todos os servidores de cache em curto intervalo. Esse padrão todos-com-todos pode causar congestionamento por incast ou transformar um único servidor em gargalo para muitos clientes.

A complexidade fica no cliente, não no servidor. Os servidores de memcached não conversam entre si; roteamento, serialização, compressão e agrupamento de pedidos vivem num cliente sem estado, que pode ser uma biblioteca ou o proxy mcrouter. Para gets, o cliente usa UDP, que reduz latência e custo; erro de get vira miss, e o servidor web evita reinserir a entrada para não sobrecarregar uma rede ou servidor já pressionado. Sets e deletes vão por TCP, via mcrouter na mesma máquina, porque precisam de confirmação. Para limitar o incast, uma janela deslizante controla os pedidos em andamento: ela cresce devagar a cada sucesso e encolhe quando um pedido fica sem resposta.

Duas falhas de coerência aparecem no cache sob demanda. O stale set acontece quando atualizações concorrentes chegam fora de ordem e um servidor grava no cache um valor que já não é o mais recente. A manada de leituras (thundering herd) acontece quando uma chave muito lida e muito escrita é invalidada sem parar e muitas leituras caem no caminho caro. A solução do artigo são os leases: no miss, o memcached entrega ao cliente um token ligado àquela chave, e só quem apresenta um token ainda válido consegue gravar. Se um delete invalidou o token, a gravação é recusada. Um ajuste simples cura a manada: o servidor devolve um token só uma vez a cada 10 segundos por chave, e quem pede nesse intervalo recebe a orientação de esperar um pouco.

1. Um cliente pede uma chave popular que acabou de ser invalidada. O servidor de cache dá miss e entrega a esse cliente um lease para aquela chave.

2. Outros clientes pedem a mesma chave logo depois. Em vez de um segundo token, recebem a orientação de esperar um pouco e tentar de novo, e a manada não chega ao banco.

3. Quem detém o lease busca o valor no banco e o grava no cache apresentando o token. Os que esperavam voltam e, em geral, já encontram o dado.

4. Se um delete chegar antes dessa gravação, o token é invalidado e o set é recusado. Assim, uma escrita atrasada não põe valor velho por cima de um mais novo.

Em uma medição de uma semana sobre chaves especialmente sujeitas à manada, o pico de consultas ao banco foi de 17 mil por segundo sem leases e de 1,3 mil por segundo com leases. Como o banco é dimensionado pelo pico, isso vira ganho de eficiência. O mesmo mecanismo permite um atalho: aplicações que progridem com dado ligeiramente velho podem aceitar o valor marcado como stale em vez de esperar o banco.

Cargas diferentes disputam a mesma memória, então o cluster é dividido em pools. Sem isso, chaves de baixo giro ainda valiosas eram expulsas antes de chaves de alto giro que ninguém mais acessava; colocar chaves de giro diferente em pools distintos evita essa interferência e permite dimensionar cada pool pelo custo do miss. Em alguns pools o artigo prefere replicar um conjunto pequeno de chaves muito pedidas a dividi-lo ainda mais, e isso exige entregar as invalidações a todas as réplicas.

03 · FALHAS E O POOL GUTTER

Quando o cache falha, o banco paga

Não conseguir buscar do cache gera carga excessiva nos serviços de trás e pode provocar falhas em cascata. A remediação automática de poucos hosts não é instantânea e pode levar alguns minutos, tempo suficiente para a cascata acontecer. Para cobrir esse intervalo, uma pequena frota dedicada, chamada Gutter, assume as responsabilidades de alguns servidores falhos. Ela representa cerca de 1% dos servidores de memcached de um cluster.

1. Um servidor de cache cai. O cliente pede uma chave dele e não recebe resposta.

2. O cliente supõe que o servidor falhou e repete o pedido num pool Gutter, uma frota separada de servidores ociosos.

3. Se o Gutter também der miss, o cliente busca no banco e insere o par no Gutter. Os pedidos seguintes da mesma chave já acham o dado ali.

4. As entradas do Gutter duram pouco: o preço da proteção ao banco é servir, por um tempo curto, dado levemente velho.

Por que não redistribuir as chaves do servidor falho entre os demais? Porque o acesso por chave é desigual: quem herdar uma chave muito quente pode se sobrecarregar, e a falha vira cascata. O Gutter desvia a carga para servidores ociosos e limita esse risco. Segundo o artigo, o mecanismo reduz em 99% a taxa de falhas visíveis ao cliente.

04 · NA REGIÃO: REPLICAÇÃO ENTRE CLUSTERS

Mais clusters, menos dependência de um só

Comprar mais servidores não resolve tudo: o incast piora conforme o número de servidores de memcached aumenta. O Facebook então dividiu web e memcached em vários clusters de front-end que, junto de um cluster de armazenamento com os bancos, formam uma região. A troca é explícita: abre-se mão de replicação de dados em troca de domínios de falha mais independentes.

O cluster de armazenamento tem a cópia autoritativa e responde por invalidar os clusters de front-end. Para isso, os comandos SQL que alteram estado são ampliados com as chaves de cache a invalidar quando a transação confirma, e um daemon (mcsqueal) em cada banco lê os deletes dos commits e os transmite aos caches de todos os clusters da região, em lotes para reduzir pacotes. Como a invalidação está nos logs confiáveis do banco, o mcsqueal pode reexecutar invalidações perdidas ou mal roteadas, algo que o envio direto pelos servidores web não permite.

Cada cluster guarda o que os seus usuários pedem, e replicar tudo em todos os clusters desperdiça memória. Para reduzir o número de réplicas, vários clusters compartilham o mesmo conjunto de servidores de memcached: é o pool regional. A troca é declarada: cruzar fronteiras de cluster custa mais latência e a rede tem 40% menos banda média entre clusters do que dentro de um, enquanto a replicação gasta mais servidores para ter menos tráfego entre clusters, latência menor e melhor tolerância a falhas. Por isso a escolha entre replicar e manter uma única cópia por região depende do item.

Um cluster novo, ou um que volta de manutenção, tem cache vazio e taxa de acerto péssima. O Cold Cluster Warmup deixa os clientes do cluster frio lerem de um cluster quente em vez do armazenamento persistente, e leva a recuperação da capacidade plena de poucos dias para poucas horas. Para evitar inconsistência por corrida, os deletes no cluster frio levam por padrão um hold-off de dois segundos, durante o qual operações add são rejeitadas: se o add falha, o cliente sabe que há dado mais novo no banco e o busca lá. O artigo admite que resta a possibilidade teórica de um delete atrasar mais que isso, e a considera rara.

05 · ENTRE REGIÕES: CONSISTÊNCIA

A réplica do banco pode estar atrasada

Com várias regiões, uma região guarda os bancos mestres e as demais têm réplicas somente de leitura. Nesse desenho, manter a consistência entre memcache e armazenamento persistente vira o principal desafio técnico, e ele nasce de um só problema: a réplica do banco pode estar atrasada em relação ao mestre. O modelo escolhido é consistência eventual de melhor esforço, com ênfase em desempenho e disponibilidade; as ideias de semântica mais estrita raramente saem da fase de projeto por serem caras demais.

Considere uma escrita na região mestre. Se o servidor web invalidasse o cache de uma região réplica logo após gravar, a invalidação poderia chegar antes de os dados chegarem à réplica, e a leitura seguinte recolocaria dado velho no cache. Por isso a invalidação sai do cluster de armazenamento, por daemon, e o fluxo de deletes compartilha o canal da replicação do banco.

Agora, uma escrita numa região não mestre com a réplica muito atrasada: a pessoa pode não ver a própria mudança. O artigo usa um marcador remoto. O servidor web cria um marcador para a chave na região, escreve no mestre embutindo a chave e o marcador a invalidar no SQL e apaga a chave no cluster local. Na leitura seguinte, o miss leva o servidor a checar o marcador: se ele existe, a consulta vai ao mestre; se não, à réplica local. É uma troca explícita, com mais latência no miss em troca de menor chance de ler dado velho.

1. Escrita na região mestre: o servidor web grava no MySQL mestre, e o SQL carrega as chaves de cache a invalidar.

2. O mcsqueal lê o que o banco confirmou e apaga as chaves nos caches da região mestre.

3. A replicação leva a mudança à réplica; só depois o mcsqueal da região réplica, que lê a réplica, apaga a chave no cache de lá. A invalidação nunca passa à frente do dado.

4. Escrita numa região não mestre: o servidor web cria o marcador da chave, escreve no mestre e apaga a chave no cache local.

5. Na leitura seguinte, o cache local dá miss e o servidor encontra o marcador, então manda a consulta ao mestre. A réplica, que ainda pode estar atrasada, é evitada.

06 · TRADE-OFFS

O que cada mecanismo compra e cobra

Repare no padrão: quase todo mecanismo aceita um pouco de dado velho ou de latência em troca de proteger o banco. É o objetivo declarado do projeto aplicado a cada escala: no cluster, leases e Gutter; na região, pools regionais e invalidação por commit; entre regiões, o marcador remoto.