MiniKV

A small, LSM-tree based key-value storage engine in Go, built as a learning project.

MiniKV is a single-node key-value store demonstrating the core building blocks of a modern LSM storage engine:

• Segmented Write-Ahead Log (WAL) with CRC32C-protected records and an fsync-on-commit durability mode.
• In-memory MemTable (skip list) with monotonic sequence numbers.
• Persistent SSTable files with a magic header/footer, a block-based data section (~4 KiB blocks with per-block CRC and optional snappy compression), a sparse block index for binary search, and a file-level Bloom filter so negative lookups skip the disk read.
• Pluggable compaction strategies (leveled, size-tiered) sharing a k-way merge that resolves duplicates by sequence number and drops tombstones / expired TTL entries only at the bottom level.
• TTL on individual keys, persisted in the WAL and SSTable and honored on reads and iteration.
• Atomic write batches (Batch + KV.Write) with WAL commit markers so a crash never leaves a partially-applied batch.
• Serializable optimistic transactions (KV.BeginTxn): reads at a snapshot, writes buffered as a Batch, commit validates the read set against a bounded commit log and applies atomically on no conflict.
• Shared block cache (LRU, byte-budgeted) amortises decompression and CRC checks across repeated point lookups against hot blocks.
• Prefix-compressed keys with restart points inside every SSTable block keep storage compact while still allowing O(log restarts) point seeks within a block.
• Range delete (KV.DeleteRange(start, end)) materialises point tombstones for every key in [start, end) in bounded chunks.
• Stats (KV.Stats()) returns atomic counters for puts/deletes/gets, txn commits/conflicts, flush & compaction throughput, block-cache hit ratio, and per-level SSTable file counts and bytes.
• HTTP+JSON server (minikv/kv/httpapi) exposes the engine over a small REST API (/v1/kv/{key}, /v1/batch, /v1/range, /v1/range/delete, /v1/stats). The bundled CLI can launch it with minikv -serve :8080.
• gRPC server (minikv/kv/grpcapi) exposes the same surface plus a streaming Scan and a streaming Replicate RPC. Schema lives in proto/minikv.proto; the CLI starts it with minikv -grpc :9090.
• Async leader/follower replication over both HTTP (NDJSON) and gRPC (Replicate stream): followers receive a snapshot bootstrap followed by a live tail of every commit and apply events via KV.ApplyReplica. Followers resume from their local LastSeq() on restart so reconnects skip already-applied events.
• Snapshot + ordered iterator API for consistent point-in-time scans that pin SSTables against compaction for the snapshot's lifetime.
• Background flush and compaction workers owned by the LSM tree; Close drains them and reports errors.
• MANIFEST log of VersionEdit records (adds/removes + next file number + last seq) so startup recovers the live SSTable set from a fsynced log instead of a directory scan, and every flush or compaction is committed atomically.

flowchart TB
    Client([Client / CLI])

    subgraph KV["KV (public API)"]
        direction TB
        API["Put / Get / Delete<br/>PutWithTTL / Write(Batch)<br/>Snapshot / NewIterator"]
        Batch["Batch<br/>(buffered ops)"]
    end

    subgraph Write["Write path"]
        direction TB
        WAL["WAL<br/>segmented, CRC32C<br/>batch commit markers"]
        MT["Active MemTable<br/>(skip list)"]
        IMT["Immutable MemTable<br/>(flush queue)"]
    end

    subgraph LSM["LSM tree"]
        direction TB
        Flush["Flush worker"]
        Compact["Compaction worker<br/>leveled / size-tiered"]
        Cache["Index + Bloom cache"]
        Snap["Snapshot refcounts<br/>(pin SSTables)"]
    end

    subgraph Disk["On-disk SSTables (v3)"]
        direction LR
        L0["L0 files"]
        L1["L1 files"]
        Ln["L2 .. Ln"]
    end

    Client --> API
    API --> Batch
    API -->|writes| WAL
    API -->|reads| MT
    Batch -->|AppendBatch + WriteBatch| WAL
    WAL --> MT
    MT -->|size threshold| IMT
    IMT --> Flush
    Flush -->|WriteSSTable<br/>+ snappy?| L0
    Compact -->|k-way merge| L1
    L0 --> Compact
    L1 --> Compact
    Compact --> Ln
    API -->|Get miss in MT| Cache
    Cache --> L0
    Cache --> L1
    Cache --> Ln
    API --> Snap
    Snap -.pins.-> L0
    Snap -.pins.-> L1
    Snap -.pins.-> Ln

