Reading RESP

In the first steps, we discussed how the server receives commands from the client and how the request is structured. Now, let’s explain how to read the RESP and parse it.

How to handle IO

To write the parser, we need to understand the format of the input we will receive in order to parse it. In GoLang, there are several libraries that help us handle IO, but we will use Bufio because it has methods that make it faster to work with data, such as ReadLine and ReadByte.

For example, if we receive data from the client in the form of a RESP string like this:

$5\r\nAhmed\r\n

What we need to do is read the first byte, which is ’$’, to determine the data type we will start reading. Then, we read the number to determine the number of bytes we need to read, which is 5, plus an additional 2 bytes, ‘\r\n’.

‘\r\n’ is called CRLF and it indicates the end of a line.

Let’s see how to do it

We create a string and convert it to a bufio buffer.

input := "$5\r\nAhmed\r\n"

reader := bufio.NewReader(strings.NewReader(input))

Now, to read the name from the RESP string, we need to follow these steps:

Read the data type, which is the first byte in the buffer.
Then, read the number to determine the number of characters we need to read, which is 5, plus an additional 2 bytes, ‘\r\n’.

b, _ := reader.ReadByte()

if b != '$' {
    fmt.Println("Invalid type, expecting bulk strings only")
    os.Exit(1)
}

Next, read the number to determine the number of characters in the string.

size, _ := reader.ReadByte()

strSize, _ := strconv.ParseInt(string(size), 10, 64)

// consume /r/n
reader.ReadByte()
reader.ReadByte()

By doing this, we have read the byte that determines the data type, followed by the number that indicates the number of characters in the string. Then, we read an additional 2 bytes to get rid of the ‘\r\n’ that follows the number.

Now, our reader object is positioned at the 5th byte, which is the letter ‘A’.

$
5
\r
\n
A
h
m
e
d
\r
\n

Since we know the number of characters or bytes we need to read, we just need to create a buffer array and read it.

name := make([]byte, strSize)
reader.Read(name)

fmt.Println(string(name))

This is how we build the parser so that we can handle all RESP commands. The complete code for the above steps is as follows:

package main

import (
    "bufio"
    "fmt"
    "strings"
    "os"
    "strconv"
)

func main() {
    input := "$5\r\nAhmed\r\n"
    reader := bufio.NewReader(strings.NewReader(input))

    b, _ := reader.ReadByte()

    if b != '$' {
      fmt.Println("Invalid type, expecting bulk strings only")
      os.Exit(1)
    }

    size, _ := reader.ReadByte()

    strSize, _ := strconv.ParseInt(string(size), 10, 64)

    // consume /r/n
    reader.ReadByte()
    reader.ReadByte()

    name := make([]byte, strSize)
    reader.Read(name)

    fmt.Println(string(name))
}

Writing RESP

Let’s create a new file called resp.go to contain all the code related to serializing and deserializing on the buffer.

First, to make it easier to work with data types, we define constants that represent each type.

const (
	STRING  = '+'
	ERROR   = '-'
	INTEGER = ':'
	BULK    = '$'
	ARRAY   = '*'
)

Then, we define a struct to use in the serialization and deserialization process, which will hold all the commands and arguments we receive from the client.

type Value struct {
	typ   string
	str   string
	num   int
	bulk  string
	array []Value
}

Note:

typ is used to determine the data type carried by the value.
str holds the value of the string received from the simple strings.
num holds the value of the integer received from the integers.
bulk is used to store the string received from the bulk strings.
array holds all the values received from the arrays.

Now that we have the Value struct, which makes it easier to parse/deserialize RESP commands, let’s create the Reader to contain all the methods that will help us read from the buffer and store it in the Value struct.

The Reader

type Resp struct {
	reader *bufio.Reader
}

func NewResp(rd io.Reader) *Resp {
	return &Resp{reader: bufio.NewReader(rd)}
}

We will use NewResp later on to pass the buffer from the Connection we created in Part 1.

At this stage, we will create two functions that are essential for the parsing process:

readLine reads the line from the buffer.
readInteger reads the integer from the buffer.

We need to implement these functions ourselves because bufio does not provide methods to do so.

ReadLine

func (r *Resp) readLine() (line []byte, n int, err error) {
	for {
		b, err := r.reader.ReadByte()
		if err != nil {
			return nil, 0, err
		}
		n += 1
		line = append(line, b)
		if len(line) >= 2 && line[len(line)-2] == '\r' {
			break
		}
	}
	return line[:len(line)-2], n, nil
}

In this function, we read one byte at a time until we reach ‘\r’, which indicates the end of the line. Then, we return the line without the last 2 bytes, which are ‘\r\n’, and the number of bytes in the line.

ReadInteger

func (r *Resp) readInteger() (x int, n int, err error) {
	line, n, err := r.readLine()
	if err != nil {
		return 0, 0, err
	}
	i64, err := strconv.ParseInt(string(line), 10, 64)
	if err != nil {
		return 0, n, err
	}
	return int(i64), n, nil
}

The Parsing or Deserialization Process

We have created the structs and methods that make it easier to read from the buffer. Now, let’s create the methods that will read from the buffer recursively. We need to read the Value again for each step of the input we receive, so that we can parse it according to the character at the beginning of the line.

func (r *Resp) Read() (Value, error) {
	_type, err := r.reader.ReadByte()

	if err != nil {
		return Value{}, err
	}

	switch _type {
	case ARRAY:
		return r.readArray()
	case BULK:
		return r.readBulk()
	default:
		fmt.Printf("Unknown type: %v", string(_type))
		return Value{}, nil
	}
}

As we did in the first step, we read the first byte to determine the RESP type we will parse. Then, we use a switch statement to parse it according to the type.

