Cache distribuído (Memcached/Redis)

01 · CONTEXTO E REQUISITOS

O que é e o que precisa fazer

Um cache distribuído guarda pares chave-valor na memória de várias máquinas ligadas em rede. Diferente do cache de um único nó, limitado aos recursos de uma máquina, ele escala na horizontal. O conjunto de nós particiona e replica os dados para continuar disponível quando um nó falha.

Os requisitos funcionais são gravar, ler e apagar pares chave-valor, configurar a expiração de cada par e despejar dados pelo critério LRU, que remove o que foi usado há mais tempo.

Nos requisitos não funcionais, o enunciado da Hello Interview pede alta disponibilidade, aceitando consistência eventual, e baixa latência, abaixo de 10 ms em get e set. Para a escala, o entrevistador imagina até 1 TB de dados e um pico de 100 mil requisições por segundo. Durabilidade, isto é, sobreviver a reinícios, fica fora do escopo.

02 · UM NÓ PRIMEIRO

Tabela hash, lista ligada e cache-aside

Antes de distribuir, convém entender um nó. Como a memória é limitada, o primer usa LRU para expirar entradas antigas. A implementação combina uma lista duplamente ligada, em que itens novos entram na cabeça e os que vão expirar saem pela cauda, com uma tabela hash que dá acesso direto a cada nó da lista.

1. O cliente faz um pedido e o serviço da aplicação o recebe.

2. O serviço consulta o cache primeiro. Se a chave está lá, é um acerto: o cache responde e passa a entrada para a frente da lista de uso recente.

3. Se a chave não está no cache, é uma falta: o serviço busca o valor no banco de origem.

4. O serviço grava o valor no cache, e a nova entrada fica na frente da lista de uso recente.

5. Se o cache está cheio, a entrada menos usada, no fim da lista, é descartada para dar lugar à nova.

O fluxo do diagrama é o que o primer descreve como cache-aside: a aplicação procura no cache e, se falta, busca na origem e atualiza o cache. Para não servir um valor velho para sempre, a forma mais direta de atualizar é dar a cada entrada um tempo máximo de vida, o TTL.

03 · VÁRIAS MÁQUINAS

Três jeitos de usar um cluster

O primer parte de duas hipóteses: o tráfego não é uniforme, e as consultas populares devem estar quase sempre no cache. Quando uma máquina não basta, há três formas de distribuir os dados.

Para saber qual máquina guarda uma consulta, o primer sugere aplicar uma função de hash à chave, algo como máquina igual a hash da consulta, e indica que o mais provável é usar consistent hashing.

04 · DISTRIBUIR AS CHAVES

Do hash simples ao consistent hashing

Escolher a máquina pelo resto da divisão do hash pelo número de nós funciona até esse número mudar. Ao adicionar ou remover um nó, a maior parte das chaves passa a apontar para outra máquina, e o cache inteiro vira falta de uma vez, o que despeja uma enxurrada de pedidos sobre o banco de origem.

Consistent hashing evita isso colocando nós e chaves no mesmo espaço circular de hash. Cada chave pertence ao primeiro nó que se encontra seguindo o anel; se um nó entra ou sai, só as chaves da vizinhança dele mudam de dono. Para equilibrar a carga, cada máquina costuma aparecer em vários pontos do anel, os chamados nós virtuais.

1. A aplicação calcula o hash da chave pedida.

2. O hash cai na faixa do nó B, então só ele é consultado; os outros nós nem participam do pedido.

3. Se o nó B não tem a chave, a aplicação busca no banco de origem e grava o valor em B.

4. O nó C cai. As chaves da faixa dele viram faltas e passam a pressionar o banco de origem.

5. Com consistent hashing, a faixa de C passa ao vizinho no anel; os nós A e B mantêm as chaves que já tinham.

O Redis Cluster resolve o mesmo problema com slots fixos: o espaço de chaves é dividido em 16384 slots, o slot de cada chave é o CRC16 da chave módulo 16384, e cada nó mestre cuida de um subconjunto deles. Reconfigurar o cluster significa mover slots de um nó para outro.

O Redis Cluster oferece ainda hash tags, que forçam várias chaves ao mesmo slot e assim viabilizam operações com mais de uma chave.

05 · QUANDO UM NÓ CAI

Réplicas e o preço da replicação assíncrona

O requisito de alta disponibilidade pede que a queda de um nó não derrube o cache. A resposta é replicar cada partição: se o primário falha, uma réplica assume. É o que o enunciado descreve ao dizer que o conjunto de nós particiona e replica os dados.

1. A aplicação envia a escrita ao primário da partição dona da chave.

2. O primário copia a escrita para a réplica sem esperar a confirmação dela, ou seja, de forma assíncrona.

3. O primário da partição A cai.

4. A réplica é promovida a primário e a aplicação passa a falar com ela. A partição B segue intacta.

5. Escritas recentes que ainda não tinham sido copiadas se perdem. É o preço da replicação assíncrona: o cache continua disponível, com consistência eventual.

O Redis Cluster assume essa troca de forma explícita: usa replicação assíncrona entre nós e, por isso, há sempre uma janela em que escritas podem ser perdidas durante partições.

06 · HOT KEYS E LIMITES

Quando uma chave só concentra o tráfego

A Hello Interview lista, entre os aprofundamentos do caso, como garantir uma distribuição uniforme de chaves entre os nós e o que fazer com uma hot key muito lida e com uma muito escrita.

Mesmo com chaves bem distribuídas, a carga pode não ser: uma única chave popular cai sempre no mesmo nó. Para leitura, saídas usuais são replicar a chave em vários nós ou guardá-la por pouco tempo num cache local dentro da aplicação. Para escrita quente, uma saída é dividir a chave em partes e somar as partes na leitura.