HLD Learn/Unique IDs & Distributing Data

Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Consistent Hashing

9 min read

You'll learn to

-Explain what a hash function is and how hash(key) % N picks a server
-Show, with numbers, why adding or removing one server breaks that approach
-Describe the hash ring and how a key finds its server by walking clockwise
-Explain virtual nodes and the uneven-load problem they solve

Last chapter was about giving every record a unique name. This one asks a different question: once your data is spread across several machines, how does a request find the right machine? Say you run three cache servers and a request arrives for the profile of user 8421. Which server is holding it? Whatever answer you choose has to be fast, every app server has to reach the same answer on its own, and it should not depend on one central address book that could itself become a bottleneck or go down.

Two Small Building Blocks First

A hash function turns any input (a username, a URL, a whole file) into a number. Two properties matter for us: the same input always gives the same number, and different inputs get numbers that look random and spread out. Think of it as a fingerprint machine for data. In this chapter we will use tiny made-up hash values like 7 or 12 so the arithmetic is easy to follow. Real hash functions produce huge numbers, for example anywhere from 0 to about 4.3 billion.

The % symbol is "modulo": the remainder after dividing. 7 % 3 = 1, because 3 goes into 7 twice with 1 left over. It works like a clock: 15:00 on a 24-hour clock is 3 o'clock on a 12-hour one, because 15 % 12 = 3. The useful part is that x % 3 always lands on 0, 1 or 2, so it can turn any big number into the number of one of three servers.

The Obvious Approach: hash(key) % N

Number your servers 0 to N-1, where N is how many servers you have. To find the home of a key, hash it and take the remainder. If hash("user:8421") comes out as 7 and you have 3 servers, then 7 % 3 = 1, so user 8421 lives on server 1. Every app server can work this out on its own, in microseconds, with no lookup table. That simplicity is why people reach for it first, and for a cluster that never changes size it works perfectly.

The Moment It Breaks: N Changes

Clusters do change size. Traffic grows and you add a server, or a machine crashes and you are down one. Take twelve keys with made-up hash values 1 through 12, and go from 3 servers to 4:

-Key 3: 3 % 3 = 0, so it lived on server 0. Now 3 % 4 = 3, so it has to move to server 3.
-Key 5: 5 % 3 = 2 before, 5 % 4 = 1 after. It moves too.
-Key 12: 12 % 3 = 0 before, 12 % 4 = 0 after. This one stays. Only keys 1, 2 and 12 stay put.

Nine of the twelve keys changed servers, just because one server was added. The cause is that N is baked into the formula, so changing N changes almost every answer. And it gets worse as the cluster grows, because the share of keys that move is N out of N+1:

How Much Moves When You Add One Server (hash % N)

75%

of keys move going from 3 servers to 4

91%

of keys move going from 10 servers to 11

99%

of keys move going from 100 servers to 101

Why this hurts in practice: if these servers are caches, every key that moved is now a cache miss on its new server, so thousands of requests suddenly fall through to your database all at once, usually when you are already under pressure. If these servers are databases, moving that much data means copying huge amounts across the network while users are still reading and writing.

The Key Idea: Stop Making the Answer Depend on N

The trouble is that where a key lives depends on how many servers exist. Consistent hashing breaks that link. A key gets a fixed position that depends only on the key itself. The servers are then placed in that same space, and a key belongs to the nearest server in one agreed direction. Add or remove a server and the keys keep their positions, so only the keys near that server are affected.

An Analogy: Pizza Shops on a Ring Road

Picture a circular ring road around a city. Houses are scattered along it, and a few pizza shops sit at various spots on it. The rule everyone follows: from your front door, walk clockwise along the road and order from the first pizza shop you reach. Nobody needs a directory or a coordinator. Your own address and the shops' positions are enough to settle it.

Now a new shop opens between two existing ones. The only houses whose answer changes are the ones between the previous shop and the new shop, because they now reach the new shop first. Every other house still reaches the same shop as before. If a shop closes, only its own customers have to walk on to the next shop clockwise. Everyone else is unaffected.

Mapping the Analogy to the Real Thing

-The ring road is the hash ring: every possible hash value laid out in a circle, from 0 up to some maximum (often 2^32, about 4.3 billion), with the end joined back to the start.
-A house is a key. Its address on the road is hash(key), for example hash("user:8421").
-A pizza shop is a server. Its address is hash(server name), for example hash("cache-1"). Using the same hash function for both is what puts them on the same ring.
-Walking clockwise to the first shop is the lookup rule: find the first server at or after the key's position, wrapping past the top back to zero if needed.
-The shop a house orders from is the server that stores that key.

