A database written in Rust

FigDB is a database. The storage engine, the crash recovery, and the network protocol are written here, in Rust, instead of being borrowed from RocksDB, etcd, or a Raft library.

What runs today is one server. It keeps an on-disk log and sorted tables, and it speaks over TCP. That path is crash-tested. A write is acknowledged only after the log has been synced to disk. Copying data to other servers, and multi-statement transactions, are the next pieces. They are not in this tree yet.

Start with Introduction, then Architecture. Measured numbers are in benchmarks/. Where this prose and the code disagree, the code and its tests win.

Quick start

cargo run -p fig-server --bin fig-server -- --dir /tmp/fig-srv --addr 127.0.0.1:7001
cargo run -p fig-server --bin fig-cli -- put k1 v1
cargo run -p fig-server --bin fig-cli -- get k1
./scripts/check.sh   # fmt --check + clippy -D warnings + full test suite
FigDB write pathSingle-node engine today; sharded replication next. FigDB write path 01 Clients CLIs and bench tools over TCP JSON-lines fig-cli fig-bench 02 Storage engine WAL-backed memtable into LSM tables WAL sync = ack flush + compact 03 Consensus Deterministic Raft core, simulation-tested R3 wiring next

1. Introduction

This chapter states what the system is, what this manual covers, and how to navigate the rest of the documentation.

1.1. Purpose and scope

The system under documentation is an ordered, persistent key-value store with crash-safe durability semantics. This manual describes its architecture, component design, external interfaces, verification strategy, build process, measured performance, and known limitations.

This manual describes the system as checked in. Statements about future work (replication, transactions, sharding) are marked as such and are not part of the implemented behavior. See Known Limitations for the explicit list of what is not claimed.

1.2. How to read this manual

The recommended reading order is:

  1. Start with the architecture overview (Architecture).

  2. Drill into component design (Design) as needed.

  3. Consult interfaces (Interfaces) and the programming model (Programming Model) when writing client code.

  4. Check verification (Verification) before changing storage logic.

1.3. Conventions

Key terms used throughout this manual:

  • Acknowledged — a write the system promises to survive a crash.

  • Prefix — the initial contiguous run of a log; recovery replays a prefix.

  • Litter — files left behind by a crash that recovery must ignore or reap.

Note
When prose and code disagree, the code plus its tests win until the documentation is updated in the same milestone.

The Markdown files already in this repository remain the canonical prose record. This manual summarizes them and links to them:

  • architecture/overview.md — system topology and write lifecycle

  • architecture/status.md — what is actually landed, crate by crate

  • architecture/durability.md — acknowledgement rule and crash windows

  • architecture/consistency.md — isolation target and validation

  • adr/ — architecture decision records

  • correctness/strategy.md — reference models and testing strategy

  • testing/strategy.md — simulator, chaos, soak, and CI split

  • testing/inventory.md — what each test file proves

  • benchmarks/ — measured results only

2. Architecture

This chapter describes the system topology, the implemented components, and the write lifecycle vocabulary used everywhere else in this manual.

2.1. System topology

The target topology is a sharded, replicated store. What exists today is the bottom of the storage engine running as a single-node process (the layers in Implemented components and their crates.), plus Raft consensus through durability: a deterministic core, a seeded simulation harness, and crash-safe persistence — not yet wired to the server (R3). See ADR-006 for the R1/R2/R3 split.

Target topology. Clients then a router then transactions then shards then a Raft group then the storage engine. Only the storage engine runs today.
Figure 1. Target write path. The storage engine is the only box that runs on the server today.
Implemented write path from the client through the write-ahead log and memtable to sorted tables.
Figure 2. Write path of the implemented single node.

2.2. Components

Table 1. Implemented components and their crates.
Component Crate Responsibility

Ordered KV model

fig-core

In-memory GET / PUT / DELETE / SCAN over bytes; oracle and limits

Write-ahead log

fig-wal

Framed, checksummed records; segments; replay; crash recovery

Storage engine

fig-storage

WAL-backed memtable; flush; manifest publishing; compaction; merged reads

Immutable tables

fig-sstable

Checksummed blocks, index, footer, Bloom filters, tombstones

Server and CLI

fig-server

TCP JSON-lines API; snapshot reads; background compaction timer

Raft consensus (unwired)

fig-raft

Deterministic core; seeded sim; crash-safe Store; R3 wiring is next

2.3. Write lifecycle vocabulary

The following terms are never conflated in this manual:

received -> replicated -> committed -> persisted -> applied -> acknowledged

There is no replication yet, so the only acknowledgement point is Wal::sync(): everything at or before the last sync survives a crash. The exact rule is stated in architecture/durability.md and summarized in Design.

3. Design

This chapter records the per-component design: what each layer stores, what it promises, and where the crash windows are.

3.1. Write-ahead log

