kvore

An embedded LSM-tree storage engine in Go. Write-optimized key/value storage with a write-ahead log, immutable SSTables, bloom filters, and background compaction.

Memtable, write-ahead log, crash recovery, SSTable flush, bloom filters, sparse indexing, and background leveled compaction. DESIGN.md has the format details, the reasoning behind the compaction strategy, what the fault injection turned up, and the measurements. Raw benchmark and crash-test output is in results/.

db, err := kvore.Open("/var/lib/mydata", kvore.DefaultOptions())
if err != nil {
	log.Fatal(err)
}
defer db.Close()

db.Put([]byte("user:1"), []byte("jayden"))
val, ok, err := db.Get([]byte("user:1"))
db.Delete([]byte("user:1"))

Layout

DESIGN.md                format, tradeoffs, findings, measurements
LICENSE                  MIT
db.go                    public API: Open, Put, Get, Delete, Close
compact.go               leveled compaction: picker, k-way merge, install
manifest.go              the live file set, swapped atomically
crash_test.go            kill-the-process fault injection harness
bench_test.go            throughput and latency measurement
internal/memtable/       skip list write buffer
internal/wal/            write-ahead log format and replay
internal/sstable/        immutable sorted files: blocks, index, footer
internal/bloom/          per-table filters
internal/kv/             the Missing/Found/Deleted vocabulary both share
internal/hrtime/         a clock fine enough to time one lookup
results/                 raw output from the fault injection and benchmark runs

Tests

go test ./...

About a minute, most of it the 60 crash trials and the corruption sweeps. -short scales those down and finishes in around 25 seconds.

The logs under results/ are the record of a run rather than scratch space, so tests write beside them and leave them alone. To refresh the committed copies:

KVORE_RECORD=1 go test -run TestCrashRecovery
go test -run '^$' -bench . -benchtime 1x | tee results/benchmarks.txt

License

MIT. See LICENSE.