Design a Consistent Hashing Ring

Core implementation: node placement and key lookup

class ConsistentHashRing {
    TreeMap<Long, String> ring = new TreeMap<>(); // hash position -> node ID, sorted

    void addNode(String nodeId) {
        ring.put(hash(nodeId), nodeId);
    }

    String getNode(String key) {
        long keyHash = hash(key);
        Map.Entry<Long, String> entry = ring.ceilingEntry(keyHash); // first node clockwise from the key
        return (entry != null) ? entry.getValue() : ring.firstEntry().getValue(); // wrap around the ring
    }
}

A TreeMap (sorted by hash value) IS the ring, conceptually — nodes are placed at their hash positions around it, and a key is assigned to the FIRST node found going clockwise from the key's own hash position (ceilingEntry, wrapping around to the first node if the key's hash is past every node's position). This structure is what makes lookups fast (O(log n) via the tree) and makes the "assign key to nearest node clockwise" rule simple to implement directly.

Walking through adding/removing a node: minimal remapping

Before: Node A at position 10, Node B at position 50, Node C at position 90
  (ring wraps at, say, 100)
  Keys hashing to 11-50 -> Node B; 51-90 -> Node C; 91-10 (wrapping) -> Node A

Add Node D at position 30:
  Only keys that PREVIOUSLY mapped to positions 11-30 now remap (to D instead of B)
  Everything else (51-90 -> C, 91-10 -> A) is COMPLETELY UNAFFECTED

This is consistent hashing's entire value proposition, made concrete: adding or removing ONE node only affects the keys in the hash-range NEIGHBORING that node — a naive hash(key) % nodeCount scheme, by contrast, would remap NEARLY EVERY key the moment nodeCount changes at all, since the modulus itself changes. Consistent hashing's minimal-remapping property is precisely why it's the standard technique anywhere nodes are added/removed dynamically without wanting to trigger a massive, disruptive full-cluster rebalance.

Virtual nodes: solving the hotspot problem

void addNode(String nodeId, int virtualNodeCount) {
    for (int i = 0; i < virtualNodeCount; i++) {
        ring.put(hash(nodeId + "#" + i), nodeId); // multiple ring positions, ALL mapping back to the same physical node
    }
}

Without virtual nodes, removing ONE physical node dumps its ENTIRE key range onto exactly ONE neighbor (whichever node is next clockwise) — creating an immediate, severe hotspot on that single neighbor. Giving each PHYSICAL node MULTIPLE positions on the ring ("virtual nodes," each independently hashed) spreads that same removed node's key range across MANY different neighbors instead of dumping it all onto one — this is a genuinely essential refinement, not an optional optimization; a real consistent-hashing implementation without virtual nodes has a real, predictable hotspot problem baked in.

Direct connection to distributed caching and database sharding

This exact ring structure IS the node-placement mechanism underlying Distributed Cache's scaling story (assigning cache keys to cache nodes) — building it here from scratch is what makes that earlier design's "consistent hashing" reference concrete rather than a name-dropped buzzword. The SAME technique, applied to DATABASE SHARDS instead of cache nodes, is hash-based database sharding — Database Scaling Specifics' sharding discussion and this ring are the identical underlying mechanism, just applied to a different kind of node (a database shard rather than a cache server).

Follow-up questions this topic invites — and their answers

Q: How many virtual nodes per physical node is typically reasonable? A: Commonly somewhere in the range of 100-200 per physical node in real systems — more virtual nodes give smoother load distribution (closer to perfectly even) at the cost of more ring entries to maintain and search through; this is a genuine tunable trade-off between balance quality and ring-management overhead, not a fixed universal number.

Q: Does consistent hashing guarantee PERFECTLY even key distribution even with virtual nodes? A: No — it guarantees APPROXIMATELY even distribution with high probability, improving as virtual-node count increases, but true perfect evenness isn't mathematically guaranteed by the hashing approach itself; for workloads needing very tight load balancing, monitoring actual per-node load (Metrics & Monitoring) and adjusting virtual node counts per physical node capacity is still a real operational practice.

Q: What happens to REPLICATION in a consistent hashing ring — does each key live on only one node? A: In practice, a key is typically replicated to the NEXT N NODES clockwise from its primary position (not just the first one) for fault tolerance — this is a direct extension of the same ring-walking lookup logic, just continuing past the first match to collect N distinct physical nodes for replica placement.

Q: How does adding a node interact with in-flight requests during the rebalance? A: A production implementation needs to handle the transition window carefully — requests for keys that are REMAPPING need their data to actually be present at the new node before being served from there (a data-migration step, not just a ring-metadata update), which is a genuinely nontrivial operational concern beyond the pure hashing algorithm covered here.