High-Performance Sharded Key-Value Store in Go

A concurrent, in-memory key-value store built in Go featuring lock striping (sharded concurrency), exact $O(1)$ LRU eviction via custom doubly-linked lists, RESP (Redis Serialization Protocol) compatibility for native integration with redis-cli, and Append-Only File (AOF) persistence.

---

📊 Benchmark Results & Shard Scaling

To evaluate the impact of lock striping, we conducted empirical benchmarks measuring throughput and latency percentiles as the shard count scaled from 1 (global lock) up to 128 independent shards under high write/read contention.

Methodology Note: To isolate internal lock contention and LRU list mutation from OS kernel TCP socket overhead, the shard scaling benchmark tests the in-memory engine across concurrent goroutines. End-to-end TCP loopback benchmarks (including network stack traversal and RESP serialization) achieve ~37k–50k ops/sec with sub-millisecond p50 latency.

In-Memory Shard Scaling Experiment

• Workload: 300,000 requests (50% GET / 50% SET)
• Concurrency: 30 concurrent worker goroutines
• Key Range: 20,000 keys (generating realistic hash collisions)

Shard Count	Throughput (ops/sec)	p50 Latency	p90 Latency	p99 Latency	Speedup vs Global Lock
1 (Global Lock)	1,898,558 op/s	347 ns	480 ns	156.42 µs	1.00x
2	2,198,121 op/s	417 ns	542 ns	209.23 µs	1.16x
4	2,363,148 op/s	358 ns	511 ns	155.31 µs	1.24x
8	2,273,747 op/s	335 ns	490 ns	29.99 µs	1.20x
16	3,395,021 op/s	326 ns	480 ns	2.37 µs	1.79x
32	3,133,491 op/s	310 ns	460 ns	1.50 µs	1.65x
64	3,350,987 op/s	302 ns	445 ns	766 ns	1.77x
128	3,236,095 op/s	301 ns	440 ns	652 ns	1.70x

Performance Visualization

Key Finding: Increasing shards from 1 (single global lock) to 64/128 shards:

1. Boosted throughput by +79% (from 1.89M to 3.39M ops/sec).
2. Slashed p99 tail latency from 156.4 µs down to 652 ns — an over 240x reduction in tail contention.

---

🏗 Architecture & Design

                     +---------------------------------------+
                     |  TCP Server (:6379) - RESP Protocol   |
                     |  (Goroutine per client connection)    |
                     +---------------------------------------+
                                         |
                       FNV-1a Hash(key) % numShards
                                         |
     +-------------------+-------------------+-------------------+
     |                   |                   |                   |
+----+----+         +----+----+         +----+----+         +----+----+
| Shard 0 |         | Shard 1 |         | Shard 2 |   ...   |Shard N-1|
| Mutex   |         | Mutex   |         | Mutex   |         | Mutex   |
| Hashmap |         | Hashmap |         | Hashmap |         | Hashmap |
| LRU List|         | LRU List|         | LRU List|         | LRU List|
+----+----+         +----+----+         +----+----+         +----+----+
     |                   |                   |                   |
     +-------------------+-------------------+-------------------+
                                         |
                        +--------------------------------+
                        | AOF Persistence Engine (fsync) |
                        +--------------------------------+

1. Lock Striping & Colocated Sharding

Instead of a single global lock or fragile per-key locks, the key space is partitioned into $N$ independent shards (default: 32) using FNV-1a 64-bit hashing. Each shard maintains its own sync.Mutex, hashmap, and LRU list. Keys in different shards execute concurrently with zero lock contention.

2. Custom Doubly Linked List + Hashmap LRU

• $O(1)$ Lookup: Hashmap map[string]*Node maps keys directly to list nodes.
• $O(1)$ Reordering: Accessed or updated keys are promoted to the MRU position (head) in-place without memory reallocation.
• $O(1)$ Eviction: When a shard reaches capacity, the least-recently-used node at the tail is unlinked and removed from the map.
• Sentinel Head & Tail: Implemented with sentinel nodes to eliminate nil checks and branch mispredictions.

3. Redis RESP Protocol Support

Implements RESP2 data types (Simple Strings, Bulk Strings, Integers, Arrays, Errors) and inline plain-text commands. You can connect with standard redis-cli, redis-benchmark, nc, or any Redis client library.

4. Durability via Append-Only Log (AOF)

All write operations (SET, DEL, FLUSHDB) are persisted to an append-only log file in standard RESP format, with configurable fsync policies (always, everysec, no). On server restart, the AOF is replayed to reconstruct the in-memory state.

---

🥊 Comparison: This Store vs. Redis

Dimension	Real Redis	This Go Key-Value Store
Concurrency Model	Single-threaded event loop	Multi-threaded with Sharded Locking
Multi-Core Utilization	Requires multi-process clustering	Scales across all CPU cores natively in 1 process
LRU Eviction	Approximated (samples 5 random keys)	Exact $O(1)$ LRU (hashmap + doubly-linked list per shard)
Memory / GC	Manual C (jemalloc, sds strings)	Go Managed Runtime + GC
Persistence	RDB snapshots + AOF background rewrite	Sequential AOF with configurable fsync & replay
Protocol	RESP2 & RESP3	RESP2 + Inline Commands (redis-cli compatible)

---

💡 Deep Dive: Exact LRU vs. Redis Approximated LRU Tradeoff

What Real Redis Actually Does

Real Redis does not maintain an exact LRU order using a linked list. Instead, it uses approximated LRU:

• Every key stores a small timestamp (roughly, "when was this last accessed") as part of its object metadata — this piggybacks on data Redis already keeps, so it is nearly free.
• When Redis needs to evict something, it does not walk an ordered list — instead, it randomly samples a small number of keys (default: 5), checks their timestamps, and evicts whichever key in that sample is oldest.
• No global structure tracks exact order across the entire keyspace.

This is called "approximated" because it does not guarantee evicting the actual least-recently-used key across the whole keyspace — just the oldest within a random sample. In practice, this provides an effective approximation, especially as sample size increases, but it is provably non-exact.

Why Redis Made That Tradeoff

There are two primary costs of maintaining an exact LRU linked list at global scale:

1. Memory Overhead: A full doubly-linked list requires two extra pointers (prev/next) per key, which accumulates significantly across millions of keys.
2. Read-Contention Cost: With a linked list, every single GET must move a node to the front of the list. That touches shared list pointers, turning read-only operations into writes against a shared, lock-guarded structure. Random sampling avoids this: a GET can update a local timestamp without contending over a global linked list.

Why This Store Uses Exact LRU via Sharding

In this project, we chose exact $O(1)$ LRU over approximated LRU because our store's concurrency model is sharded:

• The doubly-linked list lives inside an isolated shard rather than globally across the entire store.
• Contention on the linked list is localized only to concurrent requests hashing to the exact same shard.
• We deliberately trade a minor amount of pointer memory for 100% deterministic LRU eviction correctness, relying on lock striping to eliminate the contention bottleneck that makes global linked lists prohibitive in single-threaded or globally-locked architectures.

---

🚀 Quick Start

Build & Run the Server

# Build binary
go build -o kvserver ./cmd/server

# Run with default configuration (:6379, 32 shards, 1M keys capacity)
./kvserver

# Customize shards, capacity, and enable AOF persistence
./kvserver -port 6379 -shards 64 -capacity 500000 -aof appendonly.aof -fsync everysec

Interacting with the Store

Using redis-cli:

$ redis-cli -p 6379
127.0.0.1:6379> PING
PONG
127.0.0.1:6379> SET user:100 "Alice Smith"
OK
127.0.0.1:6379> GET user:100
"Alice Smith"
127.0.0.1:6379> DBSIZE
(integer) 1
127.0.0.1:6379> EXISTS user:100
(integer) 1
127.0.0.1:6379> DEL user:100
(integer) 1
127.0.0.1:6379> INFO
"# Stats\r\nkeys:0\r\ncapacity:1000000\r\nshards:32"

Using netcat / telnet (Inline Text Commands):

$ nc 127.0.0.1 6379
SET greeting "Hello World"
+OK
GET greeting
$11
Hello World
QUIT
+OK

---

🧪 Testing & Race Detection

# Run all unit and integration tests with Go Race Detector
go test -v -race ./...

# Run parallel microbenchmarks
go test -bench=. -benchmem ./pkg/sharded/...

---

📁 Repository Structure

kvstore/
├── .github/
│   └── workflows/
│       └── ci.yml       # GitHub Actions automated test & race detection CI
├── assets/
│   └── shard_scaling_benchmark.svg # Benchmark visualization chart
├── cmd/
│   ├── server/          # TCP Server main entrypoint
│   │   └── main.go
│   └── benchmark/       # Load tester & shard scaling experiment CLI
│       └── main.go
├── pkg/
│   ├── basic/           # Phase 1: Simple single-threaded map store
│   │   ├── store.go
│   │   └── store_test.go
│   ├── lru/             # Phase 2: Doubly-linked list + LRU cache
│   │   ├── list.go
│   │   ├── cache.go
│   │   └── cache_test.go
│   ├── sharded/         # Phase 3: Sharded concurrent store (lock striping)
│   │   ├── hasher.go
│   │   ├── shard.go
│   │   ├── store.go
│   │   ├── store_test.go
│   │   ├── stress_test.go
│   │   └── bench_test.go
│   ├── resp/            # Phase 4: RESP protocol parser & writer
│   │   ├── resp.go
│   │   └── resp_test.go
│   ├── server/          # Phase 4: TCP Server with client goroutine pool
│   │   ├── server.go
│   │   └── server_test.go
│   └── persistence/     # Phase 6: AOF log & replay engine
│       ├── aof.go
│       └── aof_test.go
├── go.mod
└── README.md