Merge Scheduling and Latency-Bounded Throttling

A merge rewrites large amounts of index data, and that rewriting competes with query traffic for the same disk and CPU. Run merges too eagerly and query latency spikes; run them too lazily and segment count climbs, which also hurts latency, because a query must search every segment. Merge scheduling is the balancing act between those two failures, and it is governed by two coupled decisions: which segments to merge, and how much I/O to let the merge consume.

The policy chooses the inputs

The merge policy selects the set of segments to combine. Tiered policies group segments of similar size, maintaining a logarithmic number of size tiers; leveled policies funnel small segments into progressively larger levels with a fixed fan-out. The choice is a direct read-amplification versus write-amplification trade. Tiered merging rewrites each document fewer times but leaves more segments for queries to search; leveled merging keeps the number of segments small and predictable but rewrites data more often.

The policy’s inputs are the segment sizes and counts, which it reads from the segment directory after every flush. A tiered policy sorts the segments by size and greedily packs the smallest ones into a merge until the combined size exceeds a target, which naturally produces segments that grow by a constant factor each generation. A leveled policy instead maintains a small, fixed number of segments in the top level and rolls the overflow down into the next level, rewriting that level as it fills. Both are deterministic functions of the current segment set, so the schedule is fully determined by the flush history and the policy parameters, which is what makes it predictable enough to throttle.

The policy also caps segment size. A single segment that has grown too large is left out of future merges, because merging it with anything would cost a full rewrite of the largest chunk of the index for little gain. This means very large segments accumulate garbage, the dead postings left by tombstones, until some other event forces a rewrite. The cap is a deliberate acceptance of stranded garbage in exchange for not repeatedly rewriting the biggest segments.

Throttling against a latency budget

The scheduling side decides when the chosen merge runs, and this is where latency enters. A merge consumes disk bandwidth and CPU, and if it runs at full speed it can starve queries, which then queue behind the merge’s reads. The standard mitigation is throttling: the merge rate is reduced when query latency rises, and allowed to increase when latency is comfortably low. The controller measures the recent query latency, or a proxy such as the I/O queue depth, and adjusts the merge’s allowed throughput against a target.

The mechanism is usually a token or sleep loop: the merge writes a block, then pauses for a computed interval proportional to how far over budget the system is. The pause is what makes a merge “nice”; it trades wall-clock merge completion time for steady query latency. A merge that would finish in a minute at full speed might take several minutes throttled, but queries never see a spike.

Throttling has a hard lower bound. A merge that is throttled to zero never completes, and if the ingest rate stays positive, segments accumulate faster than they combine. The scheduler therefore guarantees a minimum merge throughput even under load, accepting some latency cost to avoid the worse failure of unbounded segment growth. This is the same starvation-versus-progress dilemma a log-structured filesystem’s cleaner faces.

Backpressure from the ingest side

Merges are not the only knob. When the merge falls behind, the system can apply backpressure to ingest itself, slowing or pausing the addition of new documents until the merge catches up. Backpressure trades ingest latency for merge progress, and it is usually the last lever pulled, after throttling has already been reduced as far as it can go, because pausing ingest is visible to the producer of the data.

The interaction between refresh and merge is the subtle one. A near-real-time refresh flushes a new segment on a timer, and every flushed segment is a future merge input. A short refresh interval therefore increases merge load, and a merge that is already throttled will fall further behind as refresh keeps producing small segments. The two timers, refresh interval and merge throttle, are coupled, and tuning one without the other produces either a latency spike or a runaway segment count.

Measuring merge progress and the steady state

The scheduler’s health is captured by two counters: the rate at which new segments are flushed and the rate at which the merge reclaims them. In steady state these two must balance, otherwise the segment count trends monotonically up or down. The metric to watch is therefore not the raw I/O but the gap between the flush rate and the merge rate, because a system can be doing heavy merge I/O and still falling behind if ingest outpaces it.

The segment count itself is the lagging indicator. Because a query searches every segment, the number of open segments maps almost directly onto query-time cost: each additional segment adds a dictionary lookup and a list walk to every query. The scheduler’s real objective is therefore to hold segment count within a band, and throttling is the means of staying in the band without letting merge I/O blow the latency budget on the way.

Failure modes

The named failure is the merge storm. After a long pause, such as a restart or a period of heavy load where merges were fully throttled, the policy finds a backlog of many small segments and schedules a burst of merges all at once. The burst consumes the entire I/O budget, latency spikes, throttling kicks in, and the system oscillates between full-speed merging and query starvation. The standard defense is to cap the number of concurrent merges and to smooth the schedule, merging a little continuously rather than a lot at once.

A second failure is write amplification compounding with throttling: the same bytes get rewritten through several tiers of a leveled policy, and each rewrite is slowed by throttling, so the total I/O to reclaim one document’s garbage is the product of the policy’s amplification factor and the throttle’s slowdown. An operator who sees high write I/O but little disk progress is usually seeing this product, and the fix is a policy change, not a throttle change.

A third failure is the under-merged index. If throttling is set too aggressive and ingest stays high, segment count climbs past the point where queries stay fast, and the system enters a slow spiral: queries slow down, which raises latency, which throttles merges further, which lets segment count climb more. Breaking the spiral requires relaxing the throttle or shedding ingest, which is the reason backpressure exists as an explicit escape hatch rather than a tuning nicety.

Merge scheduling is where the theoretical immutability bargain gets paid for. The merge policy chooses the cheap structure, and the scheduler makes sure that structure can be built without making queries wait, by continuously trading merge completion time against the latency budget.