Implementation Deep Dive: Data Structures and Complexity

The Ring as a Sorted Data Structure

The hash ring is not stored as a literal circle in memory. It is stored as a sorted map from ring positions (integers) to node names. The two most common implementations are:

Python — bisect module on a sorted list:

# Ring state
ring = {10: "NodeA", 30: "NodeD", 50: "NodeB", 90: "NodeC"}
sorted_keys = [10, 30, 50, 90]

# Clockwise lookup for key at position 35
import bisect
idx = bisect.bisect(sorted_keys, 35)  # Returns 2 (first position > 35)
owner = ring[sorted_keys[idx]]         # sorted_keys[2] = 50 → "NodeB"

Java — TreeMap (Red-Black Tree):

TreeMap<Integer, String> ring = new TreeMap<>();
ring.put(10, "NodeA");
ring.put(50, "NodeB");
ring.put(90, "NodeC");

// Clockwise lookup: ceilingEntry finds the smallest key >= position
Map.Entry<Integer, String> entry = ring.ceilingEntry(35);
if (entry == null) entry = ring.firstEntry(); // wrap around
String owner = entry.getValue(); // "NodeB"

Time and Space Complexity

Where V = VNodes per server, N = number of physical servers.

With V=256 and N=100 servers, the ring holds 25,600 entries — trivially small in memory (a few hundred KB). The O(log VN) lookup is approximately log₂(25,600) ≈ 15 comparisons per key lookup, which is negligible compared to network latency.

The Wrap-Around Edge Case

The most common implementation bug is forgetting the wrap-around. When a key's position is greater than all VNode positions on the ring, the clockwise lookup must wrap back to the first (smallest) position:

idx = bisect.bisect(sorted_keys, position)
if idx == len(sorted_keys):
    idx = 0  # Wrap: the "next clockwise" node is the first node on the ring

Without this, keys that hash to positions beyond the last VNode will raise an IndexError or return None — a subtle bug that only manifests for a specific subset of keys.