Skip to content

feat(storage): atomic multi-statement programs (#131) - #208

Merged
jsam merged 5 commits into
mainfrom
fm/il-t03
Oct 3, 2026
Merged

jsam merged 5 commits into
mainfrom
fm/il-t03

Conversation

@jsam

@jsam jsam commented Oct 3, 2026 •

Copy link
Copy Markdown
Contributor

Atomic programs: transaction WAL envelope (T01), staged fact programs with one-revision publication (T02), atomic rule/schema programs with explicit unsupported boundaries (T03). Validated through the no-mistakes pipeline before merge. Refs #131.

Tracker: #199

jsam added 5 commits October 3, 2026 19:26
Two servers on one data_dir (for example a Kubernetes RollingUpdate on a
ReadWriteOnce volume) interleave WAL appends and shard rewrites and corrupt
both. StorageEngine::new now takes an OS advisory lock (flock / LockFileEx
via fs4) on data_dir/LOCK before creating, reading or writing anything
else, and holds it as the engine's last-dropped field.

A second engine on a locked directory fails with
StorageError::DataDirLocked naming the directory and the owner's recorded
pid, and leaves the directory byte-identical. The OS releases the lock when
the owner exits, including SIGKILL, so a stale LOCK file never blocks a
restart. Distinct directories lock independently.

Startup only: one open + flock + pid write (~80us measured); no per-request
lock or hot-path change.

Closes #142
A write now commits a Transaction: every change of one commit, across any
number of shards, at one revision. The WAL stores it as one checksummed
record whose trailing newline is the commit boundary, written with one
append and (in immediate mode) one fsync. Recovery replays the longest
intact prefix of records, so a restart yields the state after an exact
number of commits, never part of one.

- PersistBackend::append(shard, updates) becomes commit(txn). Inserts and
  deletes commit one-op transactions; startup multiplicity corrections and
  prefix clears commit one transaction across all their relations, so a
  failed prefix clear now leaves every relation intact.
- TxnOp is a typed enum (facts today); rule and schema changes become new
  variants. A checksummed record this server cannot decode fails startup
  with StorageError::WalUnreadable instead of being skipped.
- Tuples are stored with the lossless batch codec (base64), fixing NaN and
  infinite floats that JSON wrote as null and replay then dropped. v1
  records still replay so v1 data dirs migrate with their WAL.
- A crash-torn last line is cut off. Any other damage stops replay there
  and the cut-off bytes are saved to wal/current.wal.<ms>.corrupt, instead
  of skipping the damaged record and replaying later ones out of order.
- A failed write or fsync is cut back to the exact committed length; if
  that fails, the repair runs before the next write, rewrite or shutdown,
  so a commit that returned an error is not replayed.
- Remove the unused legacy src/storage/wal.rs, a second WAL format.

Hot path: same locks (WAL mutex, shard map, per-KG write lock), nothing
on the query path; one record per commit instead of one per tuple.

Part of #131
Consecutive fact statements of a program (+, -, conditional delete,
update) are staged without touching the knowledge graph and committed
together under the KG's existing write lock: one effective delta, one
WAL record at one logical time, one snapshot publish, and one
notification per changed relation after the publish. A statement with
other persistent effects (schema, rule, meta command) or the end of the
program commits the run first. If any statement of a run fails, none of
them is applied and none reports success.

Conditional deletes and updates evaluate on the snapshot plus the
changes staged before them and record the relations their query reads.
The commit refuses a stale read when one of those relations or a rule
changed, and the run is staged again with a short random backoff, up to
8 times, before failing with a conflict. Writes to other relations never
conflict. A cancelled (timed out) program never commits.

insert_tuples_into and delete_tuples_from are one-statement programs on
the same path, so there is one write path. Update statements now notify
the relation they change instead of "multiple". State-dependent insert
rejections (arity, view, vector index, schema) report code validation.

Partial #131 (slice #169).
A program that changes persistent state now commits all of it as one
transaction on its knowledge graph: facts, schema declarations, persistent
rules and rule removals (-name, .rule drop, .rule drop prefix, .rule
remove, .rule clear). Statements apply in order to staged copies of the
catalogs under the KG's existing write lock, so a fact is checked against
a schema declared earlier and a conditional delete or update after a rule
change evaluates with the new rule. Everything is written as one WAL
record and published as one snapshot: readers see one rule generation
with its data. The first failing statement fails the program; nothing is
applied, its query does not run, and subscribers are not notified.

Commands that cannot join the transaction (.kg, .rel, .rel drop, .clear,
.index, .compact, inspection, user, ACL, ontology, subscription) are
rejected with code unsupported before any statement runs when they share
a program with writes. Programs without writes run as before.

- TxnOp::Catalog carries each changed rule's and persistent schema's
  state after the commit, so replay is idempotent. Catalog files record
  the revision they reflect and are written atomically; the WAL keeps a
  catalog change until both files are saved past it, and startup replays
  what the files miss. KG drop removes its WAL catalog changes.
- Every catalog API is a one-statement program: one write path.
- .ontology install deploys as one transaction; .ontology remove drops a
  pack's rules in one transaction and each relation on its own.
- Python SDK load() docs state the real transaction boundary.

Hot path: fact commits take the same locks as before (the catalog log
lock only when a transaction carries catalog changes); queries are
untouched. Rule and schema changes now cost a WAL fsync and two atomic
catalog saves.

Part of #131 (slice #170).
make doc-check (rustdoc -D warnings) rejects intra-doc links from public
module docs to private modules; name them in plain text instead.
@jsam
jsam marked this pull request as ready for review October 3, 2026 19:27
@jsam
jsam merged commit d75ce6e into main Oct 3, 2026
13 checks passed
@jsam
jsam deleted the fm/il-t03 branch October 3, 2026 19:33
jsam added a commit that referenced this pull request Oct 3, 2026
main is d75ce6e (#208) plus 4578fe6 (#215), the squash of fm/il-w04,
whose tree is identical to fm/il-w04 merged above; keep this branch's tree.
jsam added a commit that referenced this pull request Oct 4, 2026
…ry request (#249)

The release-checkpoint performance gate fails on main: cheap_query serial
p50 is 1.110x the approved baseline e732cd5 on the 32-vCPU runner
(115 -> 126 us). Concurrent latency and throughput did not move. Bisected
to #214 (per-connection request pipelining), made worse by #222.

Cause: the pipeline runs requests in a `FuturesUnordered`. Its `poll_next`
wakes its own task and returns `Pending` after any poll that polled every
future in the set. With one request in flight, which is every serial
client, that happens on each request's first poll. The connection task
wakes itself, tokio schedules that as a yield, and a yield wakes an idle
worker to take the task. Each request therefore costs one more context
switch (4.0 -> 5.0 per query) and a hand-off of the connection task to
another core. #222 added no work per query but made the hand-off dearer:
user cycles per query rose 15% at the same instruction count.

Fix: keep one never-woken future in the set. After the pipeline's first
poll it is never polled again, so no poll reaches every future and the
forced yield no longer fires. The yield after futures that wake
themselves still applies. Pipelining, ordering, deadlines, cancellation
and the credential fence are unchanged. Nothing is added per request: no
lock, atomic or allocation. Each connection gets one more set node.

Bisect (cheap_query, `?edge(1, Y)`, serial). Server counters per query
from perf stat. Ratios are against e732cd5, from an interleaved probe
with one pinned server per commit, 40 rounds:

| commit | PR | user instr/query | ctx switches/query | p50 ratio |
|---|---|---|---|---|
| e732cd5 | baseline | 1.282M | 4.0 | 1.000 |
| d75ce6e | #208 atomic programs | 1.279M | 4.0 | 0.993 |
| 4578fe6 | #215 notification stream | 1.271M | 4.0 | 0.991 |
| 71a4d24 | #216 online backup | 1.275M | 4.0 | 1.016 |
| 2f621c5 | #200 first-update latency | 1.272M | 4.0 | 1.009 |
| e96df5c | #207 | 1.279M | 4.0 | 0.998 |
| 4dd8fe9 | #209 shard index | 1.272M | 4.0 | 0.987 |
| 277c7f0 | #206 | 1.274M | 4.0 | 1.008 |
| 3554c98 | #214 pipelining, deadlines | 1.296M | 5.0 | 1.020 |
| 3492a59 | #213 | 1.294M | 5.0 | 1.030 |
| 2ba9a5a | #212 provenance | 1.297M | 5.0 | 1.029 |
| 9ed61b4 | #204 key expiry | 1.297M | 5.0 | 1.027 |
| be35ee3 | #221 | 1.297M | 5.0 | 1.013 |
| c98a590 | #222 bounded streaming | 1.298M | 5.0 | 1.047 |
| a6fd628 | #219 wildcard fix | 1.297M | 5.0 | 1.061 |
| b7f7ad6 | #220 WAL durability | 1.300M | 5.0 | 1.056 |
| de54807 | #223 shared standing eval | 1.299M | 5.0 | 1.071 |
| 55ec34d | #225 checkpoint-1 fixes | 1.300M | 5.0 | 1.045 |
| 23712b8 | main | 1.300M | 5.0 | 1.064 |
| this change | | 1.300M | 4.0 | 1.033 |

Confirming A/Bs with the gate's own fixture (fresh pinned servers each
round, 40 rounds, ratio [95% interval]):

- #214 vs its parent 277c7f0: 1.039 [1.027..1.049]
- #222 vs its parent be35ee3: 1.025 [1.006..1.044]
- A/A 3554c98: 1.010 [1.002..1.025]
- e732cd5 -> main: 1.048 [1.028..1.066]
- main -> this change: 0.978 [0.958..0.989]
- e732cd5 -> this change: 1.021 [1.009..1.044], PASS (budget 1.05)

User cycles per query (perf stat, same instruction count): e732cd5 958K,
be35ee3 1053K, c98a590 1206K, this change 1006K.

Full gate, all fixtures, 20 rounds, servers pinned to CPUs 2-15:

- main -> this change: no metric worse. Every required metric is PASS, or
  INCONCLUSIVE with an interval that includes 1.0. cheap_query p50 0.979
  [0.953..1.007].
- e732cd5 -> this change: cheap_query p50 1.029 [1.019..1.072],
  INCONCLUSIVE on a busy host (load average up to 22); bound_query p50
  1.022, PASS. The insert and delta metrics improved since the baseline.

The shared host is about 4x slower per query than the CI runner, so the
same hand-off is a smaller share of each query here than there.

The remaining ~1.7% of user instructions per query since #214 is the
pipeline's own per-request bookkeeping: the boxed request future (one
4-8 KiB allocation), its set node, the request control and the in-flight
maps.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant