Home/Projects/Distributed Cache
Prototype
Systems ProgrammingDistributed SystemsInfrastructure

Distributed Cache

Most engineers use Redis without understanding what makes it hard to build correctly: concurrent access requires careful lock discipline, TTL expiration needs a background worker that doesn't block reads, and LRU eviction requires an O(1) structure that survives concurrent writes. This project implements all of this from scratch — TCP server, RESP-compatible protocol, 256-shard mutex concurrency, O(1) LRU via doubly-linked list + hashmap, write-ahead log persistence, and a background TTL expiry worker. The point isn't to replace Redis; it's to understand exactly how it works.

recruiter perspective

Built a Redis-equivalent distributed cache from scratch in C++

  • ›TCP server, RESP protocol, LRU eviction, TTL expiration, WAL persistence — all from scratch
  • ›Thread-safe concurrent access with 256-shard mutex design — no global lock
  • ›12 RESP-compatible commands, epoll event loop, configurable thread pool
Read case study
Hiring Summary

A Redis-inspired distributed key-value store built from scratch in C++. Implements TCP server with RESP protocol, 256-shard mutex concurrency, O(1) LRU eviction (doubly-linked list + hashmap), lazy TTL expiry with background worker, and write-ahead log persistence. A serious study in how distributed caching actually works at the implementation level — every design decision is explicit.

Each claim is paired with evidence that a recruiter can request or verify.

“Thread-safe concurrent access is achieved without a global lock: 256-shard mutex sharding provides O(1) access with contention bounded to ~0.4% of keys per shard under uniform key distribution.”
repoC++ Implementation● on request✓
engineer
“LRU eviction runs in O(1) amortized time using a doubly-linked list + hashmap — maintaining eviction order without array shifts or heap operations.”
repoC++ Implementation● on request✓
engineer

Metrics marked with context indicate the measurement scope (local benchmark, prototype, qualitative estimate, etc.).

256
shards
Mutex Shards
Per-key assignment: hash(key) % 256 — ~0.4% of keys per shard, near-linear contention scaling
O(1)
amortized
LRU Complexity
Doubly-linked list + hashmap — O(1) get, put, and eviction without heap or array operations
12
implemented
RESP Commands
GET, SET, DEL, EXPIRE, TTL, EXISTS, KEYS, FLUSHALL, INCR, DECR, LPUSH, LPOP

Understanding distributed caching at the implementation level — not just the API level. Most engineers know how to use Redis but not how LRU eviction, TTL expiration, and concurrent access actually work together. This project builds it from scratch in C++ to close that gap: every design decision is made explicitly rather than inherited from a library.

Challenges Addressed
  • No external cache libraries — implement all data structures from scratch
  • Thread-safe concurrent access without a global lock (global locking serializes all requests)
  • LRU eviction must be O(1) — not O(log n) with a heap, not O(n) with an array
  • TTL expiration must not block read/write operations — background worker with lazy expiry on access
◆Distributed CacheSYSTEMS PROGRAMMING/visual-placeholder

TCP server accepts connections on a configurable port, parses RESP commands from the wire, and dispatches to the cache layer. Cache: 256 shards, each with its own mutex and LRU doubly-linked list + unordered_map. Key assignment: hash(key) % 256. LRU: doubly-linked list (head = most recently used, tail = eviction candidate) + hashmap(key → list_node). O(1) get: lookup in map, move node to head. O(1) set: create node at head, evict tail if over capacity. TTL: stored per-key as expiry_time; background thread scans expired keys every 100ms; lazy expiry on GET checks timestamp. Persistence: write-ahead log (append-only) + periodic full snapshots. Thread pool: 8 worker threads, queue-based task dispatch.

Stack
C++POSIX ThreadsTCP/IPRedis Protocol (RESP)
Decision
Per-shard mutex locking over global RWLock
A global read-write lock still serializes all writes. Per-shard locking reduces contention to ~0.4% of keys per shard (assuming uniform key distribution), allowing near-linear throughput scaling with thread count.
Decision
Doubly-linked list + hashmap for O(1) LRU
A heap-based LRU is O(log n) for both access and eviction. An array with linear scan is O(n). The doubly-linked list + hashmap achieves O(1) for all three operations: get (move to head), put (insert at head), evict (remove tail).
Decision
Lazy expiry on access + background TTL worker
Eager expiry on every write would require scanning all keys with TTL — O(n) per write in the worst case. Lazy expiry checks the timestamp on GET (O(1)), and a background worker handles bulk expiry sweeps without blocking the request path.
Tradeoff
Lock granularity vs. implementation complexity
Chose: 256-shard mutex
A single global mutex is simple but serializes all operations. Fine-grained per-key locking has high overhead. 256 shards is a practical middle ground: simple to implement, dramatically reduces contention, and scales well for typical workloads.
Tradeoff
Persistence consistency vs. write throughput
Chose: Write-ahead log + periodic full snapshots
Synchronous fsync on every write craters throughput. The WAL allows batched flushes; snapshots allow log truncation. This matches Redis's RDB + AOF approach for the same reason: durability without dominating write latency.
01Cluster mode: consistent hashing across multiple nodes with replication
02Pub/sub: message channel primitives over the existing TCP transport
03Lua scripting: atomic multi-command sequences via EVAL
04Sentinel failover: automatic leader election on node failure