[NEW] Reaching 1 million requests per second on a single Valkey instance

[PingXie]

This is a true gem :). The proposal was originally brought up by @touitou-dan and below is a verbatim copy of https://github.com/redis/redis/issues/12489

---

The following is a proposal to accelerate Redis performance by:

Improving io-thread efficiency by totally offloading network layer from main thread. Reducing load on main thread remaining functionality by moving memory management and response formatting to the io-threads. Amortizing memory access latency by batching dictionary searches. We believe than by implementing these steps, a single Redis instance running on a multicore machine will deliver more than 1 million rps, up from under 400K rps as it is today.

Introduction

Io-threads were added to version 6.0 in order to split the network and some part of the application representation layer processing load among two or more cores. Io-threads can be used for both incoming requests and outgoing responses. When used on incoming traffic, io-threads not only read from the socket but also attempt to parse the first incoming request in the input buffer. In both directions, the main thread operates in a similar way, it balances the io tasks equally between the io-threads and itself, executes its part of the tasks and waits for others to complete their part before processing commands. This fan-out/fan-in approach keeps the solution simple has it requires no complex synchronization except from a barrier between the main and io threads. We measured the performance of Redis (version 7.0) with and without io-threads. All tests were performed on an EC2 Graviton 3 instance with 8 cores (r7g.2xl) with no replica and no TLS. In this test we first populated the DB with 3 million keys of size 512 bytes and sent GET/SET requests from 500 clients. The GET and SET distribution was 80 and 20% respectively. We measured the following performance numbers:

Without io-threads 205K rps With 6 additional io-threads (“—io-threads 7”) 295K rps With 6 additional io-threads doing also read 390K rps When analyzing the performance we found the following issues: a. Underutilized cores - despite the 2x performance acceleration io-threads provide, Redis main thread still spends only 57% (processPendingCommandAndInputBuffer) of time executing commands. This implies that 1. The io-threads are practically idle 57% of the time and that 2. the main thread is spending 43% of the time executing io related functionality that could and should be executed by the io-threads. In addition, out of the 57% spent on executing commands, more than 9 percent (addReplyBulk ) are spent on translating objects into responses. b. Memory management – Redis main thread spends more than 7% freeing object that have been allocated mostly by the io-threads. Such discordance between allocators and freers may cause lock contention on the jemalloc arenas and reduce efficiency. c. Memory pattern access – Redis dictionary is a straightforward but inefficient chained hash implementation. While traversing the hash linked lists, every access to either a dictEntry structure, pointer to key or a value object requires with high probability an expensive external memory access. In our tests we found that the main thread spent more that 26% on dictionary related operations.

Our suggestions:

Io-threads

We suggest to totally offload all network layer functionality from main thread to io-threads. Our preferred approach would be to divide the client layer into two halves. The first half, handled by the io-thread will be the “stream layer” which includes socket layer as well as parsing requests and formatting responses while the second part, handled by main thread, maintains the client execution’s state (blocked, watching, subscribing etc). Based on this, io-threads handle read/write/epoll on the sockets, parse and allocate commands and append the ready to be executed commands on one or more queues. The main thread extract commands from the queues, executes them in the client context and appends responses on the queues which the io-threads extract, format and transmit on the sockets. In addition to the standard Redis commands and responses, internal control commands will be exchange between io-threads and main thread such as creating and erasing client states, pausing read from client sockets, requests to free previously allocated memory etc..

Dictionary memory access

Redis de facto executes commands in batches. We suggest that before executing a batch of commands we must ensure that all memory locations needed for dictionary operations will be find in the (L1/2/3) caches and avoid the latency associated with external memory accesses. This is done by searching in the dictionary all keys from a batch of commands before executing them. Searching the dictionary with more than on key at a time, when using prefetch instructions properly, allows to amortize memory access latency. From our experience, up to 65 % of the time spent on dictionary operations can be reduced this way.

Alternative solutions

An alternative approach to increase parallelism would be to allow main and io threads run in parallel on an unmodified client layer and prevent conflicting accesses between the io and main thread with locks. Such approach, while theoretically simpler, may require considerable testing to ensure consistency as well as avoiding lock related issues such as contention and deadlocks.

Dictionary inefficiencies can be solved by replacing the hash table implementation with a more "cache friendly" one that amortizes memory access by storing entire buckets in one or more adjacent cache lines. This approach has the advantage of being more "neighbor friendly" as it issues considerably less requests to the memory channels. However since Redis dictionary deliver a non standard programmatic interface ("key to dictEntry" mapping rather than "key to value" mapping) , replacing the hash implementation requires a much bigger coding and testing effort than the proposed alternative.

[madolson]

@touitou-dan was still working on this with @uriyage. I'm planning on syncing with them internally to see what their status is and how we can port the changes here.

[kamulos]

We are developing an application that went through a series of big architectural changes. Initially it was many threads, each with its own Redis connection.

1. The first big improvement was switching to Rust (redis-rs), where in each process the Requests of many concurrent async tasks are routed through a single TCP connection. This works incredibly well, but there is a bit of fear left in terms of head-of-line blocking. The other issue #17 proposed using QUIC. It is a complexity beast, but maybe it fits the use-case well.

2. At some point we started collecting requests on the client side for a few microseconds and then sending them as a batch to Redis. This basically doubled the throughput (at the expense of latency). I'll leave the interpretation of this to the experts, but we were really surprised about the big improvement.

3. No we are using Cluster, and the throughput of a single DB instance does not matter that much anymore. But any improvement that is made here, we will try to get into reality in our product.

[mattsta]

I think there's a divide between two basic use cases which changes development priorities:

• people who just want a cache and don't truly care about performance or implementation as long as "it just works"
• people who want to do things like a billion requests per second on a 1U 168-core machine with 3 TB RAM (this machine costs about $70k today) connected in a terabit converged ethernet mesh.

Most of the "Redis panic" is around hosting providers just wanting to continue servicing easy use cases, but there's a lot of room for "bug fixes and performance enhancements" too for much more advanced use cases.

Let me continue bringing up the work I've spent 10,000 hours implementing most of these fixes already, but I'm afraid to release publicly because if I see more of my high performance code get deployed on tens of millions of computers without compensation I'll just have to walk into the ocean.

db rewrite details: https://matt.sh/best-database-ever data structure improvement details: https://matt.sh/trillion-dollar-data-structure un-maintained demo site with some entry-level docs: https://carrierdb.cloud/

[lipzhu]

Really look forward to this io-threads refactor, speaking of the io-thread, I have an optimization https://github.com/valkey-io/valkey/pull/111 which changed strategy from the threshold to decay rate when enable/disable io-threads, this can help both from high core count and CPU efficiency perspectives. @valkey-io/core-team, do you mind helping this https://github.com/valkey-io/valkey/pull/111 first before io-thread refactor?

Dictionary memory access

BTW, I also noticed the memory latency before, below is the disassembly code of dictFind, we can see the memory access instruction contribute the most cycles, the corresponding code is https://github.com/valkey-io/valkey/blob/unstable/src/dict.c#L743. Maybe we could do some prefetch before this line and a new function like dictFindBatch to handle the prefetch work?

[PingXie]

Yeah I will take a look. Btw, a few of us are at the Linux open source summit this week so our response would be a bit slower than usual.

[PingXie]

@lipzhu, I am still waiting for the detailed design. Here is my understanding of what we are trying to achieve here (but @madolson @touitou-dan can let me know if I am mistaken). With this proposal,

1. We will have per-thread epoll loop
2. As a result, user connections will be affinitized to the worker thread
3. If the connection is ready for read a. read from the socket b. parse the command into the executable format (argv[] array) c. add the parsed command to a global command queue
4. there will be a main thread, which pulls the commands queued in step 3.c, executes them (in batches potentially to take advantage of the parallel execution enabled by the CPU), generates the output (an array of robj?) but don't encode the output, and finally queues the output (array) into the per connection output queue. a. we will also queue the parsed/rewritten commands for replication to the output queue associated with the replication connection
5. If the connection is ready for write a. pulls the output array out of the corresponding connection queue b. encodes it into the output buffer c. releases the args and output arrays

IF this is the proposal (even with just step 1 and 2), I don't see the optimization proposed in #111 getting carried over.

[lipzhu]

@PingXie Maybe I confused you, https://github.com/valkey-io/valkey/pull/111 is inspired from https://github.com/redis/redis/pull/12305#issuecomment-1619530121.

For existing io-threads implementation, user may found that with the same client requests pressure, server with more CPU allocated and io-threads number configured have lower QPS than server with little io-threads configured, this doesn't make sense. Test scenario is updated in https://github.com/valkey-io/valkey/pull/111#issue-2217438933

[mattsta]

Those are all logical steps. Very similar to when I worked out a multi-threaded archietcture a couple years ago:

Be careful though because eventually you just end up implementing a full programming language virtual machine to solve the problem.

You'll end up with a full internal bytecode/IR mapping for translating all client commands into more detailed internal features because you need to manage: command distribution, a work queue, letting some workers sleep (so then you also need to implement a scheduler), then the replies have to be happy; then you also have to check if your TLS library supports isolating readers and writers concurrently or if you have to lock them all down simultaneously, etc.

[PingXie]

Maybe we could do some prefetch before this line

My understanding is that the slow access is a result of d->ht_table[table][idx] but since it depends on the idx value computed on the line right above, and then the value (he) is used right after, it is not clear to me with which operations we could run the prefetching in parallel?

        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        while(he) {

a new function like dictFindBatch to handle the prefetch work?

Yeah, I also think this will increase the cache hit rate.

[PingXie]

@PingXie Maybe I confused you, #111 is inspired from redis/redis#12305 (comment).

For existing io-threads implementation, user may found that with the same client requests pressure, server with more CPU allocated and io-threads number configured have lower QPS than server with little io-threads configured, this doesn't make sense. Test scenario is updated in #111 (comment)

Understood. I was thinking more along the line of "longevity" for #111. From a quick look at the PR, I think it is pretty contained and the change makes sense to me. If it doesn't increase our tech debts (which doesn't look like the case right now), I agree it makes sense to continue improving the status quo. I will take a close look at #111 next.

[PingXie]

Be careful though because eventually you just end up implementing a full programming language virtual machine to solve the problem.

Good point @mattsta. I wonder if there is a way to materialize this proposal in phases. We will need a more concrete design first.

[lipzhu]

@PingXie Maybe I confused you, #111 is inspired from redis/redis#12305 (comment). For existing io-threads implementation, user may found that with the same client requests pressure, server with more CPU allocated and io-threads number configured have lower QPS than server with little io-threads configured, this doesn't make sense. Test scenario is updated in #111 (comment)

Understood. I was thinking more along the line of "longevity" for #111. From a quick look at the PR, I think it is pretty contained and the change makes sense to me. If it doesn't increase our tech debts (which doesn't look like the case right now), I agree it makes sense to continue improving the status quo. I will take a close look at #111 next.

Look forward to your help :)