Range and hash partitioning
Two ways to turn a key into a partition: one keeps neighbours together, the other spreads everything evenly.
5 minute lesson
From a key to a partition
The shard key says which value decides. Something still has to turn that value into a partition. There are two basic rules, and they have opposite strengths.
- RangeA to F, G to M, N to Zeach partition owns a stretch of key values
- Hashhash of the key modulo 4the hash decides and neighbours are scattered
Opposite strengths
Range
neighbours together
- A range query
- Reads one or two partitions
- The spread of load
- As uneven as the keys
- Growing keys
- All writes hit the last partition
Hash
spread evenly
- A range query
- Asks every partition
- The spread of load
- Even
- Growing keys
- No problem
Orders are partitioned by month of their date: one partition for each month. A query asks for the orders between 10 and 20 March.
How many partitions does it have to read?
- One, the partition of March
- Two, those of March and April
- Twelve, one for each month
- All the partitions there are
Show the answer
- One, the partition of March
With ranges the database knows which stretch of dates each partition holds. The ten days in question lie inside March, so the other partitions are not even opened. This is the strength of range partitioning: a query for a range of the key touches only the partitions that the range crosses.
Range partitioning lets a range query skip every partition outside the range.
Use both at once
Most real designs combine the two. The first part of the key is hashed, to spread the load. Inside each partition the rows are sorted by a second part, so that ranges can be read there.
- Hashcustomer idpicks the partition
- Sortorder dateinside the partition
Thousands of sensors each send a reading every second. The main query is: the readings of one sensor for the last hour. The data must be spread over 20 machines.
Which key design fits?
- Hash the sensor id, and sort by time inside the partition
- Ranges of the time, with one machine for each period
- Hash the time, and sort by sensor inside the partition
- Ranges of the reading's value, from lowest to highest
Show the answer
- Hash the sensor id, and sort by time inside the partition
Hashing the sensor id spreads the sensors, and so the writes, evenly over the 20 machines. All readings of one sensor are together, and sorted by time the last hour is one connected stretch. Ranges of time would send every new reading to the newest machine. Hashing the time would scatter one sensor's hour over all of them.
Hash what the query fixes, and sort by what it ranges over.
The catch with modulo
Hash modulo the number of partitions is simple, and it has a trap. With 4 partitions a key goes to hash modulo 4. Add a fifth, and almost every key now belongs somewhere else. Nearly all the data has to move, at once.
- 4 partitions14 mod 4 = 2
- 5 partitions14 mod 5 = 4
What does hash partitioning gain over range partitioning, and what does it lose?
Show the answer
It spreads keys evenly, whatever their values, so no partition becomes hot, and keys that only grow, such as timestamps, cause no trouble. It loses the order of the keys: neighbours land on different partitions, so a query for a range has to ask all of them. And with plain modulo, changing the number of partitions moves almost all the data.
Recap
- Range partitioning keeps neighbouring keys together: good for range queries, and prone to hot spots.
- Hash partitioning spreads keys evenly and scatters ranges over all partitions.
- Combine them: hash one part of the key for spread, and sort by another part inside the partition.