Kiban

A durable LSM-tree storage engine exploring WALs, memtables, SSTables, compaction, and crash recovery from first principles.

Rust

GitHub

About

An embedded LSM-tree storage engine in Rust. Single node. Zero dependencies. Byte keys, byte values, sorted.

Writes go to a write-ahead log, then to an in-memory memtable. Flushes produce sorted SSTables. Compaction merges SSTables and drops versions that no active snapshot can observe. Reads check sources from newest to oldest; sequence numbers order everything.

Benchmarks

90R/10W · after · gets/s: 468K gets/s → 4.22M gets/s +801.7%
90R/10W · after · us: 368us → 7.48us -98%
95R/5W · after · gets/s: 280K gets/s → 4.91M gets/s +1653.6%
95R/5W · after · us: 647us → 24.8us -96.2%
99R/1W · after · gets/s: 1.91M gets/s → 4.59M gets/s +140.3%
99R/1W · after · us: 37us → 18.5us -50%
100R/0W · after · gets/s: 5.10M gets/s → 8.58M gets/s +68.2%
100R/0W · after · us: 13us → 4.42us -66%
wall clock, 40K writes: 948ms → ~470ms -50.4%
compaction throughput: ~8.85 MB/s → ~18 MB/s +103.4%
recovery-phase PUT p99: ~1990us → ~115us -94.2%

Activity

All activity for Kiban on GitHub