06 From Ziplist to Quicklist to Listpack Evolution

06 From Ziplist to Quicklist to Listpack Evolution

06 From ziplist to quicklist to listpack Evolution #

In the previous Lesson 4, when I introduced the optimized design of Redis to improve memory utilization, I mentioned that compressed lists (ziplist) can be used to store data. So now you should also know that the biggest feature of ziplist is that it is designed to be a compact data structure that occupies a continuous block of memory to save memory.

However, in computer systems, every design has its pros and cons. The same applies to ziplist.

Although ziplist saves memory overhead, it also has two design drawbacks: firstly, it cannot store too many elements, otherwise the access performance will be reduced; secondly, it cannot store elements that are too large, otherwise it may cause memory reallocation and even chain updates. Chain updates mean that each item in the ziplist needs to be reallocated memory space, resulting in reduced performance of the ziplist.

Therefore, in response to the shortcomings of ziplist in design, during the development and evolution of Redis code, two new data structures were designed: quicklist and listpack. The design goal of these two data structures is to maintain the memory-saving advantage of ziplist as much as possible, while avoiding the potential performance drawbacks of ziplist.

In today’s lesson, I will give you a detailed introduction to the design ideas and implementation ideas of quicklist and listpack. However, before I explain these two data structures in detail, I would like to first introduce why ziplist has design flaws. In this way, when you learn about quicklist and listpack, you can compare them with the design of ziplist, which will make it easier for you to grasp the design considerations of quicklist and listpack.

Moreover, the difference between ziplist and quicklist is often asked in interviews, and you may not know much about the design and implementation of the listpack data structure because it is relatively new. After learning this lesson, you will be able to easily deal with the usage of these three data structures. In addition, through the step-by-step optimized design of these three data structures, you can learn the design trade-offs that Redis data structures make between memory overhead and access performance. If you need to develop efficient data structures, you can apply these design ideas.

Alright, next, let’s first understand the flaws in the design and implementation of ziplist.

Limitations of ziplist #

As you know, the layout of a ziplist data structure in memory is a continuous block of memory. The beginning of this block is a fixed-size 10-byte metadata, which records the total number of bytes in the ziplist, the offset of the last element, and the number of elements in the list. The actual list data is stored in the memory space following these 10 bytes. At the end of the ziplist, there is a 1-byte flag (fixed at 255) to indicate the end of the ziplist, as shown in the figure below:

However, although ziplist saves memory space by using a compact memory layout, it also has two limitations: high complexity in searching and potential risk of chain updates. Let’s take a look at these two issues separately.

High complexity in searching #

Because the size of the ziplist’s head and tail metadata is fixed, and the position of the last element is recorded at the head of the ziplist, it is quick to find the first or last element in the ziplist.

However, the problem arises when searching for elements in the middle of the list. In this case, the ziplist has to traverse from either the head or tail of the list. As the number of elements stored in the ziplist increases, the complexity of searching for middle elements increases. Moreover, if the ziplist stores strings, when searching for a specific element, the ziplist needs to compare each character of the element one by one, further increasing the complexity.

Because of this, when using ziplist to store Hash or Sorted Set data, we control the number of elements saved in the ziplist through two parameters, hash-max-ziplist-entries and zset-max-ziplist-entries, in the redis.conf file.

In addition to the high complexity in searching, when inserting elements into ziplist, if there is not enough memory space, ziplist needs to reallocate a continuous block of memory, which further triggers the issue of chain updates.

Potential risk of chain updates #

As we know, ziplist needs to calculate the required space size and allocate corresponding memory space when inserting a new element. We can see these operations in the element insertion function __ziplistInsert in the ziplist.

First, the __ziplistInsert function calculates the current length of the ziplist, which can be done through the ZIPLIST_BYTES macro defined in the code snippet below. Additionally, the function declares the reqlen variable to record the additional space required for the inserted element.

// Get the current length of the ziplist: curlen
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;

Then, the __ziplistInsert function checks if the position to be inserted is at the end of the list. If it is not at the end, it needs to obtain the prevlen and prevlensize of the element at the current insertion position. The code snippet below shows this part of the code:

// If the insertion position is not at the end of the ziplist, get the length of the previous element
if (p[0] != ZIP_END) {
    ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
   ...
}

