A persistent key-value storage engine implementing the Log-Structured Merge-Tree (LSM-Tree) architecture.
Alphonse is a from-scratch implementation of an LSM-Tree storage engine, the same fundamental architecture used by LevelDB, RocksDB, and Cassandra. The project demonstrates core database internals including write-ahead logging, in-memory indexing, on-disk sorted tables, and background compaction.
The engine is written in Go 1.21+ using generics for type-safe data structures and achieves competitive performance with production databases.
Tested on a standard development machine with 1 million records:
Write Throughput: 731,322 ops/sec
Read Throughput: 182,066 ops/sec
Read Latency:
P50: 4.92 µs
P99: 12.80 µs
P99.9: 63.32 µs
The high write throughput comes from the append-only WAL design and sequential disk writes. Read performance benefits from Bloom filters that eliminate unnecessary SSTable scans, keeping P99 latency under 15 microseconds.
| Engine | Write Throughput | Read Latency (P99) | Language | Lines of Code |
|---|---|---|---|---|
| Alphonse | 731k ops/sec | 12.8 µs | Go | 2,700 |
| LevelDB | ~400k ops/sec | ~10 µs | C++ | ~20,000 |
| BoltDB | ~50k ops/sec | ~5 µs | Go | ~5,000 |
| BadgerDB | ~100k ops/sec | ~15 µs | Go | ~30,000 |
Benchmarks are approximate and vary by hardware. LevelDB numbers from Google's published benchmarks. BoltDB and BadgerDB from publicly available benchmarks.
Where Alphonse excels:
-
Write throughput - The LSM-Tree architecture converts random writes to sequential appends. Combined with efficient WAL buffering using
sync.Pool, Alphonse achieves write speeds competitive with LevelDB despite being written in a garbage-collected language. -
Code simplicity - At 2,700 lines, Alphonse is roughly 10x smaller than LevelDB while implementing the same core architecture. This makes it suitable for learning database internals or embedding in projects where a minimal dependency is preferred.
-
Read latency - Bloom filters with a 1% false positive rate eliminate most unnecessary disk reads. When the working set fits in the OS page cache (as with the 140MB benchmark dataset), reads are served from memory with single-digit microsecond latency.
Trade-offs:
- No compression (LevelDB uses Snappy)
- No iterator/range scan API yet
- Single-threaded compaction
- No column families or transactions
These are intentional omissions to keep the codebase focused on demonstrating LSM-Tree fundamentals.
The engine follows the standard LSM-Tree design with four main components:
Write-Ahead Log (WAL) - Every write is first appended to a sequential log file with CRC32 checksums. This guarantees durability: if the process crashes, uncommitted data can be recovered from the log on restart.
MemTable - A skip-list that holds recent writes in sorted order. When the MemTable reaches 4MB, it's frozen and flushed to disk as an SSTable. The skip-list provides O(log n) insertions and lookups.
Sorted String Tables (SSTables) - Immutable, sorted files on disk. Each SSTable contains data blocks, a sparse index for binary search, and a Bloom filter. The Bloom filter provides probabilistic membership testing with approximately 1% false positive rate, avoiding disk reads for keys that don't exist.
Compaction - A background process that merges SSTables from Level 0 into Level 1. This maintains read performance by reducing the number of files to search and reclaims space from deleted keys (tombstones).
┌─────────────────────────────────────────────────────────┐
│ Write Path: WAL -> MemTable -> Flush -> L0 SSTable │
├─────────────────────────────────────────────────────────┤
│ Read Path: MemTable -> L0 -> L1 -> L2 (Bloom check) │
├─────────────────────────────────────────────────────────┤
│ Background: L0 Compaction -> L1 when L0 >= 4 files │
└─────────────────────────────────────────────────────────┘
Write Path
- Serialize the key-value pair with a CRC32 checksum
- Append to the WAL and call
fsync()for durability - Insert into the MemTable (skip-list)
- If MemTable exceeds threshold, trigger background flush
Read Path
- Check the active MemTable
- Check the immutable MemTable (if a flush is in progress)
- For each level, newest to oldest:
- Check Bloom filter first (fast negative)
- Binary search the sparse index
- Scan the data block for the key
Compaction
When Level 0 accumulates 4 or more SSTables, the compactor:
- Identifies all L0 files and any overlapping L1 files
- Performs a merge-sort using a min-heap iterator
- Writes a new SSTable to L1
- Deletes the old input files
Tombstone garbage collection drops deletion markers when no older version of the key exists in deeper levels.
WAL Entry:
[CRC32: 4 bytes][KeyLen: 4 bytes][ValueLen: 4 bytes][Tombstone: 1 byte][Key][Value]
SSTable Layout:
[Data Blocks] [Index Block] [Bloom Filter] [Footer: 56 bytes]
The footer contains offsets and sizes for each section, plus a magic number for validation.
alphonse/
├── cmd/
│ ├── alphonse/ # Demo application
│ └── benchmark/ # Performance testing tool
├── internal/
│ ├── wal/ # Write-ahead log (225 lines)
│ ├── memtable/ # Skip-list implementation (377 lines)
│ ├── sstable/ # SSTable read/write + Bloom filter (641 lines)
│ ├── compaction/ # Background compaction (615 lines)
│ └── engine/ # Coordinator (480 lines)
└── go.mod
Total: ~2,700 lines of Go
db, err := engine.Open(engine.DefaultOptions("./data"))
if err != nil {
log.Fatal(err)
}
defer db.Close()
// Write
db.Put([]byte("key"), []byte("value"))
// Read
value, found := db.Get([]byte("key"))
// Delete
db.Delete([]byte("key"))# Demo
go run ./cmd/alphonse
# Benchmark
go run ./cmd/benchmark -n 100000
go run ./cmd/benchmark -n 1000000 -vsize 256Why Skip-List over Red-Black Tree? Skip-lists are simpler to implement correctly and provide comparable O(log n) performance. They also work well with range scans since nodes are linked sequentially.
Why not use mmap? Standard file I/O with the OS page cache is sufficient for this workload and avoids the complexity of memory-mapped files. The benchmark shows the page cache is doing its job with sub-15µs P99 latency.
Why CRC32? Fast, well-supported, and sufficient for detecting corruption. The same choice as LevelDB.
Why sync.Pool for WAL buffers? Reduces garbage collection pressure during high-throughput writes. Benchmarks showed a measurable improvement in tail latencies.
- Go 1.21+ (uses generics with
cmp.Ordered)
MIT