The underlying implementation principle of the five data structures of Redis

1. Introduction to the two-tier [data structure] of Redis

One of the reasons for the high performance of redis is that each data structure is specially designed and supported by one or more data structures, relying on these flexible data structures to improve the performance of reading and writing. If you want to understand the data structure of redis, you can discuss it from two different levels:

(1) The first level is from the user’s point of view. This level is also the calling interface exposed by Redis to the outside world, such as:

  • string
  • list
  • hash
  • set
  • sorted set

(2) The second level, from the perspective of internal implementation, belongs to the lower-level implementation, such as:

  • dict
  • sds
  • ziplist
  • quicklist
  • ship art
  • intset

The focus of this article is to discuss the second level:

  • Internal implementation of Redis data structures
  • The relationship between the data structures at these two levels: How Redis implements higher-level data structures at the first level by combining various basic data structures at the second level

When discussing the internal implementation of any system, we must first clarify its design principles, so that we can more deeply understand the real intention of why it is designed the way it is. In the discussion that follows in this article, we mainly focus on the following points:

  • storage efficiency. Redis is dedicated to storing data, and its main consumption of computer resources is memory, so saving memory is a very, very important aspect of it. This means that Redis must have carefully considered issues such as compressing data and reducing memory fragmentation.
  • Fast response time. The opposite of fast response time is high throughput. Redis is used to provide online access, and the response time of a single request is very high. Therefore, fast response time is a more important goal than high throughput.
  • single thread. The performance bottleneck of Redis is not CPU resources, but memory access and network IO. The advantage of using a single-threaded design is that it greatly simplifies the implementation of data structures and algorithms. On the contrary, Redis achieves high-speed concurrent access through mechanisms such as asynchronous IO and pipelining. Obviously, the single-threaded design also puts forward higher requirements for the fast response time of a single request.

2. redisObject: a bridge between two-tier data structures

Detailed explanation of redisObject data structure: http://zhangtielei.com/posts/blog-redis-robj.html

1. What is redisObject:

From the perspective of Redis users, a Redis node contains multiple databases (16 by default in non-cluster mode, only 1 in cluster mode), and a database maintains the mapping from key space to object space relationship, the key of this mapping relationship is of type string, and the value can be of various data types, such as: string, list, [hash], and a database maintains the mapping from key space to object space relationship, the key of this mapping relationship is of type string, and the value can be of various data types, such as: string, list, [hash] , set, sorted set, etc.

From the perspective of the internal implementation of Redis, the mapping relationship in the database is maintained by a dict. It is enough to express the key of a dict with a fixed data structure, which is the dynamic [string] sds; while the value is more complicated. In order to store different types of values ​​in the same dict, a general data structure is required. This general data structure is robj, whose full name is redisObject

for example:

  • If value is of type list, then its internal storage structure is a quicklist or a ziplist
  • If value is of type string, then its internal storage structure is generally an sds. But if the value of the string type value is a number, then Redis will convert it to a long type internally for storage, thereby reducing memory usage.

Therefore, an robj can represent both an sds, a quicklist, and even a long.

  1. Redis data structure definition: (based on Redis3.2 version)

/* Object types */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */

#define LRU_BITS 24
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robes;

(1) An robj contains the following five fields:

  • type: The data type of the object. Occupies 4 bits. There are five possible values: OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH, which correspond to the five data structures exposed by Redis.
  • encoding: The internal representation of the object (may also be called encoding). Occupies 4 bits. There are 10 possible values, namely the 10 OBJ_ENCODING_XXX constants in the preceding code.
  • lru: Used for LRU replacement algorithm, occupying 24 bits. This is not the focus of our discussion here, so ignore it for the time being.
  • refcount: Reference count. It allows robj objects to be shared under certain circumstances.
  • ptr: data pointer. point to the real data. For example, an robj representing a string, its ptr may point to an sds structure; an robj representing a list, its ptr may point to a quicklist.

(2) Description of the encoding field:

The special thing to look at here is the encoding field. For the same type, it may also correspond to different encodings, which means that the same data type may have different internal representations. Different internal representations will have different memory usage and search performance.

