On-disk format, version 3

pkg/engine/segment.go, pkg/engine/seek.go, pkg/engine/ivf.go and pkg/engine/persist.go are what the bytes actually obey. Where this document and those files disagree, the document is wrong.

Milestone 2 wrote version 1; milestone 3a replaced it with version 2; milestone 3b appended one section and made it version 3. It is written down because a format is the one thing in weft that cannot be quietly rewritten — code is replaceable, a file on a user’s disk demands a migration.

Versions 2 and 3 are both read. Version 1 is refused, not migrated. Open reports ErrBadVersion for v1. That reason is not technical: weft has no users, and the only v1 directory that existed was rebuildable from its sources. That argument rests on a user count and is therefore available exactly once — D-007 records it, and §7 says what it obliged version 3 to bring instead.

What version 3 brought is the reader, not a converter. v3 is v2 plus the ivf section and nothing else, and the fallback a segment without a partition needs — every id is a candidate — is the same one a pending segment and a segment below 16,384 documents already need. So reading v2 costs a branch that had to exist anyway. Index.Merge is the only thing that upgrades one: it rewrites the run it collapses with the current writer, so no migration command and no rebuilt directory is needed. What it is not is automatic — Merge does nothing below nine segments, weft never calls it for the caller, and past the ceiling it rewrites only the oldest run. A v2 index of one to eight segments therefore stays v2 for as long as nobody adds to it, and answers vector queries with every id as a candidate. That is exact and slow, which is the whole reason the reader was affordable; it is not a background upgrade.

What v1 could not express, and why the change was bytes rather than code: its docs section was a bare run of variable-length records and its key map was derived by reading all of them, so neither a DocID nor a Key could reach its document without decoding every document in front of it. No arrangement of a lazy reader fixes that.

1. Directory layout

dir/
  MANIFEST              the only entry point; one atomic rename publishes a commit
  seg-000007/           one generation, immutable once the manifest names it
    meta                collection statistics — the BM25 snapshot
    docs                every document, in DocID order
    postings            the term dictionary, block-structured
    terms               term → absolute offset into postings
    docoff              DocID → (offset into docs, token count)   ← v2
    keys                sorted Key → DocID                        ← v2
    ivf                 centroids + inverted lists                ← v3

The version decides the section list. A v2 segment has six files, a v3 segment has seven, and every frame inside one segment must declare the same version. A v3 segment missing ivf is damage, not an older segment; a v2 segment with an ivf file beside it has a file nothing names. meta is opened first for exactly this reason — its frame is what says which list applies.

A commit writes one segment holding what was added since the last commit, and leaves the previous generations’ files untouched. A segment stores ids local to itself, counting from zero, and the manifest says where it sits in the index — so a segment’s bytes do not depend on what was committed before it, which is what lets an old generation survive a new one byte for byte.

Index.Merge collapses the oldest run of segments into one when the count passes eight. Merging adjacent segments is concatenation: every document keeps the id it had, so nothing is renumbered. That is not a convenience — engine.TopK breaks ties on DocID, so a merge that moved ids would move rankings.

The manifest storing a list is version 1’s doing, from D-003. Incremental commit extends its contents and not its shape, which is the one thing about v1 that survived contact with this milestone.

A segment directory the manifest does not name does not exist. Nothing reads it, and Commit deletes it on its way past. Open leaves it alone: “unnamed” is also true of the segment a commit still in flight has written but not yet published, so a reader that swept would delete a live writer’s work.

2. File frame

Every file, the manifest included, wears the same frame:

kind is 1 meta, 2 docs, 3 postings, 4 terms, 5 manifest, 6 docoff, 7 keys, 8 ivf. It exists because a checksum tells intact bytes from damaged ones and nothing more: without a kind byte, a healthy docs file copied over meta would be parsed rather than refused.

Readers verify in this order, and the order is deliberate:

1. magic — a file that was never weft’s reads as corrupt, not as a version problem.
2. checksum — so a flipped bit in the version byte cannot masquerade as a version mismatch.
3. version — checked only once the bytes are known intact.
4. kind — catches an intact file standing at the wrong path.

Open skips step 2, and Scrub is where it went. The frame checksum covers every byte of a file, so computing it costs a full read — the cost lazy loading exists to remove. One consequence follows and is not hidden: on the Open path a damaged version byte reports ErrBadVersion rather than ErrCorrupt, because nothing has told the reader those bytes are damaged. Scrub runs all four steps in order and calls it corruption.

