Day 17: Implement Consistent Hashing for Elastic Cluster Membership — and Minimize Data Movement

In our previous lesson, we established a single-node durable storage engine capable of surviving sudden process crashes. Today, we scale horizontally. We move from a solitary machine to an elastic cluster where nodes can join and leave dynamically. Our goal is to distribute keys across these nodes without triggering a catastrophic data-migration storm when the cluster membership changes.

The Production Stakes: The Modulo Hashing Disaster

In the early days of horizontal scaling, the standard approach to distributing keys across $N$ servers was simple modulo hashing:

$$text{server} = text{hash}(key) pmod N$$

This works perfectly when the cluster is static. However, in cloud environments, infrastructure is dynamic. Nodes fail, autoscalers provision new instances, and SREs perform rolling upgrades.

Consider a cluster of 9 nodes scaling up to 10. Under modulo hashing, when $N$ changes from 9 to 10, the destination node for almost every key changes:

$$text{hash}(key) pmod 9 neq text{hash}(key) pmod{10}$$

Mathematically, approximately $N / (N + 1)$ of your keys—90% of your data—must immediately move to a different server.

When Vimeo scaled their caching layer using simple modulo hashing, adding a single cache server invalidated nearly their entire cache. This triggered a thundering herd of cache misses that overwhelmed their backend databases, degrading the entire platform. Consistent hashing solves this. By mapping both keys and servers to a circular identifier space, adding or removing a node only requires moving $1 / (N + 1)$ of the keys (10% in our example).

Component Architecture and System Fit

In our DurableKV architecture, the consistent hashing ring acts as the Request Router. It sits at the entry point of our cluster coordination layer:

When a write or read request arrives, the router hashes the key, locates its position on the ring, and forwards the payload to the corresponding node.

The Ring Topology and Virtual Nodes (VNodes)

To visualize consistent hashing, imagine a circular racetrack ranging from $0$ to $2^{32} - 1$ (the range of a 32-bit unsigned integer).

If we only map physical nodes directly to the ring, we face two major production issues:

1. Hotspots (Unbalanced Load): Random hashing of a few nodes rarely distributes them evenly on the ring. One node might end up responsible for 70% of the key space.

2. Heterogeneous Hardware: A powerful bare-metal server and a small VM would receive the same load.

To solve this, we use Virtual Nodes (VNodes). Instead of mapping physical node Node-A once, we map it dozens or hundreds of times as Node-A-v1, Node-A-v2, etc. This interleaves the ownership of the key space across the ring, smoothing out the distribution. If Node-A is twice as powerful as Node-B, we simply assign it twice as many VNodes.