When type = OBJ_STRING, it means that the robj stores a string, and encoding can be one of the following three:

  • OBJ_ENCODING_RAW: string uses the native representation, that is, it is represented by sds.
  • OBJ_ENCODING_INT: string is represented by numbers, which is actually a long type.
  • OBJ_ENCODING_EMBSTR: string is represented by a special embedded sds.

When type = OBJ_HASH, it means that this robj stores a hash, and encoding can be one of the following two:

  • OBJ_ENCODING_HT: hash is represented by a dict
  • OBJ_ENCODING_ZIPLIST: hash is represented by a ziplist

(3) Value description of 10 encodings:

  • OBJ_ENCODING_RAW: The most native representation. In fact, only the string type will use this encoding value (represented as sds).
  • OBJ_ENCODING_INT: Represented as a number. Actually represented by long.
  • OBJ_ENCODING_HT: Represented as a dict.
  • OBJ_ENCODING_ZIPMAP: is an old representation that is no longer used. Only available in versions less than Redis 2.6.
  • OBJ_ENCODING_LINKEDLIST: Also an old representation, no longer used.
  • OBJ_ENCODING_ZIPLIST: Represented as ziplist.
  • OBJ_ENCODING_INTSET: Represented as intset. Used for set data structures.
  • OBJ_ENCODING_SKIPLIST: Express as skiplist. For the sorted set data structure.
  • OBJ_ENCODING_EMBSTR: Represented as a special embedded sds.
  • OBJ_ENCODING_QUICKLIST: Express as quicklist. For list data structure.

  • The role of robj:

  • redisObject is the first-level data structure exposed by Redis: string, list, hash, set, sorted set, and which second-level data structures (dict, sds, ziplist) correspond to the underlying implementation of each data structure , quicklist, skiplist, etc.), are distinguished by different encodings. It can be said that robj is a bridge connecting the data structures of the two levels.

  • Provides a unified representation for multiple data types.
  • Allows different internal representations of the same type of data to maximize memory savings in some cases.
  • Support for object sharing and reference counting. When objects are shared, only one memory copy is occupied, further saving memory.

Third, the first layer of data structure

1、String:

String is the simplest data type and is generally used for caching of complex counting functions: the number of tweets, the number of followers, etc.

(1) The underlying implementation: dynamic string sds or long

The internal storage structure of String is generally sds (Simple Dynamic String), but if the value of a String type value is a number, then Redis will internally convert it to long type for storage, thereby reducing memory usage.

  • To be precise, String is represented by an robj in Redis.
  • robj used to represent String may be encoded into 3 internal representations: OBJ_ENCODING_RAW, OBJ_ENCODING_EMBSTR, OBJ_ENCODING_INT. The first two encodings use sds to store, and the last OBJ_ENCODING_INT encoding directly stores the string as a long type.
  • When performing incr, decr and other operations on a string, if it is OBJ_ENCODING_INT encoded internally, then addition and subtraction operations can be performed directly; if it is internally encoded by OBJ_ENCODING_RAW or OBJ_ENCODING_EMBSTR, then Redis will first try to convert the string stored in sds into long type, if it can be transferred successfully, then perform addition and subtraction operations.
  • Execute the commands append, setbit, getrange to a string whose internal representation is long, and still operate on the value of the string (ie, the string represented in decimal), instead of operating on the internal representation of long. For example, the string “32”, if interpreted as a character array, contains two characters whose ASCII codes are 0x33 and 0x32 respectively. When we execute the command setbit key 7 0, it is equivalent to changing the character 0x33 to 0x32, so that the value of the string becomes “22”. And if the string “32” is interpreted as an internal 64-bit long type, then it is 0x0000000000000020. On this basis, the setbit bit operation is performed, and the result is completely wrong. Therefore, in the implementation of these commands, the long type is first converted into a string and then the corresponding operation is performed.

*2、Hash:*

Hash is suitable for storing objects, because each attribute of an object corresponds to each field of a hash structure, and a field in the object can be easily manipulated.

(1) The underlying implementation: compressed list ziplist or dictionary dict

When the amount of data is small, the bottom layer of the hash will use the compressed list ziplist to store the data, that is, when the following two conditions are met at the same time:

  • hash-max-ziplist-entries 512: When the number of data items (ie filed-value pairs) in the hash is less than 512
  • hash-max-ziplist-value 64: When the length of any value inserted in the hash is less than 64 bytes

