Hashing consistente explicado: anel de hash, nós virtuais e rebalanceamento

Você espalha um cache por dez servidores com hash(key) % 10. O tráfego cresce, você adiciona um décimo primeiro servidor e a taxa de acertos despenca: quase toda chave agora cai em outro servidor, então o cache fica frio em todo lugar ao mesmo tempo e o banco de dados por trás dele recebe a carga inteira. O hashing consistente existe justamente para evitar isso.

Este post explica o anel de hash e os nós virtuais com um diagrama, mede quanto eles ajudam, mostra uma implementação compacta e compara as alternativas que você vai encontrar em sistemas reais: rendezvous hashing, jump hash, Maglev e slots de hash fixos.

Por que o hashing por módulo quebra

Com server = hash(key) % N, o mapeamento depende de N. Mude N, e uma chave só fica onde está se o seu hash der o mesmo resto para os dois valores, o que é raro. Em uma simulação rápida com um milhão de chaves:

O ideal é 1/11, cerca de 9,1%: o servidor novo deveria ficar com a sua parte justa e mais nada deveria mudar de lugar. O anel chega perto; a diferença que sobra vem do fato de os tokens do servidor novo caírem em arcos um pouco maiores que a média.

Para um cache, a diferença é entre uma breve queda na taxa de acertos e uma partida a frio. Para um banco de dados com sharding ou um conjunto de workers com estado, é a diferença entre mover um décimo dos dados e mover quase tudo.

O anel de hash

O hashing consistente, apresentado por Karger e colegas em 1997 para cache web, mapeia servidores e chaves no mesmo espaço de hash circular, por exemplo os inteiros de 0 a 2^64 - 1, com o maior valor voltando para 0.

1. Aplique o hash ao nome de cada servidor para obter uma posição no anel.
2. Aplique o hash a cada chave para obter uma posição no anel.
3. Ande no sentido horário a partir da posição da chave. O primeiro servidor que você encontrar é o dono da chave.

Adicionar um servidor o coloca em uma posição, e ele assume só as chaves entre o seu antecessor e ele mesmo. Todas as outras chaves ficam onde estavam. Remover um servidor passa as chaves dele para o próximo servidor no sentido horário. Nada mais muda.

Nós virtuais: corrigindo o desequilíbrio

Com uma posição por servidor, os arcos entre servidores são aleatórios e desiguais, então alguns servidores ficam com uma parte do anel muito maior que outros. A mesma simulação com dez servidores mostra o tamanho do problema:

A solução é dar a cada servidor muitas posições, chamadas nós virtuais ou tokens, aplicando o hash a nomes como cache-a#0, cache-a#1 e assim por diante. Os nós virtuais trazem ainda outras duas vantagens:

• Pesos. Um servidor com o dobro de memória recebe o dobro de tokens.
• Falhas mais suaves. Quando um servidor morre, os seus muitos arcos pequenos vão para muitos sucessores diferentes, então a carga dele se espalha pelo cluster em vez de dobrar a carga de um único vizinho.

O custo é uma tabela de lookup maior e mais metadados para mover quando os membros mudam. O Cassandra mostra esse trade-off na prática: ele usava 256 tokens por nó por padrão até a versão 4.0 baixar o padrão para 16, junto com um algoritmo de alocação de tokens que posiciona esses 16 de forma uniforme em vez de aleatória.

Uma implementação pequena

Um anel é uma lista ordenada de posições de tokens mais uma busca binária:

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

As buscas custam O(log T) para T tokens. Versões de produção também tratam colisões de tokens e mantêm idêntica a visão de membros de cada cliente, já que dois clientes com listas de servidores diferentes discordam sobre onde as chaves ficam.

Replicação no anel

Sistemas de armazenamento usam o anel para posicionamento, além de roteamento. O artigo do Dynamo, da Amazon, guarda cada chave nos primeiros N servidores distintos no sentido horário a partir da sua posição, a sua preference list, pulando tokens extras que pertencem a um servidor que já está na lista. Com N = 3, perder um servidor ainda deixa duas cópias de tudo o que ele guardava, em servidores que são seus vizinhos no anel.

A mesma ideia de “andar no sentido horário e pular duplicatas” se estende a racks e zonas: pule tokens até que as réplicas cubram domínios de falha diferentes.

Alternativas que você vai encontrar

O jump consistent hash combina com armazenamento com sharding em que os shards são numerados e só crescem. O rendezvous hashing combina com conjuntos pequenos de servidores, em que O(N) por busca não importa. Os slots de hash trocam o posicionamento automático por movimentações explícitas, controladas pelo operador, algo que muitos times preferem para bancos de dados.

Hot keys e cargas limitadas

