Compaction shrinks a durable Lace root. Records that no retention policy selects are removed and their bytes are released in place, without a second root, an interlace copy, or headroom proportional to the retained bytes. This note owns retention semantics, sweep lowering, the common compaction algorithm, its recovery, and live-record exclusion. Lace-100 owns the public entry points; the store notes own their physical layouts and link here.
The live store contract stays append-only. There is no delete
StoreOp, no tombstone, no id gap, and no change to 040/050
send commitments. Compaction is an offline maintenance call on a root
that no Lace has open:
B and produces a kept
set;After compaction the root’s
StoreRecordId/StorePosition domain restarts
contiguously from 1 in the retained records’ previous relative order.
Nothing durable outside the root refers to ids. AdmitOrder
comparisons between retained records give identical answers. Posting
lists are deleted and regenerate on demand (native filesystem, Node,
OPFS) or are rebuilt (LMDB).
A removed record is not Have again. A peer resends it
when the exchange policy still requests it; removal is not
retraction.
The input is a nonempty list of prepared policies, the same inputs
interlace operations accept. With B the root’s high-water
at sweep start, a record R is retained iff
for at least one policy P,
P.SelectStoredRecord(R) holds when P is
evaluated alone as one local module over the complete local fact view at
read-through B.
SelectStoredRecord/1 facet counts.
ExposeRecord, SelectAdvertisedCandidate,
TxDisabled, and RxDisabled are ignored. A
policy without a SelectStoredRecord rule contributes
nothing; a list in which no policy has one is a Policy
preparation error, never “remove everything”.Have. There are no exposure
wrappers, peer advertisement rows, or session authority. A policy whose
SelectStoredRecord dependency graph reaches
Here/1 or PeerConfidential/1 is a
Policy preparation error; the sweep never treats absent
authority as false.B regardless of window
order. Evidence that a policy reads but does not select is removed;
content that depended on it is then unselectable by exchange and by a
later compaction. Retention policies therefore select their own
evidence. A later compaction may remove more.Exchange evaluation caps each built relation at 2^18 rows because a
peer’s operand runs on the local side; the cap bounds the memory a peer
can make the local side retain. A root worth compacting retains far more
records than any cap, and an unbounded SelectStoredRecord
relation grows with the root. The sweep therefore decides one window of
ids at a time while every helper still sees the whole root. Windows make
memory independent of the root’s size; the derived-row cap only fixes
how large a window may be.
For window (lo, hi], 0 ≤ lo < hi ≤ B,
every rule whose head is SelectStoredRecord(R) becomes:
SelectStoredRecord(R) :- <body>,
Compare(AdmitOrder(R),'>',AdmitOrder('<hash of id lo>')), (absent when lo = 0)
Compare(AdmitOrder('<hash of id hi>'),'>=',AdmitOrder(R)). (absent when hi = B)R, wherever it occurs in the body, to the window
(store-record-fact-access.md).
When R is bound otherwise (a link target, a field value, a
helper or TopK binding), the comparisons filter that
binding. The last window needs no upper anchor because its read-through
is B.Have(R) is added: an extra scan of R
would probe the rest of the body once per window record. The comparisons
already require R to be admitted. Only a bare
true body, which 030 permits only alone, becomes
Have(R).kW: the record at that id bounds this window from above and
the next one from below. The sweep loads all of them in one
LoadRecordsByStoreId batch before the first window and
keeps only their hashes.TopK, Cardinality, negation, and recursion
need no special case: facet predicates never appear in rule bodies
(030), so the window filters the head rule’s bindings after lower
strata, including TopK ranking, have derived their complete
relations. The union over windows equals the unwindowed result.A named helper compiles to a separate rule. For
SelectStoredRecord(R) :- message(R,'lobby'). the helper
message would derive its complete relation in every window,
hit the derived-row cap on a large root, and cost
windows × helper below it.
Every positive call that passes the selected record to a helper, at
any argument position, names a hygienic clone of that helper windowed on
the receiving position. Each clone rule receives the same two
comparisons on that head term, and its own positive calls passing that
term are redirected in turn. A clone equals its original restricted to
the window, so every call it replaces keeps its meaning: the calling
rule’s window already constrains that record. The clone’s comparisons
bound its derived rows; groups rooted at the record additionally receive
the store read bounds. Original helpers remain for negated,
Cardinality, and TopK uses and for calls that
do not pass the selected record; a recursive call passing it reaches the
same clone. Cloning uses the same structural renaming as 130 composition and
exchange output specialization (interlace-policy-lowering.md).
A helper reached only through those other uses is derived whole-root once per window under the sweep’s derived-row cap, exactly as in exchange.
The window size W and each window’s
max_derived_facts_per_relation are both
RETENTION_WINDOW_RECORDS = 2^20, so the output and every
windowed clone hold at most 2^20 rows per window. Each window evaluation
also runs under a work budget of
B × RETENTION_WORK_PER_RECORD (2048), which bounds the join
bindings and record reads that the derived-row cap does not count. It
scales with B, not W, because non-windowable
helpers and joins reaching the selected record through other records
visit the whole root in every window. Exceeding either is
LimitExceeded for the compaction. Exchange keeps its 2^18
profile; these are not interlace operation options.
Each window runs one round of a fresh session evaluation per policy,
compiled from a single-module lowering with one generated record output
whose final membership also carries the stored id of every selected row.
Total cost is O(root records × rules) for the output and windowed
clones, the same as one unbounded pass, plus one re-derivation of each
non-windowable helper per window. Rule application resumes at each store
request rather than replaying, so a helper joining the whole root by
field value is linear in the root; it is still re-derived in every
window and then dominates the sweep. The work budget leaves at least
twice the cost of such a helper with a small join fan-out. Clones remove
most of the window multiplier for named helpers. A helper relation still
costs more than the same condition inlined in an include
body, because constants at the call site are not pushed into the helper:
it derives its relation for every value, then filters. The sweep’s
repeated primitive keys become hot after the first window, so later
windows use posting lists rather than root scans.
The sweep produces a kept bitmap over (0, B] of
B/8 bytes. A bit set for an id outside the current window
is still a correct answer: the window filters R, it does
not bound enumeration of other records.
RetentionSweep is a sans-IO machine in
lace-sans-io that issues one StoreOp at a time
and resumes on its result. It owns the boundary, window cursor, anchor
hashes, the current window evaluation, and the bitmap. It performs no IO
and knows no backend. The runtime drives it against the root’s
exclusively owned concrete store through that store’s ordinary operation
execution (runtime_support::retention::run_retention_sweep
synchronously), then hands the store only the kept set. A window
evaluation holds the arena-backed records it loaded until that
evaluation ends; the driver’s return is therefore the point after which
no sweep-produced record remains and the exclusive
arena-lock may be taken. Stores remain policy-neutral:
their physical compaction entry receives a kept set, never a policy.
A native arena-backed Record is a slice over the
read-only mapping and may outlive its store and Lace in any process.
Compaction rewrites and releases those bytes, so it must know no such
mapping exists.
Each native root (filesystem and LMDB) has a permanent empty
rendezvous file arena-lock. Every arena mapping takes a
shared advisory lock on it when it is created and holds it through the
descriptor owned together with the mapping; records retain that owner,
so the lock lasts exactly as long as the mapping or any record over it.
Taking it costs one lock call per mapping, none per read. It is distinct
from the native lifetime lock, which excludes concurrent
Laces; a record surviving its Lace must not prevent a new Lace from
opening. It is a separate file rather than a lock on
records because Windows byte-range locks are mandatory and
would block arena writes.
Compaction holds the root’s rendezvous lock for its whole duration:
the native lifetime lock, or LMDB’s
store-format bootstrap lock. It takes an exclusive try-lock
on arena-lock before the sweep to fail fast, releases it,
runs the sweep through a store opened under the held rendezvous, drops
that store, its mapping, and every record it produced, then takes the
exclusive try-lock again and keeps it until finished. Contention at
either point is Store: a Lace or arena-backed record of the
root is alive somewhere. While compaction runs, a native filesystem
opener fails on the lifetime lock, an LMDB opener fails once its bounded
bootstrap-lock retry expires, and any opener that gets past its
rendezvous fails on compaction-state. The compactor moves
bytes with positional reads and writes, never through a mapping.
JavaScript stores return owned copies and need no live-record exclusion.
Inputs: the exclusively owned root, the kept bitmap, and the old row
table (hash, old_offset, len in id order). New rows are the
kept old rows in id order; new_offset is the running sum of
kept lengths, so new_offset ≤ old_offset for every row.
A. plan replace `compaction-plan`: header {B, retained, J, old end} and
72-byte rows {hash[48], old_offset u64, new_offset u64, len u64}.
Its presence means it is complete.
B. state replace `compaction-state` with {move, cursor 0}.
Delete the index directory (native filesystem, Node, OPFS).
C. move for each batch of consecutive plan rows with total length ≤ J:
D = [new_offset of first row, new end of last row)
when any batch row's old range intersects D, replace
`compaction-journal`: header {first row index}, then
{row index, bytes} for each such row
write every batch row whose offset changes, from its journal copy
when its old range intersects D, else from its old range; sync arena
replace `compaction-state` with {move, cursor after batch}
D. publish filesystem profiles: replace `record-log` with the plan's rows at
their new offsets
LMDB: `compaction-state` := {reload, cursor 0}; rebuild metadata
E. release native: punch the unlogged tail [new end, capacity)
Node, OPFS: truncate `records` to the new end
F. finish remove `compaction-journal`, then `compaction-state`, then
`compaction-plan`Every “replace” writes <name>.lace-tmp, syncs it,
renames it over <name>, and syncs the directory, so
each compaction file is either absent or complete. The old end in the
plan header lets a resumed compaction report released bytes. Index
removal is repeated before D (native filesystem) or on resume (Node,
OPFS) because a crash between the state commit and the first removal
could otherwise leave lists naming old ids.
J is at least one maximum H3 record (33,620,814 bytes);
the default is 64 MiB. Headroom beyond the root is the plan (72 bytes
per retained record) plus one journal of at most J.
Destination writes of a batch lie below the next batch’s first
new_offset, which is at most that row’s
old_offset. A batch therefore overwrites only source bytes
of its own rows, and exactly those rows are journaled and synced before
any destination write. Earlier batches are synced and recorded by the
cursor before a batch starts. Journal volume falls to zero once the
accumulated gap exceeds J.
store-format is never rewritten: it is the native
rendezvous inode and LMDB’s permanent bootstrap file, and an in-place
rewrite can tear. The compaction files and their .lace-tmp
temporaries are the only additional root entries besides native
filesystem staging/, which holds no committed bytes.
Ordinary open rejects any of them, including a temporary left by an
interrupted step A on an otherwise consistent root, naming the
compaction entry point that resumes; only compaction accepts them and
removes leftover temporaries first.
Compaction on a root that holds compaction files resumes without a sweep:
compaction-state |
compaction-plan |
Action |
|---|---|---|
| absent | absent | normal root |
| absent | present | interrupted before B or after F’s state removal; the root is consistent either way. Remove the plan and journal, then compact afresh with the supplied policies. |
{move, c}, c < rows |
present | rows before c are durable. Recover the batch at
c (below), sync, continue C. |
{move, c}, c = rows |
present | the move is complete; redo D (idempotent), then E and F. |
{reload, c} |
present | LMDB arena complete; resume the reload. |
| unparsable, or plan absent or short | any | CorruptStore; nothing is guessed. |
Each row of the interrupted batch is recovered by full typed-hash verification (010) rather than its glyph line, which covers only the first 55 bytes and cannot prove a complete copy after a torn multi-page write:
new_offset that hash to the row are already
moved;CorruptStore.The journal is replaced atomically, so it is absent, complete, or a complete journal of an earlier batch, which its header excludes. Recovery resolves every row of the interrupted batch before writing, rewrites that batch’s journal when any row overlaps, and hashes at most one batch.
Release is idempotent over the whole unlogged tail, so it also retries a failed earlier release and reclaims residue from past failed writes.
Compaction takes no cancellation input. Dropping a Tokio future or a Python interruption requests a stop that takes effect before the next sweep store operation or move or reload batch; dropping a Tokio future is not a waitable boundary. Process termination at any point leaves a resumable root. A stop before A changes nothing; a later stop leaves compaction files that make ordinary open fail until compaction resumes.
The runtime opens the root’s store under its lifetime lock and drives
the sweep, then calls the store’s physical compaction entry with the
kept set. A root holding compaction files resumes through the same entry
without a kept set. The row table is the resident record log; the new
record-log uses its ordinary 64-byte rows. Moves are
positional pread/pwrite, chunked for large
records.
Release punches the tail:
fallocate(FALLOC_FL_PUNCH_HOLE | FALLOC_FL_KEEP_SIZE) on
Linux, fcntl(F_PUNCHHOLE) on macOS,
FSCTL_SET_ZERO_DATA on Windows sparse files. Holes read as
zeros through any mapping. Capacity is unchanged. A filesystem without
hole punching reports release Unsupported in the compaction
result after the root is already consistent.
Exclusion uses arena-lock and the bootstrap lock above,
not reader slots: an open store holds no slot between operations until
its first read, and a slot reveals nothing about records that outlive a
store. The row table is a cursor over records-by-id. The
sweep’s environment and arena mapping are closed before the move, so no
environment is open while the arena moves; the reload reopens it and
reads moved records positionally.
LMDB postings are written at admission and a missing posting means no candidates, so they are rebuilt during reload rather than regenerated lazily. The first reload transaction empties all three databases and inserts the first batch of plan rows; each later batch of 2^14 rows commits separately. A batch inserts the primary row, hash row, and postings projected from the record at its new offset, through a metadata-only insert shared with admission (admission also classifies duplicates and writes bytes). Batches are resume granularity, not a dirty-page budget. On resume the last primary row must match the plan row at its id by hash and range; the reload then continues after it, and otherwise restarts from the empty databases. Databases left untouched by a compaction that kept every record match the plan exactly and are kept.
Release punches the shared arena tail as for the filesystem store.
data.mdb does not shrink: emptied pages return to LMDB’s
freelist and are reused by later admissions. The compaction result’s
released bytes count arena bytes only.
The JavaScript entry point opens the store itself and holds its
profile lock (Node node-lock sentinel, OPFS Web Lock)
across sweep and rewrite. Marker validation is unchanged, since
compaction never rewrites store-format; only this path
accepts the compaction files. The store’s indexes-v2
directory is removed in B: posting-list repair would otherwise accept
stale lists after renumbering. The store never checkpoints its resident
posting lists on this path. Node replaces plan, state, journal, and log
through a synced temporary sibling and rename, then reopens its lifetime
record-log handle; an OPFS writable session without kept
data already publishes atomically on close.
OPFS runs the complete move and the final truncate in one writable
session. Its close is an atomic swap of the whole file, so OPFS needs no
journal: an interrupted session leaves records untouched
and recovery redoes the move. A session published before its state
commit is recognized by the last moved record verifying at its
destination. OPFS headroom is therefore one additional copy of
records. Node uses the common batched move and truncates
records at release. After a Node crash the stale
node-lock sentinel still requires operator removal before
resuming.
The store is small (at most 10,000 records under fixed-width id keys) and its open ignores unknown keys and does not verify bytes, so compaction uses its own key sequence under the Web Lock:
store-format
key;compaction-plan key holding the boundary, the
released bytes, and the old id of each new id;record-log key once, delete record keys
above the new count and the plan key, then restore the
store-format marker.Open with the compacting marker fails with the resume hint. Resume copies again every record whose value at its new key does not verify by hash; a record-log already rewritten (as long as the plan’s kept list) skips to the key cleanup. A compacting marker without a plan is restored and compaction starts afresh. The plan key counts toward the namespace limits.
Rust and JavaScript in-memory stores exist only while their Lace is open and have no compaction path. The Rust indexed in-memory store is the sweep’s test backend.
Sweep coverage should compare the union of windowed
SelectStoredRecord against the unwindowed scan-equivalent
result on small roots with tiny W and tiny derived-row
caps, for exact and prefix fields, link joins, negation, cardinality,
admission order, TopK, named helpers (cloned and fallback),
and heads where R is not the first group root, asserting
the FindRecords read bounds emitted per window rather than
only the result set. Preparation tests cover authority-dependent and
facet-less rejection, ignored vetoes and exposure, and a cascade where
removed evidence leaves dependent content unselected by the next
sweep.
Compaction coverage for native filesystem, LMDB, Node, OPFS, and
local storage: retained set by hash; relative order; contiguous ids;
position equal to the retained count; identical bytes by hash; journaled
overlapping batches; tail release (native allocated blocks, JavaScript
file length); LMDB postings answering queries after reload. Crash
coverage uses an arena IO fault injector that drops writes after the
last sync, not only process kills, at every step A–F and inside C before
and after the journal sync, during destination writes, and around the
cursor rename; resumed compaction yields an identical root, ordinary
open fails with the resume hint, and a torn state file or missing plan
is CorruptStore. Lock coverage: a live record from a closed
Lace, in the same and another process, fails compaction as
Store; a live LMDB store in another process fails
compaction; ordinary open during compaction fails as described and
succeeds after it; simultaneous LMDB opens of one root all succeed; LMDB
reload resumes after a crash between batches and restarts after a crash
before the first commit. Limits use explicit tiny windows, caps, and
J. An ignored big test sweeps a synthetic
2^20-record in-memory root with inline, cloned-helper,
non-windowable-helper, and whole-root value-join policies and reports
wall time and consumed work per window. A helper whose work outgrows a
tiny root fails with LimitExceeded.