Contents

Filesystem-Shaped Durable Stores

This note defines the final durable shape for filesystem-like Lace stores. It is implementation architecture, not protocol authority. The numbered specs define record and interlace truth.

Purpose

Lace needs durable admitted-record stores in native Rust, browser OPFS, and Node without making storage a public authority surface or forcing every host through a generic backend framework.

Filesystem-shaped stores share record-log and index algorithms where useful, but physical-profile compatibility is optional. Native, Node, and OPFS use runtime-specific markers and locks so incompatible writers fail closed while IO ownership remains local to each host. The optional native LMDB backend uses a separate incompatible physical profile owned by native-lmdb-store.md. It shares only the native arena implementation, not this backend’s metadata, indexes, or recovery format. The semantic store/query/fact contract is defined in store-record-fact-access.md; runtime and FFI ownership are defined in their respective architecture notes.

Implementations

Native Rust, browser OPFS, and the standard @lace/lace-js/node entry implement this layout with runtime-appropriate file and lock APIs. Share pure layout and indexing algorithms where useful, but do not introduce a universal filesystem backend: hosts retain IO, locks, scheduling, workers, promises, and lifecycle.

Committed-byte assumption

Ordinary writes receive validated records, and query/load/reopen trusts committed store state. Repair, audit, and corruption recovery may revalidate bytes explicitly. The full trust and independent-contained-record contract is owned by store-record-fact-access.md.

StoreRecordId

This layout uses the StoreRecordId and StorePosition semantics owned by store-record-fact-access.md. Durable rows, indexes, caches, and diagnostics must not introduce another local record identity.

Durable layout

A filesystem-shaped store root contains:

store-root/
  store-format
  lock | node-lock
  arena-lock                (native only)
  record-log
  records
  indexes-v2/
  staging/                  (native only)
  compaction-plan, compaction-journal, compaction-state,
  and their *.lace-tmp temporaries                       (only during compaction)

store-format

store-format selects one physical implementation profile. Exact markers are:

native Rust  lace-native-filesystem-shaped-store/6\n
Node         lace-node-filesystem-shaped-store/4\n
OPFS         lace-filesystem-shaped-store/6\n

The final byte is LF. Open requires the exact marker for its implementation and fails without touching record, lock, or index paths when the marker differs.

Open is marker-first. Native open-or-creates store-format, takes a blocking file lock on it as the bootstrap rendezvous, and reads at most the exact marker length plus one byte. Under that lock it accepts the exact marker or completes a strict exact prefix only when the root contains no entry other than that marker. Every accepted path syncs the marker and invokes the platform directory boundary before unlock. This closes concurrent root scan and marker creation races and makes an interrupted marker-only initialization resumable without accepting an ambiguous layout. Node and OPFS read the same bounded marker without a bootstrap lock and likewise complete a strict prefix only in an otherwise empty root; concurrent first openers write identical bytes, and the loser then fails on the lifetime lock. Only after marker validation may an implementation touch its lifetime lock or record/index paths. An established foreign profile therefore fails without those mutations.

Profile locks and lifecycle

One runtime Lace exclusively adopts one concrete store object. Each filesystem-shaped root has one lifetime owner, and its constructor adopts position_may_advance_externally = false. Same-process operations share that Lace’s handles. Applications needing cooperating processes over one root use the separate LMDB backend.

Native Rust opens or creates stable path lock, acquires an exclusive kernel lock without waiting, retains the locked descriptor until close or drop, and then unlocks explicitly before closing it: a copy inherited by a forked child that has not yet exec’d does not extend ownership. Contention rejects an independent opener in the same or another process, including through path aliases. Path existence is only lock rendezvous; native never writes a PID or unlinks the path. Process death releases the kernel lock; the next owner performs ordinary open recovery. Operations acquire no further root lock. Native storage requires a local filesystem with working kernel locks and coherent positional-write/read-only-mmap visibility. Forking with a live native store or Lace object is unsupported. Applications fork before constructing these objects or exec before reopening; children do not use inherited owners.

