Context:
The objective of this exercise is to create a simplified version of Redis in C# as a learning project.
We will call it "KVLite"!
While Redis is a complex and feature-rich key-value store, we will focus on implementing a subset of its features to start with.
Some common Redis features KVLite 'could' have.
Basic Key-Value Operations:
- Implement basic operations like
GET,SET,DEL,EXISTS, andTTL(time-to-live) for key-value pairs.
- Implement basic operations like
Expiration and Persistence:
- Implement key expiration using a time-to-live (TTL) mechanism i.e. to automatically remove expired keys
Multiple Client Connection:
- TCP server with the capability to handle multiple clients
The goal of this article is to teach readers to build a Key-Value Store. I will over-simplify the process to build with a step-by-step explanation. The repo below has a fully-functional code.
The KeyValue Data Structure
We will use the Dictionary<TKey,TValue> collection to store the Key and Value pair.
Dictionary is a dynamic collection. The size of a Dictionary can grow or shrink as needed as it uses a hash table to store its elements.
Hash table is a type of data structure that allows for fast lookup and insertion of elements.
For the first iteration of KVLite, the Key will be a String and the Value will be a dynamic Object.
Dictionary<string,object>
For the benefit of all the readers, I will use a simple project structure.
Create 2 projects:
Console App to run the server
ASP Net Core Web API as the client
In the KVLite.Console app, create class KeyValueStore.cs with the following code.
public class KeyValueStore
{
private readonly Dictionary<string, object> keyValuePairs;
public KeyValueStore()
{
keyValuePairs = new Dictionary<string, Object>();
}
public void Set(string key, object value)
{
keyValuePairs[key] = value;
}
public object Get(string key)
{
return keyValuePairs[key];
}
}
Update program.cs in the KVLite.Console app with the below code.
using KVLite.Console;
Console.WriteLine("Starting KVLite");
var kvStore = new KeyValueStore();
kvStore.Set("Test Key", "Test Value");
Console.WriteLine(kvStore.Get("Test Key"));
When you run the console app, you should see the kvStore.Get returning the value for the key "Test Key"
Great! We were able to run 2 simple operations. You can add other operations like Update and Delete to the KeyValueStore class and test the functionality.
TTL (Time-To-Live)
Let's implement TTL to our existing KeyValueStore.cs.
But what is TTL and why do we need it?
In context of a key-Value Store,๐ง๐ถ๐บ๐ฒ ๐๐ผ ๐น๐ถ๐๐ฒ (๐ง๐ง๐) ๐ถ๐ ๐ฎ ๐ณ๐ฒ๐ฎ๐๐๐ฟ๐ฒ ๐ผ๐ณ ๐ฅ๐ฒ๐ฑ๐ถ๐ ๐๐ต๐ฎ๐ ๐ฎ๐น๐น๐ผ๐๐ ๐๐ผ๐ ๐๐ผ ๐๐ฒ๐ ๐ฎ ๐๐ถ๐บ๐ฒ ๐น๐ถ๐บ๐ถ๐ ๐ณ๐ผ๐ฟ ๐ฎ ๐ธ๐ฒ๐.
After the time limit has expired, the key will be automatically deleted.
By default, TTL is -1 for any Redis key which means the key lives forever and this value can be changed while storing the key in DB.
Some use cases:
โ
Caching
โ
Session Management
โ
Rate Limiting
โ
Data Purging
We will implement something simple and similar to our code.
Our algorithm...
Take TTL as input from the client for the SET operation
Create another Dictionary to track Expiration Time. 'Dictionary<string, DateTime>'
In the SET operation add the key to both the keyValue dictionary and the expiration time dictionary
In the Get operation, check if they key exists in expiration time dictionary and check if DateTime value is lesser than Current Time. If lesser, remove the key from both dictionaries.
Update the KeyValueStore.cs with the below code.
public class KeyValueStore
{
private readonly Dictionary<string, object> keyValuePairs;
private readonly Dictionary<string, DateTime> expirationTime;
public KeyValueStore()
{
keyValuePairs = new Dictionary<string, Object>();
expirationTime = new Dictionary<string, DateTime>();
}
public void Set(string key, object value, int ttl)
{
keyValuePairs[key] = value;
expirationTime[key] = DateTime.UtcNow.Add(TimeSpan.FromSeconds(ttl));
}
public object Get(string key)
{
if (expirationTime.ContainsKey(key) && expirationTime[key] < DateTime.UtcNow)
{
keyValuePairs.Remove(key);
expirationTime.Remove(key);
Console.WriteLine($"Removing Key {key} as it has reached expiration");
return null;
}
return keyValuePairs[key];
}
}
Update program.cs with the below code
Console.WriteLine("Starting KVLite");
var kvStore = new KeyValueStore();
kvStore.Set("Test Key", "Test Value", 5);
Console.WriteLine(kvStore.Get("Test Key"));
Thread.Sleep(6000);
Console.WriteLine(kvStore.Get("Test Key"));
On running the app, you should see "Test Value" only once on the console as it was removed after 5 seconds.
However, this is incomplete as in most use cases, we want the Key-Value to be stored forever (until explicitly deleted).
Let's implement that.
We will set the default value of ttl to be -1.
if ttl is -1, then the datetime value stored is DateTime.MaxValue (which is forever), else the given time
public class KeyValueStore
{
private readonly Dictionary<string, object> keyValuePairs;
private readonly Dictionary<string, DateTime> expirationTime;
public KeyValueStore()
{
keyValuePairs = new Dictionary<string, Object>();
expirationTime = new Dictionary<string, DateTime>();
}
public void Set(string key, object value, int ttl = -1)
{
keyValuePairs[key] = value;
var dateTime = (ttl == -1) ? DateTime.MaxValue : DateTime.UtcNow.Add(TimeSpan.FromSeconds(ttl));
expirationTime[key] = dateTime;
}
public object Get(string key)
{
if (expirationTime.ContainsKey(key) && expirationTime[key] < DateTime.UtcNow)
{
keyValuePairs.Remove(key);
expirationTime.Remove(key);
Console.WriteLine($"Removing Key {key} as it has reached expiration");
return null;
}
return keyValuePairs[key];
}
}
This was an oversimplified implementation of the TTL.
A fully-functional version can be as below. Download the repo to run it.
using KVLite.Core.Models;
namespace KVLite.Core.Storage
{
public class KeyValueStore
{
private readonly Dictionary<string, object> keyValuePairs;
private readonly Dictionary<string, DateTime> expirationTimes;
private readonly TimeSpan defaultTtl = TimeSpan.MaxValue;
public KeyValueStore()
{
keyValuePairs = new Dictionary<string, Object>();
expirationTimes = new Dictionary<string, DateTime>();
}
/// <summary>
/// Sets a value in the key-value store with an optional time-to-live (TTL).
/// </summary>
/// <param name="key">The key of the value to set.</param>
/// <param name="value">The value to set.</param>
/// <param name="ttl">The optional time-to-live (TTL) in seconds.</param>
/// <returns>A StatusModel indicating the status of the set operation.</returns>
public StatusModel Set(string key, object value, double ttl = -1)
{
var status = new StatusModel();
try
{
if (string.IsNullOrEmpty(key))
{
status.Status = StatusConst.Error;
status.Message = "Key is null or empty";
return status;
}
if (Exists(key))
{
status.Status = StatusConst.Error;
status.Message = "Key already exists";
return status;
}
var dateTime = (ttl == -1) ? DateTime.MaxValue : DateTime.UtcNow.Add(TimeSpan.FromSeconds(ttl));
keyValuePairs[key] = value;
expirationTimes[key] = dateTime;
}
catch (Exception ex)
{
status.Status = StatusConst.Error;
status.Message = ex.Message;
}
status.Message = "Successfully Stored ";
return status;
}
/// <summary>
/// Retrieves the value associated with the specified key from the key-value store.
/// </summary>
/// <param name="key">The key of the value to retrieve.</param>
/// <returns>A StatusModel indicating the status of the get operation and the retrieved value.</returns>
public StatusModel Get(string key)
{
var status = new StatusModel();
if (string.IsNullOrEmpty(key))
{
status.Status = StatusConst.Error;
status.Message = "Key is null or empty";
return status;
}
if (!Exists(key))
{
status.Status = StatusConst.Error;
status.Message = "Key does not exist";
return status;
}
if (expirationTimes[key] >= DateTime.UtcNow)
{
status.Status = StatusConst.Success;
status.Message = StatusConst.Success;
status.Value = keyValuePairs[key];
return status;
}
// Key has expired, remove it
RemoveExpiredKey(key);
status.Status = StatusConst.Error;
status.Message = "Key does not exist";
return status;
}
/// <summary>
/// Checks if the specified key exists in the key-value store.
/// </summary>
/// <param name="key">The key to check for existence.</param>
/// <returns>True if the key exists, false otherwise.</returns>
public bool Exists(string key)
{
return keyValuePairs.ContainsKey(key) && expirationTimes.ContainsKey(key);
}
/// <summary>
/// Deletes the value associated with the specified key from the key-value store.
/// </summary>
/// <param name="key">The key of the value to delete.</param>
/// <returns>A StatusModel indicating the status of the delete operation.</returns>
public StatusModel Delete(string key)
{
var status = new StatusModel();
if (string.IsNullOrEmpty(key))
{
status.Status = StatusConst.Error;
status.Message = "Key is null or empty";
return status;
}
if (!Exists(key))
{
status.Status = StatusConst.Error;
status.Message = "Key does not exist";
return status;
}
RemoveExpiredKey(key);
if (keyValuePairs.Remove(key))
{
expirationTimes.Remove(key);
}
status.Status = StatusConst.Success;
status.Message = "Key removed successfully";
return status;
}
/// <summary>
/// Updates the value associated with the specified key in the key-value store.
/// </summary>
/// <param name="key">The key of the value to update.</param>
/// <param name="value">The new value to set for the key.</param>
/// <returns>A StatusModel indicating the status of the update operation.</returns>
public StatusModel Update(string key, object value)
{
var status = new StatusModel();
if (string.IsNullOrEmpty(key))
{
status.Status = StatusConst.Error;
status.Message = "Key is null or empty";
return status;
}
if (!Exists(key))
{
status.Status = StatusConst.Error;
status.Message = "Key does not exist";
return status;
}
if (expirationTimes[key] < DateTime.UtcNow)
{
RemoveExpiredKey(key);
status.Status = StatusConst.Error;
status.Message = "Key does not exist";
return status;
}
keyValuePairs[key] = value;
status.Message = "Updated Successfully";
return status;
}
private void RemoveExpiredKey(string key)
{
if (expirationTimes[key] < DateTime.UtcNow)
{
keyValuePairs.Remove(key);
expirationTimes.Remove(key);
}
}
}
}
Building a TCP Server
Our goal is to build an in-memory data store that can connect with multiple clients.
To accomplish this we need a server that is listening for incoming requests on a specific port.
Like all prominent databases (MYSQL, Redis, Mongo, etc.), we will build a TCP-based server.
Create a class called Server.cs in the Console app and add the following snippet.
public class Server
{
private const int Port = 6377;
private readonly TcpListener listener;
private readonly KeyValueStore keyValueStore;
public Server(KeyValueStore keyValueStore)
{
this.keyValueStore = keyValueStore;
listener = new TcpListener(IPAddress.Any, Port);
}
}
The
Serverclass has two private fields:listener: It is an instance of theTcpListenerclass.TcpListeneris a class that provides TCP network services by listening for incoming connections on a specified network port.keyValueStore: It is an instance of theKeyValueStoreclass. TheKeyValueStoreclass is a custom class that is expected to be provided as a parameter in the constructor.
The constructor of the
Serverclass takes an argument of typeKeyValueStoreand assigns it to thekeyValueStorefield. It also initializes thelistenerfield by creating a newTcpListenerinstance that listens on any available network interface (IPAddress.Any) and the specified port number (Port = 6377).
When we run the console app, we want to be able to start the server.
Let's write a method.
public void Start()
{
listener.Start();
Console.WriteLine($"Server started. Listening on port {Port}...");
while (true)
{
var client = listener.AcceptTcpClient();
ClientHandler(client);
}
}
The listener.Start() method starts listening for incoming connection requests on the specified network port.
The while (true) loop ensures that the server keeps running indefinitely. Inside the loop, the server waits for a client to connect by calling listener.AcceptTcpClient(). This method blocks execution until a client connection is made.
When a client connection is accepted, the AcceptTcpClient() method returns a TcpClient object representing the connected client.
The ClientHandler(client) method is called, passing the client object as an argument. This method is responsible for handling the client's requests and performing any necessary processing. Let's write it.
private void ClientHandler(TcpClient client)
{
try
{
var stream = client.GetStream();
var reader = new StreamReader(stream, Encoding.UTF8);
var writer = new StreamWriter(stream, Encoding.UTF8) { AutoFlush = true };
while (client.Connected)
{
try
{
if (!stream.DataAvailable)
break;
var buffer = new byte[1024];
var messageBuilder = new StringBuilder();
while (true)
{
var bytesRead = stream.Read(buffer, 0, buffer.Length);
messageBuilder.Append(Encoding.UTF8.GetString(buffer, 0, bytesRead));
if (stream.DataAvailable)
continue;
// All data has been read, exit the loop
break;
}
var receivedData = Encoding.UTF8.GetBytes(messageBuilder.ToString());
var receivedString = Encoding.UTF8.GetString(receivedData);
Console.WriteLine(receivedString);
var encodedResponse = Encoding.UTF8.GetBytes(receivedString);
stream.Write(encodedResponse, 0, encodedResponse.Length);
}
catch (Exception e)
{
Console.WriteLine(e);
}
}
// Close the client connection
client.Close();
}
catch (Exception e)
{
Console.WriteLine(e);
}
}
The method obtains the network stream (stream) from the client, and creates a StreamReader and StreamWriter to handle reading from and writing to the stream, using UTF-8 encoding.
client.Connected ensures the method runs until the connection is active.
Within the loop, it first checks if there is data available to read from the stream using stream.DataAvailable. If there is no data available, it breaks out of the loop.
If there is data available, the method initializes a byte array buffer and a StringBuilder object messageBuilder to store the received data.
It enters an inner while (true) loop to read the complete message from the stream. It reads data from the stream into the buffer and appends the UTF-8 encoded string representation of the buffer to the messageBuilder. This process continues until all the available data is read.
Update Program.cs
using KVLite;
Console.WriteLine("Starting KVLite");
var kvStore = new KeyValueStore();
var server = new Server(kvStore);
server.Start();
Our simple server is now ready.
Building a Client
The client needs to establish a connection with the server. It needs to make a connection on the IP and port the server is on.
Let's write it.
Create a class Client.cs in the Web API project. Add the following code to it.
public class Client
{
private const int Port = 6397;
private const string Host = "localhost";
private TcpClient client;
private NetworkStream stream;
private StreamWriter writer;
private StreamReader reader;
public Client()
{
Console.WriteLine($"KVLite Client initiated for {Host}:{Port}");
client = new TcpClient(Host, Port);
stream = client.GetStream();
writer = new StreamWriter(stream, Encoding.ASCII) { AutoFlush = true };
reader = new StreamReader(stream, Encoding.ASCII);
}
public string Set(string message)
{
writer.WriteLine(message);
string response = reader.ReadLine();
Console.WriteLine(response);
return response;
}
}
This code snippet represents a simple client implementation that connects to a server and can send a message to the server using the Set method. The client can then receive and display the server's response.
Create a ClientController and use the Client class to send a simple message to the Server.
Run the Web API project and send a message to the Server.
You should get the same message as response.
Congratulations - you have created a simple TCP client and Server.
Serialization Protocol
How will the client understand the operation to be executed on the input i.e. is it a GET or SET operation?
I checked how Redis has solved it under the hood and found it uses a protocol called RESP.
RESP is a compact and efficient protocol that allows Redis to communicate with clients over various network protocols, including TCP/IP and Unix sockets.
I dabbled with it for a bit but realized it would be too complex a task to write a parser on the Server considering the time constraints.
So I created JSON-like objects that will be sent as plain text and deserialized on the server.
For example:
GET: {"Operation": "GET", "key": "key"}
SET: {"Operation": "SET", "key": "key", "value": "value"}
DELETE: {"Operation": "DELETE", "key": "key"}
UPDATE: {"Operation": "UPDATE", "key": "key", "value": "value"}
Update the Client.cs
public string Set(string key, string value, string timeToLive)
{
string command = $"{{\"Operation\": \"SET\", \"key\": \"{key}\", \"value\": \"{value}\",\"ttl\": \"{timeToLive}\"}}";
writer.WriteLine(command);
string response = reader.ReadLine();
Console.WriteLine(response);
return response;
}
On the Server side, we need a parser to deserialize the incoming string.
public class InputParser
{
public enum OperationType
{
GET,
SET,
DELETE,
UPDATE
}
public class Command
{
public string Operation { get; set; }
public string Key { get; set; }
public Object Value { get; set; }
public string Ttl { get; set; }
}
/// <summary>
/// Parses the input string into a Command object.
/// </summary>
/// <param name="input">The input string to parse.</param>
/// <returns>A Command object representing the parsed input.</returns>
public Command Parse(string input)
{
var command = new Command();
try
{
command = JsonConvert.DeserializeObject<Command>(input);
}
catch (Exception e)
{
Console.WriteLine(e);
}
return command;
}
}
You can then use the Parser class to deserialize the input in Server.cs
private StatusModel ProcessRequest(string request)
{
var parser = new InputParser();
var command = parser.Parse(request);
if (command.Operation == "SET")
{
double ttl = -1;
if(!double.TryParse(command.Ttl, out ttl)) ttl= -1;
return this.keyValueStore.Set(command.Key, command.Value.ToString(), ttl);
}
else if (command.Operation == "GET")
{
return this.keyValueStore.Get(command.Key);
}
else if (command.Operation == "DELETE")
{
return this.keyValueStore.Delete(command.Key);
}
else if (command.Operation == "UPDATE")
{
return this.keyValueStore.Update(command.Key, command.Value.ToString());
}
return new StatusModel { Status = StatusConst.Error, Message = "Error"};
}
Handling Multiple Clients
One of the biggest challenges in building a server is to have the ability to handle multiple clients simultaneously.
We can do this by blocking threads and using asynchronous processing wherever possible.
Let's make small changes to Server.cs to enable multiple client requests.
public void Start()
{
listener.Start();
Console.WriteLine($"Server started. Listening on port {Port}...");
ClientListenerAsync().ConfigureAwait(false);
// The server will keep running indefinitely until manually stopped.
// Make sure to handle any necessary cleanup or termination logic.
}
public async Task ClientListenerAsync()
{
while (true)
{
var client = await listener.AcceptTcpClientAsync();
Task.Run(() => ClientHandler(client));
}
}
Conclusion
There were a lot of firsts for me in this project. Networking programming, TTL implementation, and multiclient support.
In the second part of the KVLite series, we will cover SnapShot backup of data in memory, and different data structure support for values.
I am hoping you have learnt something in this article.
I write about System Design, UX, and Digital Experiences. If you liked my content, do kindly like and share it with your network. And please don't forget to subscribe for more technical content like this.