Consistent hashing

Em maio de 1997, no Symposium on Theory of Computing (STOC), David Karger e equipe do MIT publicaram um paper de título sóbrio: "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web". O contexto era a web nascente — mid-90s, sites populares enfrentando picos de tráfego que derrubavam servidores. A solução proposta tinha duas partes: um algoritmo de hashing especialmente desenhado para sistemas distribuídos, e uma arquitetura de cache em árvore. A primeira parte — consistent hashing — viraria primitiva fundadora de uma geração inteira de sistemas distribuídos.

A intuição é simples e devastadora. Em sistemas distribuídos comuns, distribuir dados entre N servidores via hash(key) mod N tem problema fundamental: quando N muda (servidor adicionado ou removido), quase todas as chaves mudam de servidor. Adicionar 1 servidor a uma frota de 10 reroteia ~90% dos dados — em sistema com cache, vira disaster (cache cold em massa); em banco, vira movimento gigante de dados. Consistent hashing reduz esse re-roteamento para aproximadamente 1/N das chaves — o mínimo teórico. Adicionar servidor 11 a frota de 10 reroteia ~9% dos dados.

A prova é elegante e o algoritmo é simples — cabe em poucas linhas de código. Mas as consequências vão muito além do paper original. Em 2007, Amazon publicou o paper Dynamo, baseado em consistent hashing, que se tornou referência para Cassandra (Facebook, 2008), DynamoDB (Amazon, 2012), Riak, ScyllaDB. CDNs (Akamai, Cloudflare) usam variantes para mapear cliente → PoP. Memcached clusters, Redis clusters, sharding de banco — toda vez que algo precisa "decidir qual nó tem essa chave" em sistema distribuído, consistent hashing é a primitiva.

Este conceito articula o algoritmo, suas propriedades teóricas (especialmente o limite de 1/N de movimento), o problema de balanceamento naïve e a solução de virtual nodes (popularizada por Dynamo), e os casos onde se aplica em produção — não como "feature exótica de Cassandra" mas como ferramenta universal que aparece sempre que escala distribuída entra em cena.

O problema com hash(key) mod N

Considere um cluster de 4 servidores de cache, e você quer distribuir chaves entre eles. Solução naive:

servidor = hash(key) % 4

Funciona. Distribuição uniforme assumindo bom hash. Cada servidor pega ~25% das chaves.

Adicione um quinto servidor. Agora a fórmula vira hash(key) % 5. O servidor calculado muda para praticamente todas as chaves. O cache fica cold; chaves migram em massa.

A matemática é direta: hash mod 4 e hash mod 5 coincidem apenas em uma fração pequena (aproximadamente 1/(4×5) = 5%). Dos 95% restantes, todos vão para servidores diferentes — sem padrão útil. Em sistema de cache, isso é ruína para hit rate; em banco distribuído, isso é movimento custoso de gigabytes.

Esse problema afeta qualquer sistema que adicione ou remova nós com frequência: cluster com auto- scaling, deploy de novo nó, falha de nó. Em sistemas com 100 nós, perder 1 com hash modular força mover dados de ~99 dos 100 — completamente desproporcional ao 1% que de fato deveria mudar.

O algoritmo — anel de hash

Consistent hashing visualiza o espaço de hash como um anel circular (tipicamente 0 a 2³² ou 2⁶⁴). Cada servidor recebe uma posição no anel (via hash do nome ou IP). Cada chave também recebe uma posição (via hash da chave). Para decidir o servidor de uma chave: caminhe pelo anel a partir da posição da chave, no sentido horário, e o primeiro servidor encontrado é o responsável.

// pseudocódigo
function findServer(key, ring):
    keyHash = hash(key)
    // ring é lista ordenada de (serverHash, serverID)
    for (serverHash, serverID) in ring:
        if serverHash >= keyHash:
            return serverID
    // se passou todo o anel, volta para o primeiro
    return ring[0].serverID

A propriedade-chave: quando você adiciona um servidor, ele "rouba" apenas as chaves da seção do anel entre ele e o servidor anterior (em sentido anti-horário). Os outros servidores não são afetados — suas chaves continuam apontando para eles. Quando remove, as chaves daquele servidor migram apenas para o próximo servidor (no sentido horário). O resto fica.

