Building my own Redis in Go - Part 2

In part 1 of this blog series, we discussed how to create a TCP server in Go and parse the Redis Serialization Protocol (RESP). Please check out that blog here. In this blog, I'm going to discuss how the commands are executed after parsing RESP. We will also go through the implementations of some important commands.

Key-Value Store

We know that Redis is a key-value in-memory database. So, we need to set up a key-value struct to store the data in our database. Here's the structure for it:

type KeyValueStore struct {
    Strings     map[string]string
    Lists       map[string][]string
    Hashes      map[string]map[string]string
    Expirations map[string]time.Time
    mu          sync.RWMutex
}

KeyValueStore is a struct with multiple hash maps where the key for each map is a string, but the type of value depends on the data structure we want to store in the database. For now, I've included Strings, Lists, and Hashes. mu is the mutex used to acquire a lock while reading/writing to this key-value store (Remember, godisDB is multithreaded unlike Redis). Ignore the Expirations map[string]time.Time for now; we will discuss this in the next blog when we explore the EXPIRE and TTL commands.

In the main function, before listening for connections, we will initialize our key-value store.

func main() {
    listener, err := net.Listen("tcp", ":6369")
    if err != nil {
        fmt.Println("error listening")
    }
    kv := &KeyValueStore{
        Strings:     make(map[string]string),
        Lists:       make(map[string][]string),
        Hashes:      make(map[string]map[string]string),
        Expirations: make(map[string]time.Time),
    }
    ...
    go handleConnection(c, kv)

As you can see, kv is passed as an argument to handleConnection function.

Executing Commands

Now that we have a command and the arguments in a struct similar to [{HELLO [world]} , let's write a function to execute the commands

func executeCommand(cmd Command, conn io.ReadWriter, kv *KeyValueStore) string {
    switch cmd.Name {
    case "SET":
        return executeSET(cmd.Args, kv)
    case "GET":
        return executeGET(cmd.Args, kv)
    case "SETNX":
        return executeSETNX(cmd.Args, kv)
    case "MSET":
        return executeMSET(cmd.Args, kv)
....continues

This function is a switch statement that handles commands case by case. I've only included 4 commands, but it is a really long function that supports commands like PING, SET, GET, SETNX, MSET, MGET, INCR, DECR, RPUSH, LPUSH, RPOP, LPOP, LRANGE, DEL, EXPIRE, TTL. Each command is handled separately in its own function. Let's look at some important commands and their functions in this blog.

SET

SET is usually the first command you try when you start using Redis. This command sets the string value of a key. Implementing a function to execute this command is straightforward. Here's the function:

func executeSET(args []string, kv *KeyValueStore) string {
    if len(args) <= 1 {
        return "(error) ERR wrong number of arguments for 'SET' command"
    } else {
        key := args[0]
        value := args[1]
        kv.mu.Lock()
        defer kv.mu.Unlock()
        kv.Strings[key] = value
    }
    return "OK"
}

SET command accepts two arguments: the key and the value. We acquire a lock on the kv store and set the key-value in kv.Strings because the SET command sets the string value of a key. Let's move on to the GET command.

GET

The GET command returns the string value of a key. We simply need to search for the key in kv.Strings and return the value if the key exists. Here's the function:

func executeGET(args []string, kv *KeyValueStore) string {
    if len(args) < 1 {
        return "(error) ERR wrong number of arguments for 'GET' command"
    }
    key := args[0]
    kv.mu.RLock()
    defer kv.mu.RUnlock()
    if checkExpiredStrings(key, kv) {
        return "(nil)"
    }
    if value, exists := kv.Strings[key]; exists {
        return value
    }
    return "Error, key doesn't exist"
}

The GET command accepts only one argument. You can see that at the end of the function, the value is returned if the key exists. kv.mu.RLock() acquires a read lock, allowing multiple goroutines to read (but not write) at the same time. This is different from kv.mu.Lock(), where only one goroutine can read or write after acquiring the lock. The function checkExpiredStrings is called to check if the key has an expiration set. We will explore this more in the next blog.

Commands like MSET, MGET, and SETNX are various versions of the SET and GET commands. You can look at their implementations in the source code.

Let's move on to the INCR command.

INCR

INCR increments the number stored at key by one. This is a string operation because Redis does not have a dedicated integer type. The string stored at the key is treated as a base-10 64-bit signed integer to perform the operation. If the key does not exist, it is set to 0 before the operation. An error is returned if the key contains a value of the wrong type or a string that cannot be represented as an integer. Here's the function:

func executeINCR(args []string, kv *KeyValueStore) string {
    if len(args) > 1 {
        return "(error) ERR wrong number of arguments for 'INCR' command"
    }
    key := args[0]
    kv.mu.Lock()
    defer kv.mu.Unlock()

    if _, exists := kv.Lists[key]; exists {
        return "(error) WRONGTYPE Operation against a key holding the wrong kind of value"
    }

    if _, exists := kv.Hashes[key]; exists {
        return "(error) WRONGTYPE Operation against a key holding the wrong kind of value"
    }

    if _, exists := kv.Strings[key]; !exists || checkExpiredStrings(key, kv) {
        kv.Strings[key] = "1"
        return "(integer) 1"
    } else {
        num, err := strconv.Atoi(kv.Strings[key])
        if err != nil {
            return "(error) ERR value is not an integer"
        }
        num++
        kv.Strings[key] = strconv.Itoa(num)
        return fmt.Sprintf("(integer) %d", num)
    }
}

Here, we first check if the key exists in Lists or Hashmaps and then move to Strings. In kv.Strings, if the key doesn't exist, we assign the key a value of 1 and return 1. Otherwise, we increase the existing value (if it can be converted to an integer).

DECR is a similar command to INCR but for decrement. Now, let's look at storing arrays in our database. Some important commands to store and retrieve arrays are RPUSH, LPUSH, RPOP, LPOP, and LRANGE.

RPUSH

RPUSH inserts all the specified values at the end of the list stored at key. If the key doesn't exist, it creates one. Here's the function for RPUSH:

func executeRPUSH(args []string, kv *KeyValueStore) string {
    if len(args) <= 1 {
        return "(error) ERR wrong number of arguments for 'RPUSH' command"
    } else {
        kv.mu.Lock()
        defer kv.mu.Unlock()
        key := args[0]
        if _, exists := kv.Lists[key]; !exists || checkExpiredLists(key, kv) {
            kv.Lists[key] = make([]string, 0)
        }

        for i := 1; i < len(args); i++ {
            kv.Lists[key] = append(kv.Lists[key], args[i])
        }
    }
    return "OK"
}

RPUSH accepts more than one argument and appends all the provided values to the list and returns "OK".

You can check out other commands like LPUSH, RPOP, and LPOP, which are used to store and retrieve values from arrays.

LRANGE

LRANGE returns the specified elements of the list stored at key. Let's look at the function

func executeLRANGE(args []string, kv *KeyValueStore) string {
    key := args[0]
    kv.mu.Lock()
    defer kv.mu.Unlock()
    if _, exists := kv.Lists[key]; !exists || checkExpiredLists(key, kv) {
        return "Error, key does not exist"
    }

    startIndex, err := strconv.Atoi(args[1])
    if err != nil {
        return "Error, Start Index must be an integer"
    }
    endIndex, err := strconv.Atoi(args[2])
    if err != nil {
        return "Error, End Index must be an integer"
    }

    if startIndex < 0 {
        startIndex = len(kv.Lists[key]) + startIndex
    }
    if endIndex < 0 {
        endIndex = len(kv.Lists[key]) + endIndex
    }
    if startIndex > endIndex || startIndex >= len(kv.Lists[key]) {
        return "empty"
    }
    if endIndex >= len(kv.Lists[key]) {
        endIndex = len(kv.Lists[key]) - 1
    }

    str := strings.Join(kv.Lists[key][startIndex:endIndex+1], " ")
    return str
}

LRANGE accepts the key, startIndex and endIndex as arguments.There are many safety checks in this function to handle indices going out of range. Finally, the desired elements are joined with spaces and returned as a string.

We've only discussed the implementation of some essential commands. Please check out all the implementations in the source code.

Conclusion

In the next blog (part-3), we will look at two important commands, EXPIRE and TTL, and the checkExpiredLists function, which we skipped in this blog. We will also discuss how to write back to the client in RESP. Thanks for reading. Happy coding!