Segments, deletes, snapshots and merges

This note is normative for the index lifecycle. File frames, the commit file and the commit protocol are in commit-format.md; the storage interface is in storage.md.

The segment

A segment is an immutable set of files that holds a range of documents numbered 0 … docCount-1. Its name is s plus 16 lowercase hex digits (s0000000000000007); names are allocated from the commit's next segment id counter and only ever grow, so name order is creation order. A file is named <segment>.<part> (s0000000000000007.ids); a delete file is <segment>.del<generation>.

Parts:

A small flush writes most of these parts into one <segment>.pack file instead (see "Pack files" in commit-format.md); which parts share it is recorded in the commit, and readers see no difference.

Every file uses the frame of commit-format.md (magic, version, checksummed footer). The commit records each file's length, footer checksum, part and codec version, so a file replaced after the commit is noticed when the index opens.

Document ids are dense and local to a segment. Deleting a document does not renumber anything; a merge renumbers.

The codec interface

A codec is an ISegmentCodec registered explicitly in IndexWriterOptions.Codecs. It owns one or more parts, each listed in CodecRegistry (the registry number is the format version a file of that part is written with, and a codec owner raises it when the format changes). A part is owned by exactly one codec; ids and deletes belong to the index.

public interface ISegmentCodec {
    string Name { get; }
    IReadOnlyList<string> Parts { get; }
    void Flush(SegmentFlushContext context, SegmentFileSink sink, CancellationToken ct);
    void Merge(SegmentMergeContext context, SegmentFileSink sink, CancellationToken ct);
    ISegmentPartReader? OpenReader(SegmentReaderContext context, CancellationToken ct);
}

Flush. SegmentFlushContext carries the schema, the segment name and Documents: the live buffered documents in order. Document i of the list becomes document id i. Documents that were replaced or deleted while still buffered are already removed, so a new segment has no deletes. The codec writes the files for the fields it handles (it reads the field definitions from Schema) through the SegmentFileSink: sink.Create(part, magicTag, version) returns a SegmentFileBuilder with Write(span) and Complete(). Complete writes the footer, fsyncs the file and records it for the commit. A codec with nothing to write for the schema writes nothing. If Flush throws, the writer deletes every file the sink created.

