rgoussu.dev
rgoussu@goussu: ~/library/system-design/exercises
❯ ~/library/system-design/exercises cat build-your-own-redis-subject.md

Build your own Redis — subject

# The full work statement for the Redis build — RESP2 wire format, command set, expiry and eviction semantics, concurrency decision, and benchmark protocol, self-contained enough to build offline.

Subjectsaved 2026-08-08source #exercise#redis#caching#concurrency#networking#performance#subject

Brief

You are handed a fleet of services that all want the same thing: a fast, shared, in-memory key-value store with TTLs, reachable over TCP by the standard Redis client libraries already in use. Real Redis is off the table — you are building the server yourself. Anything that speaks RESP must be able to connect to your port and get correct answers, under many simultaneous clients, inside a fixed memory budget.

Instructions

1. The wire protocol (RESP2)

Implement the Redis serialization protocol, version 2, as a standalone encode/decode library with its own unit tests — no sockets involved yet. Every frame ends in \r\n (CRLF); the first byte selects the type:

First byte Type Framing
+ Simple string +OK\r\n — the text up to CRLF; may not contain CR or LF.
- Error -ERR unknown command\r\n — same framing as simple strings; the first word is conventionally an error code.
: Integer :1000\r\n — signed base-10 integer as ASCII text.
$ Bulk string $5\r\nhello\r\n — byte length, CRLF, then exactly that many raw bytes (binary-safe, may contain CRLF), then a trailing CRLF. $0\r\n\r\n is the empty string. $-1\r\n is the null bulk string (how GET reports a missing key).
* Array *2\r\n$4\r\nECHO\r\n$3\r\nhey\r\n — element count, CRLF, then that many complete frames of any type, nested arrays allowed. *0\r\n is empty; *-1\r\n is the null array.

Clients send every command as an array of bulk strings (command name first, then arguments); your server replies with whichever type the command calls for. The parser must handle a frame split across multiple TCP reads and two commands arriving in one read — buffer until a complete frame is available.

2. The server and command set

Serve TCP on a configurable port (default 6379). Command names are case-insensitive. Support:

  • PING → +PONG; PING <msg> → the message as a bulk string.
  • ECHO <msg> → the message as a bulk string.
  • SET <key> <value> → +OK. Options: EX <seconds> / PX <milliseconds> attach a time-to-live; a plain SET on a key with a TTL clears that TTL.
  • GET <key> → the value as a bulk string, or null bulk string if absent or expired.
  • DEL <key> [key …] → integer count of keys actually removed.
  • EXISTS <key> [key …] → integer count of keys present.
  • EXPIRE <key> <seconds> → :1 if the TTL was set, :0 if the key doesn't exist.
  • TTL <key> → remaining seconds; :-1 for a key with no TTL, :-2 for a missing key.
  • INCR <key> / DECR <key> → the new value as an integer; a missing key starts at 0; a value that isn't a valid integer returns an error, not a crash.

Unknown commands and wrong arity return -ERR … replies; a protocol error may close the connection, a command error never does.

3. Concurrency model — a decision, not a default

Before milestone 3, choose and write down (in the project README) one of:

  • Event loop — single thread, non-blocking sockets, readiness-based multiplexing (epoll/kqueue or your runtime's async layer). No locks; the store is touched by one thread only.
  • Thread-per-connection over a locked store — blocking I/O per client, shared dictionary guarded by a lock (or sharded locks).

The write-up must state what each model costs (context switches and lock contention vs. single-core ceiling and head-of-line blocking) and why the chosen one fits this project. Whichever you choose, INCR from N parallel clients must be atomic: N clients × M increments always ends at exactly N×M.

4. Expiry semantics

Two mechanisms, both required:

  • Lazy — every read path (GET, EXISTS, TTL, INCR, …) checks the key's deadline first; an expired key is deleted on the spot and treated as absent.
  • Active — a periodic sweep (e.g. 10×/second) samples a bounded batch of keys that carry TTLs (Redis uses 20), deletes the expired ones, and immediately repeats while more than 25% of the sample was expired. This bounds memory held by dead keys that are never read again, without ever scanning the whole keyspace in one pass.

Store deadlines as absolute monotonic-clock instants, not remaining durations.

5. Eviction under maxmemory

Accept a maxmemory <bytes> configuration. When a write would push tracked memory past the cap, evict keys until it fits, using approximate LRU: keep a last-access clock on every entry, sample K random entries (K = 5 is fine), evict the least recently used of the sample, repeat as needed. Exact LRU (a global linked list) is explicitly not required — match Redis's trade: O(1) bookkeeping, statistically near-LRU outcomes. If eviction cannot free enough space, answer writes with an -OOM error rather than crashing.

6. Benchmark protocol

Measure with the stock tool: redis-benchmark -t SET,GET -n 100000 -c 50 against your port (add -P 16 for a pipelined run). Record throughput and latency, capture a CPU profile or flame graph under that load, fix the single largest cost you find, and re-run the identical command. The deliverable is a before/after table plus one paragraph naming the bottleneck and the fix. No harness of your own is needed unless redis-benchmark is unavailable — in which case: 50 concurrent connections each issuing 2 000 alternating SET/GET on random keys from a 10 000-key space, wall-clock timed, p50/p99 reported.

Examples

A SET/GET exchange on the wire:

client → *3\r\n$3\r\nSET\r\n$5\r\nhello\r\n$5\r\nworld\r\n
server → +OK\r\n
client → *2\r\n$3\r\nGET\r\n$5\r\nhello\r\n
server → $5\r\nworld\r\n
client → *2\r\n$3\r\nGET\r\n$7\r\nmissing\r\n
server → $-1\r\n

SET with a 100 ms TTL, read before and after expiry:

SET k v PX 100   → +OK
GET k            → $1\r\nv\r\n        (immediately)
GET k            → $-1\r\n            (after 100 ms)
TTL k            → :-2\r\n            (key is gone)

Constraints

  • Standard library only for networking and data structures; no Redis client/server libraries, no protocol parsers. (A test dependency to drive redis-cli is fine.)
  • Values are binary-safe byte strings; never assume UTF-8.
  • The store lives in memory; persistence is a stretch goal, not part of the subject.
  • Correctness under concurrency beats raw speed everywhere except milestone 6, where you must report honest numbers on an idle machine and name the measurement conditions.

Acceptance

Mapped one-to-one onto the exercise's milestones:

  1. RESP parser — a unit-test suite covers all five types, null bulk string and null array, nested arrays, a frame split across two reads, and two frames in one read; a round-trip (decode → encode) reproduces every test vector byte-for-byte.
  2. PING/ECHO server — a stock redis-cli -p <port> PING prints PONG and redis-cli ECHO hey prints hey, with no client-side flags or patches.
  3. Concurrent clients — the README states the chosen model and its trade-offs; 10 parallel redis-cli loops each running INCR counter 1 000 times leave counter at exactly 10000.
  4. GET/SET with expiry — SET k v EX 1 reads back v immediately and null after 1 s; with active sweep enabled, a batch of 10 000 keys set with PX 100 and never read again measurably shrinks the store within a few seconds.
  5. Eviction — with maxmemory set below the working set, writing past the cap evicts instead of failing; a hot key touched between every insertion survives while cold keys go; memory stays under the cap for the whole run.
  6. Benchmark & profile — a before/after table from the same redis-benchmark command, the profile artifact (flame graph or equivalent), and a paragraph naming the fixed bottleneck.

Related