When the above two conditions cannot be met at the same time, the underlying ziplist will be converted into a dict. The reason for this design is that when the ziplist becomes very large, it has the following disadvantages:

  • The realloc operation caused by each insertion or modification has a greater probability of causing a memory copy, thereby reducing performance.
  • Once a memory copy occurs, the cost of the memory copy increases accordingly, because a larger piece of data needs to be copied.
  • When there are too many data items in the ziplist, the performance of searching for the specified data item on it will become very low, because the search on the ziplist needs to be traversed.

In short, ziplist is originally designed to form a continuous memory space with various data items next to each other. This structure is not good at modifying operations. Once the data is changed, the memory realloc will be triggered, which may result in a memory copy.

*3、List:*

The implementation of list is a doubly linked list, which is often used as a queue. It supports push and pop operations at both ends of the linked list, and the time complexity is O(1); it also supports access operations at any position in the linked list, but The list needs to be traversed, and the time complexity is O(n).

There are many application scenarios of list, such as Weibo’s follow list, fan list, message list and other functions can be implemented with the list structure of Redis. You can use the lrange command to do redis-based paging.

(1) The underlying implementation before Redis3.2: compressed list ziplist or doubly circular linked list linkedlist

When the amount of data stored in the list is small, the ziplist will be used to store the data, that is, the following two conditions are met at the same time:

  • The number of data in the list is less than 512
  • The length of each element stored in the list is less than 64 bytes

When the above two conditions cannot be met at the same time, the list is implemented through a doubly [circular linked list] linkedlist

(2) The underlying implementation of Redis3.2 and later: quicklist

quicklist is a doubly linked list, and it is a doubly linked list based on ziplist, each node of quicklist is a ziplist, combining the advantages of doubly linked list and ziplist

*4、Set:*

Set is an unordered collection that stores non-repeating values. It can be used for global deduplication and provides the function of judging whether an element is in the set collection, which is also not available in list. Based on set, operations of intersection, union, and difference can be realized, and functions such as common preferences, all preferences, and unique preferences can be calculated.

(1) The underlying implementation method: ordered integer set intset or dictionary dict

When the stored data meets the following two conditions at the same time, Redis uses the integer set intset to implement the set data type:

  • The stored data are all integers
  • The number of stored data elements is less than 512

When these two conditions cannot be met at the same time, Redis uses dict to store the data in the collection

*5、Sorted Set:*

Compared with the set, the Sorted set has one more weight parameter score, and the elements in the set can be arranged according to the score. It can be used as a leaderboard application and take the TOP N operation. In addition, sorted sets can be used to do delayed tasks. The last application is to do range lookups.

(1) The underlying implementation: compressed list ziplist or zset

When the data of the sorted set meets the following two conditions at the same time, the compressed list ziplist is used to implement the sorted set

  • The number of elements should be less than 128, that is, the ziplist data item should be less than 256
  • Each data size in the collection is less than 64 bytes

When these two conditions cannot be met at the same time, Redis uses zset to implement sorted set, which contains a dict + a skiplist. dict is used to query data to score (score) correspondence, and skiplist is used to query data based on score (probably a range lookup).

Fourth, the data structure of the second layer

1、sds:

Detailed explanation of sds data structure: http://zhangtielei.com/posts/blog-redis-sds.html

(1) What is sds:

The full name of sds is Simple Dynamic String, which has the following notable features:

① The memory can be dynamically expanded. The content of the string represented by sds can be modified or appended.

② The method of pre-allocating redundant space is used to reduce the frequent allocation of memory, thereby optimizing the growth operation of strings

③ Binary Safe. sds can store arbitrary binary data, not just printable characters.

④ Compatible with traditional C language string type.

(2) Data structure of sds:

sds is Binary Safe, it can store arbitrary binary data, and cannot use the character ‘\0’ to identify the end of the string like C language strings, so it must have a length field. But where is this length field? Actually sds also contains a header structure:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

There are 5 types of headers in sds. The reason why there are 5 types is to allow different lengths of strings to use headers of different sizes. This way, short strings can use smaller headers, saving memory.

Therefore, the complete structure of the sds string consists of two parts, the header and the character array adjacent to each other in the memory address:

① header: Except for sdshdr5, a header structure contains 3 fields: the real length of the string len, the maximum capacity of the string alloc and flags, flags always occupy one byte. The lowest 3 bits are used to indicate the type of header.

② Character array: The length of the character array is equal to the maximum capacity + 1, and it stores the really valid string data. After the real string data, there are free unused bytes (usually padded with byte 0), allowing limited backward expansion of the string data without reallocating memory. After the real string data, there is also a NULL terminator, the ‘\0’ character with ASCII code 0. This is for compatibility with legacy C strings. The reason why the length of the character array is 1 byte longer than the maximum capacity is that there is still 1 byte to store the NULL terminator when the length of the string reaches the maximum capacity.

There are 5 types of headers, and there are constant definitions in sds.h:

  • define SDS_TYPE_5  0

  • define SDS_TYPE_8  1

  • define SDS_TYPE_16 2

  • define SDS_TYPE_32 3

  • define SDS_TYPE_64 4

The header of the sds string is actually hidden in front of the real string data (low address direction). Such a definition has the following advantages:

  • The header is adjacent to the data, so there is no need to divide it into two memory spaces for separate allocation, which is beneficial to reduce memory fragmentation and improve storage efficiency
  • Although the header has multiple types, sds can be expressed with a unified char *. And it maintains type compatibility with traditional C language strings. If a printable string is stored in an sds, then we can directly pass it to a C function, such as using strcmp to compare the size of the string, or using printf to print.

(3) Encoding and decoding process of String robj:

The encoding and decoding process of string objects of type OBJ_STRING is very important in Redis and is widely used.

When we execute the set command of Redis, Redis first represents the received value (string type) as a robj object with type = OBJ_STRING and encoding = OBJ_ENCODING_RAW, and then performs an encoding process before storing it in the internal storage, trying to Express it as another more memory-efficient encoding. The core code of this process is the tryObjectEncoding function in object.c.

When we need to get the value of the string, such as when executing the get command, we need to perform the opposite of the encoding process described earlier – decoding. The core code of this decoding process is the getDecodedObject function in object.c.

For the detailed description of the core code tryObjectEncoding function of encoding and the core code getDecodedObject function of decoding, please read this article: Redis Internal Data Structure Detailed Explanation (3) – robj – Tie Lei’s personal blog

(4) Why does Redis’ String underlying data structure use sds:

Seeing this, we can roughly understand why String’s underlying data structure uses sds:

① High performance:

The sds data structure is mainly composed of three attributes: len, alloc, and buf[], of which buf[] is the char type array that actually stores the string; len represents the length of the string stored in the buf[] array. Since len is used to record the length of the saved string, when obtaining the length of the string, it is not necessary to traverse the array from front to back, and the value of len can be directly obtained.

② Memory pre-allocation to optimize the growth of strings:

When the data needs to be modified, it will first check whether the len of the sds space is satisfied. If it is not satisfied, the space will be automatically expanded, and then the modification will be performed. When sds allocates space, it will also allocate additional unused space free. Next time you modify it, check whether the unused space free is satisfied. If it is satisfied, you do not need to expand the space. Through the space pre-allocation strategy, the number of memory reallocations caused by the continuous growth of strings is effectively reduced.

Rules for additional allocation of free space:

  • If the len value is less than 1M after the sds string is modified, the size of the extra allocated unused space free is len 
  • If the len value is greater than or equal to 1M after the sds string is modified, the size of the extra allocated unused space free is 1M

③ Lazy space recovery, optimize the shortening operation of strings:

When the SDS string is shortened, memory reallocation will not be performed immediately to reclaim the excess space. If there is a subsequent growth operation, it can be used directly.

2、dict:

Detailed explanation of dict data structure: http://zhangtielei.com/posts/blog-redis-dict.html

A dict is a data structure used to maintain key-value mappings. All key-to-value mappings in a Redis database are maintained using a dict. However, this is just one use of it in Redis, it is used in many places in Redis. For example, the hash structure of Redis, when it has more fields, will use dict to store. For another example, Redis uses dict and skiplist together to maintain a sorted set.

