Hash and Range Partitioning: Choosing What the Shard Key Preserves

A partition function maps each key to exactly one shard. That single requirement leaves an enormous design space, and the choices inside it are not about distribution quality — almost any reasonable function distributes uniformly. They are about what else the mapping preserves. A range function preserves order, and therefore the ability to scan a key interval with one sequential read. A hash function destroys order, and therefore destroys that scan. Neither is free, and the cost of choosing wrong shows up as either a hot shard or a query that must fan out to every shard in the cluster.

Range partitioning keeps the index, and the hotspot

Split the key space into contiguous intervals: [a, b), [b, c), and so on, each owned by one shard. A point lookup finds its shard by binary search over the boundaries, which is O(log S) for S shards and cheap enough to do per request. A range scan over [x, y) touches the shards whose intervals intersect that range and reads each one sequentially, because the shard’s own storage keeps keys in order.

The property this preserves is locality. Adjacent keys live together, so an index scan is a sequence of sequential reads rather than a scatter across the cluster. For a workload that reads time-ordered data (events, logs, metrics, an append-only feed) this is the difference between one shard doing a range read and every shard doing a point read. It is also what makes ordered aggregation, ORDER BY ... LIMIT, and prefix queries tractable.

The property it concentrates is write load. Keys are rarely uniform in time: an event table keyed by timestamp receives all of today’s writes at the highest boundary, so the shard owning the newest interval absorbs the entire insert rate while the others idle. The same applies to any monotonic key: an auto-incrementing identifier, a sequence, a timestamp. A range partitioner on such a key produces a single hot shard and a cluster that cannot use its own capacity.

The standard mitigation is to prefix the key with something that spreads the writes: a hash of the source, a bucket identifier, or a coarse time unit. That restores distribution and gives up pure ordering. The keys remain ordered within each prefix, so a scan over a single source is still sequential, but a scan over all sources becomes S interleaved scans. The compromise is workable and it is the usual shape for time-series data: partition by (source, timestamp), and accept that a global time-range query fans out.

Range boundaries also need maintenance. A shard that grows past a size threshold must split, and a split changes the boundary set that every router must know. That is a metadata change with its own consistency requirements, treated in shard routing and ownership metadata.

Hash partitioning spreads load and scatters reads

Apply a hash function to the key and use the digest to select a shard: shard = hash(k) mod S, or a range over the digest. The hash destroys any structure the key had, so keys that are adjacent in value are independent in placement. Write load spreads across all shards as long as the key distribution is not itself skewed.

The cost is that every range query becomes a full-cluster query. A scan over [x, y) has no shard to skip, because the digest of x and the digest of y say nothing about which shards hold the keys between them. The query is broadcast to all S shards and the results are merged, which costs S round trips and S units of work regardless of how few rows match. For a workload dominated by point lookups, this costs nothing. For a workload with any range query on the partition key, it is disqualifying.

The other cost is that the partition key must be the query key. A table partitioned by hash(user_id) cannot efficiently answer a query by order_id unless a secondary structure maps one to the other, and that structure must itself be partitioned and itself be a distributed index. The fan-out problem does not disappear; it moves to the index.

Skew survives hashing when the key itself is skewed. A hash of a key that appears in 30% of rows produces one shard holding 30% of the rows, because the hash is a function of the value and all those rows have the same value. Hashing fixes sequential hotspots, not frequency hotspots. A key chosen for even frequency is a different design decision from one chosen for even sequential arrival, and a partition key must satisfy both.

Modulo arithmetic and what it costs to change S

hash(k) mod S has a property that is fine until the cluster grows: changing S moves almost every key. With S = 10, a key with digest d is on shard d mod 10. Move to S = 11 and that same key is on d mod 11, which is a different shard for roughly ten of every eleven keys. Adding one machine therefore rewrites almost the entire dataset, and the rewrite happens while the cluster is serving traffic.

