Shulou(Shulou.com)06/01 Report--

Preface

Last article Redis chat (1): building a knowledge graph introduces the basic concepts, advantages and disadvantages of redis and its memory elimination mechanism. I believe you have a preliminary understanding of redis. Many application scenarios of the Internet have the shadow of Redis, and what it can do is far beyond our imagination. What is the underlying data structure of Redis, and why can it do so many things? This article will explore the underlying data structures of Redis and commonly used commands.

The knowledge brain map of this paper is as follows:

1. The data model of Redis

Using key-value pair name: "Xiaoming" to show the data model of Redis is as follows:

DictEntry: in some programming languages, the data structure of key-value pairs is called a dictionary, while in Redis, each key-value key-value pair is assigned a dictionary entity, which is "dicEntry". DicEntry includes three parts: key pointer, val pointer, next pointer, next pointer to the next dicteEntry to form a linked list, this next pointer can link multiple key-value pairs with the same hash value together, through the chain address method to solve the problem of hash conflict sds: Simple Dynamic String, simple dynamic string, storing string data. The five common types of redisObject:Redis are all stored in RedisObject, and the type field in redisObject indicates the data type of the value (that is, five basic types). The ptr field points to the address where the object is located.

RedisObject object is very important, Redis object type, internal coding, memory recovery, shared object and other functions are based on RedisObject object to achieve.

The advantage of this design is that you can set up a variety of different data structures for five commonly used types according to different scenarios, so as to optimize the efficiency of objects in different scenarios.

Redis uses jemalloc as the default memory allocator to reduce memory fragmentation. In the 64-bit system, jemalloc divides the memory space into three ranges: small, large and large; each range is divided into many small memory block units; when Redis stores data, it will choose the most appropriate memory block to store.

II. Data structures supported by Redis

What are the data structures supported by Redis?

If the answer is String, List, Hash, Set, Zset, these five common basic data types of redis, each data type also contains a variety of data structures.

Use the encoding instruction to see the data structure of a value. For example:

127.0.1 embstr 6379 > set name tomOK127.0.0.1:6379 > object encoding name "embstr"

The name value set here is tom, and its data structure is embstr, which will be explained in more detail when the string is described below.

127.0.1 int 6379 > set age 18OK127.0.0.1:6379 > object encoding age "int"

The following table summarizes all the data structure types in Redis:

Underlying data structure encoding constant object encoding instruction output integer type REDIS_ENCODING_INT "int" embstr string type REDIS_ENCODING_EMBSTR "embstr" simple dynamic string REDIS_ENCODING_RAW "raw" dictionary type REDIS_ENCODING_HT "hashtable" double-ended linked list REDIS_ENCODING_LINKEDLIST "linkedlist" compressed list REDIS_ENCODING_ZIPLIST "ziplist" integer collection REDIS_ENCODING_INTSET "intset" jump table and dictionary REDIS_ENCODING_SKIPLIST "skiplist"

Supplementary explanation

If the interviewer asks: what are the data types of redis?

Answer: String, list, hash, set, zet

Generally speaking, this answer is correct. It is also mentioned earlier that the data types of redis do contain these five data types, but careful students must have found the five data types that they said are "commonly used". In fact, with the continuous update and improvement of Redis, there are already more than 5 data types of Redis.

Log on to the official website of redis to open the official introduction of data types:

Https://redis.io/topics/data-types-intro

It is found that Redis supports not only 5 data structures, but 8 data structures, and the latter three types are:

Bit array (or bitmap for short): use special commands to deal with string values, such as bit array: you can set and clear individual bits, set all bits to 1, find the first bit or unset bit, and so on. HyperLogLogs: this is a probabilistic data structure used to estimate the cardinality of a set. Don't be afraid, it's easier than it looks. Streams: only additional collections of map-like entries that provide abstract log data types.

This paper mainly introduces five commonly used data types, and the above three will be explored together later.

2.1 string string

The string type is the most commonly used data type in redis. In Redis, the string can be modified, and at the bottom it exists in the form of an array of bytes.

A string in Redis is called a simple dynamic string "SDS". This structure is very similar to ArrayList in Java and its length is dynamically variable.

Struct SDS {T capacity; / / Array capacity T len; / / Array length byte [] content; / / array contents}

Content [] stores the contents of the string, capacity represents the length allocated to the array, and len represents the actual length of the string.

There are three encoding types of strings: int, embstr, and raw, as shown in the table above, so what is the difference between these three encoding types?

Int encoding: holds integer values that can be represented by the long type.

Raw encoding: saves strings longer than 44 bytes (39 bytes before the redis3.2 version, followed by 44 bytes).

Embstr encoding: saves strings less than 44 bytes long (39 bytes before the redis3.2 version, 44 bytes after that).

Set a value to test:

127.0.0.1 int > set key1 wealwaysbyhappyOK127.0.0.1:6379 > object encoding key1 "embstr" 127.0.0.1 > set key2 aOK127.0.0.1:6379 > strlen key2 (integer) 39127.0.0.1 > object encoding key2 "embstr" 127.0.0.1 > set key2 aOK127.0.0.1:6379 > object encoding key2 "raw" 127.0.0.1. 0.0.1 45raw 6379 > strlen key2 (integer) comparison between 45raw type and embstr type

The structure of embstr coding:

The structure of raw coding:

Both embstr and raw are made up of redisObject and sds. The difference is that embstr's redisObject and sds are contiguous and only need to allocate memory once using malloc, while raw needs to allocate memory for redisObject and sds respectively, that is, it needs to allocate memory twice.

In comparison, embstr allocates memory once less, which is more convenient. But embstr also has obvious disadvantages: to increase the length, both redisObject and sds need to reallocate memory.

The structural differences between embstr and raw are described above. Here comes the point.

Why did you choose 44 as the demarcation point between the two codes? Why 39 before version 3.2? How do you get these two values?

1) calculate the size of bytes occupied by RedisObject

Struct RedisObject {int4 type; / / 4bits int4 encoding; / / 4bits int24 lru; / / 24bits int32 refcount; / / 4bytes = 32bits void * ptr; / / 8bytes.64murbit system} type: different redis objects will have different data types (string, list, hash, etc.), type record types, and 4bits will be used. Encoding: stores the encoded form, using 4bits. Lru: use 24bits to record the LRU information of an object. Refcount: reference counter, using 32bits. * ptr: the pointer points to the specific content of the object, and 64bits is required.

Calculation: 4 + 4 + 24 + 32 + 64 = 128bits = 16bytes

The first step is done. The RedisObject object header takes up a 16-byte size, which is usually fixed.

2) calculation of byte size occupied by sds

Older version:

Struct SDS {unsigned int capacity; / / 4byte unsigned int len; / / 4byte byte [] content; / / inline array with length capacity}

The unsigned int here is 4 bytes, which adds up to 8 bytes.

If the memory allocated by the memory allocator jemalloc exceeds 64 bytes, it is considered a large string and raw encoding is used.

As mentioned earlier, the string of content in the SDS structure is a string that ends with a byte\ 0. The reason for adding such a byte is to facilitate the direct use of glibc's string processing function and to facilitate string debugging and printout. So we have to subtract 1 byte.

64byte-16byte-8byte-1byte = 39byte

New version:

Struct SDS {int8 capacity; / / 1byte int8 len; / / 1byte int8 flags; / / 1byte byte [] content; / / inline array with length capacity}

Here unsigned int becomes uint8_t, uint16_t. Plus a char flags logo, using a total of only 3 bytes. This is equivalent to optimizing the memory usage of sds, and the corresponding memory used to store strings becomes larger.

Then calculate:

64byte-16byte-3byte-1byte = 44byte.

Summary:

Therefore, the maximum string length that embstr can hold after redis 3.2 is 44, compared with 39 before. The reason for the length change is the optimization of memory in SDS.

2.2 List

The bottom layer of the List object in Redis is implemented by quicklist (Quick list), which supports the addition of elements from the head and tail of the chain table, and can get the element content at a specified location.

So how is the bottom layer of the Quick list implemented? Why can you achieve such fast performance?

Rome was not built in a day, and quicklist was not built in a day. At first, the underlying list of redis was ziplist (compressed list) or linkedlist (double-ended list). First, the two data structures are introduced respectively.

Ziplist compressed list

When a list contains only a small number of list items and is a small integer value or a short string, redis uses ziplist (compressed list) as the underlying implementation of the list key.

Test:

127.0.0.1 object encoding dotahero 6379 > rpush dotahero sf qop doom (integer) 3127.0.0.1 > object encoding dotahero "ziplist"

The old version of redis is tested here, adding three heroes, qop Queen of pain, sf Shadow, and doom Doombringer, to the list of dota heroes, and ziplist is used for data structure coding.

As the name implies, the compressed list is compressed, and there is no pointer between each node, but multiple elements are adjacent and there are no gaps. So ziplist is developed by Redis to save memory and is a sequential data structure composed of a series of specially encoded continuous memory blocks. The specific structure is relatively complex, if you are interested, you can understand it in depth.

Struct ziplist {int32 zlbytes; / / the whole compressed list occupies the number of bytes int32 zltail_offset; / / the offset of the last element from the starting position of the compressed list, used to quickly locate the last node int16 zllength; / / number of elements T [] entries; / / element content list, one by one compact storage int8 zlend; / / mark the end of the compressed list, the value is always 0xFF}

Double-ended list (linkedlist)

The double-ended list is familiar to everyone, and the double-ended list here is very similar to the linkedlist in java.

It can be seen from the figure that Redis's linkedlist double-ended linked list has the following characteristics: the node has prev, next pointer, head pointer and tail pointer, and the complexity of obtaining the front node, the post node, the header node and the footer node, and the length is all O (1).

The compressed list takes up less memory, but it is a sequential data structure, and the operation of inserting and deleting elements is more complex, so the compressed list is suitable for the case of relatively small data, when there is more data, efficient insertion and deletion of double-ended lists is still a better choice.

In the eyes of Redis developers, the choice of data structure should be extreme in terms of time and space, so they combine compressed lists and double-ended lists into one to create a quick list (quicklist). Like hashmap in java, it combines the advantages of arrays and linked lists.

Quick list (quicklist) rpush: listAddNodeHead-O (1) lpush: listAddNodeTail-O (1) push:listInsertNode-O (1) index: listIndex-O (N) pop:ListFirst/listLast-O (1) llen:listLength-- O (N)

Struct ziplist {...} struct ziplist_compressed {int32 size; byte [] compressed_data;} struct quicklistNode {quicklistNode* prev; quicklistNode* next; ziplist* zl; / / points to the total number of bytes in the compressed list int16 count; / / ziplist the number of elements in the int16 count; / / ziplist storage form 2bit, the native byte array or LZF compressed storage.} struct quicklist {quicklistNode* head QuicklistNode* tail; long count; / / Total number of elements int nodes; / / number of ziplist nodes int compressDepth; / / LZF algorithm Compression depth.}

The default compression depth for quicklist is 0, which means no compression. The actual depth of compression is determined by the configuration parameter list-compress-depth. In order to support fast push/pop operations, the first and last ziplist of the quicklist are not compressed, and the depth is 1. If the depth is 2, the first ziplist and the second ziplist of the quicklist are not compressed.

2.3 Hash

The underlying implementation of the Hash data type is ziplist (compressed list) or dictionary (also known as hashtable or hash table). The choice of compressed lists or dictionaries here is also determined by the number of elements.

As shown in the figure hset, there are three key-value pairs, and when the number of bytes of each value does not exceed 64, the default data structure is ziplist.

When we add data with a value of more than 64 bytes, the default data structure has become hashtable.

Ziplist (compressed list) is used only if the Hash object satisfies both of the following conditions:

The number of elements in the hash is less than 512; the key and value strings of all key-value pairs in the hash are less than 64 bytes in length.

As you have just learned about the compressed list, hashtables is similar to hashmap before jdk1.7. Hashmap uses the chain address method to solve the problem of hash conflict.

Dictionaries in Redis

