Sharding and Rebalancing: Splitting Data Without Stopping the World

Sharding is the decision people postpone until it is expensive, then make under pressure, with the shard key chosen in an afternoon. That key then determines which queries are cheap, which are impossible, and how painful the next five years are. It is worth more than an afternoon.

The first thing to establish is whether you need it at all. Vertical scaling has moved a long way; a modern managed database on large hardware, with the read traffic pushed to replicas and the archival data moved out, handles workloads that would have required sharding a decade ago. Sharding is the answer when a single writer genuinely cannot keep up or a single dataset cannot fit — not when a few queries are slow.

The shard key is your query model

A good key co-locates the data that gets read together and distributes evenly. In multi-tenant systems the tenant ID is usually right: almost every query already filters by it, so most queries touch exactly one shard, and joins within a tenant stay local. The known weakness is skew — one enormous tenant on one shard — which is solved by a composite key for that tenant rather than by abandoning the scheme.

What fails is keying on something with a monotonic component, like a timestamp or an auto-increment ID. Ranges look neat and every new write lands on the last shard, which becomes the hot one while the rest idle. If you want time-ranged data locality and even write distribution, you need a composite of a hashed prefix and the time, not time alone.

import bisect, hashlib

class HashRing:
    """Virtual nodes keep the ring even and keep rebalancing proportional:
    adding a shard moves ~1/N of keys, not nearly all of them."""

    def __init__(self, shards, vnodes=256):
        self.ring, self.owner = [], {}
        for shard in shards:
            for i in range(vnodes):
                h = self._hash(f'{shard}#{i}')
                bisect.insort(self.ring, h)
                self.owner[h] = shard

    def _hash(self, key: str) -> int:
        return int(hashlib.blake2b(key.encode(), digest_size=8).hexdigest(), 16)

    def route(self, key: str) -> str:
        h = self._hash(key)
        i = bisect.bisect(self.ring, h) % len(self.ring)
        return self.owner[self.ring[i]]

# Modulo routing looks simpler and is a trap: changing the shard count rehashes
# essentially every key, which is a full data migration instead of a partial one.

For a small, stable number of large shards, an explicit lookup table mapping tenant to shard is often better than a hash ring. It is boring, it is inspectable, and it lets you move a single noisy tenant to its own shard without touching anybody else — which is a request you will get.

Rebalancing is a procedure, not an operation

Adding a shard means moving data while the system is serving traffic, and the safe version is always the same shape: dual-write to old and new, backfill historical data in batches, verify with a comparison job, flip reads behind a flag, then stop writing to the old location and only later delete. Each step is independently reversible, which is the entire point.

• Route through a lookup the application does not compute locally, so moving a tenant is a data change rather than a deploy.
• Make the migration resumable and idempotent; it will be interrupted, and restarting from zero on a large tenant is not acceptable.
• Verify before flipping. A comparison job over a sample, then over everything, catches the subtle transform bug that dual-writing hid.
• Keep the old data until you are confident. Storage is cheaper than reconstructing a tenant from backups.
• Cross-shard queries need an explicit answer up front — a search index, a warehouse, or a scatter-gather with a hard limit. Do not let them emerge by accident.

You do not choose a shard key once. You choose it, and then you live inside it — so pick the one whose worst query you can tolerate.

The honest summary: sharding trades a scaling ceiling for permanent operational complexity. Backups, migrations, analytics and debugging all become per-shard concerns, and every engineer who joins has to learn the routing model. Delay it with everything reasonable — archival, read replicas, bigger hardware, moving the hottest table out — and when you do commit, commit to the procedure rather than to the clever key.