dict is essentially to solve the search problem in the algorithm. It is an algorithm based on a hash table. The time complexity of the query is close to O(1). It uses a hash function and calculates the key to find the position in the hash table, uses the zipper method to resolve conflicts , and automatically expands the memory , causing rehashing ), in order to avoid re-hashing all keys at one time during expansion , Redis adopts a method called incremental re-hashing, which distributes the re-hashing operation to each addition, deletion and modification of dict Check the operation. This method can only re-hash a small number of keys at a time, and does not affect the operation of dict between each re-hashing. The reason why dict is designed this way is to avoid a sharp increase in the response time of a single request during rehashing, which is in line with the design principle of “fast response time” mentioned earlier.

When the load factor is greater than 1, Redis will trigger the expansion to expand the hash table to about 2 times the original size; when the data is dynamically reduced, in order to save memory, when the load factor is less than 0.1, Redis will trigger the shrink. Shrinks to about twice the size of the number of data in the dictionary.

3、ziplist:

Detailed explanation of ziplist data structure: http://zhangtielei.com/posts/blog-redis-ziplist.html

A ziplist is a specially encoded doubly linked list that can be used to store strings or integers, where the integers are encoded in their true binary representation rather than as a sequence of strings. pushIt can provide and popoperate on both ends of the table in O(1) time complexity .

In an ordinary doubly linked list, each item in the linked list occupies a separate piece of memory and is connected by an address pointer, but this method will bring a lot of memory fragmentation, and the address pointer will also occupy additional memory. And ziplist uses a whole block of contiguous memory, and stores each item in the table in the consecutive address space before and after, similar to an array. In addition, in order to save memory in details, ziplist adopts a variable-length encoding method for the storage of values, which roughly means that for large integers, more bytes are used to store, and for small integers, less is used. bytes to store.

In general , ziplist uses a continuous memory space to store data, and adopts a variable-length encoding method to support the storage of data of different types and sizes, saving more memory, and the data is stored in a continuous memory space, read The extraction efficiency is also very high.

4、quicklist:

Detailed explanation of quicklist data structure: http://zhangtielei.com/posts/blog-redis-quicklist.html

(1) What is a quicklist:

quicklist is a doubly linked list based on ziplist, each node of quicklist is a ziplist , for example, a quicklist contains 3 nodes, if the ziplist of each node contains 4 data items, then externally, this list is A total of 12 data items are included. Why is the structure of quicklist designed this way? To sum up, it is probably another compromise between space and time :

  • Doubly linked list facilitates push and pop operations at both ends of the list, but its memory overhead is relatively large. First, in addition to saving data on each node, it also needs to save two additional pointers; secondly, each node of the doubly linked list is a separate memory block, and the addresses are not continuous. If there are too many nodes, it is easy to generate memory fragmentation.
  • Since ziplist is a whole block of contiguous memory, the storage efficiency is very high. However, it is not conducive to modification operations, and each data change will trigger a realloc of memory. Especially when the ziplist is very long, a realloc may result in a large batch of data copies, further reducing performance.

So, combining the advantages of doubly linked list and ziplist, quicklist came into being.

(2) Configuration of the length of each ziplist in the quicklist:

However, this also brings up a new question: how long does a quicklist node contain a suitable ziplist? For example, to store 12 data items, either a quicklist contains 3 nodes, and the ziplist of each node contains 4 data items, or a quicklist contains 6 nodes, and the ziplist of each node is Contains 2 data items.

This is yet another challenge to find a balance. We only analyze from the storage efficiency:

  • The shorter the ziplist on each quicklist node, the more fragmented the memory. There are too many memory fragments, and there may be many small fragments that cannot be used in the memory, thereby reducing the storage efficiency. The extreme of this situation is that the ziplist on each quicklist node contains only one data item, which degenerates into an ordinary doubly linked list.
  • The longer the ziplist on each quicklist node, the more difficult it is to allocate a large block of contiguous memory space for the ziplist. It’s possible to have lots of small chunks of free space in memory (they add up to a lot), but you can’t find one big enough to allocate to the ziplist. This also reduces storage efficiency. The extreme of this situation is that the entire quicklist has only one node, and all data items are allocated in the ziplist of this only one node. This actually degenerated into a ziplist

