kvstore

A production-grade, embedded key-value store implemented from scratch in Go, built around an LSM-tree (Log-Structured Merge-tree) storage engine with leveled compaction, range scans, point-in-time snapshots, optional value compression, and an HTTP service mode. No third-party KV, storage, web framework, or RPC libraries are used - everything is built on the Go standard library.

Put/Delete
    │
    ▼
┌─────────────┐     fsync'd, checksummed       ┌──────────────┐
│     WAL      │ ───────────────────────────▶ │  active file  │
└─────────────┘                                └──────────────┘
    │ (only after WAL fsync succeeds)
    ▼
┌─────────────────┐   size threshold    ┌────────────────────────┐
│  active MemTable │ ──────────────────▶│ immutable MemTable(s)   │
│ (concurrent      │      exceeded       │ awaiting flush          │
│  skip list)       │                    └────────────────────────┘
└─────────────────┘                                │
    │ Get()/Scan() check here first                 │ single flush worker,
    ▼                                                │ strictly FIFO, always -> L0
┌─────────────────────────────────────────────────┐  ▼
│  L0  (overlapping, one table per flush)           │◀───────────
├─────────────────────────────────────────────────┤
│  L1  (non-overlapping, ~2 MiB target)             │◀── L0->L1 compaction
├─────────────────────────────────────────────────┤       (L0 count trigger)
│  L2  (non-overlapping, ~20 MiB target)            │◀── L1->L2 compaction
├─────────────────────────────────────────────────┤       (size trigger, x10/level)
│  ... up to L6 by default                          │
└─────────────────────────────────────────────────┘

[ Data Block   ]  repeated: [keyLen(4)][seq(8)][type(1)][valLen(4)][key][value]
[ Index Block  ]  repeated: [keyLen(4)][key][offset(8)]     (one entry per RECORD)
[ Bloom Filter ]  [numBits(4)][numHash(4)][bit array]
[ Footer       ]  [indexOffset(8)][indexLen(8)][bloomOffset(8)][bloomLen(8)][numEntries(8)][magic(4)]

Unlike a plain point-lookup format, a table may hold more than one record for the same key, stored newest-first within that key's group (sorted by Seq descending). This is what makes snapshot reads possible: compaction only drops an old version once no open snapshot could still need it.

Filenames encode the compaction level directly - L{level:02d}-{gen:020d}.sst

• so a plain directory listing recovers each table's level without opening the file; gen is purely a unique on-disk id and carries no recency meaning of its own (see below).

• Storage engine: LSM-tree with WAL, concurrent skip-list MemTable, immutable SSTables.
• Durability: strict write-ahead log, fsynced before every write is acknowledged.
• Crash recovery: WAL replay on startup, tolerant of a torn/corrupted tail.
• Concurrency: fine-grained sync.RWMutex throughout; reference-counted SSTable lifetimes so readers never race with compaction's file close/delete.
• Leveled compaction: L0 (overlapping, flush target) compacts into L1 once it accumulates too many tables; L1+ compact into the next level once total size crosses a geometrically growing target.
• Range scans (Scan(start, end)): a streaming, heap-merged iterator across the MemTable, every immutable MemTable, and every SSTable at once - no need to materialize the whole range into memory.
• Point-in-time snapshots (Snapshot()): Get/Scan against a snapshot only see writes that had completed when it was taken, built on the same per-write sequence number used for compaction's recency resolution. See the isolation caveat below.
• Value compression: optional per-value DEFLATE compression (WithCompression), applied only when it actually shrinks a value.
• HTTP service mode (-serve): a small stdlib-only REST API (PUT/GET/DELETE/scan/stats/healthz) for running the store as a standalone networked service.
• Observability: a dependency-free metrics package rendering Prometheus text-exposition format, instrumented throughout the engine (request counts, hit/miss rates, latency histograms, per-level SSTable gauges, flush/compaction counts and failures); structured logging via log/slog (with a -log-json flag for log-aggregation-friendly output); and a separate debug/ops HTTP listener (-debug-addr) exposing /metrics and net/http/pprof, deliberately isolated from the public API port.

