M1: The file

The second milestone of rupg, specified in spec/23-milestones.md section 23.4. M1 builds the single .rupg file and everything that makes a write durable: the format, the header slots, the buffer manager, the per-worker log, recovery and the hot store. It adds a first MVCC with snapshot reads and a Rust key-value API over typed tables. M1 has no SQL and no network.

Why

The file comes before SQL. Every layer stands on the file, and the file format is the hardest thing to change after users have files.

The HLC and the shard field are in M1 because a row id written without a shard field can never get one. This is the meaning of "ready for a cluster" in spec/04 §4.11. The single-node code calls the cluster traits from M1, so the cluster at M10 adds implementations and does not change the stack.

M1 has no gate, but its numbers set the floor for G4 at M3 and G5 at M5 (spec/23 §23.4).

The work

Taken from spec/23 §23.4. The reference in brackets names the spec section that owns the detail. Change the list in the spec and copy it again. Do not edit it here.

Exit criterion

No gate of spec/02 §2.10 applies to M1. The report publishes the commit latency at one writer, the commits per second at one writer per core on gpc, the size of an empty file, and the recovery time after 1 GiB of log.
1 million crash files run with no lost commit.
file_open, page_decode and log_replay each run 24 CPU hours with no open find.
The close report answers each line of the checklist in spec/23 §23.18 that applies from M1.

Open questions

These questions in spec/24 close at M1.

Q30 (spec/24 §24.5): the log ring size, 64 MiB per worker or smaller for an embedded library. Q30: What is the size of the log ring? #43
Q31 (spec/24 §24.5): the checkpoint trigger, max_wal_size for each ring or for the sum over all rings. Q31: Does max_wal_size apply to each ring or to the sum? #44
Q38 (spec/24 §24.5): the cost of the hash table fallback on 39-bit aarch64 hosts. Q38: What does the hash table fallback cost on 39-bit aarch64 hosts? #51
Q40 (spec/24 §24.5): two files during rupg upgrade. Q40: Are two files allowed during an upgrade? #53
Q69 (spec/24 §24.9): the thresholds of the performance tests, until the noise is measured. Q69: What are the thresholds of the performance tests? #82
Q70 (spec/24 §24.9): the crate names, published at M1. Q70: When are the crate names published? #83

Harness work

Benchmarks: M1: Storage and commit floors rupg-bench#2

Depends on

#1.

Spec

Progress on M1: #91 is merged.

rupg-common now has Error with its SqlState, and the identifiers of spec/04 §4.7: Oid, ShardId, RowId, Hlc, Xid and Lsn. The widths are now fixed, because the file format stores them. A test checks each SQLSTATE constant against the errcodes.txt of the pin.

No line of the checklist is complete yet. The HLC line completes when the log writes the commit timestamp, and the row id line completes with the hot store.

Next: the platform traits with the operating system and the simulation implementations (spec/21 §21.10). Then the file format in rupg-file.

Progress on M1: #92 is merged.

rupg-platform now has the Io, File, Clock and Entropy traits with their operating system and simulation implementations. SimIo is the disk model of spec/21 §21.9.1. A crash test can list the unsynced operations, give each one a fate (lost, written, torn or misdirected) and an order, and build the file that the power cut leaves. The 1 million crash files of this milestone will use it.

The platform line of the checklist stays open until the second half: Tasks, Net, MemoryPool, the CPU feature detection and the clippy rules that keep std::fs, std::net and std::thread out of the other crates.

Progress on M1: #93 is merged, and the platform line of the checklist is done.

rupg-platform now has the five traits of spec/21 §21.10: Io, Clock, Entropy, Tasks and Net, each with an operating system and a simulation implementation. It also has MemoryPool with the reclaimer and the Nth failure test mode, and the CPU levels of the kernels. clippy.toml now keeps std::fs, std::net and std::thread out of the other crates.

SimTasks runs each task to its end or to a yield_now. The scheduler of the engine must follow this rule, so a task never blocks on a lock that another task holds. The network faults come with the cluster at M10.

Next: the file format in rupg-file. It starts with the XXH64 checksum lifted from rudb, the identity block, the header slots and the page header.

Progress on M1: the first part of the file format is merged in #94.

rupg-file now has the page checksum lifted from rudb, the identity block, the two header slots with the slot choice rule, the owner record and the 64-byte page header. verify finds a bad checksum, a misdirected write and a lost write. Each block has a text form that parses back.

The checksum is now in rupg-file and not in rupg-kernels, because of the layer order. spec/08 §8.3.2 is changed to match.

