Splitting a Partition While Writes Continue

A partition that has grown past its size threshold must become two, and the cluster cannot afford to stop writing while it happens. Stopping is the simple design: fence the partition, rewrite it as two files, publish both, resume. The rewrite of a hundred-gigabyte partition takes minutes, and the outage is proportional to the size that made the split necessary in the first place. The alternative is to split without rewriting, by turning the split into a metadata operation over data that is already ordered.

The structure that makes an in-place split possible

An in-place split works because the partition’s data is already sorted. A range partition holds a sorted key space, whether in a B-tree, an LSM-tree’s sorted runs, or an index of blocks. The boundary between the two halves is a key, not a physical position: everything below the split key belongs to the left partition and everything at or above belongs to the right.

That means the split does not need to move bytes. It needs to make the existing sorted structures addressable as two ranges. In a B-tree the root’s children can be redistributed, or the tree can be left intact and the two partitions can reference disjoint key ranges within the same physical file. In an LSM-tree, each sorted run can be divided by the split key, with each half referencing a byte range of the run rather than a copy of it. Both are index surgery on structures that already exist.

The condition for this to work is that the storage engine can answer a range query bounded on both ends without scanning from the beginning of the partition. A B-tree can, because the root directs the seek. An LSM-tree can, because each run has a sparse index and the merge can start at the split key. A heap file cannot, and a store built on one cannot split in place.

import bisect

def cut_run(index_keys, split_key):
    """Two block slices over one immutable sorted run; no data is copied."""
    i = bisect.bisect_left(index_keys, split_key)
    return (0, i), (i, len(index_keys))

The two slices reference the same underlying file. This is the same mechanism that lets a snapshot coexist with a live tree: the file is reference-counted, and neither child can rewrite a file the other can still read. Splitting is cheap as long as the engine’s files are immutable once written, which is the defining property of log-structured storage and the reason the technique originated there.

The protocol, step by step

The split has four phases, and each has a failure mode that must be recoverable without losing writes.

Decide. The partition exceeds a threshold, and a split key is chosen. The key should be an existing key near the median of the partition’s contents, because a split at a non-existent key produces an empty half and a split away from the median produces a lopsided pair that must be split again immediately. If the partition’s data is uniformly distributed, the median key is the right choice. If it is skewed, the median is still the right choice for balancing data volume, and the wrong choice for balancing write traffic, which is why a hot partition’s split needs a traffic-based split point rather than a data-based one.

Freeze the split point. The split key is recorded durably before anything else happens, so that a crash during the split can be resumed rather than guessed. The record is small: the parent’s identifier, the split key, the two children’s identifiers, and the parent’s epoch. Recording it first means the operation is idempotent; a controller that finds a pending split record can complete it or abort it without ambiguity.

Cut the structures. The engine creates the two child partitions as views over the parent’s files, each with its own in-memory write buffer and its own compaction state. New writes are routed to the child that owns their key. The parent stops accepting new writes for the range but keeps serving reads.

Publish. The metadata service records the two children and removes the parent’s ownership of the range, in one atomic change. The parent becomes a read-only view that must continue to answer for a grace period, because readers with stale maps will still send it requests. The parent’s response is a redirect to the child, not an error, so the reader’s retry lands correctly on the first attempt.

The order of the last two phases is what determines correctness. If the children are published before they can serve, requests for the range fail. If the parent is retired before the children are published, requests for the range have no owner. The safe sequence publishes the children first while the parent is still authoritative, then flips ownership, then retires the parent after a grace period. During the middle interval, the parent and the children both exist and both can serve; the parent must reject writes for the range once the children own it, or the two copies diverge.

Why the parent must keep answering

Retiring the parent immediately after the flip is the natural instinct and it is wrong. Clients hold cached maps. A client whose map is a few seconds old will send requests to the parent, and if the parent has dropped the range it must answer with something. Answering “not found” is indistinguishable from a missing key, and it turns a routing problem into an apparent data loss.

The parent therefore keeps the range in a read-only state for a grace period long enough to cover the maximum client cache lifetime, and answers every request for the range with a redirect carrying the child’s identity and epoch. The grace period is a function of the client population, not of the split, and it is the same problem as routing staleness in general, described in Routing Metadata Staleness and the Cost of a Wrong Guess.

During the grace period the parent’s files cannot be deleted, because the children are views over them. The storage cost of the split is therefore not zero: for the grace period, the data is referenced by both the parent and the children, and any compaction the children perform writes new files while the parent’s old files remain. The disk usage peaks at roughly the parent’s size plus whatever the children have rewritten, which is why splits should not be performed in a tight loop on a nearly full node.

The split key under load

Choosing the split key on a live partition is harder than choosing it offline, because the data is moving while the choice is made.

The engine reads a sample of the partition’s keys to estimate the median. On a partition receiving writes, the sample is stale by the time the split completes, and for a partition with an append-only key, the median moves continuously: every new write raises the median. A split at the median of a monotonic key space puts all subsequent writes in the right child, which then grows and splits again, exactly the pathology described in Why Append-Only Keys Concentrate Load on One Shard. The split is correct and useless.

For a workload with a hot key, the split cannot help at all. A partition whose traffic is dominated by one key cannot be divided by a boundary, because the boundary is between keys, not within one. Splitting at a key above or below the hot key moves the hot key into one child and leaves that child with all the traffic. The only way to divide a hot key is to change the data model, by suffixing the key or by replicating it, and no amount of splitting achieves it.

The case where a split genuinely helps is a partition that is large and whose load is spread over a range. Splitting halves the data and halves the traffic per child, assuming the traffic is uniformly distributed over the key range. If the traffic is concentrated at one end, splitting produces one busy child and one idle one, and the busy one splits again.

The mitigation for concentrated traffic is to choose the split point by traffic rather than by data volume: sample the request distribution, find the key that divides the requests in half, and split there. That produces children of unequal size but equal load, which is the correct objective when the constraint is throughput rather than storage. The two objectives conflict, and a partitioner that only knows about bytes will optimize the wrong one.

Compaction after the split

The children inherit the parent’s sorted runs as views, which means each child’s data is spread across the parent’s run structure rather than compacted into its own. The children’s first compactions rewrite the portions of the parent’s runs that fall in their ranges, which is a copy of the data the split avoided copying.

The cost is deferred, not eliminated. A split that appears free at the moment it happens pays for itself over the next compaction cycle, when the shared runs are rewritten as two separate run sets. The write amplification of the first post-split compaction is proportional to the data in the parent, so the split’s total cost is close to the cost of the rewrite it avoided, just spread over time and interleaved with normal compaction.

This matters for capacity planning. A node that performs many splits accumulates deferred compaction debt, and the debt is paid at the worst time: when the node is already busy with the new partitions’ write traffic. Systems that split aggressively to keep partitions small therefore trade partition-size uniformity for compaction bursts, and the bursts are the mechanism behind the two-peaked recovery curves described in Rebalance Storms and the Backpressure That Prevents Them.

Splitting versus moving

A split leaves both children on the same node. A move transfers a partition to a different node. The two operations address different problems and are often confused.

Splitting addresses partition size: a partition too large to move quickly or to compact efficiently. It does not address node load, because both children stay on the node that was already overloaded. A node at capacity that splits its partitions becomes a node with more, smaller partitions and the same total load.

Moving addresses node load: a partition on an overloaded node is transferred to a node with spare capacity. It does not address partition size, and moving a partition that is too large takes proportionally longer.

The correct response to an overloaded node is to move partitions off it, not to split them. The correct response to a partition that is too large is to split it, and then possibly move one child. Performing both in sequence, split then move one child, is the standard rebalancing step: it halves the data that must cross the network, because only one child moves rather than the whole parent. That combination is the reason splitting is worth doing even when the goal is to move data, and it is the interaction that the migration protocol in Shard Migration Cutover and the Dual-Write Window assumes when it treats a partition as the unit of transfer.

When not to split

Three conditions argue against splitting, and each is a case where the split makes the cluster worse.

The partition is below the size threshold but the node is overloaded. Splitting adds metadata and compaction debt without relieving the node. Move a partition instead.

The partition’s traffic is dominated by a single key or a narrow range. Splitting produces one child with essentially all the traffic, plus the metadata cost of two partitions. The remedy is at the data model level.

The cluster’s metadata service is already at its limit. Each split adds two partitions and one boundary, and the map that every client caches grows with the partition count. A cluster with hundreds of thousands of partitions has a routing problem that is not improved by making partitions smaller. Coarse partitions are a feature, and the threshold that triggers a split should be set with the metadata budget in mind, not only with the storage engine’s preferences.