Consistent hashing addresses the movement cost rather than the distribution. Both keys and nodes are mapped onto a circular identifier space; a key belongs to the first node encountered clockwise from its position. Adding a node inserts one point on the circle, and only the keys in the arc between that node and its predecessor move — on average 1/(S+1) of the keys for S existing nodes, instead of S/(S+1). Removing a node moves only its own arc.

The price is that the circle is not automatically balanced. With few nodes the arcs are wildly unequal, so each physical node is represented by many virtual points scattered on the circle, and the balance improves as the number of virtual points grows. The variance of the load falls roughly as the inverse of the number of points per node. Karger et al. introduced the scheme for a related problem — relieving hotspots in a web cache — and the virtual-node refinement is what makes it usable for storage.

import hashlib, bisect

class Ring:
    def __init__(self, nodes, vnodes=256):
        self.points = sorted(
            (self._hash(f"{n}#{i}"), n)
            for n in nodes for i in range(vnodes)
        )
        self.keys = [p for p, _ in self.points]

    @staticmethod
    def _hash(s):
        return int.from_bytes(hashlib.sha256(s.encode()).digest()[:8], "big")

    def owner(self, key):
        # first virtual point at or after the key's position, wrapping once
        i = bisect.bisect_left(self.keys, self._hash(key))
        return self.points[i % len(self.points)][1]

Two details in that sketch are load-bearing. The wrap-around is what makes the ring a ring; without it, the keys past the last point have no owner. And the hash must be over a stable representation of the key, because a key whose byte encoding changes between writes will move between shards.

Fixed partition counts and the indirection layer

Both range and hash schemes have the same weakness: the number of shards is baked into the mapping. Consistent hashing reduces the cost of changing it but does not remove the need to move data, and modulo arithmetic does not reduce it at all.

The common answer is to separate partitions from machines. The key space is divided into a fixed, much larger number of partitions — several per machine — and each machine owns a set of partitions. Growing the cluster means moving whole partitions to the new machines, which costs the partition’s data and nothing else. The partition count is chosen once, large enough that the cluster can grow several-fold, and small enough that per-partition metadata stays manageable. A cluster with a thousand partitions can rebalance across any number of machines up to a thousand without rehashing a single key.

This indirection is what makes online resharding possible, because the unit of movement is a partition whose boundaries never change. The mapping from partition to machine is metadata, and the mapping from key to partition is a pure function of the key that never needs to change.

The trade is granularity. Too few partitions and the cluster cannot balance, because each machine’s load is a multiple of a partition’s load; the imbalance is bounded by the largest partition relative to the average. Too many partitions and the metadata grows, each partition carries per-partition overhead in memory and in background work, and a query that touches many partitions pays per-partition costs. The partition count is therefore a capacity decision made early, and the cost of changing it later is exactly the cost that the indirection was meant to avoid.

Which one a workload wants

The decision reduces to a question about the query, not about the data. If the dominant access is by exact key, hash partitioning costs nothing and distributes well. If the dominant access is by key range, or by prefix, or in key order, range partitioning is required, and the write concentration must be handled by choosing a key whose ordering is not correlated with arrival time.

Mixed workloads often call for a composite key: a partition prefix that hashes for distribution, and a suffix that preserves order within the prefix. A message store keyed by (hash(conversation_id), sequence) gives even distribution across shards and sequential reads within a conversation. A table keyed by (hash(tenant_id), timestamp) does the same per tenant. In both cases the range query that crosses prefixes fans out, and the query that stays within one prefix is efficient — which is a statement about the access pattern, not about the partitioning scheme.

The one thing neither scheme provides is a guarantee about the size of a partition. A range boundary can be chosen to split the key space evenly by count, but if the count changes the boundary does not. A hash partition can hold any number of keys. Sizing is a separate mechanism, driven by measurement and by splits, and it is the reason partitioning is an operational discipline rather than a one-time configuration.