For now, we will only handle Array and Bulk.

Now, let’s implement ReadArray because it is the first command we receive from the clients.

Before we write the method, remember that the RESP array looks like this:

*2\r\n$5\r\nhello\r\n$5\r\nworld\r\n

To make it easier to understand, we can split it into lines instead of using ‘\r\n’:

*2
$5
hello
$5
world

To read the Array, we follow these steps:

Skip the first byte because we have already read it in the Read method.
Read the integer that represents the number of elements in the array.
Iterate over the array and for each line, call the Read method to parse the type according to the character at the beginning of the line.
With each iteration, append the parsed value to the array in the Value object and return it.

func (r *Resp) readArray() (Value, error) {
	v := Value{}
	v.typ = "array"

	// read length of array
	length, _, err := r.readInteger()
	if err != nil {
		return v, err
	}

	// foreach line, parse and read the value
	v.array = make([]Value, length)
	for i := 0; i < length; i++ {
		val, err := r.Read()
		if err != nil {
			return v, err
		}

		// add parsed value to array
		v.array[i] = val
	}

	return v, nil
}

Now that the code is complete and the parser is working, we need to implement the Bulk type so that readArray knows how to return the value.

We have already covered bulk strings, but let’s quickly review their format:

$5\r\nhello\r\n

$5
hello

To read the Bulk, we follow these steps:

Skip the first byte because we have already read it in the Read method.
Read the integer that represents the number of bytes in the bulk string.
Read the bulk string, followed by the ‘\r\n’ that indicates the end of the bulk string.
Return the Value object.

func (r *Resp) readBulk() (Value, error) {
	v := Value{}

	v.typ = "bulk"

	len, _, err := r.readInteger()
	if err != nil {
		return v, err
	}

	bulk := make([]byte, len)

	r.reader.Read(bulk)

	v.bulk = string(bulk)

	// Read the trailing CRLF
	r.readLine()

	return v, nil
}

Note that we call r.readLine() after reading the string to read the ‘\r\n’ that follows each bulk string. If we don’t do this, the pointer will be left at ‘\r’ and the Read method won’t be able to read the next bulk string correctly.

Now, the RESP.go file contains everything we need to parse and deserialize RESP.

package main

import (
	"bufio"
	"fmt"
	"io"
	"strconv"
)

const (
	STRING  = '+'
	ERROR   = '-'
	INTEGER = ':'
	BULK    = '$'
	ARRAY   = '*'
)

type Value struct {
	typ   string
	str   string
	num   int
	bulk  string
	array []Value
}

type Resp struct {
	reader *bufio.Reader
}

func NewResp(rd io.Reader) *Resp {
	return &Resp{reader: bufio.NewReader(rd)}
}

func (r *Resp) readLine() (line []byte, n int, err error) {
	for {
		b, err := r.reader.ReadByte()
		if err != nil {
			return nil, 0, err
		}
		n += 1
		line = append(line, b)
		if len(line) >= 2 && line[len(line)-2] == '\r' {
			break
		}
	}
	return line[:len(line)-2], n, nil
}

func (r *Resp) readInteger() (x int, n int, err error) {
	line, n, err := r.readLine()
	if err != nil {
		return 0, 0, err
	}
	i64, err := strconv.ParseInt(string(line), 10, 64)
	if err != nil {
		return 0, n, err
	}
	return int(i64), n, nil
}

func (r *Resp) Read() (Value, error) {
	_type, err := r.reader.ReadByte()

	if err != nil {
		return Value{}, err
	}

	switch _type {
	case ARRAY:
		return r.readArray()
	case BULK:
		return r.readBulk()
	default:
		fmt.Printf("Unknown type: %v", string(_type))
		return Value{}, nil
	}
}

func (r *Resp) readArray() (Value, error) {
	v := Value{}
	v.typ = "array"

	// read length of array
	len, _, err := r.readInteger()
	if err != nil {
		return v, err
	}

	// foreach line, parse and read the value
	v.array = make([]Value, 0)
	for i := 0; i < len; i++ {
		val, err := r.Read()
		if err != nil {
			return v, err
		}

		// append parsed value to array
		v.array = append(v.array, val)
	}

	return v, nil
}

func (r *Resp) readBulk() (Value, error) {
	v := Value{}

	v.typ = "bulk"

	len, _, err := r.readInteger()
	if err != nil {
		return v, err
	}

	bulk := make([]byte, len)

	r.reader.Read(bulk)

	v.bulk = string(bulk)

	// Read the trailing CRLF
	r.readLine()

	return v, nil
}

Conclusion

Now we have deserialized RESP using the Reader, and we can modify main.go to read the commands.

package main

import (
	"fmt"
	"net"
)

func main() {
	fmt.Println("Listening on port :6379")

	// Create a new server
	l, err := net.Listen("tcp", ":6379")
	if err != nil {
		fmt.Println(err)
		return
	}

	// Listen for connections
	conn, err := l.Accept()
	if err != nil {
		fmt.Println(err)
		return
	}

	defer conn.Close()

	for {
		resp := NewResp(conn)
		value, err := resp.Read()
		if err != nil {
			fmt.Println(err)
			return
		}

		fmt.Println(value)

		// ignore request and send back a PONG
		conn.Write([]byte("+OK\r\n"))
	}
}

If we try to connect using redis-cli, we will see the following output:

cli output

Ignore the second line because when redis-cli connects, it sends COMMAND DOCS, which we are currently ignoring.

But if you look at the third line, you will see that the printed Value contains the same number of strings as we sent from redis-cli on the right side.

In the next part, we will serialize the Value response on the Writer and respond to the client with it. After that, we will be able to implement any Redis command.