Part 4 of 8 · 2 min read
Partitioning by key range
Giving each partition a continuous slice of the keys, like volumes of an encyclopedia.
Think of the volumes of a paper encyclopedia, each covering a stretch of the alphabet. If you know the boundaries, you can find the right volume at once. The volumes are not all the same width in letters: the volume for T to Z holds many words, and the one for A and B holds just as many with fewer letters. The boundaries follow the data.
Key-range partitioning
In key-range partitioning, each partition gets a continuous range of keys, from a minimum to a maximum. A key goes to the partition whose range holds it.
Example: partition 1 holds keys A to F, partition 2 holds G to M, partition 3 holds N to S, partition 4 holds T to Z.
The book notes the ranges are not necessarily equal in width, because data is not evenly spread. The boundaries must adapt to the data. An administrator can choose them by hand, or the database can choose them. Bigtable, HBase, RethinkDB and MongoDB before version 2.4 use this method.
Strengths. Within each partition the keys can be kept in sorted order (like the sorted tables of Level 2, module 4). This makes range scans easy. The key can serve as a combined index to fetch several related records in one query.
Weakness. Some access patterns create hot spots. The book's example is sensor data with a timestamp as the key (year-month-day-hour-minute-second). Partitions then correspond to ranges of time, such as one per day. All the writes happen "now", so all go to the partition for today. That partition is overloaded and the others idle.
The fix from the book: do not make the timestamp the first part of the key. Put the sensor name first, then time. With many sensors active at once, the writes spread over many partitions. A cost: to fetch several sensors in a time range, a separate range query is needed for each sensor.
A worked example. 1,000 sensors each write once per second, 1,000 writes per second in total. There are 10 partitions.
| Key | Where today's writes go | Writes/s per partition |
|---|---|---|
| Timestamp first | All to the "today" partition | 1,000 on one, 0 on nine |
| Sensor name first (names spread evenly over the alphabet) | Spread over 10 partitions | About 100 on each |
Read a month of data for one sensor:
- Timestamp first: scans all partitions that cover the month (all of them, if each holds a day).
- Sensor first: one partition (or a few), since the key starts with the sensor.
The trade-off is typical: the key must match both the writes and the reads.
| Strength | Weakness |
|---|---|
| Range scans are fast | Some key choices create hot spots (time, sequential ids) |
| Easy to see where a key lives | Boundaries must be adjusted as the data changes |
Check yourself:
- Why does a timestamp key create a hot spot?
- How does putting the sensor name first change reads over a time range for many sensors?