Next: the page table, the extent classes, the free space map with the arenas, and the ring directory. That PR completes the file format line.

Progress on M1: #96 is merged, and the file format line of the checklist is done.

rupg-file now has the page table with the 48-bit physical page and the 16-bit write tag, the extent classes E0 to E4, and the free space map with a 1024-bit map for each arena of 16 MiB. Each page kind of this crate has a text form that parses back into the same sealed page.

Two spec changes came out of this work. Extents are now aligned inside their arena and not to page 0, because the arenas start at page 3. A page table node and a free space map page hold their physical number in the logical page field, so the misdirected write check also covers them.

Next: rupg-buffer, the buffer manager with the memory limit and the PageAccess trait.

Progress on M1: #97 is merged. It is the first of two PRs for the buffer manager line, so the line stays open.

rupg-file now has the PageAccess trait with the optimistic, shared and exclusive modes. rupg-buffer has BufferPool with the vmcache state word, a clock that writes dirty pages before it evicts them, and a fixed table of frames that it reserves from the memory budget.

The thread test found a lost update when two threads wrote back the same page at the same time. Each frame now allows one write of its page at a time, and spec/08 §8.8.2 says why.

Next: the virtual memory window of spec/08 §8.8.1 on Linux and macOS, and the reclaimer that gives clean frames back to the budget. That PR closes the buffer manager line.

Progress on M1: #98 is merged, and the buffer manager line is done.

BufferPool now uses the window of spec/08 §8.8.1 on Linux and macOS. The bytes and the state word of logical page n are at index n, so a hit needs no lookup. The pool starts at shared_buffers, grows from the memory budget 64 pages at a time, and gives clean pages back when another consumer needs the memory. Windows and Miri use the fixed table of #97.

The state numbers changed so that a zero word is an evicted unit. The state word region needs no setup at open.

Next: the out-of-place page writes and the checkpoint of spec/08 §8.6, with the store of the file behind the Store trait.

The rupg facade is in (#120). Database::open opens or makes a .rupg file and replays the log when the file was not closed cleanly. create_table makes a table with typed columns, and a Transaction does insert, update, delete, get and range scan by row id. The catalog is one page that each checkpoint writes. The crash test of the facade runs 30 power cuts over 6 seeds with tables that come, checkpoints that the log size starts and a transaction that is open at the cut, and each acknowledged commit is in the file after each cut. The next PR adds rupg check.

rupg check FILE is in (#121), with rupg::check in the facade. It opens the file to read and does not replay the log. It checks the header slots, the page table, the free space map, the catalog page, the tree and each row of each table, that each logical page in use belongs to the catalog or to one table, and each block of the log after the redo position. The crash test of the facade now runs the check after each power cut. M1 has no segments and no indexes, so the check of those comes with M4 and M6. The next PRs are the larger crash run, the fuzz targets and the loom tests.

Release 0.0.9 is tagged as v0.0.9 (#122). It adds the rupg facade with the M1 Rust API (#120) and rupg check (#121). No crate is published. The next PR adds the T8 crash harness in tests/crash, which builds crash files at each sync point and counts the distinct ones.

The T8 crash test is in (#123), in the new crate tests/crash. A seeded M1 workload runs through the Rust API on the simulated disk, with commits, rollbacks, a transaction that stays open across other commits, checkpoints, and close and open. Before each sync of the file, the test builds crash files from the writes that are not synced: every subset of 8 writes or fewer, and for more writes the prefixes in both orders, the torn prefixes and a seeded sample. A crash file with the same bytes as an earlier one counts once. Each crash file must open with exactly the acknowledged commits, or those and the one commit that was in progress at the cut, and rupg check must report no error.

The count for the exit item: 1,021,877 distinct crash files from 436 seeds (seeds 0 to 435), 92,744 sync points and 70,110 commits, with no lost commit, no extra commit and no error from the check. The run took 648 seconds on 10 threads of a Mac at commit bcae64d, which is the tree of #123. The command is cargo run --release -p rupg-crash -- --files 1000000. A run of 28,538 files on Linux also passed. cargo test runs a short workload on two seeds, and the nightly workflow runs 100,000 files from a new first seed each night.

Two speed fixes came with it. The simulated disk now shares chunks of 64 KiB between a fork and a sync, and Options::window_pages lets a test make a small window, because the default reservation took about 10 ms to make and to free. On Linux, Rust zeroes an aligned allocation with its own writes, so the 8 MiB pool of rupg check touched 2,048 new pages on each check. The check now uses 64 frames.

The harness has one log ring, so the case of section 21.9.2 where one ring has its last write and another does not comes with more rings. Misdirected writes are not in the plans yet. The next PRs are the fuzz targets and the loom tests.

The three M1 fuzz targets are in (#124), in the separate fuzz/ workspace: file_open, page_decode and log_replay. All start from one base file on the simulated disk with 32 commits before a checkpoint and 16 after it, and no close, so each open replays the log. file_open changes any byte and can cut the file, and an open must give the rows after one of the commits. page_decode changes a hot page and seals it again, so the decoders see the bad bytes. log_replay changes the log after the redo position, and an open must give the rows after a commit at or after the checkpoint, or XX001. Each target also runs rupg check.

The first runs found two bugs, and #124 fixes both. A file of zero bytes with create off opened as a new empty database, so a file that a cut made empty lost its data with no error. It now gives 58P01. A leftmost child number in an inner page that pointed to the root made the tree descent loop. Each descent now checks that the level goes down at each step and gives XX001 when it does not.

After the fixes, each target ran for 5 minutes with no find. The run for the exit item started at 19:56 on a Mac from commit 189cd63, which is the tree of #124: 2 workers for each target for 12 hours, so 24 CPU hours for each target, with -timeout=1 -rss_limit_mb=2048. The nightly workflow also runs each target for 20 minutes. The next PR is the loom tests for the buffer latches and the log ring reservation.

The loom tests are in (#125), and a new CI job loom runs them on each change. The latch tests include latch.rs a second time with the atomics of loom, because the pool keeps its state words in the memory of the window, where a loom atomic cannot live. They check that a writer excludes the other latches, that shared latches count their readers, and that an optimistic read that passes still saw the page of one version. The ring test runs 2 or 3 threads that each place a block and flush to its end, and each thread must then find every block before the durable position in the store.

Each test fails when the code has a bug on purpose: no fence in still or try_exclusive, a shared latch on an exclusive frame, or a flush that does not mark itself as running. The last one first passed. Loom reorders only the steps that use one loom object, and the store is not one, so loom never ran another thread between the unlock and the write. The ring now touches an IoMark before each write and sync. It is an atomic under loom and an empty type in other builds. With 3 threads the full search took 527 s, so that case bounds the preemptions at 2.

The 24 CPU hour fuzz run is at about 2 hours with no find. The next PR is the runs with dm-log-writes and LazyFS on ext4 and XFS.

Release 0.0.10 is tagged as v0.0.10 (#126). It adds the T8 crash test (#123), the M1 fuzz targets (#124) and the loom tests of the latch and the log ring (#125). It also fixes the two bugs that the fuzz targets found: a file of zero bytes with create off now gives 58P01, and a tree descent gives XX001 when a child number points up the tree. No crate is published. The next PR is the runs with dm-log-writes and LazyFS on ext4 and XFS.

The crash tests on real kernels are merged in #127 (spec/21 section 21.9.3). tests/realdisk/logwrites.py runs the M1 workload on ext4 or XFS over dm-log-writes with a mark after each acknowledged change, then replays the log and checks the file at a sample of flush, FUA and mark entries and of the entries between them. tests/realdisk/kill.py kills the workload with SIGKILL at random points, and with --lazyfs it also drops the data that was not synced. With seed 7 and 200 steps, ext4 passed 300 check points of 1746 log entries and XFS passed 300 check points of 839 log entries. 100 SIGKILL rounds and 100 LazyFS rounds also passed. A build with no fdatasync failed the dm-log-writes and LazyFS tests. The nightly workflow runs all of them in the new realdisk job. At M1 the SIGKILL test uses the key-value workload, because there is no TPC-C yet.

Three PRs for the M1 numbers are merged.

Report the bytes of the log in rupg check #128: rupg check reports log bytes, the bytes of the log blocks that an open replays. The M1 benchmark uses it to show the size of the log before it times a recovery.
Read each log ring once in recovery and use the CRC32C instruction #129: the log checksum uses the CRC32C instruction (SSE 4.2 on x86-64, the CRC extension on AArch64), and recovery reads each ring one time. The scan keeps only the block headers, and Recovery::for_each_safe gives the safe blocks to replay and to rupg check.
Write a PAX leaf in place for an update that keeps the value lengths #130: an update in the hot store that keeps the length of each value writes the PAX leaf in place. Before, each update record decoded and encoded the whole leaf.

With rupg-bench m1 --steps recovery --log-mib 512 on my laptop (Apple M-series, file in the page cache), the open of 0.5 GiB of log takes 0.48 s, about 1 GiB/s on one thread. It took 0.89 s at #129. The budget of spec/11 is 1 GB/s with 16 cores. Spec/24 Q73 stays open for inserts, deletes, updates that change a length, and a cold disk on Linux.

The fuzz run stopped. The disk of the laptop became full at about 01:00, and libFuzzer could not write its files in fork mode. The file system did not have space for 25 minutes of the second part of the run. The one timeout input of file_open from that time runs in 60 ms, so it is not a find. Because #129 and #130 change the code that the targets run, I started the 24 CPU hours again at 238dd51 with the old corpora: each target runs with -fork=2 for 12 hours. file_open is faster after #130 (275 inputs per second on the corpus, 129 before). The 7.45 CPU hours of the first part at 189cd63 had no find, but I do not count them.

The M1 numbers are in tamnd/rupg-bench#22, from rupg-bench m1 with the facade at 238dd51. Both machines are shared and have no local NVMe, so these are smoke runs and not baselines.

	server1 (4 cores)	server2 (6 cores)
commit latency at one writer, p50	3098 us	2029 us
commit latency at one writer, p99	35891 us	6219 us
commits per second, one writer per core	541	1241
empty file after a clean close	80.05 MiB long, 300 KiB allocated	80.05 MiB long, 300 KiB allocated
open after 1 GiB of log, cold cache	9.40 s (0.11 GiB/s)	4.09 s (0.25 GiB/s)

The commit numbers follow the fdatasync time of the shared disks. gpc is not available, so the commits per second on gpc are not measured. I ticked the line because the driver and the four numbers exist, and the run on gpc is one command when the machine is ready: rupg-bench m1 --dir run --machine gpc --report reports.

The empty file is over the budget of spec/17 §17.10. Its length is 3 header pages, one arena of 16 MiB for the pages and the 4 extents of 16 MiB of the log ring. The file is sparse, and 300 KiB is allocated. Spec/17 §17.5 says that the library releases each ring at a clean close and truncates the file after its last used extent, and that is the work of M9. Even then, one arena of 16 MiB stays, so Q30 (#43) must also give the library a smaller extent. I added this to #43.

Recovery: on server1 the open of 1 GiB of log took 15.33 s at aed939c and takes 9.40 s at 238dd51, after #129 and #130.

The fuzz run at 238dd51 is complete. Each target ran with -fork=2 for 12 hours, so each one has 24 CPU hours. No target found an input that crashes, runs out of memory or times out, and the artifact directories are empty. I ticked the line.

target	time with 2 workers	CPU hours	inputs run	coverage at start and end	corpus at start and end	oom/timeout/crash
`file_open`	43291 s	24.05	24274976	3951 to 3952	218 to 263	0/0/0
`page_decode`	43296 s	24.05	47445612	4144 to 4162	537 to 663	0/0/0
`log_replay`	43282 s	24.05	37795038	3722 to 3722	83 to 97	0/0/0

The coverage did not change much in the last hours, so the corpora are close to full for these targets at this commit. The next step for M1 is the release 0.1.0.

PR #168 is merged. It adds cargo xtask lifts, which the close checklist of spec/23 section 23.18 needs. The only lifted file is rupg-file/src/checksum.rs. rudb has 33 commits to its source file after the lift, but none of them changes the checksum functions or their test vectors, so the file records the review. With a full rudb clone the task reports no change that is not reviewed. The next step is the instruction count runner of spec/21 section 21.14, which is also a line of the close checklist. Then comes the release 0.1.0.

The instruction count runner of spec/21 section 21.14 is in PR #169. cargo xtask bench runs six cases (insert, get, scan, update, delete and commit) under perf stat -e instructions:u and applies the budgets of 3 percent for one case and 1 percent for the total. The first counts are in xtask/icount.txt, from an AMD EPYC virtual machine with rustc 1.98.0. A second run changed each case by 0.01 percent or less. The total is 2,715,287,883 instructions.

PR #170 repairs the documentation job of CI. Three doc comments linked to a private item or to a name that is both a function and a macro, so cargo doc with -D warnings failed on main. The other CI jobs passed. From now on the check on the test servers runs cargo doc too, so a broken link does not get to main again.

M1 close report

M1 is done except for the publication of the crate names on crates.io, which waits for a decision of the project owner (Q70, #83). Release 0.1.0 is tagged as v0.1.0 from #171 at 573a5a4. No crate is published.

The checklist of spec/23 section 23.18

Item	From	Answer
Each gate has a number with the five parts of document 02 section 2.2	M2	Does not apply. M1 has no gate.
Each pass count is at or above its ratchet	M2	Does not apply. The ratchets start at M2.
Each fuzz target has its CPU hours with no open find	M1	Done. `file_open`, `page_decode` and `log_replay` ran 24.05 CPU hours each at `238dd51` with no crash, no timeout and no out of memory. See #2 (comment).
The crash count of document 21 section 21.9.4 with no lost commit	M1	Done. 1,021,877 distinct crash files from 436 seeds at `bcae64d` (#123), with no lost commit, no extra commit and no error from `rupg check`. See #2 (comment).
No open bug of the classes wrong answer, lost commit or corrupt file	M1	Done. At this report, 0 issues are open with `kind/bug`, 0 with `kind/wrong-answer` and 0 with `kind/security`.
The instruction count set has the new queries	M1	Done. #169 adds the set and `cargo xtask bench`. M1 has no SQL, so the six cases use the Rust API: insert, get, scan, update, delete and commit. The counts are in `xtask/icount.txt`.
Each baseline that a gate used was remeasured within 30 days	M2	Does not apply. M1 has no gate.
The lines of each crate against its budget	M1	Done. See the table below. No crate is over 150 percent of its budget.
`cargo xtask lifts` reports no rudb change that is not ported or declined	M1	Done. #168 adds the task. At rudb a98ab976 it gives "1 lifted files, no rudb change that is not reviewed".
Each changed document is updated, and each miss has an entry in document 24	M0	Done. The changelog has a 0.1.0 section, and `CONTRIBUTING.md` has the new tasks. #172 records the M1 misses in document 24: Q30, Q31, Q38 and Q40 did not close at M1 and each entry says why, Q69 has the noise that M1 measured, Q70 waits for the owner, and the new Q74 is the size of an empty file. Q73 already had the replay speed.
The release `0.M.0` is tagged, and the reproducible build matched	M1	Done. `v0.1.0` at `573a5a4`. Two release builds of `rupg` in two directories on server1, with rustc 1.98.0, gave the same SHA-256: `f90c3eaebabca3c698fdf774d957e19cf8cdc4cb991436aac853f5aafaf89d21`.
Every suite gives the same answers with every summary deleted	M4	Does not apply.
The layout equivalence oracle ran each night	M4	Does not apply.

Lines against the budgets of spec/22 section 22.4

Counted at 573a5a4 with the method of spec/22 section 22.14 (wc -l of the .rs files under src), less the generated tables of section 22.8.

Crate	Lines	Generated, not counted	Budget	Use
`rupg-common`	819	868	8,000	10%
`rupg-types`	9,743	4,183	45,000	21%
`rupg-platform`	3,562	0	12,000	29%
`rupg-file`	3,919	0	10,000	39%
`rupg-kernels`	163	0	30,000	0%
`rupg-buffer`	3,849	0	8,000	48%
`rupg-tree`	1,229	0	10,000	12%
`rupg-log`	2,489	0	14,000	17%
`rupg-hot`	1,941	0	15,000	12%
`rupg-table`	314	0	14,000	2%
`rupg-txn`	2,436	0	22,000	11%
`rupg`	1,301	0	5,000	26%
`rupg-cli`	151	0	12,000	1%

The M2 crates that have code are also under budget. The largest use is rupg-wire at 67 percent (5,365 of 8,000) and rupg-server at 46 percent (3,709 of 8,000).

The exit criterion

The M1 numbers are in Add the m1 command and the first M1 numbers of rupg rupg-bench#22. The commits per second on gpc are not measured, because the machine is not available. The empty file is over its budget and is now Q74.
1,021,877 crash files ran with no lost commit.
The three fuzz targets ran 24 CPU hours each with no find.
This report answers each line of the checklist.

Still open

Publish the crate names on crates.io, and the line of the crates that first ship. Both wait for the decision of the owner on Q70 (Q70: When are the crate names published? #83).

Navigation Menu

Repository navigation

M1: The file #2

Why

The work

Exit criterion

Open questions

Harness work

Depends on

Spec

21 remaining items

M1 close report

The checklist of spec/23 section 23.18

Lines against the budgets of spec/22 section 22.4

The exit criterion

Still open

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

M1: The file #2

Description

Why

The work

Exit criterion

Open questions

Harness work

Depends on

Spec

Activity

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

21 remaining items

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 7, 2026

tamnd commented on Oct 8, 2026

tamnd commented on Oct 8, 2026

tamnd commented on Oct 8, 2026

tamnd commented on Oct 8, 2026

tamnd commented on Oct 8, 2026

M1 close report

The checklist of spec/23 section 23.18

Lines against the budgets of spec/22 section 22.4

The exit criterion

Still open

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions