OverlayKv — a composite KvBackend layering a private writable overlay over a
shared read-only base. Reads resolve overlay-first and fall through to the base;
writes land only in the overlay; the base is never mutated, so N JVMs can share one
frozen base index while each keeps its own fork.
This is the index half of the :overlay backend (the record half is
vaelii.impl.overlay.store), and it is the whole of it. KvIndexStore
(vaelii.impl.kv) writes every index family — the count-aware trie, the context /
functor / argument roots, the rule index, the exception re-check index, the inverted
term index and the term roster — in terms of this protocol and holds no state of its
own, so one decorator here forks the entire index and the trie walker, the matcher, the
planner and the query layers above it are unchanged. That is what the KvBackend seam
was extracted for.
members(K) = (base(K) ∪ overlay(K)) − removed(K), where base(K) is
empty if K carries a tombstone, and removed(K) records the base members this
overlay removed (a base set cannot be edited, so a removal is recorded rather than
applied).kv-increment / kv-decrement seeds the overlay from
the base value, so afterwards the overlay holds base+net and reads are exact. An
untouched counter reads straight through.::deleted-keys shadows the base for
that key. A later kv-add-to-set repopulates it from the overlay only — the base
stays shadowed, which is "deleted, then re-added fresh". kv-put shadows the same
way, because a put replaces a key rather than merging into it.kv-clear! empties the overlay and sets ::cleared, after
which every base key reads absent. That is O(1) rather than a tombstone per base
key, and it is what makes reindex work on a fork: clear the merged index, then
rebuild it from the merged records.Bookkeeping lives in the overlay under reserved keys — ::cleared, ::deleted-keys,
and [::removed K] — namespaced here, so they cannot collide with an index key (every
one of those is a vector tagged with an unnamespaced keyword, or [:term-roster]).
Because the bookkeeping is overlay data, a durable overlay carries it durably and a
remount serves the same merged view with no separate recovery step.
kv-count answers the merged cardinality, never the overlay's. The count-aware
trie is a selectivity structure — plan/order costs every conjunct off count-at, and
provers/est-bindings off the functor root — so a base-blind count would not be a
wrong answer, it would be a silently wrong plan for every query touching inherited
content. kv-intersect merges for the same reason: sentexes-with-args is one set
intersection over the functor and argument roots, and it must see the base's postings
or a fork would stop finding its own inherited facts.
Merging is not the same as building the merged set, and the difference is the cost of
every query plan a fork makes. A key the fork has not touched — no overlay members, no
recorded removal, no tombstone — merges to the base's own value, so inherited? names
that case and kv-count / kv-members hand the base's own answer straight back. Over
a flat-map base the two roads read the same, because its kv-members is a reference
return; over a :dense base, where the posting has to be materialized into a set first,
counting through the merge cost 12.6 ms per call on a 100,000-handle root — a selectivity
read, per conjunct, on a key the fork had never written to. kv-member? is the same
observation at member granularity: exception-rule? probes both sides rather than
merging, which is what keeps the firing-path gate O(1) across the seam.
kv-get is the scalar/counter read and does not merge set values: an overlay value
shadows the base's. No key in the index is read both ways — the trie's counters are
read by kv-get and its handle sets by kv-members — and a backend is free to hold a
posting in a private representation (vaelii.impl.dense-kv returns an IntPostings
here), so merging at this op would mean type-testing another backend's internals.
kv-entries, whose contract is Clojure sets, merges properly.
Single writer. Pure runs one (docs/storage.md). A batch is applied op by op
through this decorator rather than as one atomic step the way MemoryKvBackend applies
it, so the instance lock is held around the whole of kv-batch — an incidental reader
beside the writer then sees a batch whole or not at all, as it does on every other
backend.
`OverlayKv` — a composite `KvBackend` layering a private **writable** overlay over a shared **read-only** base. Reads resolve overlay-first and fall through to the base; writes land only in the overlay; the base is never mutated, so N JVMs can share one frozen base index while each keeps its own fork. This is the index half of the `:overlay` backend (the record half is `vaelii.impl.overlay.store`), and it is the whole of it. `KvIndexStore` (`vaelii.impl.kv`) writes *every* index family — the count-aware trie, the context / functor / argument roots, the rule index, the exception re-check index, the inverted term index and the term roster — in terms of this protocol and holds no state of its own, so one decorator here forks the entire index and the trie walker, the matcher, the planner and the query layers above it are unchanged. That is what the `KvBackend` seam was extracted for. ## The merge model, per key * **Sets.** `members(K) = (base(K) ∪ overlay(K)) − removed(K)`, where `base(K)` is empty if `K` carries a tombstone, and `removed(K)` records the base members this overlay removed (a base set cannot be edited, so a removal is recorded rather than applied). * **Scalars and counters.** An overlay value shadows the base's. A counter is **copy-on-write**: the first `kv-increment` / `kv-decrement` seeds the overlay from the base value, so afterwards the overlay holds base+net and reads are exact. An untouched counter reads straight through. * **Whole-key delete.** A sticky tombstone in `::deleted-keys` shadows the base for that key. A later `kv-add-to-set` repopulates it from the overlay *only* — the base stays shadowed, which is "deleted, then re-added fresh". `kv-put` shadows the same way, because a put replaces a key rather than merging into it. * **Wholesale clear.** `kv-clear!` empties the overlay and sets `::cleared`, after which every base key reads absent. That is O(1) rather than a tombstone per base key, and it is what makes `reindex` work on a fork: clear the merged index, then rebuild it from the merged records. Bookkeeping lives in the overlay under reserved keys — `::cleared`, `::deleted-keys`, and `[::removed K]` — namespaced here, so they cannot collide with an index key (every one of those is a vector tagged with an unnamespaced keyword, or `[:term-roster]`). Because the bookkeeping *is* overlay data, a durable overlay carries it durably and a remount serves the same merged view with no separate recovery step. ## What has to be merged, and why `kv-count` answers the **merged** cardinality, never the overlay's. The count-aware trie is a selectivity structure — `plan/order` costs every conjunct off `count-at`, and `provers/est-bindings` off the functor root — so a base-blind count would not be a wrong answer, it would be a silently wrong *plan* for every query touching inherited content. `kv-intersect` merges for the same reason: `sentexes-with-args` is one set intersection over the functor and argument roots, and it must see the base's postings or a fork would stop finding its own inherited facts. Merging is not the same as *building* the merged set, and the difference is the cost of every query plan a fork makes. A key the fork has not touched — no overlay members, no recorded removal, no tombstone — merges to the base's own value, so `inherited?` names that case and `kv-count` / `kv-members` hand the base's own answer straight back. Over a flat-map base the two roads read the same, because its `kv-members` is a reference return; over a `:dense` base, where the posting has to be materialized into a set first, counting through the merge cost 12.6 ms per call on a 100,000-handle root — a selectivity read, per conjunct, on a key the fork had never written to. `kv-member?` is the same observation at member granularity: `exception-rule?` probes both sides rather than merging, which is what keeps the firing-path gate O(1) across the seam. `kv-get` is the scalar/counter read and does **not** merge set values: an overlay value shadows the base's. No key in the index is read both ways — the trie's counters are read by `kv-get` and its handle sets by `kv-members` — and a backend is free to hold a posting in a private representation (`vaelii.impl.dense-kv` returns an `IntPostings` here), so merging at this op would mean type-testing another backend's internals. `kv-entries`, whose contract *is* Clojure sets, merges properly. **Single writer.** Pure runs one (docs/storage.md). A batch is applied op by op through this decorator rather than as one atomic step the way `MemoryKvBackend` applies it, so the instance lock is held around the whole of `kv-batch` — an incidental reader beside the writer then sees a batch whole or not at all, as it does on every other backend.
(overlay-kv overlay base)Compose a writable overlay KvBackend over a read-only base one.
Compose a writable `overlay` `KvBackend` over a read-only `base` one.
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 |