Day 16: Hash Keys to Distribute Data Across Partitions — and Understand Data Locality

Yesterday, we finalized our single-node storage engine, ensuring that writes are durably committed to an append-only log and indexed in memory. However, a single machine has hard physical limits: disk bandwidth, network interfaces, and memory capacity eventually saturate. Today, we transition from a single-node engine to a multi-node partitioned system. We will design and implement a consistent hash ring with virtual nodes (VNodes) and support for hash tags to balance data distribution while preserving data locality.

The Production Stakes: The Modulo Hashing Outage

When engineers first scale a key-value store to multiple nodes, the intuitive approach is modulo hashing:

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

where $N$ is the number of nodes in your cluster. This works perfectly in a static world. But in cloud infrastructure, $N$ is never static. Nodes fail, disks die, and clusters must scale out to handle peak traffic.

Consider a cluster of 9 nodes scaling up to 10 nodes to handle a Black Friday surge. Using modulo hashing, let us look at what happens to the key routing:

• With $N = 9$, a key hashing to $100$ routes to node $100 pmod 9 = 1$.

• With $N = 10$, that same key now routes to node $100 pmod{10} = 0$.

Mathematically, when you change the node count from $N$ to $N+1$, approximately $frac{N}{N+1}$ of all keys (90% in this case) suddenly map to a different node.

In a production system, this triggers a catastrophic data migration event. If your storage engine automatically moves data, your network interfaces will instantly saturate, disk I/O will spike, and read latencies will skyrocket. If your system relies on the storage layer as a cache, your cache hit rate will drop to near zero, sending a thundering herd of requests to your backend database and causing a cascading outage. This exact failure mode has brought down major web platforms during routine scaling operations.

To prevent this, we use Consistent Hashing.

Architectural Blueprint: The Consistent Hash Ring

Consistent hashing maps both servers (nodes) and keys to a continuous 32-bit numeric space represented as a circle or "ring" from $0$ to $2^{32} - 1$.

Figure 1: A consistent hash ring with physical nodes mapped to multiple positions (VNodes). The key "{tenant1}u1" hashes to 0x50000000 and travels clockwise to find the next available node, which is Node A#0.