In ziplist, each element records the length of its previous element, namely prevlen. To save memory overhead, ziplist uses different space to record prevlen, and the size of this space is prevlensize.

For example, suppose the prevlen of an element A originally occupies only 1 byte (i.e., prevlensize is 1) and can record a maximum length of 253 bytes for the previous element. In this case, if the length of element B exceeds 253 bytes when inserting B before element A, A’s prevlen needs to be recorded using 5 bytes (prevlen encoding is described in Lecture 4), requiring an additional 4-byte space. However, if the insertion position of element B is at the end of the list, we don’t need to consider the prevlen of the elements after B when inserting element B.

I have created the following diagram to help you understand the impact of the data insertion process on the element at the insertion position.

Therefore, to ensure that ziplist has enough memory space to save the inserted element and the prevlen information of the element at the insertion position, after obtaining the prevlen and prevlensize of the element at the insertion position, the __ziplistInsert function immediately calculates the length of the inserted element.

Now, we know that a ziplist element consists of prevlen, encoding, and actual data data. Therefore, when calculating the required space for the inserted element, the __ziplistInsert function also calculates the lengths of these three parts separately. This calculation process can be divided into four steps.

Step 1: Calculate the length of the actual inserted element.

First, we need to determine whether the inserted element is an integer or a string. The __ziplistInsert function first calls the zipTryEncoding function to check if the inserted element is an integer. If it is an integer, it calculates the space required for encoding and data based on different integer sizes. If it is a string, the length of the string is recorded as the additional space required. The code snippet below shows this part of the process:

if (zipTryEncoding(s, slen, &value, &encoding)) {
    reqlen = zipIntSize(encoding);
} else {
    reqlen = slen;
}

Step 2: Call the zipStorePrevEntryLength function to include the prevlen of the element at the insertion position in the required space.

This is because, after inserting an element, the __ziplistInsert function may need to allocate additional space for the element at the insertion position. This part of the code is shown below:

reqlen += zipStorePrevEntryLength(NULL,prevlen);

Step 3: Call the zipStoreEntryEncoding function to calculate the size of the corresponding encoding based on the length of the string.

In the previous step, the ziplistInsert function only records the length of the string itself for string data, so in step 3, the ziplistInsert function also calls the zipStoreEntryEncoding function to calculate the size of the encoding based on the length of the string, as shown below:

reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

Alright, at this point, the __ziplistInsert function has already recorded the prevlen length of the inserted element, the size of the encoding, and the length of the actual data in the reqlen variable. This way, the overall length of the inserted element is determined, which is also the size that needs to be recorded for the prevlen of the insertion position element.

Step 4: Call the zipPrevLenByteDiff function to determine the difference in size between the prevlen of the insertion position element and the actual required prevlen.

Finally, the __ziplistInsert function calls the zipPrevLenByteDiff function to determine the difference in size between the prevlen of the insertion position element and the actual required prevlen. This difference in size of prevlen is recorded using nextdiff in the following code:

nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;

Here, if nextdiff is greater than 0, it means that there is not enough space for the insertion position element, and additional space of size nextdiff needs to be allocated to save the new prevlen. Then, when __ziplistInsert allocates the additional space, it will call the ziplistResize function to reallocate the required space for the ziplist.

The ziplistResize function takes the ziplist to be reallocated and the size of the reallocation as parameters. The parameter passed to __ziplistInsert for the reallocation size is the sum of the three lengths.

So, what are these three lengths?

These three lengths are the current size of the ziplist (curlen), the additional space required for the inserted element itself (reqlen), and the additional space required for the prevlen of the insertion position element (nextdiff). The following code shows the call to the ziplistResize function and the parameter passing logic:

zl = ziplistResize(zl,curlen+reqlen+nextdiff);

Furthermore, how does the ziplistResize function expand the ziplist after obtaining the sum of the three lengths?

We can further look at the implementation of the ziplistResize function. This function calls the zrealloc function to complete the space reallocation, and the size of the reallocation is determined by the parameter len passed in. So, we understand that the ziplistResize function involves memory allocation operations. If we insert too much data into the ziplist frequently, it may cause multiple memory allocations, which can impact Redis performance.

The following code shows a partial implementation of the ziplistResize function, where you can take a look:

unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
    // Reallocate the memory space for zl, with len being the new allocation size
    zl = zrealloc(zl,len);
    …
    zl[len-1] = ZIP_END;
    return zl;
}

Alright, at this point, we have understood that the ziplist calculates the additional space required for a new inserted element and performs reallocation. When a newly inserted element is large, it will cause an increase in the prevlensize of the element at the insertion position, which in turn will cause an increase in the space occupied by the element at the insertion position.

In this way, this kind of space addition will cause a chain update problem.

In fact, the so-called “chain update” refers to when one element is inserted, it will cause an additional prevlensize space for the current position element. And when the space of the current position element increases, it will further cause an increase in the space required for prevlensize of the subsequent elements.

Therefore, once all the subsequent elements after the insertion position are increased in space due to the increase in the prevlensize of the preceding elements, this phenomenon where the space of each element needs to be increased is called a chain update. I’ve drawn the following picture for you to take a look:

Once a chain update occurs, the ziplist will need to be reallocated multiple times, which directly affects the access performance of the ziplist.

Therefore, although the compact memory layout of the ziplist can save memory overhead, if the number of elements saved or the size of the elements increases, the ziplist will face performance issues. So, is there any way to avoid the problem with ziplist?

This is what I’m going to introduce to you next: the design ideas behind quicklist and listpack, two other data structures.

Design and Implementation of quicklist #

Let’s start by learning about the implementation of quicklist.

The design of quicklist combines the advantages of both linked lists and ziplists. In simple terms, a quicklist is a linked list, and each element in the linked list is a ziplist.

Let’s take a look at the data structure of quicklist, which is defined in the quicklist.h file, and the specific implementation of quicklist is in the quicklist.c file.

First, let’s look at the definition of quicklist elements, which is quicklistNode. Since quicklist is a linked list, each quicklistNode contains pointers to its previous and next nodes as **_prev and _next respectively. At the same time, each quicklistNode is a ziplist, so in the structure of quicklistNode, there is also a pointer to the ziplist called zl.

In addition, the quicklistNode structure also defines some properties, such as the byte size of the ziplist, the number of elements it contains, the encoding format, and the storage method. The following code shows the structure definition of quicklistNode:

typedef struct quicklistNode {
    struct quicklistNode *prev;     // pointer to the previous quicklistNode
    struct quicklistNode *next;     // pointer to the next quicklistNode
    unsigned char *zl;              // pointer to the ziplist in quicklistNode
    unsigned int sz;                // size of the ziplist in bytes
    unsigned int count : 16;        // number of elements in the ziplist
    unsigned int encoding : 2;      // encoding format, either raw byte array or compressed storage
    unsigned int container : 2;     // storage method
    unsigned int recompress : 1;    // whether the data is compressed
    unsigned int attempted_compress : 1;    // whether the data can be compressed
    unsigned int extra : 10;        // reserved bits
} quicklistNode;

After understanding the definition of quicklistNode, let’s take a look at the definition of quicklist itself.

As a linked list structure, quicklist defines the head and tail pointers of the entire quicklist in its data structure, so we can quickly locate the head and tail of the quicklist through the data structure of quicklist.

In addition, quicklist also defines attributes such as the number of quicklistNodes and the total number of elements in all ziplists. The structure definition of quicklist is as follows:

typedef struct quicklist {
    quicklistNode *head;      // head of the quicklist
    quicklistNode *tail;      // tail of the quicklist
    unsigned long count;     // total number of elements in all the ziplists
    unsigned long len;       // number of quicklistNodes
    ...
} quicklist;

From the structure definitions of quicklistNode and quicklist, we can draw the following schematic diagram of quicklist:

Because quicklist adopts a linked list structure, when inserting a new element, quicklist first checks whether the ziplist at the insertion position can accommodate the new element. This is done by the _quicklistNodeAllowInsert function.

The _quicklistNodeAllowInsert function calculates the new size (new_sz) after inserting the new element, which is equal to the current size of the quicklistNode (node->sz), the size of the inserted element (sz), and the size occupied by the prevlen in the ziplist after inserting the element.

After calculating the size, the _quicklistNodeAllowInsert function sequentially checks whether the new size (sz) meets the requirements, that is, whether a single ziplist does not exceed 8KB or the number of elements in a single ziplist meets the requirements.

As long as one of these conditions is met, the quicklist can insert the new element in the current quicklistNode, otherwise, the quicklist will create a new quicklistNode to store the newly inserted element.

