Turning 38 is bad luck. Good luck is being healthy.

Getting cancer at 38 is bad luck. Good luck is having no metastases.

Developing metastases a year later is bad luck. Good luck is having them only in the lungs.

Having the first two lines of treatment fail is bad luck. Good luck is responding to the third.

Having the tumor quickly become resistant to the third line is bad luck. Good luck is that molecular testing points to a couple of other promising drugs.

Running out of treatment options and slowly dying from suffocation is bad luck. Good luck is knowing that it will soon be over.

Luck has layers.

Dictionary structure, key eviction, hash table resize and rehash, and command execution

By now, I’ve already considered how Redis server starts up, how clients connect to it, and how Redis reads their commands and writes responses — both in a single-threaded and I/O threaded mode. Finally, I’ve made my way to the heart of Redis in this Redis 7 Internals series. In this post, I’ll describe how its db engine, if I may call it so, is implemented. This is where Redis finally executes a command. Unlike I/O operations, like reading and parsing clients’ commands and writing responses, this is always done in a single main thread.

I won’t repeat the basic concepts that Redis relies upon, like epoll multiplexing mechanism, event loop, and non-blocking I/O. Instead, let’s get straight to where I left off when I described command parsing: command processing.

From a higher-level view, this logic looks like the following. A command is looked up, then Redis checks whether it can execute it for this client, and if it can, it does some chores and finally executes it.

Redis Looks Up a Command and Checks Whether It Can Execute It

First, Redis looks up a command. All commands are stored in a redisServer.commands dict, which is populated during start-up. Redis simply fetches a command from this dictionary. If it doesn’t exist, then it’s not executed, apparently.

Before executing a command, Redis runs some checks. There are lots of them, indeed. Here are some of those:

• Redis makes sure that a client has passed a correct number of arguments.
• Redis checks ACL whether a client is allowed to run this command.
• Given there are problems with saving data on disk, if a command is a write one and it’s sent by an ordinary client, not a master, then Redis rejects this command.
• Given healthy replicas, quantity and max allowed lag are configured. If there’re not enough of them, the write command can’t be run.
• Apparently, Redis can’t execute a write command from ordinary clients (non-master) on a read-only slave.
• Given stale reads are not allowed, if a command which doesn’t allow stale reads is run on a replica with a broken connection to a master, it’s rejected. You can tell that a command allows stale reads if it has a CMD_STALE flag — echo or hello, for instance. Most of them don’t, though.
• Given an RDB file or AOF file is loading right now if the current command isn’t loading-compatible, then it’s rejected. As always, this property is defined as a flag — CMD_LOADING, in this case. The same goes for asynchronous loading, which is available only on a replica during a catch-up with the master.
• If a replica wants to execute a read-, write-, or a replicable command (that is, almost any command), Redis master rejects it.

Besides those checks, Redis runs some mandatory procedures.

Overview of Structures Redis Uses for Data Storage

Each Redis database has two dictionaries. The first one is used for keys with expiry date. It’s redisDb.expires, and values stored there are expiration timestamps. The other is for client values; it’s redisDb.dict.

Each Redis dict has two hash tables. Both are implemented as a plain array; each slot, or bucket, contains a list of elements — in case of several elements’ hashes point at the same array index (this is known as a hash collision). Thus, it’s a classic hash table implementation, nothing special:

But why two of them? Just wait a sec, I’ll describe it in the next section.

Which data structures do hash tables contain? Each one stores linked lists of dictEntrys. The client key is in its key field. In the case of a dict struct, val field stores a redisObject which points to a client-set value. Most of the time, data that clients create and manipulate is stored exclusively there — in a redisObject.ptr pointer. expires dictionary stores client-defined expiration timestamps in the dictEntry.v.s64 field in milliseconds.

Here is an overall view of what a dictionary looks like:

Short Recap of Maintenance Procedures: Resize and Rehash of Dictionaries

When the number of elements in a hash table is high, the hash collision number increases. For instance, if a hash table has four buckets and four hundred elements, each bucket contains a list of about a hundred elements in length. Search time complexity effectively degrades to linear — O(n) instead of remaining constant — O(1).

That’s why Redis monitors a hash table size: if the number of elements becomes too high, a hash table is expanded. Having a sparse hash table is no good either: Redis has some procedures which iterate over a hash table. If it has a million buckets and just one element, most CPU cycles are wasted on iteration itself instead of doing some useful stuff. That’s why Redis shrinks sparse hash tables.

But it’s not an in-place algorithm. Expanding and rehashing all of the elements in one go would take a lot of time. That’s why Redis does that incrementally. First, it creates a new hash table with a suitable size. Then, it starts moving elements there from the first hash table gradually. In each cron iteration, Redis rehashes elements residing in one hundred consecutive buckets. Besides, while accessing or mutating a hash table, elements from a single bucket are rehashed. Redis remembers a bucket index where it left off; it’s stored in dict.rehashidx. All the previous buckets are guaranteed to be empty; all the subsequent ones probably contain some data:

You can read implementation details of those processes in the first post of this series.

Redis Runs Some Regular Procedures Before Command Execution

Clients are evicted

Redis tracks how much memory each client consumes. Those clients are stored in a redisServer.client_mem_usage_buckets array. Clients are grouped in buckets by the amount of memory they occupy, and clients are stored in each bucket as a list. For instance, the first bucket stores clients, which take up to 32 kB. The second one stored clients taking up to 64 kB, and so on: memory threshold doubles with each subsequent bucket. The last one stores clients occupying more than 4 GB:

If a memory limit for how much memory clients can occupy is configured, Redis starts the eviction procedure. What is meant by client eviction is all memory associated with a client is freed. Redis starts with the last redisServer.client_mem_usage_buckets bucket, where the clients consuming the highest amount of memory are located. Before each new client’s eviction, Redis checks whether the total memory occupied by all clients fits into the specified limit. If it does, eviction stops. If not, the next client in the current bucket is evicted. If no clients are left in a current bucket, Redis moves to the next one. During a client eviction process, everything about a client is freed: read but not yet parsed commands, parsed commands with arguments, non-sent replies, watched keys, pubsub-related stuff. Besides, a connection socket is closed.

Keys are evicted

Key eviction is a process that runs when Redis occupies more memory than a configured limit, and it has to delete some keys. If a policy has a random in its name, it’s really nothing special: Redis just picks a random key in each database and deletes it. It’s quick and dirty.

But for all other policies, key eviction logic is more involved. From the higher level, each iteration looks like the following. Redis takes a sample of keys from the first database, then for each element, it calculates a property called “idle time” and finally inserts an element in a 16-sized pool in ascending order. Over time, the meaning of “idle time” broadened, but the crucial property remained: the greater the value, the more suitable it is for eviction. This process is repeated for each database. Finally, when Redis has a pool of keys from each database, the key with the highest “idle time” is deleted.

Don’t forget that this logic is executed in the context of running a command. Redis doesn’t aim to arrive within memory limits in one go — this can take too long. Instead, keys are evicted iteratively and within strict temporal boundaries. The maximum duration is configured by maxmemory-eviction-tenacity setting. When it’s lower or equal to ten, the specified value is a factor of 50 μs. When it’s higher than ten but lower than 100, each subsequent duration is 15% higher than the previous. maxmemory-eviction-tenacity equaling 100 effectively disables a time limit:

The default value is 10, so before executing a command, Redis performs key eviction for not much longer than 0.5 ms.

Now let’s look at one iteration of key eviction in more detail. I start with an eviction pool filling. The following logic is executed for each database, but keys are inserted in a single fixed-sized pool.

Redis gets a sample of keys from a current database
This is what dictGetSomeKeys() does. Strictly speaking, it doesn’t get a sample. In statistics, the sample is supposed to be random and filled independently. Instead, this procedure simply takes maxmemory-samples (by default, it’s five) subsequent elements starting with the one chosen randomly from a given dictionary.

Which dictionary is sampled? If a policy has a volatile in its name, it means that only keys with explicitly set expiry timestamps are eligible for eviction. In this case, an expires dictionary is sampled. Otherwise, dict is chosen.

When rehashing is not in progress, implementation is quite straightforward. Redis just picks a random bucket in a hash table and iterates it, collecting elements along the way. First, it iterates each bucket’s list. If it’s empty or there are no more elements in it, Redis moves to the next bucket. When it’s collected maxmemory-samples of them, it stops.

When rehashing is in progress, the logic is a bit more involved. Generally, it looks like the following. First, Redis generates a random index. Then, it goes to the first hash table’s bucket, which resides under this generated initial index and iterates all elements from that bucket’s list. Then, it goes to the second table’s bucket of the same index and gets all elements from there. Then, Redis repeats that with the subsequent index, and so on — until the necessary number of elements is collected. To illustrate this process, I’d like to consider one normal case and two more edge ones, in more detail.

Rehashing is in progress: the dictionary is expanding, and a random index is greater than a rehash index.

Let’s say a random index is 5:

The iteration looks like this:

Here is what the resulting pool looks like:

Now, let’s move on to some more rare cases.

Rehashing is in progress: the dictionary is shrinking, and a random index is less than a rehash index but greater than the second hash table size.

Let’s say a random index is 4. In this case, an initial index is set to rehash index because all the buckets before the rehash index are empty:

During pool population, only the larger table is iterated — the one that is being shrunk because an initial index is greater than the size of the second hash table:

As a result, there are only four items in a pool — this is less than what was asked. But there are no more items left.

Rehashing is in progress: the dictionary is expanding, and a random index is still less than a rehash index.

Let’s say a random index is 1:

In this case, Redis iterates through both hash tables but skips already rehashed buckets from the first hash table — they are empty anyway:

Here is the resulting pool:

After a pool is ready, Redis goes to the next part.

Redis sorts a pool
Then, Redis sorts a pool in an ascending idle time order. For different key eviction policies, “idle time” means different things, but it has a crucial property: the greater it is, the better candidate for eviction a corresponding item is.

Idle time in case of LRU policy
The “idle time” name was coined at times when the only policy implemented in Redis was the Last Recently Used. When it’s employed, the best candidate for eviction is the last recently used one, indeed. In this case, redisObject.lru stores LRU_BITS (which is 24) least significant bits of a timestamp when a corresponding key was last looked up:

It means that this value wraps around every 194 days. In other words, Redis can’t tell the difference between the last lookup time of one day ago and 195 days ago. For most workloads, I think it’s OK though: if you have keys that are looked up that rarely, it’s not a problem to hit a database one or two times a year in case they got evicted.

In the case of LRU policy, the best candidate for eviction is the one used the least recently. In this case, “idle time” means what it is: a time interval when a current key has not been looked up:

idle = now() - dictEntry.val.lru

Let’s now move to how idle time is calculated when LFU is used.

Idle time in case of LFU policy
In this case, redisObject.lru stores a combination of when the key was last looked up, concatenated with a relative usage frequency:

The last lookup time wraps around every 45-something days, which isn’t a problem still, I believe. Redis needs it to calculate key usage frequency; I’ll describe it in a few moments. The frequency itself is not a precisely calculated value reflecting a physical concept of frequency. We don’t need that. It’s enough for us if it just correlates with usage frequency so that it can be used for comparing with each other. Since it is just 8 bits, 0 is for the least frequency, and 255 is for the greatest one.

Now, how is it updated? It’s a three-step process. First, a counter is decreased proportionally to the time a corresponding key has not been looked up. That sounds natural: if a key was last looked up a month ago, its usage frequency is low. That’s what Redis stores the last lookup time for. Second, a counter is increased probabilistically: the greater a counter, the less likely it is to increase. Why so? Because we need a counter to fit in 8 bits, so we slower its increase rate. Third, a new timestamp in minutes is taken, and the 16 least significant bits are extracted and concatenated with a new counter.

How’s “idle time” calculated when this policy is in place? In the case of LFU, we need an inversed frequency so that the higher the frequency, the lower the “idle time,” so the less suitable this item is for eviction. The opposite is true: the lower the frequency, the higher the “idle time”, so the more suitable this item is for eviction. Thus, Redis extracts this frequency and subtracts it from its maximum possible value, 255:

idle = 255 - LFUDecrAndReturn(o);

Idle time in case of volatile-ttl policy
When this eviction policy is used, it is an expires dictionary, which is sampled. Keys there are ordinary client-set keys, but values are expiration timestamps. We invert them: the lower an expiration timestamp, the better it suits for eviction:

idle = ULLONG_MAX - (long)dictGetVal(de);

Redis removes a key with the highest “idle time”
By now, Redis has an ordered pool of elements. Then, Redis just picks the last element — the one with the highest “idle time”, and deletes it.

That’s pretty much it. Now Redis is ready to run a client command.

Redis Executes a Command

Finally, Redis runs a command. This boils down to invoking a redisCommandProc *proc field of a client’s parsed command. So, if you want to see a source code of some specific command, head to commands table, find there a command you’re interested in, and click on the eleventh argument. This procedure is an implementation of a command you’re looking for.

Generic flow of a command

It’s quite simple, actually. First, Redis finds an element in a dictionary with one of the procedures whose name starts with lookupKey…. Typically, it’s either lookupKeyWrite(), or lookupKeyRead(), or lookupKeyWriteOrReply(), or lookupKeyReadOrReply(). The difference between read and write procedures are that the latter deletes an expired element even on a read-only replica. ...OrReply procedures add a reply in case the key is missing.

After an element is found, Redis runs whichever logic is implied by a command. That’s the core of a command. If it’s complicated enough, it’s often extracted into its own procedure. For instance, in the case of a simple get command, the found value is just wrapped in a reply and stored in a client struct for future sending. In the case of a zadd command, where Redis inserts each element a client sent in a sorted set, this logic is encapsulated in zsetAdd procedure, and so on. Just pick a command you’re interested in and dive into its implementation!

Key lookup

The majority of Redis commands first look up a passed key. Let’s consider this in more detail.

lookupKey…-family of procedures operate on a redisDb level: they all have it as a first argument. This is quite a high level of abstraction: there is no search logic itself. Instead, it’s outsourced to the dictFind procedure, which operates on dict-level. This procedure is a typical implementation of a hash table search logic, with some Redis specifics in case of rehash is in progress. First, Redis runs one step of it, and second, Redis checks both hash tables for a searched key. Besides, if rehash is in progress, Redis runs a rehash step on each data manipulation operation.

When dictFind returns a dictEntry and it exists, Redis checks whether this element has already expired. If it has, but a command is executed on a replica by a master, elements are never considered expired. Otherwise, unless a key was looked up with either lookupKeyWrite() or lookupKeyWriteOrReply(), it’s considered expired but not physically removed. Besides, if EXPIRE_AVOID_DELETE_EXPIRED is present, the current expired key is not evicted either. In all other cases, an expired key is deleted. As a special case, this includes a situation when a key has expired on a read-only replica, but it’s looked up with a …Write-family of procedures.

Finally, if a key has survived an expiration logic, its access time is updated depending on an eviction policy used. There are two exceptions for this. The first one is when a client explicitly specified that it doesn’t want to modify an access time. The second one is when there is currently a child process running. Why? When a child process is created through forking, it inherits access to the same data as the parent process.

This is made possible by the copy-on-write (CoW) technique, which is a mechanism implemented by the operating system. If either the parent or child process modifies shared data, a new memory page is copied, and the changes are visible only to the process that made the modification. This results in increased memory usage and potential performance overhead. That’s why Redis avoids performing maintenance tasks while a child process is running.

In closing

That’s it for this article and likely for this Redis 7 Internals series. I’ve described some parts which were interesting to me, but of course, there are lots of cool features left that I haven’t touched.

Redis is an incredible piece of software: it’s extremely fast, well-designed, and its code is remarkably readable. I’ve had a really good time diving into it, and I encourage you to do it too.

Redis Internals: Redis Processes a Command was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

With one I/O thread

In the previous article of the Redis 7 Internals series, I discussed how Redis handles command parsing and response sending to clients without using I/O threads. I encourage you to read it as this current article is a logical continuation, building upon the concepts explained there. With this in mind, I won’t recap here the major Redis concepts it relies heavily on, such as an epoll instance, connection sockets, and an event loop.

I still won’t delve into a command execution itself — that’s what my next article is about. Instead, I’m focusing on I/O threads implementation. I think this is where my Miro diagram is helpful the most.

What are I/O Threads, and When Might They Be Useful

