kiban
githubget started

library · start here

how it is built.

Follow one write until it is safe, then one read until it is right. Most of a storage engine is deciding exactly when you are allowed to say yes.

8 min read · kiban v0.2.0 · the full architecture reference

Kiban is an embedded LSM-treeLSMLog-structured merge tree. Writes land in memory, then move to sorted files on disk that are merged in the background. storage engine in Rust. There is no server. Your program links the library, owns a directory, and stores ordered byte keys and byte values. An exclusive lock on that directory means one owner at a time, even across processes.

The LSM idea is simple: never edit data in place. New writes go to a log and to memory, and memory is written out as sorted files that never change again. Everything hard comes from one fact. For a while, the same data exists in several places, and at every moment the engine must know which copy it can trust.

one write

Watch the question on the figure. It is the only one that matters: if the power went out right now, would this record survive?

key agent/7/note = “ship it”

  1. memtablememory
  2. write-ahead logdisk
  3. frozen memtablememory
  4. new SSTdisk
  5. MANIFESTdisk
  6. lower levelsdisk

survives a crash?not yet

  1. put returns

    The record is appended to the WALWALWrite-ahead log. Every change is appended here first, so it can be replayed after a crash., the memtablememtableThe in-memory table that takes new writes before they are flushed to an SST. is updated, and the call returns. That return is not a promise. The log is still buffered, and a crash here can lose the record. Kiban says so in its API instead of hiding it.

  2. sync makes the promise

    sync() is the line between accepted and durable. It covers every write accepted so far, in every live log file. If a sync fails, the engine refuses further writes until it is reopened, because it can no longer say what the disk holds.

  3. the memtable freezes

    When enough has been written, the memtable freezes and a new one takes over with a new log. The old log has to stay alive, and still be syncable, because it is the only durable copy of that data. Getting this wrong was one of our worst bugs.

  4. a file nobody will change

    The frozen memtable is written out as a sorted SSTSSTSorted string table: an immutable file of sorted keys and values. Once written, it never changes. and synced. The record is now in two places, and neither has been let go. The file exists, but nothing refers to it yet.

  5. one atomic switch

    The MANIFESTMANIFESTThe engine's record of which files are live. A file does not exist to kiban until the MANIFEST says so. names every live file. A new one goes to a temporary file, gets synced, renamed into place, and the directory is synced. That rename is the commit point. Only after it can the old log be retired.

  6. compaction moves it down

    compactioncompactionBackground merging of SSTs into larger sorted files, which drops old versions and keeps reads fast. merges files into lower levels, where key ranges never overlap. It builds new files outside the engine's main lock, then applies the change through the same MANIFEST switch. Nothing is deleted until nothing can still need it.

Syncing is slow, and that is where group commitgroup commitLetting many waiting writers share one disk sync, so durability costs less per write. comes in. Writers that arrive while a sync is running wait together, and the next sync covers them all. At 16 writers, kiban reaches 14,101 synced writes a second with 480 syncs. Without grouping it manages 1,836 a second and needs 4,000 syncs. Every write is still synced before it returns.

one read

Reads have the opposite problem. The record may be in several places at once, in different versions, and the engine has to return the right one quickly.

key agent/7/note = “ship it”

  1. read viewmemory
  2. active memtablememory
  3. frozen memtablememory
  4. one table per leveldisk
  5. newest visible versionmemory

answernothing yet

  1. take a consistent view

    A read starts by capturing a published view of the database: which memtables and which files count. Writers can keep moving. This read will answer from the state it captured.

  2. check memory first

    The active memtable holds the newest data, then the frozen one. A later log means a later sequence number, so a match here wins and the read is done.

  3. one table per level

    Below L0L0The top level of the tree, where flushed files land. Its files can overlap in key range., files in a level never overlap, so a binary search on first keys finds the only table that could hold the key. Inside it, the perfect hash computes the record's location instead of searching for it.

  4. sequence decides

    Finding the key is not enough. Which level a file sits in does not prove which value is newest, so the read compares sequence numbers and takes the highest one it is allowed to see. A newer delete wins too. The tombstonetombstoneA marker that records a deletion, so older versions of the key stay hidden. hides everything older, and the key reads as missing.

A cached point read over a million records takes a median of 1.09 µs, 2.6× faster than tuned RocksDBRocksDBMeta's widely deployed LSM storage engine, the standard to beat. in the same campaign. The perfect hash essay explains how, and that speed depends on a warm cache.

what broke

The diagrams above are tidy because each line was paid for. These are three of the failures that scale testing found in our own engine.

a sync that lied

When a memtable froze, its log file stayed listed as live, but the object that wrote to it was dropped. Dropping it did not sync it. The next sync() covered only the new log, so it could report success for records that a power cut would erase. Now the frozen memtable owns its log writer, and sync covers both. A successful sync now covers every accepted write until a committed SST replaces its log.

a snapshot that lost its data

A snapshotsnapshotA frozen view of the database at one moment. Later writes do not change what it sees. kept its sequence number and file list, but read the engine's current memtables. Once its data was flushed, that data was in neither place. The fix made snapshots own their sources. Then testing found a second cause: moving a file between levels created a new record for the same physical file, so a pinned file could still be deleted. A real filesystem reproduced it with no crash at all.

a read that disagreed with a scan

Versions of one key can span search intervals inside a block, and lookup could start too late and skip the newest ones. A reproduction with 40 updates returned value 8 from a point read while a scan correctly returned 40. It could skip a delete as well. Lookup was corrected, and every read path now uses the same sequence rule.

how we check

Every fix above has a regression test. Beyond those, a simulated device loses unsynced data on command, crash suites run across millions of seeds, processes are killed and reopened for 1,000 cycles, and Loom explores thread orderings in the custom locking.

The limits matter just as much. Killing a process keeps the OS cache, so it is not a real power cut. The device and concurrency models are bounded. None of this proves kiban correct, and it does not make it production-ready. It is evidence, and all of it is published.

what it costs

Kiban runs on Linux and makes no API or format promise before 1.0. It is an early engine with its losses in the open.