CS Fundamentals Trainer · Guias
Consistent hashing
Por que hash mod N quebra quando os servidores mudam, como o anel e os nós virtuais resolvem isso, com código e alternativas.
17 min de leitura
Consistent hashing é uma forma de decidir qual servidor é dono de qual chave, de modo que, quando servidores entram ou saem, apenas uma pequena parte das chaves precisa se mover. Ele está por baixo de caches, bancos de dados, load balancers e CDNs, e é item básico em entrevistas de design de sistemas. A ideia é pequena o bastante para ser implementada em trinta linhas, e este guia faz isso em quatro linguagens.
1. O problema: espalhar chaves entre servidores
Você tem um cache ou um banco de dados grande demais para uma máquina, então divide as chaves entre N servidores. Você precisa de uma regra que, dada uma chave, sempre aponte o mesmo servidor, a partir de qualquer cliente, sem perguntar a ninguém. A regra óbvia é:
server = hash(key) mod N
Ela espalha as chaves de forma uniforme e não custa nada. Sua falha aparece no momento em que N muda.
O que acontece quando N muda
Adicione um quinto servidor a quatro, e hash(key) mod 4 vira hash(key) mod 5. Para a maioria das chaves a resposta muda. Medi isso com 100 000 chaves:
| Servidores | Chaves que mudaram | Mínimo ideal |
|---|---|---|
| 4 → 5 | 79,9 % | 20 % (1/5) |
| 9 → 10 | 90,0 % | 10 % (1/10) |
| 99 → 100 | 99,0 % | 1 % (1/100) |
Quanto maior o cluster, pior fica: quase todas as chaves se movem por causa de uma única máquina adicionada. Em um cache, isso é um paredão repentino de misses que cai sobre o seu banco de dados. Em um banco de dados, é uma migração de dados enorme. O ideal é que um novo servidor assuma apenas a sua parte justa (1/(N+1) das chaves) e nada mais se mova. O consistent hashing consegue isso [1].
2. O anel
Imagine a faixa de saída da função de hash, digamos de 0 a 2^32 − 1, curvada em um círculo, de modo que o maior valor fique ao lado do 0. Então:
- Coloque cada servidor no anel calculando o hash do seu nome (ou endereço).
- Coloque cada chave no anel calculando o hash da chave.
- Uma chave pertence ao primeiro servidor encontrado no sentido horário a partir da posição da chave (dando a volta no fim).
Diagram: A ring with three servers and four keys (read clockwise)
Lendo a figura: as chaves em 25 e 40 vão no sentido horário até o próximo servidor, B em 55. A chave em 70 vai para C em 90. A chave em 95 passa do fim do anel e dá a volta até A em 10. Cada servidor é dono do trecho do anel que fica entre o seu antecessor e ele mesmo.
Adicionando e removendo servidores
Agora adicione um servidor D na posição 80:
Diagram: Adding Server D at 80 takes keys only from its neighbour
Apenas as chaves entre 55 e 80 (aqui, a chave em 70) mudam de dono, de C para D. Todas as outras chaves ficam onde estavam. Se um servidor sai, apenas as suas chaves se movem, para o próximo servidor no sentido horário. Com N servidores, a parcela esperada que se move é cerca de 1/N. Na minha execução, adicionar um 11º servidor a um anel de 10 moveu 8,9 % das chaves, contra os 9,1 % ideais (outro conjunto de nomes deu 10,0 %: o número é aleatório, centrado em 1/N); e toda chave que se moveu foi para o novo servidor e para nenhum outro lugar.
3. Carga desigual e nós virtuais
Há uma pegadinha. Com um ponto por servidor, os servidores caem em lugares aleatórios do círculo, e os espaços entre eles são muito desiguais. Um servidor pode ser dono de um espaço três vezes maior que o de outro, e outro pode receber quase nada. Medi a carga para 10 servidores e 100 000 chaves. Como o resultado depende da sorte de onde os pontos caem, repeti com 12 conjuntos diferentes de nomes de servidores e mostro a execução típica (mediana) e a pior das 12:
| Pontos por servidor | Servidor mais ocupado vs média (mediana / pior) | Servidor mais ocioso vs média (mediana / pior) |
|---|---|---|
| 1 | 2,68 × / 3,48 × | 0,09 × / 0,01 × |
| 10 | 1,42 × / 1,81 × | 0,60 × / 0,45 × |
| 100 | 1,15 × / 1,22 × | 0,85 × / 0,72 × |
| 200 | 1,12 × / 1,20 × | 0,89 × / 0,83 × |
| 500 | 1,07 × / 1,12 × | 0,94 × / 0,89 × |
| 1 000 | 1,04 × / 1,11 × | 0,95 × / 0,92 × |
Com 100 servidores o mesmo teste é um pouco pior (com 200 pontos: mais ocupado 1,19 ×, mais ocioso 0,81 ×; com 1 000 pontos: 1,11 × e 0,89 ×), porque a parte de cada servidor é menor e as diferenças aleatórias pesam mais. Parte do que você vê é também o próprio teste: 100 000 chaves em 100 servidores são apenas 1 000 chaves cada, então as contagens têm seu próprio ruído de alguns por cento.
A correção são os nós virtuais ("vnodes"): cada servidor é colocado no anel muitas vezes, sob nomes como server-a#0, server-a#1, server-a#2... A sua parte passa a ser a soma de muitos espaços pequenos e aleatórios, e somas de muitos pedaços pequenos e aleatórios ficam próximas de uniformes. A dispersão diminui apenas com a raiz quadrada do número de pontos: dez vezes mais pontos a deixam cerca de três vezes menor. Então 100 a 200 pontos por servidor (um padrão comum) dão uma carga dentro de aproximadamente ±15 a 25 % da média, e chegar a ±10 % exige de várias centenas a mil. Escolha o número conforme o desequilíbrio com que você consegue conviver. Nós virtuais têm um segundo benefício: quando um servidor sai, sua carga se espalha por muitos outros servidores em vez de cair inteira sobre um vizinho (que poderia então falhar também, e assim por diante). Eles também permitem dar a uma máquina maior mais pontos do que a uma menor, proporcionalmente à sua capacidade.
O custo é memória e tempo de busca: 100 servidores com 200 pontos cada são 20 000 entradas; com 1 000 pontos são 100 000, ainda pouco. Buscar uma chave é uma busca binária em um array ordenado, que é rápida (cerca de 15 passos).
4. Uma implementação funcional
O anel é um array ordenado de posições. Uma busca calcula o hash da chave e encontra a primeira posição maior que ele com busca binária; se não houver nenhuma, volta para a primeira entrada. A seguir vêm quatro versões (escolha uma linguagem nas abas; sua escolha é lembrada). Todas usam SHA-256 como hash e mantêm seus primeiros 8 bytes (6 em JavaScript, para ficar dentro do que um número guarda com exatidão). Um hash rápido não criptográfico também serve, desde que espalhe bem os valores.
import bisect
import hashlib
def h(s):
return int.from_bytes(hashlib.sha256(s.encode()).digest()[:8], "big")
class Ring:
def __init__(self, vnodes=150):
self.vnodes = vnodes
self.hashes = [] # sorted positions on the ring
self.owner = {} # position -> server
self.points_of = {} # server -> how many points it has
def add(self, server, weight=1.0):
if server in self.points_of: # adding twice would store the points twice
return
count = round(self.vnodes * weight) # a bigger machine gets more points
for i in range(count):
pos = h(f"{server}#{i}")
self.owner[pos] = server
bisect.insort(self.hashes, pos)
self.points_of[server] = count
def remove(self, server):
count = self.points_of.pop(server, None)
if count is None:
return
for i in range(count):
pos = h(f"{server}#{i}")
del self.owner[pos]
self.hashes.remove(pos)
def get(self, key):
return self.get_n(key, 1)[0]
def get_n(self, key, n):
"""The owner and the next n-1 distinct servers clockwise (the replicas)."""
if n > len(self.points_of):
raise LookupError("not enough servers")
start = bisect.bisect_right(self.hashes, h(key))
found = []
for step in range(len(self.hashes)):
server = self.owner[self.hashes[(start + step) % len(self.hashes)]] # % wraps around
if server not in found: # skip the other points of a server we already have
found.append(server)
if len(found) == n:
break
return found
type Ring struct {
vnodes int
hashes []uint64 // sorted positions on the ring
owner map[uint64]string // position -> server
members map[string]bool // servers on the ring
}
func NewRing(vnodes int) *Ring {
return &Ring{vnodes: vnodes, owner: map[uint64]string{}, members: map[string]bool{}}
}
func hash(s string) uint64 {
sum := sha256.Sum256([]byte(s))
return binary.BigEndian.Uint64(sum[:8])
}
func (r *Ring) Add(server string) {
if r.members[server] {
return // adding twice would store the points twice
}
r.members[server] = true
for i := 0; i < r.vnodes; i++ {
pos := hash(fmt.Sprintf("%s#%d", server, i))
r.owner[pos] = server
r.hashes = append(r.hashes, pos)
}
sort.Slice(r.hashes, func(a, b int) bool { return r.hashes[a] < r.hashes[b] })
}
func (r *Ring) Remove(server string) {
if !r.members[server] {
return
}
delete(r.members, server)
kept := r.hashes[:0]
for _, pos := range r.hashes {
if r.owner[pos] == server {
delete(r.owner, pos)
continue
}
kept = append(kept, pos)
}
r.hashes = kept
}
// Get returns the server that owns key, or "" when the ring is empty.
func (r *Ring) Get(key string) string {
if len(r.hashes) == 0 {
return ""
}
x := hash(key)
i := sort.Search(len(r.hashes), func(i int) bool { return r.hashes[i] > x })
if i == len(r.hashes) {
i = 0 // wrap around
}
return r.owner[r.hashes[i]]
}
const crypto = require("node:crypto");
// 48 bits are plenty, and a JavaScript number holds them exactly
const h = (s) => crypto.createHash("sha256").update(s).digest().readUIntBE(0, 6);
class Ring {
constructor(vnodes = 150) {
this.vnodes = vnodes;
this.points = []; // { pos, server }, sorted by pos
this.members = new Set();
}
add(server) {
if (this.members.has(server)) return; // adding twice would store the points twice
this.members.add(server);
for (let i = 0; i < this.vnodes; i++) {
this.points.push({ pos: h(`${server}#${i}`), server });
}
this.points.sort((a, b) => a.pos - b.pos);
}
remove(server) {
if (!this.members.delete(server)) return;
this.points = this.points.filter((p) => p.server !== server);
}
get(key) {
if (this.points.length === 0) throw new Error("no servers");
const x = h(key);
let lo = 0;
let hi = this.points.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.points[mid].pos > x) hi = mid;
else lo = mid + 1;
}
return this.points[lo % this.points.length].server; // % wraps around
}
}
using System.Buffers.Binary;
using System.Security.Cryptography;
using System.Text;
public sealed class Ring
{
private readonly int _vnodes;
private readonly List<(ulong Pos, string Server)> _points = new(); // sorted by Pos
private readonly HashSet<string> _members = new();
public Ring(int vnodes = 150) => _vnodes = vnodes;
private static ulong Hash(string s) =>
BinaryPrimitives.ReadUInt64BigEndian(SHA256.HashData(Encoding.UTF8.GetBytes(s)));
public void Add(string server)
{
if (!_members.Add(server)) return; // adding twice would store the points twice
for (int i = 0; i < _vnodes; i++) _points.Add((Hash($"{server}#{i}"), server));
_points.Sort((a, b) => a.Pos.CompareTo(b.Pos));
}
public void Remove(string server)
{
if (_members.Remove(server)) _points.RemoveAll(p => p.Server == server);
}
public string Get(string key)
{
if (_points.Count == 0) throw new InvalidOperationException("no servers");
ulong x = Hash(key);
int lo = 0, hi = _points.Count;
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (_points[mid].Pos > x) hi = mid; else lo = mid + 1;
}
return _points[lo % _points.Count].Server; // % wraps around
}
}
add ignora um servidor que já está no anel (adicionar duas vezes guardaria seus pontos duas vezes, e um único remove deixaria posições órfãs que nenhum servidor possui). São esboços: uma versão real protege o anel com um lock de leitura e escrita (leituras são muito mais comuns que mudanças) e troca por um anel inteiro novo em vez de editar o que está ativo. Remover é linear no número de pontos, o que é aceitável para um punhado de mudanças por dia.
Experimente você mesmo: adicione 10 servidores, mapeie 100 000 chaves, adicione um 11º servidor e conte quantas chaves mudaram de dono. Você deve ver cerca de 9 a 10 %, e toda chave que mudou deve agora pertencer ao novo servidor. (O valor exato muda com os nomes dos servidores: vi 8,9 % em uma execução e 10,0 % em outra, contra os 9,1 % ideais.)
5. Replicação: mais de um dono
Sistemas reais mantêm várias cópias de cada chave. Com um anel, a regra natural é: o dono é o primeiro servidor no sentido horário, e as réplicas são os próximos servidores no sentido horário depois dele, pulando nós virtuais que pertencem a um servidor já escolhido (senão duas cópias poderiam cair na mesma máquina). O Dynamo da Amazon chama isso de preference list [2]. Na versão em Python acima, get_n(key, 3) a retorna: o dono e os dois próximos servidores distintos. O Cassandra funciona da mesma forma. Se um servidor morre, o próximo da lista já tem uma cópia e assume, e o anel dá a cada servidor restante uma parte pequena e igual do trabalho extra.
6. Quando o anel não é a resposta
O consistent hashing tem vários parentes, e saber por que eles existem é uma boa resposta em entrevistas.
| Técnica | Ideia | Boa em | Limites |
|---|---|---|---|
| Anel com vnodes | Descrito acima | Entradas e saídas arbitrárias, replicação | Memória para os pontos; a carga ainda não é perfeitamente uniforme |
| Rendezvous (highest random weight) hashing | Para uma chave, calcule hash(key, server) para cada servidor e escolha o mais alto | Muito simples, uniforme, sem anel para armazenar | A busca custa O(N); aceitável para dezenas de servidores [3] |
| Jump consistent hash | Uma função minúscula (poucas linhas, sem memória) mapeia uma chave a um número de 0 a N − 1 | Muito uniforme e extremamente rápida | Os servidores precisam ser numerados de 0..N−1; só dá para adicionar ou remover no fim, então serve para armazenamento com shards, não para caches em que qualquer nó pode falhar [4] |
| Hash slots (Redis Cluster) | 16 384 slots fixos; cada chave mapeia para um slot com CRC16; uma tabela atribui slots a servidores | Explícito, fácil de rebalancear um slot por vez | Você gerencia a tabela de slots [5] |
| Bounded loads | Um anel, mas um servidor que já está acima de um teto de carga repassa a chave ao próximo | Evita hot spots em dados enviesados | Contabilidade extra [6] |
| Maglev hashing | Uma tabela de busca preenchida de modo que cada servidor receba uma parte igual e poucas entradas mudem | Load balancers: buscas rápidas e carga muito uniforme | A tabela é reconstruída na mudança; um pouco de perturbação na remoção [7] |
Duas delas têm só algumas linhas (Python de novo; h é a função de hash de antes):
def rendezvous(key, servers):
# every server "bids" for the key; the highest bid wins, and a removed server only loses its own keys
return max(servers, key=lambda s: h(f"{s}|{key}"))
def jump_hash(key, buckets):
# key is a 64-bit integer; returns a bucket number from 0 to buckets - 1
b, j = -1, 0
while j < buckets:
b = j
key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF
j = int((b + 1) * (1 << 31) / ((key >> 33) + 1))
return b
Note que nenhuma delas resolve uma hot key: se uma chave recebe metade de todas as requisições, quem a possui fica sobrecarregado, por melhor que as chaves estejam espalhadas. Para isso você replica a chave, coloca um cache na frente ou a divide em várias chaves.
7. Onde você o encontra
- Caches distribuídos: clientes de memcached costumam usar um anel (conhecido como ketama) para que perder um nó de cache não esvazie o cache inteiro.
- Bancos de dados: Dynamo, Cassandra e Riak particionam os dados em um anel.
- Balanceamento de carga: enviar o mesmo usuário ou chave ao mesmo backend (para que seu cache local esteja aquecido), sem manter uma tabela de atribuições.
- CDNs e armazenamentos de objetos: escolher qual nó guarda qual objeto.
- Sharding no seu próprio app: uma biblioteca decide qual banco de dados guarda um cliente. Encurtadores de URL e caches o usam para isso.
8. Perguntas que entrevistadores gostam de acrescentar
"Por que não simplesmente manter uma tabela de chave → servidor?"
Uma tabela funciona quando o número de chaves é pequeno, mas então ela própria é um grande pedaço de estado compartilhado de que todo cliente precisa e que precisa se manter consistente. O hash não precisa de nenhum estado compartilhado além da lista de servidores.
"Como os clientes ficam sabendo que um servidor entrou?"
A lista de servidores precisa chegar a todo cliente: por um serviço de coordenação (ZooKeeper, etcd, Consul), um protocolo gossip (Dynamo e Cassandra) ou uma configuração distribuída. Por um curto período os clientes podem discordar sobre o anel. Uma leitura pode então ir ao antigo dono e errar. Isso é aceitável para um cache. Para um banco de dados, o sistema precisa transferir os dados com cuidado: copiar primeiro, trocar a propriedade depois.
"O que acontece com os dados de um servidor removido?"
Em uma queda, as réplicas os têm. Em uma remoção planejada, o servidor que sai envia suas faixas aos novos donos antes de partir. Quando um servidor é adicionado, ele precisa buscar suas faixas nos donos atuais, e até que as tenha os antigos donos continuam respondendo.
"Quantos nós virtuais?"
O suficiente para que a dispersão seja aceitável. Nos meus testes, de 100 a 200 por servidor deixaram o servidor mais ocupado de 12 a 25 % acima da média, e cerca de 1 000 o levaram para 4 a 11 %. Mais pontos uniformizam mais a carga, ao preço de memória e reconstruções mais lentas. Dê pesos conforme o tamanho da máquina e meça nas suas próprias chaves, porque o resultado muda de execução para execução.
"Como você lida com um servidor lento, não morto?"
O anel não sabe nada sobre saúde. Adicione health checks e remova servidores com falha do anel (ou pule-os e use a próxima réplica). Para evitar oscilação, exija várias verificações falhas antes da remoção.
9. Coisas a mencionar em uma entrevista
- Comece com
hash mod Ne mostre por que quebra: quase tudo se move. - Desenhe o anel e diga que uma chave vai para o próximo servidor no sentido horário.
- Diga que apenas cerca de 1/N das chaves se movem quando um servidor muda.
- Traga você mesmo o problema da dispersão desigual e resolva-o com nós virtuais e pesos.
- Mencione a replicação ao longo do anel e como os clientes ficam sabendo das mudanças.
- Cite uma alternativa (rendezvous, jump hash, hash slots) e quando você a preferiria.
Resumo rápido
hash(key) mod Nmove quase toda chave quando N muda.- Um anel atribui cada chave ao próximo servidor no sentido horário; adicionar ou remover um servidor move apenas cerca de 1/N das chaves.
- Um ponto por servidor dá carga desigual; de 100 a 200 nós virtuais por servidor a deixam quase uniforme.
- A busca é uma busca binária em um array ordenado de posições.
- As réplicas são os próximos servidores distintos ao longo do anel.
- Rendezvous hashing, jump hash, hash slots e Maglev resolvem o mesmo problema com trade-offs diferentes.
- Uma hot key não é um problema de hash; faça cache ou divida-a.
Fontes
- Karger et al., Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997. A ideia original.
- DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. O anel, os nós virtuais e as preference lists.
- Wikipedia, Rendezvous hashing. O esquema highest random weight de Thaler e Ravishankar.
- Lamping e Veach, A Fast, Minimal Memory, Consistent Hash Algorithm, 2014. Jump consistent hash.
- Documentação do Redis, Redis cluster specification. Os 16 384 hash slots.
- Mirrokni, Thorup e Zadimoghaddam, Consistent Hashing with Bounded Loads, 2016.
- Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI 2016.
Pratique este tema: System Design System Design › Distributed systems