Part 6 of 8 · 4 min read
Strategies that move whole partitions
Fixed partitions, dynamic splitting and partitions per node.
Think of a warehouse that keeps goods in 1,000 numbered crates. A new forklift driver is hired. A few crates are handed to the new driver from each of the others. The crates themselves, and the labels on them, do not change. Only who looks after which crate changes.
The book describes three strategies.
1. Fixed number of partitions. Create many more partitions than nodes, and assign several to each node. A cluster of 10 nodes might have 1,000 partitions from the start, about 100 per node. When a node is added, it steals a few partitions from every existing node until the spread is fair. When a node leaves, the same in reverse. Only whole partitions move. The number of partitions and the assignment of keys to partitions do not change. Only the assignment of partitions to nodes changes. This takes time over the network, so the old assignment serves reads and writes until the transfer ends. A more powerful machine can be given more partitions. Riak, Elasticsearch, Couchbase and Voldemort use this approach.
The catch: the number is usually fixed when the database is set up, and it caps the number of nodes. It must be set high enough for future growth, but each partition has management overhead, so too many is bad. If the data set varies much in size, the partitions are either too big (slow rebalancing and recovery) or too small (too much overhead).
2. Dynamic partitioning. For key-range partitioning, fixed boundaries would be inconvenient: wrong boundaries might put all data in one partition. HBase and RethinkDB create partitions dynamically. When a partition grows beyond a configured size (10 GB by default in HBase), it splits into two with about half the data each. If lots of data is deleted and a partition shrinks below a threshold, it may merge with a neighbour. After a split, one half can be moved to another node. This is like the splitting at the top of a B-tree (Level 2, module 4).
The number of partitions adapts to the data volume. The catch: an empty database starts with one partition, so all writes go to one node until the first split. HBase and MongoDB allow pre-splitting, an initial set of partitions on an empty database, which needs a known key distribution. Dynamic partitioning works with hash partitioning too: MongoDB since version 2.4 splits dynamically in either case.
3. Partitions proportional to nodes. Cassandra and Ketama have a fixed number of partitions per node. When a new node joins, it randomly picks that number of existing partitions, splits each, and takes half of each, leaving the other half. Randomness can produce unfair splits, but averaged over many partitions (256 per node by default in Cassandra) the new node takes a fair share. Boundaries are picked at random, so hash partitioning is needed. This is closest to the original definition of consistent hashing (module 6).
A worked example of the fixed number of partitions. 1,200 partitions, 10 nodes, 120 per node. An 11th node joins.
- Fair share: 1,200 ÷ 11 ≈ 109 partitions.
- The new node takes about 109 partitions in all, about 11 from each of the 10 old nodes (so each old node falls from 120 to about 109).
- Data moved: 109 ÷ 1,200 = 9.1 percent of the data. Compare with 91 percent under hash mod N.
- If the data is 6 TB, partitions are 5 GB each. Moving 109 partitions = 545 GB. At 100 MB per second (shared over the network), that takes 545,000 MB ÷ 100 = 5,450 seconds, about 91 minutes, while the cluster keeps serving.
A worked example of dynamic splitting. A partition limit of 10 GB. A partition reaches 10 GB and splits into two of 5 GB. A node with 8 partitions of 8 GB each (64 GB) as data grows by 25 percent: each reaches 10 GB, and splits into two 5 GB partitions. The node holds 16 partitions. The new halves can be moved to other nodes to balance.
| Strategy | Partitions | Strength | Weakness |
|---|---|---|---|
| Fixed number | Set at the start | Simple, moves only whole partitions | Hard to choose the number; caps nodes |
| Dynamic | Grows with the data | Adapts to data size | Starts with one partition; needs pre-splitting |
| Per node | Proportional to nodes | Partition size stays stable | Random splits may be uneven |
Check yourself:
- A cluster has 600 partitions and 6 nodes. A 7th joins. About how many partitions does it take?
- Why does dynamic partitioning start badly on an empty database?