Sharding and consistent hashing: how data is split across many servers

Key points

• Sharding buys write capacity and storage at the cost of cross-shard queries, cross-shard transactions and harder operations; try vertical scaling, replicas and in-database partitioning first.
• The shard key decides everything: high cardinality, even load, and the property that most queries need only one shard.
• Range sharding keeps scans cheap but invites hot spots; hash sharding spreads load but loses ranges; a directory gives full control at the price of a lookup service.
• Going from N to N+1 servers with hash mod N moves about N/(N+1) of the keys; consistent hashing moves about 1/(N+1).
• Virtual nodes even out a hash ring; rendezvous hashing needs no ring; jump hash needs no memory but only numbered buckets.
• Plan resharding from day one: many small fixed partitions moved as units are easier than splitting live key ranges.

Why shard, and why not yet

Sharding is horizontal partitioning across machines: rows of the same table live on different servers, chosen by a shard key. It is the answer when one primary can no longer take the write rate, or the data no longer fits on one machine. It is also expensive for as long as the system exists. Queries that span shards get slower and harder to write, transactions across shards need extra machinery, and backups, schema changes and failover multiply by the number of shards.

Most applications hit a fixable bottleneck long before they need it. Work through the cheaper options first:

• Fix the queries. Missing indexes and full scans cause most “the database is too slow” problems; see database indexing explained.
• Scale vertically. A larger machine with more memory and faster disks is a configuration change, not a redesign.
• Add read replicas for read-heavy load, and a cache in front of hot reads (see caching strategies). Neither helps write throughput.
• Partition inside one database. PostgreSQL’s declarative partitioning splits a table by range, list or hash; the planner skips partitions that cannot match a query, and dropping or detaching an old partition is far faster than a bulk DELETE. It solves big-table and data-retention problems on one server, and teaches you the access patterns a shard key will need.
• Split by function. Moving one heavy domain, such as events or search, to its own database is a different kind of split; monolith vs microservices covers when service boundaries are worth it.

Shard keys and hot spots

The shard key is the column, or columns, that decide which shard a row lives on. Changing it later means moving every row, so it is the most important decision in a sharded design. The Citus documentation’s advice for choosing a distribution column generalizes well:

• High cardinality. A key with few distinct values, such as a status or a country, caps the number of useful shards.
• Even distribution. If many rows share a few values, Citus notes that data accumulates in certain shards and those nodes do more of the work.
• Query locality. Most queries should name one key value, so they go to one shard. In a multi-tenant SaaS app that is usually the tenant id, and Citus recommends distributing tables by a common tenant column so a tenant’s rows sit together and its joins and transactions stay on one node. See multi-tenant architecture for the wider design.

Hot spots come from two places. Skewed keys: one enormous tenant, or one celebrity account, outweighs a whole shard. Monotonic keys under range sharding: a timestamp or an auto-increment id sends every new write to the last range, so one shard takes all the inserts while the rest sit idle. The remedies are hashing the key, adding a suffix to split a hot key across several shards (and reading all of them back), caching hot reads, or moving a very large tenant to a shard of its own.

Range, hash and directory-based sharding

Real systems combine them. Vitess maps a column to a keyspace ID with a primary vindex, typically a hash, then assigns each shard a range of keyspace IDs, named by hex boundaries such as -80 and 80- for the two halves; a lookup vindex is a directory for secondary columns, so a query by another column goes to the right shard instead of all of them. Cassandra hashes each partition key onto a token ring. PostgreSQL hash partitioning assigns rows by a modulus and remainder of the key’s hash, inside one server.

Why hash mod N remaps almost everything

The obvious hash scheme is shard = hash(key) % N. It balances well, and it breaks the moment N changes. Going from N to N+1 servers, a key stays put only if its hash leaves the same remainder for both, and for uniform hashes that is about 1 key in N+1. So about N/(N+1) of all keys move: with 10 servers becoming 11, about 91 percent of the data changes servers, and for a cache, 91 percent of the keys miss at once.