Recency is resolved by per-record sequence number, not table order, table "version", or compaction level. Every write is assigned a globally monotonic Seq at the moment it's accepted, and that Seq is carried unchanged through every future compaction. Get/Scan never assume anything about slice order or which table is "newest" - they compare the Seq on every candidate record they find. This was essential for correctness (see the bug list below) and is also exactly what makes snapshots possible: a snapshot is just a pinned Seq value, filtered against at read time.

Flushing is single-threaded by design. A dedicated flushWorker goroutine processes rotated-out MemTables strictly one at a time, in the order they were rotated - always into level 0. This guarantees flushes complete in the same order the underlying writes happened, which is what lets background compaction safely conclude it has seen every table that could hold an older value for a key before dropping a tombstone.

Leveled compaction picks whole levels, not partial key ranges. L0->L1 compaction always takes every L0 table (they may overlap each other) plus every L1 table; Ln->Ln+1 compaction (n>=1) takes every table in level n plus every table in level n+1. A real production system (RocksDB, LevelDB) instead picks specific overlapping files to bound the cost of any one compaction - the whole-level approach here is a deliberate simplicity trade-off, still enough to demonstrate genuine multi-level space/read-amplification control.

Compaction determines "is it safe to drop a tombstone" via a conservative, whole-level check: a compaction pass is only "bottommost" for its keys if no table exists at any level deeper than the one it's compacting into (rather than a precise per-key-range overlap check against deeper levels). This trades a little delayed space reclamation for a much simpler correctness argument.

SSTable file lifetime is reference-counted. A reader (a Get, a Scan, or compaction's own merge) can be in the middle of reading a Table at the exact moment compaction decides to supersede it. Table.Acquire/Release/Retire defer the actual file close (and, for compacted-away tables, deletion) until every outstanding reader is done.

A Snapshot is guaranteed consistent for any key whose value, as of the snapshot, had already survived at least one MemTable rotation without being overwritten again in the same still-mutable MemTable generation. In the narrow window where a key is written more than once within one MemTable's lifetime, the MemTable only retains the latest write (it is a plain overwrite map, not itself multi-versioned) - so a snapshot taken between those writes may observe the newer value until that MemTable flushes or rotates. Once a write has left the active MemTable, full snapshot isolation applies, because SSTables retain every version an open snapshot might still need (see sstable.Merge's minKeepSeq parameter and the MVCC-style retention walk it drives).

