Key Range Partitions
Also known as:
Range Partitioning
Range Sharding
Key-Range Partitions
Definition
Key range partitions divide a sorted keyspace into contiguous chunks and store each chunk on a node. Keys that sort next to each other live together, so a query for a span of keys contacts only the chunks that overlap that span. The number of chunks changes over time: a chunk splits when it grows too large or too busy, and small neighbors can merge. Sequential keys such as timestamps pile up on the last chunk, which is the pattern’s classic hotspot.
Key Takeaways
- Neighboring keys share a node, so range scans and prefix scans stay on a few partitions.
- A key is found by binary search over a sorted list of range boundaries, then a lookup of which node owns that range.
- Ranges split and merge. The partition count is not fixed up front the way it is with fixed partitions.
- A timestamp or auto increment id writes only to the newest range. Splitting that range moves the hotspot. A high cardinality prefix, or a hash of the leading column, spreads it.
How It Works
- Keep keys in sorted order and cut the line into half open spans such as [a, f), [f, n), and [n, z).
- Store a sorted directory of those boundaries, usually in a consistent core or in meta ranges, and cache it on each client.
- When a range crosses a size or load limit, pick a split key and replace it with two smaller ranges. Move one of them if the node is still busy.
- In CockroachDB, TiKV, and YugabyteDB each range is its own Raft group, so a hot range is a hot leader until it is split and one half moves.
Where It Is Used
- Google Bigtable tablets, HBase regions, and Cloud Spanner splits are key ranges of the row or primary key.
- CockroachDB ranges default to a split around 512 MiB. TiKV regions are the same idea under TiDB.
- YugabyteDB defaults to ranges of a hash, and uses ranges of the raw key only when you ask for ASC or DESC sharding.