Redis- Structure – Compressed list

What is a compressed list

Ziplist is also widely used in Redis as one of the underlying implementations of zset, List and Hash structures. When our container object has less than a certain number of elements, Redis uses ziplist storage to reduce memory usage.

    > hset test_hash me sidfate
    (integer) 1
    > object encoding test_hash
    "ziplist"
Copy the code

Why use Ziplist when there are fewer elements?

Because in the collection container of Redis, linked list is used in many cases. Elements and elements are connected in sequence through the stored associated Pointers, but such Pointers tend to be random I/O, that is, pointer addresses are discontinuous (uneven distribution). Our Ziplist itself is a contiguous block of memory, so its read and write is sequential I/O, from the bottom of the disk read and write, sequential I/O efficiency is definitely higher than random I/O. You might ask, why not just use sequential I/O instead of random I/O, because Ziplist is contiguous memory, and when you have more elements, that means you need to operate more memory when you create and expand, so ziplist is more efficient when you have fewer elements.

How does Ziplist reduce memory usage?

Let’s take a look at the source code.

Source structure

As an aside: Whenever you want to explore a project’s source code, the first thing you should look at is its comments, and good comments are documentation. It also tells us that we should pay attention to the writing of comments in the beginning.

First of all, we can understand some basic information from the source comments:

Ziplist is a specially encoded two-way list structure designed to improve memory efficiency. It can store strings or integer values that are encoded as actual integers rather than strings. It can push and pop both ends of the list in O(1) time. However, because each operation needs to reallocate the memory used by ziplist, the actual complexity is related to the size of memory used by Ziplist.

The layout of the Ziplist structure is as follows:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
Copy the code

The structure of each node entry in Ziplist is as follows:

<prevlen> <encoding> <entry-data>
Copy the code

Redis has a lot of dirty operations on the ziplist entry structure in order to save it. Let me explain one by one.

prevlen

Prevlen represents the length of the previous element so that you can traverse the list from back to front. It has a special encoding: if the length is less than 254 bytes, it takes up 1 byte; When the length is greater than or equal to 254, five bytes are occupied, the first byte is set to 254 (0xFE), and the remaining four bytes take the length of the previous entry as the value. Prevlen, when expressed as 5 bytes, does not necessarily have a length greater than or equal to 254. This is to reduce realloc and memmove efficiency.

Why is the threshold 254? Let’s calculate, the maximum value that can be stored in a byte is 255, so the threshold should be 255. Remember we also have zlend, which has a value of 0xFF (255), so 254 to avoid confusion.

encoding

Encoding Indicates the encoding of the element, which depends on its content. When the element is a string, the first two bits of the first byte of the encoding will hold the encoding type used to store the length of the string, followed by the actual length of the string. When an entry is an integer, the first two bits are set to 1. The following two bits specify what type of integer will be stored after this header. An overview of the different types and encodings follows. The first byte is always enough to determine the type of the entry.

• | 00 PPPPPP | 1 byte

  A string with a length of 63 bytes or less. 63 can be expressed as 6 bytes, so PPPPPP represents the actual length of the string.

• | 01 PPPPPP | QQQQQQQQ | – 2 bytes

  The value is a 14-bit string with a length less than or equal to 16,383 bytes.

• 10000000 | | QQQQQQQQ | RRRRRRRR | SSSSSSSS | TTTTTTTT | – 5 bytes

  The length is greater than 16383 (14 characters). The last four bytes represent the length.

• | | – 3 11000000 bytes

  11000000 + INT16 (2 bytes).

• | | – 5 11010000 bytes

  11010000 + int32 (4 bytes).

• |11100000| – 9 bytes

  11010000 + int64 (8 bytes).

• |11110000| – 4 bytes

  11110000 + 24-bit signed integer (3 bytes).

• |11111110| – 2 bytes

  11110000 + int8 (1 byte).

• |1111xxxx|

  The value of XXXX is an integer ranging from 0001 to 1101, that is, from 1 to 13, but 0000, 1110, and 1111 are all used. To read the value, you need to subtract XXXX by 1, that is, the integer 0 to 12 is the final value.

• 11111111 | |

  Represents the end of ziplist, which is the zlend value 0xFF.

If you feel confused, don’t panic, I don’t need to remember all of the above, I will use a live chestnut (official example) to summarize. Here is a compressed list containing the strings “2” and “5” :

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
      |             |          |       |       |     |
   zlbytes        zltail    zllen     "2"     "5"   end
Copy the code

The first four bytes represent the number 0x0f = 15 (zlBytes = 15), indicating that the ziplist occupies a total of 15 bytes. The next four bytes represent the number 0x0c = 12 (zltail = 12), indicating that the offset of the last element is 12, which is the length of the element “5” from the beginning of the Ziplist. And then zllen = 2, which means there are two elements. Then there’s the entry that actually stores the “2” and “5.” 00 means the previous element is 0 because it is the first element, f3 is 0x11110011, which is our 1111XXXX encoding type, 3-1 = 2 is exactly our “2”, and “5” is the same. And finally, the ff ending indicates the end.

Did you notice that in the official example we always store the string “2” and “5”, but Redis stores it as an integer? This is actually done deliberately by Redis, many places will do similar processing, the purpose, or to reduce memory consumption.

Finally, let’s look at another example of saving a string. If we replace the “5” with “Hello World”, the original “5” entry will become:

[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
Copy the code

As for why, you can compare the above themselves to try again, as an exercise.