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/meta2 ranges 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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.