cfg := kv.DefaultConfig("./data")
cfg.CompactionStrategy = "leveled" // or "size-tiered"
cfg.Compression = "snappy"          // or "none" (default)
db, err := kv.NewKV(cfg)
// ...
db.Put(key, value)
db.PutWithTTL(key, value, 30*time.Second)
db.Get(key)
db.Delete(key)

// Context-aware variants:
db.PutCtx(ctx, key, value)
db.PutCtxWithTTL(ctx, key, value, ttl)
db.GetCtx(ctx, key)
db.DeleteCtx(ctx, key)

// Atomic write batch (all-or-nothing on crash):
b := kv.NewBatch()
b.Put([]byte("a"), []byte("1"))
b.PutWithTTL([]byte("session"), []byte("tok"), 30*time.Second)
b.Delete([]byte("old"))
if err := db.Write(b); err != nil { /* ... */ }

// Serializable transaction (read-set validated at Commit):
tx, _ := db.BeginTxn()
balance, _, _ := tx.Get([]byte("alice"))
tx.Put([]byte("alice"), debit(balance, 5))
if err := tx.Commit(); errors.Is(err, kv.ErrTxnConflict) {
    // retry...
}

// Consistent point-in-time view:
snap, _ := db.Snapshot()
defer snap.Close()
v, ok, _ := snap.Get(key)

// Ordered range scan (nil bounds = unbounded):
it, _ := db.NewIterator([]byte("a"), []byte("m"))
defer it.Close()
for it.Next() {
    fmt.Printf("%s = %s\n", it.Key(), it.Value())
}

The store is safe for concurrent use.

Config.SyncMode selects the WAL sync policy:

SyncAlways is the default and is the only mode that survives power loss.

The active memtable is guarded by a mutex; the LSM read path takes a read lock only long enough to snapshot the SSTable metadata list before doing disk I/O. Compaction atomically swaps SSTable metadata under the same lock and evicts stale index-cache entries before deleting files, so concurrent Get calls never observe a file that has been compacted away. Snapshots take an atomic reference count on each pinned SSTable; compaction defers deletion of pinned files until the last snapshot releases them.

The CI workflow runs go test -race -cover ./... and go vet ./....

cmd/cli.go            Interactive CLI + HTTP/gRPC/raft mode dispatcher
cmd/raft.go           Raft node bootstrap, self-announce loop, join client
kv/doc.go             Package overview
kv/kv.go              Public KV API (Put/Get/Delete/PutWithTTL/Snapshot/NewIterator)
kv/batch.go           Atomic write-batch API
kv/txn.go             Serializable OCC transactions (BeginTxn / Commit / Rollback)
kv/memtable.go        Skip-list MemTable
kv/wal.go             Segmented WAL with CRC32C records + batch commit markers
kv/sstable.go         SSTable read/write + block index + snappy + Bloom filter (v4 format)
kv/bloom.go           Bloom filter implementation
kv/lsm.go             LSM tree, flush + compaction workers, index cache, snapshot pinning
kv/manifest.go        MANIFEST log (VersionEdit replay on startup)
kv/compaction.go      Strategy interface + leveled and size-tiered strategies
kv/snapshot.go        Snapshot + merged-order Iterator (exposes ExpireAt per entry)
kv/acktracker.go      Sync-replica quorum tracking for the leader/follower path
kv/httpapi/           HTTP+JSON server (REST: /v1/kv, /v1/batch, /v1/range, /v1/stats, NDJSON /v1/replicate/stream)
kv/grpcapi/           gRPC server + follower client (bidi Replicate stream with acks)
kv/raftnode/          hashicorp/raft FSM + Node wrapper + HTTP control plane
proto/                gRPC service definition (minikv.proto)
tests/kv_test.go      Unit, recovery, concurrency, TTL, snapshot, batch, and compaction tests
tests/faultinject_test.go  Spawn-the-binary SIGKILL recovery tests
.github/workflows/    CI (build, vet, race tests, golangci-lint)
.golangci.yml         Linter configuration

go build ./...
go run ./cmd -data ./data

> put k1 v1
OK
> put-ttl session-x token 30s
OK
> get k1
v1
> scan - -
  k1 = v1
  session-x = token
(2 entries)
> delete k1
OK

go test -race ./...

go test -bench=. -benchmem ./tests
# narrow:
go test -bench=BenchmarkGet -benchmem ./tests

Reported on Apple M2 Pro, SyncNone, in-memory tmp dir, 1 KiB values:

SyncAlways Put throughput is dominated by fsync latency and is orders of magnitude slower; that's the point of the durability knob.

Set with Config.CompactionStrategy (or -strategy on the CLI).

Leveled (default):

