1. The problem: why hash(key) mod N breaks when N changes

Instagram's feed cache spreads hundreds of millions of keys (timelines, counters, profile objects) across many Redis/Memcached servers. Each app server must decide, with no coordination, which cache server holds a key. The obvious answer:

server_index = hash(key) mod N        # N = number of cache servers

It's fast, stateless and — with a good hash — spreads keys evenly. The problem is what happens when N changes: a server crashes (N decreases) or you add capacity before a big event (N increases). Almost every key's mod N result changes, so almost every key is now "on the wrong server".

1.1 Worked example: 12 keys, 4 → 5 servers

Take keys whose hashes are 0–11 for simplicity:

8 of 12 keys moved (67%) here. In general a key stays put only if h mod 4 = h mod 5, which is true for 4 out of every 20 consecutive hash values — so over many keys, 80% move. The general rule for going from N to N+1 servers with mod hashing: only about 1/(N+1) of keys stay; the fraction that moves is N/(N+1). The bigger the cluster, the worse it gets: going from 100 to 101 servers moves ~99% of keys — to add 1% capacity!

Assume Instagram's cache tier: 100 M hot keys on 4 servers, 95% hit ratio, 1 M reads/s.
Add a 5th server with mod-N routing:
  80 M keys are now looked up on the "wrong" server → miss
  hit ratio collapses from 95% to roughly 0.95 × 20% ≈ 19%
  database reads jump from 50,000/s (5% misses) to ~810,000/s  → the database falls over.

Removing a failed server (4 → 3) is just as bad: a key stays only if h mod 4 = h mod 3,
true for 3 of every 12 values → 75% of keys move, at exactly the moment you're already degraded.

For a database (rather than a cache), "moving" means physically copying 80% of the data across the network while serving traffic. We need a mapping where adding or removing one server moves only the keys that must move — ideally just 1/N of them. That's what consistent hashing provides (Karger et al., 1997, originally designed for distributed web caching — the work that led to Akamai's CDN).

2. The hash ring

Take a hash function that outputs, say, a 32-bit number: 0 to 2³² − 1 (≈ 4.3 billion). Now imagine bending that number line into a circle, so that after 2³² − 1 comes 0 again. This is the hash ring (Cassandra's Murmur3 ring uses the 64-bit range −2⁶³ … 2⁶³ − 1).

1. Place the nodes. Hash each server's identifier (e.g. hash("cache-a") or its IP) to get its position on the ring. Each node's position is called its token.
2. Place the keys. Hash each key (hash("user:42:timeline")) with the same function to get its position.
3. Assign ownership. Each key belongs to the first node at or after its position, moving clockwise — the key's successor. Equivalently, each node owns the arc of the ring from the previous node's position (exclusive) up to its own position (inclusive).

                       0 / 2^32
                  .-----  ●A (pos 20) -----.
             k4 •'                          `• k1  ──► owned by B
           ●D  /                              \
        (290)  |      ring positions          |
   k3 • ──► D  |      increase clockwise      •  k5 ──► B
               \                              /
                `.                          .● B (pos 110)
                  `-----  ●C (200) -----• k2 ──► C
 Rule: walk clockwise from the key's position; the first node you meet owns it.
 A owns (290, 20],  B owns (20, 110],  C owns (110, 200],  D owns (200, 290]

Note that the hash of a node and the hash of a key live in the same space, and nothing about a key's position depends on how many nodes exist. That independence is the whole trick.

3. Lookup: clockwise successor via binary search

Implementation is simple: keep the node positions in a sorted array. To find a key's owner, hash the key and binary-search for the first position greater than (or equal to) the key's hash. If you run off the end of the array, wrap around to index 0 (that's the "ring").

positions = [20, 110, 200, 290]          # sorted node tokens
owner     = {20: "A", 110: "B", 200: "C", 290: "D"}

lookup(hash = 75):   first position > 75   → 110 → "B"
lookup(hash = 290):  first position >= 290 → 290 → "D"   (bisect_left treats equal as owned)
lookup(hash = 300):  nothing > 300         → wrap to index 0 → 20 → "A"

Cost: with M total positions on the ring, a lookup is O(log M) — for 100 servers × 200 virtual nodes = 20,000 positions, that's about 15 comparisons, i.e. well under a microsecond. Adding a node is O(M) with a sorted array (insertion) or O(log M) with a balanced tree — irrelevant in practice because membership changes are rare. Every client computes the same answer independently, as long as everyone has the same membership list (distributed via config service, gossip, or a ZooKeeper/etcd watch).

4. Adding and removing nodes: only ~K/N keys move

Suppose a new node E hashes to a position between B and C. Which keys change owner?

• Keys in the arc (B, E] previously walked clockwise past E's (empty) spot to C. Now they hit E first → they move from C to E.
• Every other key still meets the same first node → unchanged.

So adding a node only steals keys from one neighbour, and removing a node only hands its keys to one neighbour (its successor). With K keys and N nodes evenly spread, a change moves about K/N keys — the theoretical minimum, since the new node must end up with its fair share.

4.1 Worked example: 1,000,000 keys

The Python demo in Section 7 measures this on 100,000 real keys: adding a 5th node to 4 moved 19.6% of keys (ideal 20%), and every moved key went to the new node; mod-N would have moved 80%.

5. Virtual nodes: balance and heterogeneous capacity

5.1 Why one point per node is unbalanced

N random points split a circle into arcs whose lengths vary a lot: the largest arc is typically several times the average (on the order of log N times). Measured on 200,000 keys and 10 nodes using the implementation below:

With one position each, one server got 3.6× its fair share while another got almost nothing. The spread shrinks roughly like 1/√V where V is the number of positions per node.

5.2 The fix: many virtual nodes per physical node

Give each physical node V virtual nodes (vnodes): hash "cache-a#0", "cache-a#1", …, "cache-a#99" to get 100 positions, all owned by cache-a. Lookup is unchanged — find the successor position, then map it to its physical node.

Benefits of virtual nodes:

• Even load. Many small arcs average out (see the table: 100 vnodes → ~8% spread).
• Graceful failure. When a node dies, its many arcs are absorbed by many different successors, so each survivor takes a small, roughly equal slice instead of one neighbour taking it all.
• Faster recovery/rebuild. A new or replacement node streams data from many peers in parallel rather than from one.
• Heterogeneous capacity (weights). A server with twice the RAM gets twice as many vnodes and therefore ~twice the keys — add_node("cache-big", weight=2) in the implementation below.

Costs: a bigger ring (N × V positions — still tiny: 1,000 servers × 256 = 256,000 sorted integers), and in databases, more token ranges to repair and stream. Cassandra used num_tokens: 256 by default for years; Cassandra 4.0 lowered the default to 16 with a smarter token-allocation algorithm that places tokens to balance load deliberately rather than randomly.

6. Replication along the ring

To store each key on N replicas (see Replication), Dynamo-style systems use the ring itself: the key's primary is its successor node, and the other replicas are the next distinct physical nodes clockwise. The ordered list is called the key's preference list.

1. Hash the key; find the first vnode clockwise → its physical node is replica #1.
2. Keep walking clockwise. For each vnode, if its physical node is already in the list, skip it (otherwise two "replicas" could be the same machine — no redundancy).
3. Stop when you have N distinct physical nodes. Optionally also skip nodes in the same rack or availability zone until each replica is in a different failure domain — Cassandra's NetworkTopologyStrategy does this per data center, placing replicas on distinct racks.

Nice properties: every node can compute any key's replica set locally; when a node joins or leaves, preference lists change only for keys near it on the ring; and during a temporary failure, the next node in the walk can accept writes on its behalf (the sloppy quorum and hinted handoff covered in Replication).

7. A complete Python implementation

The whole algorithm fits in ~60 lines: a sorted list of vnode positions, a dict from position to physical node, and bisect for the binary search. It supports weights, removal and replica sets.

import bisect
import hashlib
from collections import Counter


def _hash(value: str) -> int:
    """Map a string to a point on the ring: 0 .. 2**32 - 1."""
    digest = hashlib.md5(value.encode("utf-8")).digest()
    return int.from_bytes(digest[:4], "big")


class ConsistentHashRing:
    def __init__(self, vnodes_per_weight: int = 100):
        self.vnodes_per_weight = vnodes_per_weight
        self._points = []          # sorted list of vnode positions
        self._owner = {}           # position -> physical node name
        self._nodes = {}           # physical node -> list of its positions

    def add_node(self, node: str, weight: int = 1) -> None:
        positions = []
        for i in range(self.vnodes_per_weight * weight):
            pos = _hash(f"{node}#vn{i}")
            if pos in self._owner:          # extremely rare collision: skip it
                continue
            self._owner[pos] = node
            bisect.insort(self._points, pos)
            positions.append(pos)
        self._nodes[node] = positions

    def remove_node(self, node: str) -> None:
        for pos in self._nodes.pop(node):
            del self._owner[pos]
            idx = bisect.bisect_left(self._points, pos)
            self._points.pop(idx)

    def get_node(self, key: str) -> str:
        if not self._points:
            raise RuntimeError("ring is empty")
        h = _hash(key)
        idx = bisect.bisect_left(self._points, h)    # first vnode at or clockwise of h
        if idx == len(self._points):                 # past the last point: wrap to 0
            idx = 0
        return self._owner[self._points[idx]]

    def get_nodes(self, key: str, n: int) -> list:
        """Replica set: walk clockwise, collecting n DISTINCT physical nodes."""
        if n > len(self._nodes):
            raise ValueError("not enough physical nodes")
        result = []
        idx = bisect.bisect_left(self._points, _hash(key))
        while len(result) < n:
            if idx == len(self._points):
                idx = 0
            node = self._owner[self._points[idx]]
            if node not in result:                   # skip other vnodes of chosen nodes
                result.append(node)
            idx += 1
        return result


if __name__ == "__main__":
    ring = ConsistentHashRing(vnodes_per_weight=100)
    for name in ["cache-a", "cache-b", "cache-c", "cache-d"]:
        ring.add_node(name)

    keys = [f"user:{i}:timeline" for i in range(100_000)]
    before = {k: ring.get_node(k) for k in keys}
    print("Load with 4 nodes:", sorted(Counter(before.values()).items()))

    ring.add_node("cache-e")
    after = {k: ring.get_node(k) for k in keys}
    moved = sum(1 for k in keys if before[k] != after[k])
    print("Load with 5 nodes:", sorted(Counter(after.values()).items()))
    print(f"Keys moved: {moved} ({moved / len(keys):.1%}); ideal = 1/5 = 20.0%")
    print("All moved keys went to cache-e:",
          all(after[k] == "cache-e" for k in keys if before[k] != after[k]))

    naive_moved = sum(1 for i in range(100_000) if i % 4 != i % 5)
    print(f"Naive mod-N would move: {naive_moved} ({naive_moved / 100_000:.1%})")

    print("Replicas for user:42:timeline ->", ring.get_nodes("user:42:timeline", 3))

    ring.remove_node("cache-b")
    gone = {k: ring.get_node(k) for k in keys}
    moved_b = sum(1 for k in keys if after[k] != gone[k])
    print(f"Removing cache-b moved {moved_b} keys, all previously on cache-b:",
          all(after[k] == "cache-b" for k in keys if after[k] != gone[k]))

Actual output (Python 3, deterministic because MD5 is deterministic):

Load with 4 nodes: [('cache-a', 26028), ('cache-b', 22725), ('cache-c', 23324), ('cache-d', 27923)]
Load with 5 nodes: [('cache-a', 20640), ('cache-b', 19816), ('cache-c', 18519), ('cache-d', 21391), ('cache-e', 19634)]
Keys moved: 19634 (19.6%); ideal = 1/5 = 20.0%
All moved keys went to cache-e: True
Naive mod-N would move: 80000 (80.0%)
Replicas for user:42:timeline -> ['cache-b', 'cache-d', 'cache-e']
Removing cache-b moved 19816 keys, all previously on cache-b: True

What to notice:

• Balance: with 100 vnodes per node, each of 4 nodes holds 23–28% (ideal 25%); after adding cache-e each holds 18.5–21.4% (ideal 20%).
• Minimal movement: 19.6% of keys moved — essentially exactly the new node's fair share — and only onto the new node. Mod-N would have moved 80%.
• Removal: deleting cache-b moved exactly the 19,816 keys cache-b owned, and nothing else; thanks to vnodes, they were spread across all four survivors.
• Replicas: get_nodes returned three distinct physical nodes.

8. Where consistent hashing is used

Contrast: Redis Cluster uses 16,384 fixed hash slots (CRC16(key) mod 16384) assigned to nodes — the "fixed number of logical partitions" approach from Sharding, which achieves the same goal (move slots, not keys) with an explicit slot map instead of a ring.

9. Alternatives and refinements

9.1 Rendezvous hashing (Highest Random Weight, HRW)

For each key, compute a score for every node — score = hash(node_id + key) — and pick the node with the highest score. For N replicas, take the top-N scores.

def hrw_owner(key: str, nodes: list) -> str:
    return max(nodes, key=lambda node: _hash(f"{node}:{key}"))

• ✅ Remove a node → only keys whose top choice was that node move (each to its own second choice, so load spreads evenly across survivors). Add a node → it wins ~1/N of keys. Same minimal-disruption property as the ring.
• ✅ Naturally balanced without virtual nodes; no ring to store; trivially gives an ordered replica list; supports weights (e.g. score = −weight / ln(h) with h normalised to (0,1)).
• ❌ Lookup is O(N) hashes per key — fine for tens or hundreds of nodes, costly for thousands (can be made hierarchical).
• Used by: Apache Ignite, GitHub's load balancer (GLB) director, many CDN/cache routing schemes, Microsoft's CARP proxy-array protocol.

9.2 Jump consistent hash

Google's jump consistent hash (Lamping & Veach, 2014) maps a 64-bit key to a bucket number in [0, num_buckets) with a tiny loop, no memory, O(ln N) time and near-perfect balance:

def jump_hash(key: int, num_buckets: int) -> int:
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF   # 64-bit LCG step
        j = int((b + 1) * (float(1 << 31) / float((key >> 33) + 1)))
    return b

• ✅ Going from n to n+1 buckets moves exactly ~1/(n+1) of keys, all to the new bucket (measured: 10 → 11 buckets moved 8.98% of 100,000 keys; ideal 9.09%).
• ✅ Better balance than a ring with vnodes, zero lookup state.
• ❌ Buckets must be numbered 0 … n−1, and you can only add or remove the last bucket. You can't remove an arbitrary failed server — so it fits sharded storage with numbered, replicated shards (each "bucket" is a replica group that never disappears), not a pool of individually failing cache nodes.

9.3 Consistent hashing with bounded loads

Even with vnodes, a ring balances keys, not load: a few very hot keys can overload their owner. Consistent hashing with bounded loads (Mirrokni, Thorup & Zadimoghaddam, Google, 2016) sets a capacity per node of c = ⌈(1 + ε) × average load⌉. A request goes to its usual successor unless that node is at capacity, in which case it continues clockwise to the next node with room.

 ε = 0.25, 4 servers, 100 active connections  →  average 25, cap = ⌈1.25 × 25⌉ = 32 each

 key K hashes near server B:   B has 32/32 (full) → skip
                               next clockwise: C has 20/32 → assign to C ✔
 Guarantee: no server exceeds 1.25× the average, while most keys still land on their
 "natural" server (good cache affinity) and changes still move few keys.

Vimeo contributed this to HAProxy (hash-balance-factor) to keep video-cache affinity without overloading any single cache server. It's ideal for load balancing with affinity, where load matters more than strict key placement.

9.4 Comparison

10. How Instagram uses consistent hashing

10.1 Example: scaling the feed cache before a big event

1. Assume 40 Redis timeline servers, 100 vnodes each, and ~400 M cached timelines (~10 M per server). Traffic is forecast to rise 25%, so ops adds 10 servers.
2. The new servers' vnodes are inserted into the ring; the new membership list is published via the config service, and every Feed Service instance rebuilds its ring (a few ms).
3. Each new server takes ~1/50 of the ring → in total 10/50 = 20% of timelines (≈80 M keys) now map to new servers and miss once. With mod-N, 40/50 = 80% (≈320 M) would have missed.
4. Misses are refilled lazily from Cassandra (or by pre-warming: copying the affected ranges before flipping the membership). Because those 20% are spread evenly over time and users, the database sees a manageable bump instead of a stampede. See Caching for stampede protection.

11. Trade-offs & common pitfalls

Common pitfalls

• Using one point per node — 3–4× load imbalance with a handful of nodes. Use 100+ vnodes (or a token-allocation algorithm).
• Inconsistent membership views — during a rolling config push, half the clients use the old ring and half the new, so the same key is written to two servers and reads flip between them. Version the membership and propagate it quickly; tolerate short windows with TTLs.
• Language-specific or randomised hashes (Python hash(), Java String.hashCode() with poor mixing) → different clients disagree or keys cluster.
• Flapping nodes — a node bouncing in and out of the ring moves its keys back and forth. Add hysteresis: require sustained health before re-adding.
• Replicas on the same machine/rack — forgetting to skip vnodes of already-chosen physical nodes (or racks) when walking the ring.
• Assuming it solves hot keys — a celebrity's timeline key still lives on one server. Combine with replication of hot keys, local caching, or bounded-load hashing. See Sharding.
• Forgetting data movement in stateful stores — for a cache, a moved key is just a miss; for a database, the new owner must stream the data before it can serve it.

12. Real-world technologies

13. Interview corner

14. Check your understanding

Related lessons

• Sharding — logical shards, hash vs range partitioning and hot keys
• Replication — preference lists, sloppy quorums and hinted handoff on the ring
• Caching — the Redis/Memcached tiers that consistent hashing distributes
• Databases — Cassandra's partition keys and token ring
• Load Balancing — hash-based affinity, ring hash and Maglev
• CDN — consistent hashing inside a PoP to pick the cache server for a URL