In short, I/O threads are ordinary threads that execute I/O operations — namely, response writing and, optionally, command parsing — in parallel. To realize when this can be useful, let’s first consider two scenarios that seem to be a reason to introduce this functionality.

Problem: thousands of consequent socket writes of under-64-kB-sized data in the single main thread can take too long

Suppose we have a Redis instance with a single main thread and lots of simultaneously connected clients (think of thousands). Then, at about the same time, each sends a command. Redis executes those commands one by one and then writes a response. As you’ve hopefully read in the previous article, this writing is done in NET_MAX_WRITES_PER_EVENT-sized batches — that is, 64 kB each. As a reminder, this is done so that each client gets an equal share of time.

How long would it take to send responses to each of them? Let’s suppose that each response size is exactly NET_MAX_WRITES_PER_EVENT. Single write call with data of this size takes about 20 μs on my laptop. Multiplying it by ten thousand, you get a whopping 200 ms. That is, the client whose command was received last will experience 200 ms of added latency induced exclusively by a sequence of ten thousand write system calls.

That’s what a really heavy and under-optimized search query takes in my PostgreSQL instance. Even if I neglect data processing and network transmission time, both mean and median latencies are roughly 100 ms. In reality, this number would be several times more. Sounds like a lot for a highly performant in-memory data store.

Even if a response size is more reasonable, like 1 kB, write call duration doesn’t decrease proportionally. I suppose this is due to a fixed cost of a system call itself, which is comparable with the cost of moving data of this size. It becomes about 7–10 μs on my laptop. Thus, despite some latency gain, it seems that median latency of 35–50 ms is something we can and should do about.

And what about reading and parsing commands? Given the most frequent Redis commands is likely GET, an entire command is RESP format is about 30 bytes. Reading this data takes several microseconds — not that different from reading or writing 1 kB, actually. Thus, the latency induced solely by read system calls is similar to that induced by write system calls.

Solution: Redis runs all I/O in parallel threads

The solution represents a common way these problems are solved: if a system has a bottleneck, identify a limited resource and scale out. The bottleneck here is evident: it’s a single thread that does all the readings and writings. A limited resource in Redis is the single main thread running on a single CPU core at any moment. Scaling out runs more threads on more CPU cores.

Hence, this brings us to I/O threads, which hopefully run all I/O operations in parallel. Actually, this is an OS that decides which thread to run on which CPU core. But, generally, if the overall system load is normal, and your application utilizes several parallel threads, chances are high that they run on separate cores. If they don’t, you can always tweak the CPU affinity setting.

Once again, I’m talking about this specific scenario when write size is under 64 kB. Now, let’s consider the next scenario where the size of the data being written is higher.

Problem: thousands of consequent socket writes of over-64-kB-sized data in the single main thread can take way longer

In this case, after the first NET_MAX_WRITES_PER_EVENT-sized chunk is written for each client, Redis subscribes to write events for each connection socket. That means that if the network is not congested, Redis will send the remaining part of a response in a subsequent event loop iteration. In other words, in the best-case scenario, when the network doesn’t experience congestion and send buffers are emptied quickly, Redis sends NET_MAX_WRITES_PER_EVENT-sized chunks to each client in each event loop iteration — until an entire response is written:

Even if each response size is slightly higher than 64 kB, mean latency triples. As I’ve written in the previous section, both mean and median latencies are about 100 ms. If Redis needs two event loop iterations, both mean and median latencies become 300 ms. In other words, this value increases by 200 ms on each event loop iteration. In percentage terms, some clients experience latency way worse than others: a client whose command was received first has to wait until Redis writes responses to all other 9999 clients on the first iteration. Thus, it has to wait an additional 200 ms. You can feel the difference with the previous scenario when additional latency induced by writes was just its own write system call, that is, 20 μs.

Solution: Redis runs writes in I/O threads

Given an average command size is still 30 bytes, the contribution of a read call to the overall latency is still a few microseconds. If an average response size is hundreds of kilobytes, the contribution of write calls is higher. Moving the reading part into I/O threads won’t be as noticeable as parallelizing the writing.

OK, so should I try this feature?

As I’ve described above, I/O threads shine when there are lots of clients and even better when responses are large. How much is “lots of clients,” and how much is “responses are large,” exactly? You can do some math and calculate it for your specific case and setting, but generally, enabling this feature and seeing the result is a lot easier. But first, ensure you have a good monitoring tool to compare the performance adequately.

Last but not least, note that command execution is still single-threaded! I’ll show it in a source code later anyway, but if you don’t read that far, I think it’s important to mention this fact.

Let’s consider what happens in Redis internals when several clients send commands. I/O threads mechanics unfold gradually, so I’ll describe a specific example starting with Redis start-up followed by several event loop iterations.

Redis Configuration and Start-Up

I assume that Redis is configured with one I/O thread (io-threads equals 2), and reading and parsing is also done in I/O threads. Thus, our single I/O thread is created and paused before running the first event loop iteration.

Here is a brief description of how I/O threads are created and run.

I/O Threads Start-Up Recap

As a reminder, IO threads start when Redis starts up. If the number of threads specified in a config is 1, then I/O threads mechanism is efficiently disabled. If their quantity is no more than IO_THREADS_MAX_NUM, Redis repeats the following logic IO_THREADS_MAX_NUM - 1 times (excluding the main thread).

First, it initializes and acquires a current thread’s mutex. Then, sets a number of clients to be processed by it to zero. And after that, Redis actually creates a thread. IOThreadMain is the procedure that runs in each of those threads. It’s an infinite loop that basically does two things.

First, after an I/O thread is created, it tries to acquire a lock if there are no clients assigned to it. If the main thread already acquires this lock, then IO thread hangs. And that’s exactly what happens when Redis starts. Note that it’s not a busy wait, though. That is, the CPU is not utilized. There is also a tricky 1,000,000 for-loop that breaks when getIOPendingCount(id) != 0. I’ll get back to it soon.

The second one is iteration through clients designated to a current I/O thread. For each client, Redis either reads a command or writes a response. The specific strategy is defined by an io_threads_op global variable. When it’s completed, clients list is emptied.

First Iteration: One Client Sends a Single Command

I’ve described this case in the previous article in detail. Here is a short recap:

To begin, Redis receives new events with epoll_wait() procedure. For each read event, data is read. Then, Redis parses a command, executes it, and constructs a reply. Besides, a client is saved into a server.clients_pending_write list. It’s important to note that the reply is not immediately sent to a client. Instead, this occurs during the subsequent event loop iteration in the beforeSleep() procedure.

Second Iteration: Several Clients Send Commands; Redis Reads, Parses, and Executes Them

The second iteration starts beforeSleep() runs. Let’s suppose more clients start sending commands:

Meanwhile, Redis reaches handleClientsWithPendingReadsUsingThreads(). Our instance is configured to do client reads in I/O threads (server.io_threads_do_reads = 1), but they are inactive at the moment. So for now, we don’t do reads in parallel, even if currently there were thousands of clients sending commands.

Shortly after this, Redis writes a response for commands executed on a previous event loop iteration. This is done in handleClientsWithPendingWritesUsingThreads procedure. Redis first checks whether I/O threads are disabled (server.io_threads_num == 1) and even if they are not, assesses whether it makes sense to utilize parallelization. In our case, it doesn’t: there is a single client with pending writes, and it’s less then server.io_threads_num * 2, which is 4.

Thus, the four clients that have sent a command during this event loop iteration are processed as usual right after an epoll_wait call, in a loop over aeEventLoop->fired:

By the end of this iteration, there are four clients with pending responses. That is, the length of server.clients_pending_write is four.

Third Iteration: Redis Write Responses in I/O Threads

Clients keep sending new commands. Similar to the previous iteration, each one of the four clients sends a command. handleClientsWithPendingReadsUsingThreads doesn’t have a chance to do reading and parsing in parallel, even if there were thousands of clients: I/O threads are still inactive (server.io_threads_active = 0). And at this stage, Redis isn’t even supposed to activate them.

The situation is different with writes. Unlike a previous iteration, now there are enough clients to justify threaded response writing: there are four clients with pending responses, which is no less than server.io_threads_num * 2. Hence, Redis finally activates I/O threading facility. This boils down to unlocking each thread’s mutex and setting server.io_threads_active to 1:

As soon as mutexes are unlocked, all I/O threads wake up: they are finally able to acquire a lock they had been waiting on. But they release it right away and start a new iteration of a while-loop. And here goes that one million for-loop I’ve already mentioned earlier. While it runs, the main thread assigns clients from a server.clients_pending_write to threads:

After that, it sets a context for those threads. In our case, it’s a write context which is indicated by a IO_THREADS_OP_WRITE value. Finally, the main thread sets a number of clients to be processed by each thread, and this is a signal for each I/O thread that they can break that million-for-loop and start doing its work.

If a million iterations take less time than it’s needed for the main thread to assign IO threads with clients, nothing bad happens: mutex is locked, then unlocked right away, and the iteration continues — until getIOPendingCount(id) != 0. So this million-loop is just a way not to mess with locking and unlocking too often.

I’m calling it a poor-man’s condition variable signaling, but it’s not an arrogant sentiment from my side. I realize that Redis developers probably had very good reasons to do it the way it’s currently implemented — I’m simply not aware of them.

Once clients are assigned to threads, IO context is defined, and “condition variables” are set, all threads start writing responses. This is a fan-out part of a concurrency pattern Redis uses here. After the main thread is done with it, it waits until all other I/O threads finish.

Meanwhile, each I/O is doing its share of response sending. When they complete, their “condition variable” is zeroed, and an I/O thread enters a busy-wait state: it waits for another portion of clients.

Finally, a fan-in part follows in the main thread: Redis checks which clients still have pending writes. For those that do, it subscribes to write events in a corresponding socket and sets a handler function to sendReplyToClient. From a lower-level implementation point of view, response sending is no different from a single-threaded scenario.

This iteration ends the same way as all the others: Redis iterates through fired read events and invokes readQueryFromClient. But it behaves differently now: those reads are postponed for further processing. Besides, each client is put on a server.clients_pending_read list. Here is a higher-level view of the third iteration:

Thus, at the end of this iteration, four clients have pending reads. Let’s see how they are processed.

Fourth Iteration: Redis Reads and Parses Commands in I/O Threads

Finally, Redis can read and parse client commands in I/O threads. handleClientsWithPendingReadsUsingThreads checks server.io_threads_active , which is 1, and server.io_threads_do_reads, which is 1 either. Conceptually, the following logic differs from threaded writing; the same fan-out/fan-in approach is utilized. Let’s consider it briefly.

The fan-out part goes like this. First, the main thread takes a list of clients with pending reads created at the end of the previous iteration and allocates them per threads. Then it sets an IO context to reading. Finally, it sets a “condition variable” to the number of clients to be processed, which is a non-zero value.

Note that IO threads have already turned active on a previous event loop iteration. That is, they are not hanging: their mutex is already unlocked, and they are busy-waiting for new clients. As soon as getIOPendingCount(id) != 0, they start doing their work, depending on io_threads_op value. In this case, they readQueryFromClient. The main thread does its reads too.

It’s important to remember that readQueryFromClient procedure is used in a single-threaded context for reading, parsing (specifically, processMultibulkBuffer is used in case of multi-bulk requests), executing a command, and constructing a response. But in the case of the I/O thread context, the command execution doesn’t occur. After command is parsed, the client is marked as having a pending command, and that’s it.

It’s worth mentioning that during parsing, Redis can create responses indicating a protocol error. Like any reply, it boils down to addReplyProto procedure, which first calls prepareClientToWrite. This procedure puts a client in a pending write queue so that Redis will iterate it a few moments later and sends those responses. But there are two conditions for a client to end up there: it shouldn’t already be in that queue, which is natural, and this procedure should be called outside of a thread context.

The second condition's rationale is that Redis developers probably wanted to avoid lock contention. When appending a queue in a multi-threaded context, it should be done with locking (since Redis doesn’t use lock-free queues). However, this approach could potentially become a bottleneck. Thus, Redis simply avoids this concurrent mutation by adding a client in the write queue or in the fan-in stage.

The fan-in part is when it’s time to collect results. After all threads are done, the main thread drops an I/O context, iterates through clients whose commands Redis has just parsed, and executes those commands. If they imply a response, it’s created the same way as in a single-threaded scenario; specifically, a client is put in a pending write queue. Now remember the end of the previous paragraph — if a current client had an error in its command, it’s not put in that queue. That’s what Redis does now.

This pending write queue is processed in a handleClientsWithPendingWritesUsingThreads procedure. I’ve described it in detail in the previous section.

Here is its higher-level view of this iteration:

Suppose that one client sends a command during this iteration. Since I/O threads are still active, this client is added in a server.clients_pending_read list — the same way as at the end of the third iteration.

Fifth Iteration: I/O Threads Shut Down

There is a client with pending reads; it’s processed in handleClientsWithPendingReadsUsingThreads. Since there is only one client, it will be processed by the main thread. Its command is parsed and executed, as always. Then this client is put in a pending write queue that’s processed by a handleClientsWithPendingWritesUsingThreads procedure. And that is where Redis checks whether it’s still worthwhile to keep I/O threads running.

If there are fewer clients with pending writes then server.io_threads_num * 2, then Redis stops threaded I/O. That’s what happens in our case: one (listLength(server.clients_pending_write)) is less than four (server.io_threads_num * 2 = 2 * 2 = 4). The main thread just locks each thread’s mutex, and that’s it. I/O threads hang while trying to obtain an already-taken lock. Busy waiting ceases.

Note that if there were no clients sent on a previous iteration, Redis won’t have a chance to shut I/O threads down. They will be busy-waiting until some client sends a command that implies a response.

In closing

I hope you’ve enjoyed reading this article as much as I’ve enjoyed reading Redis source code and writing this piece. See you in the final part of this series, where I’m diving into command execution logic.

Redis Internals: Client Sends a Command and Receives a Response was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

The case when there are no I/O threads

In the previous article of the Redis 7 Internals series, I described what happens on the Redis side when a client connects to it via TCP. Now, I’ll consider what happens when a client sends a command and receives a response. Please note that I won’t delve here into an implementation of how Redis retrieves or writes data — its db engine, if I may call it so.

This part is command specific, and I will consider a general way of figuring this out, with an example, in a future article. Instead, this article focuses on how Redis receives a request and writes a response when there are no I/O threads. It’s probably the shortest and easiest article in this series, but it is a foundation for a more sophisticated I/O threads mechanism. I will describe it in the next article.

This article relies heavily on a concept of event loop — Redis’ driving force behind executing commands. So, at the risk of repeating myself time and again, I’ll first skim through its main parts. If you’ve already read any of my previous articles, feel free to skip them and head right to the main part.

Recap of Redis Start-Up Process

Epoll instance

An epoll instance is a fundamental data structure within the Linux kernel, encompassing two crucial components: an interest list and a ready list. By adding a file descriptor to the interest list, also known as an epoll set, the epoll instance continuously monitors it asynchronously for events. Events signify changes in the state of a file descriptor, primarily involving two distinct alterations.

The first change occurs when a file descriptor becomes readable, indicating data availability for reading. Essentially, the file descriptor transitions from a not-ready state to a state ready for reading. The second alteration occurs when a file descriptor’s buffer has sufficient space to write data. In such scenarios, these file descriptors are commonly referred to as writable. Whenever any of these events occur, the epoll instance promptly adds the corresponding file descriptor to the ready list:

To retrieve the file descriptors that are currently ready for input/output operations, the epoll_wait() procedure can be invoked.

Epoll represents just one of several multiplexing mechanisms utilized to track the state of file descriptors asynchronously. In the context of Redis, when it is built on the Linux operating system, epoll serves as the chosen implementation.

Connection socket

During a startup, Redis creates listening sockets and registers them in an epoll instance for read events. Those listening sockets store all incoming client connection requests in an associated TCP buffer called an accept queue:

Redis accepts up to one thousand connection requests per single event loop iteration. As a result, each client has its own connection socket — the one with which a TCP connection is established. This connection socket receives its client’s commands:

Each connected socket is also registered in an epoll instance for read events. When a client sends a command and it’s put in a connection socket’s receive queue, it means that a socket has just become readable and readQueryFromClient() is executed.

Event loop

The event loop represents a programming construct that builds upon a system’s multiplexing mechanism. Its essence lies in an infinite loop that continuously retrieves file descriptors whose state has undergone changes, indicating their readiness for read or write operations.

The event loop operates through a series of fundamental steps:

1. Initially, you register interest in I/O events for each relevant file descriptor. In the case of using an epoll as the multiplexing mechanism, it’s epoll_ctl() system call. This action, often referred to as subscribing to an event, signifies detecting a change in a file descriptor’s state. For example, when a client sends a request and it’s received by a connection socket, the socket’s state alters, signaling the presence of newly arrived data awaiting an application's reading.
2. Subsequently, you await I/O events on the registered file descriptors by invoking a blocking system call specific to the chosen multiplexing mechanism. In the case of an epoll mechanism, this involves utilizing the epoll_wait() procedure. The blocking system call can either wait indefinitely until at least one event occurs or specify a timeout duration.
3. Once the blocking system call from the previous step returns, you obtain the events that have transpired.
4. Following that, you identify the type of event, such as a read or write event, and handle it accordingly by executing the associated callback function, typically referred to as a handler in Redis.
5. Lastly, you continuously repeat these steps, perpetually monitoring and tracking the state of file descriptors asynchronously.

By adhering to this event loop pattern, developers can efficiently manage I/O operations and respond promptly to changes in file descriptor states.

Redis Receives a Command

That’s what readQueryFromClient() does. First, it checks whether a command should be parsed right away or should be postponed until IO threads do it. I’ll consider an IO threads scenario in the next article, so here, we have this mechanism disabled. Redis then reads a raw command data from a socket and stores it in a client’s query buffer. This is a piece of functionality involving a connection, and in such cases it’s implemented as a function pointer in ConnectionType struct. Here is an example of what a raw command data could look like if a client sent set a 12345:

*3 // this is a number of arguments
$3 // this is a length of the following lexeme -- a command, in this case
set // this is a command itself
$1 // this is a length of the first argument, in bytes
a
$5 // this is a length of the second argument, in bytes
12345;

This is a multi-bulk request format — a part of RESP, the default Redis protocol.

Then, Redis reads a client’s buffer and parses a command. All the heavy lifting is implemented in processMultibulkBuffer() procedure. It fills client’s argv field with parsed arguments. For instance, for the previous command, there are three of those: set, a, 12345.

Note that the first line of a multi-bulk command is always the number of arguments. Thus, Redis always knows whether an entire command was parsed. It might not be the case when, for example, a current command is really large, and it can’t fit within a single TCP segment. Or when a client sends multiple commands, and the last one, again, doesn’t make it in a TCP segment. And if epoll_wait() returns just before the second TCP segment arrives, and Redis gets a partial command.

It’s OK, though: the TCP stack of an underlying system will wait until it arrives, and Redis will find this out by calling epoll_wait() in the subsequent event loop iteration.

If an entire command is parsed, then Redis is ready to execute it. That’s what processCommandAndResetClient() does. Besides actually executing a command, it does some auxiliary bookkeeping stuff: resets client fields used for command parsing tracking, and updates some stats.

I will describe a command execution in one of my following articles.

Redis Writes a Response

Sending a reply to a client contains three logical parts:

1. Redis adds a client to a server.clients_pending_write list
2. Then, it constructs a reply in a specific format
3. This reply is stored in a client structure
4. In the subsequent event loop iteration, each pending reply is written asynchronously in a connection socket.

Now, let’s consider each part in more detail.

Redis reply is constructed

Reply formatting is implemented in an addReply* set of procedures located in networking.c file. It could be an addReplyBulk procedure, for instance. First, a reply length is added. It’s followed by a response body, and finally, by a new line.

For example, if a key a equals 12345, when a client gets it, the reply looks like that:

$5
123456
// this is a new line

Redis reply is stored in a client

Internally, this reply can be stored in a fixed-size buffer and, if it doesn’t fit there entirely, in a reply list. If a reply length is under 16 kB so that it fits in a reply buffer, it’s stored only in a buf field of a client struct. Otherwise, the remaining part is stored in a reply field. It is a linked list. If its current tail has some spare space, reply is appended to its buffer. After that, the remaining part is stored in a new list item which becomes the new tail. Its minimal size is 16 kB, and the maximum size is unbounded.

Why does Redis need this mechanism? Why can’t everything be stored in a dynamic-sized buffer? Its size can be increased and decreased with each new reply indeed. Well, I’m not a systems developer, but I can think of the following reasons:

1. Memory reallocation is not cheap, especially when applied on the Redis scale. For instance, you can have thousands of clients receiving responses at about the same time. It’s thousands of realloc-like procedures in a single event loop iteration. Given a very rough estimate of a single event loop iteration is about one millisecond (in reality, it can be two or even three orders of magnitude less), this can add up to millions of memory reallocations per second. This can affect Redis’ performance.
2. Frequent memory reallocations lead to memory fragmentation. Although Redis has a built-in way to mitigate it, it’s better to avoid it altogether.
3. Memory allocation and its subsequent freeing is cheaper than two reallocation calls. Each reallocation involves copying the existing data to a new memory block of a different size, which can have a time complexity of O(n), where n is the size of the data being reallocated. Meanwhile, free() procedure has a constant time complexity, typically O(1). It only releases the memory without any additional CPU or memory overhead.

So that’s why Redis uses a fixed-size 16 kB buffer which, on the one hand, is enough for most replies and, on the other, is not too much of an overhead.

Redis adds a client to a clients_pending_write list

Before setting a reply, Redis makes sure that a client is in a server.clients_pending_write list. This behavior is implemented in a prepareClientToWrite() procedure. Besides a few cases, Redis checks whether a client doesn’t have a stored reply (if it does, it means that this client is already in a pending write list), and it is currently not in an IO thread. If those two conditions are satisfied, putClientInPendingWriteQueue() is executed, which finally adds a client wrapped into a listNode in a server.clients_pending_write list.

Short recap

I think now it’s a good time to remind you of what a higher-level command execution looks like:

First, new events are received through epoll_wait() procedure. Then, they are looped through, and for each read event, a command is parsed, executed, and a reply is built. Note that it’s not yet sent to a client — it occurs on the subsequent event loop iteration in beforeSleep() procedure. Let’s get right into it.

Redis reply is sent to a client

This logic consists of two logical parts. The first one is where Redis sends a response. The second one is where Redis registers a connection socket for write events. This is needed when a response was sent only partially. It can occur when, for instance, a socket is blocked for writing because its send buffer is full.

This logic is implemented in a handleClientsWithPendingWritesUsingThreads() procedure. The name might trick you into thinking that IO threads are involved somehow; actually, this is not necessarily a case. IO threads machinery runs only if this behavior is enabled in settings and if Redis considers this whole enterprise worthwhile. If either of those conditions fail, responses are delivered in a the main thread. This logic is implemented in a handleClientsWithPendingWrites() procedure. Its implementation is quite straightforward. Redis takes all the clients with pending writes (as I’ve written above, they are stored in a server.clients_pending_write list) and calls writeToClient() for each one. As you can guess, this is a procedure that sends a response to a client.

Redis sends a response
writeToClient has a limit of how much data Redis can write to a socket. Why? There are specific scenarios where the likelihood of connection socket blocking is lower than the average. In such cases, Redis can spend too much time serving a response to a single client. Think of a user who connects to Redis through a loopback interface locally. I can hardly imagine network congestion there. Besides, the bandwidth is extremely high.

Another example might be when a client skips the TCP stack altogether and connects to Redis with Unix Domain Sockets. Despite their buffer capacity is generally lower, the data written in them is copied between processes. Thus, in both scenarios, it might take a while for connection sockets to block. Hence, Redis serves no more than NET_MAX_WRITES_PER_EVENT bytes for a client in each event loop iteration.

There are two procedures used for actual data writing. Ordinary write() is used for data stored in a c->buf buffer. It’s a contiguous block of memory, and the write procedure works with exactly this kind of data.

But for a reply list, writev() is used. Why? Because linked list occupies a non-contiguous memory region. And that’s exactly what writev is used for. Thus, Redis iterates through each item and constructs an array of scattered iovec structs. Then, it’s written atomically in a connection socket. So, if Redis had used a write procedure, it would have had two options. The first one is issuing several write calls, which is costly: generally, the fewer system calls, the better. The second option is to copy all reply list items’ contents into a single contiguous memory block and issue a single write. I don’t think the second option is subpar to a writev approach, though.

Each of those write procedures returns several bytes written, and if it’s zero, an errno is filled with an error code explaining what happened. Some of them indicate a permanent error; others are retryable. EAGAIN is among the latter. It means a connection socket’s send buffer is full, and writing gets blocked. In other words, as the comment goes, it’s Try again.

Redis subscribes to write events in a connection socket
Finally, Redis checks whether there is some data left for a current client to be sent. As I’ve already mentioned, there are at least two scenarios when this can occur. The first one is hitting a NET_MAX_WRITES_PER_EVENT limit, and the second one is an error code returned from a write procedure — most notably, an EAGAIN. In either case, Redis registers a connection socket for write events. It means that when it becomes writable, Redis will figure that out with an epoll_wait procedure and send the remaining part of a response with a previously set write handler.

It’s represented with a sendReplyToClient procedure. It boils down to simply calling a writeToClient() — an exact same procedure that was issued during the first attempt, in a handleClientsWithPendingWrites. The only difference is that the write handler is installed, as implied by the second argument. In this case, when all the data is finally sent, Redis unsubscribes from write events for a current connection socket.

Here is how response sending looks like when it can’t get sent in a single write call:

This is a very high-level view. Check out this Miro board for details.

In Closing

In short, an entire command execution flow looks like that. In the first event loop iteration, a command is parsed, executed, and a response is saved. In the subsequent iteration’s beforeSleep procedure, Redis sends this response to a client. If it’s sent only partially for some reason, Redis registers a current client’s connection socket for write events. When it fires, a socket becomes writable, and Redis writes the remaining part of a response. This process is repeated until an entire response is sent. When it’s done, Redis unsubscribes from write events.

Stay tuned. The next article is about how IO threads work.

Redis Internals: Client Sends a Command and Receives a Response was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

I’m continuing the Redis 7 internals series. First off, this article is much shorter than the previous one, where I delved into an implementation of Redis server startup. If you’re not one of the six percent of people who managed to read that article to the end (assuming the Medium stats page is correct, and I’m confident it is), don’t worry. I’ll provide enough context so you won’t have to finish that big boy.

Short Recap of Redis Server Start-Up

Here, I’ll walk through the concepts that the client connection process relies on.

Epoll instance

An epoll instance is a data structure in the Linux kernel that contains an interest list and a ready list. When a file descriptor is added to the interest list, also known as an epoll set, the epoll instance monitors it asynchronously for events. Events are changes in a file descriptor state. There are mainly two such changes. The first one is when a file descriptor has data available for reading. In other words, it becomes readable: its state has changed from not-ready to ready for reading. The second occurs when a file descriptor’s buffer has available space for writing. In this case, such file descriptors are usually referred to as writable. As soon as any of those events occurs, the epoll instance adds the file descriptor to the ready list:

To retrieve the file descriptors that are ready for I/O operations, you can call the epoll_wait() procedure.

Epoll is one of several so-called multiplexing mechanisms that allow tracking file descriptors’ state asynchronously. It’s used in Redis when it’s built on Linux. Other systems use other implementations of the same concept.

Here is a bit more detailed version.

Event loop

Event loop is a programming construct built on top of a system’s multiplexing mechanism. Essentially, it boils down to obtaining file descriptors whose state has changed in an infinite loop. That is, those file descriptors are ready either for writes or reads.

It works by following a set of basic steps:

1. First, you register interest in I/O events for each file descriptor using the appropriate system call. This is often referred to as subscribing to an event, which, as I’ve already mentioned, represents a change in the state of a file descriptor. For example, when a client connects to a listening socket, the state of the socket changes: it has a connection request waiting to be read and accepted by an application.
2. Next, you wait for I/O events on the registered file descriptors by blocking the system call that depends on your multiplexing mechanism. For an epoll mechanism, this is an epoll_wait() procedure. This can be either an indefinite wait until at least one event happens or a timeout can be specified.
3. Once a blocking system call from the previous step returns, you receive the events that have happened.
4. Then, you determine the type of event that occurred (e.g., read, write) and handle it appropriately by executing the associated callback function.
5. Finally, you repeat these steps to keep tracking the state of file descriptors asynchronously.

For event loop implementation details in Redis, you can refer to this section.

Listening sockets: user’s perspective

When Redis starts up, it creates listening sockets. They handle incoming connection requests. Redis can create TCP sockets when it’s connected to with TCP, and Unix Domain Sockets when it’s connected to locally. Each socket has an associated memory allocated by a Linux kernel. This memory is often referred to generally as a buffer. This is an umbrella term for all kinds of data structures used to store a TCP request until it’s processed. Typically, they all exhibit a queue-like behaviour. In case of connection requests, they are accepted from an accept queue:

When Redis accepts a connection request, another socket is created. It’s usually referred to as a connection socket:

From now on, it serves all client requests. I’m describing this in more detail in the main part of this post.

When listening sockets are created, Redis puts them in an epoll set for read events:

Thus, Redis checks whether there are new connection requests on each event loop iteration. If there are, Redis runs a specific procedure which I’ll consider soon.

Here you can find more details about overall connection lifecycle, reusable addresses, non-blocking sockets, and more. And here is a detailed description of what happens in the Linux TCP stack when a connection is established.

Redis Accepts a Connection Request

After a connection request is in a listening socket’s accept queue, it’s ready to be accepted by Redis.

On the next event loop iteration, Redis checks whether any of listening sockets are readable. If there are, then Redis executes a corresponding procedure. For reading listening sockets, that is, accepting a connection request, it’s a connSocketAcceptHandler(). First, it creates a connected socket, then it creates a connection and a client data structures associated with this socket, and puts a socket in an epoll set for read events. This procedure accepts up to 1000 connection requests from an accept queue in each event loop iteration. Here is what’s going on there on a higher level.

Now, let’s consider it in more detail.

Connection request accepting on a network level

This logic is implemented by the anetTcpAccept() procedure from an anet module. On Linux systems, a specific system call used for connection accepting is accept4(). It is similar to accept(), but with an additional flag argument that allows for various options to be set. Redis uses it to set an accepted socket as non-blocking automatically.

Briefly, here is what happens in the kernel. An entry point for connection request accepting is inet_accept procedure. All the heavy lifting is done in a protocol-specific accept() procedure, which in the case of TCP IPv4 proxies to inet_csk_accept(). It dequeues a head of an accept queue and returns it.

Connection data structure creation

That’s what connCreateAcceptedSocket() does. It sets a connection type to CT_Socket. It’s one of the implementations of the ConnectionType type which contains many connection-related procedures. Besides, the newly created connection structure has a connected socket descriptor and a CONN_STATE_ACCEPTING state:

Why is it still accepting? Despite a connected being accepted on a network level, it’s not yet ready to serve client requests because its connected socket is not yet registered in an epoll instance. I’m describing it in the next section.

Client structure creation

If the total number of connections doesn’t exceed a maxclients setting, a client structure is created. Besides initializing all of its fields, there are some operations carried out with a connected socket.

Let’s take a look at TCP protocol again.

The Nagle’s algorithm
When sending data over TCP, each packet has a certain amount of overhead, including metadata such as the TCP header, IP header, and likely Ethernet header. This metadata is necessary for the packet to be properly routed and processed by the receiving end.

For example, if the payload is just one byte, the total size of the packet will be much larger than one byte due to the overhead. Assuming an Ethernet header size of 14 bytes, an IP header size of 20 bytes, and a TCP header size of 20 bytes (that’s the minimum possible size; it can reach up to 60 bytes though), the total packet size would be 55 bytes. This means that sending many small packets can result in a significant amount of overhead, leading to decreased network performance. To mitigate this, the Nagle algorithm can be used.

It works like the following. Before sending a new TCP segment, the TCP stack checks if there is unacknowledged data. If there is any, the TCP stack waits until one of the following conditions is met:

1. It has accumulated enough data to fill a TCP segment. The maximum amount of data that can be sent in a single TCP segment is called Maximum Segment Size, or MSS for short:

2. Or, there is no unacknowledged data remaining. This means that all previously sent data has been acknowledged by the receiver.

