db-11 — Execution

What was built, in the order it was built.

1. Rust (src/rust)

  • Cargo.toml declares lib crate pager11 and binary pagerctl. Edition 2021; release profile lto = "thin", codegen-units = 1.
  • src/lib.rs contains:
    • Constants MAGIC: &[u8;16] = b"DSE-PAGER-v1\0\0\0\0", HEADER_LEN = 24.
    • Frame { pid, data: Vec<u8>, dirty, prev: Option<usize>, next: Option<usize> } plus Pager { file, page_size, num_pages, capacity, frames: Vec<Frame>, free: Vec<usize>, map: HashMap<u32,usize>, head/tail: Option<usize>, hits, misses }.
    • Pager::open(path, page_size, capacity), ::allocate(), ::read(pid), ::write(pid, bytes), ::flush(), ::cache_hits(), ::cache_misses(), ::num_pages().
    • LRU helpers promote(frame_idx), evict_tail(), admit(...) operating on the indexed doubly-linked list.
    • Hand-rolled SHA-256 (FIPS 180-4) so the lib has no dependencies. sha256_hex(bytes) and sha256_file(path).
    • SplitMix64 PRNG and run_workload(path, page_size, capacity, pages, ops, seed, scenario) -> Pager.
    • 10 inline #[cfg(test)] tests: header round-trip, allocate monotonic, read-after-write within and across eviction, dirty survives eviction, flush is idempotent, hits/misses counts, scenario determinism (sequential), scenario determinism (random), scenario determinism (mixed), SHA-256 empty-string test vector.
  • src/bin/pagerctl.rs: order-independent arg parser (args.windows(2) lookup). Subcommands init <path> [--page-size N] and workload <path> --seed S --ops N --pages P --cache C --scenario {sequential|random|mixed} [--page-size N]. Workload prints sha256_file(path) to stdout with no trailing newline.

2. Go (src/go)

  • go.mod module github.com/10xdev/dse/db11, Go 1.22.
  • pager.go ports the Rust API one-for-one. Uses container/list for the LRU chain and map[uint32]*list.Element for lookup. SHA-256 via crypto/sha256 (stdlib is fine; the cross-language comparison is on the file bytes, not the digest algorithm).
  • pager_test.go mirrors the 10 Rust tests plus an 11th, TestWorkloadMatchesCanonicalHashes, that bakes in the three canonical hashes (A/B/C) and runs all three scenarios in a loop. This is the test that catches "Go silently disagrees with Rust" regressions before the cross_test script even runs.
  • cmd/pagerctl/main.go is the matching CLI. Custom flag parser (findFlag, firstPositional, mustU64, mustInt) because flag.Parse stops at the first non-flag argument and the shared script passes <path> before the flags.

3. C++ (src/cpp)

  • CMakeLists.txt builds:
    • pager11 (static lib from src/pager.cc + src/sha256.cc).
    • pagerctl (executable linking pager11).
    • test_pager11 (ctest target linking pager11).
    • Flags: -Wall -Wextra -Wpedantic -Werror -O3 -DNDEBUG in Release.
  • src/pager.h, src/pager.cc: factory function Pager::open(...) returning a std::unique_ptr<Pager>. std::list<Frame> for the LRU chain; std::unordered_map<uint32_t, std::list<Frame>::iterator> for O(1) lookup. std::list::splice for promotion.
  • src/sha256.h, src/sha256.cc: FIPS 180-4 SHA-256 in ~120 lines.
  • src/pagerctl.cc: matching CLI. Includes <unistd.h> for getpid() (used by tests for unique tmp paths); the omission of that header was the only build error during initial bring-up.
  • tests/test_pager11.cc mirrors the Rust tests; uses #undef NDEBUG before <cassert> so asserts fire under Release. Prints OK 11 tests on success. Wired into ctest as a single test case.

4. Scripts

  • scripts/verify.sh:
    1. Rust: cargo test --quiet.
    2. Go: go test ./....
    3. C++: cmake -S … -B build -DCMAKE_BUILD_TYPE=Release && cmake --build build -j && ctest --test-dir build --output-on-failure.
    4. Exits 0 only if all three are green; prints === OK ===.
  • scripts/cross_test.sh:
    1. Builds Rust/Go/C++ pagerctl binaries (cargo release, go build, cmake+make).
    2. Scenario A sequential, seed=42, pages=32, cache=8, ops=200, page_size=256: pagerctl workload <tmp> … per language; sha256
      • size comparison against baked-in expected hash.
    3. Scenario B random, seed=7, pages=64, cache=8, ops=500, page_size=256: same shape, different hash.
    4. Scenario C mixed, seed=2024, pages=128, cache=16, ops=1000, page_size=512: same shape, different hash.
    5. Spot-check: read the first 20 bytes of Scenario A's file and assert they equal 4453452d50414745522d76310000000000010000 (magic DSE-PAGER-v1\0\0\0\0 + 0x00000100 for page_size = 256 LE).
    6. Print === ALL OK ===.

What was deliberately not built

  • Free-list / page reclamation. allocate() only grows the file. db-21 (storage engine advanced) introduces a free-list page.
  • Page checksums. No CRC32 footer. db-15 will add one when SQLite-compatibility demands it.
  • mmap backend. All I/O goes through pread/pwrite. An mmap-based variant is a possible db-21 follow-up.
  • Concurrency. No latches; the pager assumes a single thread. db-13 (MVCC) and db-17 (Raft) introduce concurrent access at higher layers.
  • WAL. db-11's pager has no WAL; durability is via in-place write + fsync at flush(). db-03 already covered WAL and db-13 will add a transactional WAL on top of the pager.
  • Compression / encryption. Out of scope; the page bytes are whatever the caller wrote.