02 Data Structures Quick Redis Operations and Some Slow Ones #
When it comes to Redis, the first word that comes to our mind is “fast.” But have you ever wondered what exactly makes Redis so fast? One important aspect is its ability to quickly find and operate on data within microseconds after receiving a key-value pair operation.
With so many databases out there, why does Redis stand out in terms of performance? One reason is that Redis is an in-memory database, meaning all operations are performed in memory, which inherently has fast access speed. Another reason is its data structures. Key-value pairs are organized using specific data structures, and efficient data structures form the foundation for Redis to process data quickly. In this lesson, I will discuss data structures with you.
At this point, you may say, “I know this, it’s just String, List, Hash, Set, and Sorted Set, right?” Actually, these are just the data types for the values in Redis key-value pairs, representing the way the data is stored. Here, when we mention data structures, we are referring to their underlying implementations.
In simple terms, Redis has a total of 6 underlying data structures, namely Simple Dynamic Strings, Doubly Linked Lists, Zip Lists, Hash Tables, Skip Lists, and Int Arrays. The corresponding relationship between these data structures and data types is shown in the following diagram:
As you can see, the String data type has only one underlying data structure, which is the Simple Dynamic String. The List, Hash, Set, and Sorted Set data types each have two underlying implementation structures. Usually, we refer to these four types as set types because one key corresponds to a set of data.
At this point, some questions are worth considering:
- What structures organize the keys and values?
- Why are there so many underlying structures for set types, and how do they store data? Are they all fast?
- What is a Simple Dynamic String, and is it the same as the commonly used string?
Next, I will discuss the first two questions with you. By doing so, you will not only understand the basic principle behind Redis’s “fast” performance but also identify potential “slow operations” in Redis, thus maximizing its performance advantage. As for the Simple Dynamic String, I will discuss it in subsequent lessons.
Let’s first take a look at how keys and values are organized.
How are keys and values organized? #
To enable fast access from keys to values, Redis uses a hash table to store all key-value pairs.
A hash table is essentially an array, and each element of the array is called a hash bucket. So, we often say that a hash table consists of multiple hash buckets, and each hash bucket contains key-value pair data.
You may wonder: “If the value is a collection type, how can a hash bucket that is an array element store it?” In fact, the elements in the hash bucket do not store the values themselves, but rather pointers that point to the actual values. This means that regardless of whether the value is a string or a collection type, the elements in the hash bucket are pointers to them.
In the following figure, you can see that the entry elements in the hash bucket store *key and *value pointers, which respectively point to the actual key and value. In this way, even if the value is a collection, it can be accessed through the *value pointer.
Because this hash table stores all key-value pairs, I also refer to it as the global hash table. The greatest advantage of a hash table is that it allows us to quickly retrieve key-value pairs in O(1) time complexity—by simply calculating the hash value of the key, we can determine its corresponding hash bucket position and then access the corresponding entry element.
As you can see, this lookup process primarily relies on hash calculation and is not directly affected by the amount of data. In other words, whether the hash table has 100,000 keys or 1 million keys, we only need to calculate once to find the corresponding key.
However, if you only understand the O(1) complexity and fast lookup feature of a hash table, you may find that the operations sometimes become slow when you write a large amount of data to Redis. This is actually because you overlooked a potential risk, which is the conflict problem of the hash table and the operation blocking that rehashing may bring.
Why is the operation of the hash table slowing down? #
When you write more data to the hash table, hash conflicts are inevitable. Here, hash conflict refers to the situation where the hash values of two keys coincide and map to the same hash bucket during the calculation of the hash bucket.
After all, the number of hash buckets is usually fewer than the number of keys, which means that some hash values of keys will inevitably correspond to the same hash bucket.
The way Redis solves hash conflicts is through chaining. Chaining is easy to understand—it means multiple elements in the same hash bucket are stored using a linked list, connected by pointers.
As shown in the figure below: entry1, entry2, and entry3 all need to be stored in hash bucket 3, resulting in a hash conflict. At this time, the entry1 element will point to entry2 through a *next pointer, and similarly, entry2 will also point to entry3 through a *next pointer. In this way, even if there are 100 elements in hash bucket 3, we can connect them using the pointers in the entry elements. This forms a linked list, also known as a collision chain.
However, there is still a problem here: elements on the hash collision chain can only be found and operated on one by one through pointers. If more and more data is written into the hash table, there may be more and more hash collisions, which can lead to excessively long hash collision chains and thus result in longer search time and decreased efficiency for elements on these chains. This is not acceptable for Redis, which values speed.
Therefore, Redis performs rehashing on the hash table. Rehashing involves increasing the number of existing hash buckets so that the increasing number of entry elements can be distributed among more buckets, reducing the number of elements in each individual bucket and thus reducing collisions. How is this done specifically?
In order to make rehashing more efficient, Redis by default uses two global hash tables: hash table 1 and hash table 2. Initially, when you first insert data, hash table 1 is used by default, and hash table 2 is not assigned any space. As the data gradually increases, Redis starts the rehashing process, which consists of three steps:
- Allocating more space to hash table 2, for example, twice the size of the current hash table 1.
- Remapping and copying the data from hash table 1 to hash table 2.
- Releasing the space of hash table 1.
At this point, we can switch from hash table 1 to hash table 2, using the enlarged hash table 2 to store more data, while keeping the original hash table 1 as a backup for the next rehashing process.
This process may seem simple, but the second step involves a large amount of data copying. If all the data in hash table 1 is migrated in one go, it will cause Redis to block its threads and be unable to serve other requests. In this case, Redis cannot access the data quickly.
To avoid this problem, Redis adopts incremental rehashing.
In simple terms, during the second step of copying data, Redis continues to process client requests normally. With each request processed, it starts from the first index position in hash table 1 and copies all the entries at that position to hash table 2. When processing the next request, it copies the entries at the next index position in hash table 1. The diagram below illustrates this:
Incremental rehashing
This cleverly distributes the overhead of a large-scale copying operation over multiple request processing steps, avoiding time-consuming operations and ensuring fast data access.
Alright, by now you should understand how Redis organizes its keys and values using hash tables. For the string type, once the hash bucket is found, direct operations such as insertion, deletion, and modification can be performed, resulting in an O(1) complexity for hash table operations.
However, for set types, even after finding the hash bucket, further operations need to be performed within the set. Next, let’s see the efficiency of operations on set types.
Efficiency of Set Data Operations #
Unlike the String type, the first step in working with a set type value is to find the corresponding hash bucket position in the global hash table, followed by adding, removing, modifying, or querying within the set. So, what factors are related to the efficiency of set operations?
First, it is related to the underlying data structure of the set. For example, a set implemented with a hash table will have higher access efficiency than one implemented with a linked list. Second, the efficiency of operations is determined by the specific characteristics of the operations themselves. For example, reading or writing a single element is more efficient than reading or writing all elements.
Next, let’s discuss the underlying data structures and operation complexity of set types.
What are the underlying data structures? #
As I mentioned earlier, there are mainly 5 types of underlying data structures for set types: integer arrays, doubly linked lists, hash tables, compressed lists, and skip lists.
Among them, we have already learned about the characteristics of hash tables; integer arrays and doubly linked lists are also commonly used, and their operations involve sequential reading and writing, meaning accessing elements one by one through array indexes or linked list pointers, with an operation complexity of O(N) and relatively low efficiency; compressed lists and skip lists may not be as commonly encountered in everyday situations, but they are also important data structures in Redis, so let me explain them in more detail.
A compressed list is actually similar to an array, where each element corresponds to a stored data. Unlike arrays, a compressed list has three fields at the beginning: zlbytes, zltail, and zllen, which represent the length of the list, the offset of the list tail, and the number of entries in the list, respectively. At the end of the compressed list, there is also a zlend, indicating the end of the list.
In a compressed list, if we want to locate the first and last elements, we can directly locate them based on the lengths of the three fields at the beginning, with a complexity of O(1). However, when searching for other elements, it is not as efficient, and we have to search one by one, resulting in a complexity of O(N).
Let’s take a look at skip lists next.
With an ordered linked list, we can only search for elements one by one, which makes the process very slow. To address this issue, skip lists were introduced. Specifically, skip lists add multiple levels of indexing to the linked list, allowing for quick data positioning through several jumps based on the index positions, as shown in the following diagram:
Quick lookup process in a skip list
If we want to find the element 33 in the linked list, we can only traverse the list from the beginning and search 6 times until we find 33. At this point, the complexity is O(N), and the search efficiency is very low.
To improve the search speed, let’s add an additional level of indexing: starting from the first element, every two elements are selected as an index. These indices then point to the original linked list through pointers. For example, we extract element 1 as the first-level index from the first two elements, and extract element 11 as the first-level index from the third and fourth elements. Now, we only need 4 lookups to locate the element 33. If we want to further improve the speed, we can add a secondary index: extract certain elements from the primary index to create the secondary index. For example, we can extract elements 1, 27, and 100 from the primary index as the secondary index, which points to the primary index. In this way, we only need 3 lookups to locate element 33.
As you can see, this search process involves jumping between multiple levels of indexes, which is exactly why it is called a “skip list”. When the data size is large, the search complexity of a skip list is O(logN).
Now, we can classify these data structures based on their time complexities for searching:
Complexity of Different Operations #
There are many types of operations for collection data structures, including reading and writing individual elements, such as HGET and HSET, operations on multiple elements, such as SADD, and operations that traverse the entire collection, such as SMEMBERS. These operations have different complexities, and the complexity levels are important factors to consider when choosing a collection type.
I have summarized a “four-line chant” to help you quickly remember the complexities of common collection operations. With this knowledge, you can avoid high complexity operations in your usage.
- Single element operations are fundamental;
- Range operations are usually time-consuming; statistic operations are usually efficient;
- There are only a few exceptions.
First, single element operations refer to the add, delete, modify, and query operations on individual data in each type of collection. For example, HGET, HSET, and HDEL for Hash types, and SADD, SREM, SRANDMEMBER for Set types. The complexity of these operations is determined by the data structure used by the collection. For example, since HGET, HSET, and HDEL operate on a hash table, their complexities are all O(1); When a Set type uses a hash table as its underlying data structure, the complexities of SADD, SREM, and SRANDMEMBER are also O(1).
Here, there is one thing you need to pay attention to. Collection types support adding, deleting, modifying, and querying multiple elements at the same time. For example, HMGET and HMSET for Hash types, and SADD also support adding multiple elements at the same time. In this case, the complexity of these operations depends on the complexity of single element operations and the number of elements. For example, when HMSET adds M elements, the complexity changes from O(1) to O(M).
Second, range operations refer to traversal operations in collection types, which can return all the data in the collection, such as HGETALL for Hash types and SMEMBERS for Set types, or return a range of data, such as LRANGE for List types and ZRANGE for ZSet types. The complexity of these operations is generally O(N), which is time-consuming, and we should try to avoid them.
However, starting from Redis version 2.8, Redis provides the SCAN series operations (including HSCAN, SSCAN, and ZSCAN), which implement progressive traversal and only return a limited number of data each time. Compared to operations like HGETALL and SMEMBERS, this avoids Redis blocking due to returning all elements at once.
Third, statistic operations refer to the recording of the total number of elements in a collection, such as LLEN and SCARD. The complexity of these operations is only O(1). This is because when a collection type uses data structures such as compressed lists, doubly linked lists, or integer arrays, these structures specifically record the number of elements, allowing these operations to be completed efficiently.
Fourth, there are exceptions, which refer to special records in certain data structures. For example, both compressed lists and doubly linked lists record the offsets of the head and tail of the list. As a result, for the four operations of LPOP, RPOP, LPUSH, and RPUSH in List types, which add or delete elements at the head or tail of the list, they can be directly located by the offsets, so their complexity is also O(1), enabling fast operations.
Summary #
In this lesson, we learned about the underlying data structures in Redis. This includes the global hash table structure used to store each key-value pair in Redis, as well as the five underlying structures used to implement set types: doubly linked list, compressed list, integer array, hash table, and skip list.
The reason Redis can operate quickly on key-value pairs is, on one hand, because the hash table with O(1) complexity is widely used. This includes String, Hash, and Set, where the complexity of their operations is mostly determined by the hash table. On the other hand, Sorted Set also adopts the skip list with O(logN) complexity. However, for range operations on set types, the complexity is usually O(N) due to the need to traverse the underlying data structure. Here, my suggestion is to use other commands as alternatives, such as using SCAN to avoid time-consuming full collection traversal operations within Redis.
Of course, we cannot forget the List type, which has higher complexity. The complexity of operations for its two underlying implementation structures, doubly linked list and compressed list, is O(N). Therefore, my suggestion is to use the List type according to the specific situation. For example, since POP/PUSH has high efficiency, it can be used primarily for FIFO queue scenarios instead of being used as a collection for random read and write operations.
Redis has a rich variety of data types, and each type has many operations. It is often impossible for us to memorize the complexities of all operations at once. Therefore, the best approach is to grasp the principles and adapt to changes. Here, you can see that once you understand the basic principles of data structures, you can infer the complexities of different operations based on the principles, even if you are not familiar with a particular operation. This way, you don’t have to memorize everything, and you can make choices quickly and reasonably.
One Question per Lesson #
Integers arrays and compressed lists do not have a significant advantage in terms of search time complexity, so why does Redis use them as underlying data structures?
Understanding data structures is a prerequisite for understanding Redis performance. If you have friends who are not familiar with data structures, feel free to share today’s content with them. I look forward to discussing and exchanging ideas with you in the comments section.