Documentation

Architecture

youdaheDB is a distributed SQL database built bottom-up. Every layer sits on the one below and nothing is started before its foundation runs end to end.

            ┌──────────────────────────────────────┐
  clients   │  psql · JDBC · psycopg · any ORM     │
            ├──────────────────────────────────────┤
            │  PostgreSQL wire protocol            │
            │  SQL parser → cost-based planner     │
            ├──────────────────────────────────────┤
            │  MVCC · HLC · 2PC · OCC              │
            ├──────────────────────────────────────┤
            │  hash ring → router → ranges         │
            ├──────────────────────────────────────┤
            │  Raft — one group per range          │
            ├──────────────────────────────────────┤
            │  TCP server · client · CLI           │
            ├──────────────────────────────────────┤
            │  thread-safe engine · group commit   │
            ├──────────────────────────────────────┤
            │  LSM: WAL · memtable · SSTables      │
            └──────────────────────────────────────┘

The two structural decisions worth naming: each shard is its own Raft group, so sharding (capacity) and replication (durability) stay orthogonal; and the storage engine is a library first, so it is embeddable without a server.

Storage engine

A log-structured merge tree. Writes are sequential appends, never random writes.

Write-ahead log

Every mutation is appended to data.wal and fsynced before it is acknowledged. On startup the log is replayed to rebuild the memtable, so a process killed with SIGKILL loses nothing that was acknowledged.

Memtable

A sorted BTreeMap holding recent writes. Sorted because flushing to a sorted file should be a linear walk, not a sort. A delete writes a tombstone rather than removing the key — the value may still exist in an SSTable below.

Lookups return one of three things, and the third is what keeps deletes correct:

• Found(value) — return it
• Deleted — the key was deleted; stop searching and report absent
• NotFound — not in this layer; continue to the next one

SSTables

Immutable sorted files produced by flushing a memtable. Each carries a sparse index over ~4KB blocks and a bloom filter in its footer, so a lookup binary-searches the index, reads exactly one block, and often skips the file entirely without any disk I/O at all.

MANIFEST

An append-only log of which SSTables are live. Startup reads the manifest, not a directory listing, so a half-written file from a crashed flush is simply garbage with no manifest record — which makes crash cleanup trivial rather than a heuristic.

Read & write paths

Two orderings carry the entire correctness argument for the engine.

Write path

put(k, v)
  1. append to WAL
  2. fsync            ← must complete before step 3
  3. mutate memtable
  4. acknowledge

A crash between 3 and 2 — that is, mutating memory before the log is durable — loses a write that was already acknowledged.

Flush

flush()
  1. write memtable → new SSTable
  2. fsync the SSTable   ← must complete before step 3
  3. clear the WAL
  4. clear the memtable

Clear the WAL first and a crash in that window destroys data that exists in neither place.

Read path

Memtable first, then SSTables newest to oldest. Falling through a Deleted into an older SSTable resurrects a deleted key — the single easiest bug to write here.

memtable      → Found  → return
              → Deleted → return absent, STOP
              → NotFound
sst-0003      → bloom says "definitely not" → skip, no disk I/O
sst-0002      → key outside [min_key, max_key] → skip
sst-0001      → Found → return
              exhausted → not found

Compaction

Flushes accumulate SSTables. Every one of them has to be consulted on a read miss, so reads get slower over time while superseded values and tombstones are never reclaimed. Compaction k-way merges runs, keeps the newest version of each key, and drops what is dead.

The merge iterator that compaction needs is the same one that powers scan — a priority queue over one cursor per layer, yielding the smallest key, newer layers shadowing older. It is built once and used for both, which is why it is sequenced before compaction.

Compaction writes to a temp file and renames into place, so a crash mid-merge leaves the inputs intact rather than a half-written output.

Raft consensus

Replication for fault tolerance. Each range is an independent Raft group of three replicas, so losing a node costs availability for nothing as long as a quorum survives.

• Persistent state first. currentTerm and votedFor must survive a restart — a node that forgets its vote can vote twice in one term and elect two leaders.
• Leader election, then log replication with the prevLogIndex / prevLogTerm consistency check.
• Commit index and apply, including the current-term restriction — the classic Raft safety bug is committing an entry from a previous term by counting replicas.

Ranges & sharding

Sharding is about capacity; Raft is about durability. They are orthogonal.

The keyspace is split into contiguous ranges, placed on a consistent hash ring with virtual nodes. A router maps a key to its range; the range's leaseholder serves reads without a Raft round trip. Ranges split when they grow and merge when they shrink.

Transactions

ACID across shards, built on multi-version concurrency control.

• MVCC re-encodes keys as (user_key, timestamp). This touches the SSTable format, compaction (which must now retain versions visible to open snapshots) and the read path together — the single most invasive change in the roadmap.
• Hybrid logical clocks give a total order without trusting wall clocks.
• Two-phase commit for writes spanning more than one range.
• Optimistic concurrency control, then selectable strong / eventual / causal reads.

SQL layer

A parser and AST, a cost-based planner with EXPLAIN, and the PostgreSQL wire protocol. The wire protocol is deliberately sequenced before the optimizer.

Plans are reported Postgres-style, extended with the storage specifics this engine can actually report:

youdahedb=# explain select * from users where id = 1;
Query Plan
Index Scan using users_pkey on users  (cost=0.00..8.50 rows=5 width=64)
  Index Cond: id = 1
  Storage: LSM (memtable + L0..L3)
  Ranges scanned: 1 (r2, leaseholder n1)
  Bloom filters consulted: 6, skipped: 5
  Planning Time: 0.184 ms
  Execution Time: 0.200 ms

HTTP API

The contract shared by the console and the CLI, versioned under /api/v1. Both clients probe /api/v1/health and fall back to equivalent sample data when nothing answers, so the whole surface is usable before the server exists. Full schemas live in web/API.md.

Presence of this endpoint is what flips both clients from sample data to live.

Body {"sql": "..."}. Returns {cols, rows, ms}, or {plan} for EXPLAIN, or {notice}, or {error}. The HTTP status stays 200 on a query error so the shell can render a Postgres-style ERROR: line rather than a transport fault.

Memtable occupancy, WAL size, per-level SSTable counts and bytes, bloom filter hit rates, MANIFEST record count. The only section whose backing code is close to existing.

One measure per series — the console renders each as its own chart and never puts two scales on one axis. Prometheus text format is served separately at /metrics, outside /api/v1.

CLI reference

youdahedb is a psql workalike. The meta-commands are identical to the ones in the console's SQL shell — learn them once.

Meta-commands

Exit codes

Scriptable by design: 0 success, 1 query error, 2 connection error.

Wire protocol

The native protocol is length-prefixed binary, covering GET, PUT, DELETE, SCAN and PING, one connection per client.

The Postgres-compatible protocol is a separate listener that speaks the real thing — this one stays as the low-overhead internal path.

Design principles

Two rules decide almost every sequencing question in this project:

• Shortest path to something that runs end to end. Don't perfect a layer before the layers around it exist — a flawless component with nothing calling it teaches you nothing about whether the design is right.
• Measurement and safety before optimization. You cannot tell whether a bloom filter helped without a benchmark, and you cannot safely restructure a storage engine without a crash test.

There is also a hard constraint: the standard library only. No crates, in the database or its tests. Every B-tree, hash, file format, protocol parser and thread pool is written here.

Where to next

Development happens in the open — every design decision is written up in an issue with the reasoning attached, and the build order is public.

Browse the roadmap → Get started →