Range Partition Boundaries and the Split Key Contract

A range-partitioned table keeps the key order intact across machines. Each partition owns a half-open interval [start, end), the intervals tile the key space without gaps or overlaps, and a lookup is a search over the boundary list rather than a hash. The mechanism is simple enough to describe in a sentence. The difficulty is entirely in the boundary list: who decides it, where it is stored, what a split means for readers holding an older copy, and what happens when the interval chosen at creation turns out to be the wrong shape for the workload that arrives.

The boundary set as a data structure

The canonical representation is an ordered array of split points, with partition i owning [b[i], b[i+1]) and the last partition ending at positive infinity. Lookup is a binary search, O(log P) in the number of partitions, and the array is small enough to be cached on every client.

import bisect

class Boundaries:
    def __init__(self, splits: list[bytes]):
        self.splits = splits          # b[0] is the low end of the first partition

    def locate(self, key: bytes) -> int:
        # a key equal to a split belongs to the partition that starts at it
        i = bisect.bisect_right(self.splits, key) - 1
        if i < 0:
            raise KeyError(key)   # below the table's first boundary
        return i

The half-open convention is load-bearing. If partitions were closed at both ends, a key equal to a boundary would belong to two partitions, and every scan would either duplicate it or need a rule about which side to trust. Half-open intervals make the tiling exact: the union of all partitions is the whole key space, the intersection of any two is empty, and a key has exactly one owner by construction. The same convention governs the interior of a sorted storage engine, where an SSTable’s index block maps separator keys to blocks using the same [low, high) discipline.

Two representations are in use. A dense boundary list names every split point explicitly, which is what the array above does. A sparse representation stores boundaries inside the data itself, as special records in the sorted stream, which is how Bigtable-style tablets and some embedded engines record where one partition ends. The sparse form keeps the boundary colocated with the data, so a partition split is a local write followed by a metadata update, and the boundary cannot drift out of sync with the contents. Its cost is that a client cannot learn the boundary set without reading data or asking a coordinator.

An important degenerate case: a table can have a single partition covering [−∞, +∞). That is the state of every range-partitioned table at creation, and it means the initial write rate is bounded by one machine no matter how many are available. The bootstrap problem is real, and it is why systems pre-split by sampling or by an explicit split list at table creation.

Where split points come from

Three strategies produce the initial boundaries, and they fail in different ways.

Evenly spaced splits on the key domain. The boundary list is generated by dividing the range of the key type into P equal parts. For integer keys this gives partitions of equal width; for string keys it gives partitions of equal lexicographic span. Equal width is not equal load, because keys are not uniformly distributed over their domain. An integer key that is a timestamp in microseconds has all recent data in the top sliver of the domain, so an evenly spaced split gives one partition everything and the rest nothing. The fix is to split on the distribution of the key, not the domain, which requires sampling.

Sampled splits. The system reads a sample of existing keys, sorts them, and takes every k-th one as a boundary. This produces partitions of roughly equal key count at the time of sampling. It does not produce partitions of equal growth rate, and for an append-only key the sample is stale as soon as it is taken. Pre-splitting by sample is a reasonable answer for a bulk load and a poor answer for a live workload.

Adaptive splits. The system starts with one partition and splits whenever a partition exceeds a size or throughput threshold. This is the only strategy that tracks the actual workload, and it is the one deployed systems rely on for steady state. The threshold is usually a byte size, on the order of hundreds of megabytes to a few gigabytes per partition, chosen to keep a partition small enough to move between machines in a bounded time and large enough that the metadata cost per partition stays negligible. A tablet of 1 GB moves in seconds over a fast link; a tablet of 100 GB moves in minutes, and the movement blocks compaction and consumes bandwidth that the workload needs.

The split key within a partition is not arbitrary. It must be an existing key, or at least a key that the storage layer can seek to, because splitting at a non-existent key leaves a partition whose lower half is empty. Most engines pick the median key of the partition’s current contents, which yields two partitions of roughly equal size at the moment of the split.

The contract a split key implies

A split is a change to shared metadata, and the correctness of the whole system rests on a few invariants that are easy to state and easy to violate.

The first invariant is that boundaries are ordered and non-overlapping at every point in time that any reader can observe. A reader that holds boundary set version 7 and issues a read for key k must receive either the data from the partition that owned k under version 7, or a redirect to the partition that owns it now. It must never receive an empty result because the read went to a machine that has already given up the range. Systems satisfy this by keeping the old partition serving until the new one is durable and reachable, and by having the old partition answer with a redirect rather than a miss. The window between the metadata change and the last reader’s cache refresh is the dangerous interval, and it is the subject of Routing Metadata Staleness and the Cost of a Wrong Guess.

