CODING CHALLENGE · N°33

Consistent Hashing Ring

Medium SystemsDistributed SystemsHashing

How distributed caches and databases decide which node owns a key — while keeping churn tiny when nodes join or leave. Build a hash ring with virtual nodes and route keys to the next node clockwise. A provided hash keeps Python and TypeScript in lock-step. Solve it in your browser, with hidden tests.

The problem

Place each of the nodes on a hash ring at vnodes points (virtual nodes), using the provided hash32. To route a key, hash it and walk clockwise to the first ring point at or after it (wrapping past the end back to the smallest). Implement assign(keys, nodes, vnodes): return, for each key, the name of the node that owns it. The point for node n’s replica r is hash32(n + "#" + r).

EXAMPLE 1

Input assign(['k1','k2','k3'], ['A','B','C'], 3)

Output ['C', 'A', 'C']

each key maps to the next node clockwise on the ring

CONSTRAINTS

Use the provided hash32 for both node points and keys (do not invent your own — the tests depend on it).
Each node contributes vnodes ring points; more virtual nodes → smoother load balance.
A key hashing past the largest ring point wraps around to the smallest point.
The routing must be deterministic: the same key always maps to the same node for a fixed ring.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Build a list of (point, node) for every node × replica, sort it by point, and for each key find the first point ≥ hash32(key) (wrapping to index 0 if none). Return the owning node per key.

HINTS — 4 IDEAS

Ring points: for each node n and replica r in 0…vnodes-1, add (hash32(n + "#" + r), n). Sort by the point.
To route a key, compute kh = hash32(key) and scan the sorted ring for the first point ≥ kh.
If no point is ≥ kh (the key is past the last point), wrap around to the first point — the ring is circular.
Virtual nodes are the trick that makes load even and keeps re-mapping small when a node is added or removed.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Hash each node to one or more points on a ring (a sorted structure of hash values → node), giving each physical node many virtual nodes so the arcs are even. To place a key, hash it and walk clockwise to the first node point at or after it (scan the sorted ring, wrapping around at the end). Adding or removing a node only re-owns the keys in its arc.

Complexity

The reference solution here does a linear scan: O(R) over R ring points, plenty fast at this ring's size. A production deployment with thousands of virtual nodes binary-searches the sorted ring instead (Python's bisect, or an equivalent), getting lookup down to O(log R). Adding or removing a node is O(V) — O(V log R) with the binary-search version — for its V virtual nodes.

Common mistakes

Too few virtual nodes — the ring is lumpy and some nodes run hot.
Falling back to hash(key) % N, which remaps almost every key when N changes.
Forgetting wrap-around: a key past the last node point belongs to the first node.

Where this shows up

Consistent hashing is how distributed caches and databases (Dynamo, Cassandra, Riak, Memcached clients) spread keys so a membership change moves only ~K/N keys instead of the whole keyspace — turning a node add/remove from a cache-wide stampede into a small, local reshuffle.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Distributed Systems