Em frota de 100 servidores, adicionar o 101º só afeta as chaves da fatia que ele cobre — tipicamente 1/101 ≈ 1% dos dados. Isso é o mínimo teórico possível para qualquer redistribuição.

O problema de balanceamento e a solução virtual nodes

Consistent hashing puro tem um problema: o balanceamento depende de hash uniforme, mas com poucos servidores, a sorte do hash pode dar distribuição desigual. Servidor A pega 40% do anel, servidor B pega 10% — o tráfego vai desigual.

A solução, popularizada pelo paper Dynamo (2007), é virtual nodes: cada servidor físico é representado por múltiplas posições no anel. Em vez de servidor A ter 1 posição, ele tem 100 ou 200 posições (com hashes ligeiramente distintos: hash(A_0), hash(A_1), ..., hash(A_199)).

O efeito é que cada servidor tem muitas pequenas fatias do anel, intercaladas com fatias dos outros. A distribuição converge para uniforme rapidamente (lei dos grandes números), e adição/remoção de servidor resulta em movimento que afeta muitos servidores existentes em pequena medida — em vez de um único vizinho perdendo metade dos dados.

Na prática, 100-200 virtual nodes por servidor físico é faixa típica. Cassandra usa 256 por padrão; Dynamo usou centenas. O número exato é trade-off: mais virtual nodes = melhor balanceamento, mas mais overhead de metadata e roteamento.

Onde consistent hashing é usado

Em 2026, consistent hashing aparece em quase todo sistema distribuído sério. Vale conhecer os principais.

Bancos NoSQL distribuídos

Cassandra (Facebook, 2008) usa consistent hashing como mecanismo central. Cada nó do cluster é responsável por uma faixa do anel; o partition key (definido pelo usuário no schema) determina em qual faixa cada row vive. Adicionar nó ao cluster é operação relativamente barata — só uma faixa migra.

DynamoDB (Amazon, 2012) abstrai a mecânica do usuário (você só vê "partition key"), mas internamente usa consistent hashing derivado do design Dynamo original.

ScyllaDB (KVM, 2015 — reescrita C++ do Cassandra) e Riak (Basho, 2009 — agora open source) seguem o mesmo padrão.

Caches distribuídos

Memcached não tem consistent hashing embutido, mas a maioria das bibliotecas client (em Python, Go, .NET) implementa do lado do cliente. Cliente conhece a lista de servidores; aplica consistent hashing localmente para decidir onde ler/ gravar.

Redis Cluster usa um esquema de hash slots (16384 slots distribuídos entre nós) — variante de consistent hashing onde o anel é discreto. Cada chave mapeia para um slot via CRC16(key) mod 16384; cada slot é atribuído a um nó. Ressharding redistribui slots, não chaves individuais.

CDN e edge networks

CDNs usam consistent hashing para mapear "qual PoP cacheia esse URL". Cliente em São Paulo solicita /asset.css; o roteamento interno do CDN decide qual servidor dentro do PoP de São Paulo é responsável. Se um servidor cai, apenas seu pedaço migra.

Cloudflare, Fastly, Akamai — todos usam variantes. Algumas com modificações específicas ( weighted consistent hashing para diferentes capacidades; rendezvous hashing como alternativa).

Load balancers

Load balancers L4/L7 modernos têm consistent hashing como algoritmo opcional. Útil quando há cache local por instância — mantém afinidade cliente↔instância sem cookies (e, importantemente, sem o problema de "instância nova captura todo o cache").

NGINX: hash $request_uri consistent;. Envoy: ring_hash ou maglev (algoritmo do Google, similar). HAProxy: balance hdr ou balance uri com modo consistent.

Implementação básica em código

Para fixar o algoritmo, vale ver implementação mínima. Cada linguagem implementa similarmente.

using System.Security.Cryptography;
using System.Text;

public class ConsistentHashRing<T> where T : notnull
{
    private readonly SortedDictionary<uint, T> _ring = new();
    private readonly int _virtualNodes;

    public ConsistentHashRing(int virtualNodes = 100) => _virtualNodes = virtualNodes;

    public void AddNode(T node)
    {
        for (int i = 0; i < _virtualNodes; i++)
        {
            uint hash = Hash($"{node}_{i}");
            _ring[hash] = node;
        }
    }

    public void RemoveNode(T node)
    {
        for (int i = 0; i < _virtualNodes; i++)
        {
            uint hash = Hash($"{node}_{i}");
            _ring.Remove(hash);
        }
    }