In other words, Nagle’s algorithm causes delays in the transmission of small packets when there is unacknowledged in-flight data. This way, it can reduce the overall number of packets being transmitted, which, in turn, can reduce network congestion and improve performance. When a connection is first established, the algorithm is enabled by default.

Just to clarify, when an application sends a tcp request and there is no unacknowledged data, tcp packets are sent right away, even if their payload is just one byte:

The same way, if each tcp segment is filled to its maximum size, sending side doesn’t wait for an ack of previously sent data:

In some cases, however, the Nagle algorithm can be detrimental to performance. For example, in situations with a need for real-time or low-latency communication, the buffering and delay caused by the Nagle algorithm can be unacceptable. In such cases, disabling the Nagle algorithm and, hence, “synchronous” awaiting of packet acknowledgments in some scenarios, may be necessary to achieve optimal performance.

Delayed acknowledgment mechanism
Delayed acknowledgment is a feature in TCP that allows a receiver to delay sending acknowledgment packets for received data. Instead of sending an immediate ACK for each individual packet, the receiver can wait for one of the following outcomes:

1. Combining ACKs: The receiving host may wait to accumulate multiple ACKs before sending them together in a single packet:

This helps reduce the overhead of sending frequent small ACK packets and improves network efficiency.

2. Response-piggybacking ACK: the host may delay sending the ACK until it generates a response packet. The ACK can be included in the response packet, reducing the number of separate ACK packets:

3. Timeout: If no other packet or application response triggers the ACK, the host may eventually send an ACK after a certain timeout period. This timeout is typically around 200–500 milliseconds. It ensures that the sender eventually receives an ACK even if there is no immediate data or response to trigger it.

The purpose of delayed acknowledgment is to minimize network overhead and improve efficiency. By delaying the transmission of ACKs, the receiver can reduce the number of small control packets being sent, leading to better network utilization and reduced congestion. This can be beneficial in scenarios where a high volume of small data packets is exchanged, such as interactive applications. Although, John Nagle denies the benefits that this feature provides.

As I wrote earlier, Nagle’s algorithm may wait for an acknowledgment of a previously sent packet before sending the next one — for instance, in cases when data flow is not very intensive and packets can stay underfilled for quite some time. From the other hand, delayed acknowledgment mechanism delays acknowledgment sending which a sending host awaits. Hence, if a sending host has Nagle’s algorithm enabled (which is so by default in TCP), and a receiving host has the delayed acks feature enabled (which is also a default), two hosts may wait for each other. This situation is effectively a deadlock, which can be resolved only with a timeout. For example, consider this scenario:

That’s the reason why they don’t always play well together.

How Redis deals with it
Redis disables the Nagle algorithm by setting the TCP_NODELAY option on a connected socket using the setsockopt() system call. In other words, Redis instructs the operating system to send a response to a client as soon as it is available, no matter its size, and without waiting for an acknowledgment of previously sent response packets.

But Redis keeps the default delayed TCP acknowledgment feature. When a request sent to Redis doesn’t quite fit in a single TCP segment, the response can be delayed dramatically:

This can be eliminated by a TCP_QUICKACK option, but Redis doesn’t use it. But Camellia, Redis proxy by NetEase, supports this option.

Note that disabling Nagle’s algorithm on the Redis side does not affect a client's behaviour. Generally, when TCP_NODELAY is set only on a server side, clients will continue to buffer requests or wait for acknowledgment of previous packets. That’s why you should consider setting this option on the client side as well. For instance, that’s how the previous case looks like when Nagle’s algorithm is disabled on a sending side:

TCP keepalive
If a tcp-keepalive is specified, keepalive mechanism is enabled by Redis. TCP uses it to detect whether the other end of a connection is still alive and reachable. It does this by periodically sending small packets, or keepalive messages, to the other end and waiting for a response. The idea is to detect whether a connection has become idle or lost due to a network failure or an endpoint crash. In this case, OS closes a corresponding socket.

To enable keepalives, the SO_KEEPALIVE socket option must be set on a socket. This option tells the TCP stack to send keepalive messages on the socket periodically.

The frequency and number of keepalive messages sent are controlled by three TCP socket options: TCP_KEEPIDLE, TCP_KEEPINTVL, and TCP_KEEPCNT. TCP_KEEPIDLE specifies the time in seconds the connection must be idle before keepalive messages are sent. TCP_KEEPINTVL specifies the interval in seconds between subsequent keepalive messages. TCP_KEEPCNT specifies the number of keepalive messages that can be sent before the connection is considered broken.

For example, if TCP_KEEPIDLE is set to 60, TCP_KEEPINTVL is set to 10, and TCP_KEEPCNT is set to 5, then after 60 seconds of inactivity, the first keepalive message is sent. If no response is received within 10 seconds, a second message is sent, and so on, until 5 messages have been sent. If no response is received to these messages, the connection is considered broken, and the operational system closes a socket.

Connected socket registration in an epoll instance
Finally, a connected socket is registered for read events in an epoll instance. As any functionality related to connection, the procedure implementing this logic is defined in a ConnectionType. For a TCP connection, it’s connSocketSetReadHandler(). It adds a connection socket in an epoll set to monitor for read events and sets a procedure to be executed when new data arrives to readQueryFromClient(). It will be invoked with a single argument which is a current connection structure.

Finally, that’s what a client structure looks like:

Connection is accepted on the Redis level

Finally, connection is accepted on Redis land. This boils down to invoking a ConnectionType’s accept procedure, which in the case of TCP is resolved to connSocketAccept. There, connection state is set to CONN_STATE_CONNECTED. Now, a client can start sending commands and receive responses. As I’ve written at the end of the previous section, an entry point for all commands sent to Redis is a readQueryFromClient() procedure, which I’ll write about in the next article.

As usual, you can get a higher-level view here.

In closing

As promised, this is a much lighter article than the first one. It wasn’t such for me personally, though: while writing it, I published an article about TCP connection establishment internals and a retrospection about implementing a Radix tree for HTTP routing. I did my best to ensure this article didn’t lose its integrity, and I’m quite happy with where I landed. All in all, stay tuned. I’ll describe how Redis executes user commands in the next article.

Redis Internals: Client Connects to Redis by TCP was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

What is a Radix tree?

Wikipedia does a great job describing it already, but for the sake of this post to be autonomous, I’ll give a short informal description.

Suppose you have lots of string keys which point to some values. You need a data structure that allows to store and look them up. First option is a hash table: it’s the fastest way to look up the keys, but each key is a byte sequence of a fixed length. With a Radix tree, you can utilize the fact that some strings have a common prefix.

For instance, suppose you have three strings: vasya, vasily, and vasilevich. They correspond to the values of 1, 2, and 3. Those strings have a common prefix of vas. After it’s extracted, the last two strings have an il common prefix. Now imagine how much space you save when utilize this approach at scale, when you have billions of strings.

Internal nodes contain those common prefixes, and each prefix points either no the next internal node, or a leaf node with a value:

Radix tree is a great way to avoid O(n) complexity — where n is a number of routes. Instead, it becomes O(m), where m is a length of a searched key.

Why use Radix tree for route lookup?

First of all, there is nothing better than a hash table lookup: nothing beats O(1). But routes can have placeholders: /transactions/:id/refund, for instance, and this is the case I’m optimizing for in this post. If there are a couple of dozen million transactions, I need some persistent storage for storing all possible route values. Besides, I should write a logic for dynamically adding new routes as new transactions are created. But I don’t want to add an extra network hop for route lookup. So, I’m not taking this path.

I need a data structure which can be used locally and, hence, doesn’t take too much space. Besides, this structure should deal nicely with placeholders. And, finally, I want to avoid O(n) complexity. So, I think Radix tree is worth the try.

Visual overview of a Radix tree

First, I consider where I wanted to land. I make it visual, and I give no implementation details — hopefully, it can serve as a mental model and helps to build up heuristics. Then, I’ll proceed with ways to get there.

Keys with no placeholders

I’ve already given an example for this case in a “What is a Radix tree?” section. So let’s skip this part and move on to the next scenario.

Keys with placeholders

What if I want to add a key with a placeholder, for example, vasily/:id/hey with a value 1? I can’t think of a nice semantic way to form a static prefix out of a dynamic one. So I introduce a new entity — “internal node with a placeholder prefix”:

I think of it this way: if I can’t represent a dynamic prefix statically in a nice way, I’m left with the single option — not to represent it at all. This placeholder is hidden inside an Internal-node-with-a-placeholder-prefix-thing.

Now, let’s add another key to a radix tree above: vasily/:id/heyday, and its value is 2. In an innermost internal node, their common prefix is /hey. But what should I do with the first key? It ends with /hey, so the evident option is to add an empty string into the new innermost Internal node. To be honest, I don’t think it’s such a bad idea, but at the time of writing code I thought it would be more semantic to introduce a new entity called “Internal node with leaf node”. Here is how the result could look like:

And finally, let’s consider the last and most interesting case.

Keys with and without placeholders which conflict with each other

Now, what if I want to build a radix tree with two keys: vasily/:id/hey = 1 and vasily/hey/:id = 2? They contain a dynamic and a static prefix on the same positions, thus conflicting with each other. Why do I use a word “conflict”? Because placeholders and static keys can’t be represented at the same time in a single internal node. Hence, I need to introduce a new node — I called it a “Conflict-resolving node”. Basically, it contains two internal nodes: the first one with fixed, static prefixes, and the second one with placeholder prefix. Mind the leaf node corresponding to value 2. Its key ends with a placeholder, thus I represent this fact with a “Leaf node with a terminating placeholder” entity:

For me, the only sensible way of key lookup in this case is to first check the static key, and if there is no match, move on to placeholder node. Why? I think of a fixed key as a special case of a placeholder. It can come in handy when I decide to override a generic key with some special key. For instance, if I lookup a key vasily/hey/hey in an aforementioned tree, I will always end up with the vasily/hey/:id key.

Visual overview of Radix tree building

Let’s now consider the process of key adding. Here are the examples; they represent the same cases I outlined in the previous section, and contain some extra ones.

Keys with no placeholders

First example

Let’s add the first key — vasily. It’s quite straightforward. The resulting tree looks like that:

Now, let’s add a key vasya. Is there some prefix of this key which is already present in a tree? Yes, it’s vas:

Now, I need to turn a leaf node with key vasily into an internal node with a key vas:

Finally, I can add a key ya in an innermost internal node — the one corresponding to vas prefix:

We’re done. This is probably the simplest example, but it demonstrates important concepts which allow me to come up with a draft of a general higher-level solution for key adding. It goes like that, referencing the previous example:

1. Find the deepest internal node where to add a key. It’s the single internal node with the single key, vasily.
2. Then, find the left-hand common part. It’s vas. This leaves me with the key ya that I should add. But I don’t have a internal node where I can add it.
3. That means that I should split an existing key, using the common prefix, vas, as a key, so that I end up with an internal node.
4. Finally, I can add a key ya in a newly created internal node.

Second example

Now, let’s add the third key, vassal, in this tree. The common prefix is vas:

This key, vas, is already present in a tree. Let’s dive in further then, and cut the prefix off a key:

Great, empty common prefix is a condition indicating that it’s time to add a key in an internal node. An entire tree now looks like that:

At this point I can refine a general algorithm a bit:

1. Find the deepest internal node where I should a key, the suitable key in this node, and a common prefix. Do so recursively, diving deeper into a tree on each run.
2. If a common part is empty — great, add a key into an internal node.
3. If not, I should modify a tree’s structure prior to adding a key. Those modifications can take several forms. You’ve already seen the first one, where an existing key is split. I’ll describe some others in the examples below.
4. When it’s done, add a key.

Let’s consider some more examples.

Keys with placeholders

First example

Suppose we have a tree with a single key: vasily/:id/hey. It can be represented visually like this:

Now, let’s add a key vasily/:id/heyday. Following an algorithm I’ve outlined above, I end up with the following deepest internal node, along with the single suitable key:

Why is it suitable? Because it has a left-hand common part with a key to add:

Thus, I need to modify an existing structure so that I can add a key day later:

I’ve replaced a leaf node with an “internal node with a leaf node” entity. Internal-node-part is empty, while the previous leaf node migrated here. Now, everything is ready for adding the last suffix of an added key:

Second example

Now what if it’s the other way round: there is a vasily/:id/heyday key in a tree, and I want to add vasily/:id/hey? First, I’m going to split heyday into hey and day:

Then I’m ready to add a new key. But I’m adding it as a leaf of an internal-node-with-a-leaf entity which replaces an existing internal node:

This results into the same tree I arrived at in the previous example.

Keys with and without placeholders which conflict with each other

That’s the last case, and probably the most interesting one. Let’s consider we have a tree with a single key vasily/:id/hey. It looks like that:

Now I want to add a key vasily/hey/:id. Apparently, there is a conflict: prefix vasily/ is followed by an :id placeholder in the first key, and a static string hey in the second key. Hence, I run a structure-modifying step: wrap an existing node-with-placeholder-prefix with a conflict-resolving node, and pass an empty internal node where I will add a new key a few moments later:

And finally I add a new key in a previously created internal node. Now, the whole tree looks like the following:

You can find code implementing these concepts and building a radix tree here.

How to output a Radix tree as code

Now, what I need is effectively a memory dump of a tree into plain-text code. Besides, I want nice formatting reflecting my aesthetic preferences. This implementation boils down to traversing a tree: checking each node’s class and outputting a current node based on it. Its argument might be another node, so this whole procedure is recursive in nature. For example, our radix tree contains the following eight keys: /vasily/:lebov = 0, /vasilev/:anton/vasily/:belov = 1, /vasilev/:anton/anton/:petrovich/anton/:vasilyev = 2, /vasilev/baton/:vakhlakov/vakhlakov = 3, /vasilevs/:antons/tabakovs/:matskyavichus = 4, /vasile/:anton = 5, /vasily/belov = 6, /vasilev/baton/vakhlakov/:vakhlakov = 7. Its output looks like that:

new DefaultInternalNode(
    [6],
    [
        '/vasil' =>
            new DefaultInternalNode(
                [1, 2],
                [
                    'y/' =>
                        new DefaultConflictResolvingNode(
                            new DefaultInternalNode(
                                [5],
                                [
                                    'belov' => new DefaultLeafNode(6),
                                ]
                            ),
                            new LeafNodeWithTerminatingPlaceholder(0)
                        ),
                    'e' =>
                        new DefaultInternalNode(
                            [1],
                            [
                                'v' =>
                                    new DefaultInternalNode(
                                        [1, 2],
                                        [
                                            '/' =>
                                                new DefaultConflictResolvingNode(
                                                    new DefaultInternalNode(
                                                        [6],
                                                        [
                                                            'baton/' =>
                                                                new DefaultConflictResolvingNode(
                                                                    new DefaultInternalNode(
                                                                        [10],
                                                                        [
                                                                            'vakhlakov/' => new LeafNodeWithTerminatingPlaceholder(7),
                                                                        ]
                                                                    ),
                                                                    new InternalNodeWithPlaceholderPrefix(
                                                                        [10],
                                                                        [
                                                                            '/vakhlakov' => new DefaultLeafNode(3),
                                                                        ]
                                                                    )
                                                                ),
                                                        ]
                                                    ),
                                                    new InternalNodeWithPlaceholderPrefix(
                                                        [1],
                                                        [
                                                            '/' =>
                                                                new DefaultInternalNode(
                                                                    [6, 7],
                                                                    [
                                                                        'vasily/' => new LeafNodeWithTerminatingPlaceholder(1),
                                                                        'anton/' =>
                                                                            new InternalNodeWithPlaceholderPrefix(
                                                                                [7],
                                                                                [
                                                                                    '/anton/' => new LeafNodeWithTerminatingPlaceholder(2),
                                                                                ]
                                                                            ),
                                                                    ]
                                                                ),
                                                        ]
                                                    )
                                                ),
                                            's/' =>
                                                new InternalNodeWithPlaceholderPrefix(
                                                    [10],
                                                    [
                                                        '/tabakovs/' => new LeafNodeWithTerminatingPlaceholder(4),
                                                    ]
                                                ),
                                        ]
                                    ),
                                '/' => new LeafNodeWithTerminatingPlaceholder(5),
                            ]
                        ),
                ]
            ),
    ]
);

The first argument of each internal node is an array with key lengths, so that a key lookup logic always knows exactly how many symbols to cut off from an input string.

This radix tree has sped up route lookup tenfold, comparing to linear search. To be honest, I was expecting even more significant boost. So, since I’m elbow-deep in this enterprise already, why not combine this approach with the one Nikita Popov suggested back in 2014 — to collect all routes in a single regular expression?

How to output a Radix tree as a regular expression

What I need is just another class for representing a tree, this time in a form of a regular expression. Conceptually, it’s not that different from a memory-dump version. The most interesting part here is a way to map a found pattern to an original key. For example, I have the following regular expression: ^(a|b)$. There are two strings that match it: “a” and “b”. But, how do know which one matches in each case? Here is what the MARK verb does: it tags a path that a regexp engine has taken. Now, you can write the previous regular expression this way: ^(a(*:1)|b(*:2))$. Given you have a way to identify each match by a tag, you’re done. For instance, if you know in advance that tag 1 corresponds to a string a, and tag 2 corresponds to a string b, all you’re left to figure out is a way to get that tag. To do that, you can access a MARK key of an array you pass in the third argument of a preg_match procedure.

The route set from the previous section corresponds to this regular expression — in a readable form with tabs:

(?|/vasil
    (?|
    y/
        (?|
            (?|
            belov(*:6))|([^/]+)(*:0))|
    e
        (?|
        v
            (?|
            /
                (?|
                    (?|
                    baton/
                        (?|
                            (?|
                            vakhlakov/([^/]+)(*:7))|
                            ([^/]+)(?|/vakhlakov(*:3))))|
                    ([^/]+)(?|/
                        (?|
                        vasily/([^/]+)(*:1)|
                        anton/
                            ([^/]+)(?|/anton/([^/]+)(*:2)))))|
            s/
                ([^/]+)(?|/tabakovs/([^/]+)(*:4)))|
        /([^/]+)(*:5))))

Or, in a more compact form:

#(?|/vasil(?|y/(?|(?|belov(*:6))|([^/]+)(*:0))|e(?|v(?|/(?|(?|baton/(?|(?|vakhlakov/([^/]+)(*:7))|([^/]+)(?|/vakhlakov(*:3))))|([^/]+)(?|/(?|vasily/([^/]+)(*:1)|anton/([^/]+)(?|/anton/([^/]+)(*:2)))))|s/([^/]+)(?|/tabakovs/([^/]+)(*:4)))|/([^/]+)(*:5))))#

That’s more concise than a radix tree memory dump. Here is a regular expression for 69 highly-conflicting routes — pretty neat.

This optimization gave another whopping 20x boost to route lookup speed. Who knew regular expressions are that fast?! Crazy.

In Closing

It was fun for real implementing this logic. Being mostly a business applications developer, I don’t do such things very often. Route lookup speed increased two orders of magnitude, which saves us some CPUs. For a typical I/O-bound application with decent load, it’s not life-changing but noticeable still.

And, as it turned out, Symfony already has it this way! Kudos to Nicolas Grekas. I’ve never been a big fan of frameworks in general, but I always considered that people involved in Symfony ecosystem are brilliant.

While working on the Redis Internals series, I decided to take a quick look at TCP implementation in the latest commit of the Linux kernel master branch. Who knew it would be a week-long detour, but boy was it worth it!

Let’s get right into it.

Overview: the Three-Way Handshake and All of His Friends

Here, I start with the basics, and then narrow down my focus and proceed to a connection establishment specifically.

What is a TCP socket?

It’s just a programming construct used in the Linux kernel source code. It’s an abstraction over how Linux communicates with other hosts distributed over a network.

Client-server communication: a client’s view

When an application wants to exchange data with a server, first it should establish a connection. As a result, Linux kernel creates a socket containing all the information needed to send requests in a reliable way, and returns its id to an application. Then, an application can send a request using this socket. When it does so, an underlying Linux TCP stack temporarily saves this request in a socket; it’s actually sent over a network a few moments later. This process is referred to as “write in a socket”.

Client-server communication: a server’s view

A server must create at least one listening socket to be able to accept client connections. When a client sends a tcp connection request, server’s listening socket reads it and the Linux kernel creates a new socket, specifically for further data exchange with this client. This newly created socket is called a connection socket. A server application source code must have access to its identifier, or a descriptor — to be able to read a specific client’s requests and write it responses. In order to do that, a server accepts a connection request, issuing a specific command. When it’s done, a data exchange becomes possible.

When a server receives a request, server-side Linux TCP stack stores it in a socket until an application reads it. That’s why a process of receiving data is often called “reading from a socket”.

Connection establishment

The process of connection creation in TCP is called the three-way handshake. It has three stages. First, a client sends a SYN packet. Server receives it and creates a data structure typically referred to as a connection request, or mini socket. It has an information that the future connection socket will need, so it has to store it until a connection is fully established. After this, a server sends a confirmation that a syn packet was processed. It’s sent in a syn-ack packet. When a client receives it, it finally sends the last packet, an ack. Server Linux kernel then creates a connected socket waiting for a server application to obtain, or accept, it.

TCP segments, sequence numbers, and acknowledgements

TCP stack receives a stream of bytes and converts them into chunks known as TCP segments. It’s size is agreed upon during a connection establishment. It’s known as MSS: maximum segment size. This name is misleading: it denotes the maximum size of tcp segments’ payload that a current connection will use. That is, it excludes tcp and ip headers size. What’s important here, a sending part can suggest its own value in a syn packet, but ultimately it’s up to a receiving part what value to select. Generally, it doesn’t choose a value greater than what a client proposed. This value is then communicated back to a sending part in a syn-ack packet.

Each tcp segment contains a sequence number of the first byte of data in current segment, within a current connection. It’s called just a sequence number, for short. But it doesn’t start with zero. In this case, an attacker could guess it and send counterfeit packets. That’s why it’s chosen randomly by both sides during the three-way handshake. Each side generates its own sequence number, sends it to a counterpart, and waits for an acknowledgment:

When a host receives a sequence number generated by the other host, it simply increments it and sends back. Thus, sequence number validation is trivial for an original sender.

After a three-way handshake process completed successfully, data exchange looks like that:

Queues

When a syn packet arrives, server-side Linux kernel creates a connection request and saves it in a way historically referred to as a queue; you can stumble upon it elsewhere by the names of “half-open connection queue”, an “incomplete connection queue”, a “SYN queue”, “connection request queue”, or “request socket queue”. The last one owns its name to a structure which represents a connection request, a request_sock:

After an ack packet has arrived, connection request is removed from a connection request queue and a connection socket is created. It’s put in another queue which is known by a variety of names: accept queue, backlog queue, pending connection queue, or connection backlog. When a server application “accepts” a connection (using some command that boils down to an accept system call), it simply dequeues an existing socket from an accept queue.

You’ll see a more detailed explanation of this process below.

SYN-flood DDoS attack

What happens if lots of clients send a syn packet, but don’t send an ack packet? In previous Linux versions, half-open connections were added in an accept queue. This caused problems to legitimate connections, since an accept queue is home for not yet accepted connection sockets.

In newer Linux versions, there is a separate storage for connection requests. But server resources can get exhausted anyway — Linux kernel has to store all those connection requests until an ack packet arrives, which, in case this attack is carried out, never happens.

But there is a workaround.

Syncookies

Actually, almost all of the data a connection request contains can be obtained on an ack-processing step. An exception for this is an mss value sent by an initiating host: it sends it only in a syn packet. Frankly, I don’t think that there is some fundamental principle violated if an initiating host sends an mss in an ack packet. For me, it looks more of a TCP design flaw.

However, TCP does the following. When a receiving host processes a syn packet, it extracts an mss value, clamps it to a user-defined value if set, and encodes it in a sequence number which is sent back to a sending host in a syn-ack packet. Sending host acknowledges a syn-ack packet just the same way: it increments receiving host’s sequence number and sends it in an ack packet. Receiving host extracts an mss value from it and calculates a final result.

This mechanism can be either totally disabled, or enabled only when a connection request queue is full, or always used, regardless of connection request queue state.

Now, let’s dive into the source code.

The Three-Way Handshake with no Syncookies

First, here is an image again of what a three-way handshake looks like when syncookies are not used:

Let’s consider it step by step.

Receiving host receives a syn packet

When a client initiates a 3wh, it sends a syn packet to the server. There,
the TCP layer’s entrypoint is a tcp_v4_rcv procedure. When a packet is received, a listening socket is looked up. If it’s found, its state is TCP_LISTEN. Through a tcp_v4_do_rcv() helper procedure, we reach tcp_rcv_state_process(). This procedure is effectively a state machine applied to a socket that processes a current packet: it first checks a socket state, then runs some logic based on it, and advances the state accordingly. There, I fall into a clause indicating that it’s a syn packet processing stage. Then, through a tcp_v4_conn_request() procedure, I find myself in tcp_conn_request(). I’m interested in a case when syncookies are not used, but normal operation is possible. This boils down to a single case when syncookies are either disabled or have a default value of 1, and a request socket queue is not full (and given a listening socket is not in a TIME_WAIT state).

As a side note, when tcp_syncookies is 2, then syncookies are always used, even when request socket queue is not full.

A request socket is created. As I mentioned above, request socket is not a full-blown connection socket used for data exchanging, instead it’s a connection request, or a mini socket — as it’s typically referred to in Linux source code. Its ireq_state is TCP_NEW_SYN_RECV, a listener socket is attached to it and a syn packet saved. Finally, a request_sock is cast to a sock struct and is added in a “queue”. Well, actually it’s not a queue. It’s a mechanism consisting of two parts:

1. a hash-table, usually referred to as an ehash, which is used for socket lookups;
2. and, however crazy, an accept queue tracking its length through the qlen field. To make things more confusing, an accept queue is represented as a struct with a request_sock_queue name.

This “queue” is often referred to as a half-open connection queue, or a SYN queue — as I mentioned above. Here we can see its length incrementing when a new connection request is added.

And finally, a syn-ack is sent.

So, for now, no socket is created. Only a mini socket is created, which is a request_sock struct disguised as a normal socket represented as a sock structure.

Receiving host receives an ack packet

As during a syn packet processing step, a socket is looked up. In an __inet_lookup procedure, __inet_lookup_established is issued first. It looks up a socket in an ehash. And there is one indeed — a temporary request_sock cast to a sock struct which was added during a syn packet processing stage. Its state is still TCP_NEW_SYN_RECV, so we fall through a sk->sk_state == TCP_NEW_SYN_RECV clause. Then, a tcp_check_req invoked there creates a child socket by cloning a listening socket. This newly created socket is in a TCP_SYN_RECV state. It’s added in an ehash, so __inet_lookup_skb will find it when a client starts exchanging data. Right after this normal socket was added, a mini socket is removed from an ehash — it’s not needed there anymore.

Then, a socket is added in a tail of an accept queue and its length incremented. From an implementation point of view, it’s not a socket actually. Instead, it’s the same request_sock created on a syn stage, but it now stores a child socket created earlier. It’s a funny asymmetry: request queue conceptually has connection requests, although technically it contains sockets (not to mention it’s not a queue whatsoever), while an accept queue conceptually contains sockets, although technically it consists of connection requests. The length of an accept queue is tracked through a sk_ack_backlog field of a listening socket.

Finally, a tcp_child_process is called. It calls an already familiar tcp_rcv_state_process, but this time for a newly created socket. Its state is TCP_SYN_RECV, and it’s set to TCP_ESTABLISHED. It’s worth noting that each socket arriving in an accept queue is in an TCP_SYN_RECV state; it becomes established a few moments later.

The Three-Way Handshake with Syncookies

I won’t delve into the same level of detail as in a previous section — much of an implementation remains the same. I only highlight the differences between a scenario when syncookies are used and when they’re not.

First, here is a flow:

Receiving host receives a syn packet

As on a previous step, tcp_rcv_state_process is invoked through tcp_v4_rcv entrypoint and tcp_v4_do_rcv helper. There, in a tcp_conn_request procedure, we read sysctl_tcp_syncookies setting. It’s 1 by default. Syncookies mechanism is used if it’s 2 or if a connection queue is full, given a listening socket is not in a TIME_WAIT state, namely a tcp_tw_isn field is empty.

Then, a syncookie is generated. In case of tcp, cookie_v4_init_sequence procedure does that. Syncookie is a sum of the following values:

1. two hashes of addresses and ports of a source and a destination;
2. Linux internal representation of current time;
3. a clamped mss value and a sequence number sent by an initiating host.

Then it’s all sent to a client in a seq field of a syn-ack packet.

Although a request socket was created as part of an implementation, it’s not put in a connection request queue. Instead, it’s disposed of.

Receiving host receives an ack packet

As always, everything starts with a tcp_v4_rcv procedure. Since there is no connection request in an ehash, only a listening socket can be found. It’s in a TCP_LISTEN state, so we find ourselves in tcp_v4_do_rcv. There, a syncookies mechanics it started. First, a syncookie value is validated:

1. It’s checked that a syncookie must be less than 120 seconds old;
2. Then, an mss value is extracted and returned. If this value is in a range from 0 to 3, then syncookie is considered valid.

If everything is ok, then a socket is created. More precisely, it’s achieved with tcp_v4_syn_recv_sock procedure — the same one used when syncookie is disabled. This socket ends up in an accept queue the same way either. For now, it’s still in an TCP_SYN_RECV state.

The three-way handshake completes similar to the previous section — with tcp_child_process procedure invoked for a child socket.

In closing

So that’s about it. This topic is extensive indeed, I have highlighted only those details that were of particular interest to me. Hopefully, there will be some more posts about intricacies of TCP implementation.

UPD: an original version of this post contained a mistake in a syncookies explanation. Thanks to the noble and benevolent Hacker News souls who pointed it out — in a kind and gentle manner that we all lack in the darker places of the Internet.

Level Up Coding

Thanks for being a part of our community! Before you go:

• 👏 Clap for the story and follow the author 👉
• 📰 View more content in the Level Up Coding publication
• 💰 Free coding interview course ⇒ View Course
• 🧠 AI Tools ⇒ View Now

🔔 Follow us: Twitter | LinkedIn | Newsletter

🚀👉 Join the Level Up talent collective and find an amazing job

Deep-Dive into TCP Connection Establishment Process was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.

What this is all about

Recently I decided to have a look at Redis source code. At that time, I couldn’t think that it will get me hooked for a good couple of months, so I wasn’t really too much picky about choosing any specific version. I just cloned current dev branch. It’s stable — I mean, the code works, tests pass, but this is a work in progress: probably that’s the reason why the branch name is, uhm, “unstable”. However, everything covered here applies to Redis 7, except some lower-level details. More specifically, the commit I’m referring to throughout this series is ahead of Redis 7.0.X versions, and is part of recently released Redis 7.2.0 version. Oddly enough, there is no such thing as Redis 7.1.

What is covered, and what is not

My primary purpose is to give a higher-level overview of how Redis works — that’s I think the most important part when diving into a new codebase. Being a business applications developer by day, I had absolutely no idea how such kind of systems work internally. And that’s the overview that I personally wish I had when I started this endeavor.

Besides a higher-level overview, there are some parts that I’ve found particularly interesting. I’m describing those too. But there are way more interesting things that I’m not diving into here. However, having an overall picture, it won’t be much of a trouble to do oneself.

Originally, this overview was in a half-visual-half-textual form in this Miro board. Current series is, at least to some extent, a complementary afterthought. Comparing those two, I think that the Miro version allows to see better a bigger picture, and by its very nature it’s more visual. While accompanying posts makes an effort of explaining some parts in more depth.

Scenarios

I think that the best way to describe how the system works is through user stories. As a side note, no wonder that I also think that the best way to decompose any new feature is through writing and discussing user stories as well. Moreover, I prefer to discuss them through specific examples which might serve as BDD-style tests. That’s what I’ve tried to apply here. There are several specific scenarios I consider, some are small, some are large. Within these scenarios, when applicable, I’ve tried to describe lower-level functionality by a concrete example.

The initial post delves into the processes set in motion when Redis initiates. This piece is quite substantial, and understandably so, given the multitude of activities transpiring during this phase. Redis establishes listening sockets, initializes background threads and threaded I/O machinery, and finally throws a party with an event loop — essentially the heartbeat of Redis. Alongside the execution of client commands, it manages various cyclic tasks: client eviction, key expiration, defragmentation, maintenance procedures for hash tables like resizing and rehashing, as well as data persistence.

The following post outlines the way Redis accepts client connections. There I examine the intricacies of listening sockets, their configuration, and how they generally function. If you get fascinated by this whole network-thing, you might also like delving directly into the implementation of TCP connection establishment within the Linux TCP stack.

The next post explores the process in which Redis reads and parses a command, assembles a response, and transfers it into a socket. Furthermore, I delve into how Redis manages responses based on their size, detailing its approach to handling different reply sizes.

The fourth post takes a lot of cues from the previous one and zooms in on threaded I/O. It’s a deep dive into I/O threads — what they are, when they come in handy, and how they’re put into action. I’m also digging into five back-to-back event loop iterations to describe in detail how I/O threads jump in and out of the game.

Lastly, I’m going to detail how Redis goes about carrying out a command. In that section, I’ll guide you through the primary data structures that Redis leans on for storing data. Then, I’ll dive into the necessary maintenance procedures that kick in with every command. This will include revisiting hash table resizing and rehashing, plus breaking down the nitty-gritty of key eviction. To wrap things up, I’ll sketch out the general steps that a command execution follows.

Redis 7 Internals Series: Redis server starts in standalone mode

This is the first post in the Redis 7 Internals Series. You can find this scenario here. Read it left to right; that’s the order in which each logic block is executed while the Redis server starts.

Everything starts with a main() procedure in the server.c file. There are several major parts there.

Config Initialization

It can be roughly divided into two stages. The first is initializing default config values hard-coded in the Redis source code. This logic is implemented in an initServerConfig() procedure. The second one is reading a config file and overwriting default settings; you can find it in a loadServerConfig() procedure.

initServerConfig()

There is a standardConfig static_configs[] variable defined in config.c file. Each standardConfig struct has, among others, a default value for a setting it defines and an address of a redisServer field that stores this value. For example, one of the static_config[] elements goes like this:

createBoolConfig("appendonly", NULL, MODIFIABLE_CONFIG | DENY_LOADING_CONFIG, server.aof_enabled, 0, NULL, updateAppendonly)

It means that the default value for server.aof_enabled is set to 0. Default config values are set in a initConfigValues() procedure. There, for each standardConfig struct defined in static_configs array, config->interface.init(config) is called. interface field is a typeInterface struct, which mainly deals with getting and setting data of a specific type. For example, for boolean config, init procedure is set to boolConfigInit — you can see that in a createBoolConfig macros which initializes a standardConfig struct:

#define createBoolConfig(name, alias, flags, config_addr, default, is_valid, apply) { \
    embedCommonConfig(name, alias, flags) \
    embedConfigInterface(boolConfigInit, boolConfigSet, boolConfigGet, boolConfigRewrite, apply) \
    .type = BOOL_CONFIG, \
    .data.yesno = { \
        .config = &(config_addr), \
        .default_value = (default), \
        .is_valid_fn = (is_valid), \
    } \
}

Besides, each standardConfig is added in a dictionary, that is, a hash table — so that a config name can find any item in constant time. It is represented as a dict struct in Redis.

You can check out a more concise Miro version here.

loadServerConfig()

Here, each setting provided in redis.conf, is read and set with the typeInterface’s set procedure. Thus, default values are overwritten.

All data manipulation procedures for each typeInterface implementation are defined in config.c.

Listening Sockets Creation

Pair this description with visuals.

connTypeInitialize()

It starts with ConnectionType initialization. This struct contains procedures that are related to a connection and specific to an underlying socket type. It has procedures both for a client and a server. Among other things, they connect to an endpoint, create a listening socket bound to a specific address, accept connections, write data to a client socket, read data from a listening or connection socket, and shut down a connection.

So, for now, initialization simply means that a static ConnectionType *connTypes[CONN_TYPE_MAX] is filled with connection types for TCP sockets, Unix domain sockets, and, if Redis was compiled with BUILD_TLS=yes, for tls (which in Redis can be used only with TCP sockets).

initListeners()

Two main things happen here. First, listening sockets are created, and second, their file descriptors are added in an epoll set. Let’s now go through everything in order.

Overall lifecycle of a network application
When clients send connection requests, they first create a socket on their side. After that, they send a connection request which boils down to connect() system call. To accept connection requests, the server side must have listening sockets. Each socket has some allocated memory for a queue which temporarily stores incoming client connection requests:

Each accept() system call issued against a listening socket extracts the first connection request and creates a new connected socket. This socket will be used to communicate with a specific client that made this connection request. This recently created connection socket will handle the next command the client sends. Here’s what the flow looks like:

When either server or client wants to terminate their connection, one of them first issues the shutdown() system call. It disables sending or receiving data on the specified socket so any pending requests can be handled. After that, the socket is closed, which removes the underlying file descriptor and releases its resources.

So, for now, listening sockets are created. In the case of TCP, this logic is implemented in a listenToPort() procedure. Binding and listening specifically are made in an anetListen() procedure.

Two more things worth noting. First, addresses that sockets are bound to are set as reusable. Second, created sockets are made non-blocking, but what does this mean?

Reusable addresses
If the address is not reusable, which is the default setting, only one socket can be bound with it. Otherwise, more than one address can be bound to it, and OS automatically distributes incoming requests to different sockets. Here’s what the flow looks like:

It’s useful when you want to restart a server quickly, but your operating system thinks that the address is still used by some socket, which, in the case of Redis, is not the case: it binds an address to a single socket. So that’s the way to avoid this situation. The address is made reusable in a anetSetReuseAddr() procedure.

Non-blocking sockets
When you read data from an ordinary blocking socket, and there is none available, the read() system call will hang — or block — until data becomes available. It’s not a busy-wait, that is, your CPU is not utilized, but further code execution just doesn’t happen. In the case of non-blocking sockets, a special code is returned instead: it means that there is no data to be read right now. Thus, your thread doesn’t hang, but your code should be ready for this scenario.

The same thing applies for the write() system call. But how can writing be blocked? First, this is what writing in a socket looks like.

When you issue a write() system call, you don’t actually write into the underlying file descriptor. It’s not like writing in a file. Moreover, there is no file at all. Instead, there is a file descriptor, which is just an entry in a file descriptor table maintained by a kernel for each process, and some kernel memory associated with it is called a buffer. I wrote about it earlier.

That’s where the kernel actually writes your data. What happens if you write a message that doesn’t fit into a buffer? If it’s a blocking socket, your write() system call hangs. When a kernel finally releases some memory, and your message fits in the buffer, the write() call still hangs. It waits until this message is delivered to a recipient. And since TCP has no upper bound for when exactly a message is delivered, your app can hang indefinitely.

Now, if I write to a non-blocking socket and a message doesn’t fit in a buffer entirely, only a part of a message is written, and a special code is returned. Your app should be ready to resume writing when the buffer is ready. And this brings us to an epoll instance.

epoll instance
Epoll instance is a Linux kernel data structure that consists of two lists: an interest list and a ready list. When you want to know that some file descriptor has some data to be read or it is ready for writing, you can add a file descriptor to an interest list, which is also called an epoll set. The epoll instance asynchronously tracks the state of the registered file descriptors and adds them to a ready list as soon as they become ready for I/O operations. You can get a ready list by calling an epoll_wait() procedure.

Each epoll set item is called an epoll event, which might sound misleading. Usually, when there is an “event,” it’s already happened. You can subscribe to events; after some time, they happen, and you can somehow get that event. That’s what happens in the case of an epoll set as well, but an epoll_event is probably an unfortunate name for an interest list item.

You do the following when you subscribe to read or write events for your file descriptors. First, you create an epoll_event struct. Then, you specify what exactly you’re interested in. If you subscribe to read events, it goes like epoll_event.events |= EPOLLIN. And finally, you specify a file descriptor you’re interested in: epoll_even.data.fd = my_fd;.

In Redis, epoll logic is implemented in ae_epoll.c file. To get events that actually happened since the last time you checked, you can call epoll_wait.

Event handlers
How does Redis know which procedure to run when a specific event occurred? It keeps event handlers in an aeEventLoop struct’s aeFileEvent *events array. Its name seems misleading a bit; it should’ve been handlers I think. Array indices are file descriptors, so Redis can quickly find a correct handler. If you’re subscribing to read events, you want to set a read handler which is stored aeFileProc *rfileProc field, and if to write events, then you set a handler in a aeFileProc *wfileProc.

aeCreateFileEvent is a procedure which subscribes to specific events and sets corresponding handlers.

Quick Recap
So, in short, you subscribe to read or write events for your file descriptors, and then you check their state. If you do so periodically in an infinite loop, this whole mechanism is called an event loop. And that’s exactly what happens with listening sockets. Redis puts them in an epoll set, subscribes to read events, and sets aeFileProc *rfileProc field to ConnectionType.accept_handler, which is connSocketAcceptHandler in case of TCP connection. After that, Redis periodically checks whether those socket descriptors have pending client connections. When there are, Redis accepts them. There will be a separate post about it. For now, you can check this diagram.

Background I/O Initialization

There are some system calls that can block for quite some time. Most notably, it’s fsync, which actually moves data from OS memory pages to a storage device. Besides, if a large amount of memory has been allocated using malloc() and free() is called on it, the operating system may need to perform some behind-the-scenes operations, such as defragmentation of memory, which can take a significant amount of time and cause the free() call to block.

That’s why Redis doesn’t run operations that employ those calls in the main thread. Instead, it utilizes special background threads — one thread per job type, three threads in total. In a source code, they are often referred to as bio threads, where “bio” stands for background I/O, although free has nothing to do with I/O. There are four job types:

enum {
    BIO_CLOSE_FILE = 0, /* Deferred close(2) syscall. */
    BIO_AOF_FSYNC,      /* Deferred AOF fsync. */
    BIO_LAZY_FREE,      /* Deferred objects freeing. */
    BIO_CLOSE_AOF,      /* Deferred close for AOF files. */
    BIO_NUM_OPS
};

File closing is not a blocking call usually, and it returns most of the time immediately. But there are some obscure cases when it can block, and what’s worse, this behavior varies across systems. So generally, closing file descriptors in the background is a good practice. Moreover, in Redis, this is done with a prior fsync call, which is relatively costly.

Each thread runs bioProcessBackgroundJobs procedure. If the bio_cpulist setting is specified, it’s applied here with redisSetCpuAffinity procedure. It boils down to sched_setaffinity system call. Effectively, you specify a set of CPUs for those threads to run on. This can reduce the overhead of context switching, cache invalidation, and other CPU-related tasks, leading to faster execution times and improved performance.

Then, an infinite loop processes a job list specific to this thread. If it’s empty, the thread waits for a signal notifying about the new job and hangs:

if (listLength(bio_jobs[worker]) == 0) {
    pthread_cond_wait(&bio_newjob_cond[worker], &bio_mutex[worker]);
    continue;
}

If it’s not, Redis gets the first element from bio_jobs[worker] list and processes it.

bioSubmitJob is a procedure used to add a job for a background execution.

Threaded I/O

Redis is usually claimed to be single-threaded. That doesn’t mean that Redis has a single main thread for everything. As you’ve already seen in a previous part, there are background threads, for instance. Moreover, Redis forks child processes sometimes. So, what it actually means, instead, is that all client commands are handled by a single main thread on a data storage level.

For instance, if you have ten thousand simultaneously connected clients, and all of them issue a SET command against the same key at just the same moment of time; it means that Redis will set this key with a specified value ten thousand times, one by one, one at a time, in total isolation from each other, in the single main thread.

But this fact nevertheless leaves some space for optimization in specific scenarios. The primary scenario that is being targeted is as follows. If you have lots of clients connected at the same time, and they issue commands that have large responses, it might take some time to iterate all those clients and, for each of them, issue a write() system call.

This command copies data from Redis, which resides in user space, to a TCP buffer, which is in kernel space. So, first, it’s inherently slow because of this boundary crossing, and second, the larger response, the more time it takes to copy it. And Redis came up with a solution targeting this issue: it can write responses in threads running in parallel. Those threads are usually referred to as io threads. The number of threads can be set with io-threads setting.

The second scenario is conceptually the same, but it targets command parsing. Since it’s less typical for clients to have a large request body, this case is even rarer. This behavior is controlled by a separate setting, io-threads-do-reads.

I/O threads implementation is considered in more detail in this diagram. Threads are started in initThreadedIO() procedure. IOThreadMain is a procedure that runs in each thread.

A couple of notes about implementation: First, how does Redis understand that there are some responses to write or some incoming requests to parse? It checks getIOPendingCount procedure that returns several items to be processed by a thread whose id is passed as an argument. Second, how does Redis know exactly what it should do — send a response or parse a command? A global static variable defines it, io_threads_op. Here’s how to use this variable:

if (io_threads_op == IO_THREADS_OP_WRITE) {
    writeToClient(c,0);
} else if (io_threads_op == IO_THREADS_OP_READ) {
    readQueryFromClient(c->conn);
}

In the case of writing responses to clients, both thread operation and pending responses count are set synchronously in handleClientsWithPendingWritesUsingThreads. Reads are done in handleClientsWithPendingReadsUsingThreads.

Last but not least, it might seem that I/O threads are busy-waiting when there is nothing to do for them. Here’s the code:

for (int j = 0; j < 1000000; j++) {
    if (getIOPendingCount(id) != 0) break;
}
/* Give the main thread a chance to stop this thread. */
if (getIOPendingCount(id) == 0) {
    pthread_mutex_lock(&io_threads_mutex[id]);
    pthread_mutex_unlock(&io_threads_mutex[id]);
    continue;
}

They’re not, actually. Their state is controlled by locking corresponding mutexes, io_threads_mutex[id] — you can see that in a comment that goes like Give the main thread a chance to stop this thread. Initially, they are locked by the main thread. When Redis decides that there are enough clients to justify their processing with I/O threads, it unlocks their mutexes in a startThreadedIO() procedure. And when active clients quantity decreases, Redis simply acquires a lock again in a stopThreadedIO() procedure. That leads to I/O threads hanging when they try to lock already locked mutex.

I’ll write a separate post about how the whole client request handling is done with I/O threads. For now, you can head over to this Miro diagram.

Load Client Data From Disk Into Memory

First, here’s a quick overview of what persistence looks like in Redis.

Two persistence options in Redis

The first one is generating a data snapshot, all Redis data in a single binary file. This file is called an RDB file, and this whole mechanism is usually referred to as RDB, which stands for Redis database. The filename can be configured with a dbfilename setting.

The second one is logging all mutating commands in a human-readable format — the same one used in the Redis protocol. All files created by Redis when this option is used are collectively called AOF files, which stands for append-only file. You can enable this option with the appendonly setting. The specific implementation of an underlying mechanism changes across different Redis versions.

AOF in Redis 7

In Redis 7, the AOF mechanism was reworked significantly. It employs two types of files for storing client data.

The first one is a base file. It’s a snapshot of an entire Redis instance dataset. Its format depends on aof-use-rdb-preamble setting. If it’s on, the base file has raw binary data. In this case, the base file is no different from an RDB file. If it’s off, the base file contains data as a compacted list of commands.

For instance, if some client has set a specific key with different values a hundred times, only the last actual command will end up in a base file. The same applies to other data structures. If a client appended a hundred values to a list of one item per command, the base file will contain a single RPUSH command with a hundred arguments.

The second type is an increment file, or, for short, an incr file. That’s where all the currently run mutating commands are written. They are stored as is.

When the Redis server starts, it checks a config for a currently-used persistence mechanism and loads a corresponding file. In the case of AOF, it first loads a base file and then an incr file.

As new data is being written in storage, the current incr file requires rotation, so it wouldn’t grow indefinitely. This rotation process, usually referred to as AOF rewrite, runs periodically. Instead of overwriting existing files, new ones are created. In short, it goes like this. First, a new incr file is created. All the current commands are written in this new file now. After that, a new snapshot is taken. When it’s completed, previous versions of a base file and an incr file are deleted. I describe this process in more detail here, and I’ll write about it a bit later.

Now, let’s consider the loading part. As usual, you can find it in a diagram here.

Implementation of AOF files loading into memory

As I’ve written earlier, two types of files store client data. They can have several versions at once, so they have to be tracked somehow. That’s what a manifest file serves for. It stores currently active versions of a base file and incr files, along with their previous, historical, versions that will be deleted soon. If appendfilename setting equals my_appendonly_file, a manifest file can look like that:

# this is a base file, type "b" for "base" 
file my_appendonly_file.aof.2.base.aof seq 2 type b

# This is a previous version of a base file, mind ".base" prefix in a filename.
# Type h means "historical"
file my_appendonly_file.aof.1.base.aof seq 1 type h

# this is a previous version of an incr file. Mind ".incr" prefix.
file my_appendonly_file.aof.1.incr.aof seq 1 type h

# this is a currently active incr file. All current commands are written here
file my_appendonly_file.aof.2.incr.aof seq 2 type i

The AOF rewrite process starts with loading this manifest file into memory, namely in an aofManifest struct. Here’s what that looks like:

typedef struct {
  aofInfo     *base_aof_info;       /* BASE file information. NULL if there is no BASE file. */
  list        *incr_aof_list;       /* INCR AOFs list. We may have multiple INCR AOF when rewrite fails. */
  list        *history_aof_list;    /* HISTORY AOF list. When the AOFRW success, The aofInfo contained
              in `base_aof_info` and `incr_aof_list` will be moved to this list.
              We will delete these AOF files when AOFRW finish. */
  long long   curr_base_file_seq;   /* The sequence number used by the current BASE file. */
  long long   curr_incr_file_seq;   /* The sequence number used by the current INCR file. */
  int         dirty;                /* 1 Indicates that the aofManifest in the memory is inconsistent with
                                         disk, we need to persist it immediately. */
} aofManifest;

This is done in a aofLoadManifestFromDisk() procedure.

Then, client data is loaded. First, Redis checks which persistence mechanism is currently used. If AOF is disabled, then it loads an RDB snapshot. Otherwise, AOF files are loaded: first, a base file, and second, all the incr files. Usually, there is a single incr file. But if a previous AOF rewrite process is completed with an error, Redis can have more than one incr file. Incoming commands are written in a single incr file at any given time.

Important consequence: if you’ve been using only RDB mechanism, when you stop Redis, then enable AOF, and then start your instance, your data from an RDB file will not be loaded. Like almost any setting in Redis, you can switch AOF on the fly: CONFIG SET appendonly yes.

loadSingleAppendOnlyFile() is a procedure that loads an AOF file. It has a back-compatibility check, so this procedure can work with files created in previous Redis versions. Earlier, if aof-use-rdb-preamblewas on, an AOF file contained a so-called preamble. It was just an initial Redis dataset in a binary format, no different from an RDB snapshot. So, if Redis starts for the first time after an upgrade, this procedure first reads this preamble if it’s present, and then it goes on with a so-called AOF tail. In Redis 7, a base file can contain either raw binary data or a compacted list of commands, not both.

When data is loaded, Redis opens an incr file from a manifest so it is ready for writing client commands. If it’s the first Redis 7 start, neither a base nor an incr file exists. In this case, they’re created, and a manifest file is updated.

Finally, if history files are left after the last AOF rewrite, Redis deletes them now, in a aofDelHistoryFiles() procedure. Like any file deletion in Redis, this is done asynchronously in a bio thread.

Event Loop

Overview

I’ve already mentioned an event loop concept when I talked about an epoll set. But epoll mechanism is an implementation detail of an event loop, which is, in and of itself, just an abstract concept. It is a programming construct that enables a program to efficiently handle multiple input/output operations without blocking or wasting CPU cycles. Typical cases are network I/O and file I/O. What powers any event loop is a specific multiplexing mechanism. A concrete kernel implementation tracks registered file descriptors and reports their state when you ask. Epoll is one of those implementations, the latest and the most performant one. It’s now used in Redis when it’s built on Linux systems.

Regardless of an implementation mechanism, an event loop has these basic steps:

1. Register interest in I/O events for each file descriptor using the appropriate system call. In other words, you subscribe to an event. I/O event is basically a change in the state of a file descriptor. For instance, if you have a listening socket and some client connects to an address bound with it, the state of this socket changes: now it has a connection request in its TCP buffer, waiting to be read and accepted.
2. Wait for I/O events on the registered file descriptors by blocking the system call depending on your multiplexing mechanism. You can wait indefinitely until at least one event happens or with some timeout.
3. When a blocking system call from a previous step returns, you get events that have happened so far.
4. Determine the type of event that occurred (read, write, etc.) and handle it appropriately by executing the associated callback function.
5. Repeat.

Event loop with an epoll mechanism

First, Redis creates a so-called epoll instance: epoll_create(1024);. This system call effectively creates a container for an epoll set and a ready list and returns a file descriptor associated with it. In early Linux versions, its single argument hinted to the kernel about what size it should expect an epoll set to be. But now it is ignored. To start tracking the state of a file descriptor, you issue an epoll_ctl system call. Besides adding an item in an epoll set, this procedure can also modify and remove it. And when you want to get all events that happened to registered file descriptors, you call epoll_wait.

Event loop in Redis

I’ve built, installed, and run Redis on Linux, so I’ll refer to an epoll as a multiplexing mechanism. As usual, you can combine reading this text with this diagram.

First, an epoll instance is created inaeApiCreate procedure, which is called during event loop initialization in aeCreateEventLoop. To track some file descriptor’s state, you can call aeApiAddEvent(). aeApiDelEvent() removes a file descriptor from an interest list.

As the last step in server start-up, Redis runs an infinite loop of aeProcessEvents procedure, effectively implementing an entire event loop iteration. It has several logical parts.

1. The first one is all the logic that should be run before waiting on events. Since this wait is blocking with a specific timeout, the logic executed before epoll_wait is collected in a procedure called beforesleep. It’s implemented here. Among others, it calls procedures dealing with reading clients’ commands and writing a response to them. I’ll write a separate post about several scenarios when a client sends a request, and Redis handles it. Nevertheless, you can already find the corresponding diagrams here.
2. After that, Redis asks for all the events that happened since the latest event loop iteration. This logic is implemented in aeApiPoll procedure. In it, Redis issues a epoll_wait system call. It’s always made with a specific timeout, so it never blocks indefinitely. Then, Redis collects fired events in aeEventLoop->fired.
3. Then, Redis loops over aeEventLoop->fired and runs corresponding handlers. They are stored in an aeEventLoop->events array. Handlers are added by calling a aeCreateFileEvent procedure.
4. Finally, so called time events are handled. Those are events indicating that specific time interval has passed. In C, they are known as timer events. You can subscribe to them natively with creating a timer with timerfd_create and putting a resulting file descriptor in an epoll set, and then setting a timeout with timerfd_settime procedure. It can come in handy for executing a logic that needs to be run periodically. However, there is actually no such thing as a classical timer event in Redis. Instead, it emulates them. First, you register a handler with a aeCreateTimeEvent procedure, where you effectively specify a timestamp when your handler should run. Then, at the end of each event loop iteration, processTimeEvents is called. There, Redis iterates each handler and checks whether a specified timestamp has come. If it has, the corresponding handler is executed.
   That’s how cron is implemented in Redis, for instance. We’ll see shortly what happens there, but first a quick tour of a beforeSleep() procedure.

beforeSleep()

There are some procedures that should be executed before receiving new events. As I’ve already written, among them are procedures dealing with clients’ input and output; there will be a separate post covering those. Here, I’ll briefly walk through procedures related to blocking clients. Hopefully, someday I’ll update this part with key invalidation tracking feature that uses a pub/sub mechanism.

Clients’ blocking

There is a set of procedures executed in beforeSleep() that all relate to a scenario when client connection is blocked. Blocking means that Redis doesn’t parse and, hence, doesn’t execute any commands that a client sends, though it reads and stores those raw requests in client’s buffer.

Overview
First, let’s consider how this blocking generally works using BRPOP command as an example.

When a client sends a BRPOP command, then Redis blocks a client for specified keys with a specified timeout if none of those keys exist. This logic is implemented in a blockForKeys() procedure. There, each client first sets the keys it blocks on. Then, each key is added in a redisDb->blocking_keys dict, and its value is a list of clients blocked on it. Thus, Redis has access to both the keys blocked by a given client and the clients blocked on a given key. Besides, timeout is handled in the same manner. It’s set to a currently blocked client, as well as it’s added in a server.clients_timeout_table radix tree. Finally, a client is marked as blocked.

When some other client adds a first item into any of non-existing lists the first client blocks on, this key is added in a database. dbAdd() procedure checks whether there are any clients blocked on it, and if there are, this key is added in a server.ready_keys list.

handleBlockedClientsTimeout()
This procedure walks through a server.clients_timeout_table radix tree and gets all clients with expired timeout. Each of them is unblocked. It means that the client is not marked as blocked anymore, hence from now on all of its futher commands will be processed. Finally, Redis puts it in a server.unblocked_clients list which will be processed in the next part.

processUnblockedClients()
Here, Redis iterates server.unblocked_clients list. As I’ve written above, it has all the clients unblocked recently. If any of those sent any commands while being blocked, they were suspended; now it’s time to parse and execute them. I’ll write a separate post about command execution scenario, but you can check out a Miro diagram right away.

handleClientsBlockedOnKeys()
This procedure iterates through recently added client keys that at least one client blocks on. As I’ve mentioned earlier, they are stored in a server.ready_keys list. For each such key, each client that blocks on it is unblocked. As I’ve already written, from now on all of its futher commands will be processed: both parsed and executed. Besides, it ends up in a server.unblocked_clients list that Redis iterates in a processUnblockedClients() procedure described above.

Redis Cron

Redis cron refers to a serverCron procedure. It runs hz times per second. But if dynamic-hz is 1 (it’s the default), then the cron frequency is adapted according to the number of active clients:

if (server.dynamic_hz) {
    while (listLength(server.clients) / server.hz >
           MAX_CLIENTS_PER_CLOCK_TICK)
    {
        server.hz *= 2;
        if (server.hz > CONFIG_MAX_HZ) {
            server.hz = CONFIG_MAX_HZ;
            break;
        }
    }
}

There is lot going there. Redis stats is updated, shutting down is handled gracefully, some info is written in logs, some postponed logic is executed — I won’t dive into those. I’ll describe what I consider the most significant parts.

clientsCron()

Actually, the comment section of this procedure already does a great job of describing what’s going on here. In short, it takes all the active clients and processes 1 / server.hz of them, so all the clients are supposed to be processed within about one second. For each client, Redis runs the following procedures:

1. If client timeout is specified, Redis calculated an amount of time when a current client has been idle. If it exceeds a config setting, a client is disposed of and connection is closed —connection socket’s file descriptor is first removed from an event loop and then closed.
2. client struct’s querybuf field size is decreased if needed. This is where a client request body is stored until it parsed. The same thing is done to client’s output buffer, which serves for storing data waiting to be written to a connection socket.
3. Client memory usage statistics is updated (clientsCronTrackExpansiveClients is about clients expensive in terms of memory they use).
4. If client-output-buffer-limit is reached, a client is closed immediately.

Historically, Redis has used the following trick here. In the beginning of each iteration, the tail of server.clients is moved to a head. Why? If this client is removed, O(n) complexity is avoided: Redis starts searching an item from list’s head, but since it is always the first one, the search always takes a constant time. However, as far as I understand, this is not needed anymore. When a client connection request is accepted and client struct is created, server.clients list item is cached there:

void linkClient(client *c) {
    listAddNodeTail(server.clients,c);
    /* Note that we remember the linked list node where the client is stored,
     * this way removing the client in unlinkClient() will not require
     * a linear scan, but just a constant time operation. */
    c->client_list_node = listLast(server.clients);

Moreover, since new clients are added in the tail of server.clients list, clientsCron() will process them first, leaving old clients neglected for some time.

databasesCron()

Here are the procedures needed for Redis storage level maintenance.

activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW)
You can find a visual counterpart here.

This procedure removes expired keys. They are also removed upon retrieval, but what if they are never retrieved? They can fill all the available memory. That’s why keys are expired proactively.

Keys with set expiration time are stored in a redisDb’s expires field, which is a dict struct. There are actually two hash tables in each dict for gradual resizing. It’s needed when a number of items in a hash table grows too large, so hash table size must be adjusted accordingly. Or, the number of elements may get too low so a hash table is shrunk for more efficiency. I’ll write more on that later. For now, it’s enough that there are two of them and both of them are implemented as arrays.

That’s how a hash table in an redisDb’s expires field could look like:

Those violet circles are bucket entries, or hash table elements. When they belong to the same bucket, they form a singly linked list, with each element pointing to the next. Each element is represented as a dictEntry struct:

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
};

Expiration time is stored in v.s64 field as a unix timestamp. The key pointer that is used in redisDb->expires item is the same key pointer that is used in redisDb->dict’s dictEntry storing a client value. Now, let’s suppose that the circles marked as red are expired:

Redis walks through each hash bucket in a hash table, and if a current bucket has a linked list of bucket entries, it’s iterated either. This iteration logic is implemented in dictScanDefrag() procedure. It’s more complicated than that, but for now this approximation is enough. For each visited bucket entry, Redis invokes expireScanCallback() procedure. It checks whether an expiration time has passed, and if it has, then a key is deleted from both dictionaries — the one storing an expiration time itself and the one storing actual client data:

Redis continues this scanning until it hits either a bucket entries limit or hash buckets limit, so this won’t take too long. In reality, the former limit is several dozens on average, but in this example it’s 3. The latter is twenty times more.

By the end of this iteration, redisDb->expires’s hash table looks like this:

And redisDb->dict’s hash table looks like that:

This process will continue on the next cron iteration from where it left off.

activeDefragCycle()
Defragmentation is the process of reducing memory fragmentation, which occurs when free memory in a program is divided into small pieces that are too small to be useful for allocating new objects or data. This can lead to inefficient memory usage and slower program performance over time. Defragmentation helps to consolidate free memory into larger contiguous blocks, which can then be more effectively used for new allocations. This process is quite costly and is disabled in Redis by default. Typically, you can identify that you need defragmentation by examining info memory output periodically.

Defragmentation itself boils down to reallocating memory for a current pointer in case it’s worthwhile. Redis performs this process incrementally, the same way it approaches key expiration. That is, it doesn’t perform all the required work in a single run, because it might take a while and Redis will be unresponsive during those periods. Instead, such kinds of operations are carried out in small steps, in a controllable manner with tight limits, but often. It iterates hash tables with dictScanDefrag() procedure, walks through hash table buckets, and, for each bucket, defragments three types of pointers: dictEntry, its key, and v.val. It starts with dictEntrys:

1. First, dictDefragBucket() is invoked for a current bucket. There, activeDefragAlloc() is executed against each bucket entry. It boils down to two things. First, Redis asks jemalloc memory allocator whether it’s worthwhile to reallocate a current pointer. And if it is, this pointer’s memory is reallocated and an old pointer’s memory is copied into a new one. After that, an old pointer is freed.
2. After that, Redis walks through each dictEntry in a current bucket again, and for each one, executes defragScanCallback(). This procedure boils down to calling defragKey() procedure. First, it defragments a key. Then, Redis performs defragmentation on a value by using a procedure that depends on the type of a current dictEntry.v.val.

tryResizeHashTables()
If the number of elements in a hash table becomes too low relative to its size, this can lead to several problems. First, a large number of buckets means that a lot of memory is allocated for the hash table, but most of it remains unused. Second, performance degrades when a sparse hash table is scanned. That’s why Redis periodically shrinks underutilized hash tables. tryResizeHashTables() procedure does exactly that: it reduces the size of hash tables if they are fewer than ten percent full.

Resizing process never touches a hash table with client data. Imagine a hash table with a million keys. If it resized in-place, each key must be rehashed and moved to a new slot. This might take a while. Instead, a hash table with new size is allocated in a dict->ht_table[1]:

Its size is set to the closest power of two greater or equal to the number of elements in a hash table.

Resizing here only shrinks a dictionary. Expanding takes place in several places, most notably — while inserting new value, namely in a dictFindPositionForInsert() procedure.

Note that creating a new hash table and moving data there from an old one, that is, dict->ht_table[0], are two different processes. The process of moving data into a new hash table is called rehashing. It’s done incrementally while interacting with a dictionary, both in read and write operations. For instance, check out dictFind(), dictGetRandomKey(), dictFindPositionForInsert(), etc. Besides, it’s performed in each cron iteration with incrementallyRehash() procedure.

