Cache Distribuído

"Projete um cache distribuído em memória como o Memcached ou o Redis Cluster: um armazenamento chave-valor que muitos servidores de aplicação usam para não bater no banco, guardando mais dados do que cabem numa máquina, com latência abaixo de um milissegundo."

Quase todo caso desta disciplina termina com "e coloca um cache na frente". Este caso abre essa caixa. Um cache distribuído é um pequeno banco de dados distribuído com regras relaxadas: ele pode perder dados (a fonte da verdade está em outro lugar), mas precisa ser rápido, espalhar as chaves de forma equilibrada por muitos nós, sobreviver a nós entrando e saindo sem um estouro de manada no banco e lidar com chaves muito mais quentes que as outras. É a entrevista em que hash consistente, políticas de despejo, atraso de replicação e chaves quentes aparecem num só design — as mesmas ideias por trás do Dynamo, do Cassandra e do Redis Cluster.

No BoxOffice, o cache guarda páginas de eventos, retratos da disponibilidade de lugares e sessões. Às 10:00 de um dia de abertura de vendas ele absorve milhões de leituras por minuto; se um nó de cache morrer às 10:01, a questão é se sua fatia do tráfego passa suavemente para os outros ou cai inteira sobre o PostgreSQL de uma vez.

1. Esclarecer os requisitos

(roteiro de entrevista)

Requisitos funcionais

1. get(key), set(key, value, ttl), delete(key); operações atômicas opcionais (incr, compare-and-set).
2. As chaves expiram depois do TTL; quando a memória enche, o cache despeja algumas chaves.
3. O conjunto de dados é maior que uma máquina: as chaves são particionadas entre muitos nós.
4. Nós podem ser acrescentados ou removidos (escalonamento, falhas) sem reiniciar os clientes.

Requisitos não funcionais

Fora do escopo (diga explicitamente)

Persistência em disco (snapshots/AOF), replicação entre regiões, estruturas de dados complexas além de strings e contadores, autenticação — cite que o Redis oferece várias delas.

2. Estimativas de guardanapo (back-of-the-envelope)

# Distributed cache: assumptions (illustrative)
items         = 1_000_000_000   # cached objects (working set)
value_b       = 1_000           # average value size
key_b         = 50
overhead_b    = 50              # per-item metadata, pointers, allocator slack
node_mem_gb   = 64              # RAM per node usable for data (leave headroom)
ops_s         = 2_000_000       # total cache operations per second at peak
ops_per_node  = 80_000          # comfortable ops/s per node (single-threaded engine)
replicas      = 1               # replicas per primary
hit_ratio     = 0.95

data_tb       = items * (value_b + key_b + overhead_b) / 1e12
nodes_memory  = data_tb * 1e3 / node_mem_gb
nodes_ops     = ops_s / ops_per_node
primaries     = max(nodes_memory, nodes_ops)
total_nodes   = primaries * (1 + replicas)
net_gb_s      = ops_s * value_b / 1e9
db_rps        = ops_s * (1 - hit_ratio)
db_rps_90     = ops_s * (1 - 0.90)