The least you can move is the new server’s fair share, about 1/(N+1) of the keys, all of it going to the new server. A hash scheme that achieves roughly that is what “consistent” means here. Karger and co-authors, who introduced the idea in 1997 for distributed web caches, describe a consistent hash function as one that changes minimally as its range of buckets changes.

Consistent hashing and virtual nodes

Picture the hash space as a circle. Each server is hashed to a point on it, and each key is hashed onto the same circle and belongs to the next server point clockwise. Karger’s construction maps an item to the closest bucket point; systems such as Dynamo use the clockwise successor. Adding a server only takes the arc between it and its predecessor; the Dynamo paper puts it as the arrival or departure of a node affecting only its immediate neighbors.

With one point per server, random positions leave arcs of very different sizes, and a removed server dumps its whole load on one neighbor. Virtual nodes fix both: each server takes many points. Karger’s construction already gives each bucket many points, a number proportional to the log of the largest expected bucket count. Dynamo calls them virtual nodes, or tokens, and lists three benefits: a failed node’s load spreads evenly across the rest, a new node takes a roughly equal share from every other node, and a bigger machine can take more virtual nodes than a smaller one.

import bisect
import hashlib

def h64(s: str) -> int:
    """A stable 64-bit hash. Python's built-in hash() changes between runs."""
    return int.from_bytes(hashlib.sha256(s.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, nodes, vnodes=100):
        self.vnodes = vnodes
        self.points = []  # sorted (position, node) pairs
        for node in nodes:
            self.add(node)

    def add(self, node):
        for i in range(self.vnodes):  # one point per virtual node
            bisect.insort(self.points, (h64(f"{node}#{i}"), node))

    def remove(self, node):
        self.points = [p for p in self.points if p[1] != node]

    def node_for(self, key: str) -> str:
        i = bisect.bisect(self.points, (h64(key),))  # next point clockwise
        return self.points[i % len(self.points)][1]  # wrap around the top

More points mean better balance and more metadata. In a run with 10 nodes and 100,000 keys, the busiest node held 3.09 times the mean with one point per node, 1.18 times with 100 and 1.05 times with 1,000. Cassandra’s documentation describes the same trade-off: in 2.x, random token selection needed a default of 256 tokens per node to balance well, and later versions added a deterministic token allocator so fewer tokens give good balance. It also notes the cost of many tokens: each node has more neighbors, which raises the chance that an outage affects some range, and repairs become more numerous and slower.

Rendezvous hashing and jump consistent hash

Rendezvous hashing, or highest random weight (HRW), comes from Thaler and Ravishankar’s 1998 paper “Using Name-Based Mappings to Increase Hit Rates”. For each key, score every server with a hash of the server and the key together, and pick the highest score. There is no ring to store or keep sorted, every client computes the same answer from the same server list, and when a server leaves, only its keys move, each to its own second choice. The cost is a lookup that scores all N servers.

Jump consistent hash, published by Lamping and Veach in 2014, needs no memory at all: a few lines of arithmetic map a 64-bit key to a bucket number. The authors report that it is faster than Karger’s method and divides keys more evenly. Its limitation, in their words, is that buckets must be numbered sequentially, so you can add or remove only the last bucket, which suits numbered data shards rather than a pool of cache servers that fail at random.

def jump_hash(key: int, num_buckets: int) -> int:
    """Jump consistent hash (Lamping and Veach): a 64-bit key to 0..num_buckets-1."""
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = (key * 2862933555777941757 + 1) % 2**64  # 64-bit linear congruential step
        j = int((b + 1) * (2**31 / ((key >> 33) + 1)))
    return b

def rendezvous(key: str, nodes) -> str:
    """Highest random weight (Thaler and Ravishankar): score every node, keep the top."""
    return max(nodes, key=lambda n: h64(f"{n}:{key}"))

How many keys move: an experiment

The code below places 100,000 keys on 10 nodes, adds an eleventh, and counts how many keys changed nodes under each scheme. The numbers in the comments are from an actual run with the code above.

# Uses h64, HashRing, jump_hash and rendezvous from the blocks above.
keys = [f"user:{i}" for i in range(100_000)]
before = [f"node-{i}" for i in range(10)]
after = before + ["node-10"]

def moved(old, new):
    return sum(old(k) != new(k) for k in keys) / len(keys)

r1, r2 = HashRing(before), HashRing(after)
print(moved(lambda k: h64(k) % 10, lambda k: h64(k) % 11))  # 0.909
print(moved(r1.node_for, r2.node_for))                       # 0.084
print(moved(lambda k: jump_hash(h64(k), 10),
            lambda k: jump_hash(h64(k), 11)))                # 0.090
print(moved(lambda k: rendezvous(k, before),
            lambda k: rendezvous(k, after)))                 # 0.090
# The floor is 1/11 = 0.091, the new node's fair share. With the ring, every
# moved key went to node-10. Busiest node's keys over the mean, by vnodes per
# node: 1 -> 3.09, 10 -> 1.35, 100 -> 1.18, 1000 -> 1.05 (jump hash: 1.02).

Modulo moved 91 percent of the keys. The other three moved between 8 and 9 percent, close to the 9.1 percent floor; the ring came in slightly under it because, with 100 virtual nodes, node-10 happened to land a little less than its fair share of the circle. That is the whole argument for consistent hashing in one table: when a node joins, the data that moves is about the data the new node should hold, and nothing else.

Rebalancing and resharding

Choosing where a key belongs is the easy half. Moving data while the system serves traffic is the hard half. The Dynamo paper is candid about it: in one of its partitioning schemes, a joining node had to have its key ranges scanned out of other nodes’ stores at low priority, and during the busy shopping season that bootstrapping took almost a day. Amazon moved to a scheme that splits the hash space into a fixed number of equal partitions, gives each node an equal share of them, and moves whole partitions as files.

• Create many more partitions than servers from the start, and move whole partitions. Adding a server then means reassigning some partitions, never re-hashing keys.
• Split ranges when they grow. Vitess reshards by splitting key ranges onto new shards, copying and verifying the data while the old shards keep serving, then cutting over with a few seconds of read-only time, as its documentation describes.
• Throttle the copy. Data movement competes with live traffic for disk and network.
• Make the routing table versioned, and have clients refresh it when a shard answers that it no longer owns a key.

1. Copy the data for the moving range to the new shard while the old one keeps taking writes.
2. Stream the changes made since the copy started, from the old shard’s change log, until the new shard has caught up.
3. Verify: row counts and checksums per range.
4. Briefly stop writes for the range, apply the last changes, and switch the routing table to the new shard.
5. Keep the old copy until you are sure, then delete it.

Cross-shard queries and transactions

Everything that touches one shard stays as simple as a single database. Everything else costs more:

• Queries by a column other than the shard key fan out to every shard and merge the results. Global secondary indexes, such as Vitess lookup vindexes, turn that into a lookup and a single-shard query, at the cost of keeping the index in step with the data.
• Joins work only between rows on the same shard. Citus co-locates tables that share a distribution column so their matching rows sit on one node, and copies small reference tables to every node; otherwise, its documentation notes, the join has to be split into steps and combined in the application.
• Sorting, pagination and aggregates across shards need a merge step, and OFFSET pagination gets expensive; use keyset pagination by the sort key.
• Auto-increment ids collide across shards. Use ids that are unique without coordination, such as UUIDs or time-ordered ids with a shard or node component.
• Transactions across shards need two-phase commit, which some systems provide and all pay for in latency and failure modes. Often the better design keeps each transaction on one shard and coordinates the rest asynchronously with an outbox and idempotent consumers, as in idempotency and job queues.

The pattern behind all of this: choose the shard key so the transactions and queries that matter most stay on one shard, and accept that the rest are slower. If that key does not exist for your data, that is a strong sign the system is not ready to be sharded yet.

BYD Tech builds web apps and their backends: the code lives in the client’s GitHub from day one, the founders are on the calls, and AI-assisted work is reviewed by an engineer.