Services

Resources

Company

Our Work

📙

Key Value DB (Redis) exercise

Problem statement

Write an in-memory key-value DB. Think of your program as v0.1 of Redis.

The program will accept DB commands as inputs from the command line and process them by creating DB structures in memory. The output will be displayed on the standard output stream. The implementation for the commands should be as close to the actual Redis command behavior as possible.

The available commands are case-insensitive and can be entered in the following format:

COMMAND [argument1] [argument2] ...

Replace the COMMAND with one of the supported commands and provide the necessary arguments.

Prerequisite: Basic knowledge of Redis and Redis commands.

Overview of Redis commands

  1. SET: Used to set a key-value pair in Redis. It assigns a value to a specified key, overwriting the existing value if it already exists. If the value contains spaces, it should be enclosed in quotes for proper parsing and assignment.

    1. Example:


$ SET name John
> OK

$ SET name "Foo Bar"
> OK

$ SET surname foo bar // value should be enclosed in quotes
> (error) ERR syntax error

GET: Used to retrieve the value associated with a specific key in Redis. It returns the value stored at the given key. If the key does not exist it prints the error on the terminal. Example:

$ GET name
> "foo"

$ GET surname //since surname does not exist          
> (nil

DEL: Used to delete a key and its associated value from Redis. If the key is found and deleted successfully, then it prints 1. If the key does not exist, it prints 0 on the terminal.

  1. Example:

$ SET name foo
> OK

$ DEL name
> (integer) 1  
        
$ DEL surname // since the surname does not exist
> (integer) 0

INCR: Used to increment the value stored at a key by 1. If the key does not exist, it is set to 1. INCR operation can only be performed on integer values.

  1. Example:

$ SET counter 0
> OK

$ INCR counter    
> (integer) 1

$ GET counter     
> "1"

$ SET age 10.5
> OK

$ INCR age
> (error) ERR value is not an integer or out of range

INCRBY: INCRBY command is similar to INCR but allows you to increment the value stored at a key by a specified integer value instead of just 1. If the key does not exist, then it set the key to the provided value. INCRBY operation can only be performed on integer values.

  1. Example:

$ INCRBY counter 10 
> (integer) 10

$ INCRBY counter 
> (error) ERR wrong number of arguments for 'incrby' command

$ SET age 10.5
> OK

$ INCRBY age 1
> (error) ERR value is not an integer or out of range

MULTI: Used to start a transactional block in Redis. It marks the beginning of a transaction, where multiple commands can be executed as a single atomic operation.

  1. EXEC: Used to execute all the commands that were queued during a transactional block started by MULTI. It executes all the commands atomically, meaning they either all succeed or all fail. If any one of the operations in the transaction fails, then it prints the error on the terminal.

  1. DISCARD: Used to discard the queued commands in a transactional block without executing them. It cancels the transaction and removes all the commands from the queue.

    1. Examples of MULTI and EXEC:

$ MULTI
> OK

$ INCR foo        
> QUEUED

$ SET bar 1 
> QUEUED

$ EXEC
> 1) (integer) 1
	2) OK

Examples of MULTI and DISCARD:

$ MULTI           
> OK

$ INCR foo        
> QUEUED

$ SET bar 1 
> QUEUED

$ DISCARD   
> OK

$ GET key1  
> (nil

If a command does not exist, then it should print the error:

$ foobar
> (error) ERR unknown command

We have divided the problem statement into multiple stories. You’re supposed to implement the stories.

Story 1 (set, get, and delete commands)

Implement the following commands: SET, GET and DELETE

$ SET name foo
> OK

$ SET surname "foo bar"
> OK

$ GET name
> "foo"

$ DEL surname
> (integer) 1  

$ GET surname           
> (nil)

$ SET surname bar 
> OK

Expectations:

  1. Using the SET command, the user should be able to set the value of a key to a given value. If the value contains spaces, it should be enclosed in quotes for proper parsing and assignment.

  1. Using the GET command, the user should be able to retrieve the value of a given key. If the key does not exist, it prints the error on the terminal.

  1. Using DEL command, the user should be able to delete a given key-value pair based on the key. If the key is found and deleted successfully, then it prints 1. If the key does not exist, it prints 0 on the terminal.

  1. If a key is deleted and the user performs a GET operation on that key, the output should be nil.

Story 2 (incr and incrby commands)

Implement Basic Numeric Operations (INCR, INCRBY) with Error Handling

$ SET counter 0
> OK

$ INCR counter    
> (integer) 1

$ GET counter     
> "1"

$ INCRBY counter 10 
> (integer) 11

$ INCR foo          
> (integer) 1

$ INCRBY bar 21    
> (integer) 21

Expectations:

  1. The INCR and INCRBY command should print an error on the terminal if the key is incremented value is not an integer. It is essential to ensure that the incremented value is always an integer.

Story 3 (multi, exec, and discard commands)

Implement the following commands: MULTI, EXEC, and DISCARD

Example 1: EXEC

$ MULTI
> OK

$ INCR foo        
> QUEUED

$ SET bar 1 
> QUEUED

$ EXEC
> 1) (integer) 1
	2) OK

Example 2: DISCARD

$ MULTI           
> OK

$ INCR foo        
> QUEUED

$ SET bar 1 
> QUEUED

$ DISCARD   
> OK

$ GET key1  
> (nil

Expectations:

  1. The commands inside MULTI will be queued for atomic execution using EXEC, i.e., all the queued commands will only be executed after the EXEC command.

  1. If DISCARD is used, all the queued commands should be flushed, and the queue should be emptied without executing.

Story 4 (compact command)

Implement a COMPACT command that outputs the current state of the data store. This is a custom command that the actual Redis server doesn’t implement.

Example 1:

$ SET counter 10
> OK

$ INCR counter
> OK

$ INCR counter
> OK

$ SET foo bar
> OK

$ GET counter    
> "12"

$ INCR counter
> "13"

$ COMPACT        
> SET counter 13
  SET foo bar

Example 2:

$ INCR counter      
> OK 

$ INCRBY counter 10 
> OK

$ GET counter       
> "11"

$ DEL counter      
> (integer) 1

$ COMPACT           
> (nil

Expectations:

  1. Club the commands together when incrementing the same key multiple times.

Story 5 (expose the server via tcp)

Expose the program via TCP and allow the separate clients (e.g., nc or telnet) to connect to it.

  • Update the program to expose our Redis-server via a TCP server on a specific port (e.g., 9736).

  • Read the port number from .env file.

  • Connect to our Redis-server running on a specified port via telnet or nc.

  • Optionally, implement an additional command, DISCONNECT, in the client program to close the TCP connection and exit. Alternatively, the client can also disconnect by issuing a Ctrl+C signal.

  • Connect to our Redis-server using the commands: nc localhost <specified-port> or telnet localhost <specified-port> Example: nc localhost 9736 or telnet localhost 9736

  • The client should be able to send any of the above commands (up to Story 4) over TCP to the server and receive the output in the TCP response.

Story 6 (allow multiple client connections)

Allow multiple clients to connect to our Redis-server.

  • In this story, make sure our Redis-server works well with multiple clients simultaneously i.e., in multiple terminal windows, we can connect to our Redis-server via telnet or nc and send commands to the terminal.

  • Both clients should have the same storage i.e., say we have two clients, client 1 and client 2, if we execute a command SET name John using the 1st client, we should be able to perform GET operation on that key using the 2nd client.

Explanation:

We SET the name to “John” using the 1st client, and when we execute GET name using the 2nd client it returns the result as “John”.

  • When using MULTI command, both the clients should work independently, i.e., if we use MULTI command using the 1st client, and try to execute any command in the 2nd client, then the 2nd client should not queue the command.

Explanation:

1st client uses the MULTI command, and SET command is queued, but the INCR command in 2nd client is not queued, instead, it gets executed immediately.

Story 7 (select command)

Allow the program to connect to different databases. Working should be similar to the SELECT command in Redis.

  • There are logical databases in Redis which are a form of namespacing.

  • Redis instance supports 16 logical databases by default. These databases are effectively siloed off from one another. When you run a command in one database, it doesn’t affect any of the data stored in other databases in your Redis instance.

  • The 16 logical databases are indexed 0-15

$ SELECT 1
> OK 

$ SELECT 500 
> (error) ERR DB index is out of range

$ SELECT -1
> (error) ERR DB index is out of range

$ SELECT one
> (error) ERR value is not an integer or out of range

Implement a SELECT command to select a particular database index.

For example:

Explanation:

When 1st database is selected in client 1 and SET name John is executed, the key name should be set to John only for the 1st database. When we execute GET name on the 2nd database in client 2, it should return (nil), as shown in the figure above.

  • When we have multiple clients connected to multiple databases, for e.g., two clients connected to database 1 and two clients connected to database 2, the storage should only be shared across clients of the same database.

    • For example:

Explanation:

We execute SET name John on the 1st client of database 1 and then execute GET name on the 2nd client of database 2, it should return John. Similar behaviour should be shown for database 2.

NOTE:

The default number of databases in Redis is 16, indexed 0-15. But this number can be increased. To read more about it, follow this link. But for our implementation, we can consider the default number of databases, i.e., 16.

Instructions

  1. Define the structure of the key-value DB:

    1. Decide on the data structure to use for storing key-value pairs in memory. Depending on your preference and requirements, you can choose a map, slice, or custom data structure.

  1. Implement a TCP server:

    1. Accept and handle multiple client connections concurrently using goroutines.

    2. Set up the server to listen on a specific port provided as a command-line argument or a configuration file.

  1. Handle client connections:

    1. For each client connection, create a separate goroutine to handle the communication with that client.

    2. Read commands sent by the client from the TCP connection.

    3. Parse and execute the commands by extracting the operation, key, and value.

    4. Write the output of the command back to the client.

  1. Error handling and validation:

    1. Handle errors during command processing, such as invalid commands, missing keys, or other exceptional cases.

    2. Validate inputs to ensure they meet the expected format or requirements.

    3. Handle network-related errors such as connection interruptions or client disconnections gracefully.

    4. Ensure the error handling in your program is the same as that of Redis. E.g., Redis returns this error ERR wrong number of arguments for 'set' command when a wrong number of arguments are passed to the SET command. Your program should implement the same validation logic and error message as that of Redis.

  1. Graceful shutdown:

    1. Implement a mechanism to gracefully shut down the TCP server when the client disconnects or issues a Ctrl + C signal.

    2. Handle interrupt signals (e.g., Ctrl+C) on the server side to initiate a clean shutdown of the server and close all client connections.

  1. Follow Test-Driven-Development

    1. Write test cases before you implement the code. If not possible, write tests after the code is written.

  1. Update the README

    1. Write README describing the Assumptions/Technical decisions/Future TODOs/Known issues of your implementation.

    2. If there is a doubt, make reasonable assumptions and document them in the README.

Key Value DB (Redis) in Go

Key Value DB (Redis) in Go

Key Value DB (Redis) in Go