The second invariant is that a split does not move data. Splitting a partition in two on the same machine is a metadata operation plus, in some engines, a rewrite of the local index. The bytes stay put. Only a rebalance, which moves a partition to a different machine, transfers data. Conflating the two leads to systems that copy gigabytes in order to change an integer. Splitting and moving are separate operations with separate costs, and the split must be cheap enough to happen automatically under load.

The third invariant is that the union of the partitions equals the whole key space at all times. A split that publishes the new boundary before the new partition can serve creates a hole; a split that publishes after creates an overlap. The safe order is: create the new partition in a state where it can serve, fence the old one from accepting writes for the moved range, copy the range’s data if the new partition is on a different machine, then publish the new boundary. Each step leaves the tiling valid.

The fourth is that a key never appears in two partitions’ data files simultaneously in a way that permits two different values to be returned. During a move, the source and destination both hold the range. Reads must be routed to the source until the move commits, and the destination must not answer reads for that range until then, or the two answers can differ by whatever writes arrived in between.

Skew and the boundary that cannot be split

Range partitioning preserves order, so it inherits every pathology of ordered keys. A key that is monotonically increasing places all new writes at the end of the key space, in the last partition. The partition splits as it grows, so the data spreads, but the write traffic does not: the newest partition is always the one receiving all inserts, and it splits again as soon as it fills. The result is a cluster where one machine does the writing and the rest hold cold data. The mechanism and the countermeasures are the subject of Why Append-Only Keys Concentrate Load on One Shard.

A worse case is a single key with enormous traffic. Range boundaries are defined on keys, so a single key cannot be divided by any boundary. The partition holding it is a lower bound on that key’s throughput, and splitting around it only isolates the problem. The available remedies are all at the data model level: hash the key into sub-keys with a suffix, replicate the key for read scaling, or cache it in front of the store.

A third case is a boundary that cannot be found. If the key type is a float or a composite, choosing a split key that lies strictly between two adjacent keys is not always possible, because the domain may be dense. Floating-point keys between 1.0 and the next representable value have no interior point. Engines that split on the median of existing keys avoid the problem by never inventing a key, but they lose the ability to split an empty or single-key partition, which is exactly the partition that needs splitting when one key is hot.

Reading across boundaries

A scan that spans several partitions is executed as a sequence of per-partition scans, and the coordinator must stitch them into one ordered stream. Two details matter for correctness and one for cost.

The ordered stream must respect the boundary convention at the seams: the scan of partition i ends just below b[i+1], and the scan of partition i+1 begins at b[i+1]. If either side is off by one key, the result contains a duplicate or drops a key, and the bug appears only when a scan happens to cross a boundary at exactly the wrong place.

The cost of a cross-boundary scan is proportional to the number of partitions touched, each with its own round trip. A scan over a tenth of the key space touches a tenth of the partitions on average, but the slowest of those partitions sets the latency, so a scan over many small partitions is latency-dominated by whichever machine is busiest. The mitigation is to read partitions in parallel with a bounded window, which converts latency into throughput at the price of memory for buffered results.

A scan can also observe different partitions at different times, since each is read independently. Without a snapshot mechanism, the result is not a consistent cut of the data: a row inserted into partition 3 after partition 1 was read appears in neither, and a row deleted from partition 5 after partition 1 was read appears in the result even though it was gone before the scan finished. Range partitioning makes this visible because the scan is long-lived; the same problem exists under hash partitioning but the fan-out is usually shorter. Snapshot isolation across partitions requires a timestamp mechanism, which is a separate design problem from partitioning and is not solved by the boundary layout.

Why boundaries are kept coarse

There is a temptation to split finely, on the theory that more partitions means better balance. The opposite is true in practice. Each partition carries fixed costs: an entry in the metadata service, a lease or leader election if it is replicated, a compaction unit, a metric series, and a routing entry in every client’s cache. These costs are per-partition and do not shrink with partition size, so doubling the partition count doubles them while leaving the data volume unchanged.

Coarse boundaries also reduce the number of partitions a scan must touch, which directly reduces tail latency. And they make rebalancing cheaper per byte moved, because a move is at least one partition’s worth of data; moving many small partitions costs more in coordination than moving one large one.

The counter-pressure is that a partition must be small enough to move quickly and small enough that its leader’s CPU is not the bottleneck for its request rate. The workable range is wide, from a few hundred megabytes to a few gigabytes, and the exact number matters less than keeping partitions within it. Systems that let partitions grow to tens of gigabytes discover that a rebalance takes long enough to be interrupted by the next rebalance, and the two interact badly, as described in Rebalance Storms and the Backpressure That Prevents Them.