Native also opens or creates the permanent empty rendezvous file arena-lock. Every arena mapping holds a shared lock on it for the mapping’s lifetime, including while returned records outlive their store; compaction takes it exclusively. It is separate from lock, which excludes concurrent Laces, so a surviving record never prevents a new Lace from opening. Its ownership is defined in store-compaction.md.

Node retains its lifetime sentinel at node-lock and lifetime descriptors for records and record-log. Marker and index IO use operation-scoped descriptors; completed reads own their bytes and retain no open index file. A failed scoped close is retained by the existing file owner, never reused or retried, and prevents sentinel removal. Clean explicit close waits for active store work, checkpoints and closes files, then removes node-lock last. A crash leaves the sentinel; reopen fails with its full possibly-stale path and never removes it automatically. Its error permits manual deletion only when the operator is certain that no process has the store open.

OPFS acquires a Web Lock with ifAvailable and fails immediately on contention. A named root derives one stable lock name. Opening a caller-supplied directory handle requires an explicit stable lockName; omission fails. The lock is held until close has waited for active work and released store resources. There is no process-local WeakSet or ownership registry.

Native close and drop never publish posting lists. Runtime Lace close first blocks new object access and drains concrete active reads, mutations, and position refreshes through durable classification and position publication, then consumes the native store object, releases its lifetime lock, and closes the descriptor. Started non-cancellable work may delay this boundary. Python uses the same consuming native close path. JavaScript close preserves its posting-list checkpoint and the Node-sentinel or OPFS-Web-Lock ordering above. Every visible result comes from one coherent view.

record-log

record-log is the append-order table from StoreRecordId to record hash and byte range in records. It defines admission order, authoritative StorePosition, Lace position-watch values, and index membership identity.

Each row is 64 bytes:

0..48   H3 typed record hash text, ASCII
48..56  record byte offset, little-endian u64
56..64  record byte length, little-endian u64

StoreRecordId(1) is row 0. High-water is the count of complete well-formed rows. There is no separate metadata counter.

Rows describe contiguous committed byte ranges. The first offset is 0; each later offset equals the previous committed end; length is nonzero; offset plus length must not overflow or exceed the committed records length.

records

records is one byte arena containing full canonical stored record bytes, append-only outside compaction. Committed record-log rows point to exact byte ranges.

Native Rust is compiled only for 64-bit Unix and Windows targets; elsewhere its store, Lace::filesystem and filesystem compaction are absent. A native root’s capacity is fixed when the root is created and recorded as the length of its sparse records arena. Creation uses the decimal byte count in LACE_NATIVE_STORE_CREATE_CAPACITY when set, otherwise 1 << 40 bytes, or 1 << 36 bytes on Android, whose arm64 kernels commonly provide only a 39-bit user address space, and on Windows, which charges commit memory for file mappings in proportion to their size. A capacity is at least 1 MiB and a multiple of 64 KiB; any other value of the variable fails open before the arena is sized. Opening an existing root uses its recorded capacity and does not read the variable, so a root opens wherever that capacity can be mapped. The native LMDB profile shares this rule. Physical initialization creates and syncs the empty record-log before creating records, and sizes an empty arena only while the log is empty. Once sized, the file is never resized or replaced; its committed bytes are rewritten only by compaction under exclusive ownership. An existing arena without record-log, an empty arena with nonempty log data, and an arena whose length is not a valid capacity fail closed. Unix sparse sizing uses the filesystem’s ordinary hole behavior; Windows marks the arena sparse with FSCTL_SET_SPARSE before sizing it.

With lifetime ownership acquired, initialization flushes lock, records, and record-log even when resuming paths left by an interrupted opener, then invokes the platform directory boundary before open success. Unix implements that boundary with directory sync_all. On Windows, native and Node sync each created file but have no supported unprivileged parent-directory flush equivalent; their directory boundary is therefore a no-op and makes no independent directory-entry crash-durability guarantee. Missing truth files still fail closed, while missing index replacements rebuild or fall back to scan.

