Notespartitioning🌱 seedling
Range Partitioning
Also: Key-Range Partitioning · Range Sharding · Ranged Sharding
Sort the keys and give each shard a contiguous range of them, with boundaries chosen so each range holds a similar amount of data. Range scans stay on one shard; monotonic keys pile onto the last one.
Why it exists
Many queries ask for a range: a customer's orders this month, a sensor's readings today. If the keys are kept in order across shards, a range is one contiguous run on one (or a few adjacent) shards.
How it works
- The key space is cut at boundary keys; each shard owns
[start, end). Within a shard keys are stored sorted (an LSM-Tree or B-Tree). - Boundaries follow the data, not the alphabet: equal amounts of data, not equal widths.
- Ranges usually split dynamically when they grow too big or too busy, and merge when they shrink (Rebalancing).
- Routing needs a map from boundary keys to shards (Request Routing).
Trade-offs
| Gains | Costs |
|---|---|
| efficient range scans and ordered iteration | sequential keys (timestamps, auto-increment IDs) make a Hot Spot on the newest range |
| splits follow real data distribution | needs a range map and split/merge machinery |
| natural for time-series and prefix queries | a fresh table starts as one range: bulk loads hit one node until it splits |
In practice
- CockroachDB splits a range at 512 MiB by default and also on load (by default above 500 ms of CPU per second, or 2,500 QPS when balancing by QPS);
meta1/meta2ranges hold the range map. - Bigtable, HBase, TiKV, Spanner and MongoDB's ranged sharding all partition by key range.
Pitfalls
- Keying by timestamp alone: every insert hits one shard. Prefix with an entity ID (sensor, user) and keep time as the second part of the key.
- Forgetting to pre-split before a bulk load.
Connections
- Part of
- Partitioning
- Learn first
- Horizontal Scaling
- Contrasts with
- Hash Partitioning
- In real systems
- CockroachDBSpannerMongoDBVitess
- Mentioned
- LSM-TreeB-TreeRequest Routing
Recall
These cards are also in your review deck, scheduled with spaced repetition.