Unit checksums

Each docs record, each postings block and each terms entry carries its own CRC-32C, four bytes, immediately after it. A reader that touches one unit verifies one unit, which is what makes lazy reading and integrity compatible.

Every unit checksum is seeded with what names the unit — a DocID for a record, its own absolute file offset for a block, its index for a terms entry — folded in as eight little-endian bytes before the unit’s own content. The seed is the part that matters. A document record does not carry its DocID; its position did, and docoff is what turns an id into that position. Trust the table and one damaged entry yields a healthy record decoded under someone else’s id — a plausible wrong answer rather than an error. Binding the id in makes the record prove which document it is.

The frame checksum still covers the unit checksums, so Scrub catches damage anywhere including in the checksums themselves.

segHeaderLen is 6 (4 + 1 + 1). The terms index stores absolute file offsets, so this constant is part of the format, not an implementation convenience.

3. Primitives

• uvarint / varint — encoding/binary. Unsigned for counts, lengths, ids and frequencies; signed for Unix seconds, which are negative before 1970.
• string — uvarint byte length, then the raw bytes. UTF-8 is never assumed; keys and text round-trip as bytes.
• float32 — 4 bytes, little-endian IEEE-754 bit pattern.

4. Sections

MANIFEST

generation      uvarint     strictly increasing; a write names its directory from it
segment count   uvarint
  segment name  string      e.g. "seg-000007"
  base          uvarint     the first DocID this segment owns
  count         uvarint     how many documents it holds

The bases must tile [0, total) contiguously and in ascending order. A list that did not would give two segments overlapping ids, and a reader would answer with whichever it walked into first — a wrong document, not an error — so this is checked while the list is read rather than afterwards.

Some published segment must be named for the current generation, and none may be named for the next one: each write clears seg-<gen+1> before using it, so a manifest already naming it would aim that removal at live data. Version 1 could say something stronger — the last segment is the generation’s — because a commit published exactly one; a merge publishes its result at the front, since it replaces the oldest run.

Segment names come off disk and are therefore validated, not trusted: a name must start with seg-, contain no path separator, and equal its own basename. A manifest naming seg-../../etc is refused rather than followed.

meta

document count  uvarint     ≤ 2³²−1, the DocID ceiling
total length    uvarint     Σ document token counts
vector width    uvarint     0 when no document carries a vector

These three are the collection statistics BM25 reads, written under the same read lock as the documents, so a commit is a point-in-time snapshot with its statistics intact (FINDINGS §4.4). Open cross-checks all three against the docs file and refuses a segment whose meta disagrees with its own documents.

docs

document count  uvarint
per document:
  key           string      unique, non-empty
  text          string
  token count   uvarint     stored, not recomputed
  vector width  uvarint     0, or the corpus width
  vector        float32 × width
  link count    uvarint
  link          string × count
  time seconds  varint      Unix seconds
  time nanos    uvarint     0 … 999,999,999

Four decisions here are load-bearing:

• DocID is positional. A document’s index in this file is its DocID, so the id is never written and cannot contradict itself.
• Token count is stored, not recomputed from the text at load. Recomputing would let a future change of tokenizer silently disagree with the postings the segment already holds.
• Links are keys, not DocIDs (FINDINGS §4.2). Lazy resolution is what makes forward references and dangling edges free, and milestone 4’s evaluation joins an external citation graph by key.
• Time carries no presence flag. The zero time.Time’s own Unix seconds decode back to a value that IsZero again, so “no timestamp” — which the recency scorer reads as “no opinion” — survives by arithmetic rather than by convention. The zone is dropped; a restored time is the same instant in UTC, and instants are all any scorer reads.

postings

