QuillNEW

High performance .NET: Building a Redis Clone–separation of computation & I/O

by Oren Eini

After achieving 1.25 million ops/sec, I decided to see what would happen if I would change the code to support pipelining. That ended up being quite involved, because I needed to both keep track of all the incoming work as well as send the work to multiple locations. The code itself is garbage, in my opinion. It is worth it only as far as it points me inthe right direction in terms of the overall architecture. You can read it below, but it is a bit complex. We read from the client as much as we are able, then we send it to each of the dedicated threads to run it.

In terms of performance, it is actually slower than the previous iteration (by about 20%!), but it serves a very important aspect, it makes it easy to tell where the costs are.

Take a look at the following profiler result:

image

You can see that we are spending a lot of time in I/O and in string processing. The GC time is also quite significant.

Conversely, when we actually process the commands from the clients, we are spending most of the time simply idling.

image

I want to tackle this in stages. The first part is to stop using strings all over the place. The next stage after that will likely be to change the I/O model.

For now, here is where we stand:

using System.Collections.Concurrent;
using System.Net.Sockets;
using System.Text;
using System.Threading.Channels;

var listener = new TcpListener(System.Net.IPAddress.Any, 6379);
listener.Start();

ShardedDictionary _state = new(Environment.ProcessorCount / 2);

while (true)
{
    var tcp = listener.AcceptTcpClient();
    var stream = tcp.GetStream();
    var client = new Client(tcp, new StreamReader(stream), new StreamWriter(stream)
    {
        AutoFlush = true
    }, _state);
    var _ = client.ReadAsync();
}

class Client
{
    public readonly TcpClient Tcp;
    public readonly StreamReader Reader;
    public readonly StreamWriter Writer;
    public readonly ShardedDictionary Dic;

    public struct Command
    {
        public string Key;
        public string? Value;
        public bool Completed;
    }


    private List<string> _args = new();
    private Task<string?> _nextLine;
    private Command[] _commands = Array.Empty<Command>();
    private int _commandsLength = 0;
    private StringBuilder _buffer = new();
    private int _shardFactor;

    public Client(TcpClient tcp, StreamReader reader, StreamWriter writer, ShardedDictionary dic)
    {
        Tcp = tcp;
        Reader = reader;
        Writer = writer;
        Dic = dic;
        _shardFactor = dic.Factor;
    }

    public async Task ReadAsync()
    {
        try
        {
            while (true)
            {
                if (_buffer.Length != 0)
                {
                    await Writer.WriteAsync(_buffer);
                    _buffer.Length = 0;
                }
                var lineTask = _nextLine ?? Reader.ReadLineAsync();
                if (lineTask.IsCompleted == false)
                {
                    if (_commandsLength != 0)
                    {
                        _nextLine = lineTask;
                        Dic.Enqueue(this, Math.Abs(_commands[0].Key.GetHashCode()) % _shardFactor);
                        return;
                    }
                }
                var line = await lineTask;
                _nextLine = null;
                if (line == null)
                {
                    using (Tcp) // done reading...
                    {
                        return;
                    }
                }

                await ReadCommand(line);

                AddCommand();
            }
        }
        catch (Exception e)
        {
            await HandleError(e);
        }
    }

    private async Task ReadCommand(string line)
    {
        _args.Clear();
        if (line[0] != '*')
            throw new InvalidDataException("Cannot understand arg batch: " + line);
        var argsv = int.Parse(line.Substring(1));
        for (int i = 0; i < argsv; i++)
        {
            line = await Reader.ReadLineAsync() ?? string.Empty;
            if (line[0] != '$')
                throw new InvalidDataException("Cannot understand arg length: " + line);
            var argLen = int.Parse(line.Substring(1));
            line = await Reader.ReadLineAsync() ?? string.Empty;
            if (line.Length != argLen)
                throw new InvalidDataException("Wrong arg length expected " + argLen + " got: " + line);

            _args.Add(line);
        }
    }

    private void AddCommand()
    {
        if (_commandsLength >= _commands.Length)
        {
            Array.Resize(ref _commands, _commands.Length + 8);
        }
        ref Command cmd = ref _commands[_commandsLength++];
        cmd.Completed = false;
        switch (_args[0])
        {
            case "GET":
                cmd.Key = _args[1];
                cmd.Value = null;
                break;
            case "SET":
                cmd.Key = _args[1];
                cmd.Value = _args[2];
                break;
            default:
                throw new ArgumentOutOfRangeException("Unknown command: " + _args[0]);
        }
    }

    public async Task NextAsync()
    {
        try
        {
            WriteToBuffer();

            await ReadAsync();
        }
        catch (Exception e)
        {
            await HandleError(e);
        }
    }

    private void WriteToBuffer()
    {
        for (int i = 0; i < _commandsLength; i++)
        {
            ref Command cmd = ref _commands[i];
            if (cmd.Value == null)
            {
                _buffer.Append("$-1\r\n");
            }
            else
            {
                _buffer.Append($"${cmd.Value.Length}\r\n{cmd.Value}\r\n");
            }
        }
        _commandsLength = 0;
    }

    public async Task HandleError(Exception e)
    {
        using (Tcp)
        {
            try
            {
                string? line;
                var errReader = new StringReader(e.ToString());
                while ((line = errReader.ReadLine()) != null)
                {
                    await Writer.WriteAsync("-");
                    await Writer.WriteLineAsync(line);
                }
                await Writer.FlushAsync();
            }
            catch (Exception)
            {
                // nothing we can do
            }
        }
    }

    internal void Execute(Dictionary<string, string> localDic, int index)
    {
        int? next = null;
        for (int i = 0; i < _commandsLength; i++)
        {
            ref var cmd = ref _commands[i];
            var cur = Math.Abs(cmd.Key.GetHashCode()) % _shardFactor;
            if (cur == index) // match
            {
                cmd.Completed = true;
                if (cmd.Value != null)
                {
                    localDic[cmd.Key] = cmd.Value;
                }
                else
                {
                    localDic.TryGetValue(cmd.Key, out cmd.Value);
                }
            }
            else if (cmd.Completed == false)
            {
                next = cur;
            }
        }
        if (next != null)
        {
            Dic.Enqueue(this, next.Value);
        }
        else
        {
            _ = NextAsync();
        }
    }
}

class ShardedDictionary
{
    Dictionary<string, string>[] _dics;
    BlockingCollection<Client>[] _workers;

    public int Factor => _dics.Length;

    public ShardedDictionary(int shardingFactor)
    {
        _dics = new Dictionary<string, string>[shardingFactor];
        _workers = new BlockingCollection<Client>[shardingFactor];

        for (int i = 0; i < shardingFactor; i++)
        {
            var dic = new Dictionary<string, string>();
            var worker = new BlockingCollection<Client>();
            _dics[i] = dic;
            _workers[i] = worker;
            var index = i;
            // readers
            new Thread(() =>
            {
                ExecWorker(dic, index, worker);
            })
            {
                IsBackground = true,
            }.Start();
        }
    }

    private static void ExecWorker(Dictionary<string, string> dic, int index, BlockingCollection<Client> worker)
    {
        while (true)
        {
            worker.Take().Execute(dic, index);
        }
    }

    public void Enqueue(Client c, int index)
    {
        _workers[index].Add(c);
    }

}

 

Woah, already finished? 🤯

If you found the article interesting, don’t miss a chance to try our database solution – totally for free!

Try nowtry now arrow icon