wal

A disk-based key-value storage engine, written from scratch in Go — made basically to understand how databases work internally: pages, B+Trees, buffer management, write-ahead logging and concurrency control. No external storage libraries are used anywhere; every byte of the on-disk format is hand-rolled only.

Work in progress. This is a learning project, so correctness and clarity are prioritised over performance, and each layer is built (and properly tested) before the next one is started.

Architecture

The engine is layered bottom-up, more or less mirroring how real systems (SQLite, Postgres, InnoDB) are organised:

┌───────────────────────────────────────────┐
│  cmd/         CLI (REPL)                  │  put / get / delete / checkpoint
├───────────────────────────────────────────┤
│  btree/       B+Tree                      │  ordered key-value index
├───────────────────────────────────────────┤
│  wal/         Write-ahead log             │  durability, crash recovery
├───────────────────────────────────────────┤
│  pool/        Buffer pool                 │  page cache, pin/evict
├───────────────────────────────────────────┤
│  pager/       Pager                       │  file ⇄ fixed-size pages
└───────────────────────────────────────────┘

pager/

Treats a single database file as an array of 4096-byte pages addressed by PageID. Page 0 is the meta page (magic number, format version, page count, B+Tree root). Meta is kept in memory and made durable only via FlushMeta/Close, or through the WAL — it is not synced on every change, since that job now belongs to the write-ahead log.

pool/

A buffer pool sitting between the B+Tree and the pager. Pages are fetched (pinned) into a fixed set of frames, mutated in memory, and written back to the file only lazily — on eviction, or on an explicit flush. Eviction uses the clock (second-chance) policy. All bookkeeping (pins, dirty flags, the page table) is guarded by an internal mutex, so the pool is safe to use from more than one goroutine.

wal/

An append-only write-ahead log. Every mutating tree operation logs a full-page image of each page it changed, followed by a commit marker, and fsyncs once before the operation is acknowledged back to the caller. On startup, any committed group left over from a previous run gets replayed into the main file automatically; a torn or incomplete record at the tail is simply discarded — same as if it had never happened.

btree/

B+Tree nodes, one per page, using a slotted page layout: a sorted slot array of 2-byte offsets grows from the front, variable-length cells grow from the back, with free space sitting in between. Leaf cells are keyLen | valLen | key | value; internal cells are keyLen | child pageID | key. Supports Get/Put/Delete with node splits and lazy deletion (no merging on delete). A tree-wide RWMutex currently guards the whole structure — readers run concurrently with each other, writers are exclusive. Latch crabbing (finer, per-page locking) is planned, but not done as such, yet.

cmd/

A small REPL to try the whole engine end-to-end, no code required.

How to use

Build the CLI:

go build -o kv ./cmd

Run it with a database file name (if not given, it defaults to kv.db):

./kv mydata.db

You will get a prompt where the following commands can be typed, one at a time:

> put foo bar
OK
> get foo
bar
> delete foo
OK
> get foo
(not found)
> checkpoint
OK
> exit

• put <key> <value> — inserts a key, or updates it if already present
• get <key> — fetches a key's value, or prints (not found)
• delete <key> — removes a key, or prints (not found)
• checkpoint — flushes everything to the main file and empties the log
• exit / quit / Ctrl-D — checkpoints and closes cleanly before quitting

Development

go test ./...              # run all tests
go vet ./...