incrementallyRehash()
So, we have a dict that has just been resized, that is, a second hash table with a new size:

It’s time to move the first hash table’s data there. When it’s performed in a cron iteration, Redis moves bucket entries in a hundred-size batches, and with a specific time limit which is one millisecond. So, let’s start with a first bucket:

When the second hash table is larger than the first one, new bucket index is calculated by taking an item key’s hash. So their distribution in a new hash table has good chances to be even. This is not the case when the second hash table is smaller. In this case, new hash is not calculated. Instead, a new bucket index is taken as a current index in a first hash table masked with the size of smaller has table. Since hash tables are always powers of two, all the elements residing in the first bucket of a first hash table end up in the first bucket of a second hash table, and so on:

That’s barely a problem though. If a hash table is shrinking, it means it’s really sparse and a scenario when any single bucket has lots of elements is unlikely.

Then Redis continues with the next non-empty bucket:

And so on. When done, hash tables swap places and the second hash table is reset:

Until then, when rehashing is still in progress, reads are done in both hash tables. New keys are added in the second one, so they are not lost when rehashing is over.

A new process forking and a copy-on-write technique
That’s about all that happens in a databasesCron() procedure. One thing to note is that all those manipulation with in-memory data are allowed only when there is no child process. Why? When a child process is forked, than it has access to all the data that the parent process has. This happens thanks to copy-on-write technique implemented by an OS. But if either process mutates some shared data, an underlying memory page is copied and becomes visible only to a process that did a modification. Another process still sees data that was actual at the moment of forking.

This CoW technique has associated costs, such as increased space usage and potential performance overhead. That’s why Redis avoids maintenance tasks when there is a child process running. That’s the reason why you occasionally see this check throughout a codebase. Besides, data mutation in a child process is worthless — the parent won’t see it anyway. That’s why resizing — and, hence, a following rehashing —are disabled in a child process.

rdbSaveBackground()

This procedure creates an rdb snapshot. By default, this procedure is triggered once an hour if there is a single change, every 5 minutes with at least 100 changes, and once a minute with at least 10000 changes. Those settings can be changed though.

All of the heavy lifting takes place in a child process. There, an rdbSave() procedure is executed and a process exits. Its implementation is quite straightforward but tedious. The whole instance data is first written in a file. For performance reasons, some of this data might be stored in a buffer within the C library’s I/O subsystem. So when the write is over, Redis first needs to make sure that all of this data is moved to the specified file. That’s what a fflush procedure does. However, this does not guarantee that the data has been fully written to the disk. It can be cached by OS or disk controller. To actually move this data on disk, fsync call is needed.

The rdbSaveRio() procedure in Redis is responsible for writing the contents of the Redis database to disk. It starts by writing some metadata and function definitions, and then proceeds to write the contents of each database. For each entry in the database, the procedure writes the key and value. The key is preceded by a value type identifier, and the value is written in its raw binary form. In addition to the key and value, the procedure writes the expiration time of the key, as well as either the LRU or LFU eviction information, depending on the configured eviction policy.

rewriteAppendOnlyFileBackground()

I’ve already wrote about the process of loading data from files in case of AOF mechanism. Here is a rewrite process described.

It’s triggered when all of the following conditions hold true:

1. AOF is on (that is, appendonly setting is 1)
2. rewrite process has not already started
3. current AOF file size exceeds auto-aof-rewrite-min-size setting
4. aof file size grew more than auto-aof-rewrite-percentage config value since the latest rewrite
5. and a rewrite process is not postponed because of repeated failures

This process is performed in several steps.

Flush Redis buffer into an AOF file
First of all, if there are commands in Redis memory not yet written in an AOF file, it’s done right away.

New incr file created where the current commands are written
Then, a new incr file with the next sequence number is created and added in a manifest file. For instance, a manifest file had looked like this before rewrite process started:

file my_appendonly_file.aof.2.base.aof seq 2 type b

# If previous aof rewriting ended with an error, history files can be left here. They are deleted in the end of successful aof-rewriting.
file my_appendonly_file.aof.1.base.aof seq 1 type h
file my_appendonly_file.aof.1.incr.aof seq 1 type h

# This is a currently active incr file. All the current commands are logged here.
file my_appendonly_file.aof.2.incr.aof seq 2 type i

It can contains history files if the latest rewrite ended with failure. Then, previous incr file fsynced and closed. And, finally, a new incr file is set to write current commands. Now, a manifest file looks like that:

file my_appendonly_file.aof.2.base.aof seq 2 type b

file my_appendonly_file.aof.1.base.aof seq 1 type h
file my_appendonly_file.aof.1.incr.aof seq 1 type h

file my_appendonly_file.aof.2.incr.aof seq 2 type i
file my_appendonly_file.aof.3.incr.aof seq 3 type i

Entire Redis instance snapshot is written into temporary base file
After new incr file is ready to writing all mutating commands, a new child process is forked. There, the actual rewrite happens. It’s implemented in a rewriteAppendOnlyFile() procedure. The whole Redis dataset is written in a temporary file called temp-rewriteaof-bg-<current pid>.aof. If aof-use-rdb-preamble is enabled (it’s so by default), then the data is written in a raw binary format — the same one that an rdb snapshot has. If it’s disabled, data is written as a human-readable compacted list of commands. It iterates through all dictEntrys in each dict and, depending on a value type, writes a set command. For instance, for a key key5 having a simple string value value5, it writes:

*3
$3
SET
$4
key5
$6
value5

It has a form of a command, but unlike an incr file, there is no history in this file. Each key is written only once, with its current value.

Worth noting that during the snapshot creation, the parent process continues to handle client commands, including mutating ones, which Redis writes to a new incr file. However, the child process that takes the snapshot does not see these changes. It only sees a snapshot of the data at the moment of forking. As a result, the data in the snapshot and the live dataset neither intersect nor have gaps. Hence, there is no data duplication or data loss when they are loaded into memory when Redis starts up.

When snapshot is ready, it becomes a new base file
In each cron iteration, Redis checks whether a snapshot creation has completed. If it has, then the temporary file is renamed to the new base file, while the previous base file becomes historical. Additionally, all the incr files except for the currently active one become historical as well. When a file becomes historical, it is not renamed; rather, it is marked as such in the manifest file, which is persisted at this point. Now it looks like that:

# this is a new base file
file my_appendonly_file.aof.3.base.aof seq 3 type b

# this is a previous incr file
file my_appendonly_file.aof.2.incr.aof seq 2 type h
# this is a previous base file
file my_appendonly_file.aof.2.base.aof seq 2 type h
# this is a base file left from the latest non-successful aof rewrite
file my_appendonly_file.aof.1.base.aof seq 1 type h
# this is an incr file left from the latest non-successful aof rewrite
file my_appendonly_file.aof.1.incr.aof seq 1 type h

# this is a currently active incr file where incoming commands are written
file my_appendonly_file.aof.3.incr.aof seq 3 type i

Finally, the historical files are deleted both from disk and from the manifest file, which is updated again:

file my_appendonly_file.aof.3.base.aof seq 3 type b

file my_appendonly_file.aof.3.incr.aof seq 3 type i

In closing

That’s what Redis server start-up looks like in a standalone mode. I haven’t considered cluster capability, replication, or sentinel mode. However, I hope that if you dive into those, you’ll have some background helping you with that.

Redis Server Start-Up Internals was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

Overall hierarchy of tests

In 2009, Mike Cohn, an agile evangelist and practitioner, came up with the term “Testing pyramid”. From the bottom to the top, it consisted of three layers: Unit tests, Service Tests, and UI Tests. The naming might seem a bit vague, and the pyramid itself is outdated to a certain extent. But the overarching idea behind it is quite simple. There should be a good amount of small and fast lower-level tests, typically called unit-tests. As you go higher up the pyramid, that is, the coarser-grained your tests are, the amount of them should decrease. The reasoning behind this idea is quite simple either: it is cheap and simple to write fine-grained unit-tests. Besides, they typically run extremely fast.

Every new layer is a leap to a notable abstraction. At least talking about a backend code, the most practical levels are the ones that correspond to abstraction layers. Those are typically the following, from the highest to lowest:

1. End-to-end tests, customer journey level. They typically include browser, imitating real user’s behaviour.
2. Endpoint tests that include transport. They typically correspond to the controller level of your application. Such tests are typically called Integration tests.
3. Unit tests for classes used within a user story. It is your domain level.

This list aligns with ports-and-adapters architecture, popularized by Robert Martin in his book.

Unit tests

There isn’t a single definition of a unit-test. For me, a unit test is the one that relies only on clear and specific abstractions. The scope they operate in is typically small. A litmus test is the following: when your tests are “unit” enough, you don’t need to debug. If you need, the problem is probably not with your tests, but with your design. Create finer-grained classes, cover them with tests. If you are able to spot a bug in a matter of seconds, congratulations: you’ve come up with a decent unit-tests suite. It’s crucial since there should be no tension in running tests like every five seconds or so.

Why not having only unit tests, if they are so great? Because when you have to refactor some user story, you’ll be covered by controller tests. If there are none, you’ll be in big trouble.

Integration tests

Unit test concept has a quite vague definition. Integration test even more so.

In practice, most of the time they mean testing either controllers (or Application Services, in DDD lingo) or endpoints. Typically, this implies that you mock third-party service calls, but don’t mock a database, using the real one instead. Being a higher-level test, you don’t test its implementation details, that is the behaviour of its internal classes. Instead, you test that the HTTP response is correct and desired side effects are in place.

Be very cautious to stay at the same abstraction level. For example, if you test order registration endpoint, don’t test that there is a record in a database. It’s an implementation detail. Today you use Postgres, and tomorrow you end up with Mongo. Instead, call order details API endpoint to make sure that it contains all the required data. What’s the whole point in doing so? Integration tests are your safety net. When implementation details change, sometimes drastically, you want to make sure that everything works as expected.

Writing integration tests often involves discussions on what to mock and what not to mock. For me, the guideline is simple. Your code should be the most fragile and error-prone part in the whole testing process. Say, what is more reliable, your database or your application code? I bet it’s the former. And what about the network? The network is notoriously fragile and slow, and this is the reason why network calls rarely take part in tests. Another example is when your application deals with external devices that are out of your control. For example, devices that print checks are pretty fragile. You don’t want your test fail because the printer is run out of paper or inks or anything else. Otherwise, you end up testing those devices instead of testing your code.

E2e tests

End-to-end tests are the last line of defense. They test a complete customer journey, from UI to the backend, to UI again, and so forth. I always keep in mind the Pareto principle when writing them: 20% of any effort gives 80% of the result. Identify your key business-processes and automate them. Usually, it’s the one that brings your business most of the money. For example, order registration and further processing, resulting in its delivery. Thus, with such tests in your test-suite, there is not a chance for you to introduce a devastating bug, so your back will be covered.

The flipside is the speed and reliability, both of which e2e tests lack.
Tests running in a console are about one order of magnitude faster comparing to tests with browser involved. So despite things might look shining in the beginning, a year ago you could end up with a test suite that takes an hour to run.

Besides, end-to-end tests are often flaky. And the more complicated they are, the flakier they get, because of an increasing amount of unforeseen factors. Some rare browser quirk, unexpected layout behavior — all this adds up to overall flakiness. There is a common workaround, though. Don’t spin up a browser; work only through DOM. Thus your tests will be way faster, not 100% end-to-end though.

Having end-to-end tests help you to reveal unexpected coupling, particularly the one that is hard to spot — for example, an accidental coupling between user stories. Remember how last time you modified some user story, and another one got broken unexpectedly? That’s precisely the case for end-to-end tests, covering a set of user stories that form a particular customer journey.

People often conflate e2e tests with UI tests, which is a broader concept.

UI tests

UI tests probably deserve their own pyramid. Principles are the same, after all. Doing UI development, most of the tests are typically small, fast, and the ones operating in a small scope, which generally falls into the category of “unit”. In other words, this term is often used as a frontend equivalent of a unit-test, which is typically applied to backend development.

Generally, there are two things to test in UI. First one is behaviour. There is a myriad of functionality examples that can be covered with UI unit tests. Calculating an order’s total, a link leading to a correct URL, an alert notification is displayed in red, etc. Besides, you don’t have to test most of the behaviour in an end-to-end fashion, even if you need a response from a backend. Write a stub, and you’re good to go. It can very well be tested in isolation.
Jasmine and Mocha are a good place to start out with UI unit tests.

Testing UI layout is typically a bit more intricate endeavour. The basic idea is simple enough, though. With every build, your tests automatically create browser snapshots and compare them with the ones from the previous builds. If they differ, something is wrong. For example, cypress can do such kind of stuff.

Tests within Continuous delivery

If you want to deploy your software frequently and reliably, having a test portfolio is not enough. The key is automating it. You should be able to deploy your code at all times of day and night. Do you want to rely on human beings, who can forget to run tests before pushing code? Do you want to deploy your code only to find out that it doesn’t compile? I bet you don’t. So the best advice you can get is to use a CI/CD pipeline because it excludes a human-factor.

Besides, infrastructure provisioning and deployment process are quite tedious and repetitive tasks, which we humans are particularly bad at. CI/CD pipelines, on the contrary, are extremely good at automating those tasks. Manual tasks don’t scale. If you need a single manual tester now, you’ll need a growing number of them as your system grows bigger. So instead of spending an increasingly significant amount of time carrying them out, you can automate all your processes once and for all.

Common pitfalls

Manually-run tests
The absence of tests automation is a perfect recipe on how to abandon your team’s testing activity. A couple of times when some team member forgets to run tests before pushing code could be enough to get disappointed in a whole testing endeavor. How not to? Use a proper CI/CD pipeline that never forgets running your tests before deployment.

Flaky tests
The flaky test is the one which fails once in a while. There are several problems with this kind of tests.

First one, when a new build is tested and fails, you can’t say for sure why it happened: because of some flaky test or because a new bug was introduced.

Second, the credibility of test suite decreases and a team ceases to write tests, considering it a useless activity. Having a CI/CD pipeline which alerts in case of a failed test and declines to ship stuff literally makes you fix that flaky test, restoring overall test-suite credibility and team morale.

Ice cream cone
A small amount of cheap and fast tests, a vast amount of slow and expensive (in terms of time required to write them) UI tests. So a slim test pyramid degenerates into a clumsy ice cream cone.

This cone appears when you start with more high-level tests than you should. Your whole test suite becomes slow, and bugs become hard to get spotted. Instead of testing, you end up in gloomy debug-land. Besides, such kind of tests is not particularly reliable. If you run the same browser-involved e2e test a hundred times, the chances are that one of those tests fails — because of some browser quirks.

It’s not real code — it’s just a test!
Test code is by no means different from the rest of your code. Indeed, it’s not run in production. But you still have to maintain it. And maintainability costs are much higher than in writing ones. So the same best practices that are used in production code are applied to testing code as well.

Desire to test a private method
This is a clear indication that a class where that private method belongs to breaks the Single-Responsibility Principle. It’s a God Object that knows too much and does too much. The cure is simple: extract this private method in its own class and cover it with unit tests.

Testing the wrong thing
Do you test stuff that brings you most of the money? Very often, developers test for the sake of testing itself, without realizing the true value of testing — reducing risks and saving money. So before writing any tests, especially higher-level ones, talk with your product-owner, she certainly could give you some clues on the stuff of the utmost importance.

Tests structure exactly mirrors classes structure
This seems logical from the first sight but look at it this way. Some of your tests should serve you as a safety net which ensures that your system’s behaviour doesn’t change when you modify its internal implementation. More often than not, most of our lower-level classes represent that internal implementation. So any modification in that class would cause a corresponding test failure. Fixing it each time is a daunting task. What Robert Martin recommends is a “test contra-variance,” which means testing only observable behaviour of a class. Which means that if your class A, providing some domain-specific behaviour, uses a bunch of implementation-specific and stable helpers, you don’t need to test them. XTest would be just fine. So no need in testing all the internal implementation, that’s very fragile.

In closing

This topic is huge indeed, and I’ve barely scratched the surface here. I suggest that you read some more on it; Growing Object-Oriented Software, Guided by Test and The Art of Software Testing are great sources of further inspiration.

What to Test in CI/CD Pipeline was originally published in The DevOps Corner on Medium, where people are continuing the conversation by highlighting and responding to this story.