It can be seen that the ziplist on a quicklist node should maintain a reasonable length. So how long is reasonable? This may depend on the specific application scenario. In fact, Redis provides a configuration parameter list-max-ziplist-sizeso that users can adjust it according to their own situation.

list-max-ziplist-size -2

This parameter can take a positive or negative value.

When a positive value is taken, it means that the length of the ziplist on each quicklist node is limited according to the number of data items. For example, when this parameter is set to 5, it means that the ziplist of each quicklist node contains at most 5 data items.

When taking a negative value, it means that the length of the ziplist on each quicklist node is limited according to the number of bytes occupied. At this time, it can only take five values ​​from – 1 to – 5, and the meaning of each value is as follows:

  • -5: The size of the ziplist on each quicklist node cannot exceed 64 Kb. (Note: 1kb => 1024 bytes)
  • -4: The size of the ziplist on each quicklist node cannot exceed 32 Kb.
  • -3: The size of the ziplist on each quicklist node cannot exceed 16 Kb.
  • -2: The size of the ziplist on each quicklist node cannot exceed 8 Kb. (-2 is the default value given by Redis)
  • -1: The size of the ziplist on each quicklist node cannot exceed 4 Kb.

5、intset:

Detailed explanation of intset data structure: http://zhangtielei.com/posts/blog-redis-intset.html

(1) What is intset:

intset is an ordered set of integers, which facilitates binary search to quickly determine whether an element belongs to this set. It is somewhat similar to ziplist in memory allocation. It is a continuous block of memory space, and different encodings are adopted for large integers and small integers (by absolute value), and the use of memory is optimized as much as possible.

(2) The data structure of intset:

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

The meaning of each field is as follows:

  • encoding: Data encoding, indicating that each data element in the intset is stored in several bytes. It has three possible values: INTSET_ENC_INT16 means 2 bytes per element, INTSET_ENC_INT32 means 4 bytes per element, INTSET_ENC_INT64 means 8 bytes per element. Therefore, integers stored in intset can only occupy at most 64 bits.
  • length: Indicates the number of elements in the intset. encodingand lengthtwo fields form the header of the intset.
  • contents: is a flexible array member , which means that the header of the intset is followed by the data elements. The total length of this array (that is, the total number of bytes) is equal to encoding * length. Flexible arrays appear in the definition of many data structures in Redis (such as sdsquicklistskiplist ) to express an offset. contentsIt needs to allocate space for it separately, and this part of the memory is not included in the intset structure.

One thing to note is that an intset may change its data encoding as data is added:

  • Initially, the newly created intset uses the smallest memory INTSET_ENC_INT16 (value 2) as the data encoding.
  • Each time a new element is added, whether to upgrade the data encoding is determined according to the size of the element.

(3) Compared with intset and ziplist:

  • ziplist can store arbitrary binary strings, while intset can only store integers.
  • ziplist is unordered, while intset is ordered from small to large. Therefore, searching on ziplist can only be traversed, while on intset, binary search can be performed, and the performance is higher.
  • ziplist can perform different variable-length encodings for each data item (each data item has a data length field in front of it len), while intset can only use a unified encoding ( encoding) as a whole.

6、ship art:

Detailed explanation of skiplist data structure: http://zhangtielei.com/posts/blog-redis-skiplist.html

(1) What is a skip table:

The skip table is an ordered linked list that can perform binary search. It adopts the design idea of ​​changing space for time. The skip table adds a multi-level index to the original ordered linked list (for example, every two nodes extract a node to the previous level.) for fast search by index. The skip table is a dynamic data structure that supports fast insertion, deletion, and lookup operations. The time complexity is O(logn) and the space complexity is O(n). The skip table is very flexible and can effectively balance execution efficiency and memory consumption by changing the index construction strategy.

① Delete operation of skip list: In addition to deleting the nodes in the original linked list, the nodes in the index should also be deleted.

② After inserting elements, the dynamic update of the index: continuously inserting data into the jump table, if the index is not updated, there may be a situation where there is a lot of data between two index nodes, or even degenerate into a singly linked list. In response to this situation, when we add elements, we pass a random function and choose to insert this data into the partial index layer. For example, if the random function generates a value K, then we add this node to the index of the K level from the first level to the Kth level

Leave a Comment

Your email address will not be published. Required fields are marked *