Write-Ahead Logging and Crash Recovery in Search

A search index holds an in-memory buffer of recently added documents. Those documents are searchable, but they are not yet durable: they live only in RAM until they are flushed to an immutable segment, and a flush can be many seconds away. If the machine crashes in that window, the documents are gone. The mechanism that closes the window is a write-ahead log, a sequential record of every mutation, replayed after restart to reconstruct the tail the crash would otherwise destroy.

Why the log exists

The core problem is that durable segment writes are expensive while in-memory indexing is cheap. An index could make every document durable by fsyncing a new segment on every add, but that turns the add path into a disk-sync-bound operation, reducing throughput by orders of magnitude. The write-ahead log decouples the two: the log is the durability mechanism, and the segments are the performance mechanism.

The log works because appending a record to a file is the cheapest durable write a storage device supports. A sequential append is a single write to the end of a file, and an fsync of that append forces only the device’s cache, not a tree of random blocks. Each incoming document is therefore first written as a record in the log, with a monotonically increasing sequence number, and only then added to the in-memory buffer. The rule “log before index” is the write-ahead discipline: a document is never reported as accepted until its log record is durable.

This is the same pattern that database systems have used for decades under the name write-ahead logging, and the ARIES recovery method formalized the invariants. The essential property is that the log is written before the data structures it describes are updated, so that at every instant the log is a superset of the durable state. A crash can lose anything that exists only in memory, but it cannot produce a durable structure that the log does not also describe, and that asymmetry is what makes replay possible.

What the log stores

A log record contains enough to reconstruct the mutation: for an add, the document id and the raw source fields, because re-tokenizing the raw document is cheaper than logging the postings themselves; for a delete, the document id or the delete-by-query predicate. The record does not need to store the derived postings, because those are re-derivable by re-running the index pipeline, but it must store the raw input, which is the only thing that cannot be reconstructed.

Storing the raw source rather than the postings is a size-versus-work trade. The raw source is usually smaller than its postings would be, because a long document’s postings include positions for every token, but replaying it requires re-running the analyzer and the full add path. Storing the postings would make replay a pure copy but would bloat the log to the size of the index delta. Most systems choose the raw source and accept a longer replay, because crashes are rare and replay cost is paid only then, while log size is paid on every write forever.

The sequence number on each record is the recovery anchor. The log records mutations in the exact order they were accepted, and the sequence number lets recovery determine which records are already reflected in the segments and which are not. A record is only safe to discard once its effects have been written into a committed segment, which is the event that truncates the log.

The commit and the truncate

A commit, or full flush, is the operation that makes the in-memory buffer durable as segments and then declares the log obsolete up to a point. The commit syncs the newly flushed segments to disk, records which segment generation is now durable, and then truncates the log to remove every record whose effects are now in those segments. After the truncate, the log holds only the records for mutations that arrived since the last commit, which keeps it small.

The ordering of these steps is the entire correctness argument. The segments must be synced before the log is truncated. If the log were truncated first and the machine crashed before the segments synced, the mutations would exist in neither the segments nor the log, and they would be lost. The sync-then-truncate order guarantees that at every instant, every durable mutation is in at least one of the two places.

Replay after restart

Recovery starts from the last committed segments, which are durable and complete, and replays the log from the point after the truncate. Each record is applied in sequence-number order: adds are re-indexed into a fresh buffer, deletes are re-applied as tombstones. At the end, the index is in the same state it was in before the crash, modulo any records that were accepted but never durably logged, which are lost by design.

Replay is idempotent only if the records carry enough information. A delete-by-query record replays the predicate, not the result set, so replay re-resolves it against the recovered index; if the predicate is time-dependent or the source query is no longer reproducible, replay can diverge from the original. This is why some systems log the resolved document id set for delete-by-query rather than the predicate, trading log size for replay fidelity.

Replay also interacts with the document id counter. The ids issued by the add path are monotonic, and recovery must restore the counter to its pre-crash value or the next add will reuse an id already held by a recovered document. The counter is therefore either reconstructed from the highest id seen during replay or, more simply, logged as part of the commit record, so that after a commit the counter is durable and replay only needs to account for the records after it.

The fsync and its cost

The performance of the whole design hinges on how often the log is fsynced. An fsync per document is fully durable but slow; an fsync per batch is fast but leaves a window where a crash loses the un-synced tail. Systems expose this as a durability setting: a durable mode that fsyncs every record, and a faster mode that fsyncs on a timer or a size threshold, accepting loss of the tail on a crash. The difference is not correctness, but the length of the window: a one-second sync interval means a crash can lose at most one second of accepted documents.

The reason an fsync is so much more expensive than the write it flushes is that it forces the storage device to move its volatile cache to the persistent medium, which on a spinning disk means waiting for a platter rotation, on the order of milliseconds, and on flash means programming cells, which is fast but still far slower than the page-cache write that preceded it. Batching many appends behind one fsync amortizes that fixed cost across the batch, so throughput rises with batch size while the loss window widens in proportion. This is the same throughput-versus-durability dial that a database’s transaction log exposes, and it is the single most important operational choice a search operator makes about data safety.

The write-ahead log is the reason a search system can honestly claim to have indexed a document that is still sitting in RAM. The segments give it speed, the refresh gives it visibility, and the log gives it the one thing neither of those provides: a guarantee that the document survives the machine dying.