“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”
Today we’ll talk about the underlying implementation of Redis lists, hashes, and ordered collection types, compressed lists.
Redis uses compressed lists for all three data types. The best advantage of compressed lists is memory saving, sequential data structures composed of a series of specially encoded contiguous memory blocks
Compressed list structure (Ziplist)
A ziplist can contain multiple entries, each of which can hold an array of characters or integers of limited length
zlbytes: record the number of bytes of memory occupied by the compression list, the program can be directly onziplistMemory size is adjusted without the need for calculationziplistMemory size while traversing the entire list.zltail: Records the number of bytes from the end of the compression list to the start of the compression list. With this offset, the program can determine the end of the table without traversing the entire compression list.zllen: records the number of nodes in the compressed list when the number of elements in the compressed list exceeds2^16 - 2The time,zllenWill be set to2 ^ 16-1, when the program queries the value is2 ^ 16-1, you need to traverse the entire compressed list to get the number of elements.entryX: Compresses each node contained in the list. The length of the node is determined by the contents stored in the node.zlendSpecial value:0xFF(decimal255) to mark the end of the compressed list.
Although Ziplist saves memory by storing data in a compact memory layout, there are some issues that need to be noted.
Ziplist has high search complexity
Ziplist’s ZIPLIST_HEADER_SEZE has a fixed size of 10 bytes, which records the offset of the last element, so finding the first and last elements in Ziplist is quick.
But to find other elements in the middle, you need to traverse the entire Ziplist.
The more elements you store in ziplist, the more time it takes to find them.
Therefore, Ziplist is suitable for storing small amounts of data.
Ziplist has a chain update problem
Ziplist must store data in a contiguous chunk of memory, so when data needs to be inserted, it calculates how much space is needed and reallocates memory accordingly. If data is inserted frequently, it will cause continuous application for new continuous memory, affecting ziplist performance.
The above is one of them, and the other is caused by the fact that the node that stores the real data has a property that stores the size of the previous node.
Ziplist entry structure
<prevlen> <encoding> <entry-data>
prevlenA: beforeentryFor reverse traversal.encoding: code, due toziplistIt’s just to save space, soziplistThere are various encodings used to represent strings or integers of different lengths.data: Used for storageentryReal data;
The prevlen property of the node is in bytes, and the encoding length can be 1 byte or 5 bytes.
- If the front node length is less than 254, the length is 1 byte.
- When the front node length is greater than 254, 1 byte is not enough. The first byte is set to 254, and the last four bytes are the actual length of the front node.
When the inserted data exceeds the space required by the next prevlen element to store bytes, memory is reappropriated. After reapplying, the number of bytes may be larger than the next prevlen element needs to store the number of bytes.
In this way, once the insertion position of all subsequent elements, because the prevlenszie of the preceding element is increased, the space of each element needs to be increased, which is the phenomenon of chain update.
Once chained updates occur, ziplist memory needs to be reallocated multiple times, which directly affects ziplist access performance.
Cascading updates may also occur if a node in ziplist is deleted.
At the end
Since Ziplist has these two problems, what else can replace them?
The answer is yes.
Redis implements ziplist’s evolution of QuickList.
The next article continues with Quicklist.