The following code shows the logic to determine whether it is allowed to insert data in the current quicklistNode, you can take a look:

unsigned int new_sz = node->sz + sz + ziplist_overhead;
if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))
    return 1;
else if (!sizeMeetsSafetyLimit(new_sz))
    return 0;
else if ((int)node->count < fill)
    return 1;
else
    return 0;

In this way, by controlling the size or number of elements in each ziplist in each quicklistNode, quicklist effectively reduces the occurrence of chain updates when adding or modifying elements in ziplist, thus providing better access performance.

In addition to designing the quicklist structure to handle the issues of ziplist, Redis also introduced the listpack data structure in version 5.0 to completely avoid chain updates. Let’s continue to learn about its design and implementation ideas.

Design and Implementation of listpack #

listpack, also known as compact list, is characterized by using a contiguous memory space to compactly store data, and to save memory space, listpack uses multiple encoding methods to represent data of different lengths, including integers and strings.

The relevant implementation files of listpack are listpack.c, and the header files include listpack.h and listpack_malloc.h. Let’s start by looking at the creation function lpNew of listpack, as we can understand the overall structure of listpack from the code logic of this function.

The lpNew function creates an empty listpack initially allocated with LP_HDR_SIZE plus one byte. The LP_HDR_SIZE macro is defined in listpack.c and defaults to 6 bytes, with 4 bytes used to record the total number of bytes of the listpack and 2 bytes used to record the number of elements in the listpack.

In addition, the last byte of the listpack is used to indicate the end of the listpack, with its default value being defined as LP_EOF. Similar to the end marker of ziplist items, the value of LP_EOF is also 255.

unsigned char *lpNew(void) {
    // Allocate LP_HDR_SIZE + 1
    unsigned char *lp = lp_malloc(LP_HDR_SIZE + 1);
    if (lp == NULL) return NULL;
    // Set the size of the listpack
    lpSetTotalBytes(lp, LP_HDR_SIZE + 1);
    // Set the number of elements in the listpack, initially 0
    lpSetNumElements(lp, 0);
    // Set the end marker of the listpack to LP_EOF, with a value of 255
    lp[LP_HDR_SIZE] = LP_EOF;
    return lp;
}

Take a look at the following image, which shows the listpack header with size LP_HDR_SIZE and the listpack tail with the value 255. When a new element is inserted, it will be inserted between the listpack header and tail.

Now that we understand the overall structure of listpack, let’s take a look at the design of listpack items.

Similar to ziplist items, listpack items also contain metadata and the actual data. However, to avoid the chain update problem caused by ziplist, each listpack item does not save the length of its previous item like ziplist items do. Instead, it only includes three aspects, which are the encoding type of the current element (entry-encoding), the element data (entry-data), and the length of the encoding type and element data (entry-len), as shown in the following image.

Here, there are two key points about the design of listpack items that you need to grasp, namely the encoding methods for listpack items and the method to avoid chain updates of listpack items. Let me guide you through them in detail.

Encoding methods for listpack items #

Let’s first take a look at the encoding type of listpack elements. If you have looked at the listpack.c file, you will find that there are many macro definitions similar to LP_ENCODING XX_BIT_INT and LP_ENCODING XX_BIT_STR, as shown below.

#define LP_ENCODING_7BIT_UINT 0
#define LP_ENCODING_6BIT_STR 0x80
#define LP_ENCODING_13BIT_INT 0xC0
...
#define LP_ENCODING_64BIT_INT 0xF4
#define LP_ENCODING_32BIT_STR 0xF0

These macro definitions correspond to the encoding types of elements in listpack. Specifically, **listpack encodes integers and strings of different lengths**, let's take a look at each.

Firstly, for **integer encoding**, when the encoding type of a listpack element is LP_ENCODING_7BIT_UINT, it means that the actual data of the element is a 7-bit unsigned integer. Since LP_ENCODING_7BIT_UINT itself is defined as 0, the value of the encoding type is also 0, taking up 1 bit.

At this point, the encoding type and the actual data of the element share 1 byte. The highest bit of this byte is 0, representing the encoding type, and the following 7 bits are used to store the 7-bit unsigned integer, as shown in the following figure:

![](../images/8c4bd520d3953f7e70b6e3f08543c6fb-20221013234939-dq92b7e.jpg)

