I was using Redis as an execution cache in the backend for my compiler project. It worked. I had no complaints. But every time I called client.Set() or client.Get(), I had this nagging feeling that I had no idea what was actually happening. I was trusting a black box to do something I should understand.
So I removed Redis, and I built the replacement.
This is the story of how I built StrataKV, a WAL-durable, LSM-tree-inspired key-value storage engine in Go, published on pkg.go.dev and now running in production as the execution cache for the Blan Cloud Engine. Along the way I measured everything, caught a silent bug that only revealed itself through benchmarking, and learned more about storage systems than any course taught me.
Why LSM Trees?
Before writing a line of code, I had to pick an architecture. There are two dominant approaches to building a writable key-value store:
B-Trees (what most relational databases use) do in-place updates. A write finds the right node in the tree and modifies it directly. Reads are fast, O(log n) with no extra overhead. But writes involve random disk I/O, which is expensive.
Log-Structured Merge Trees (LSM trees, what LevelDB, RocksDB, and Cassandra use) never modify data in place. Every write is an append. This turns random writes into sequential writes, which are dramatically faster on disk. The tradeoff: reads get more expensive because data might be spread across many files, and you need a background process (compaction) to consolidate things periodically.
I chose LSM because:
- The Blan cache is write-heavy: every new compilation result needs to be written
- Sequential appends are simpler to reason about for crash safety
- The architecture maps cleanly to immutable data structures, which I prefer
The core idea of an LSM tree is this: writes go to memory first (the MemTable), get flushed to disk as immutable files (SSTables or segment files) when memory fills up, and periodically get consolidated by compaction. A Write-Ahead Log (WAL) makes everything crash-safe.
Let me walk you through each component.
The Write-Ahead Log
The WAL is the first thing that happens on any write. Before touching memory, we append the operation to a sequential log file on disk and call fsync. If the process dies after the fsync, the data is on stable storage. If it dies before, the partial write is ignored on recovery.
Here's the record format:
[1 byte: op type] [4 bytes: key_len LE] [4 bytes: val_len LE] [key bytes] [val bytes]
One byte for the operation (0 = Put, 1 = Delete), four bytes each for lengths in little-endian, then the payload. No checksums, no framing, just raw binary records, one after another. Simple to write, simple to replay.
func (w *WAL) WriteEntry(isDelete bool, key, value []byte) error {
w.mu.Lock()
defer w.mu.Unlock()
header := make([]byte, 9)
if isDelete {
header[0] = 1
}
binary.LittleEndian.PutUint32(header[1:5], uint32(len(key)))
binary.LittleEndian.PutUint32(header[5:9], uint32(len(value)))
if _, err := w.file.Write(header); err != nil {
return err
}
if _, err := w.file.Write(key); err != nil {
return err
}
if !isDelete {
if _, err := w.file.Write(value); err != nil {
return err
}
}
return w.file.Sync()
}
The file.Sync() at the end is the critical line. This is an fsync syscall: it tells the OS to flush its write buffers to the physical device. Without it, the OS might buffer the write in memory and lose it on a crash. With it, the write is durable before we return.
Recovery on startup is a simple sequential replay:
func (w *WAL) Recover(fn func(isDelete bool, key, val []byte)) error {
w.mu.Lock()
defer w.mu.Unlock()
w.file.Seek(0, io.SeekStart)
for {
header := make([]byte, 9)
_, err := io.ReadFull(w.file, header)
if err == io.EOF {
break
}
if err != nil {
return err
}
isDelete := header[0] == 1
keyLen := binary.LittleEndian.Uint32(header[1:5])
valLen := binary.LittleEndian.Uint32(header[5:9])
key := make([]byte, keyLen)
io.ReadFull(w.file, key)
var value []byte
if !isDelete {
value = make([]byte, valLen)
io.ReadFull(w.file, value)
}
fn(isDelete, key, value)
}
w.file.Seek(0, io.SeekEnd)
return nil
}
If a record is truncated, meaning the process crashed mid-write before the fsync, io.ReadFull hits EOF before reading the full expected bytes and the loop breaks. The partial record is silently dropped. This is intentional. The durability guarantee is: durable after fsync, no guarantee before it.
The MemTable
After the WAL write succeeds, we update the in-memory MemTable:
type Entry struct {
Value []byte
Deleted bool
}
type MemTable struct {
mu sync.RWMutex
data map[string]Entry
}
func (m *MemTable) Put(key, value []byte) {
m.mu.Lock()
defer m.mu.Unlock()
copyVal := append([]byte(nil), value...)
m.data[string(key)] = Entry{Value: copyVal, Deleted: false}
}
func (m *MemTable) Get(key []byte) ([]byte, bool) {
m.mu.RLock()
defer m.mu.RUnlock()
entry, exists := m.data[string(key)]
if !exists || entry.Deleted {
return nil, false
}
return entry.Value, true
}
I used a plain Go map[string]Entry, not a sorted structure. Real LSM engines use skip lists for the MemTable because sorted order enables building a sparse index in the SSTable for O(log n) reads. I made a deliberate simplification: no sparse index, linear scan within a segment. I accepted worse read performance in exchange for simpler code and faster iteration on the architecture.
Tombstone semantics: Delete doesn't remove the key from the map. It sets Deleted: true. This matters because the key might exist in older segment files on disk. We need the tombstone to survive the flush so it can override those older versions. Physical deletion only happens during compaction.
The Full Write Path
Here's the complete Put operation, which shows how everything fits together:
const maxMemTableSize = 1 << 20 // 1 MiB
func (db *DB) Put(key, val []byte) error {
db.mu.Lock()
defer db.mu.Unlock()
if err := db.wal.WriteEntry(false, key, val); err != nil {
return fmt.Errorf("failed to write the WAL: %w", err)
}
db.mem.Put(key, val)
if db.mem.ApproximateSize() >= maxMemTableSize {
if err := db.flushLocked(); err != nil {
return fmt.Errorf("failed to flush the memtable: %w", err)
}
}
return nil
}
The ordering is non-negotiable: WAL fsync, then MemTable update, then size check, then maybe flush. Never the other way around. If we updated the MemTable first and crashed before the WAL write, we'd have data in memory with no recovery path.
Flushing to Disk: Segment Files
When the MemTable crosses 1 MiB, we flush it to an immutable segment file:
func (db *DB) flushLocked() error {
data := db.mem.Export()
if len(data) == 0 {
return nil
}
segName := fmt.Sprintf("%d.seg", time.Now().UnixNano())
segPath := filepath.Join(db.dataDir, segName)
if err := storage.WriteSegment(segPath, data); err != nil {
return fmt.Errorf("failed to write segment %s: %w", segName, err)
}
if bf, err := storage.BuildBloomFilter(segPath); err == nil {
db.segmentFilters[segName] = bf
}
db.mem.Clear()
db.wal.Close()
os.Remove(filepath.Join(db.dataDir, walFileName))
newWAL, err := storage.NewWAL(filepath.Join(db.dataDir, walFileName))
if err != nil {
return err
}
db.wal = newWAL
return nil
}
The segment filename is a Unix nanosecond timestamp. This is intentional: lexicographic sort of filenames gives chronological order, which the read path uses to scan newest-to-oldest.
After a successful flush, the WAL for those entries is no longer needed. The data is durable in the segment file. We delete the WAL and open a fresh one.
The segment format is the same binary record structure as the WAL: no index, no footer, just flat binary records:
func WriteSegment(path string, data map[string]memtable.Entry) error {
f, err := os.OpenFile(path, os.O_CREATE|os.O_WRONLY|os.O_TRUNC, 0644)
if err != nil {
return err
}
defer f.Close()
for k, v := range data {
keyBytes := []byte(k)
header := make([]byte, 9)
if v.Deleted {
header[0] = 1
}
binary.LittleEndian.PutUint32(header[1:5], uint32(len(keyBytes)))
binary.LittleEndian.PutUint32(header[5:9], uint32(len(v.Value)))
f.Write(header)
f.Write(keyBytes)
if !v.Deleted {
f.Write(v.Value)
}
}
return f.Sync()
}
The Read Path
A Get checks three places in order, from fastest to slowest:
func (db *DB) Get(key []byte) ([]byte, bool) {
db.mu.RLock()
defer db.mu.RUnlock()
// 1. Check MemTable: fastest path, in memory
if val, found := db.mem.Get(key); found {
return val, true
}
// 2. List segments, newest first
files, _ := os.ReadDir(db.dataDir)
var segments []string
for _, f := range files {
if strings.HasSuffix(f.Name(), ".seg") {
segments = append(segments, f.Name())
}
}
sort.Slice(segments, func(i, j int) bool {
return segments[i] > segments[j] // descending = newest first
})
// 3. Check each segment, using Bloom filter to skip where possible
for _, seg := range segments {
bf, exists := db.segmentFilters[seg]
if exists && !bf.MightContain(key) {
continue // definitely not in this segment
}
segPath := filepath.Join(db.dataDir, seg)
if val, found, isDeleted := storage.SearchSegment(segPath, key); found {
if isDeleted {
return nil, false // tombstone — key was deleted
}
return val, true
}
}
return nil, false
}
We scan newest-to-oldest because newer segments always contain the most recent version of a key. The moment we find a match, whether a live value or a tombstone, we return immediately.
The Bloom filter check (bf.MightContain(key)) is what makes negative lookups fast. If the filter says "definitely not present," we skip the entire disk scan for that segment. More on this below.
Compaction
Without compaction, segment files accumulate indefinitely. Every overwrite of a key creates a new entry in a new segment; the old version isn't deleted, it's just superseded. After the benchmark workload (50K initial writes, 200K overwrites, 80K deletes), I had 1,945 segment files and nearly 2GB on disk.
Compaction reads all segments, merges them, keeps only the newest version of each key, drops tombstones, and writes one output segment:
func (db *DB) Compact() error {
db.mu.Lock()
defer db.mu.Unlock()
files, _ := os.ReadDir(db.dataDir)
var segments []string
for _, f := range files {
if strings.HasSuffix(f.Name(), ".seg") {
segments = append(segments, f.Name())
}
}
if len(segments) < 2 {
return nil
}
sort.Strings(segments) // oldest first
// Merge: older entries get overwritten by newer ones for the same key
mergedData := make(map[string]memtable.Entry)
for _, seg := range segments {
storage.ReadSegment(filepath.Join(db.dataDir, seg), mergedData)
}
// Drop tombstones — their work is done
finalData := make(map[string]memtable.Entry)
for k, v := range mergedData {
if !v.Deleted {
finalData[k] = v
}
}
// Write the merged output
newSegName := fmt.Sprintf("%d.seg", time.Now().UnixNano())
newSegPath := filepath.Join(db.dataDir, newSegName)
storage.WriteSegment(newSegPath, finalData)
// Register Bloom filter for the new segment
if bf, err := storage.BuildBloomFilter(newSegPath); err == nil {
db.segmentFilters[newSegName] = bf
}
// Delete old segments
for _, seg := range segments {
os.Remove(filepath.Join(db.dataDir, seg))
delete(db.segmentFilters, seg)
}
return nil
}
The merge is oldest-first into a single map. Since Go maps overwrite on duplicate keys, the last write (newest segment) naturally wins. Tombstones are dropped in the final pass because once all segments are merged, there are no older versions to protect against; the tombstone has served its purpose.
Results after one compaction cycle:
| Metric | Before | After | |---|---|---| | Segment files | 1,945 | 2 | | Disk usage | 1,953.79 MB | 393.42 MB | | Storage reclaimed | n/a | 79.86% | | Average GET latency | 1.230s | 186ms | | Compaction duration | n/a | 9.22s |
1,945 files down to 2 (the second is the WAL), 80% disk space reclaimed, GET latency cut by 6.6x. The 9.22-second compaction duration is a real cost: compaction holds a global write lock for its entire duration. Everything blocks. This is the biggest limitation of the current design.
Bloom Filters, and the Bug That Revealed Itself
With 1,945 segments and linear scan within each one, reads were slow: 1.230 seconds average GET latency. Even after compaction brought segments to 2, reads still required scanning the full segment file for the key.
Bloom filters solve the segment-selection problem. For each segment file, I build an in-memory probabilistic data structure that answers "is this key definitely not in this segment?" in constant time. If the filter says no, we skip the disk scan entirely.
type BloomFilter struct {
bitset []bool
size uint32
hashes uint8
}
func (b *BloomFilter) Add(key []byte) {
h1, h2 := hash(key)
for i := uint8(0); i < b.hashes; i++ {
idx := (h1 + uint32(i)*h2) % b.size
b.bitset[idx] = true
}
}
func (b *BloomFilter) MightContain(key []byte) bool {
h1, h2 := hash(key)
for i := uint8(0); i < b.hashes; i++ {
idx := (h1 + uint32(i)*h2) % b.size
if !b.bitset[idx] {
return false // definitely not present
}
}
return true // probably present (may be a false positive)
}
func hash(data []byte) (uint32, uint32) {
h := fnv.New64a()
h.Write(data)
sum := h.Sum64()
return uint32(sum), uint32(sum >> 32)
}
The double-hashing technique (h1 + i*h2) simulates k independent hash functions from two, which is a standard optimization. I used 10,000 bits and 3 hash functions. For the filter to say "definitely not present," at least one of the 3 bit positions must be unset. If all 3 are set, the key might be present, and this is a false positive. We pay for it with an unnecessary disk scan, but false positives don't cause wrong results, just wasted work.
The Bug
When I added Bloom filters and re-ran the benchmark, pre-compaction GET latency went from 1.230s to 1.378s. It got worse.
A Bloom filter having zero effect would mean identical latency. Getting slower meant something was adding overhead without adding benefit.
I added logging to the read path to count filter hits vs misses, and immediately saw the problem: segment files created during the current session (by flushLocked()) were never being skipped by the filter. The filter check was always failing to the "might be present" path for these segments.
The cause was a single missing line. In flushLocked():
// This line existed in Compact():
if bf, err := storage.BuildBloomFilter(segPath); err == nil {
db.segmentFilters[segName] = bf // ← THIS WAS MISSING in flushLocked()
}
BuildBloomFilter() was being called and the filter was being built, but it was never registered in db.segmentFilters. So when the read path checked:
bf, exists := db.segmentFilters[seg]
if exists && !bf.MightContain(key) {
continue
}
exists was always false for flushed segments. We fell through to SearchSegment() every time, paying the filter-construction overhead at Open() while getting none of the read benefit during the session.
One line added to flushLocked(), and the numbers changed dramatically:
| Metric | No Bloom Filter | With Bloom Filter (post-compaction) | |---|---|---| | GET latency, existing key | 186.1 ms | 175 µs | | GET latency, missing key | 358.7 ms | 163 µs | | Speedup (missing keys) | n/a | 2,196x |
163 microseconds vs 358 milliseconds. A missing key now resolves with an in-memory bit-array check instead of scanning every segment on disk.
The lesson here is mundane but important: benchmark before and after every optimization, and treat a result that's worse than baseline as a signal that something is broken, not just that the optimization didn't work. If I'd just run the benchmark once and seen "numbers improved overall," I might have missed that the filter was doing nothing for in-session reads.
The Real-World Integration
StrataKV was built for a concrete purpose: replacing Redis in the Blan Cloud Engine's execution cache. Here's how it's used:
import stratakv "github.com/Adityarya11/StrataKV/engine"
func InitStrataKV(dataDir string) {
var err error
DB, err = stratakv.Open(dataDir)
if err != nil {
log.Fatalf("StrataKV failed to open: %v", err)
}
}
func GetCachedOutput(hashKey string) (string, bool) {
val, found := DB.Get([]byte(hashKey))
return string(val), found
}
func SaveCacheOutput(hashKey, output string) {
DB.Put([]byte(hashKey), []byte(output))
}
The Blan backend hashes incoming C++ source code with SHA-256, checks StrataKV for a cached result, and either returns it or executes the code and stores the result. O(1) cache lookups, WAL-backed durability across restarts, no external process to manage.
The Gaps I Know Are There
Building this taught me exactly where the gaps between "educational implementation" and "production engine" are:
Skip list for MemTable. A sorted MemTable would enable sorted SSTable output, which enables a sparse index, which enables O(log n) reads within a segment instead of linear scan. This is the most impactful missing feature.
Bit-packed Bloom filter. I used []bool, which is 1 byte per bit, 8x memory waste. The correct implementation uses []uint64 with bitwise operations. Same logic, 8x smaller.
Per-segment filter sizing. My filter is fixed at 10,000 bits regardless of segment size. For a segment with 100,000 keys this is hopelessly saturated. The correct approach: at flush time, compute m = -n*ln(p) / (ln(2))^2 for your target false positive rate p and key count n, then build a filter of exactly that size.
Async flush and compaction. Both currently hold a global write lock. Flush causes a brief stall; compaction causes a 9-second stall. Real engines use background goroutines with immutable MemTable handoff for flush, and snapshot-based compaction that doesn't block readers.
WAL checksums. No corruption detection. A power loss mid-write can produce garbled bytes that look like valid records. CRC32 per record is the standard fix.
Group commit for WAL. Every write currently calls fsync individually. At high write throughput, batching writes and calling one fsync per batch (e.g., every 100ms or every 1,000 writes) dramatically improves throughput at minimal durability cost.
Tools I Used vs. Systems I Understand
None of the limitations above surprised me. I knew about them as I built it. Knowing them is the point.
Before this project, "Redis" and "RocksDB" were tools I used. After it, they're implementations of principles I understand. Ask why RocksDB uses a skip list for the MemTable, and I have an answer, because I tried the alternative and measured what it costs. Ask why WAL records need fsync before MemTable update, and I have an answer, because I traced the crash recovery path by hand and understood what invariant each ordering preserves.
The code is on GitHub and importable as a Go library:
go get github.com/Adityarya11/StrataKV@latest
The benchmark harness is in scripts/benchmark.go if you want to run it yourself. The full benchmark report is in BENCHMARKS.md.
Building things from scratch is the fastest way I know to actually understand them.