Why does naive hash(key) % N sharding make rebalancing painful, and how does consistent hashing help

• Modulo sharding – shard = hash(key) % N distributes keys evenly for a fixed N, but changing N changes the result for almost every key, forcing a near-total data migration.
• Consistent hashing – keys and shards are mapped onto a fixed circular ring; each key belongs to the next shard clockwise, so adding or removing a shard moves only the keys in one arc (roughly 1/N).
• Virtual nodes – each physical shard occupies many points on the ring, evening out arc sizes and spreading rebalancing load across many shards instead of one neighbor.
• Rebalancing – data movement during shard changes should be throttled and run in the background to avoid overwhelming the cluster.

What is modulo sharding and why is it attractive?

The formula shard = hash(key) % N is simple, stateless, and gives a good even spread for a fixed N. A decent hash function scatters keys uniformly and the modulo buckets them evenly. For a cluster whose size never changes, it works well.

package com.bank.sharding;

public class ModuloRouter {

    private final int shardCount;

    public ModuloRouter(int shardCount) {
        this.shardCount = shardCount;
    }

    public int shardFor(String accountId) {
        int hash = accountId.hashCode() & 0x7FFFFFFF;
        return hash % shardCount;
    }
}

Expected output with 4 shards:
SAV2001 -> shard 1
SAV3002 -> shard 2
SAV4003 -> shard 3

Why does changing N cause a catastrophic remapping?

Because N appears in the formula, changing N changes the result for almost every key. Going from 4 to 5 shards, a key whose hash modulo 4 was 1 might now have hash modulo 5 equal to 3. Only about 1/N of keys stay put, so roughly 80% of all data must be relocated. For a large bank this means moving terabytes across the network, saturating disks, degrading the service, and risking inconsistency while data is in flight.

// Demonstration: how many keys move when N changes
public class RebalanceDemo {
    public static void main(String[] args) {
        int oldShards = 4;
        int newShards = 5;
        int totalKeys = 100_000;
        int moved = 0;
        for (int i = 0; i < totalKeys; i++) {
            String key = "ACCT-" + i;
            int hash = key.hashCode() & 0x7FFFFFFF;
            if (hash % oldShards != hash % newShards) moved++;
        }
        System.out.printf("Keys moved: %d / %d (%.1f%%)%n",
                moved, totalKeys, 100.0 * moved / totalKeys);
    }
}

Expected output:
Keys moved: 79832 / 100000 (79.8%)

How does consistent hashing work?

You imagine a ring of hash values from 0 to a large maximum that wraps around. You hash each shard to a point on the ring, and hash each key to a point with the same function. A key belongs to the first shard you reach walking clockwise. Each shard owns the arc between itself and the previous shard.

package com.bank.sharding;

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashRouter {

    private final TreeMap<Integer, String> ring = new TreeMap<>();

    public void addShard(String shardName) {
        int hash = shardName.hashCode() & 0x7FFFFFFF;
        ring.put(hash, shardName);
    }

    public String shardFor(String key) {
        int hash = key.hashCode() & 0x7FFFFFFF;
        SortedMap<Integer, String> tail = ring.tailMap(hash);
        int nodeHash = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(nodeHash);
    }
}

Why does adding a shard move only 1/N of keys?

When a new shard is added, it takes ownership only of the arc between itself and the previous shard clockwise. Only the keys in that one arc move, from the single shard that previously owned that arc. Every other key is untouched. Removing a shard is symmetric: its arc is absorbed by the next shard clockwise.

What problem do virtual nodes solve?

With only one point per shard, arcs can be very unequal. One shard may get a huge slice and another a tiny one. Virtual nodes fix this by placing each physical shard at many points on the ring.

package com.bank.sharding;

import java.util.TreeMap;

public class VirtualNodeRouter {

    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int virtualNodes;

    public VirtualNodeRouter(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    public void addShard(String shard) {
        for (int i = 0; i < virtualNodes; i++) {
            String virtualKey = shard + "-vn" + i;
            int hash = virtualKey.hashCode() & 0x7FFFFFFF;
            ring.put(hash, shard);
        }
    }

    public String shardFor(String key) {
        int hash = key.hashCode() & 0x7FFFFFFF;
        var tail = ring.tailMap(hash);
        int nodeHash = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(nodeHash);
    }
}

Expected output (150 virtual nodes per shard, 3 shards):
SAV2001 -> shard-B
SAV3002 -> shard-A
SAV4003 -> shard-C
Distribution: shard-A=33.2%, shard-B=33.5%, shard-C=33.3%

How is modulo sharding different from consistent hashing?

| Aspect | Modulo (hash % N) | Consistent Hashing |
|---|---|---|
| Keys moved on add/remove | ~80-90% of all keys | ~1/N of keys |
| Distribution evenness | Excellent for fixed N | Excellent with virtual nodes |
| Implementation | Trivial | Moderate (ring + virtual nodes) |
| Rebalancing cost | Catastrophic | Incremental |
| Weighted shards | Not supported | Give bigger machines more virtual nodes |
| Used by | Simple fixed-size clusters | Dynamo, Cassandra, distributed caches |

What are common mistakes?

// WRONG: using modulo and planning to "just rebalance later"
int shard = hash(accountId) % 4;
// When you go to 5 shards, 80% of data moves.

// CORRECT: use consistent hashing from the start
ConsistentHashRouter router = new ConsistentHashRouter();
router.addShard("shard-A");
router.addShard("shard-B");
// Adding shard-C moves only ~1/3 of keys from neighbors.
router.addShard("shard-C");

What should a senior engineer know?

• Consistent hashing is the backbone of Dynamo-style databases, Cassandra, and distributed caches.
• The number of virtual nodes trades distribution smoothness against metadata size; a few hundred per node is common.
• Rebalancing data should be throttled and background so it does not overwhelm the cluster.
• Consistent hashing handles placement and rebalancing, not replication; you still replicate each key to several successive shards on the ring for availability.
• A good shard key must have high cardinality, since consistent hashing assumes keys spread across the ring.

What are common interview follow-up questions?

• How do you replicate data on a consistent hash ring? (Store each key on the N successive nodes clockwise.)
• How does a client discover which shard owns a key? (Gossip protocol distributes the ring topology.)
• Can you remove a shard without downtime? (Yes, migrate its arc in the background, then remove the node.)