Native opens one read-only MmapRaw over the complete arena. Appends use positional writes at the accepted log prefix’s committed end. Only a complete accepted record-log row may construct a slice over its immutable mapped range; there is no safe arbitrary-range mapping API. Returned records retain the mapping owner, which also holds the shared arena-lock, independently of the store lifetime. Unlogged suffix bytes are ignored. Node and OPFS preserve the same logical arena with host file APIs. Their capacity and mapping details remain profile-specific rather than protocol data. Unsupported host behavior is a store open or append failure, not a reason to add a second durable layout.

Node and OPFS keep one immutable, record-aligned read page over this arena. A sparse array of page-start StoreRecordId positions is derived from the resident record-log; it is not durable state. Pages pack consecutive complete records up to 33 MiB. That bound exceeds the 33,620,814-byte maximum H3 Seal record, so every valid H3 record belongs to exactly one page without an oversized-record case. A cache miss reads the exact first-record offset through last-record end in one host range read. Record projection borrows an internal subarray, while full-record results receive owned bytes.

The store retains only one such page. It does not maintain an LRU of record pages or retain decoded fact objects. Appending immutable records either extends the final page or starts another; an older cached prefix remains valid and is reloaded only when a requested range is absent.

staging/

Native staging/ holds received records before admission. A connected operation receiving into the store writes each record item to its own new file there as it arrives, syncs it once the record is verified, and hands the resulting file-range record to StoreRecords, which copies it into the arena in pieces through one store-owned buffer of the runtime’s IO chunk size. A staging file is removed when its last record, including one carried by RecordSaved, drops. Each adoption stages into its own subdirectory, as the portable file store defines; open removes what earlier processes and finished adoptions left. Staging is never committed state: no row names it, and recovery and compaction ignore it.

No durable facts layer

The store does not persist a facts directory or fact-block database. Canonical record bytes are the durable fact source. Transient projections and decoded visitors are caches or operation-local helpers.

indexes-v2/

indexes-v2/ contains durable posting lists keyed by primitive same-record access shapes. Posting lists contain sorted StoreRecordId values plus a checked_through sentinel. They are acceleration only.

The directory name is the index generation. A change to the projected 020 record facts names a new generation, because a list from an earlier projection can be wrong: a list for a then-absent field name can already cover every old record as checked. After marker validation and lifetime ownership, open removes every root entry named indexes-* other than the current generation and rebuilds lists on demand. That deletes a cache; it reads no old format. The store-format marker changes only with record bytes or layout.

Primitive keys:

FieldPresence(Name)
FieldExact(Name,Value)
FieldPrefix(Name,Start)
RecordLinkTarget(Target)
RecordLinkNameData(Name,Data)

No field name is privileged. Arbitrary application fields and the 020-projected synthetic and structural fields, including :Type, :Length and By, use the same primitive indexing machinery; record kind is FieldExact(:Type,B|P|S).

Each key string becomes x followed by lowercase hexadecimal UTF-8 bytes: empty text is x, .. is x2e2e, and A and a are x41 and x61. This is one injective component encoding across native, Node and OPFS, including on case-insensitive filesystems. It produces no dot components, device names, trailing dots/spaces or path separators. Decoding accepts only this spelling and valid UTF-8; it preserves a leading U+FEFF rather than treating it as a BOM. The enclosing physical profile gates the format; there is no old-path parser or migration.

Below indexes-v2/, the paths are:

field-presence/ENC(name).ids
field-exact/ENC(name)/ENC(value).ids
field-prefix/ENC(name)/ENC(start).ids
record-link-target/ENC(target).ids
record-link-name-data/ENC(name)/ENC(data).ids

ENC is the component encoding above. Each directory component and the entire .ids.lace-tmp leaf is at most 255 ASCII bytes. The relative path below indexes-v2, including that temporary suffix, is at most 1,024 bytes. Node and OPFS reserve the same suffix space so materializability agrees across hosts. Longer keys remain valid queries but are not materialized; scans preserve their exact semantics. Absolute root lengths and host-specific IO failures still use the ordinary scan fallback, not path truncation or hash aliases.

A posting-list file is logically:

[matching_store_record_ids..., checked_through]

Before allocating its read buffer, native, Node and OPFS bound a posting-list file to (store high-water + 1) * 8 bytes: at most one entry per admitted record plus the sentinel. An oversized file is unusable acceleration and uses the existing repair or scan fallback. Node and OPFS marker reads likewise consume at most the exact expected marker length plus one byte before exact-profile validation; they never materialize the rest of an oversized marker.

