kiban
githubget started

kiban · 基盤 · n. foundation

a storage engine, built from scratch.

kiban is an embedded LSM-tree key-value store for Linux, written in Rust: a write-ahead log, memtables, SSTs, leveled compaction, snapshots and crash recovery.

ask your aiopens with a prompt to explain kiban

v0.2.0 · early release
see it in code

open, put, sync().

Open a directory, write, sync, read. Byte keys and byte values, kept in order, inside your process.

use kiban::db::Kiban;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut db = Kiban::open("example-db")?;
    db.put(b"hello", b"world")?;
    db.sync()?; // put alone is not crash-durable
    assert_eq!(db.get(b"hello")?, Some(b"world".to_vec()));
    drop(db);

    let reopened = Kiban::open("example-db")?;
    assert_eq!(reopened.get(b"hello")?, Some(b"world".to_vec()));
    Ok(())
}

Rust 2024 · no runtime dependencies by default · Linux · MIT

what Ok means.

Ok means accepted. sync() means durable.

promised
sync()every write accepted before it survives a crash
write(batch)all or nothing, one WAL record
snapshot()unmoved by later writes and compactions
a failed syncthe engine refuses writes until reopened
WAL, SST, MANIFESTCRC-32 checksummed
after a crasha real past state, every synced write in it
synced WAL damagereported when a later sync mark proves it
WAL rotationold log synced before the next opens
not promised
put() before sync()lost if the machine goes down
dropnot a sync
two processes, one directorynot validated
machine power losssimulated, not tested on hardware
API, on-disk formatmay change before 1.0
not built yetcompression, range deletes, reverse iteration, transactions

we tried to break it.

Simulated crashes, injected filesystem faults and real SIGKILLs. After each one, the reopened database is checked for a prefix of accepted writes that includes every synced write.

Crash seeds on every PR
Power losses per seed
Bugs found and fixed
SIGKILL / reopen cycles
Acknowledged writes verified
Library tests

Every guarantee names the test that checks it. Tested cases, not a proof, and not a claim of production readiness.

Read the repair report

against the field.

One agent-memory workload on four engines at kiban commit 3935977: warm cache, one worker, every result checked. kiban leads warm reads, keeps pace on durable writes, and gives up disk and memory to do it.

Faster point reads than tuned RocksDB
Faster latest-ten reads than tuned RocksDB
Faster latest-ten reads than SQLite with mmap
Faster point reads than LMDB
More durable writes with group commit, at 16 writers
The syncs for the same durable writes, at 16 writers

every workload

Median latency, p99 beneath. Pick an opponent. A gap that changes sign between trials reads as even.

Median latency or throughput of kiban and the selected engine per workload, with p99 and the paired ratio between them.
workload kiban 1×kiban faster →
reads
point read1M records
latest ten1M records, one agent
point read, small cache32 MiB cache, mmap on
latest ten, small cache32 MiB cache, mmap on
durable writes
new recordsynced before return
updatesynced before return
16 concurrent writersgroup commit, every write verified

double the writers

Group commit shares one sync across waiting writers. Press play, or drag across the plot.

writes per second, every one synced

kiban
RocksDB
SQLite
kiban, ungrouped
10M random writes, inside the tree
L3
L2
L1
L0

writes per second

┊ RocksDB finished the same run at 35 s

queued above level targets

replay the long runs

The scale runs, second by second from each engine's median trial. Press play, or drag across the plot.

100k hot keys within 1M, four threads. Operations completed over time; the finish line is 100M.

kiban 3935977
RocksDB 11.8.1

The default point index costs this small-cache run half its speed: with it off, kiban reached 3.8M ops/s.

the other column

What these wins cost, and what this campaign cannot tell you.

where it loses
memory450 MiB peak RSS, RocksDB 356, SQLite 349
disk352 MiB for 1M records, RocksDB 304, SQLite 315
latest ten, small cacheLMDB is 1.4× faster at 32 MiB
point read, no mmapbehind LMDB at 32 MiB unless mmap is on
sustained writesRocksDB finishes the long write runs about 3× sooner
point index, tiny cachehalves 100M reads at 33 MiB: 1.7M ops/s, 3.8M with it off
flush and compaction1.36× and 1.26× slower with the point index
not measured
larger than memorybeyond the 32 MiB cache rows
cold readsevery read here starts warm
many readersone reader, one pinned core
shared hostnot an exclusive core

One shared laptop on mains power: Intel Core Ultra 9 185H, NVMe behind LUKS, Linux 7.2. A memory record is a JSON value with 200 bytes of text, across 64 agents. Reads ran on one pinned core, five rotated trials per engine. kiban ran with its agent_memory settings, RocksDB with the winner of its published screen, and SQLite with its fastest read row. These runs use the engine code released as v0.2.0, and say nothing about larger-than-memory or cold-storage performance.

Methodology and raw results The v0.1.0 throughput comparison

follow a write.

One put(), from the log to memory to a sorted file on disk.

Where one write goesMemory is drawn above disk. put(pear = green) is appended to the write-ahead log on disk and inserted into the memtable in memory. The full memtable freezes, is written to disk as a sorted SST, and the MANIFEST records the SST. Then the old log is deleted.MEMORYlost on crashDISKsurvives a crashput(pear = green)memtablekey orderapplepear = greenzebrafrozenno new writesapplepear = greenzebrawrite-ahead log40 orange41 apple42 pear = greenSST filesortedapple … zebrapear = greenMANIFESTlive files+ SST 0012123456

what happens after put()?

The work that follows a write: compaction, snapshots, file cleanup, and recovery after a crash.

What happens after a writeOn disk, two overlapping L0 files are merged with L1 into a new set of non-overlapping L1 files. A snapshot pins the old L1 files it reads. The MANIFEST records the new files; the replaced files are deleted once nothing uses them. After a crash, memory is lost and the WAL is replayed into a fresh memtable.MEMORYlost on crashDISKsurvives a crashL0ranges overlapapple … pearkiwi … zebrasnapshotseq 41still reads old L1L1no overlapsapple … figgrape … kiwilemon … zebraMANIFESTcommit+ L1 0021 … 0024− L1 0011 … 0013− L0 0007, 0008WALon disk42 pear = greenmemtablerebuiltreplayed from WAL12345

inside the engine.

An ordered byte-key, byte-value store that runs inside your process. The MANIFEST decides which log and table files belong to the database.

The kiban engine as stacked layersAn isometric cut-away whose layers are the LSM levels, with key order running left to right. Writes append to the WAL and land in sorted position on the memtable. The memtable freezes and flushes into L0 as a sorted file; the MANIFEST commits it and the old WAL retires. Compaction then merges L0 into L1 and re-cuts the non-overlapping L1 key ranges. L2 holds the oldest, largest files.WALseq 1005MANIFESTv40put(lime)L2 · oldest, largest filesL1 · disjoint key rangesmemtableakey orderz
get() and scan() read the memtables, then the SSTs, newest first; the newest visible version wins.
block cache
Holds checksum-verified SST blocks for reads. Compaction streams through its own reader and leaves the cache alone.
MANIFEST
Records which WAL and SST files are live, and at which level, before any reader sees the change.
compaction
Merges overlapping files downward. From L1 on, files in a level never overlap in key range.
snapshots
Pin a sequence number and the files behind it. Later writes and compactions don't change what a snapshot reads.

what's here.

Shipped features and the work ahead.

capabilities
Rustshipped
Python (ctypes)shipped
MCP servershipped
C ABIshipped
Group commitshipped
Perfect-hash point indexshipped
agent_memory profileshipped
roadmap
doneCrash-simulation suite
doneWrite path: group commit
doneBindings: Python/MCP
donePublished benchmarks
nextStorage API: reverse/prefix scans, namespaces, range deletes, TTL
plannedTransactions

everything we measured.

How kiban is built, how it was tested, and what it lost along the way.

  1. how it is built.

    Ownership, durable state, reads, snapshots and maintenance.

  2. against the field.

    Four engines at one commit: the campaign behind this site's numbers.

  3. the perfect hash.

    The experiment that showed immutable tables could beat a B+tree.

The reports worth reading, set for the screen.

Open the library