The Fundamental Partitioning Dilemma
When a storage system grows beyond a single physical server, the keyspace must be split across hundreds or thousands of nodes. Distributed systems rely on two foundational partitioning paradigms: Range Partitioning and Consistent Hashing.
Architectural Comparison
flowchart TD
subgraph RangePart ["Range Partitioning (Bigtable / Spanner / HBase)"]
RNode1["Node 1: Keys a to g"]
RNode2["Node 2: Keys g to p"]
RNode3["Node 3: Keys p to z"]
end
subgraph HashPart ["Consistent Hashing (Dynamo / Cassandra / Riak)"]
Ring["Token Ring [0 .. 2^64-1]"]
HNode1["Node A (Token 1000)"]
HNode2["Node B (Token 5000)"]
HNode3["Node C (Token 9000)"]
end
Tradeoff Matrix
| Dimension | Range Partitioning | Consistent Hashing |
|---|---|---|
| Range Queries | Extremely Efficient: Sequential keys reside on contiguous nodes. BETWEEN '2026-01-01' AND '2026-01-31' hits exactly 1-2 nodes. | Terrible: Adjacent keys hash to completely random positions on the ring. Range queries across partition keys require scatter-gather to every node (ranges within one partition key, via clustering or sort keys, stay efficient). |
| Hot Spot Vulnerability | High: Monotonically increasing keys (auto-increment IDs, timestamps) direct 100% of write traffic to the single tail partition. | Spreads distinct sequential keys, but a single hot key or skewed request distribution can still overload one owner. |
| Metadata Coordination | Requires a centralized Partition Manager / Coordinator to track split boundaries and rebalance tablets. | Decentralized: Nodes determine partition ownership locally via token ring ranges and gossip protocols. |
Worked example: how much data moves when you add a node
A cluster has 10 nodes holding 10 TB. You add an 11th.
| Scheme | Fraction of keys that move | Data moved |
|---|---|---|
| hash(key) mod N | About 10/11, roughly 91% | About 9.1 TB |
| Consistent hashing with many virtual nodes | About 1/11, roughly 9% | About 0.9 TB, taken evenly from all nodes |
| Range partitioning with split and move | Only the ranges assigned to the new node | Chosen by the balancer, for example about 0.9 TB |
Worked example: the timestamp hotspot
An event table keyed by event_time under range partitioning receives 50,000 writes per second. Every new key is greater than all existing keys, so 100% of writes land on the tail range, whatever the cluster size. Fixes:
- Composite key:
(device_id, event_time)spreads writes across devices while keeping each device's events in time order. - Salting: prefix with
hash(event_id) mod 16; writes spread over 16 ranges, but a time-range query must fan out to 16 ranges. - Pre-splitting: HBase and Bigtable users create split points ahead of time so a new table does not start on one server.
How real systems choose
| System | Scheme | Range queries |
|---|---|---|
| Bigtable, HBase, Spanner, CockroachDB, TiKV | Range, with automatic splits | Efficient across the whole keyspace |
| Cassandra, ScyllaDB | Hash of partition key on a token ring | Only within a partition, via clustering columns |
| DynamoDB | Hash of partition key into internal partitions, sort key ordered within | Only within a partition key |
| MongoDB | Either ranged or hashed shard keys | Depends on the choice |