Searching by meaning: vector databases and retrieval · 06 / 08

Making the index durable

An index living in RAM vanishes on restart. How do you write it to disk once and for all, without ever corrupting it, even if power cuts out mid-insertion?

In the previous chapter, we earned the right to trust an index: the differential oracle certifies that it really retrieves the neighbors it claims to return. But that index, carefully built and verified, lives in RAM. And RAM is wiped on the slightest restart. Rebuilding an index of several million vectors takes hours of computation. The question of this chapter is therefore down-to-earth, and yet it decides the survival of the engine: how do you write that index to disk once and for all, read it back intact, and survive a power cut that strikes mid-write?

This is a change of world. Until now we reasoned in geometry, distances, recall. Now we reason in bytes, faults, guarantees. And we will discover a sneaky threat, a direct cousin of the one in chapter 5: a saved index can be read back without the slightest apparent error, and still lie about its content.

An index that does not survive a restart

An in-memory index is volatile by nature. Cut the power, kill the process, restart the machine: everything is lost. For a state to survive, it must be made durable , meaning written to a medium that retains its value without power (a disk, an SSD), and with assurance that the write truly reached that medium.

One might think this is trivial: just open a file and dump the index into it. That is exactly where the trap hides. Writing data takes time, and during that time, anything can happen. The machine can go down in the middle of the operation. And an interrupted write does not leave a clean empty file: it leaves a half-written file.

The real danger: the torn write

Imagine your index occupies ten blocks on disk. You launch the save, which rewrites those ten blocks one by one. The machine shuts off after the sixth. On disk, you now have six new blocks and four old blocks, welded into the same file. That is a torn write , and it is the nightmare of any persistence layer.

The trap is not data loss. Loss, we know how to handle: just rebuild everything. The trap is silent corruption. That hybrid file opens without error. Its header is consistent, its first records read perfectly. It looks valid. But its internal pointers cross the boundary between old and new, and the index we reload is an incoherent monster that will return nonsensical neighbors without ever raising an exception.

You recognize the pattern. In chapter 5, an index could pass every local test while collapsing in quality. Here, a file can pass every open-time check while being structurally rotten. The same lesson, transposed: what looks correct on the surface can be wrong underneath.

Four strategies for writing without tearing

Faced with the torn write, engineering has invented several defenses. Here are four, plus the naive approach that serves as the counter-example. Each makes a different trade-off between safety, write cost, read-back speed, and data freshness.

Strategy	Crash-safe?	Write cost	Read-back	Freshness
In-place overwrite	No: torn write	Low	Immediate	Maximum
Atomic rename	Yes: all or nothing	Full copy	Immediate	Maximum
Snapshot	Yes: all or nothing	Full copy	Immediate	Behind between two snapshots
Append-only log	Yes: consistent prefix	Low, incremental	Needs replay	Maximum
Memory-mapped file	At the OS’s mercy	Very low	Immediate	Maximum

In-place overwrite is the naive strategy: the final file is rewritten directly. Fast and simple, but it is precisely the one that tears. The four others each correct it in their own way.

The atomic write via rename writes the new index into a temporary file alongside the original, without touching it; once the temporary is complete and flushed to disk, a rename publishes it in one move. The snapshot does the same with a full, periodic copy of the state. The append-only log never rewrites anything: it appends each change to the end of a file, so a crash can only damage the last record, which is truncated on read-back. The memory-mapped file lets the operating system manage the flow between memory and disk, elegant but with durability that depends on when the system decides to flush its pages.

The key: atomicity through rename

Of these four defenses, one deserves a closer look, because it is the most universal and the most instructive: the atomic rename. Its idea unfolds in three steps.

First, the entirety of the new index is written to a temporary file, separate from the official file. During all that time, the official file remains the old index, complete and intact: if the machine goes down here, we only lose the half-written temporary, with no consequence. Next, we call fsync on the temporary to guarantee it is truly on disk, not merely in a cache that a crash would erase. Finally, we rename the temporary over the official file.

That last gesture is the secret. At the filesystem level, the rename is atomic: there is no instant where the index name points to a half-replaced file. At every moment, it designates either the complete old file or the complete new one. The “halfway” is made impossible by construction.

write(temp) then fsync(temp) then rename(temp to official)

The write-temp-then-rename pattern

This is what text editors that never corrupt your file, embedded databases, and most serious tools do under the hood. The same technique turns a dangerous write into an all-or-nothing transition.

Reading back and demanding identical: the round-trip oracle

Suppose the index was correctly written, with no crash. Are you safe? Not yet. There remains a second way to lie, and it has nothing to do with crashes: serialization itself can betray you.

Serializing is transforming an in-memory structure into a sequence of bytes for disk. Deserializing is the reverse. We would like these two operations to be exactly reciprocal: reading back what we just wrote must return the starting state, byte for byte. But it is easy to break. A vector of floats written with too little precision comes back rounded, hence different. A set of neighbors written in an unstable order comes back in a changed order, hence different bytes from one write to the next.

Hence the round-trip test : we serialize the state, reload it, and demand that the result be identical to the original. That is, word for word, the differential oracle of chapter 5, transposed to persistence. The reference is no longer the slow exact index: it is the in-memory state. The tested version is no longer the approximate index: it is what we reload from disk.

And the trap of chapter 5 returns too. A logical check, which verifies that we have the same nodes and the same neighbor sets, stays green even when the neighbor order has changed: logically, it is the same. Only a byte-for-byte comparison against a canonical reference catches this instability. The logical check is blind where the strict oracle sees. Local property versus global truth, once again.

Your turn: crash the machine

The component below brings together the two dangers of this chapter. At the top, choose a persistence strategy and slide the crash instant along the write plan: observe what the read-back recovers depending on where the machine goes down. At the bottom, the round-trip oracle: activate the serialization bugs and watch the logical check stay green while the byte-for-byte comparison turns red.

Persistence strategy

Crash the machine

Crash moment 0 / 8

Slide to cut power after N operations have executed.

Write plan

write block 0 to the indexnot reached
write block 1 to the indexnot reached
write block 2 to the indexnot reached
write block 3 to the indexnot reached
write block 4 to the indexnot reached
write block 5 to the indexnot reached
write block 6 to the indexnot reached
fsync: flush the index to disknot reached

After restart

Old index intact: write lost, but consistent

Reloaded index : 4 nodes

Round-trip oracle

Serialize, reload, compare to the in-memory state.

Logical check (same sets)green
Byte-for-byte oraclegreen

The logical check stays green where the byte-for-byte oracle sees the corruption.

Three questions to ask yourself while playing:

Choose in-place overwrite and place the crash in the middle. What verdict? Try again with atomic rename at the same point. Why does one tear and not the other?
With the append-only log, move the crash record by record. Do you ever see “corrupted” appear? What do we recover instead?
In the oracle section, activate the unstable neighbor order alone. Does the logical check turn red? And the byte-for-byte oracle? Which of the two would have let the bug reach production?

Exercises

Solution to exercise 1: tracing a crash, strategy by strategy

An index moves from an old state of 3 blocks to a new state of 5 blocks. The machine goes down just after 2 blocks have been written. What do we recover depending on the strategy?

Step 1. In-place overwrite. The 2 new blocks were written directly over the official index. The file now contains 2 new blocks followed by old blocks: a mixture.

\text{disk} = [\,\text{new}_0,\ \text{new}_1,\ \text{old}_2,\ \dots\,]

Partial result. Incoherent mixture: corrupted. This is the only strategy that tears.

Step 2. Atomic rename. The 2 blocks were written into the TEMPORARY file. The rename has not taken place (it is the final step). The official index has not moved.

\text{official} = [\,\text{old}_0,\ \text{old}_1,\ \text{old}_2\,]

Partial result. Complete old index: intact, write simply lost.

Step 3. Append-only log. We appended 2 new records to the end of the log. Read-back replays the old state plus these 2 additions, a perfectly consistent prefix.

\text{reloaded} = \text{old} + [\,\text{append}_0,\ \text{append}_1\,]

Result. Behind but consistent, never corrupted. Three strategies, three outcomes: only in-place overwrite produces a torn file.

Solution to exercise 2: why the logical check misses the ordering bug

We serialize a node whose neighbors in memory are the list $[1, 2]$ . A bug writes the neighbors in reverse order, $[2, 1]$ . We want to know which of the two checks catches the bug.

Step 1. The logical check. It compares the SETS of neighbors, without taking order into account.

\{1, 2\} = \{2, 1\}

Partial result. The sets are equal: the logical check stays green. It sees nothing.

Step 2. The byte-for-byte oracle. It compares the string actually written to the canonical reference, which sorts neighbors in ascending order.

\text{written} = \texttt{"2,1"} \neq \texttt{"1,2"} = \text{reference}

Result. The bytes differ: the oracle turns red. It is the oracle, and it alone, that would have prevented the bug from reaching production. Exactly as in chapter 5, the local property (same neighbors) is satisfied while the strict truth (same bytes) is violated.

In one sentence

An in-memory index only becomes durable once written to disk, and writing it naively over the old file exposes it to a torn write, a silent corruption neutralized by atomicity (write alongside then rename in one move, or append only at the end of a log); and as in chapter 5, only a byte-for-byte round-trip oracle, not a simple logical check, guarantees that what we reload is exactly what we had in memory.

Quiz

1. Why is a torn write more dangerous than a simple data loss?
2. How does atomic rename prevent a torn write?
3. A bug writes neighbors in an unstable order. Which check catches it?

Towards chapter 7

The index is now durable and verified: it survives restarts and we can prove we reload it faithfully. But it is still missing something. All the search we have built rests on MEANING, captured by vectors. Yet there are queries where meaning is not enough: an exact reference number, a rare proper noun, a keyword that must appear verbatim. Vector search, brilliant on paraphrases, can miss an obvious literal match. Chapter 7 therefore marries our vectors to the lexical world, that of exact words at BM25, to build a hybrid search that looks for both meaning and letter.

Sources

Haerder, T. & Reuter, A. (1983). “Principles of Transaction-Oriented Database Recovery.” ACM Computing Surveys 15(4), 287-317. DOI 10.1145/289.291
Pillai, T. S., Chidambaram, V., Alagappan, R., Al-Kiswany, S., Arpaci-Dusseau, A. C. & Arpaci-Dusseau, R. H. (2014). “All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications.” OSDI. USENIX
O’Neil, P., Cheng, E., Gawlick, D. & O’Neil, E. (1996). “The Log-Structured Merge-Tree (LSM-Tree).” Acta Informatica 33(4), 351-385. DOI 10.1007/s002360050048

Going further

Documentation for redb, an embedded transactional key-value store in Rust: redb.org