Camada Zero · 27 · Consistent Hashing

Hashing por módulo (key % N) quebra feio quando o N muda: trocar o número de servidores remapeia quase tudo. Consistent hashing põe nós e chaves no mesmo anel e só mexe numa fração quando a topologia muda. Mexe nos nós aqui embaixo e olha o contador.
← voltar à trilha
0Nós
0Chaves
0Movidas na última mudança
—Carga max / min
◆ losango = nó (vnode) chave (cor = nó dono) contorno branco = movida agora
OperaçãoCusto
Lookup (chave → nó)O(log n)
Add/remove nó~K/n chaves movem
Por módulo (comparação)~quase K movem
Cada chave pertence ao primeiro nó no sentido horário do anel. Adicionar ou remover um nó mexe só nas chaves daquele trecho, perto de K/n, e deixa o resto parado. Por isso consistent hashing segura cache distribuído e sharding sem derrubar o backend a cada mudança de topologia. Os virtual nodes (vnodes) espalham cada nó físico em vários pontos pra equilibrar a carga.

O ring em Go

type Ring struct {
    hashes []uint32          // vnodes ordenados
    nodes  map[uint32]string // hash -> nó
    vnodes int
}

func (r *Ring) Add(node string) {
    for i := 0; i < r.vnodes; i++ {
        h := hash(fmt.Sprintf("%s#%d", node, i))
        r.hashes = append(r.hashes, h)
        r.nodes[h] = node
    }
    sort.Slice(r.hashes, func(i, j int) bool {
        return r.hashes[i] < r.hashes[j]
    })
}

func (r *Ring) Get(key string) string {
    if len(r.hashes) == 0 { return "" }
    h := hash(key)
    // 1º vnode com hash >= h (busca binária do módulo 02)
    i := sort.Search(len(r.hashes), func(i int) bool {
        return r.hashes[i] >= h
    })
    if i == len(r.hashes) { i = 0 } // wrap
    return r.nodes[r.hashes[i]]
}

🧠 Desafio — Consistent Hashing

Brinca com o anel aqui de cima antes de responder. As duas últimas são de reflexão: escreve a sua e só então revela o modelo.

🔧 Prática — ache o bug

Esse roteador de cache distribuído tem um problema sério ao escalar. Clica na linha do bug.