What makes a dumped index and a dumped set of records provably the same KB.
The index is derived from the records, so an index dump is only valid against the records it was derived from. Nothing downstream can notice when it is not: a stale trie node simply reports fewer handles and a query returns fewer results — no exception, no warning, just a KB that quietly knows less. So the writer records a fingerprint over the records and the reader recomputes it while storing them; a mismatch discards the index and rebuilds.
A sum, not a chain. The digest is the sum (mod 2⁶⁴) of a per-record hash, so it is commutative — the reader accumulates it in whatever order the frames arrive, which is not the order the writer walked — and additive rather than xor, so two identical records cannot cancel each other out.
What is hashed is what the index is a function of: the handle, :sentence,
:context, :truth, and a rule's :antecedent / :consequent. sentex/path,
kv/root-keys, kv/sentex-terms and the rule index read exactly those, and the handle
because a posting is a set of handles — the same content at a different handle makes
every posting naming it wrong. Deliberately not hashed: :strength, :varmap,
:direction, :defeasible. None of them changes a single index entry, so a dump
differing in one of them still has a valid index, and hashing them would make the cache
go unused for a reason that is not a reason. (:strength also arrives after the
storing pass — a premise mark is applied once every record is down — so hashing it
would cost the second pass over the records this exists to avoid.)
The hash is FNV-1a over the fields' own hash values: cheap, deterministic across
runs, and strong enough for the question being asked, which is whether two sets of
records are the same — not whether an adversary can forge one. A dump is not a
trust boundary; if it were, this would be a real digest and signed.
Two granularities, one rule. of-records hashes what a record says, and needs
the record — which is what a dump's reader has in hand anyway. of-slots hashes
where each record is: (id, offset, length) off the idx, no frame decoded and no
record fetched. The mapped index snapshot (vaelii.impl.disk.index-snapshot) is
checked with that one, because an image exists to make an open cost bytes read rather
than records read, and a content digest would put every record back on the open path.
It is the coarser hash in one direction and the finer one in the other: it cannot see
a record rewritten to the same bytes at the same offset (nothing can produce that),
and it does see a rewrite the index does not care about — a premise mark, or a
compaction moving every frame — so a snapshot is discarded and rebuilt after one.
Both directions are safe, because a discard is always legal for derived state.
What makes a dumped index and a dumped set of records provably the same KB. The index is derived from the records, so an index dump is only valid *against the records it was derived from*. Nothing downstream can notice when it is not: a stale trie node simply reports fewer handles and a query returns fewer results — no exception, no warning, just a KB that quietly knows less. So the writer records a fingerprint over the records and the reader recomputes it while storing them; a mismatch discards the index and rebuilds. **A sum, not a chain.** The digest is the sum (mod 2⁶⁴) of a per-record hash, so it is commutative — the reader accumulates it in whatever order the frames arrive, which is not the order the writer walked — and *additive* rather than xor, so two identical records cannot cancel each other out. **What is hashed is what the index is a function of**: the handle, `:sentence`, `:context`, `:truth`, and a rule's `:antecedent` / `:consequent`. `sentex/path`, `kv/root-keys`, `kv/sentex-terms` and the rule index read exactly those, and the handle because a posting *is* a set of handles — the same content at a different handle makes every posting naming it wrong. Deliberately **not** hashed: `:strength`, `:varmap`, `:direction`, `:defeasible`. None of them changes a single index entry, so a dump differing in one of them still has a valid index, and hashing them would make the cache go unused for a reason that is not a reason. (`:strength` also arrives after the storing pass — a premise mark is applied once every record is down — so hashing it would cost the second pass over the records this exists to avoid.) The hash is FNV-1a over the fields' own `hash` values: cheap, deterministic across runs, and strong enough for the question being asked, which is whether two sets of records are *the same* — not whether an adversary can forge one. A dump is not a trust boundary; if it were, this would be a real digest and signed. **Two granularities, one rule.** `of-records` hashes what a record *says*, and needs the record — which is what a dump's reader has in hand anyway. `of-slots` hashes where each record *is*: `(id, offset, length)` off the idx, no frame decoded and no record fetched. The mapped index snapshot (`vaelii.impl.disk.index-snapshot`) is checked with that one, because an image exists to make an open cost bytes read rather than records read, and a content digest would put every record back on the open path. It is the coarser hash in one direction and the finer one in the other: it cannot see a record rewritten to the same bytes at the same offset (nothing can produce that), and it *does* see a rewrite the index does not care about — a premise mark, or a compaction moving every frame — so a snapshot is discarded and rebuilt after one. Both directions are safe, because a discard is always legal for derived state.
(accumulator)A mutable fingerprint accumulator: (acc h sx) folds one record in, (acc) reads
{:count n :max-handle h :digest d}. Mutable because it is folded inside the storing
loop — the one pass over the records a reader gets — and single-writer like everything
else here.
A mutable fingerprint accumulator: `(acc h sx)` folds one record in, `(acc)` reads
`{:count n :max-handle h :digest d}`. Mutable because it is folded inside the storing
loop — the one pass over the records a reader gets — and single-writer like everything
else here.(of-records store sentex-ids get-sentex)The fingerprint of every sentex in store, by walking it — what the writer records.
A reader never calls this: it accumulates while storing instead, since a second pass
over the records to validate a cache would cost more than the cache saves.
The fingerprint of every sentex in `store`, by walking it — what the *writer* records. A reader never calls this: it accumulates while storing instead, since a second pass over the records to validate a cache would cost more than the cache saves.
(record-hash h sx)A 64-bit hash of the sentex sx stored at handle h — its identity for the purpose
of deciding whether an index still describes it. See the namespace docstring for what
is in it and what deliberately is not.
A 64-bit hash of the sentex `sx` stored at handle `h` — its identity for the purpose of deciding whether an index still describes it. See the namespace docstring for what is in it and what deliberately is not.
(slot-accumulator)The same accumulator over slots rather than records: (acc h offset length) folds one
in, (acc) reads the same {:count :max-handle :digest} shape. Commutative and
additive for the same reasons.
The same accumulator over slots rather than records: `(acc h offset length)` folds one
in, `(acc)` reads the same `{:count :max-handle :digest}` shape. Commutative and
additive for the same reasons.(slot-hash h offset length)A 64-bit hash of one idx slot — the handle and where its frame lies. A record rewritten in place gets a new frame at a new offset, so this moves whenever the record at a handle does, without the frame being read.
A 64-bit hash of one idx slot — the handle and where its frame lies. A record rewritten in place gets a new frame at a new offset, so this moves whenever the record at a handle does, without the frame being read.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |