Design decisions¶
moraine started from a written design, and every decision since, including every departure from that design, is recorded with its reason in DECISIONS.md. This page summarises the entries that shape the library most; each heading links to the full entry.
Before writing any library code I ran a verification spike: twelve throwaway programs that checked the assumptions the design rests on against delta-rs, object_store, usearch and tantivy. docs/SPIKE.md is the record of how I validated the approach, with the numbers.
Name and licence¶
D1: the design's
working name osdb became moraine. The bare moraine crate name was taken on crates.io, so the
package is morainedb and the library is moraine.
D2: I license
my Rust projects under Apache-2.0 or MIT, and moraine follows.
Commits: delta-rs's format, moraine's protocol¶
D8: the spike showed that delta-rs 1.x commits to S3 with a plain put-if-absent and no DynamoDB lock, so no lock service was needed at all.
D18: I made group commit the default and set a request budget: an append costs one PUT per data file and one conditional PUT of the log entry, with no listing, HEAD or read-back. Checkpoints and log cleanup moved out of the write path into maintenance.
D25: delta-rs's own commit path lists the log and runs post-commit work on every commit, so I wrote the commit protocol in moraine and kept delta-rs for what it does well: the action types, their serialisation, schema conversion and checkpoint loading. It stays confined to one module, which is what makes the budget enforceable and exactly testable.
Performance as a requirement¶
D17: kv0, another project of mine, had measured its delta-rs engine against its Lance engine and found Delta 70 to 86 % slower at logging and slower at start-up and key lookups. A storage engine slower than both obvious alternatives on the paths users touch most has no reason to exist, so I made performance a design requirement instead of a late tuning task. D21 turns that into targets that are acceptance criteria: a feature with a target is not done until the benchmarks show it met, or an entry explains the miss.
Keys, sorted files and caches¶
D19: the original design had no scalar indexes. I added a declared cluster key, files sorted by (cluster key, primary key), file key ranges held in memory, and a key-index sidecar, so a point lookup costs at most one range read per matching file. D20: because data files are immutable, footers, page indexes and key indexes are cached by (path, size) and never invalidated, snapshots are refreshed incrementally, and small tables are held in memory per version.
Contention, and a target I replaced¶
D26 records two contention targets missed in the first table benchmarks, and a jittered pause I tried and reverted because it lowered the median by starving some writers. D28 adds the starvation guard that met the S3 targets at the time. On local disk I dropped the commit p50 target and replaced it with throughput, a p99 bound and every row exactly once, because the median of a fairly served queue is set by the number of writers, not by how fast the log is. D31 records the fair comparison, including where moraine loses, and the S3 p99 target that is now missed; I kept the target rather than loosening it.
Hardening before indexes¶
D29: before sidecar indexes added a parser and many more objects, I put in deterministic corruption fuzz tests that run with the normal tests, a segmentation-invariance simulation, not-found errors that suggest the closest name, AWS SDK credentials and region resolution, and object tags.
Exactly-once writes¶
D32:
kv0's write-ahead log has to be replayed exactly once after a crash or an unknown outcome, so I
pulled caller transaction ids forward from the maintenance work. I chose a txn(app_id, version) builder
that returns a WriteOutcome over an extra argument on every method, because the id is per
write and the result type changes with it. See Exactly-once writes.
Indexes¶
D33:
the bundle header names the kind with 8 ASCII bytes so kinds defined outside the crate need no
central registry; vector columns are List<Float32> because Delta has no fixed-size list; specs
resolve every default at creation so a stored spec never changes meaning.
D34
checks the TurboQuant and xor-filter facts against their sources before code relied on them.
D35
bounds index-build memory with windows of input and estimates taken from measurement.
D36
encodes keys so byte order equals value order, and uses the page section only for files sorted
by the primary key alone.
D37
records the vector benchmark: usearch stays the default because TurboQuant, though far faster to
build and smaller, scans every code and is 3 to 6 times slower at a million rows. It also settles
the defaults that
D16
left open (expansion_search 128, TurboQuant rerank 8) and keeps the D21 vector target, met at
100,000 rows and missed at a million, with the fix planned alongside compaction. See
Benchmarks.
Ambiguous commits and follow-ups¶
D38: a commit error that does not say the write was refused is now treated as ambiguous and resolved through the transaction id, like a timeout; and rows with equal sort keys keep their append order, which is now a documented guarantee. D39 places the follow-ups from porting kv0: named pins instead of general time travel, a public file list on snapshots, concurrent search of a file's graph parts, checkpoints, and Arrow's default list item name.
Maintenance¶
D47:
moraine writes and reads its own Delta checkpoints, at the version in hand, keeping its file tags
in them; opening a table reads _last_checkpoint and lists the log from there.
D48:
compaction runs on moraine's own commit path as a file swap, merges adjacent runs of one level
sorted by cluster and primary key, builds the merged files' sidecars before the commit, and
keeps the file order so equal keys keep their commit order; the same swap is public as
Table::replace_files.
D49:
named pins are a table property plus a manifest of the pinned version's files.
D50:
vacuum and the collectors decide by the store's clock and by the log, never by a listing alone;
leases are generation files fenced through Delta transactions.
D51:
queued writes go through an inbox and a lease-elected ingestor, exactly once per batch.
D52
and D53
close the search items the vector and full-text work left open. The simulation found three
faults on the way, each fixed before maintenance was merged: a stale handle could commit at a version log
cleanup had freed, compaction could commit files vacuum had already taken as orphans, and an
ingest could commit a queued batch twice.
Blobs and index before commit¶
D57: a blob column is a struct of Delta types; keys spread over prefixes by their random bits; a write copies every reference it did not upload, and a value streamed up ahead of a write is committed as it is only through the same handle within the commit deadline; collection marks every file vacuum keeps, not just the current snapshot, so readers of older and pinned versions keep their blobs. D58: every write builds its files' sidecars before the commit, within size and cost limits each index's policy sets. D59 and D60: compaction streams a k-way merge over its sorted inputs, and merges TurboQuant codes instead of rebuilding them. D61: no row of a file within its index's before-commit limits is ever on the exact route; the provisional 5 % share of all rows was measured and missed where small files waited for compaction's graph builds, and stays an open target. D62 has the measurements, and D63 what is left.
The public API¶
D90:
before the first release I shrank the public surface to what applications use, made every
public enum, report and option struct #[non_exhaustive] with setters for the options, gave
plain writes a Committed result, made Error cloneable with other libraries' errors behind
sources, and stated how the 0.1.0 betas are versioned.