File format

The reasons for each exception to the plain layout are worth knowing before you touch the reader; the sections below give them.

A sparse vector's indices are written as gaps because a SPLADE vector's sit close together, and a small gap takes a byte.

A crash in the middle of an append leaves the last record cut short, in its header or its body: the open loads everything before it and cuts it off the file, so there is no separate recovery step after a crash.

On Linux a sync goes to <file>.sync beside the file: a log of fixed size holding what the file took since its last own fsync. An fsync of a file that grew commits ext4's journal as well, 356 us against 65 for bytes written where the file already reached, so a durable write syncs the log and the file is synced once the log is full. An open writes back into the file what the log holds and the file lost, before it reads it, then wipes the log's header; an entry carries a hash and the log names the file it was written for (its inode, and a hash of the bytes before the log's start), so an entry cut short ends it and a log beside another file -- one a restore or an import renamed into the place -- is ignored. A clean close syncs the file and removes the log. A tool that only reads the file (fenec types) applies none: after a power loss, open the database before you copy or inspect it. The file's format is the same with it or without.

It is derived data, not a cache. On open, the version, the dimension, the precision and the link bounds are validated, and the live nodes against the documents: every one's document has to hold a vector, and every document holding one has to have a node. If any of it does not hold, the record is ignored and the index is rebuilt from scratch. A corrupt or stale graph therefore cannot cause data loss.

It is written during snapshot, compact and checkpoint, and a server appends one to the file's tail now and then (below) — never on the normal write path. What it stores is the links, not the vectors: the vectors are already in the document records, and the expensive part is the build. The exception is a tombstone, the node a deleted or rewritten document leaves behind until compact: it still routes searches, but its document is gone or holds another vector, so the record carries the vector the node was linked with.

The graph is restored where its last record is, against the documents as they stood there: a checkpoint's image holds one after each collection's data. Everything after that point is applied to it the way the write path applied it: the node of each document written since is retired, and the vector the document holds now goes in. A crash therefore costs the writes after the last graph, not the graph. An earlier record of the same graph is passed over — the open walks the record heads to find the last one first — since restoring it would read every vector again for nothing.

A server keeps its graphs in the file as they change, since it writes a checkpoint only on its way down: once a graph has changed in 10 000 nodes since it last reached the file, has none waiting to be linked, and the file has grown by three times its record since, it is appended to the tail, the writes held off while it is written. The record holds the whole graph, which is why the growth counts too: a big graph written every few thousand writes would be written over and over for a little of it. It is written in version 6, whose layout is version 5's; a binary that does not know 6 rebuilds the graph rather than restore it against the documents the whole file left, which a vector rewritten after the record would not match. It is not a write: the change counter does not move, no replica is sent it, and a record cut short is cut off the file like any other. The next checkpoint leaves the ones before it out.

A server does not wait for the tail. It opens with the tail's vectors in the arena but in no neighbour list, measures each of them in every near, and links them on a thread beside its queries. A checkpoint written before that is done marks those nodes as waiting: a node's flag byte, 0 for a live node and 1 for a tombstone, is 2 for one, in a graph record of version 5, which is written only then. The next open leaves them waiting again, or links them there when it is not a server's. An older binary does not know version 5 and rebuilds the graph, as it does from any record it cannot read.

A graph over bit codes (quant=bit) also carries the centres its codes are taken from, since a restored graph has to code its vectors against the ones it was built with. Where the quantization's code goes, a bit graph writes 3; the number of centres follows, then each centre as dim little-endian f32s — none while the index still holds its vectors whole. A tombstone's vector is its code: the signs, the centre's number in a byte and two f32s. A bit graph written before the centres, with the vectors' own signs and code 2, is built again on open; a binary from before them does not know 3, and builds its own.

For every kind but the graph that byte is all the file holds: the hash, text, ordered and inverted indexes are built from the documents by the first statement that reads each after an open, so there is nothing of theirs to validate or to go stale — and a binary that splits text another way, as one before runs of characters did, builds its own text index from the same documents. An old binary cannot open a file whose schema uses a newer kind and reports unknown index kind 4, the same refusal as for a record kind it does not know.

An older binary meets a type tag it does not know, or a collation code, and refuses the file, rather than read the field and order it in another order — or, meeting a json field, before it reads an object (value tag 13) it would have no reading of: unknown type tag 14. The value and type tags share their numbers, so 13 and 14 are new to both, where 11 and 12 are a collation's and a dropped place's, and 17 is nocase's: a binary from before it refuses the file rather than compare the field's bytes and take a second spelling its @unique refuses. The collation's weights are not in the file: they are the binary's, and a @sorted index over the field is built from the documents on open.

Record kind 6 sits at the front of the file and is fixed width. Both are deliberate.

At the front, because at the end a corrupt or half-written tail would break opening. The end of the file is exactly where the graph stops, and the graph is derived data — a record that errors out in that region would take that tolerance back.

Fixed width, because the body length is known only after the body is written. A placeholder can be filled in place, whereas a uvarint would mean shifting the whole image.

The body length means "this is where this image's own records end". Every record after it was written after the checkpoint and carries the counter forward. Old files without the record load fine — the counter is then counted from the records. The reverse does not hold: an old binary cannot open a new file and reports unknown record kind 6.

Every write is a block: the documents a put, a set or a del writes, the statements of a /batch or of the browser module's run of several. Their frames are held back until the block ends and are appended as one record, so a crash cuts all of them off the file or none; a block that fails is put back in memory instead, and nothing of it reaches the file. Within one collection the record is a data record of as many frames — the form an image's data records have always had, so a binary from before blocks reads it — and a lone schema change is the record it always was. Across collections, or with a schema change among other writes, it is record kind 9, holding each write's record: a data record, or a create's, a drop's or an index's. A binary from before blocks refuses it with unknown record kind 9, and one from before 10.4 a block holding a schema change as corrupt.

The change counter moves by the writes a record holds, not by one a record: a block of five writes is numbered by its last, and whatever counts records by their numbers — a replica, an archive — counts them that way. A restore to a change inside a block stops before it, since the database never stood there.

Held back until it lands, a block's frames were in memory twice — in the record being built and in the stores — so a load of 250 000 768-dim rows in one command peaked 1.57 GB over what it left. Once a block's frames amount to 16 MB, a server appends them as record kind 10, a spill, whose body is a block record's, and the stores read those documents from the file from then on. The block lands as record kind 11, which names its spills by where their bodies are in the file and how long they are, and holds its writes since the last. A load applies a spill only where a land names it: one that a rollback, a lapsed lease or a crash left is dead in the file, and the ones a file ends with are cut off, as a record cut short is. The land never travels: a replica and an archive are sent the block as the one kind 9 record it would have been. A binary from before spills refuses kinds 10 and 11 as unknown.

Record kind 8 says which history the writes belong to: a list of (id, from change) pairs, one per fork, and whether the file is a replica's. A replica is fed a primary's writes by their number on the change counter, so this is the one record that must not move the counter — a replica would be numbered one change off its primary. It is appended when a history forks or a replica follows one, and written into every image while it is set; a file that never had a replica holds none. An old binary cannot open a file with one and reports unknown record kind 8.

A document id is normally derived from the records: a replay takes one more than the largest id it saw. Compaction throws tombstones away, so that derivation falls short — the highest deleted id disappears from the image entirely and would be handed out again on the next open.

An id coming back silently binds everything still holding it — a link handed out, a row a subscriber holds — to the wrong document. The record is per collection and comes right after the schema. Only snapshot writes it; the append path does not need it, because the tombstones are still there. Old files without the counter still load correctly.

Behind the counter an image writes an index of the collection's data record, which comes right after it: the record's length, the bytes in it that are dead, and each live document's id, payload length and place, each written as its difference from the one before — four bytes a document for records of 590 bytes. A mapped open takes the offset index from it rather than walking the record's frames, whose heads each say where the next one starts: a chain of cache misses that was 5.5 ms of a 14.2 ms open at 100 000 × 128, which opens in 8.4 ms with it. An index that does not fit the record — another length, ids out of order, a payload past its end — is passed over and the record walked. Every reader of the record, older ones included, reads the counter and nothing after it.

A graph holding tombstones is rebuilt by compact from the live vectors: nothing else takes a tombstone out, and every write that changes a document's vector, or deletes it, leaves one. A graph without them is kept as it is.

The rewrite goes to a side file and is renamed, so a half-written checkpoint cannot corrupt the database — and since an image is only ever whole, a record cut short inside it, or an image longer than the file, is refused as a damaged file rather than cut off as a crash's torn tail is. A server's compact writes its image beside the database into <file>.fenec.beside, with no lock held; the documents written meanwhile go into it as a data record at the end of the image, and its header takes the counter as it stands when it is renamed into place. A side file left by a crash is written over by the next compact, and can be deleted.