Source code analysis of redis ziplist compressed list

Catalog

Preface

Source code interpretation

ziplist Layout

entry node

prelen

encoding code

summary

Preface

I believe you have used Redis For people who , data type List It's not strange . Most people need to implement a queue , The first choice is List 了 . But in fact Redis Of List Types can be implemented in many ways . This article introduces one of these implementations ziplist - Compressed list .

Source code interpretation

As always, , About ziplist The definition and implementation of is still in a pair of files , Namely ziplist.h and ziplist.c. stay ziplist.c There is a comment at the head of the file that describes what is ziplist.

ziplist It's a specially encoded two-way linked list , Designed to improve memory efficiency . It stores strings and integer values , Where an integer is encoded as an actual integer instead of a series of characters . It allows O(1) Push and pop-up operations are performed on either side of the list within a certain time . however , Because each operation needs to be reassigned ziplist Memory used , So the actual complexity and ziplist The amount of memory used .

From this passage we get ： There are different encoding methods for different data types , It is understood that the data will be compressed , So as to achieve the purpose of reducing memory usage . But with the storage value Data level increase , Use ziplist The cost is also increasing .

ziplist Layout

ziplist Is a special two-way linked list , Unlike ordinary linked lists, they use front and back pointers to associate them , It is stored in continuous memory . The overall structural layout is shown below ：

zlbytes: 32 Bit unsigned integer , Record ziplist The occupied space of the whole structure . Of course, it also includes zlbytes In itself . This structure has a great use , When it needs to be modified ziplist You can know its own size without traversal . This SDS There are similarities in the length of the record string in , These good designs can often be adopted in normal development .

zltail: 32 Bit unsigned integer , Record the whole ziplist Last of entry The offset . So in the tail POP You don't need to go through it first .

zllen: 16 Bit unsigned integer , Record entry The number of , So it can only mean 2^16. however Redis Special treatment has been made ： When the number of entities exceeds 2^16 , The value is fixed to 2^16 - 1. So this time to know the number of all entities must traverse the entire structure .

entry: The structure of real data storage .

zlend: 8 Bit unsigned integer , Fixed for 255 . by ziplist At the end of .

entry node

Every entry The metadata that contains two pieces of information is prefixed . The first metadata is used to store the previous entry The length of , So that you can traverse the list from back to front . The second metadata is to represent entry Code form of . Used to represent entry type , Integer or string , In the case of strings , It also indicates the valid length of the string .

So a complete ziplist It's stored like this ：

prelen

Record the previous entry The length of . If the previous one entry The length of is less than 254 , Then use 1 Bytes of 8 Bit unsigned integer to represent .

If the previous one entry The length is greater than or equal to 254, Then use 5 In bytes . The first 1 Bytes fixed to 254 (FE) As identification , The remaining 4 Bytes are used to represent the previous entry The actual size of .

So in both cases entry The structure is as follows ：

1. Previous entry Not larger than 253.<prevlen from 0 to 253> <encoding> <entry>2. Previous entry Larger than 253.0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>encoding code

entry The encoding field of depends on the content of the specific value , Divided into strings 、 The two types of numbers are handled separately .

One 、 When entry When is a string , Yes 3 Coding methods . Code No 1 Before bytes 2 Bit will hold the encoding type used to store the string length , Followed by the actual length of the string .

1. The length is less than or equal to 63 byte （6 position ） The string value of . “pppppp” To represent an unsigned 6 Bit data length .|00pppppp| - 1 byte2. The length is less than or equal to 16383 byte （14 position ） The string value of .14 The data of bit adopts big endian Storage .big endian Is a kind of byte order , Yes Little-Endian、Big-Endian Two kinds of .|01pppppp|qqqqqqqq| - 2 bytes3. The length is greater than or equal to 16384 Byte string value . use big endian The stored and representable string length is the maximum 2^32-1, So the first byte is not used , So low 6 Bits are useless , So it's all 0.|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes

Two 、 When entry When it's an integer , Yes 6 Coding methods . front 2 The bits are fixed to 1, Next 2 Bit is used to specify what type of integer is stored after this header .

And ziplist The header is the same , All integers begin with Little-Endian Ordinal representation , Even if this code is in Big-Endian Compiled in the system .

1. Integer encoding is int16_t（2 byte ）.|11000000| - 3 bytes2. Integer encoding is int32_t（4 Bytes ）.|11010000| - 5 bytes3. Integer encoding is int64_t（8 byte ）.|11100000| - 9 bytes4. Integer encoding is 24 Bit with sign （3 Bytes ）.|11110000| - 4 bytes5. Integer encoding is 8 Bit has sign （1 byte ）.|11111110| - 2 bytes6. 0 To 12 Of unsigned integers . The encoded value is actually 1 To 13, because 0000 and 1111 Out-of-service , So we should start from the encoded 4 Subtract... From the bit value 1 To get the right value .|1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer

3、 ... and 、 End code identification

1. Express ziplist End identification .|11111111| summary

ziplist To save memory , Compact continuous storage . Therefore, it is not as easy as the general linked list under the modification operation , Need to reallocate new memory , Then copy to the new space .

ziplist It's a two-way list , The time complexity can be O(1) From the bottom of the head 、 At the end pop or push.

There may be a chain of updates .

In fact, this data structure is not directly operated in use , But you can set the circumstances under which it is used . Can be in Redis Set in the configuration file of .

If there are the following optional settings ：

hash-max-ziplist-entries：hash When the number of type elements exceeds the specified data . Use hash Storage , Otherwise, use a compressed table .

hash-max-ziplist-value： hash When the type element length exceeds the specified data . Use hash Storage , Otherwise, use the compressed linked list .

zset-max-ziplist-entries：zset type Compressed list ziplist Maximum number of limiting elements . If the specified value is exceeded, the skip table will be used skiplist + dict To store .

zset-max-ziplist-value：set type Compressed list ziplist Maximum limit size . If the specified value is exceeded, the skip table will be used skiplist+dict To store .

This is about Redis ziplist  This is the end of the article on source code analysis of compressed lists , More about Redis ziplist  Please search the previous articles of SDN or continue to browse the related articles below. I hope you can support SDN more in the future ！