Range partitioning

Deep dive

How it works

In: a key, a scan [a, b), or a size/load signal · Out: the owning descriptor, the ordered ranges a scan visits, or a new boundary · State: the range map (R entries of start, end, owner, generation) · Cost: O(log R) per lookup, O(log R + k) per scan

1. Map. Store start -> (end, owner, gen) sorted. The first start is the empty key, the last end +infinity: ranges tile the space, every key is in exactly one.
2. Lookup. The owner is the entry with the greatest start <= key (predecessor search).
3. Scan. Look up a, then walk successors while start < b; fan-out is the overlap count (distributed-scatter-gather-query).
4. Split. Past a size or load threshold, pick a split key (sampled median; for load, the key that halves traffic) and replace [s,e) by [s,m) and [m,e), both with a new generation. Metadata only.
5. Merge. A range that stays small joins its right neighbour (same owner, or move one first).
6. Rebalance. A controller moves whole ranges between nodes (online-resharding); each range can be its own consensus group (multi-raft).
7. Route. Clients cache the map. A node that does not own the key, or sees another generation, answers "range moved" with the fresh descriptor; the client updates its cache and retries (cache-invalidation). Descriptors carry the generation.

A monotonic key always lands in the last range, so one node takes every write and each split leaves the new right half hot. Mitigate: salt the key with a hash-bucket prefix, reverse it, split by load, or pre-split before a bulk load.

Code

Boundary map with lookup, split, merge, scan routing, size policy; checks on random splits and merges plus a hot-spot demo. Compiled and run, std only.

use std::collections::BTreeMap;
use std::ops::Bound::{Included, Unbounded};

type Key = Vec<u8>;
/// [start, end); end None = +infinity; gen bumps on every change
#[derive(Clone, Debug, PartialEq)]
struct Desc { end: Option<Key>, owner: u32, gen: u64 }

struct RangeMap { m: BTreeMap<Key, Desc> } // start key -> descriptor; first start is ""

impl RangeMap {
    fn new(owner: u32) -> Self {
        let mut m = BTreeMap::new();
        m.insert(vec![], Desc { end: None, owner, gen: 1 });
        RangeMap { m }
    }
    /// greatest start <= key; always exists (first start is "")
    fn lookup(&self, k: &[u8]) -> (&Key, &Desc) {
        self.m.range::<[u8], _>((Unbounded, Included(k))).next_back().unwrap()
    }
    /// cut the range holding `at` in two; false if `at` is already a boundary
    fn split(&mut self, at: &[u8]) -> bool {
        let (start, d) = self.lookup(at);
        if start.as_slice() == at { return false; }
        let (start, mut right) = (start.clone(), d.clone());
        right.gen += 1;
        let left = self.m.get_mut(&start).unwrap();
        left.end = Some(at.to_vec());
        left.gen += 1;
        self.m.insert(at.to_vec(), right);
        true
    }
    /// join the range at `start` with its right neighbour (same owner)
    fn merge(&mut self, start: &[u8]) -> bool {
        let Some(d) = self.m.get(start) else { return false };
        let Some(next) = d.end.clone() else { return false };
        let right = &self.m[&next];
        if right.owner != d.owner { return false; }
        let (end, gen) = (right.end.clone(), d.gen.max(right.gen) + 1);
        self.m.remove(&next);
        let left = self.m.get_mut(start).unwrap();
        (left.end, left.gen) = (end, gen);
        true
    }
    /// ranges overlapping [a, b), in key order
    fn scan(&self, a: &[u8], b: &[u8]) -> Vec<(&Key, &Desc)> {
        let first = self.lookup(a).0;
        self.m.range::<[u8], _>((Included(first.as_slice()), Unbounded))
            .take_while(|(s, _)| s.as_slice() < b).collect()
    }
    /// size policy: split at the median once a range holds more than `max` keys
    fn size_split(&mut self, sorted_keys: &[Key], max: usize) -> bool {
        sorted_keys.len() > max && self.split(&sorted_keys[sorted_keys.len() / 2])
    }
}

