ProjectsRedis Server
A small server that speaks the Redis wire protocol, so the real redis-cli and redis-benchmark can talk to it, and stores strings, counters and lists with optional expiry and a snapshot on disk. Building it teaches how a protocol marks where each message ends on a TCP stream, how one process serves many clients without corrupting shared data, how keys expire cheaply, and how a snapshot survives a restart.
From Coding Challenges #8 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 9 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Step 1 builds the encoder and decoder on their own, tested before any networking exists, and every later step sends and receives these values.
Covers: the first byte names the type · simple strings, errors and integers · length-prefixed bulk strings · null versus empty · arrays and nesting · CRLF as the terminator · lengths count bytes, not characters · complete, incomplete and invalid input
Redis serialization protocol (RESP) specification ↗ · RESP3 specification (redis-specifications) ↗ · Type-length-value (Wikipedia) ↗
Step 2 is the first time bytes come from a real client, and redis-cli and redis-benchmark split and merge commands in ways the unit tests of step 1 never did.
Covers: a stream keeps no message boundaries · partial reads · several commands in one read · a read buffer per connection · pipelining and reply order · partial writes · the client closing the connection
Beej's Guide to Network Programming: Son of Data Encapsulation ↗ · Redis pipelining (Redis docs) ↗ · recv(2), Linux manual page ↗
Step 2 adds the first commands, PING and ECHO, and step 3 adds SET and GET with their own argument rules and error cases.
Covers: the command name and its arguments · case-insensitive names · a table from name to handler · arity checks before running · each command's reply type · error replies versus closing the connection
RESP specification: Simple errors (Redis docs) ↗ · COMMAND: arity and command metadata (Redis docs) ↗
Step 3 leaves the choice of storage to you, and step 7 asks whether your data structure is the right one when your server is slower than Redis.
Covers: hashing a key to a bucket · average constant-time lookups · collisions and the load factor · growing and rehashing · incremental rehashing · keys compared as bytes
Hash table: Dynamic resizing (Wikipedia) ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 3.4 Hash Tables ↗
Step 4 has to survive redis-benchmark's 50 parallel connections, and the page suggests trying both a thread per client and async I/O.
Covers: a thread per connection · an event loop over non-blocking sockets · readiness notification such as epoll and kqueue · shared data and data races · making a whole command atomic · one slow command or client holding up the rest
The C10K problem (Dan Kegel) ↗ · Redis event library (Redis docs) ↗ · Race condition: In software (Wikipedia) ↗
Step 5 adds the four expiry options to SET, tests values before and after they expire, and asks for expiry that stays cheap as the keyspace grows.
Covers: relative and absolute expiry times · one absolute deadline per key · lazy expiry on access · active expiry by random sampling · why not a timer per key · wall-clock versus monotonic time · which writes clear an expiry
EXPIRE: Appendix, Redis expires (Redis docs) ↗ · SET (Redis docs) ↗ · clock_gettime(2), Linux manual page ↗
Step 6 adds counters and lists next to plain strings, so the store has to remember each value's type and every command has to check it.
Covers: one type per key · binary-safe strings · strings that hold integers · the 64-bit range and overflow · lists with cheap pushes at both ends · WRONGTYPE errors · multi-key commands and their counts
Redis data types (Redis docs) ↗ · Redis lists (Redis docs) ↗ · INCR (Redis docs) ↗
Step 6 adds SAVE and loading on start, so the data has to outlive the process and come back with the same keys, types and deadlines.
Covers: a point-in-time snapshot · a consistent view while clients write · a self-describing file with types and lengths · storing absolute deadlines · writing a temporary file, then renaming it · flushing to the disk · loading at start-up and skipping expired keys · what a crash between snapshots loses
Redis persistence: Snapshotting (Redis docs) ↗ · rename(2), Linux manual page ↗ · Files are hard (Dan Luu) ↗
Step 7 compares your server with real Redis using redis-benchmark, and the numbers only mean something if both runs are set up the same way.
Covers: throughput versus latency · closed-loop clients and Little's law · round trips and pipelining · comparing like with like · noise and repeated runs · finding the bottleneck before optimising
Redis benchmark (Redis docs) ↗ · Active Benchmarking (Brendan Gregg) ↗ · Little's law (Wikipedia) ↗
What you'll build · 8 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project for a long-running server that listens on the port given in the PORT environment variable rather than always on 6379, so it can run next to a real Redis and be tested in a sandbox. Install Redis too if you can, for its redis-cli and redis-benchmark tools, which later steps use as clients.
Works whenYour program starts, reads PORT from the environment and keeps running, and redis-cli runs on your machine.
Write a decoder that turns RESP bytes into values and an encoder that turns values back into bytes, for simple strings, errors, integers, bulk strings, arrays and both forms of null. There is no networking yet.
Works whenUnit tests pass for the page's sample messages, among them a null, an empty bulk string, an OK reply, an error, and PING and ECHO sent as arrays: each decodes to the expected value and encodes back to the same bytes. Input cut off partway is reported as incomplete, broken input as invalid, and neither crashes the decoder.
Concepts: RESP
Accept TCP connections on the port from PORT, read commands with the decoder from step 1, answer PING with PONG and ECHO with its argument, and keep each connection open for more commands until the client closes it.
Works whenredis-cli, pointed at your port, gets PONG back for PING and Hello World back for ECHO with that argument, and several commands in one session all get their answers.
Concepts: framing messages on a TCP byte stream · command dispatch and error replies
Add SET with a key and a value, replying OK, and GET, replying with the value or with null for a missing key. Choose the data structure that holds the keys, and answer a wrong number of arguments or an unknown command with an error reply.
Works whenAfter SET Name John, GET Name returns John, and GET on a key that was never set returns nil. A command with missing arguments gets an error and the connection stays usable. Automated tests cover both the normal and the error cases, through a Redis client library if you like.
Concepts: the keyspace as a hash table · command dispatch and error replies
Serve many connections at the same time, with a thread per client or with asynchronous I/O, and keep the shared keyspace correct when clients change it together. Trying both models is worth it if you have time.
Works whenredis-benchmark -t SET,GET -q against your port, with its default 50 connections, finishes with no errors and no crash, using -n 1000 if it runs slowly. Speed doesn't matter yet.
Concepts: serving many clients safely
Extend SET with EX and PX, a lifetime in seconds or milliseconds, and EXAT and PXAT, an absolute Unix time in seconds or milliseconds. An expired key behaves as if it doesn't exist, and expiry stays cheap however many keys there are.
Works whenAutomated tests set keys with each option and find them readable before their deadline and gone after it.
Concepts: key expiry
Add EXISTS and DEL, which take one or more keys, INCR and DECR for counters, LPUSH and RPUSH for lists, and SAVE, which writes the dataset to a file. On start, load that file if it exists. Every command treats an expired key as missing.
Works whenEach command's replies match the examples in the Redis documentation, including the error for a command used on a key of the wrong type. After SAVE, a stop and a restart, the same keys come back with their values, types and deadlines.
Concepts: typed values and type errors · snapshot persistence and loading at start-up
Run redis-benchmark -t set,get -n 100000 -q against a real Redis and then against your server on the same machine. Compare the results and look for what slows yours down, such as the data structure or the way clients share the keyspace.
Works whenYou have results for both servers from the same machine and settings, repeated a few times. Your server answers every request without errors, and you can say where it spends its time.
Concepts: measuring throughput honestly