App Server

Ring Lookup

Node A

Node B

Node C

The ring is not a machine you deploy. It is a lookup your app (or a router in front of the cluster) performs: hash the key, find the next server clockwise, send the request there.

App ServerRing Lookup- hash the keyRing LookupNode A- next server clockwise

Watch It Happen

The simulation below puts 12 keys (the small dots) and servers (the labeled circles) on a ring. Each dot takes the color of the server that owns it. Press Play, or step through with the arrows. Step 0 starts with three servers, A, B and C. In step 1, server D joins and only the dots in D's new slice change color: 2 of the 12. In step 2, server B is removed and only B's 4 dots change color, falling through to the next server clockwise. Compare that with the 9 of 12 keys that moved under hash % N.

Adding and Removing Servers on a Hash Ring

12 keys, hashed once and fixed. Watch how few of them actually move when the server set changes.

server A server B server C

Three servers on the ring, evenly spaced. Each owns the keys in the arc clockwise from the previous server up to itself.

Keys that moved this step: 0 / 12

step 0 / 2

The Catch: Uneven Slices, and Virtual Nodes

There is one catch. Servers get their positions by hashing their names, and random positions are lumpy. Three shops might land close together on one side of the ring road, leaving one shop responsible for most of the houses. In the code example below, with one position per server, one server ends up with about 60% of 10,000 keys and another with only about 10%.

The fix is virtual nodes. Instead of giving each server one spot on the ring, give it many, such as 100 or 200 spots, each hashed from a name like "cache-1#0", "cache-1#1" and so on. In the analogy, every pizza chain opens many small kiosks scattered all around the ring road. Each kiosk still serves the houses just before it, but every chain now holds lots of small slices instead of one big one, and the slices average out. In the same example, 100 spots per server brings the shares to roughly 34%, 35% and 32%.

-Even load: many small slices per server average out to a fair share each.
-Gentler failures: when a server dies, its many small slices are picked up by many different neighbors, instead of all landing on one unlucky server.
-Bigger machines can take more: give a server with twice the capacity twice as many spots.

Optional: check the numbers yourself. Run it, then change the 3 and 4 to see how the totals shift.

import hashlib
from bisect import bisect_right

def position(name):
    # Turn any string into a point on the ring (0 to 2**32 - 1)
    digest = hashlib.md5(name.encode()).hexdigest()
    return int(digest, 16) % (2 ** 32)

def build_ring(servers, spots_per_server):
    # Every server gets several spots ("virtual nodes") on the ring
    ring = []
    for server in servers:
        for i in range(spots_per_server):
            ring.append((position(f"{server}#{i}"), server))
    ring.sort()
    points = [p for p, _ in ring]
    names = [s for _, s in ring]
    return points, names

def owner(ring, key):
    points, names = ring
    # Find the first spot clockwise from the key.
    # The "%" wraps past the top of the ring back to the start.
    index = bisect_right(points, position(key)) % len(points)
    return names[index]

keys = [f"user:{i}" for i in range(10000)]

# 1) Uneven slices: one spot per server vs 100 spots per server
for spots in (1, 100):
    ring = build_ring(["A", "B", "C"], spots)
    counts = {"A": 0, "B": 0, "C": 0}
    for key in keys:
        counts[owner(ring, key)] += 1
    print(f"{spots:>3} spot(s) per server -> keys per server: {counts}")

# 2) Add a 4th server: hash % N versus the ring
moved_modulo = 0
for key in keys:
    if position(key) % 3 != position(key) % 4:
        moved_modulo += 1

before = build_ring(["A", "B", "C"], 100)
after = build_ring(["A", "B", "C", "D"], 100)
moved_ring = 0
for key in keys:
    if owner(before, key) != owner(after, key):
        moved_ring += 1

print(f"hash % N moved {moved_modulo} of {len(keys)} keys")
print(f"the ring moved {moved_ring} of {len(keys)} keys")

import hashlib
from bisect import bisect_right

def position(name):
    # Turn any string into a point on the ring (0 to 2**32 - 1)
    digest = hashlib.md5(name.encode()).hexdigest()
    return int(digest, 16) % (2 ** 32)