fn main() {
    let mut s = 88172645463325252u64;
    let mut rnd = move || { s ^= s << 13; s ^= s >> 7; s ^= s << 17; s };
    let key = |x: u64| x.to_be_bytes()[..2].to_vec(); // small key space
    let mut rm = RangeMap::new(0);
    for i in 0..2000 { // random splits; every 4th op merges a random range
        if i % 4 < 3 { rm.split(&key(rnd())); } else {
            let st = rm.m.keys().nth((rnd() % rm.m.len() as u64) as usize).unwrap().clone();
            rm.merge(&st);
        }
    }
    // coverage, no overlap: ranges chain from "" to +inf, so each key is in exactly one
    let all: Vec<_> = rm.m.iter().collect();
    assert!(all[0].0.is_empty() && all.last().unwrap().1.end.is_none());
    for w in all.windows(2) { assert_eq!(w[0].1.end.as_ref(), Some(w[1].0)); }
    for _ in 0..2000 { // scan [a,b) == brute-force overlap, in order
        let (mut a, mut b) = (key(rnd()), key(rnd()));
        if a > b { std::mem::swap(&mut a, &mut b); }
        let got: Vec<_> = rm.scan(&a, &b).iter().map(|x| x.0.clone()).collect();
        let want: Vec<_> = all.iter().filter(|(s, d)| **s < b && d.end.as_ref().map_or(true, |e| *e > a)).map(|x| x.0.clone()).collect();
        assert_eq!(got, want);
    }
    // split then merge is the identity (up to gen)
    let snap = |m: &RangeMap| m.m.iter().map(|(s, d)| (s.clone(), d.end.clone(), d.owner)).collect::<Vec<_>>();
    let (before, k) = (snap(&rm), vec![0x77, 1, 2]);
    let start = rm.lookup(&k).0.clone();
    assert!(rm.split(&k) && rm.merge(&start) && before == snap(&rm));
    // hot spot: 64 pre-split ranges; counter keys hit one range, salted keys hit all
    let mut hm = RangeMap::new(0);
    for p in 1..64u8 { hm.split(&[p * 4]); }
    let hit = |f: &dyn Fn(u64) -> Key| -> usize {
        (1_000_000..1_100_000u64).map(|id| hm.lookup(&f(id)).0.clone()).collect::<std::collections::BTreeSet<_>>().len()
    };
    assert_eq!(hit(&|id| id.to_be_bytes().to_vec()), 1);
    assert_eq!(hit(&|id| { let mut k = vec![(id.wrapping_mul(0x9E3779B97F4A7C15) >> 56) as u8]; k.extend(id.to_be_bytes()); k }), 64);
    let keys: Vec<Key> = (0..10u8).map(|i| vec![i]).collect(); // 10 keys > max 8: split at the median
    assert!(RangeMap::new(0).size_split(&keys, 8));
}

Complexity and constants

Lookup, split and merge are O(log R) in a BTreeMap. An entry is two keys, owner and generation: order of 64 bytes, so 100k ranges are a few MB. A split moves no data; it is one replicated metadata write. Measured on Apple M4 Pro, u64 boundaries, 2M random lookups: BTreeMap range 28 ns at 1k ranges, 59 ns at 100k; sorted Vec with partition_point 4.7 and 17.6 ns.

Efficiency

• Cost: a client-side lookup is tens of ns on one core (measured above, memory-latency bound); what matters is the avoided metadata round trip. A split is one replicated metadata write; a move costs O(range bytes) of network and disk.
• Levers:
  • client-side map cache, refreshed on "moved" errors — removes the metadata round trip (FoundationDB clients cache the key-range map) — many clients, rare changes
  • sorted Vec instead of BTreeMap — 59 → 17.6 ns at 100k ranges (measured) — read-mostly map
  • merge-walk over a sorted key batch — 0.5 to 0.9 ns per key (measured, 2M sorted keys) — multi-get, bulk load
  • load-based splitting — small hot ranges split on traffic (CockroachDB kv.range_split.load_qps_threshold, default 2500; Spanner) — read- or write-hot ranges
  • pre-split before a bulk load — spreads first writes (HBase docs: about 10 regions per server) — empty table, known key spread
• Naive → standard → state of the art:
  • linear scan of the range list · O(R) per request
  • sorted map, client cache, size splits · O(log R), no extra RPC
  • sorted array, batched merge-walk, load splits · about 1 ns per key in a sorted batch (measured)

Implementation notes

• Half-open [start, end): neighbours share a boundary, no gap or overlap. Compare as bytes; encode integers big-endian.
• Pick the split key from the data (sampled median, or where size or traffic crosses half), not the middle of the key space.
• Keep a gap between split and merge thresholds (CockroachDB: split above 512 MiB, merge below 128 MiB) to avoid flapping.
• Salting with B buckets turns a scan into B sub-scans merged with k-way-merge; B near the node count.

Pitfalls

• Timestamp or auto-increment keys put every write on one range (Spanner and HBase docs warn).
• Size-only splitting: a small read-hot range never splits; one hot key cannot (cache or replicate it).
• No generation check: a cache reads from the old owner after a move.

Variants and alternatives

In production

• Bigtable tablets are contiguous row ranges, the unit of distribution and load balancing; HBase regions follow.
• CockroachDB splits at the size limit or a QPS threshold and merges small neighbours; TiKV regions split and merge by size, scheduled by PD.
• MongoDB ranged sharding keeps neighbouring shard-key values in a chunk; Spanner adds split boundaries by size and load.
• TimescaleDB partitions hypertables by time into chunks.

Implementations

Sources

• Chang et al., Bigtable: A Distributed Storage System for Structured Data, OSDI 2006. paper
• Corbett et al., Spanner: Google's Globally-Distributed Database, OSDI 2012. paper
• CockroachDB: distribution layer, range sizes, load-based splitting
• Apache HBase Reference Guide: pre-splitting, hotspotting, hbase.hregion.max.filesize
• TiKV region-split-size
• MongoDB: ranged and hashed sharding
• Google Cloud Spanner schema and data model: splits, load-based splitting, hotspots
• FoundationDB architecture · Timescale hypertables