A new empty list contains one raw 0 checked-through StorePosition sentinel and no record identities. A list that does not cover the requested boundary is repaired by scanning exactly (checked_through, read_through]. Its sentinel advances only after that complete interval has been examined.

Native publication writes one complete replacement to a deterministic same-directory temporary path, syncs it, removes the prior destination when present, renames the temporary file, and invokes the platform directory boundary described above. The temporary name does not end in .ids; repair removes a leftover temporary file. A crash may leave the destination missing, which safely rebuilds. There is no in-place rewrite, per-process durable namespace, index-directory lock, per-list lock, or append-only segment format.

Posting-list read, repair, publication, quota, or path failure discards unusable acceleration and falls back to a complete record scan when committed records remain readable. If record truth itself cannot be read, the operation returns a store failure.

Commit rules

A new record is visible only after its bytes and record-log row are committed consistently. One native StoreRecords transaction performs this sequence:

  1. classify duplicates and repeated hashes in the input batch;
  2. allocate contiguous ids and byte ranges;
  3. write every missing canonical record at the committed arena end, copying a file-range record in bounded pieces;
  4. sync records once;
  5. append every corresponding fixed-width record-log row;
  6. sync record-log once; and
  7. adopt the committed rows in resident state.

No row is written before all record bytes named by that grouped commit are durable. The complete row is the admission point. Duplicate admission returns the existing id and appends nothing. Unlogged native arena suffix bytes are ignored and may be overwritten by a later write; the fixed arena is never truncated. Node preserves the same bytes-before-row commit ordering under its profile-owned lifetime exclusion.

After mutation success or error, the runtime executes authoritative CurrentStorePosition and publishes the confirmed result through its Lace. Posting lists may lag high-water, repair, rebuild, or use scan-equivalent fallback; index currency is not a precondition for position publication.

Heat and materialization

Stores may answer any valid FindRecords by scan. Durable posting lists are the steady-state query path for filesystem-shaped stores, but there is no required set of prebuilt lists.

Materialization is demand and heat driven:

Eviction, close, and drop never publish a native posting list. Repair and complete replacement are the only native durable-list publication path. The store does not persist query heat as durable authority. Existing posting-list paths that decode to primitive keys may seed startup heat as a performance hint.

Posting lists reside in heap vectors/arrays, not the mapped record arena. Native hot lists remain mutable store-owned values. After heat synchronization and all required repairs finish, a query borrows their bounded slices. Cold lists are immutable Arc<PostingList> values shared by the resident LRU and the active query; eviction drops only the cache’s owner, and repair replaces a list rather than mutating an active snapshot. Query-held lists can outlive cache residency, but no posting owner or iterator escapes in a store result. checked_through still establishes coverage; retaining a list does not widen the query boundary.

Node and OPFS retain ordinary references to posting arrays through the query, including across eviction during preparation and awaited residual record IO. The owning Lace’s existing whole-call sequence excludes mutation through result construction and drains before backend close, as defined in js-opfs-wasm-memory-layout.md. No additional lock or snapshot owner is needed. JS demotion/close checkpoints retain their existing behavior; they do not acquire native’s no-checkpoint rule.

Recovery and reconciliation

Native open performs recovery after acquiring lifetime ownership. It truncates only an incomplete final record-log row. Every complete row must have canonical encoding, a nonzero representable length, a contiguous in-arena range, a complete record glyph whose typed hash matches the row hash, and a hash not present in any prior row. A complete-row capacity, encoding, contiguity, arithmetic, glyph/hash, or duplicate violation fails closed; recovery does not discard complete malformed rows. The fixed records arena is never truncated.

After a failed write, reconciliation establishes the durable log prefix before another operation uses the store. It rejects regression, truncates a partial final row, validates the complete new suffix, and adopts rows, hashes, committed end, and position together. After a log write or sync error, no page-cache-visible suffix is adopted until a successful log sync establishes durability. Failure to establish that prefix prevents further use. Ordinary reads and position probes use resident admitted state; there is no external-log refresh.

