Segment-Based Indexing and the Merge Operation

A search index that mutated in place would be fast to query but nearly impossible to update safely: every append to a postings list would need to move or rewrite the tail of a compressed list, and a concurrent reader would see a half-updated structure. The answer adopted by essentially every production search system is to build the index as a collection of small, immutable segments and to reclaim their waste through a periodic merge. The merge operation is the single most important mechanism behind both update cost and steady-state query latency.

Why immutability

A segment is a complete, self-contained inverted index over a batch of documents: it has its own term dictionary, its own postings lists, and its own document id mapping. Once written, a segment never changes. This buys three things. First, writes are sequential: a segment is produced by sorting an in-memory buffer and streaming it to disk, with no seeks and no in-place updates. Second, readers are trivially safe: a query sees a fixed set of segments, and since none of them change, there is no read-write race to manage. Third, crashes are simple: a half-written segment is simply discarded, because it is either complete and sealed or it is garbage.

The cost of immutability is accumulation. Every flush writes a new segment. A busy index that flushes thousands of times would end up with thousands of segments, and a query has to open and search every one of them, because a term might live in any segment. Query cost scales with segment count even when the total data is small. Merge exists to keep that count bounded.

What merge does

A merge takes a group of N smaller segments and produces one larger segment by reading all of their postings and writing them out combined. Because each input segment’s lists are sorted by document id, and because a segment’s document ids are internally contiguous, the merge is a k-way sorted merge: the output list for a term is the concatenation of the per-segment lists in segment order. No list ever has to be sorted from scratch.

The merge also must resolve document ids. A document id in the input is only unique within its segment; a segment’s ids start at zero and count up. When two segments are combined, the ids in the second input must be shifted by the number of documents in the first, so the output segment has contiguous ids from zero. This remapping is done once per document at merge time, and it is why a merged segment’s ids are always dense, while the ids across segments before the merge are sparse relative to the global id space. The remapping touches every posting, which is another reason merge is expensive even when no garbage exists to reclaim.

Merge is also the point where garbage is reclaimed. Every deleted document’s postings, flagged dead in place by the tombstone mechanism, are simply not copied to the output. A term whose list consists entirely of dead postings produces no output list at all. Merge therefore compacts the index, shrinking total size back toward the size of the live data.

The trade-off is I/O. A merge reads every byte of the segments it combines and writes most of it back out. The write amplification of a size-tiered policy is roughly logarithmic in the number of flushes, because each document participates in several merges across its lifetime rather than one. This is the same cost curve that a log-structured filesystem pays for its cleaner, and it is the reason merge is scheduled and throttled rather than run eagerly.

Choosing which segments to merge

A merge policy picks the inputs. Two families dominate. Tiered, or size-tiered, policies merge groups of segments whose sizes are within a ratio of each other, which keeps segment sizes in a small number of distinct tiers and bounds the number of segments logarithmically. Leveled, or leveled-compaction, policies keep a fixed number of small segments that roll up into larger levels, which gives more predictable and lower read amplification at the cost of higher write amplification.

The choice is a direct latency-versus-write trade. Tiered merging does less I/O per document but can leave many segments for a query to search. Leveled merging searches fewer, larger segments but rewrites data more often. A system tuned for fast queries with a steady write stream leans leveled; one tuned for ingest throughput leans tiered.

Merge and the searcher switch

A merge is invisible to queries until it completes and the result is published. The old segments stay available while the merged segment is written to a temporary file; only when the merged segment is fully written and synced does the system atomically swap it into the visible set and drop the inputs. Readers holding an older view of the segment set are unaffected, because the swap is a pointer change, not a mutation of the files they are reading. This copy-on-write publication is the same mechanism that makes near-real-time refresh possible, and it means a reader never blocks on, or sees, a merge in progress.

The swap also drops the input segments’ files, but not immediately: they stay on disk until every reader that still holds them has finished, through the reference counting described in searcher snapshots. A merge therefore has a two-phase life: a long, expensive copy phase that is invisible, followed by a near-instant publish phase that changes what is visible. The system spends almost all of its merge time in the first phase, which is why a merge can run in the background without any query ever noticing its existence.

The one thing a merge must respect is ordering of the deletion stream. A delete arrives with a generation or sequence number; a merge may drop a document only if it has seen every delete up to the generation it is merging. If a delete arrives after the merge read its inputs, that delete applies to the merged segment instead, and must be replayed against it. Getting this wrong produces resurrected documents, the classic merge bug.

Failure modes

Merge degrades at the edges. A single enormous segment cannot be merged with anything cheaply, so policies cap segment size and leave the largest segments alone, accepting that some garbage in a very large segment stays until the segment is rewritten for another reason. Merge storms happen when a policy tries to catch up after a long pause: dozens of merges run at once, and their I/O competes with query traffic, which is why merge is throttled against a measured I/O or latency budget. And a merge that runs out of disk space partway through fails cleanly, leaving the temporary file to be deleted and the inputs untouched, which is exactly the crash-safety property immutability was designed to provide.

Segment-based indexing is the architectural foundation everything else in this cluster stands on. Deletion is cheap because merge reclaims; refresh is cheap because segments are immutable; and query latency is bounded only because merge keeps segment count small enough to search.