Three systems on three subdomains. The B+Tree and its latch crabbing, the CRDT and its operation log, the join-order search and its cost model — each one written rather than imported. The frameworks are around the edges.
The three systems were chosen so their hard parts do not overlap. Between them they cover the trees, the graphs and the dynamic programming that most backend work never reaches for — and in every case the algorithm is written, not pulled from a crate.
CRDTMARGINAL
Concurrent edits from several people merge to one document with nothing to resolve by hand. Written from scratch — importing it would leave nothing learned.
Lexer → parserCAIRN
A hand-written lexer and recursive-descent parser taking SQL text to an AST. No parser generator anywhere in the pipeline.
Join-order DPCAIRN
best[S] filled bottom-up over relation subsets with a real cost model, then a genetic fallback once the table stops fitting.
B+Tree & latch crabbingCAIRN
A reader drops the parent latch the moment the child is latched, so descents overlap instead of serialising — the hardest part of a B+Tree to get right.
Buffer poolCAIRN
LRU-K, ARC and Clock run against the same access trace, side by side — so the difference between them is visible rather than asserted.
ARIES recoveryCAIRN
Write-ahead logging with the three ARIES passes, and a crash you can inject anywhere on the timeline to watch them run.
RaftCAIRN
Leader election, log replication and leases, hand-rolled. Holds cluster metadata only — deliberately kept off the query hot path.
RopeMARGINAL
A balanced tree over text, so splicing into the middle of a long document is O(log n) instead of a full copy.
HNSWBOTH
A navigable small-world graph in layers, traversed by greedy beam search — semantic search in marginal, a vector worker in cairn.
Currently looking for Rust work.
Backend and systems roles — storage engines, query execution, distributed coordination. The kind of problem where the algorithm is the product, not the glue around it.