When the encoding type is LP_ENCODING_13BIT_INT, it means that the actual data of the element is a 13-bit integer. Meanwhile, since LP_ENCODING_13BIT_INT is defined as 0xC0, which is 1100 0000 in binary, the last 5 bits of this binary value, combined with the following 1 byte, a total of 13 bits, are used to store the 13-bit integer. The first 3 bits '110' are used to represent the current encoding type. I have drawn the following figure for you to see.

![](../images/3ecbb8412d41d0a36587dfdaf49714d7-20221013234939-ttqdnea.jpg)

After understanding these two encoding types, LP_ENCODING_16BIT_INT, LP_ENCODING_24BIT_INT, LP_ENCODING_32BIT_INT, and LP_ENCODING_64BIT_INT, you should also be able to grasp their encoding methods.

These four types use 2 bytes (16 bits), 3 bytes (24 bits), 4 bytes (32 bits), and 8 bytes (64 bits) respectively to store integer data. At the same time, their encoding types themselves occupy 1 byte, and the values of the encoding types are the same as their macro definitions.

Next, for **string encoding**, there are three types: LP_ENCODING_6BIT_STR, LP_ENCODING_12BIT_STR, and LP_ENCODING_32BIT_STR. From the previous introduction, you can see that the numeric digit before 'BIT' in the name of integer encoding type represents the length of the integer. Therefore, similarly, the numeric digit before 'BIT' in the name of string encoding type represents the length of the string.

For example, when the encoding type is LP_ENCODING_6BIT_STR, the encoding type occupies 1 byte. The macro definition value of this type is 0x80, which corresponds to the binary value 1000 0000. The first 2 bits of the binary value are used to identify the encoding type itself, while the last 6 bits store the length of the string. Then, the data part in the list item contains the actual string.

The following diagram shows the layout of the three string encoding types and the data, you can take a look.

![](../images/9c17c0be0519100c509e2378acd6e125-20221013234939-0o8djwa.jpg)

### Implementation of avoiding chaining updates in listpack

Finally, let's understand how listpack avoids chaining updates.

In listpack, each list item only records its own length, unlike the list item in ziplist, which also records the length of the previous item. Therefore, when we add or modify elements in listpack, it actually only involves operations on each list item itself, without affecting the length changes of subsequent list items, thus avoiding chaining updates.

However, you may wonder: **If listpack only records the length of the current item, does listpack support querying the list from left to right or from right to left?**
Actually, listpack supports both forward and backward querying of lists.

**When the application queries listpack from left to right**, we can first call the lpFirst function. This function takes a pointer to the listpack header as its parameter and, when executed, moves the pointer to the right by the size of LP_HDR_SIZE, which skips the listpack header. You can see the code for the lpFirst function below:

```c
unsigned char *lpFirst(unsigned char *lp) {
    lp += LP_HDR_SIZE; // Skip the 6 bytes of the listpack header
    if (lp[0] == LP_EOF) return NULL; // If it is the end-of-file byte of the listpack, return NULL
    return lp;
}

Then, call the lpNext function, which includes a pointer to a specific list item in the listpack as its parameter. The lpNext function further calls the lpSkip function and passes the pointer to the current list item, as shown below:

unsigned char *lpNext(unsigned char *lp, unsigned char *p) {
    ...
    p = lpSkip(p); // Call the lpSkip function to offset the pointer to the next list item
    if (p[0] == LP_EOF) return NULL;
    return p;
}

Finally, the lpSkip function calls the lpCurrentEncodedSize and lpEncodeBacklen functions.

The lpCurrentEncodedSize function calculates the encoding type of the current list item based on the value of the first byte of the list item. It then calculates the total length of the encoding type and the actual data based on the encoding type. The lpEncodeBacklen function calculates the length of the entry-len itself based on the sum of the encoding type and actual data length.

With this information, the lpSkip function knows the encoding type, actual data, and total length of the entry-len of the current item. It can then offset the current item pointer to the right by the corresponding length, achieving the goal of finding the next list item.

The following code shows the basic calculation logic of the lpEncodeBacklen function:

unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) {
    // Entry-len length is 1 byte if the sum of the encoding type and actual data length is less than or equal to 127
    if (l <= 127) {
        ...
        return 1;
    } else if (l < 16383) { // Entry-len length is 2 bytes if the sum of the encoding type and actual data length is greater than 127 but less than 16383
        ...
        return 2;
    } else if (l < 2097151) { // Entry-len length is 3 bytes if the sum of the encoding type and actual data length is greater than 16383 but less than 2097151
        ...
        return 3;
    } else if (l < 268435455) { // Entry-len length is 4 bytes if the sum of the encoding type and actual data length is greater than 2097151 but less than 268435455
        ...
        return 4;
    } else { // Otherwise, entry-len length is 5 bytes
        ...
        return 5;
    }
}

I have also created a diagram that shows the basic process of traversing listpack from left to right. You can review it below.

Now that you understand forward querying of listpack from left to right, let’s take a look at backward querying of listpack from right to left.

Firstly, we can locate the end mark of the listpack directly based on the total length of the listpack recorded in the listpack header. Then, we can call the lpPrev function, which takes a pointer to a specific list item as its parameter and returns a pointer to the previous list item.

The key step in the lpPrev function is to call the lpDecodeBacklen function. The lpDecodeBacklen function reads the entry-len of the current list item byte by byte from right to left.

So, how does the lpDecodeBacklen function determine whether the entry-len has ended?

This depends on the encoding method of the entry-len. The highest bit of each byte of the entry-len is used to indicate whether the current byte is the last byte of the entry-len. There are two cases:

If the highest bit is 1, it means the entry-len has not ended yet, and the left bytes of the current byte still represent the content of the entry-len.
If the highest bit is 0, it means the current byte is the last byte of the entry-len.

The lower 7 bits of each byte of the entry-len record the actual length information. It’s worth noting that the lower 7 bits of each byte of the entry-len are stored in big-endian mode, which means the low-order byte of the entry-len is stored at the higher memory address.

I have created the following diagram to illustrate this special encoding method of the entry-len. Please take a look:

In fact, because of the special encoding method of the entry-len, the lpDecodeBacklen function can start parsing from the pointer to the start of the current list item and decode the entry-len value of the previous item byte by byte from right to left. This is the return value of the lpDecodeBacklen function. As mentioned earlier, the entry-len records the sum of the encoding type and actual data length.

Therefore, the lpPrev function calls the lpEncodeBacklen function again to calculate the length of the entry-len itself. With this information, we can obtain the total length of the previous item, and the lpPrev function can move the pointer to the start of the previous item. Following this method, listpack achieves the functionality of querying from right to left.

Summary #

In this lesson, I have introduced the design concepts of quicklist and listpack starting from the shortcomings of ziplist.

You need to understand that the main drawback of ziplist is that its lookup efficiency decreases as the number of elements in the ziplist increases. Moreover, if data is added or modified in the ziplist, the memory space occupied by the ziplist needs to be reallocated. What’s worse, adding or modifying an element in the ziplist may cause the prevlen space of subsequent elements to change, leading to chain updating issues, resulting in the need to reallocate the space for each element and thus decreasing the access performance of the ziplist.

Therefore, in order to address the issues of ziplist, Redis first designed and implemented quicklist in version 3.0. Quicklist is a structure that links ziplists together using a linked list, and each element of the linked list is a ziplist. This design reduces the need to reallocate memory space and copy memory data when inserting data. At the same time, quicklist limits the size of each ziplist on a node, and if a ziplist becomes too large, a new quicklist node will be added.

However, because quicklist uses the quicklistNode structure to point to each ziplist, it undoubtedly increases memory overhead. In order to reduce memory overhead and further avoid chain updating issues of ziplist, Redis designed and implemented the listpack structure in version 5.0. The listpack structure follows the compact memory layout of ziplist and places each element right next to each other.

In listpack, each list item no longer includes the length of the previous item. Therefore, when the data in a list item changes, causing the length of the list item to change, the lengths of other list items are not affected, thus avoiding the chain updating issues faced by ziplist.

In summary, in the design and implementation of memory-compact lists, from ziplist to quicklist, and then to listpack, you can see the design trade-offs between memory space overhead and access performance in Redis. This series of design changes is very worthwhile for you to learn.

One question per lesson #

The ziplist uses the zipTryEncoding function to calculate the additional memory space required to insert elements. Assuming that one element to be inserted is an integer, do you know how large of an integer ziplist can support?

Feel free to share your answer and thought process in the comments section. If you find it helpful, you’re also welcome to share today’s content with more friends.