This is a deliberate, bounded-scope decision rather than an oversight: true full-history MVCC would require the MemTable itself to be multi-versioned (as RocksDB's memtable, keyed on {userkey, seq}, is), which is a significantly larger change than fits this project's scope. The engine and CLI/README are explicit about the boundary rather than silently claiming stronger guarantees than are actually provided.

Every feature here was validated by writing (and then deliberately stress-running, with -race, dozens of iterations of) integration tests rather than by inspection alone. Several real, non-obvious bugs were caught this way:

1. Trusting SSTable list order for recency. An early Get() assumed the last-appended table was newest. Two background operations (a flush and a compaction) can finish - and get appended - in the opposite order they were started. Fixed by resolving recency explicitly per-record via Seq, never by list position.
2. Compaction re-numbering ("leapfrogging") data it touched. Stamping each compacted output with a fresh version number could promote a long-untouched key above a genuinely newer tombstone that hadn't been swept into the same pass yet, silently resurrecting deleted data. Fixed by switching entirely to the immutable per-record Seq.
3. A reader racing with compaction's file close/delete. Fixed with the reference-counted Table lifecycle described above.
4. Concurrent flush goroutines completing out of write-order, letting a delete's SSTable be compacted before an earlier put's SSTable for the same key had even been written. Fixed by serializing all flushes through one worker goroutine.
5. Dropping a tombstone while an older version was retained for a snapshot. Once snapshot support needed compaction to sometimes keep more than one version of a key, an unconditional "drop the tombstone at bottommost" rule became unsafe: with the tombstone gone, an ordinary unbounded read would fall through to the older, snapshot-only version and see it as if it were still live. Fixed by only allowed dropping the tombstone when no active snapshot needs anything older than it either - i.e. exactly when nothing would be left standing below it anyway.

import "kvstore/engine"

e, err := engine.Open("./data",
    engine.WithFlushThreshold(4*1024*1024),
    engine.WithL0CompactionTrigger(4),
    engine.WithBaseLevelSizeBytes(2*1024*1024),
    engine.WithLevelSizeMultiplier(10),
    engine.WithCompression(false),
)
if err != nil {
    // handle
}
defer e.Close()

err = e.Put([]byte("key"), []byte("value"))
val, err := e.Get([]byte("key"))     // engine.ErrNotFound if absent/deleted
err = e.Delete([]byte("key"))

// Range scan: nil start/end means unbounded on that side.
it, err := e.Scan([]byte("a"), []byte("m"))
defer it.Close()
for {
    key, value, ok, err := it.Next()
    if err != nil { /* handle */ }
    if !ok { break }
    // use key, value
}

// Point-in-time snapshot.
snap, err := e.Snapshot()
defer snap.Close()
val, err = snap.Get([]byte("key"))            // as of snap's creation time
it, err = snap.Scan(nil, nil)                 // likewise

go run ./cmd/kvstore -dir ./data                              # interactive REPL
go run ./cmd/kvstore -dir ./data -bench                        # concurrent read/write benchmark
go run ./cmd/kvstore -dir ./data -serve -addr :8080            # HTTP server
go run ./cmd/kvstore -dir ./data -serve -debug-addr :6060      # + metrics/pprof on a separate debug port (default on)
go run ./cmd/kvstore -dir ./data -serve -log-json              # structured JSON logs instead of text

By default, running with -serve also starts a separate debug/ops listener on :6060 (override with -debug-addr, or set it to "" to disable) exposing /metrics (Prometheus text format) and /debug/pprof/* (net/http/pprof). This is deliberately a different port from the public API (-addr): metrics and profiling endpoints should not be reachable from wherever untrusted clients can reach the KV API itself, so in a real deployment -debug-addr would typically be bound to localhost or otherwise firewalled off, separately from whatever's in front of -addr.

REPL commands: PUT <key> <value>, GET <key>, DELETE <key>, SCAN <start> <end> [limit] (use "" for unbounded), SNAPSHOT / SNAPSHOT-END (subsequent GET/SCAN read as of that point in time until closed), STATS, EXIT.

PUT    /kv/{key}                     body = raw value bytes   -> 204
GET    /kv/{key}                                              -> 200 + raw value, 404 if absent
DELETE /kv/{key}                                              -> 204
GET    /scan?start=&end=&limit=                                -> 200 + JSON [{"key","value"} base64]
GET    /stats                                                  -> 200 + JSON engine.Stats
GET    /healthz                                                -> 200 "ok"

curl -X PUT --data 'hello' http://localhost:8080/kv/greeting
curl http://localhost:8080/kv/greeting
curl "http://localhost:8080/scan?start=a&end=z&limit=100"
curl http://localhost:8080/stats

The whole observability story - the store, a load generator producing continuous traffic, Prometheus scraping it, and a pre-provisioned live Grafana dashboard - runs with one command:

docker compose up --build

Then open:

• Grafana: http://localhost:3000 - the "kvstore Overview" dashboard loads automatically (anonymous admin access is enabled for this demo stack only; see docker-compose.yml), with panels for operation rates, get hit/miss rate, write/get latency percentiles, SSTables per level, MemTable state, and flush/compaction activity, all updating live every 5 seconds.
• Prometheus: http://localhost:9090 - the raw scrape target and query interface, if you want to run your own PromQL.
• kvstore API: http://localhost:8080 - the same HTTP API described below, reachable directly (curl -X PUT --data hello localhost:8080/kv/greeting).
• kvstore debug endpoints: http://localhost:6060/metrics and http://localhost:6060/debug/pprof/ - what Prometheus is actually scraping, and pprof profiling, on their own listener (see "Observability" below for why this is a separate port from 8080).

The loadgen service (a tiny script hitting the API in a loop - see deploy/loadgen.sh) exists purely so the dashboard has real, moving data to show instead of sitting flat; it's not part of the kvstore project itself. Data persists in a Docker volume (kvstore-data) across docker compose down/up cycles; use docker compose down -v to wipe it.

Everything here builds on the plain Dockerfile at the repo root (a standard two-stage Go build producing a small Alpine-based final image) and docker-compose.yml; nothing about the engine itself changes when running this way versus go run ./cmd/kvstore directly.

go test ./...                        # correctness
go test ./... -race -count=20        # stress the concurrency guarantees

Tests are split across four packages:

• router: the ring (determinism, distribution balance - this test is what caught the FNV-1a clustering bug described in ringHash's doc comment) and full integration tests that stand up several real engine + server instances as shards behind a real Proxy: keys land on exactly one shard, scans merge into correct global order, limit applies after the merge, stats aggregate, and one shard going down fails only that shard's keys (and fails scans outright rather than returning partial data).
• metrics: unit tests for the metrics primitives themselves - counter/ gauge/vec rendering, histogram bucket cumulativeness, and a concurrent race test.
• sstable: unit tests for the storage primitives in isolation - write/read round-trips, multi-version Get respecting a Seq bound, range iteration, compression round-trips, the reference-counted Table lifecycle, and (critically) Merge's snapshot-aware retention logic, including a regression test for bug #5 above.
• engine: end-to-end integration tests - basic CRUD, flush/reopen, crash recovery (including a deliberately corrupted WAL tail), leveled compaction promoting tables across levels, range scans across the MemTable and multiple SSTables at once, snapshot isolation, compression round-tripping through the full engine, metrics reflecting real operations, and concurrent stress tests (puts/deletes/overwrites racing across many goroutines against shared keys with tiny flush/compaction thresholds) - the regime that exposed every bug listed above.

Everything above describes a single node. router/ and cmd/kvrouter/ add horizontal sharding: the keyspace is partitioned across a fixed set of independent kvstore instances (each one exactly the single-node engine described above, unmodified) via consistent hashing, fronted by a routing layer that presents the same HTTP API as a single node.

                     ┌──────────────┐
   client  ────────▶ │   kvrouter    │  (stateless, horizontally scalable)
                     │ consistent-   │
                     │ hash ring     │
                     └──────┬───────┘
              ┌─────────────┼─────────────┐
              ▼             ▼             ▼
        ┌──────────┐  ┌──────────┐  ┌──────────┐
        │ kvstore-0 │  │ kvstore-1 │  │ kvstore-2 │   (StatefulSet: each
        │ (shard)   │  │ (shard)   │  │ (shard)   │    its own PVC/disk)
        └──────────┘  └──────────┘  └──────────┘

• Point operations (PUT/GET/DELETE /kv/{key}): the router hashes the key with a consistent-hash ring (SHA-256-based, 128 virtual nodes per shard) and forwards the request to the one shard that owns it.
• Range scans (GET /scan): hash-based sharding does not preserve key order across shards, so the router fans the same scan out to every shard concurrently and performs a k-way merge of their (already sorted) results into one globally ordered stream - a limit is applied only after that merge, never per-shard, since applying it per-shard first could drop entries that belong in the true global top-N.
• GET /stats: fanned out to every shard and aggregated, with both cluster-wide totals and a per-shard breakdown.
• GET /healthz: reports per-shard health, not just one boolean - without replication, each shard is its own failure domain, so "shard 1 is down" and "the whole cluster is down" are different, both-important facts.
• Partial failure is isolated, not cluster-wide: if one shard is unreachable, point operations for keys on other shards keep working normally; only the down shard's portion of the keyspace is affected. A scan, however, fails outright if any shard can't answer, rather than silently returning partial results - consistent with this project's general stance of surfacing a correctness gap instead of hiding it.

This is deliberately sharding without replication or consensus, not a full distributed database:

• No replication / automatic failover. Each shard is a single point of failure for its slice of the keyspace. If a shard's pod is lost but its disk (PVC) survives, Kubernetes reschedules it and it recovers via the same WAL-replay crash recovery the single-node engine always has; if the disk itself is lost, that shard's data is gone. A production system would replicate each shard (e.g. via Raft) so a single node failure doesn't cost availability or durability.
• No dynamic membership or automatic rebalancing. The shard count is fixed for the ring's lifetime and configured statically (an explicit address list). Changing it changes which shard owns which key; this project does not implement live data migration to match, so scaling the shard count is a manual, offline operation, not something that happens transparently.
• No cross-shard transactions. Operations are all single-key (or, for scans, an unordered-across-shards fan-out/merge of independent single-key reads) - there's no multi-key atomicity across shards.

These are the same kind of explicit, documented scope boundaries as the engine's own snapshot-isolation caveat earlier in this README - real gaps, named rather than hidden, with the reasoning for why they're out of bounds for this project.

docker compose -f docker-compose.distributed.yml up --build

This starts 3 shards plus a router (localhost:9000) plus a load generator, using the exact same images and router binary the Kubernetes manifests use:

curl -X PUT --data hello http://localhost:9000/kv/greeting
curl http://localhost:9000/kv/greeting
curl http://localhost:9000/stats      # aggregated across all 3 shards
curl http://localhost:9000/healthz    # per-shard health

Each shard's own debug endpoint stays reachable individually too (:6060, :6061, :6062), same as the single-node setup, if you want to point your own Prometheus at a specific shard.

kubectl apply -f k8s/

(The 00-/10-/20- filename prefixes are what make kubectl apply -f k8s/ process them in the right order - namespace, then shards, then router - without needing Kustomize or Helm.) This creates:

• a kvstore namespace,
• a 3-replica StatefulSet named kvstore plus a headless Service of the same name, giving each shard a stable identity (kvstore-0.kvstore, kvstore-1.kvstore, kvstore-2.kvstore) and its own PersistentVolumeClaim,
• a Deployment named kvrouter (2 replicas by default, since it's stateless and scales independently of the shard count) configured via a ConfigMap listing those same three shard addresses, plus a ClusterIP Service in front of it.

You'll need to build and push kvstore:latest and kvrouter:latest (both build from the one Dockerfile, via --target kvstore / --target kvrouter) to a registry your cluster can pull from, and update the manifests' image: fields accordingly - they're left as plain kvstore:latest/kvrouter:latest rather than pointing at a specific registry, since that's inherently environment-specific.

Once running, kubectl port-forward svc/kvrouter 9000:9000 -n kvstore gets you the same localhost:9000 API as the Docker Compose version above.

Validation note: this sandbox has no Docker daemon and no network access to any container registry, so I could not run docker compose up or kubectl apply against a live cluster to test this end to end. What I did do: validated every manifest against the real Kubernetes OpenAPI schemas with kubeconform (all 6 resources valid), manually cross-checked every label selector/ConfigMap reference/namespace across files for consistency, validated both Compose files with docker compose config, linted the Dockerfile with hadolint, and - most importantly - ran the actual compiled kvstore and kvrouter binaries as real, separate OS processes on this machine (three shards plus a router, driven entirely by curl), which caught a genuine bug in the consistent-hash ring's hash function (see the router package's ringHash doc comment) before it ever reached you. What remains untested is whatever only a real container runtime or cluster would catch (image build specifics, cluster networking/DNS quirks on your specific environment) - if something doesn't come up cleanly, that's the most likely place to look.

• Leveled compaction merges whole levels rather than picking specific overlapping files, and its "safe to drop a tombstone" check is a conservative whole-level test rather than a precise per-key-range overlap check against deeper levels.
• The SSTable index is a full per-record index rather than a sparse one; simpler and fine at moderate scale, but uses more memory per table than a sparse index would at very large table sizes.
• Per-value compression (rather than per-block) keeps each record's byte offset meaningful for direct seeks, at the cost of a worse compression ratio than block-level compression would give (no shared dictionary across records).
• Snapshot isolation has the in-memory-overwrite caveat described above: it is not full MVCC, since the MemTable itself is not multi-versioned.
• If a background flush repeatedly fails (e.g. persistent disk-full), the affected MemTable stays queued in memory with no automatic retry loop beyond process restart.