RESP Codec

Track: Protocols and sockets. 6 stages. Languages: Go, Python, JavaScript, Rust.

Redis and its clients talk to each other in a simple format called RESP. Your job is to read RESP messages out of a stream of bytes, and to turn values back into RESP bytes too. The hard part: bytes can arrive broken up in any way, mid message or several messages at once, so your code must remember what it has already seen and pick up right where it left off. Implement New(), Feed(chunk) -> ([]frame, error code), Encode(value) -> bytes, and Reset() using your language's names. Feed is called once for every new chunk of bytes. Reset throws everything away and starts clean. Every message ends with a carriage return and a newline, two bytes written as \r\n. We write \r\n out visibly on this page so you can see exactly where it goes, instead of a real line break. Build the byte-reading state machine and the encoder yourself. No Redis client library, no ready-made RESP parser. For help with the ideas, read the notes.

Where it is used

• Every Redis client library, in every language, speaks RESP to the Redis server. Commands go out as arrays of bulk strings.
• Valkey and Dragonfly, two other in-memory databases, speak the same protocol, so existing Redis clients work with them unchanged.

A decoder that expects one network read to hold exactly one message works on a quiet test machine and breaks under real load, when TCP splits or joins messages.

Stages

rc1: hello (very easy)

A message starts with one letter that says its kind, then its content, then \r\n. Five kinds, one at a time:

• A simple string: +OK\r\n -> "OK"
• An error message: -ERR bad\r\n -> "bad" (an error is just text, like a simple string, with a different starting letter)
• A whole number: :42\r\n -> 42. Negative numbers work too: :-5\r\n -> -5
• A bulk string, its own length written first: $5\r\nhello\r\n -> "hello"
• An array of other messages: *3\r\n:1\r\n:2\r\n:3\r\n -> [1, 2, 3]

Encode does the reverse: give it a value, get back those exact bytes.

The tester will verify: Feed returns the right value for one message of each kind above, and Encode turns each value back into the exact same bytes.

rc2: messages that arrive in pieces (easy)

Bytes can arrive broken up anywhere, even in the middle of a message. When a message is not finished yet, wait quietly for more bytes instead of guessing. When more than one message arrives in the same chunk, return all of them together, not one at a time. Example: Feed("+OK\r") -> nothing yet. Then Feed("\n") -> "OK" (now it is finished). Example: Feed(":1\r\n:2\r\n:3\r\n") -> 1, 2, 3, all three in that one call.

The tester will verify: a message split across two or more Feed calls still comes out whole and correct once it finishes, and every message that finishes within one call comes out in that same call.

rc3: empty, missing, and bytes of any kind (medium)

A bulk string's length tells you exactly how many bytes belong to it. Count bytes to find where it ends, never search for \r\n, because its bytes can be anything at all, even bytes that look like \r\n. An empty bulk string and a missing one are different things:

• $0\r\n\r\n -> "" (found, just empty)
• $-1\r\n -> missing (not the same as empty, and not an error either)

An array can hold other arrays too: 2\r\n1\r\n:9\r\n:5\r\n -> [[9], 5].

The tester will verify: a bulk string's declared length decides where it ends, even when its bytes contain \r\n or a zero byte. An empty bulk string and a missing one stay different. Arrays inside arrays decode correctly.

rc4: wrong messages, and how deep arrays can go (medium-hard)

Some bytes are not valid RESP. When that happens, Feed must return one of these words instead of a value:

• bad_type_byte: the first byte is not one of the five known kinds.
• bad_integer: a whole number's text is not clean (extra letters after the digits, no digits at all, a leading zero like 007, a leading +, a leading space, an underscore, two minus signs, or -0, which is never allowed, only plain 0).
• integer_overflow: the text is a clean whole number, but too big or too small to fit in -9223372036854775808 to 9223372036854775807.
• bad_length: a declared length that is negative (other than -1, which means missing) or over the limit: 536,870,912 bytes for a bulk string, 1,048,576 for an array's item count.
• missing_crlf: a line that should end with \r\n but does not.
• nesting_too_deep: an array nested more than 32 levels deep. Even an empty array at level 33 counts. A missing array (*-1\r\n) never counts toward depth, at any level, since it never opens anything.

When more than one of these could apply to the same bytes, check them in this order: missing_crlf first, then bad_integer, then integer_overflow, then bad_length, then nesting_too_deep. Once Feed returns one of these words, treat the connection as broken for good. Every later Feed call on the same decoder must return that same word again, without reading the new bytes at all. Call Reset to start over clean. One more rule about finishing a line: it finishes as soon as a \n arrives, even if what came right before it was wrong. A lone \r with nothing after it yet just means "wait for one more byte", never an error by itself.

The tester will verify: each kind of wrong input gets exactly the right word above, the order above is followed whenever more than one word could apply, and once broken, a decoder keeps returning the same word on every later Feed call.

rc5: very large numbers, deep arrays, and real-world letters (hard)

Decode the smallest and largest whole numbers that fit, -9223372036854775808 and 9223372036854775807, exactly, with no rounding. When Encode is given text with letters outside plain English, such as accents or emoji, measure its length in bytes, never in letters you can count by eye. Keep decoding correctly even when bytes keep arriving in small, random-sized pieces. Example: the word "café" is 5 bytes, because "é" alone takes 2 bytes. Its bulk string header must say $5, never $4.

The tester will verify: the smallest and largest whole numbers decode exactly, a bulk string's length from Encode is always a byte count, and decoding still works when the input trickles in a few bytes at a time.

rc6: decode speed (L2, hard)

Keep Feed fast even when a lot of messages arrive back to back, split into realistic small chunks. Keep every answer correct too. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct.

Rules

• Build the byte-reading state machine and the encoder yourself. No Redis client library, no ready-made RESP or frame-codec package.
• Keep payloads as raw bytes, not text. A bulk string can hold any bytes at all, not just printable letters.
• Standard library only.

Read the RESP Codec notes in the wiki