Merge. SegmentMergeContext carries the schema, the new segment name, the total live document count and Sources, one MergeSource per source segment in merge order. A source has Info, MaxDoc, this codec's own Reader for that segment (an ISegmentPartReader, or null if the segment had none of the codec's parts), Live (the source's deleted set as of the merge start) and DocMap: DocMap[old] is the new document id or -1 for a deleted document. Live documents are numbered consecutively in source order, DocMap.Base being the first new id of a source and DocMap.LiveCount the number it contributes. The codec writes the same parts it would write on flush, covering exactly the live documents. Documents deleted after the merge began are still copied; the writer deletes them again in the result.

Read. OpenReader receives a SegmentReaderContext (storage, schema, SegmentInfo, limits; OpenPart(part, out file) opens a part's file after checking its length against the commit). It returns the codec's view of the segment or null. A part reader may implement any of the reader contracts of the layers above (ITextFieldReader, IColumnReader, IStoredFieldsReader …) and SegmentReader.GetPart<T>() finds it by type. Readers are used from several threads and must be thread-safe. A codec holds no per-segment state; flush and merge may run on a background thread.

Keyword lookup. A part reader may implement ITermDocLookup so that IndexWriter.DeleteByTerm(field, value) reaches committed segments. Deleting by the identifier field never needs it (the ids part serves it).

Rules for codecs. All bytes written must be deterministic for the same input (no hash-order iteration, no timestamps). Readers validate every offset and length before trusting it and raise CorruptIndexException naming the file; they honour the IndexLimits in the context. The sink calls are synchronous.

The ids part, OIXI version 1

A sorted map from identifier to document id, so the index can replace, delete and find a document by identifier with no other codec: u32 count, a table of count entries (u32 dataOffset, u32 docId) sorted by the identifier's UTF-8 bytes (ordinal, strictly ascending), then the identifiers as varint length plus bytes, back to back in table order. A lookup is a binary search with range reads; nothing is held in memory and a lookup of an identifier up to 256 UTF-8 bytes allocates nothing. Identifiers are unique among the live documents of the index (Upsert replaces); a segment never holds two entries for one identifier, because a document replaced while still buffered is dropped before the flush.

The delete file, OIXD version 1

Body: u32 maxDoc, u32 deletedCount, u8 encoding, then encoding 0, a bitmap of ceil(maxDoc/64) little-endian u64 words, or encoding 1, the sorted deleted ids as varints (the first id, then each gap minus one). The writer picks the smaller, the bitmap on a tie. A reader rejects: a count that disagrees with the ids or with the commit, bits or ids at or past maxDoc, ids out of order, trailing bytes, an unknown encoding. A sparse delete file is held as a sorted array, so a tiny file can never force a large allocation.

A segment's deletes are versioned by the delete generation in the commit: generation 0 means no delete file; a commit that adds deletes writes <segment>.del<g+1> and lists it in place of generation g, whose file stays until the previous commit is unreferenced. A delete file is never modified.

Writer lifecycle

IndexWriter is the single writer of a storage. Calls take turns (a lock), so it is safe from several threads.

1. Buffer. Upsert(document) validates against the schema, deletes the live document with the same identifier (in the buffer or in a segment) and buffers the new one. Add is the same for schemas without an identifier. At MaxBufferedDocuments the buffer flushes.
2. Flush. The buffer becomes a new segment: every codec's Flush, then ids. The files of the segment are completed without a sync and then fsynced together (concurrently where the storage allows it) before the flush returns; a merge does the same. Nothing refers to them yet.
3. Delete. DeleteById and DeleteByTerm mark documents in the buffer or set bits in the segment's in-memory deleted set. Delete files are written at commit.
4. Merge. MaybeMerge (run after every commit by default) asks the TieredMergePolicy for groups and queues them on the IMergeScheduler. A merge reads its sources and writes a new segment; it changes nothing visible. A finished merge is installed by the next commit: the sources are replaced by the result, and deletes made to a source after the merge began are re-applied to the result through the document map.
5. Commit. Install finished merges, flush, drop segments whose documents are all deleted, write delete files for changed segments, build the commit (generation + 1) and run the commit protocol of commit-format.md. Then the commit's files are pinned, the previous commit's pin and the writer's own pending pins are released; files whose last reference went are deleted. A commit with no change writes nothing.

If the commit protocol throws, the writer cannot know whether the commit became durable and refuses further work; opening the index again tells.

Tiered merge policy

Segments are grouped into tiers by live document count: tier 0 holds segments below FloorSegmentDocs × SegmentsPerTier (1,000 × 10), and each next tier's limit is SegmentsPerTier times larger. A tier with at least SegmentsPerTier (10) segments merges its oldest MaxMergeAtOnce (10) segments, never producing more than MaxMergedSegmentDocs (5,000,000) live documents. A segment more than DeletesPctAllowed (33) percent deleted is rewritten alone. The plan is a pure function of the segment list.

Size ratio. The segments the tiers leave alone are also consolidated from the small end: sort them by live documents (name order breaks ties), count sizes below FloorSegmentDocs as the floor, and merge the largest group of the k smallest (2 to MaxMergeAtOnce) whose k-th member is at most SizeRatio (2) times the combined size of the smaller ones, within MaxMergedSegmentDocs. Segment sizes then fall off geometrically, so an index of any size keeps a handful of segments. Why: every query pays a fixed cost per segment, and fuzzy, typo and prefix expansion walk the top of each segment's term dictionary again, so on 150,000 abstracts six segments answered a two-edit fuzzy query in 2.2 ms and one segment in 1.4 ms. The price is rewriting: with flushes of 20,000 documents, 302,567 documents are written about 3.8 times in all (1.7 with SizeRatio = 0, the plain tiered policy), growing by about one write per doubling. On a bulk load the extra merges run on the merge scheduler, not on the thread that adds documents.

Scheduler seam and throttle

IMergeScheduler runs queued work. CooperativeMergeScheduler (the default; no threads) runs work on the caller during Poll (the start of every commit) and WaitForIdle; ThreadedMergeScheduler runs it on one background thread. Merge output is a function of the sources, the codecs and the new segment name only, and the name is allocated when the merge is queued, so for the same sequence of operations the segment bytes are identical under both schedulers when the caller waits for merges at the same points (WaitForMerges). Without waiting, a threaded merge may finish before or after a given commit, so the layout then depends on timing, and the contents never do. MaxMergeBytesPerSecond makes a threaded merge pause (through the scheduler) so that its output does not exceed the rate; a cooperative scheduler cannot pause and ignores it.

Snapshots and file lifetime

Every file has a reference count. References are held by: the newest commit (its commit file and every file it lists), each open IndexSnapshot, each running merge (its sources) and the writer for files written since the last commit. A file is deleted when its count reaches zero, never before. So a snapshot of commit N keeps reading correctly while the writer commits and merges past it, and the files are released when the snapshot is disposed. IndexSnapshot.Open(storage) opens the newest commit from any process, with or without a writer. Where the storage can lock, it also takes a reader lease that tells a writer in another process to keep that commit's files (docs/processes.md); the writer defers deleting any file a live lease pins and deletes it once the lease is gone, including a lease whose process was killed. IndexReader keeps a pinned snapshot and refreshes it to the newest commit.

Recovery

IndexWriter.Open reads the newest commit with CommitProtocol.OpenLatest (raising CorruptIndexException for a damaged commit; there is no fallback to an older one) and deletes every file that matches the engine's names (commit-*.oic, commit-*.tmp, s<16 hex>.*) and is not listed by the newest commit, except files that a live reader lease in another process still pins. Files with other names are left alone. Open first takes write.lock; a second writer fails with IndexLockedException. After a crash at any instant the last acknowledged commit, or a commit the caller had not yet been told about, opens and is complete.

What is tested

• tests/Durability runs the writer under the fault injector with a power cut at every storage operation of a workload (flushes, commits, delete-generation writes, merges), for each crash policy and several seeds, and checks that the reopened index equals an acknowledged commit exactly. It also fails every operation in turn.
• The multi-process campaign (Durability procs) runs a writer process and several reader processes against one directory under random kills of both (docs/processes.md).
• The kill harness runs a writer in a child process that is killed at random points; the parent reopens the directory and compares it with the commits the child acknowledged on a side channel.