O hashing consistente equilibra chaves, não tráfego. Um usuário famoso ou um produto viral continua caindo em um único servidor. O hashing consistente com cargas limitadas (bounded loads) limita cada servidor a uma porcentagem definida acima da média e manda o excedente para o próximo servidor no sentido horário. O HAProxy implementa isso com a configuração hash-balance-factor. Para chaves realmente quentes, você ainda precisa replicar essa chave, agrupar requisições ou colocar um pequeno cache local na frente.

Armadilhas operacionais

• Trocar a função de hash ou o esquema de tokens embaralha tudo, exatamente como o hashing por módulo. Trate isso como uma migração.
• Os membros precisam ser consistentes. Distribua a lista de servidores a partir de uma única fonte, como um serviço de coordenação ou a configuração do balanceador de carga, e mude-a em um único passo.
• Servidores instáveis causam churn. Um servidor que falha nos health checks a cada poucos minutos leva as suas chaves de um lado para o outro. Adicione histerese antes de removê-lo e adicioná-lo de novo.
• Servidores novos começam frios. Um nó de cache novo recebe a sua parte das requisições na hora; aqueça-o ou aumente o peso dele aos poucos se o backend não aguentar os cache misses.

O diagrama do anel de hash

Como ler:

• O círculo é o espaço de hash. As posições crescem no sentido horário, e o topo é onde o maior valor volta a zero.
• Os tokens coloridos são nós virtuais. Cada cor é um servidor, e cada servidor tem vários tokens espalhados pelo anel.
• As chaves ficam nas posições dos seus hashes, e as setas apontam no sentido horário para o token que é dono delas.
• Os tokens tracejados pertencem ao servidor D, que está sendo adicionado. Só as chaves logo antes dos tokens de D, no sentido anti-horário, mudam de dono.
• A legenda e o bloco Markdown listam os servidores e os números de movimentação da simulação acima.

Desenhar esquemas de hashing com clareza

• Desenhe o anel, não uma tabela. A regra do sentido horário é visual; uma tabela de lookup esconde por que só algumas chaves mudam de lugar.
• Pinte os tokens por servidor e adicione uma legenda, em vez de puxar uma aresta de cada token até o seu servidor.
• Mostre uma mudança de membros. Um anel estático explica o roteamento; um anel em que um servidor entra explica todo o sentido da técnica.
• Coloque números reais ao lado: chaves movidas e distribuição da carga. Eles convencem mais que a figura.

O hashing consistente aparece em vários posts de design de sistemas deste blog: no diagrama de sharding de banco de dados, para posicionar dados; no diagrama de balanceador de carga, para roteamento persistente; e no diagrama de estratégias de cache, para caches distribuídos.

Monte no Archboard

1. Entre com Google ou GitHub e crie um diagrama.
2. Adicione uma forma Elipse grande do pack Básico como o anel.
3. Adicione sobre o anel formas Elipse pequenas como tokens, pintadas por servidor: duas para cada um dos servidores A, B e C, e duas tracejadas para o novo servidor D.
4. Adicione quatro nós Redis do pack Dados em uma coluna ao lado do anel como legenda, com as cores dos seus tokens.
5. Adicione as chaves como rótulos Texto do pack Básico sobre o anel, com setas curtas até os tokens donos delas.
6. Adicione um bloco Markdown do pack Básico com os números de movimentação de chaves e de carga.

O exemplo usa 14 nós de diagrama e fica dentro do plano Free.

Perguntas frequentes

Que problema o hashing consistente resolve? Ele mantém a maioria das chaves no mesmo servidor quando servidores são adicionados ou removidos. Com o hashing por módulo, mudar a quantidade de servidores remapeia quase todas as chaves; com o hashing consistente, só cerca de 1/N delas muda de lugar.

O que são nós virtuais no hashing consistente? Cada servidor físico é colocado muitas vezes no anel, com nomes diferentes. Mais posições deixam os arcos mais uniformes, permitem dar pesos aos servidores conforme a capacidade e espalham a carga de um servidor que falhou por muitos outros.

Quantos nós virtuais cada servidor deve ter? O suficiente para uma distribuição uniforme no tamanho do seu cluster: na nossa simulação, 100 por servidor mantiveram o servidor mais carregado a até 7% da média com dez servidores. Sistemas com alocação de tokens mais inteligente, como o Cassandra 4.0 em diante, usam bem menos.

O Redis Cluster usa hashing consistente? Não no sentido do anel. O Redis Cluster mapeia as chaves para 16.384 slots de hash fixos e atribui os slots aos nós; mover dados significa mover slots explicitamente.

Qual é a diferença entre hashing consistente e rendezvous hashing? Os dois movem cerca de 1/N das chaves quando os membros mudam. O rendezvous hashing pontua cada servidor para cada chave e escolhe o maior; não precisa de anel, mas custa O(N) por busca.

Comece grátis — um assento, sem cartão de crédito.