Ordinary recovery trusts prior admission and does not recompute record hashes, embedded hashes, or Seal Marks. It may lazily load indexes and warm-start heat from posting-list paths that decode to primitive keys. Explicit maintenance may validate stored record bytes and rebuild all indexes. Repair never adopts an unknown layout.

Compaction

Compaction is the only path that removes records or rewrites committed arena bytes. It runs under the root’s lifetime ownership on a root with no live mapping, moves retained records down in place, replaces record-log, deletes indexes-v2/, and releases the freed tail: native punches holes and keeps the arena’s capacity length; Node and OPFS truncate records. Ids and positions restart contiguously in the retained records’ previous order. Ordinary open rejects a root holding compaction files. Retention, the algorithm, its files, and recovery are owned by store-compaction.md.

Search and index scope

Filesystem indexes accelerate only the same-record constraints defined by store-record-fact-access.md; they never index canonical containment. Every indexed answer preserves that document’s FindRecords matching, read boundary, continuation, row-limit, and completeness semantics. Scan-equivalent fallback remains the correctness path.

OPFS, browser local storage, and JavaScript Node notes

OPFS and Node roots are not physically interchangeable with native roots or with each other. OPFS and @lace/lace-js/node are host-owned JavaScript stores. They own file handles, locks, promises, workers, trusted committed-record parsing, posting-list maintenance, and close/checkpoint behavior. Ordinary query/load/reopen does not call Rust/WASM record validation or crypto. The two implementations may share JavaScript layout, projection, heat, repair, and scan-equivalent test algorithms.

One StoreRecords batch appends all record bytes, then all log rows, each in one host write. On OPFS that write is one createWritable({ keepExistingData: true }) session, which copies the whole file before publishing it atomically on close, so a batch costs O(file size). Interlace admits each received record as its own batch; OPFS reception of N records therefore costs O(N × file size). Worker-only FileSystemSyncAccessHandle writes in place without that copy and is not used because OPFS Laces also run in Window realms.

The browser local-storage implementation is not filesystem-shaped, but it uses the same H3 admission-contract cut. Its durable marker is exactly lace-local-storage-store/4; it rejects every other marker without migration. When Web Locks are available it acquires one exclusive lock with ifAvailable and fails immediately on contention. The explicit singleTab fallback uses one realm-local ownership set only when Web Locks are unavailable. It adopts position_may_advance_externally = false; mutation outside its lifetime owner is an error, and its storage event listener is not a position-notification source.

Native Rust notes

Native runtimes may construct the Rust implementation directly and wrap blocking work according to their scheduling model. The runtime receives the native store’s external-advance adoption value directly; drivers do not infer polling from a concrete store variant. Poll cadence, failure fanout, cancellation, and commit-publication ordering are defined in runtime-provider-architecture.md and open-store-wakes.md.

Tests

Filesystem-store conformance should cover marker creation, bounded reads, strict-prefix resumption, and rejection; concurrent native marker rendezvous; fail-fast same-process and subprocess exclusion including path aliases; lifetime lock release after close, drop, failed open, and process death; contiguous ids and duplicate detection; crash-resumable arena initialization only before the first complete row; creation-only capacity override and invalid-capacity rejection; mapped-record lifetime across close and reopen; fixed old read boundaries during later local commits; native external-advance adoption set to false; partial-final-row truncation; complete-row failure without position regression; durable reconciliation after failed writes; synced posting-list replacement and crash recovery; lagging-list repair; oversized-list scan fallback; injective key-path vectors including empty, dot, case-distinct and UTF-8 components; real materialization/reopen without wrong-key reuse; full leaf/temporary name limits with long-key scan fallback; query-held cold lists surviving eviction during preparation; borrowed hot lists at old read boundaries; JS whole-call exclusion across record-read awaits; and native no close/drop publication; native arena-lock held exactly while a mapping or returned record lives. Node clean/stale sentinels and OPFS ifAvailable locks and supplied-handle lock names retain their profile-specific coverage. Semantic query, identity, fact-projection, and trust-boundary coverage belongs to store-record-fact-access.md.