Rebalancing & Consistent Hashing

Your database is growing. You need more shards. But how do you add them without taking the system offline? This is the rebalancing problem.

The Naive Approach: Modulo Hashing

The simplest sharding uses modulo:

def get_shard(key, num_shards):
    return hash(key) % num_shards

This works great... until you need to add a shard.

The Problem: Massive Data Movement

Formula: Keys that move = (N-1) / N
4 -> 5 shards: 75% move
10 -> 11 shards: ~91% move
100 -> 101 shards: ~99% move

This is unacceptable for a production system with billions of keys.

The Solution: Consistent Hashing

Consistent hashing was invented to solve exactly this problem. Instead of hash % N, we map both keys and servers onto a hash ring.

How It Works

• Create a ring from 0 to 2^32 (or similar large range)
• Place shards on the ring at positions = hash(shard_id)
• For each key, walk clockwise from hash(key) to find the first shard

                    0 (= 2^32)
                       │
            Shard A ───┼─── Shard B
                      ╱│╲
                     ╱ │ ╲
                    ╱  │  ╲
                   ╱   │   ╲
          Shard D ─────┼───── Shard C
                       │

Key Assignment

def get_shard_consistent(key, shard_positions):
    key_hash = hash(key)

    # Walk clockwise to find first shard
    for shard, position in sorted(shard_positions.items(), key=lambda x: x[1]):
        if position >= key_hash:
            return shard

    # Wrap around to first shard
    return sorted(shard_positions.items(), key=lambda x: x[1])[0][0]

Adding a Shard

When we add Shard E to the ring:

Before:                          After:
     A ─── B                          A ─── B
    ╱       ╲                        ╱       ╲
   ╱         ╲                      ╱    E    ╲
  D ───────── C                    D ───────── C

Keys in region AB → Shard B       Keys in region AE → Shard E (new)
                                  Keys in region EB → Shard B

Virtual Nodes

Basic consistent hashing has a problem: if shards are unevenly distributed on the ring, some shards get more keys than others.

# Instead of 1 position per shard:
shard_positions = {
    "shard_A": hash("shard_A")
}

# Use many virtual nodes per shard:
shard_positions = {
    "shard_A_v0": hash("shard_A_v0"),  # -> shard_A
    "shard_A_v1": hash("shard_A_v1"),  # -> shard_A
    "shard_A_v2": hash("shard_A_v2"),  # -> shard_A
    # ... 100+ virtual nodes per shard
}

Virtual Node Benefits

Rebalancing Strategies

Strategy 1: Live Migration

Move data while the system is running.

1. Add new shard to routing layer (receives no traffic yet)
2. Start copying data from source shards
3. Track new writes with double-write or change log
4. Once caught up, update routing to include new shard
5. Clean up old data from source shards

Strategy 2: Double-Write During Migration

Ensure no data is lost during the transition:

def write_during_migration(key, value):
    old_shard = get_shard_v1(key)  # Old mapping
    new_shard = get_shard_v2(key)  # New mapping

    # Write to both during migration
    old_shard.write(key, value)
    if old_shard != new_shard:
        new_shard.write(key, value)

def read_during_migration(key):
    new_shard = get_shard_v2(key)
    value = new_shard.read(key)

    if value is None:
        # Fallback to old shard if not migrated yet
        old_shard = get_shard_v1(key)
        value = old_shard.read(key)
        if value:
            # Backfill to new shard
            new_shard.write(key, value)

    return value

Strategy 3: Ghost Tables (Percona)

For MySQL, Percona's pt-online-schema-change approach:

1. Create "ghost" table with new structure on target shard
2. Copy existing rows in small batches
3. Capture changes via triggers or binlog
4. Apply changes to ghost table
5. Atomic swap when synchronized

Adding Shards Safely: A Checklist

Removing Shards

Removing shards follows the reverse process:

1. Stop accepting new keys for the shard being removed
2. Migrate data to remaining shards
3. Verify all data is migrated
4. Update routing to remove the shard
5. Decommission the server

Real-World: Cassandra's Approach

Apache Cassandra uses consistent hashing with virtual nodes (called "vnodes"):

# cassandra.yaml
num_tokens: 256  # 256 virtual nodes per physical node

When adding a node:

• New node joins the ring with 256 token positions
• Each existing node streams a portion of its data
• Load is distributed across all existing nodes
• No single node bears the full migration burden

Key Takeaways

Next up: Cross-Shard Queries - Handling JOINs and aggregations across shards.