O que é hashing consistente?

Question

IT Interview Practice · Accepted Answer

**Hashing consistente** é uma técnica para distribuir dados entre nós (servidores) que **minimiza redistribuição quando nós são adicionados ou removidos** — diferentemente do hashing simples, que remapeia a maioria das chaves quando o número de nós muda. É importante para caches distribuídos, bancos de dados e distribuição de carga.

## O problema com hashing simples

```text
Simple approach: node = hash(key) % N  (N = number of nodes)
  ✗ when N CHANGES (add/remove a node), N changes → MOST keys remap to different nodes →
    massive data movement / cache invalidation (almost everything moves!)
→ adding/removing a server causes huge disruption → bad for dynamic distributed systems.
```

## Como o hashing consistente funciona

```text
Map both NODES and KEYS onto a HASH RING (a circle of hash values):
  → a key belongs to the FIRST node clockwise from it on the ring
  → adding/removing a node only affects keys in ONE segment of the ring (its neighbors) →
    only a SMALL fraction of keys move (≈ K/N, not most of them)
→ minimal redistribution when nodes change → much better for dynamic systems.
```

## Nós virtuais e usos

```text
✓ VIRTUAL NODES → each physical node maps to MANY points on the ring → EVEN distribution
  (avoids uneven load from few nodes/uneven placement) → handles heterogeneous capacity
USES:
  → distributed CACHES (e.g. memcached clusters) — add/remove cache nodes without mass
    invalidation
  → distributed DATABASES (Cassandra, DynamoDB) — partition data across nodes
  → load balancers; any system distributing data/load across a changing set of nodes
```

## Por que isso importa

Entender hashing consistente é um conhecimento valioso de nível sênior porque é uma **técnica fundamental para distribuir dados em sistemas distribuídos dinâmicos**, usada em muitos sistemas reais, portanto é importante para o design de sistemas distribuídos.

O problema que resolve é real e importante: **hashing simples** (`hash(key) % N`) causa **remapeamento da maioria das chaves quando o número de nós muda** (adicionar ou remover um servidor move quase todos os dados — causando movimentação massiva de dados ou invalidação de cache), tornando-o péssimo para sistemas distribuídos dinâmicos onde nós são adicionados e removidos. **Hashing consistente** resolve isso mapeando tanto nós quanto chaves em um **anel hash** (com uma chave pertencendo ao primeiro nó no sentido horário), então **adicionar ou remover um nó move apenas uma pequena fração de chaves** (aquelas em um segmento do anel, ≈ K/N) em vez da maioria — minimizando redistribuição e disrupção quando o conjunto de nós muda.

Entender isso — como o anel funciona e por que minimiza a movimentação de chaves — é o insight chave.

Entender **nós virtuais** (mapear cada nó físico para muitos pontos do anel para distribuição uniforme, evitando a carga desigual que poucos nós ou nós mal posicionados causam, e tratando capacidade heterogênea) reflete como o hashing consistente funciona bem na prática.

Entender os **usos** — caches distribuídos (adicionar/remover nós de cache sem invalidação em massa), bancos de dados distribuídos (Cassandra, particionamento de dados do DynamoDB) e balanceadores de carga — esclarece sua importância, já que é usado em muitos sistemas reais amplamente utilizados.

Hashing consistente é uma técnica de sistemas distribuídos clássica e importante que aparece frequentemente em discussões de design de sistemas.

Como distribuir dados entre um conjunto dinâmico de nós (com disrupção mínima quando nós mudam) é uma necessidade comum em sistemas distribuídos e hashing consistente resolve isso (onde hashing simples falha muito), e como é usado em sistemas reais (caches e bancos de dados distribuídos) e entendê-lo reflete conhecimento de sistemas distribuídos, entender hashing consistente é um conhecimento valioso de nível sênior — uma técnica fundamental para distribuição de dados em sistemas distribuídos dinâmicos, usada em muitos caches e bancos de dados reais, resolvendo o problema de redistribuição de chaves do hashing simples, e um conceito de sistemas distribuídos clássico refletindo a profundidade esperada para papéis sênior projetando sistemas distribuídos.

O problema com hashing simples

Como o hashing consistente funciona

Nós virtuais e usos

Por que isso importa

Perguntas relacionadas