    public T GetNode(string key)
    {
        if (_ring.Count == 0) throw new InvalidOperationException("ring is empty");

        uint keyHash = Hash(key);
        // primeiro servidor com hash >= keyHash (ou volta para primeiro)
        var found = _ring.FirstOrDefault(kv => kv.Key >= keyHash);
        return found.Value is null ? _ring.First().Value : found.Value;
    }

    private static uint Hash(string s)
    {
        using var md5 = MD5.Create();
        byte[] bytes = md5.ComputeHash(Encoding.UTF8.GetBytes(s));
        return BitConverter.ToUInt32(bytes, 0);
    }
}

// uso
var ring = new ConsistentHashRing<string>();
ring.AddNode("cache-1.internal");
ring.AddNode("cache-2.internal");
ring.AddNode("cache-3.internal");

string server = ring.GetNode("user:42:profile");
// sempre o mesmo servidor para essa chave, até mudança no ring

# pip install uhashring

from uhashring import HashRing

# inicializa com nós
ring = HashRing(nodes=[
    "cache-1.internal",
    "cache-2.internal",
    "cache-3.internal",
])

# busca nó por chave
server = ring.get_node("user:42:profile")
print(server)  # sempre o mesmo até a frota mudar

# adicionar nó
ring.add_node("cache-4.internal")
# após isso, ~25% das chaves migrou (próximo de 1/4)
# mas ~75% continua nos mesmos servidores

# implementação manual (educacional)
import hashlib
import bisect

class Ring:
    def __init__(self, virtual_nodes=100):
        self.virtual_nodes = virtual_nodes
        self.hashes = []        # ordenado
        self.hash_to_node = {}

    def _hash(self, s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.virtual_nodes):
            h = self._hash(f"{node}_{i}")
            bisect.insort(self.hashes, h)
            self.hash_to_node[h] = node

    def get_node(self, key):
        h = self._hash(key)
        idx = bisect.bisect_right(self.hashes, h) % len(self.hashes)
        return self.hash_to_node[self.hashes[idx]]

package main

import (
    "fmt"
    "github.com/buraksezer/consistent"
    "github.com/cespare/xxhash/v2"
)

type Member string
func (m Member) String() string { return string(m) }

type hasher struct{}
func (h hasher) Sum64(data []byte) uint64 { return xxhash.Sum64(data) }

func main() {
    cfg := consistent.Config{
        PartitionCount:    271,        // número de partições
        ReplicationFactor: 20,         // virtual nodes por nó físico
        Load:              1.25,       // tolerância de desbalanceamento
        Hasher:            hasher{},
    }
    ring := consistent.New(nil, cfg)

    ring.Add(Member("cache-1.internal"))
    ring.Add(Member("cache-2.internal"))
    ring.Add(Member("cache-3.internal"))

    // localizar nó por chave
    member := ring.LocateKey([]byte("user:42:profile"))
    fmt.Println(member)

    // bounded-load consistent hashing — limita carga máxima por nó
    // se um nó saturar (acima de Load * média), próximo nó é escolhido
}

Variantes — rendezvous hashing e jump hash

Consistent hashing tem variantes que merecem reconhecimento. Cada uma tem nicho próprio.

Rendezvous hashing (HRW — Highest Random Weight)

Proposto em 1996 por Thaler e Ravishankar — anterior ao Karger. Algoritmo: para cada chave, calcule hash(key, server) para todos os servidores, escolha o servidor com maior valor. Tem propriedades similares ao consistent hashing clássico (1/N de movimento ao adicionar/remover), sem precisar manter um anel — apenas a lista de servidores.

Ganha quando: lista de servidores é pequena (dezenas), porque calcular hash N vezes por chave é viável. Mais simples de implementar do que anel. Perde quando: muitos servidores (custo O(N) por lookup vira problemático).

Jump consistent hash

Proposto por Lamping & Veach (Google, 2014). Algoritmo determinístico que mapeia chave → bucket (servidor) sem manter estado nenhum. Usa apenas o número de buckets atual.

// implementação canônica em ~10 linhas
int jumpHash(long key, int numBuckets) {
    long b = -1, j = 0;
    while (j < numBuckets) {
        b = j;
        key = key * 2862933555777941757L + 1;
        j = (long)((b + 1) * (1.0 / ((double)((key >> 33) + 1) / (1L << 31))));
    }
    return (int)b;
}