term count      uvarint
per term (in the terms index's order):
  block count   uvarint
  per block:
    posting count uvarint    = 128 except in the last block
    maxDocID      uvarint    last DocID in this block
    maxTF         uvarint    highest term frequency in this block
    minDocLen     uvarint    shortest document in this block
    per posting:
      DocID       uvarint    absolute for each block's first posting, then a delta ≥ 1
      frequency   uvarint    ≥ 1, and ≤ the document's token count

Delta chains stop at the block boundary. Every block’s first DocID is absolute, so a block can be decoded without its predecessors — which is the entire point of the metadata below, since a skipper that had to decode every preceding block to learn where this one starts would be skipping nothing. It costs at most three bytes per block, and retrofitting it would cost a format migration.

Term strings are not in this file — they live in the terms index, and entries are located by the offsets recorded there.

maxDocID, maxTF and minDocLen are D-001: everything block-max WAND needs, written from the start because retrofitting them is a migration while writing them costs three varints per block. No query reads them before milestone 5. They are re-derived from each block’s contents and compared on every Open, which is what stops an unread field from rotting.

Block size 128 is convention from the block-max WAND literature, not a measurement — marked ponytail: in the source.

terms

term count      uvarint
per term:
  term          string       strictly ascending
  offset        uvarint      absolute file offset of the term's postings entry

This is milestone 3’s seek structure and no query uses it yet. It is nevertheless load-bearing today: the postings file holds no term strings, so a segment cannot be read without it. That is deliberate — an index nothing reads is an index that rots, and this one cannot.

docoff (v2)

document count  uvarint
  offset        uint64 LE   absolute file offset of the record in docs
  token count   uint64 LE   the same number the record itself carries

Fixed width, sixteen bytes an entry, and that is the whole point: entry i is at a computable position, so Doc(id) is arithmetic plus one record decode. A uvarint table would have to be walked from the front, which is the cost being removed.

Eight bytes for the offset rather than four, because a 656 MB docs file already sits one order of magnitude from a uint32 ceiling and raising it later is a migration. The token count rides along rather than being read out of the record, because BM25 asks for a length once per posting and reaching it through the record would make every posting cost a key, a text and a vector.

The record carries the length too, and the two are compared — a copy nobody checks is what D-001 is about.

keys (v2)

key count       uvarint
  offset        uint64 LE      absolute file offset of the entry, in key order
  (reserved)    8 bytes        written zero; the table shares docoff's 16-byte width
  key           string         the entries themselves, ascending
  document id   uvarint        segment-local

The reserved half is padding, not a field: the table reuses docoff’s entry width and has no token count to put beside the offset. Eight bytes a document, kept because the width is on disk — narrowing it belongs to a version bump, not to a reader that would then disagree with every v2 index already written.

The offset table makes Resolve a binary search rather than a map rebuilt by reading every document. Ascending order is what the search rests on, so an unsorted table does not fail — it answers wrongly — and the decoder checks it.

Offsets are computed forward rather than patched back in: an entry’s encoded length is known from the key and the id, and the table’s own size from the count. A writer that had to seek backwards could not stream, and merge cannot buffer a corpus.

ivf (v3)

list count      uvarint     nlist; 0 means no partition, and then dim is 0 too
centroid width  uvarint     dim; must equal meta's vector width
  centroid      float32 × dim, LE, L2-normalized      × nlist
  member count  uvarint                                × nlist
  list offset   uint64 LE   absolute file offset       × nlist
per list, in list order:
  DocID         uvarint     absolute for the first, then a delta ≥ 1
  checksum      4           CRC-32C seeded with the list's own number

An IVF-flat partition of the segment’s vectors: spherical k-means centroids, and the segment-local DocIDs assigned to each. Index.Nearest ranks the centroids by inner product with a query, reads the best nprobe lists, and returns their members as the documents worth scoring exactly. No score is stored and none is computed here — the metric belongs to the caller, which is D-008.

Four decisions here are load-bearing:

• The section is always written, nlist = 0 when the segment holds fewer than 16,384 documents or no vectors. A section list that varied with the corpus would make the rejection table above say “may or may not be here”, and every reader and the first-commit ownership check would have to know which. nlist = 0 means every id in the segment is a candidate — with one exception, and it is a different case rather than a fourth spelling of this one: a segment whose meta claims no vector width at all contributes no candidates, because a scorer skips a document with no vector before it compares widths, so those ids can produce neither a score nor a width-mismatch error, only a decode of every record in the segment.
• Spherical, not plain L2. Vectors are normalized before training and the assignment maximizes an inner product. Ranking is by cosine, and partitioning by raw L2 would gather the documents with the largest norms into one list regardless of direction — losing exactly the neighbours a cosine query wants.
• The offset table is fixed width, for the reason docoff’s is: a query probes a few lists out of up to a thousand, and reaching list j through a uvarint table would mean decoding the j−1 lists in front of it, which is the corpus. At eight bytes an entry it is at most eight kilobytes. Offsets are computed forward, never patched back in, so the writer still streams.
• Each list’s checksum is seeded with its own number. A list carries no copy of which centroid it belongs to, so a reader following a damaged offset would decode a healthy list under the wrong centroid. That is not an error, it is a plausible wrong candidate set — and a wrong candidate set is indistinguishable from ordinary recall loss, which is the one failure an approximate index must not be allowed to hide.

nlist is min(⌈√count⌉, 1024), from the document count rather than the vector count — and then clamped once more to the number of vectors training actually sampled, because k-means with more centroids than points has no fixed point. nprobe is a constant 64 and is not configurable; Nearest raises it on its own when a query would otherwise return fewer than k candidates, so “at least k” is a contract rather than a tuning exercise. nprobe is the reader’s policy and is not stored, so changing it needs no rebuild. nlist is the writer’s: it is the section’s first field, and the centroid array and both tables are sized by it, so changing how it is derived rewrites every segment.

Damage in a list costs speed, not availability. A list that fails its own checksum makes the whole segment behave as though it had no partition: every id becomes a candidate, the answer becomes exact, and the query becomes slow. That is D-006’s rule where absence is the safest answer, and Scrub is what names the damage.

5. What a reader rejects

Bytes from disk are a trust boundary. Every failure is an error wrapping ErrCorrupt or ErrBadVersion; none is a panic, and none is an index that looks plausible but breaks an invariant a scorer relies on.

What only Scrub checks. Open verifies the frame header, the manifest and meta, and each unit as it is read. Everything else in the table above — the whole-file checksums, every document, every posting list, both seek tables in full — is Scrub’s. The gap that leaves is real and worth stating: a unit nothing ever reads is never verified, so rot in a document no query reaches sits there until somebody runs Scrub. Milestone 2 got this free because Open read every byte; milestone 3 buys it explicitly.

One thing nothing checks, stated plainly. No reader verifies that every vector-bearing document appears in some ivf list. A document missing from the partition is invisible to a vector query, and the cost of that is recall — the same currency an approximate index spends by design, and not separable from it by any rule available on either path. Buying the check would mean carrying one bit per document out of the docs walk, and the answer it would give is “this index recalls slightly less than it should”, which weft-eval recall measures directly against a brute-force scan.

What a reader deliberately does not check is that a term matches the text of the documents it names: nothing re-tokenizes Text to compare per-document term frequencies. A doctored file can therefore file a document’s postings under a token its text does not contain, and text search will return it for that token. That is accepted, for the same reason docLen is stored rather than recomputed — a segment records what was indexed, not what this build’s tokenizer would index today, and a reader demanding the two agree would refuse every segment written before a tokenizer change. The invariants above are the ones the scorers actually rest on; term-to-text correspondence is not one of them, and buying it would cost a full re-tokenization of the corpus on every Open.

6. Atomicity and durability

Commit writes the segment’s six files, fsyncs each, fsyncs the segment directory, fsyncs the index directory so the segment directory’s own entry is durable before anything names it, then renames a temporary manifest over MANIFEST and fsyncs the index directory again. Syncing only the inside of the segment would leave the rename free to land first, and a manifest naming a directory whose entry never made it is the mixed state the rename exists to rule out.

Guaranteed against process death, on POSIX. The rename is atomic there, so a crash at any point leaves either the previous generation or the new one — never a mix, and never a partly visible segment. A segment written but not yet named by a manifest is indistinguishable from one that was never written.

The guarantee is the platform’s, not weft’s. Go’s os.Rename contract does not promise atomic replacement everywhere it compiles — Windows in particular — and weft calls no platform-specific replacement primitive. Linux and macOS are what milestone 2 claims and what its tests run on; anywhere else the commit point is as atomic as that system’s rename and no more.

Best-effort against power loss. Contents and directory entries are fsynced, but weft uses no platform-specific write barrier (no F_FULLFSYNC on macOS, no device cache flush), and directory syncing is unsupported on some systems, where the error is deliberately ignored. A filesystem that reorders aggressively can therefore still lose a commit that Commit reported as done. Tests pin the process-crash guarantee; the power-loss case is documented, not tested.

Commit refuses to run against a corrupt manifest rather than guessing the next generation, because writing on top of a directory in an unknown state could orphan a commit the caller believes exists.

A first commit has to establish that the directory is weft’s. Commit deletes every seg-* entry it finds — its own target before writing it, the rest in the sweep afterwards — and a manifest is what proves those names are weft’s own debris. With no manifest there is nothing to say that seg-000001 is debris rather than a caller’s directory sitting under a name weft happens to reserve, so Commit aimed at a home or documents directory would recursively delete data it never wrote. The same goes for MANIFEST.tmp, the other name Commit deletes on sight. A commit that crashed before its rename must still be recoverable, so the test is what such a commit leaves behind rather than mere absence: a seg-* entry may exist, but only as a real directory holding nothing but regular section files, and MANIFEST.tmp may exist too — and every one of those files has to carry weft’s magic, because a reserved name and a file type are things a caller’s own data can have by coincidence and four bytes of magic are not. A file the writer created but never filled satisfies that as well: it buffers until close, so its debris is empty or a prefix of the frame. Anything else — a stray entry inside the segment, a directory named meta, which the recursive clearing would take everything beneath, a symlink standing at any of those names, or a file under one of them that weft did not write — and the commit refuses before it mutates anything at all. The magic is the ownership signal and the only one available here: the kind byte says which section a file is rather than whose it is, and a torn write may stop before reaching it. A frame intact enough to carry the magic but broken past it is weft’s own debris, and the reader’s checksum is what refuses it as an index.

One writer at a time. Commit is safe alongside Add and queries — it takes the same read lock a query does — but not alongside another Commit on the same directory. Open performs no deletions and no writes, so opening a directory while it is being committed to cannot damage it; a reader that loses the race against Commit’s sweep of the previous generation sees an error and can retry.

Nothing weft opens leaves the index directory. Commit and Open both work through an os.Root on that directory, so every path below it — segment directories and section files alike — is resolved by the OS with the guarantee that it stays beneath the root. A symlink standing where seg-000007 belongs is refused rather than followed, and the refusal is not a check of weft’s that a rename could race.

Two things that follows from, and one it does not:

• The manifest’s name check and the root do different jobs. seg-000007 is a syntactically perfect name whether the entry standing there is a directory or a link into somebody else’s index; the first question is about the manifest’s bytes, the second about the filesystem.
• The temp manifest is additionally created with O_EXCL, because it sits at a predictable path: without it, a symlink planted at that name would be written through, which is the difference between “can write in the index directory” and “can overwrite any file this process can reach”.
• It is not a claim that the directory’s contents are trustworthy. Somebody who can write there can plant a whole valid segment, and weft would read it — which is why every value in it is validated anyway.

7. Changing this format

1. Unknown versions are refused, never guessed. “Probably compatible” is how a wrong index gets loaded silently.
2. Any change to what the bytes mean bumps formatVersion — a new field, a retyped field, a reordered field, a relaxed invariant.
3. The frame does not change. Magic, version and kind must stay where they are, or a future reader cannot even reach the version in order to reject it.
4. Multiple segments needed no bump, and lazy reading did. The manifest already carried a list and the segment format is per-segment, so incremental commit and merge changed contents rather than shape — D-003 designed for that and it held. What forced version 2 was smaller and inside a single segment: docs was positional and the key map was derived, so neither a DocID nor a Key could reach its document without decoding the corpus.
5. Migration, when it comes, reads the old version and writes the new one. There is no in-place upgrade path.
6. Version 2 skipped that, and no later version may. v1 is refused rather than converted, on the single ground that weft had no users and the one v1 directory in existence was rebuildable. That is an argument about a user count, so it expires the moment somebody has an index they cannot rebuild — D-007. A version 3 owes either a converter or a reader that understands both.
7. Version 3 paid that debt with the reader, and it was nearly free. v3 appends ivf and changes nothing else, and a segment without a partition has to be readable regardless — a pending segment has none, a segment below 16,384 documents has none, and a damaged partition is treated as none. So “v2 is a segment with no partition” reuses a branch that already existed, where a converter would have been a command, a rebuild, and a directory in two states while it ran. Merge upgrades whatever run it collapses, but it only fires past nine segments and only on the oldest run, so a small v2 index is not upgraded at all — it is read, which was the debt. The lesson for version 4 is the one that made this cheap: append a section rather than changing one, and the old version stays readable by construction. A version that retypes or reorders an existing field gets no such discount and owes the converter.

8. Known limits