The idea: two ways to decide which node holds a key
A table too big for one node is split into partitions, one or more per node, by a partition key. Something has to map each key to its node. Range partitioning gives every node a contiguous range of keys: n1 holds 0–33, n2 34–66, n3 67 and up. Hash partitioning computes a hash of the key and sends it to node hash(key) % N. Both spread a random set of keys evenly. They differ in what they do to keys that are close together.
The page stores the same 12 keys, event times t, on 3 nodes both ways and runs every action on both sides at once. A load bar under each node counts the writes it has taken, and the scoreboard keeps three numbers: how the last batch of writes was spread, how many nodes the last query had to ask, and how many keys the last added node made move. The hash is a toy, (37·t + 11) mod 100, so the arithmetic stays visible; real systems hash to a 64-bit number.
Range partitioning
The router holds a small sorted table of boundaries and finds a key's node by searching it. Keys inside a node stay sorted, so the data a range query needs sits together. When a range grows too big, the system splits it at a middle key and can move one half to another node. HBase regions, Bigtable tablets, CockroachDB and TiKV ranges, MongoDB ranged sharding and Spanner splits all work this way, and so does PostgreSQL's PARTITION BY RANGE inside one server (see partitioning vs sharding).
Hash partitioning
The router hashes the key, so similar keys get unrelated hash values and land on different nodes. Load spreads evenly whatever pattern the keys follow, and the router needs no table, only N. The price is order: the nodes no longer hold ranges of keys, so a query over a range of keys cannot know where they are. Cassandra and DynamoDB hash the partition key, Redis Cluster hashes keys to 16384 slots (see Redis Cluster), Kafka picks a partition by hashing the record key, and MongoDB offers hashed sharding.
Time-series keys: the range hot spot
Times, auto-increment IDs and sequence numbers only grow. Under range partitioning each new key is the largest so far, so it always falls in the last range. Demo: time-series writes writes t = 100 … 105: on the range side all 6 go to n3, which takes 100% of the writes while n1 and n2 do nothing. On the hash side they spread 2 · 2 · 2.
Splitting does not help. Demo: split the hot range adds a node: n3's range 67+ splits at t = 101 and n4 takes 101+. The next 6 events all go to n4: the hot spot moved, it did not go away. Systems that range-partition time-series data work around it: they put something before the time in the key (a device or user ID, so the key is (device, time)), add a small salt or bucket number in front, or hash-partition by the first part of the key and keep ranges only inside it (Cassandra's partition key + clustering columns, Bigtable's row-key design advice).
Range scans: one node vs scatter-gather
Demo: range scan 40–55 runs WHERE t BETWEEN 40 AND 55. The range router sees that only n2's range 34–66 overlaps and asks n2, which reads 44, 51, 55 next to each other and already in order: 1 node, 2 messages. The hash router cannot tell which nodes hold keys between 40 and 55, so it asks all 3 (scatter-gather), each finds one row, and the router merges the three lists: 3 nodes, 6 messages. With 100 nodes the hash side would ask 100. A point lookup (Demo: point lookup t = 44) is a tie: both routers compute the one node, n2 by range and n1 by hash.
Adding a node
Demo: add a node grows both sides from 3 to 4 nodes. The range side splits its fullest range (n3, 67+, at its median key 86) and only n3's upper half moves: 2 of 12 keys. The hash side changes N from 3 to 4, which changes hash(t) % N for most keys: 8 of 12 move, between every pair of nodes. Plain % N is why real hash-partitioned systems put a fixed set of buckets between keys and nodes: Redis Cluster's slots, Cassandra's token ring, consistent hashing. Then a new node takes over some buckets, and only about 1/N of the keys move, the same as a range split.
When to pick which
| Range partitioning | Hash partitioning | |
|---|---|---|
| Key → node | search a sorted table of boundaries | hash(key) % N, or hash → slot → node |
| Random keys | even, if the boundaries fit the data | even |
| Growing keys (time, IDs) | every write on the last node ✗ | spread ✓ |
| Range scan, ORDER BY key | the few nodes whose ranges overlap, in order ✓ | every node, then merge ✗ |
| Point lookup | one node | one node |
| Adding a node | split a range, move half of it | % N: most keys move; slots or a ring: about 1/N |
| Boundaries | must follow the data (split, merge) | none to manage |
| Used by | HBase, Bigtable, CockroachDB, TiKV, Spanner, MongoDB ranged | Cassandra, DynamoDB, Redis Cluster, Kafka, MongoDB hashed |
Pick range when queries read ranges or need the keys in order and the keys arrive in a spread-out way; pick hash when writes must spread whatever the keys look like and queries look up single keys. Many systems combine them: hash the first part of the key to pick the node, keep the rest sorted inside it.
What the page leaves out
Replication of each partition, automatic splitting by size or load and merging small ranges, the balancer that moves ranges between nodes, list and composite partitioning, secondary indexes (local ones mean scatter-gather, global ones are partitioned again by their own key), hot single keys that no scheme can split, real hash functions and token spaces, and virtual nodes. Demo: random keys shows that both schemes spread keys with no pattern; how evenly a range scheme does depends on where its boundaries are.