Ganha quando: número de servidores muda apenas por crescimento (sempre adicionar, não remover do meio). Simples, rápido, sem estado. Perde quando: precisa remover servidor específico (não é arbitrariamente removível) ou pesos heterogêneos.

Maglev hashing

Proposto pelo Google em 2016 (load balancer Maglev). Tabela de tamanho fixo (tipicamente 65537 entradas) pré-computada, onde cada entrada aponta para um servidor. Lookup é O(1) puro. Reconstrução da tabela após mudança no pool é cara, mas raramente necessária.

Usado por Envoy como algoritmo maglev. Para load balancers de alto throughput, maglev oferece performance superior a ring hash.

Bounded-load consistent hashing

Consistent hashing puro pode ter desbalanceamento mesmo com virtual nodes — alguns servidores ficam ligeiramente mais carregados que outros. Em sistemas onde isso importa, há variante moderna.

Bounded-load consistent hashing (Mirrokni, Thorup, Zadimoghaddam, 2018) limita explicitamente a carga máxima por servidor. Se a escolha "natural" no anel já está saturada (acima de média × fator de tolerância, tipicamente 1.25), caminha para o próximo servidor no anel.

Vorpal: o Google usa essa variante em sistemas internos. Bibliotecas Go modernas (incluindo a buraksezer/consistent mostrada no lang-compare) implementam. Para sistemas de produção com SLO agressivo de latência, vale conhecer.

Anti-padrões frequentes

Hash modular em sistema com mudança frequente. Já visto. Adicionar nó causa cache thundering. Em qualquer sistema com auto- scaling, sempre prefira consistent hashing.

Poucos virtual nodes. Implementação naive com 1 virtual node por servidor físico tem distribuição desigual sob load. Defesa: 100-200 virtual nodes por servidor é faixa razoável; testar empiricamente para confirmar uniforme.

Hash function fraca. Hash com colisões ou distribuição não-uniforme arruina balanceamento. MD5 ou SHA-256 são overkill mas funcionam; xxhash, MurmurHash3, FNV são mais rápidos e têm qualidade adequada.

Não considerar replicação. Em sistemas com replicação (Cassandra, Riak), cada chave vive em N servidores consecutivos no anel, não 1. Configurar replication_factor implica que consistent hashing precisa entender a "vizinhança" no anel — não apenas o "primeiro responsável".

Re-hashing chaves quando virtual nodes mudam. Se você muda o número de virtual nodes (de 100 para 200, por exemplo), a posição de cada servidor no anel muda — e portanto chaves migram. Configurar virtual nodes deveria ser decisão única, não ajustada em runtime.

Por que importa para a sua carreira

Consistent hashing é vocabulário canônico em entrevistas de design para sistemas distribuídos. "Como você distribuiria cache entre 100 servidores?" é pergunta direta — a resposta forte explica por que mod N falha, descreve o anel, menciona virtual nodes para balanceamento, e referencia Dynamo/Cassandra. Em revisão de design, detectar uso de hash modular onde consistent hashing seria correto evita problemas de cache cold em deploy ou auto-scaling. Em pos-mortem de "cache hit rate caiu para zero após adicionar servidor", o diagnóstico estrutural é "estamos usando hash modular". Em discussão de arquitetura de sistema com pretensão distribuída, articular consistent hashing como primitiva é vocabulário que mostra maturidade.

Como praticar

1. Implementação do zero. Em sua linguagem principal, implemente consistent hash ring com virtual nodes. Teste empiricamente: adicione/remova nós e meça quantas chaves migram. Compare com hash modular. Esse exercício, feito uma vez, fixa a intuição.
2. Comparar variantes. Implemente (ou use bibliotecas para) consistent hashing clássico, rendezvous hashing, e jump hash. Para cada um, meça: tempo de lookup, qualidade de distribuição, % de chaves movidas em adição/remoção. Documente trade-offs. Esse é exercício avançado mas calibra escolha de algoritmo.
3. Hot key simulation. Configure um sistema de cache com consistent hashing e simule carga onde 1 chave recebe 50% do tráfego. Meça o balanceamento (RPS por nó). Implemente uma estratégia de mitigação (réplica em N nós) e compare. Esse exercício torna concreto o problema de hot key e a solução.