The dict structure in redis contains two hashtable inside, usually only one hashtable has a value. However, when the dict is expanded and reduced, a new hashtable needs to be allocated, and then the gradual relocation is carried out. In this case, the two hashtable stores the old hashtable and the new hashtable respectively. When the relocation is over, the old hashtable is deleted and the new hashtable is replaced.

2.4 Set

The underlying Set data type can be intset (set of integers) or hashtable (hash table, also known as hash table).

When the data are all integers and the quantity is small, intset is used as the underlying data structure; when there is data other than integers or the amount of data increases, hashtable is used as the underlying data structure.

127.0.0.1 sadd myset 6379 > 1112222333 (integer) 3127.0.0.1 object encoding myset "intset" 127.0.0.1 object encoding myset 6379 > sadd myset (integer) 1127.0.1 purl 6379 > object encoding myset "hashtable"

The data structure of inset is as follows:

Typedef struct intset {/ / Encoding uint32_t encoding; / / the number of elements contained in the collection uint32_t length; / / an array of saved elements int8_t contents [];} intset

The underlying implementation of intset is an array of ordered, non-repeating numbers. The integer type of intset can be 16-bit, 32-bit, 64-bit. If all the integers in the array are 16-bit long and a 32-bit integer is added, the entire 16-bit array will be upgraded to a 32-bit array. Upgrading can improve the flexibility of intset and save memory, but it is irreversible.

2.5 Zset

Zset in Redis is also called ordered set. Its underlying layer is ziplist (compressed list) or skiplist (jump table).

Compressed lists have been introduced earlier, and they are similarly used when the number of elements is relatively small. The jump list is mainly introduced here.

Skip meter

Jump list, as the name implies, can jump, jump to query the elements you want to find. You may be unfamiliar with this kind of data structure, although you usually have little contact with it, it is indeed a data structure with good performance in all aspects, which can support fast query, insert and delete operations. it is also much easier to develop than a red-black tree.

Why does the jump meter have such a high performance? How on earth does it "jump"? The jump table uses the idea of dichotomy, and it can be searched quickly by dichotomy in the array, and it is also possible in the linked list.

For example, the linked list is as follows:

Suppose you want to find the node 10, you need to traverse it one by one to determine whether it is the node you are looking for. So how to improve efficiency? I believe everyone is familiar with the mysql index, which can improve the efficiency. You can also use the index here. Extract an index layer:

In this way, you only need to find 9 and then find 10, which greatly saves the search time.

You can also extract another layer of index to better save time:

In this way, the "binary search" based on linked list supports fast insertion and deletion, and the time complexity is O (logn).

Because of the fast search efficiency of the jump table, as well as the implementation of the simple, easy to read. So Redis gave up the red-black tree and opted for a simpler jump table.

Jump table in Redis:

Typedef struct zskiplist {/ / header node and footer node struct zskiplistNode * header, * tail; / / the number of nodes in the table unsigned long length; / / the number of layers of the node with the largest number of layers in the table int level;} zskiplist;typedef struct zskiplistNode {/ / member object robj * obj; / / score double score; / / back pointer struct zskiplistNode * backward / / layer struct zskiplistLevel {/ / forward pointer struct zskiplistNode * forward; / / span-the distance between the node and the current node pointed by the forward pointer unsigned int span;} level [];} zskiplistNode

Zadd---zslinsert--- average O (logN), worst O (N)

Zrem---zsldelete--- average O (logN), worst O (N)

Zrank--zslGetRank--- average O (logN), worst O (N)

Summary

This article briefly introduces the underlying implementation of Redis's five common data types. I hope you can learn more about it by combining the source code and materials.

The beauty of data structure is reflected incisively and vividly in Redis, from String to compressed list, quick list, hash table, jump table, these data structures are applicable to different places and perform their own functions.

Moreover, Redis upgrades and combines these data structures to maximize the efficiency of memory storage. because of this, Redis can become an indispensable high-performance, second-level key-value memory database for many Internet companies.

Author: Yang Heng

Extended reading: Redis chat (1): building a knowledge graph

Source: Yixin Institute of Technology

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.