def build_ring(servers, spots_per_server):
    # Every server gets several spots ("virtual nodes") on the ring
    ring = []
    for server in servers:
        for i in range(spots_per_server):
            ring.append((position(f"{server}#{i}"), server))
    ring.sort()
    points = [p for p, _ in ring]
    names = [s for _, s in ring]
    return points, names

def owner(ring, key):
    points, names = ring
    # Find the first spot clockwise from the key.
    # The "%" wraps past the top of the ring back to the start.
    index = bisect_right(points, position(key)) % len(points)
    return names[index]

keys = [f"user:{i}" for i in range(10000)]

# 1) Uneven slices: one spot per server vs 100 spots per server
for spots in (1, 100):
    ring = build_ring(["A", "B", "C"], spots)
    counts = {"A": 0, "B": 0, "C": 0}
    for key in keys:
        counts[owner(ring, key)] += 1
    print(f"{spots:>3} spot(s) per server -> keys per server: {counts}")

# 2) Add a 4th server: hash % N versus the ring
moved_modulo = 0
for key in keys:
    if position(key) % 3 != position(key) % 4:
        moved_modulo += 1

before = build_ring(["A", "B", "C"], 100)
after = build_ring(["A", "B", "C", "D"], 100)
moved_ring = 0
for key in keys:
    if owner(before, key) != owner(after, key):
        moved_ring += 1

print(f"hash % N moved {moved_modulo} of {len(keys)} keys")
print(f"the ring moved {moved_ring} of {len(keys)} keys")

Where You Will See This in Real Systems

-Cache clusters: Memcached client libraries use consistent hashing so that adding a cache server does not wipe out most of the cache.
-Distributed databases: Cassandra and other Dynamo-style databases use a ring to decide which node stores which row.
-Content delivery networks and load balancers: the same URL or user keeps being routed to the same server, so that server's local cache stays warm.

Remember it in one line: with hash % N, the number of servers is part of every key's address, so changing it moves almost everything. On a ring, a key's address depends only on the key, so adding or removing a server moves only about 1 in N keys.

Go Deeper

From the Wiki🔵 Consistent Hashing

A technique that minimizes data redistribution when nodes are added to or removed from a distributed cache or storage cluster.

Imagine a clock face (0-12). Your 3 servers sit at positions 12, 4, and 8. Each piece of data is hashed to a "time" on the clock, and is served by the next server clockwise. When you add a 4th server at position 2, only data between 12 and 2 moves - the rest stays put. With normal hashing, ALL data would move.

In a naive distributed cache with N nodes, you route a key by doing hash(key) % N. This works perfectly - until you add a node. Now you have N+1 nodes, and hash(key) % (N+1) gives entirely different results for almost every key. Every cached item is now on the wrong node. You've just invalidated ~100% of your cache in one go.

Consistent Hashing solves this by placing both servers and keys on a conceptual ring (a circular number line, e.g., 0 to 2^32). Each server owns an arc of the ring. A key is assigned to the first server clockwise from its position on the ring.

When you add a node, only keys in the arc that the new node takes over need to be moved. On average, only 1/N of the data moves (where N is the number of existing nodes).

When you remove a node, only the keys on that node's arc need to be redistributed to the next node clockwise.

Virtual nodes (vnodes): A real system assigns each physical server many positions on the ring (e.g., 150 virtual nodes per server). This ensures even distribution even when servers have different capacities or arrive/depart at different times. Cassandra uses 256 vnodes per server by default.

-Only O(K/N) keys need remapping when a node joins or leaves (K = total keys, N = nodes).
-Virtual nodes solve uneven distribution and make heterogeneous clusters work correctly.
-Used by: Cassandra, DynamoDB, Memcached (via client-side hashing), Amazon S3, Chord.
-The load balancing is only probabilistically even; vnodes improve this significantly.

Read the full Wiki entry

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Generating Unique IDs at Scale Database Sharding & Partitioning

Discussion2

Join the Discussion

🏗️Mathias Grudzinski(edited)13d ago

This chapter isnt written very beginner friendly

🏗️ShivohamScaleDojo Team5d ago

@Mathias Grudzinski Thanks for the feedback, Mathias! We’ve updated the chapter with more in-depth content to make the concepts clearer and easier to understand. We appreciate you taking the time to share your thoughts, as it helps us continuously improve ScaleDojo. We’d love for you to check out the updated content and share your thoughts!