The log is a sequence of framed records carrying dense sequence numbers. Each frame carries a checksum. Replay reads a prefix:

  • a clean prefix replays fully,

  • a torn tail (short read) is truncated and never replays,

  • a corrupt frame stops replay; the suffix is truncated.

Wal::open(&opts) -> (Wal, Vec<WalEntry>, RecoveryReport)
wal.append_put(key: Vec<u8>, value: Vec<u8>) -> u64  // dense seqno
wal.append_delete(key: Vec<u8>) -> u64
wal.sync() -> ()                       // acknowledgement point
wal.synced_seq() -> Option<u64>
Segment::replay(path) -> (ReplayOut, u64)
Note
Sequence numbers stay dense across reopen and rotation, so no write is ever replayed twice or skipped.

3.2. Memtable engine

The engine applies PUT to the WAL first, then to the in-memory table. Restart replays the log into a fresh table. Rejected writes leave no trace.

3.2.1. Flush and manifest publishing

The live table set is defined by tables/MANIFEST (version 1), not the directory listing. Flush publishes in order: write sst-000007.sst.tmp (zero-padded 6-digit ids), sync, rename, directory fsync, update MANIFEST (MANIFEST.tmp, sync, rename, directory fsync), then delete WAL segments.

3.2.2. Crash windows

  • Crash before rename: only *.tmp litter, deleted at open.

  • Crash after rename, before manifest: unlisted orphan .sst, deleted at open; the WAL still holds the data.

  • Crash after manifest, before WAL deletion: table and WAL overlap as harmless duplicates; the next flush clears the WAL.

Warning
Never treat the directory listing as the live set. An unlisted .sst file is either litter or an orphan and must be reaped, never merged into reads.

3.3. SSTables and compaction

Tables are immutable: checksummed blocks, an index, a footer, per-table Bloom filters, and tombstones for deletes. When 8 tables accumulate, the oldest batch of 8 is merged (size-tiered oldest-batch policy) with the same publish protocol as flush, so compaction crash windows reduce to the flush cases above.

Tombstone garbage collection runs only on full merges with an empty memtable, where no older layer can exist below a dropped tombstone, so a dropped tombstone can never resurrect a shadowed key.

3.4. Raft consensus

The core (fig-raft::Node) is a pure state machine: no I/O, no threads, no clock. Inputs are messages plus timer events; outputs are outbound messages plus committed entries. Elections, log matching (truncate-then-append, no holes), current-term commit advancement, and exactly-once in-order application all live here (R1; see ADR-006).

Durability is explicit (R2). The core reports what changed via take_dirty; persist::Store writes current_term, voted_for, and the log to raft-state.json atomically (tmp, sync, rename, directory fsync) and replays it into Node::restore on restart. Heartbeats mark nothing dirty, so steady-state leadership costs no disk write. An uncommitted suffix may be overwritten by a new leader — it is never applied before commit.

A seeded simulation harness (virtual ticks, partitions, drops) proves single-leader election, ordered replication, failover preserving the committed prefix, and partition healing deterministically on fixed seeds.

Note
The core is not yet wired to the server. Client writes still ack on Wal::sync() without replicating; majority-ack replication is R3.

3.5. Decision records

The ADRs stay in docs/adr/ rather than the chapter sidebar.

  • docs/adr/001-memtable-structure.md

  • docs/adr/002-manifest-publishing.md

  • docs/adr/003-compaction-policy.md

  • docs/adr/004-tcp-server-protocol.md

  • docs/adr/005-concurrency-model.md

  • docs/adr/006-raft-replication.md

4. Interfaces

This chapter specifies the external interfaces: the wire protocol and the configuration limits. It is the contract between the server and its clients.

4.1. Wire protocol

The server speaks newline-delimited JSON over TCP: one request line gets one response line. Keys and values are arbitrary bytes, so they travel base64-encoded (standard alphabet) in *_b64 fields. Every request carries a seq number for pipelining; every response echoes that seq with ok, and failures add a stable code (plus a human message) so clients branch on codes, never on text.

{"seq":1,"op":"put","key_b64":"ay4=","value_b64":"dg=="}
{"seq":1,"ok":true}
{"seq":2,"op":"get","key_b64":"ay4="}
{"seq":2,"ok":true,"value_b64":"dg=="}
Table 2. Wire requests (see ADR-004 for rationale).
Request Fields Effect

put

key_b64, value_b64

Stage write; acknowledged at the next sync

get

key_b64

Snapshot read; missing keys return NOT_FOUND

delete

key_b64

Stage tombstone; response reports removed

scan

start_b64, end_b64, limit

Ordered range read; limit defaults to 1000, clamped to 1..10000

sync

(none)

Persist the staged prefix; defines the acknowledgement point

flush

(none)

Force memtable flush into a manifest-published table

compact

(none)

