Consistent Hashing#

Problem statement (interviewer prompt)

Design a key-distribution scheme that maps keys to N storage nodes such that adding or removing one node moves only ~K/N keys. Support weighted nodes, replication to neighbours, and handle heterogeneous hardware.

Hash both keys and servers onto a ring; each key is owned by the next server clockwise. Adding/removing 1 server moves only K/N keys.

flowchart LR
  K1[key A]
  K2[key B]
  K3[key C]
  K4[key D]
  N1((Node 1))
  N2((Node 2))
  N3((Node 3))
  K1 --> N1
  K2 --> N2
  K3 --> N3
  K4 --> N1

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class K1,K2,K3,K4 service;
    class N1,N2,N3 queue;

Consistent hashing ring diagram showing node distribution and replica key ranges (N=3), based on Amazon Dynamo paper — Consistent hashing ring with N=3 replicas, as described in the Amazon Dynamo paper. Each node owns a range of the ring; adding/removing a node shifts only 1/N of keys. Source: Flash1984 / Marlus Gancher, Wikimedia Commons (CC BY-SA 3.0)

flowchart TB
  subgraph Hashing[Hash Ring 0..2^32-1]
    direction LR
    H[hash function<br/>MD5 / Murmur3 / xxHash]
    VN[Virtual Nodes /<br/>vnodes per server]
  end

  subgraph Ring[Logical Ring]
    direction LR
    A((vn_A1))
    B((vn_B1))
    C((vn_C1))
    D((vn_A2))
    E((vn_B2))
    F((vn_C2))
    G((vn_A3))
    H1((vn_B3))
    I((vn_C3))
    A --> B --> C --> D --> E --> F --> G --> H1 --> I --> A
  end

  subgraph Servers[Physical Servers]
    SA[Server A]
    SB[Server B]
    SC[Server C]
  end

  subgraph Replication
    REP[Walk N successors<br/>for N replicas]
    Q[Quorum: R+W>N]
  end

  subgraph Membership
    GOSSIP[Gossip protocol<br/>SWIM]
    HC[Failure detector<br/>phi-accrual]
    REBAL[Bootstrap /<br/>handoff]
  end

  Key[key k]
  Key --> H
  H --> Ring
  Ring -. owner = next vnode .-> SA
  Ring -. owner = next vnode .-> SB
  Ring -. owner = next vnode .-> SC
  REP --> SA
  REP --> SB
  REP --> SC
  GOSSIP -.membership.-> Ring
  HC -.detect down.-> REBAL
  REBAL -.move ranges.-> Servers
  VN -.~100-256 vnodes/server.-> Ring

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class H,VN,SA,SB,SC,REP,Q,GOSSIP,HC,REBAL,Key service;
    class A,B,C,D,E,F,G,H1,I queue;

Why virtual nodes#

Without vnodes, ring is uneven; heterogeneous servers can't be weighted.
~100-256 vnodes/server smooths distribution; resize easily.

Replication strategy#

Walk N successor positions on the ring (skip same physical host / rack).
Read/write quorum: R + W > N for consistency.

Variants#

Jump consistent hash (Lamping & Veach): no ring, O(1) memory; only bucket count, no removal of arbitrary nodes.
Rendezvous (HRW) hashing: pick max(hash(key,node)); easy weights.
Maglev hashing (Google): lookup table, near-uniform, ECMP-friendly.

Where it's used#

Memcached client (Ketama), Redis Cluster (slot 0-16383 via CRC16), Cassandra & Dynamo (token ring), Amazon DynamoDB, Riak, Akamai CDN, Google Maglev LB.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	CDN	edge caching for static assets	cdn
`HLD`	Consistent hashing	key placement with minimal remap	consistent-hashing
`HLD`	Raft / Paxos consensus	replicated state machine via majority quorum	consensus-raft-paxos
`HLD`	Leader/follower replication	sync/semi-sync/async replication, failover	replication-leader-follower
`LLD`	Behavioural patterns	Strategy, Observer, State, Command, Chain	behavioral-patterns

Quick reference#

Problem solved#

Plain hash(key) mod N reshuffles ~all keys when N changes. Consistent hashing moves only K/N keys.

Algorithm#

Hash each server → place on ring (with V virtual copies).
Hash each key → find first server clockwise.
To replicate, take next R-1 distinct servers.

Properties#

Movement on add/remove: K/N keys.
Load skew without vnodes: high; with V≈200 vnodes, std-dev tolerable.
Lookup: O(log V·N) with sorted positions + binary search.

Failure handling#

Hinted handoff (Dynamo): if replica down, neighbor stores hint, replays later.
Anti-entropy: Merkle trees compare ranges and repair drift.

Alternatives & when to use#

Algorithm	Pros	Cons
Mod-N	trivial	massive remap on change
Consistent hash + vnodes	flexible	needs lookup table
Jump hash	O(1), no metadata	only sequential nodes
Rendezvous (HRW)	easy weights	O(N) per lookup
Maglev	uniform, fast	needs table reseeding

Refs#

Karger et al. 1997 paper; Dynamo (Amazon); Akamai paper; Maglev (Google 2016).

FAQ#

What is consistent hashing?#

Consistent hashing maps keys and nodes onto a circular hash ring. Each key is owned by the next node clockwise. Adding or removing one node remaps only K/N keys, not the whole dataset.

Why use consistent hashing instead of modulo hashing?#

With modulo hashing, adding one node remaps almost every key, causing a full cache reshuffle. Consistent hashing moves only the keys that belonged to the new node's neighbour, keeping disruption minimal.

What are virtual nodes in consistent hashing?#

Virtual nodes are multiple positions for the same physical node on the ring. They smooth out load imbalance from random hashing and let you assign more virtual nodes to bigger machines for weighted distribution.

Which systems use consistent hashing?#

Amazon Dynamo, Cassandra, Riak, Memcached clients, Akamai CDN, and Discord's Elixir sharding layer all use consistent hashing or a close variant for key-to-node mapping.