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

Explore the topic

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

Distributed Systems