Force a merge of live tables; response reports merged

stats

(none)

Return flushes, flushed_records, flushed_bytes, compactions, compacted_records, and live tables

Unknown operations and malformed lines return INVALID_ARGUMENT and the connection stays up; see Verification for the wire gate tests.

Tip
Batch many put requests behind a single sync. Acknowledgement is a prefix property, so one sync covers every write before it.

4.2. Configuration limits

Keys and values are arbitrary bytes subject to fig-core::Config::Limits, validated at the API boundary before they reach the log:

  • maximum key length: 64 KiB (max_key_bytes),

  • maximum value length: 4 MiB (max_value_bytes),

  • maximum decoded request line: 32 MiB (max_request_bytes).

Oversized inputs are rejected with INVALID_ARGUMENT.

5. Programming Model

This chapter shows how client code uses the interfaces from Interfaces: the basic write/read cycle, error handling, and the durability contract in practice.

5.1. Basic write/read cycle

The fastest path is fig-cli, which takes raw UTF-8 strings and handles the base64 framing itself (arbitrary binary keys remain a client-library concern, not a shell concern):

fig-cli --addr 127.0.0.1:7001 put k1 v1
fig-cli get k1
fig-cli scan a z 100
fig-cli stats

The equivalent raw session over TCP (fig-server defaults to 127.0.0.1:7001), one JSON object per line:

{"seq":1,"op":"put","key_b64":"azE=","value_b64":"djE="}
{"seq":2,"op":"sync"}
{"seq":3,"op":"get","key_b64":"azE="}

In application terms the cycle is:

  1. Connect to the server over TCP.

  2. Send put requests, each tagged with a client-chosen seq.

  3. Send sync to acknowledge the staged prefix.

  4. Send get or scan to read from a snapshot; match responses to requests by the echoed seq.

5.2. Errors

All failures use shared error kinds (fig-core::Error) surfaced on the wire as stable code strings: bad input is INVALID_ARGUMENT, a missing key is NOT_FOUND. Corruption is fail-safe: replay stops at the first corrupt frame and truncates the suffix rather than surfacing torn data.

5.3. Durability contract

sync is the only acknowledgement point. In application terms:

  • writes before the last successful sync response survive a crash,

  • writes after it may be lost,

  • reads always observe a consistent snapshot of the acknowledged prefix.

6. Verification

This chapter defines what "proven correct" means: reference models, differential tests on randomized operation streams, crash gates, and the continuous gates that enforce them.

6.1. Strategy

Reference models are compared against the implementation on seeded random operation streams: the naive oracle must agree with the real structure on every get and scan, including tombstone behavior. Crash tests plant failures at every publish window and assert that reopen yields exactly the acknowledged state.

Note
Randomized gates use fixed seeds so failures reproduce deterministically.

6.2. Test gates

Table 3. Enforcement gates (unit tests live next to the code; crash tests in tests/).
Location What it proves

fig-core: kv, ops

Roundtrip, ordering, scan bounds; oracle agreement up to 10k ops

fig-wal: record, segment, wal

Frame roundtrip; torn tails read as torn; dense seqnos across reopen

fig-wal/tests/crash.rs

Acked prefix survives seeded crash campaigns; corruption truncates suffix

fig-storage, fig-sstable

Replay, flush, tombstone suppression, Bloom behavior, manifest roundtrips

fig-storage/tests/

Kill/restart, mid-flush litter, and compaction windows reopen clean

fig-server/tests/tcp.rs

Wire roundtrip, garbage-input survival, restart durability, concurrency

fig-raft/tests/raft_sim.rs

One leader per term on seeds; ordered replication; solo self-election; minority isolation; failover preserving the committed prefix

fig-raft: persist

Vote + entries survive reopen; heartbeats write nothing; tmp litter reaped, corrupt state is Corruption; uncommitted suffix never applied pre-commit

The local gate runs everything:

./scripts/check.sh   # fmt --check + clippy -D warnings + full test suite

Two operational gates run outside cargo test: fig-bench --verify-only recomputes the oracle for a load run with zero shared state, and scripts/soak.sh repeats load/sync/SIGKILL/restart cycles, re-verifying every earlier cycle’s keys after each restart.

Warning
Storage logic changes must update the corresponding gate in the same commit. A passing build with a weakened oracle is a regression, not an improvement.

7. Implementation

This chapter covers the repository layout, the build, and the continuous integration gates.

7.1. Repository layout

crates/fig-core/     errors, config/limits, KV oracle, tracing
crates/fig-wal/      the log (record / segment / wal) + crash tests
crates/fig-storage/  memtable engine + LSM flush/merge + equivalence gates
crates/fig-sstable/  immutable tables + indexed reads + differential tests
crates/fig-server/   TCP JSON-lines server + fig-cli + wire tests
crates/fig-raft/     deterministic core + sim + crash-safe persistence
docs/                manual source (this system) + existing Markdown notes
scripts/check.sh     local gate: fmt + clippy + tests

