Scaling Out with Consistent Hashing

Building a Key-Value Store Part 3:

Commit covered in this milestone: 0de645a

Series Context: This is Part 3 of our series on building a distributed key-value store from scratch in Java. If you are just joining us, in Part 1 we built a blazing fast, thread-safe in-memory store. In Part 2, we added durability to survive server crashes using a Write-Ahead Log (WAL) and SSTables. You can find the complete source code for the finished project here: https://github.com/rahulch07/kvstore.

In the previous article, we solved durability. Our data survives crashes and restarts.

Unfortunately, durability does not solve scalability.

Every request still flows through a single JVM process running on a single machine. That machine has fixed CPU cores, fixed RAM, fixed disk capacity, and fixed network bandwidth. Eventually, one of those resources becomes the bottleneck.

Modern databases solve this problem through horizontal partitioning — splitting data across many independent machines so storage capacity and throughput grow simply by adding servers.

Partitioning spreads the dataset across multiple machines so storage and throughput increase linearly with cluster size.

But this introduces a new challenge: When a request arrives, how do we decide which server should store or retrieve the data?

The First Attempt: Modulo Hashing

A natural first solution is to hash every key into an integer and map that integer to one of N servers.

int server = hash(key) % numberOfNodes;

This approach is incredibly appealing because it is:

• Simple.
• Deterministic.
• Evenly distributed (with a good hash function).
• Constant time.

It satisfies every requirement… until the cluster changes.

The Rehashing Problem

This is the biggest weakness of modulo hashing.

Let’s see what happens when we increase our cluster size from 3 nodes to 4 nodes.

Notice that the hash function never changed. Only the divisor changed.

Changing that one integer invalidated almost the entire routing table. That’s the key insight.

Imagine a cluster storing 5 million keys and 100 GB of data. Adding one server means moving roughly 75% of the dataset. That means:

• Gigabytes transferred across the network.
• Massive cache misses as requests hit empty new nodes.
• Unprecedented disk I/O spikes.
• Network saturation.
• Severe client latency increases.

This catastrophic migration storm is why modulo hashing is rarely used in distributed databases.

The Solution: Consistent Hashing

Consistent Hashing is the exact algorithm used by DynamoDB, Cassandra, and nearly every modern distributed database. It completely eliminates the massive rehashing problem.

To understand it, we start with the hash space itself. A standard 32-bit hash function can output any integer from 0 to 2³² — 1.

We connect both ends to form a circle.

How Routing Works

Routing a key to a node takes three simple steps:

Why clockwise? Why not nearest? Why not anticlockwise?

Because every point on the ring belongs to the first server encountered while moving clockwise. That naturally partitions the ring into ownership ranges. A server owns the entire section of the ring extending counter-clockwise until the next server.

Adding a Node

The genius of this ring becomes apparent when we scale. Let’s add Node D.

When Node Cis placed on the ring, it splits Node A’s partition. Only that arc changes ownership. Everything else remains untouched. That’s the “aha” moment.

Removing a Node

The exact same principle applies to failures.

If Node C is removed, Node A now owns that partition. Again, only the adjacent partition changes; the rest of the cluster is entirely undisturbed.

The Virtual Node Enhancement

Placing physical nodes directly on the ring introduces a critical issue: uneven distribution.

Because node IDs hash randomly, Node A and Node B might end up very close to each other on the ring, leaving a massive gap for Node C to cover.

To solve this, we use Virtual Nodes (VNodes). This is arguably the most important engineering improvement in consistent hashing.

Instead of placing Node A on the ring once, we place it 150 times (using names like NodeA-vnode-1, NodeA-vnode-2, etc.). We do this for every physical server.

Each physical server owns many tiny ranges instead of one huge range. Those tiny ranges average out, resulting in an evenly scattered, perfectly balanced distribution of data and traffic across the cluster.

Why TreeMap? Implementing the Ring in Java

A consistent hash ring requires two operations:

1. Keep nodes ordered by hash.
2. Efficiently locate the first node clockwise.

Java’s TreeMap is a natural fit because it maintains keys in sorted order and provides ceilingEntry() in O(log N), allowing us to locate the next node on the ring without implementing a custom balanced tree.

@Service
public class HashRing {
    private final int VIRTUAL_NODES = 150;
    private final TreeMap<Long, String> ring = new TreeMap<>();

    public void addNode(String nodeId) {
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            long hash = HashUtils.hash(nodeId + "-vnode-" + i);
            ring.put(hash, nodeId);
        }
    }
    public String getNode(String key) {
        if (ring.isEmpty()) return null;

        long hash = HashUtils.hash(key);
        Map.Entry<Long, String> entry = ring.ceilingEntry(hash);

        // If we wrapped past the end of the ring
        if (entry == null) {
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }
}

That is a robust, O(log N) routing algorithm in just a few lines of code.

Trade-offs

Consistent hashing is the industry standard, but it brings its own set of trade-offs:

Advantages:

• Minimal data movement when scaling (only 1/N of the data moves).
• Linear scalability for storage and throughput.
• Deterministic routing.
• No central routing table (no single point of failure).

Costs:

• Additional routing metadata (storing the VNodes in memory).
• More complex implementation than simple modulo arithmetic.
• Memory consumed by virtual nodes (though 150 entries per node is negligible).
• Rebalancing logic is still required to physically move the data when ownership changes.

Test it Yourself

You can verify the routing distribution of the hash ring by adding a few nodes and checking where keys land:

# Terminal 1
SPRING_PROFILES_ACTIVE=node1 ./mvnw spring-boot:run

# Terminal 2
SPRING_PROFILES_ACTIVE=node2 ./mvnw spring-boot:run

# Terminal 3
SPRING_PROFILES_ACTIVE=node3 ./mvnw spring-boot:run

# 1. Write 30 keys to node-1 (any node can receive any request)
for i in $(seq 1 30); do
  curl -s -X PUT http://localhost:8080/api/v1/keys/key:$i \
    -H "Content-Type: application/json" \
    -d "{\"value\": \"val-$i\"}" > /dev/null
done

# 2. Read the same keys from a DIFFERENT node (node-2)
# Should still work — node-2 routes to the responsible node
curl http://localhost:8081/api/v1/keys/key:1
curl http://localhost:8081/api/v1/keys/key:15
curl http://localhost:8081/api/v1/keys/key:30

# 3. Verify distribution — keys should be spread across all three nodes
# Watch the logs for "Forwarding" entries — node-1 handles ~33%, forwards ~67%

# 4. Check that consistent hashing is consistent:
# The same key always routes to the same node regardless of which node receives the request
for node_port in 8080 8081 8082; do
  echo -n "From node at $node_port: "
  curl -s "http://localhost:$node_port/api/v1/keys/key:1"
done
# All three should return the same value ✅

# 5. Confirm each key has exactly one owner
# Check logs: "Forwarding PUT /key:N → node-X" shows which node owns key:N
# PUT key:1 from node-1 should always forward to the same node every run

What’s Next?

Up to this point, our hash ring has existed entirely in memory. It can determine which node should own a key, but there is only one node in our application.

In the next article we’ll bring the ring to life by running multiple instances of our key-value store with Docker Compose, forwarding requests between nodes, and building our first real distributed cluster.