• L0 collects new SSTables produced by memtable flushes; when L0 reaches Config.Level0Fanout files, all L0 files are merged into L1.
• L1 and deeper collect promoted SSTables; when a level reaches Config.LevelNFanout files it is merged into the next level.

Size-tiered:

• SSTables on each level are grouped into power-of-two size buckets; once a bucket holds at least Config.Level0Fanout files it is merged in place (L0 promotes to L1).
• Good for write-heavy workloads where read amplification is less critical.

Both strategies use the same k-way merge ordered by (key asc, seq desc), so the newest write always wins. Tombstones and expired TTL entries are kept until they would be promoted into a level with no deeper data, at which point they are safe to drop.

MiniKV supports primary-backup replication out of the box. Followers connect to the leader's gRPC Replicate stream, receive a snapshot bootstrap (when starting fresh) followed by a tail of every commit, and apply each event via KV.ApplyReplica. The stream is bidirectional: followers send ack_seq frames as they durably apply events.

Two modes:

• Asynchronous (default, Config.SyncReplicas == 0): writes return as soon as the local WAL is durable. Followers catch up at their own pace. A leader crash can lose any commits that were not yet streamed.
• Synchronous quorum (Config.SyncReplicas == N, N > 0): a write blocks until at least N followers have acked its seq, or Config.ReplicationTimeout (default 5s) elapses. On timeout the write returns kv.ErrReplicationTimeout; the commit is still durable locally and is replayed once a follower catches up.

The HTTP NDJSON /v1/replicate/stream endpoint is async-only — it has no ack channel — so synchronous replication requires gRPC.

Recovery is validated by tests/faultinject_test.go, which spawns a real minikv binary, drives it via HTTP, sends SIGKILL, restarts with the same data dir, and asserts that every write whose response returned 204-NoContent is readable after the restart — including under concurrent multi-writer load.

• Single static leader (non-raft mode). In the default leader/follower topology there is no automatic failover; the operator picks the leader. For automatic election use raft mode (see below).
• The format on disk is versioned but has no forward migration: opening a store written by an older incompatible version returns ErrUnsupportedFormat.

When -raft-id is set the binary runs as one node of a Raft cluster backed by github.com/hashicorp/raft. The LSM acts as the FSM: every write is proposed to the Raft log and applied on every node in commit order. Reads are served locally.

Bring up a 3-node cluster on one machine:

# Terminal A — bootstrap the cluster:
minikv -raft-id n1 -data ./d1 -raft-addr 127.0.0.1:7001 -raft-http :8081 -raft-bootstrap

# Terminal B — start a follower and ask the leader to admit it:
minikv -raft-id n2 -data ./d2 -raft-addr 127.0.0.1:7002 -raft-http :8082 -raft-join 127.0.0.1:8081

# Terminal C — another follower:
minikv -raft-id n3 -data ./d3 -raft-addr 127.0.0.1:7003 -raft-http :8083 -raft-join 127.0.0.1:8081

Each node exposes a small HTTP control plane:

• PUT /v1/kv/<key> body {"value": "<base64>"} — proposed via raft. A request that arrives on a non-leader is reverse-proxied to the leader using the replicated peer-HTTP map; the caller gets the leader's response (typically 204 No Content) and never has to retry. If the leader's HTTP address hasn't been announced yet, the handler falls back to 503 with X-Leader (raft addr) and X-Leader-HTTP (HTTP addr, when known) hints.
• GET /v1/kv/<key> — local (potentially stale) read.
• DELETE /v1/kv/<key> — proposed via raft (forwarded on non-leader).
• GET /v1/raft/status — {leader, leader_id, is_leader, http}.
• GET /v1/raft/peers — replicated {id: http_advertise} peer map.
• POST /v1/raft/join body {id, addr} — leader-only AddVoter.
• POST /v1/raft/transfer optional body {id, addr} — leader-only; hands leadership to the named server, or to any other voter when the body is omitted. Useful for graceful rolling restarts.
• POST /v1/raft/peer_announce body {id, http} — leader-only; publishes a peer's HTTP advertise address into the replicated map. The CLI auto-calls this on join and again whenever a node observes itself as the new leader.

Pre-vote is enabled by default (the TCP transport supports it), so a brief network partition won't cause unnecessary term bumps when a flapping follower reconnects.

If the leader is killed, the survivors elect a new one within a few hundred milliseconds and writes resume. This path is exercised by TestRaftLeaderFailover and TestRaftLeadershipTransfer in kv/raftnode/; TestHTTPForwardingProxiesNonLeaderWrites covers the reverse-proxy fast path.

• Multi-region replication topologies.