7.2. Building and testing

cargo build --workspace          # debug build of all crates
cargo test --workspace          # full test suite
./scripts/check.sh               # canonical gate: fmt + clippy + tests
make docs                        # build this manual into build/docs/

Release builds use link-time optimization ([profile.release], single codegen unit); see benchmarks/ for measured release-vs-debug comparisons.

Tip
Run ./scripts/check.sh before every push. CI mirrors it, plus the dedicated WAL crash gate.

8. Performance

This chapter explains how performance is measured and what the current numbers show. Measured results live in benchmarks/; this chapter states the method and the interpretation so numbers are never read out of context.

8.1. Method

All runs use fig-bench (per-operation latency in microseconds, p50/p99 over the full run) against a local server with a stated durability policy (for example, an explicit sync every 500 puts, so every measured put is acknowledged). Hardware, compiler, dataset, and durability policy are recorded with each run because throughput is meaningless without them.

Throughput and latency are related by the offered load. For a single sequential client over n operations with mean latency \(E[L\)]:

\[T = \frac{n}{\sum_i L_i} = \frac{1}{E[L]}\]

With concurrent clients the wall-clock form applies instead (\(T = n / T_{wall}\)), which is why single-client and multi-client figures are reported separately in benchmarks/.

8.2. Reading the results

  • GET throughput is typically round-trip bound; compiler optimization level moves it little.

  • PUT throughput is execution bound (flush and compaction rewrites), so release optimization and moving merges off the write path dominate.

  • Foreground merges stall writes visibly in p99/max; background compaction trades that tail for steady throughput.

Note
Concurrency figures are loopback-only unless stated otherwise, and no power-loss testing is claimed. See Known Limitations.

8.3. Measured runs

Recorded 2026-10-01 on an Apple M3, 16 GiB, rustc 1.98.1. Keys are 14 bytes and values are 64 bytes. sync runs every 500 puts. Full tables: docs/benchmarks/README.md.

PUT and GET throughput for 1 and 8 clients
Figure 3. Run C release throughput, background compaction
p99 latency for inline compaction versus background compaction
Figure 4. p99 before and after moving compaction off the write path

Run B inline compaction, release, 60k keys: PUT 7,960/s (p99 1.74 ms) and GET 10,023/s. The same PUT on the debug build was 4,890/s. Run C, with merges off the write path, reaches 26,987 PUT/s at one client and 59,315 PUT/s at eight. Eight-client GET is 96,013/s. Final compact leaves one 5.0 MB table, about 87 bytes per key, write amplification about 2.1x at this size.

9. Known Limitations

This chapter lists what the system explicitly does not do yet. It exists so no reader infers guarantees from the chapters above.

  • No replication: a disk loss is not survived, only a process crash. The Raft core through durability (deterministic elections, log matching, crash-safe Store) is landed and tested, but it is not wired to the server yet — writes ack on Wal::sync() without a majority round.

  • Single node only: no shards, no Raft groups serving traffic, no distributed transactions.

  • No power-loss testing: kill -9 exercises page-cache-survives crashes; unsynced-tail loss is covered by truncation simulation, not by pulling the plug.

  • No fsync-per-write figures: published runs batch syncs.

  • Checksums exist at the WAL frame level; there are no checksums above it.

  • Benchmarks are loopback-only with a small client count; there are no multi-host latency claims.

Warning
Do not deploy this system where disk loss or multi-node consistency is required. Server replication wiring (R3) is next; it is not here.

When a limitation above is fixed, update this chapter, the affected design chapter, and the corresponding decision record in the same commit.

10. Engineering log

Each note below is the original project log, in chronological order. Open the arrow in the sidebar to jump to an entry.

10.1. 2026-10-01 — FigDB built from ground level up!

About me

I’m Tyrone Marhguy, a Computer Engineering student at the University of Pennsylvania, class of 2028. FigDB is the transactional database I am building in Rust.

I grew up between Kumasi and Accra. In 2021, Achimota School denied me admission because I wear dreadlocks as an expression of my Rastafarian faith. Ghana’s High Court ordered the school to admit me; I finished secondary school there, then came to Penn on a full scholarship. BBC Pidgin and Deutsche Welle covered the case.

I design the architecture, build the boards, and write the software. Tomato is a 32-bit computer with a running FPGA implementation and discrete boards in progress. I also build systems software, including a search engine, a compiler, and a database, and I contribute fixes to open-source EDA tools such as LibreLane, OpenROAD, Verilator, and OpenFPGA. That work has included production software at Aragorn AI and battery-management hardware at Vero Electric.

Hardware

Software and systems

Open source

See open-source work for contributions to LibreLane, OpenROAD, Verilator, and OpenFPGA.