rows = [
    ("data_tb", data_tb, "TB"), ("nodes_memory", nodes_memory, "nodes"),
    ("nodes_ops", nodes_ops, "nodes"), ("primaries", primaries, "nodes"),
    ("total_nodes", total_nodes, "nodes"), ("net_gb_s", net_gb_s, "GB/s"),
    ("db_rps", db_rps, "req/s"), ("db_rps_90", db_rps_90, "req/s"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

O que os números dizem:

• ~1,1 TB de dados precisam de ~17 nós pela memória, mas 2 M de ops/s precisam de 25 nós pela vazão. ⇒ dimensione pelos dois e fique com o maior: aqui a vazão decide (25 primários, 50 nós com uma réplica cada).
• 2 GB/s de valores atravessam a rede no pico — divididos por 25 nós são ~80 MB/s cada, tranquilo para placas de rede modernas, mas uma única chave grande lida milhares de vezes por segundo pode saturar o link de um nó.
• Com 95% de acerto o banco recebe 100 mil req/s; com 90% recebe 200 mil req/s. ⇒ cada ponto de taxa de acerto vale 20 mil requisições por segundo no banco. Perder um nó de 25 (4% das chaves) frio é um súbito +80 mil faltas/s para o banco — o motivo de failover e réplicas aquecidas importarem (cache).

3. API

GET    key                         → value | nil
SET    key value EX 300            → OK                 (TTL in seconds)
SET    key value NX EX 30          → OK | nil           (only if absent: locks, leases)
DEL    key                         → 1 | 0
INCRBY key 5                       → 42                 (atomic counter)
MGET   k1 k2 k3                    → [v1, v2, v3]       (batched: one round trip)

# Cluster-aware client: the key decides the node
slot = CRC16(key) mod 16384        → node owning that slot (Redis Cluster)
-MOVED 3999 10.0.1.17:6379         → slot moved: update the client's map and retry there

• A biblioteca cliente faz parte da API: ela calcula o hash da chave, mantém o mapa de partições → nós, faz pool de conexões e pipelining das requisições.
• Um MGET com chaves em nós diferentes vira um scatter-gather; use hash tags ({event:42}:seats, {event:42}:page) para manter no mesmo nó as chaves relacionadas que são lidas juntas.

4. Modelo de dados

# On each node: a hash table of entries + an eviction structure
entry  = { key, value, expires_at, flags, lru_clock | lfu_counter }
index  = hash table key → entry                   (O(1) get/set)
policy = LRU list / sampled LRU / LFU counters   (who to evict when memory is full)

# Cluster metadata (gossiped between nodes or stored in a coordination service)
slots 0–5460      → node-a (primary), node-d (replica)
slots 5461–10922  → node-b (primary), node-e (replica)
slots 10923–16383 → node-c (primary), node-f (replica)

5. Design de alto nível

flowchart LR
    app1["Servidor de app #1<br/>cliente que conhece o cluster"] --> a["node-a<br/>slots 0–5460"]
    app1 --> b["node-b<br/>slots 5461–10922"]
    app2["Servidor de app #2<br/>cliente que conhece o cluster"] --> b
    app2 --> c["node-c<br/>slots 10923–16383"]
    a -. replicação assíncrona .-> ra["réplica a'"]
    b -. replicação assíncrona .-> rb["réplica b'"]
    c -. replicação assíncrona .-> rc["réplica c'"]
    app1 -- falta --> db[("Banco de dados<br/>fonte da verdade")]
    app2 -- falta --> db
    a -. métricas .-> m["Métricas"]

Uma leitura com cache-aside, incluindo um slot que mudou de nó:

sequenceDiagram
    autonumber
    participant A as App (biblioteca cliente)
    participant B as node-b
    participant C as node-c
    participant D as Banco de dados
    A->>A: slot = CRC16("event:42") mod 16384 → node-b (mapa em cache)
    A->>B: GET event:42
    B-->>A: -MOVED 9001 node-c (o slot foi migrado)
    A->>A: atualiza o mapa de slots
    A->>C: GET event:42
    C-->>A: nil (falta)
    A->>D: SELECT evento 42
    D-->>A: linha
    A->>C: SET event:42 … EX 300

6. Aprofundamentos (deep dives)

6.1 Particionamento: por que hash % N quebra, e o hash consistente

Com nó = hash(chave) % N, passar de 4 para 5 nós muda o dono de quase todas as chaves — um cache com 80% das chaves de repente no lugar errado é, para o banco, o mesmo que um cache vazio. O hash consistente coloca nós e chaves no mesmo anel de valores de hash; uma chave pertence ao primeiro nó no sentido horário. Acrescentar um nó só toma chaves dos vizinhos — cerca de 1/N delas. Cada nó físico recebe muitos nós virtuais (pontos no anel) para a carga ficar equilibrada e as chaves de um nó que falhou se espalharem por todos os outros, não só por um vizinho (particionamento).

import bisect
import hashlib

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

keys = [f"event:{i}" for i in range(50_000)]
kh = {k: h(k) for k in keys}

def mod_n(n):
    return {k: kh[k] % n for k in keys}

def ring(nodes, vnodes):
    points = sorted((h(f"node{n}#{v}"), n) for n in range(nodes) for v in range(vnodes))
    hashes = [p for p, _ in points]
    owner = {}
    for k in keys:
        i = bisect.bisect(hashes, kh[k]) % len(points)
        owner[k] = points[i][1]
    return owner

def moved(a, b):
    return sum(a[k] != b[k] for k in keys) / len(keys)

def max_over_avg(owner, nodes):
    counts = [0] * nodes
    for n in owner.values():
        counts[n] += 1
    return max(counts) / (len(keys) / nodes)

print("| scheme | keys_moved_pct | max_load_vs_avg |\n|---|---:|---:|")
a, b = mod_n(4), mod_n(5)
print(f"| `hash % N` | {moved(a, b):.1%} | {max_over_avg(b, 5):.2f} |")
for v in (1, 10, 100, 1000):
    a, b = ring(4, v), ring(5, v)
    print(f"| `ring, {v} vnodes/node` | {moved(a, b):.1%} | {max_over_avg(b, 5):.2f} |")

Leia a tabela em duas colunas. Chaves movidas ao passar de 4 para 5 nós: hash % N move ~80%; o anel move ~20% — o mínimo teórico, 1/5. Equilíbrio de carga (o nó mais ocupado em relação à média): com um ponto por nó o anel fica muito desigual (o nó mais ocupado guarda quase o dobro da sua parte); com centenas de nós virtuais ele se aproxima de 1,0.

6.2 Despejo, TTL e memória

Quando a memória enche, algo precisa sair. A política decide a taxa de acerto que você obtém com a mesma RAM (modos de falha de cache):

• Motores reais aproximam: o Redis amostra algumas chaves e despeja a melhor candidata entre elas (LRU ou LFU aproximados, com contadores que decaem) em vez de manter uma ordem global perfeita.
• TTL é ferramenta de consistência, despejo é ferramenta de memória. Sempre defina um TTL (para o dado desatualizado ter um limite) e acrescente jitter aos TTLs gravados em massa (ex.: 300 s ± 10%) para não expirarem no mesmo segundo.
• Deixe folga: planeje ~70–80% da RAM para dados. Fragmentação, buffers de replicação e o fork para snapshots precisam do resto; um nó que faz swap para o disco é mais lento do que nenhum cache.

6.3 Replicação e failover

sequenceDiagram
    autonumber
    participant A as App
    participant P as Primário (node-b)
    participant R as Réplica (node-e)
    participant S as Detector de falhas
    A->>P: SET seats:42 v7
    P-->>A: OK
    P--)R: replica v7 (assíncrono)
    Note over P: o primário cai antes de v7 chegar à réplica
    S->>S: node-b perdeu heartbeats → a maioria concorda
    S->>R: promove node-e a primário
    A->>R: GET seats:42
    R-->>A: v6 (a escrita confirmada v7 se perdeu)

• A replicação costuma ser assíncrona: escritas rápidas, mas um failover pode perder as últimas escritas confirmadas. Para um cache isso é aceitável — a próxima falta recarrega do banco. Se um valor desatualizado for perigoso (disponibilidade de lugares), mantenha TTLs curtos ou apague as chaves na escrita (invalidação).
• A detecção de falhas precisa de maioria (Redis Sentinel, ou os nós do cluster votando) para que um observador isolado não promova uma réplica sozinho.
• Split brain: depois de uma partição, o primário antigo ainda pode aceitar escritas de clientes do lado dele. Mitigue fazendo o primário parar de aceitar escritas quando não enxerga réplicas/pares suficientes (min-replicas-to-write), e com épocas/termos para clientes e nós rejeitarem o primário velho.
• Réplicas aquecidas também atendem leituras (se leituras desatualizadas forem aceitáveis) e evitam o estouro de manada do nó frio depois do failover.

6.4 Chaves quentes, chaves grandes e estouros de manada

• Chave quente — uma chave (a página do evento durante uma abertura de vendas, o perfil de uma celebridade) recebe tantas requisições que seu nó satura enquanto os outros ficam ociosos. O hash consistente não ajuda: uma chave mora num nó só. Soluções: um pequeno cache L1 em processo com TTL de segundos em cada servidor de aplicação; replicar a chave com vários nomes (event:42#1 … #8) e ler uma cópia aleatória; atendê-la pelas réplicas.
• Chave grande — um valor de 5 MB lido 1 000 vezes por segundo são 5 GB/s num nó. Divida-o (pagine, comprima), ou guarde em cache os fragmentos renderizados em vez do objeto inteiro.
• Estouro de manada (thundering herd) — uma chave quente expira e milhares de requisições falham ao mesmo tempo e vão todas ao banco. Soluções (modos de falha de cache):
  • Coalescência de requisições / leases: a primeira falta ganha uma lease (SET lock:key NX EX 5) e recarrega; as outras esperam um pouco ou recebem o valor velho. O Memcache do Facebook usou leases exatamente para isso.
  • Expiração antecipada probabilística: cada leitor pode renovar antes do TTL com uma probabilidade que cresce conforme a expiração se aproxima, então uma requisição renova antes em vez de todas ao mesmo tempo.
  • Servir o velho enquanto revalida para dados em que alguns segundos de desatualização tudo bem.

import math, random, time

def should_refresh_early(expires_at: float, recompute_s: float, beta: float = 1.0) -> bool:
    """XFetch: refresh before expiry with a probability that grows near the deadline."""
    return time.time() - recompute_s * beta * math.log(random.random()) >= expires_at

if (stampedeProtection) {
    var lockKey = key + ":lock";
    var token = UUID.randomUUID().toString();
    if (tryLock(lockKey, token)) {
        try {
            cached = read(key);               // someone may have filled it meanwhile
            if (cached != null) {
                return count(new Result(cached, "HIT"));
            }
            return count(load(key, ttl, loader));
        } finally {
            unlock(lockKey, token);
        }
    }
    // another request is already loading this key: wait for it instead of
    // sending one more identical query to the database
    for (int i = 0; i < 20; i++) {
        sleep(Duration.ofMillis(25));
        cached = read(key);
        if (cached != null) {
            return count(new Result(cached, "HIT"));
        }
    }
}

6.5 Roteamento: quem sabe onde mora uma chave?

A implantação de memcache do Facebook, por exemplo, colocou o roteamento num proxy (mcrouter) para que milhares de servidores web não precisassem cada um gerenciar conexões com todos os nós de cache.

7. Gargalos, modos de falha e trade-offs

Os trade-offs para dizer em voz alta: disponibilidade e velocidade acima de consistência (um cache pode estar desatualizado ou perder escritas; o banco é a verdade), memória vs. vazão (dimensione pelos dois), e distribuição equilibrada vs. chaves quentes (o hash espalha chaves, não popularidade).

8. Experimente no playground

Dois cenários cobrem as duas metades deste caso: o cache na frente de um banco, e o particionamento dos dados entre nós.

Abrir o playground completo

9. Perguntas de follow-up que o entrevistador faz

10. Rubrica de autoavaliação

Relacionados: Cache, Redis, Modos de falha de cache, Particionamento, Hands-on 5 (cache-aside com Redis, taxa de acerto e estouro de manada).

Como se conecta

Quais aulas este caso testa? Cada ramo é uma aula cujas ideias o design usa (azul), com os componentes da paleta em que elas aparecem (verde):

flowchart LR
    CASE(["Distributed cache"]) --> EST["Estimation<br/>size by memory and ops/s"]:::tech
    CASE --> PART["Databases<br/>consistent hashing, virtual nodes"]:::tech
    CASE --> EVI["Caching<br/>eviction LRU, LFU, W-TinyLFU, TTL"]:::tech
    CASE --> REP["Databases<br/>async replication, failover"]:::tech
    CASE --> HOT["Caching<br/>hot keys, big keys, stampedes"]:::tech
    CASE --> ROUTE["routing<br/>cluster-aware client"]:::tech
    PART -.-> k1["cache (cluster)"]:::comp
    REP -.-> k2["sql · nosql<br/>(source of truth)"]:::comp
    ROUTE -.-> k3["app"]:::comp
    HOT -.-> k4["metrics"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Aulas que ele testa: Caching — padrões · Caching — Redis · Cache — modos de falha · Bancos de dados — particionamento · Bancos de dados — replicação · Estimativas — números · Hands-on 5. Componentes da paleta: cache · app · sql · nosql · metrics. Cenários: read-heavy-cache, sharding.

Referências

• KARGER, D. et al. Consistent Hashing and Random Trees¹.
• DECANDIA, G. et al. Dynamo: Amazon's Highly Available Key-value Store².
• NISHTALA, R. et al. Scaling Memcache at Facebook — leases, pools regionais, mcrouter³.
• EINZIGER, G.; FRIEDMAN, R.; MANES, B. TinyLFU: A Highly Efficient Cache Admission Policy⁴.
• XU, A. System Design Interview, vol. 1, cap. 5 "Design Consistent Hashing" e cap. 6 "Design a Key-Value Store"⁵; especificação do Redis Cluster⁶.