When it comes to Redis, the first thing people think about is Redis caching. Why? Because “fast” is the biggest characteristic of Redis, used for caching, reduce I/O operations, Redis is very suitable, but why is Redis so fast?

In fact, this is related to two aspects, on the one hand, Redis is an in-memory database, almost all operations are done in memory, memory access speed is of course very fast compared to disk; On the other hand, thanks to the data structure of Redis, Redis designed a set of data structure suitable for itself in order to complete the operation of adding, deleting, modifying and checking more quickly and efficiently. This paper makes a simple analysis on the data structure of Redis.

Data type and data structure

Those of you who often use Redis will probably tell you right away that there are five commonly used Redis data types: String, List, Hash, Set, and SortedSet. Redis designed the underlying data structure implementation for these five commonly used data types, including SDS (simple dynamic string), LinkedList (double LinkedList), HashTable (HashTable), SkipList(SkipList), IntSet(integer set), ZipList(compressed list), etc. Their corresponding relationship is shown in the figure below:

It can be seen that, except String only uses simple dynamic String implementation, the other four data types are implemented using the underlying data structure. This is because in different situations, Redis will use different underlying data structure to optimize storage when implementing a data type.

List

Ziplist encoding is used when a list meets both of the following criteria:

  • The list holds all string elements that are less than 64 bytes long;
  • The list object holds less than 512 elements.

List encodings that do not meet these two criteria use linkedList encodings:

Hash table

The ziplist encoding is used when a hash table meets both of the following conditions:

  • The key and value strings of all key-value pairs stored in the hash table are less than 64 characters long;
  • The number of key-value pairs stored in the hash table is less than 512.

Hash tables that do not meet these two criteria need to use HashTable

Set

When the set satisfies both of the following criteria, the set uses intSet encoding:

  • All elements of the collection are integer values;
  • The set contains no more than 512 elements.

Collection objects that do not satisfy these two conditions need to use hashTable:

Ordered set

Ordered sets satisfy the following two conditions at the same time, ordered sets use ziplist encoding:

  • The number of elements in the ordered set is less than 128.
  • Ordered collections hold all element members less than 64 characters long;

Skiplist is used for collection objects that do not satisfy these two conditions:

Through the underlying principle of Redis, we have an in-depth understanding of how the underlying structure of Redis is designed.

Simple dynamic strings

Redis itself has built an abstract type: Simple Dynamic String (SDS), which is used as the default string representation for Redis:

  • The value of free attribute is 0, indicating that SDS does not allocate any unused space.
  • The len attribute value is 5, indicating that SDS stores a 5-byte string.
  • The buf property value is an array of type char, the last byte of which is “\0”;

Thus, the time complexity of obtaining SDS length is O(1).

Optimization of SDS in performance

SDS, as a “dynamic string”, supports the expansion of string through the redistribution operation (first check whether the SDS space meets the requirements of modification, if not automatically expand to the required size) to prevent the problem of buffer overflow; Also, when SDS shortens a string, the program frees up space that the string no longer uses. At the same time, in the case of frequently changing strings, the performance is optimized by using two strategies: space preallocation and lazy space release:

Space pre-allocation: When SDS is modified for space expansion, Redis not only allocates the space required for the modification to SDS, but also allocates additional space:

  • If the SDS length is less than 1MB, Redis allocates the same amount of unused space as len.
  • If SDS length is greater than or equal to 1MB, Redis allocates 1MB of unused space;

Through space preallocation, SDS can reduce the number of space allocations after modification.

Lazy space free: When the SDS string is shortened, Redis does not reclaim the shortened bytes and stores them in free instead. By lazy space freeing, SDS avoids memory reallocation after shortening strings and provides an advantage for expected string growth.

A series of optimizations for string manipulation by SDS improves Redis read and write speed.

Two-way linked lists

As a common nonlinear structure, linked list provides efficient node rearrangement capability. In Redis, a series of functions are realized through bidirectional linked list:

Bidirectional chain watchband has a header pointer and a tail pointer, so get the head node and tail node is O(1); In addition, the length of the list is also O(1) with len.

Hash table

Hash tables are the underlying data structures of Redis dictionaries:

The sizemask property always equals size-1. This property performs ampersand with the hash value to determine which index of the table array a key should be placed on.

Resolving key conflicts

Redis hash table uses chain address method to resolve key conflicts. And, for faster speed, Redis always adds new nodes to the head of the list (O(1) time).

rehash

With the continuous execution of operation, when the number of key/value pair hash table to save too much or too little, Redis will response on the size of the hash table of expansion and contraction, in simple terms, is the use of free hash table to expand or contract operations, and will default hash table assigned to the specified hash tables, finally set up the new hash table for the default hash table.

Of course, the rehash action is not a one-off, but rather a gradual process, to prevent the server from having so many Rehash nodes that it stops accessing them for a certain amount of time. In progressive rehash, delete/find/update operations are performed on both hash tables, and additions are stored on the new hash table.

When will rehash be triggered? There are two cases:

  1. Redis does not run BGSAVE or BGREWRITEAOF. The load factor of the hash table is 1, which automatically expands.
  2. Redis is running BGSAVE or BGREWRITEAOF. The load factor of the hash table is 5.
  3. If the load factor of the hash table is less than 0.1, it shrinks automatically.

Wherein, the calculation formula of load factor is as follows:

Load factor = Number of nodes in the hash table/size of the hash table

Skip lists

A skip list is an ordered data structure that supports node search with average O(logN) and worst O(n) complexity. If an ordered set contains many elements, Redis will use the skip list as the underlying implementation of the ordered set:

Each time a new skip list node is created, Redis randomly generates a value between 1 and 32 as the size of the Lavel array, which is the size (or height) of the layer. A forward pointer can be used to quickly reach the nearest layer between layers, or a backward pointer (BW) can be used to back up to the previous node.

The point value of a node is a floating-point number of type double, and all the nodes of a skip list are arranged in order of point value from lowest to highest. A node’s member object is a pointer to a string object. Nodes with the same score are sorted by the size of the member object in lexicographical order, with smaller nodes taking precedence.

Set of integers

The set of integers is used when a set contains only integer numeric elements and there are not many of them:

The encoding attribute may be INTSET_ENC_INT16/INTSET_ENC_INT32/INTSET_ENC_INT64. If we are adding a new element to the set and the new element is of a longer type than all the current types in the set, we need to start with the set of integersupgradeIn order to add new elements (integer collections do not support downgrading) to save memory.

Compress lists

Compressed lists are developed by Redis to save memory. A compressed list can contain any number of nodes, and each node can hold a byte array or integer value:

Among them:

  • Zlbytes: indicates the total length of the compressed list
  • Zltail: indicates the offset of the last node of the storage table
  • Zllen: indicates the number of nodes in the compressed list

By compressing lists, Redis can further save space for simple data.

Extend data types

Redis also provides three special types of Bitmap, HyperLogLog and GEO for special scenarios such as massive computing.

  • Bitmap itself uses String type as a data type of binary state statistics realized by the underlying data structure. String type is a byte array that will be saved as binary. Redis uses each bit of the byte array to represent the binary state of an element.
  • HyperLogLog is a type of data set used in statistical techniques. When the number of elements in the set is very large, the space required to calculate the cardinality is always fixed. It is often used in various statistical scenarios.
  • GEO is a data type oriented to LBS service scenarios. It uses GeoHash encoding to convert the latitude and longitude to the weight score of elements in the sorting set, which is equivalent to using the “range” search of the sorting set

conclusion

This article focuses on a brief analysis of Redis data structures, including the underlying structure of commonly used data types and the real secret of why Redis is so fast.