A persistent, embeddable key-value store written from scratch in Go — built on an LSM-tree storage engine, fronted by a Redis-compatible network server.
Cinder is a working database, not a toy. It implements the same storage architecture that powers RocksDB, LevelDB, Cassandra, and BadgerDB: a log-structured merge tree with a write-ahead log, immutable sorted on-disk tables, Bloom filters, and background compaction. No external storage dependencies — the only imports are the Go standard library.
443,000 writes/sec · 957,000 reads/sec · sub-10µs p99 reads
(in-process, single core for writes, 8 cores for reads — see Benchmarks)
Any Redis client can talk to it:
$ cinder -addr :6380 -dir ./data
$ redis-cli -p 6380 set hello world
OK
$ redis-cli -p 6380 get hello
"world"Most key-value stores are a black box you import. Cinder is the box, opened up. It was built to answer a concrete question — what actually happens between db.Put(k, v) and the bytes landing durably on disk such that they survive a crash and can be read back in microseconds? — and to implement every layer of that answer:
- Durability without losing throughput → a write-ahead log with CRC-checked frames and torn-write recovery.
- Fast writes despite slow random disk I/O → buffer in memory, flush sequentially. This is the core LSM insight.
- Fast reads despite data scattered across many files → Bloom filters, per-table sparse indexes, and a layered merge so a point lookup costs at most one seek per level.
- Bounded space and read cost as data grows → leveled background compaction that continuously merges and garbage-collects.
┌─────────────────────────────────────────────┐
Put / Delete ───▶│ WAL (append + fsync) → durability │
└───────────────────┬─────────────────────────┘
▼
┌──────────────────────────┐
│ Memtable (skip list) │ in-memory, sorted
└───────────┬───────────────┘
full → rotate (immutable)
▼ background flush
╔═══════════════════════════════════════════════════════════════╗
║ L0 [sst] [sst] [sst] [sst] ← may overlap; newest first ║
║ L1 [sst][sst][sst] ... ← sorted, non-overlapping ║ on disk
║ L2 [sst][sst][sst][sst] ... ← 10× the size of L1 ║ (SSTables)
║ ... ║
╚═══════════════════════════════════════════════════════════════╝
▲ background compaction merges levels,
collapses overwrites, drops tombstones
- The mutation is appended to the write-ahead log and (optionally) fsync'd. This is the durability point — after this returns, the write survives a crash.
- It is inserted into the in-memory memtable (a skip list — ordered, O(log n)).
- When the memtable exceeds its size threshold it becomes immutable, a fresh memtable + WAL take over, and a background goroutine flushes the frozen memtable to a new L0 SSTable.
Because the on-disk write is one large sequential file rather than many random updates, write throughput is bounded by sequential I/O, not seeks.
A lookup checks sources newest-to-oldest and stops at the first hit:
memtable → immutable memtable → L0 (newest file first) → L1…Ln (binary search).
Each SSTable lookup does one Bloom filter check (skips the file entirely on a miss), one binary search over an in-memory sparse index to find the right block, then a single ReadAt for that block. L1+ files are non-overlapping, so at most one file per level can hold the key.
A single background goroutine runs leveled compaction: when L0 accumulates too many files (or a level exceeds its byte budget), it merges the inputs with the overlapping files one level down via a k-way merge, keeping only the newest version of each key and dropping tombstones once no older data can exist beneath them. Each level holds ~10× the one above, which bounds the number of levels — and therefore read and space amplification — to O(log n).
- WAL frames are length-prefixed and CRC32C-checked; a torn or corrupt trailing frame (the signature of a crash mid-write) is detected and truncated on replay rather than corrupting recovery.
- The
MANIFEST(the record of which SSTables exist at which level) is updated atomically via write-temp-then-rename. - On startup the engine replays any surviving WALs into a memtable and flushes it, so recovery is deterministic.
In-process, cinderbench, Apple Silicon, 100-byte values, 1,000,000 keys. Writes are single-writer by design (see Concurrency model); reads use 8 goroutines.
| Workload | Throughput | avg | p50 | p99 | p99.9 |
|---|---|---|---|---|---|
| Write (sequential) | 442,724 ops/s | 2µs | 1µs | 5µs | 24µs |
| Read (random, 8 concurrent) | 956,720 ops/s | 8µs | 5µs | 86µs | 306µs |
Write, --durable (fsync/write) |
144 ops/s | 6.9ms | 6.3ms | 18ms | — |
The last row is the honest cost of fsync-on-every-write durability on macOS — a ~3000× throughput drop that motivates why real databases batch and group-commit. Cinder's default buffers the WAL and fsyncs on flush, trading a bounded window of un-fsync'd writes for throughput; --durable makes every write survive power loss.
Reproduce:
make bench # default 1M-op run
go run ./cmd/cinderbench -n 1000000 -readers 8 -valuesize 100
go run ./cmd/cinderbench -n 5000 -durable # durable modemake build # builds ./bin/cinder and ./bin/cinderbench
./bin/cinder -addr :6380 -dir ./data
# in another terminal (any Redis client works):
redis-cli -p 6380 set user:1 alice
redis-cli -p 6380 get user:1
redis-cli -p 6380 scan user: COUNT 100Supported commands: PING · SET · GET · DEL · EXISTS · SCAN · DBSIZE · INFO · QUIT. Both the RESP array protocol (used by real clients) and inline commands are accepted.
Embed it directly in a Go program:
db, _ := engine.Open(engine.Options{Dir: "data"})
defer db.Close()
db.Put([]byte("k"), []byte("v"))
v, _ := db.Get([]byte("k"))| Decision | Rationale |
|---|---|
| LSM-tree, not B-tree | Optimizes for write throughput by turning random writes into sequential flushes. The trade-off is read & space amplification, which compaction bounds. |
| Single-writer, multi-reader | Writes serialize behind one lock (the LevelDB model); reads run concurrently under a read lock. This keeps WAL ordering and the memtable simple and lock-light, and matches the reality that a WAL is inherently a serial append. |
| Background flush + compaction | All disk I/O for flush/compaction happens off the write path on one goroutine, which only takes the lock to install results. Writers stall only under sustained overload (the L0 back-pressure trigger). |
| Bloom filter per SSTable | A negative is definitive, so lookup-misses skip the file without a read — the common case in real workloads. |
| Block-based SSTable + sparse index | One seek per table regardless of size; the index stays in memory and is small (one entry per ~4KB block). |
| Skip list memtable | Ordered iteration for flushing + O(log n) ops, with far less code than a balanced tree. |
The correctness-critical paths are covered by unit tests, an integration test of the network server, a randomized fuzz test that runs 20,000 mixed put/delete operations against a reference map and asserts equivalence, crash-recovery tests, and a concurrency test run under the race detector.
make test # go test ./...
make race # go test -race ./...Coverage on core packages: engine 86% · skiplist 90% · bloom 87% · sstable 79% · wal 67%.
cinder/
├── cmd/
│ ├── cinder/ RESP server binary
│ └── cinderbench/ throughput + latency benchmark tool
├── internal/
│ ├── record/ on-disk record encoding (keys, seqnums, tombstones)
│ ├── skiplist/ ordered in-memory memtable
│ ├── bloom/ Bloom filter
│ ├── wal/ write-ahead log (append, fsync, CRC, replay)
│ ├── sstable/ immutable sorted tables (writer, reader, index, bloom)
│ ├── engine/ LSM engine: memtable rotation, flush, manifest,
│ │ leveled compaction, recovery, Get/Put/Delete/Scan
│ └── server/ RESP protocol parser + TCP server
└── README.md
Cinder is intentionally scoped to the storage engine and a single-node server. Natural extensions, in rough order of interest:
- Snapshots / MVCC reads — sequence numbers are already threaded through every record; exposing read snapshots is the next layer.
- Block cache — cache hot data blocks to cut repeated
ReadAts. - Compression — Snappy/zstd on data blocks (the format already separates blocks from the index).
- Replication — a Raft layer over the WAL would turn this into a distributed store.
MIT — see LICENSE.