The time complexity of each ziplist change is very high, because you have to create a new Ziplist to be used as the updated list. If the list is very large and updated frequently, it will put a great burden on Redis. How to keep the spatial efficiency of Ziplist without making it too complicated to update? The answer from the authors of Redis is quickList.
Basically, you combine Ziplist with an ordinary two-way list. Save a Ziplist in each double-linked list node, and then store a batch of list data in each Ziplist (the specific Ziplist size can be configured), which can not only avoid the memory consumption caused by a large number of linked list Pointers, but also avoid a large number of performance loss caused by ziplist update, and break the large Ziplist into pieces.
The data structure
quicklist
A picture is worth a thousand words, so let’s see what the next actual QuickList looks like in memory.
To give you an overview of the different nodes in the figure above, all the lists in Redis are actually QuickLists, so the list arguments in commands like pop push are QuickLists. The quickList fields and their meanings are as follows.
typedef struct quicklist {
quicklistNode *head; /* header */
quicklistNode *tail; /* 尾结点 */
unsigned long count; /* Total number of entries in all ziplist */
unsigned long len; /* Total number of QuickList nodes */
int fill : QL_FILL_BITS; /* 16 bits, maximum capacity of each node */
unsigned int compress : QL_COMP_BITS; /* 16 bits, quickList's compression depth, 0 indicates that all nodes are not compressed, otherwise indicates how many nodes are not compressed from both ends */
unsigned int bookmark_count: QL_BM_BITS; /*4 bits, the size of the Bookmarks array. Bookmarks is an optional field used when QuickList reallocates memory, but does not occupy space when not in use */
quicklistBookmark bookmarks[];
} quicklist;
Copy the codeQuicklist is a simple, double-linked list, but with a few more fields, we’ll focus on compress. In the figure above, I use two different colors of nodes, green is the normal Ziplist node, and red is the ziplist node (LZF node) compressed, LZF is a lossless compression algorithm. In order to save memory space, Redis compresses quickList nodes with LZF. However, not all quickList nodes can be compressed. You can configure the compress value of COMPRESS, which means that all nodes are not compressed. Compress is 1, indicating that one node does not perform LZF compression from both ends. The default value of **compress is 0(no compression), which can be configured according to your actual service scenarios. 天安门事件
Why not compress all nodes instead of flowing out the configurable compress port? In fact, statistics show that data changes at both ends of the list are the most frequent. Commands such as lpush,rpush, LPOP and rPOP operate at both ends. Frequent compression or decompression will cause unnecessary performance loss of the code. This shows that Redis is not just about performance, it is also trying to reduce storage footprint and trade off between storage and performance.
There is also a fill field, which means the maximum capacity of each quicknode node. Different values have different meanings. The default value is -2, but other values can also be configured.
- -1: the ziplist size of each quicklistNode cannot exceed 4kb. (Recommended)
- -2: the number of ziplist bytes in each quicklistNode cannot exceed 8kb. (Default & Recommended)
- -3: the number of ziplist bytes in each quicklistNode cannot exceed 16kb.
- -4: the number of ziplist bytes in each quicklistNode cannot exceed 32kb.
- -5: the ziplist size of each quicklistNode cannot exceed 64kb.
- Any positive number: indicates the maximum number of entries that a Ziplist structure can contain. The maximum value is 215215.
quicklistNode
A quicklistNode is a double-linked list of nodes that contains Pointers to the front and back nodes and other information about the node. Such as LZF compressed node, Ziplist related information…… Details are as follows:
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl; /* Ziplist */ for the quickList node
unsigned int sz; /* The number of bytes of ziplist */
unsigned int count : 16; /* Number of ziplist items */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* Is this node compressed before? * /
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* Unused 10 bits */
} quicklistNode;
Copy the codeNow that we’ve seen what a QuickList looks like in memory at any given moment, let’s look at how it changes as data is inserted or deleted.
The operation of the quicklist
create
/* Create a new QuickList. * Release quickList with quicklistRelease(). */
quicklist *quicklistCreate(void) {
struct quicklist *quicklist;
quicklist = zmalloc(sizeof(*quicklist));
quicklist->head = quicklist->tail = NULL;
quicklist->len = 0;
quicklist->count = 0;
quicklist->compress = 0;
quicklist->fill = 2 -;
quicklist->bookmark_count = 0;
return quicklist;
}
Copy the codeThere’s nothing more to say about create, but it’s important to note that fill defaults to -2, which means that the ziplist in each quicklistNode is up to 8K bytes long and can be configured to suit your business needs.
Head plug and tail plug
For lists, header and tail inserts are the most common, but they are relatively simple.
/* Insert a piece of data at the head of the QuickList * return 0 if inserted at an existing node * return 1 */ if inserted at a new header
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
if (likely(
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD); // Insert into the ziplist corresponding to the header
quicklistNodeUpdateSz(quicklist->head);
} else { // Otherwise create a new header and insert data
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
quicklist->count++;
quicklist->head->count++;
return(orig_head ! = quicklist->head); }/* Inserts a piece of data at the end of the QuickList * returns 0 if inserted at an existing node * returns 1 */ if inserted at a new header node
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_tail = quicklist->tail;
if (likely(
_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
quicklist->tail->zl =
ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
quicklistNodeUpdateSz(quicklist->tail);
} else {
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
}
quicklist->count++;
quicklist->tail->count++;
return(orig_tail ! = quicklist->tail); }Copy the codeHead and tail are called _quicklistNodeAllowInsert can determine whether the first direct in the current head | end nodes can be inserted, if can directly inserted into the corresponding ziplist, otherwise you need to create a new node operation again. Remember that the _quicklistNodeAllowInsert field is a fill field that uses the value of fill to determine whether the maximum capacity has been exceeded.
Specific position insertion
Head-to-tail insertion is easy, but non-head-to-tail insertion of QuickList is more tedious because of the need to take into account insertion location, storage of the front node, and storage of the back node.
/* Insert a new entry before or after an existing entry * if after==1, otherwise before */
REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
void *value, const size_t sz, int after) {
int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
int fill = quicklist->fill;
quicklistNode *node = entry->node;
quicklistNode *new_node = NULL;
if(! node) {/* If node is not included in entry, create a new node and insert it into quickList */
D("No node given!");
new_node = quicklistCreateNode();
new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
__quicklistInsertNode(quicklist, NULL, new_node, after);
new_node->count++;
quicklist->count++;
return;
}
/* Check if the node to be inserted is full */
if(! _quicklistNodeAllowInsert(node, fill, sz)) { D("Current node is full with count %d with requested fill %lu",
node->count, fill);
full = 1;
}
if (after && (entry->offset == node->count)) {
D("At Tail of current ziplist");
at_tail = 1;
if(! _quicklistNodeAllowInsert(node->next, fill, sz)) { D("Next node is full too.");
full_next = 1; }}if(! after && (entry->offset ==0)) {
D("At Head");
at_head = 1;
if(! _quicklistNodeAllowInsert(node->prev, fill, sz)) { D("Prev node is full too.");
full_prev = 1; }}/* Not sure where to insert the new element */
if(! full && after) {// If the current node is not satisfied, insert it directly
D("Not full, inserting after current position.");
quicklistDecompressNodeForUse(node);
unsigned char *next = ziplistNext(node->zl, entry->zi);
if (next == NULL) {
node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL);
} else {
node->zl = ziplistInsert(node->zl, next, value, sz);
}
node->count++;
quicklistNodeUpdateSz(node);
quicklistRecompressOnly(quicklist, node);
} else if(! full && ! after) { D("Not full, inserting before current position.");
quicklistDecompressNodeForUse(node);
node->zl = ziplistInsert(node->zl, entry->zi, value, sz);
node->count++;
quicklistNodeUpdateSz(node);
quicklistRecompressOnly(quicklist, node);
} else if(full && at_tail && node->next && ! full_next && after) {/* If the current node is full, insert into the end of the current node, and there is room for the next node, insert into the head of the next node. * /
D("Full and tail, but next isn't full; inserting next node head");
new_node = node->next;
quicklistDecompressNodeForUse(new_node);
new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD);
new_node->count++;
quicklistNodeUpdateSz(new_node);
quicklistRecompressOnly(quicklist, new_node);
} else if(full && at_head && node->prev && ! full_prev && ! after) {/* If the current node is full, the position to insert is at the head of the current node, and the previous node has space, then insert to the end of the previous node. * /
D("Full and head, but prev isn't full, inserting prev node tail");
new_node = node->prev;
quicklistDecompressNodeForUse(new_node);
new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
quicklistRecompressOnly(quicklist, new_node);
} else if(full && ((at_tail && node->next && full_next && after) || (at_head && node->prev && full_prev && ! after))) {/* If the current node is full and both front and back nodes are full, create a new node and insert it */
D("\tprovisioning new node...");
new_node = quicklistCreateNode();
new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
new_node->count++;
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
} else if (full) {
/* Otherwise, the current node is full and we need to split it into two new nodes. This is usually used when inserting the current node somewhere in the middle of the ziplist */
D("\tsplitting node...");
quicklistDecompressNodeForUse(node);
new_node = _quicklistSplitNode(node, entry->offset, after);
new_node->zl = ziplistPush(new_node->zl, value, sz,
after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
_quicklistMergeNodes(quicklist, node);
}
quicklist->count++;
}
Copy the codeThe code is quite long and summarized as follows:
- If the node is not satisfied, insert the node directly.
- If the node being inserted is full, the position to be inserted is at the end of the current node, and there is room for the next node, then insert into the head of the next node.
- If the node being inserted is full, the position to be inserted is at the head of the current node, and there is room for the previous node, then it is inserted at the end of the previous node.
- If the node being inserted is full, both front and back nodes are full, and the position to be inserted is at the head or tail of the current node, create a new node and insert it.
- Otherwise, the current node is full and the insertion position is in the middle of the current node. We need to split the current node into two new nodes and then insert it.
To delete data
Data deletion is supposed to be the opposite of insertion, not quite as you’ll see after looking at the following code:
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
quicklistNode *prev = entry->node->prev;
quicklistNode *next = entry->node->next;
int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
entry->node, &entry->zi);
/* after delete, the zi is now invalid for any future usage. */
iter->zi = NULL;
/* If current node is deleted, we must update iterator node and offset. */
if (deleted_node) {
if (iter->direction == AL_START_HEAD) {
iter->current = next;
iter->offset = 0;
} else if (iter->direction == AL_START_TAIL) {
iter->current = prev;
iter->offset = - 1; }}}REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,
unsigned char **p) {
int gone = 0;
node->zl = ziplistDelete(node->zl, p);
node->count--;
if (node->count == 0) {
gone = 1;
__quicklistDelNode(quicklist, node);
} else {
quicklistNodeUpdateSz(node);
}
quicklist->count--;
/* If we deleted the node, the original node is no longer valid */
return gone ? 1 : 0;
}
Copy the codeDelete is much easier than insert. I looked at the insert logic first. Insert has split nodes, but delete does not have merge nodes.
Other apis
Once you understand the design of the QuickList data structure, you should be able to guess the implementation of each API. I won’t list the code here, but you can look it up for yourself.
quicklist *quicklistCreate(void); / / create quicklist
quicklist *quicklistNew(int fill, int compress); // Create a new QuickList with some specified parameters
void quicklistSetCompressDepth(quicklist *quicklist, int depth); // Set the compression depth
void quicklistSetFill(quicklist *quicklist, int fill); // Set the capacity upper limit
void quicklistSetOptions(quicklist *quicklist, int fill, int depth);
void quicklistRelease(quicklist *quicklist); / / release quicklist
int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz); // Insert the header
int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz); // Insert the tail
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
int where); // Specify head or tail inserts
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl); // Put a ziplist in quickList
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
unsigned char *zl); // Put all the data in ziplist into QuickList
quicklist *quicklistCreateFromZiplist(int fill, int compress,
unsigned char *zl); // Generate a QuickList from ziplist
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
void *value, const size_t sz);
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
void *value, const size_t sz);
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); // Delete data
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
int sz); // Data replacement
int quicklistDelRange(quicklist *quicklist, const long start, const long stop); // Range deleted
quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction); / / the iterator
quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
int direction, const long long idx); // An iterator from the specified position
int quicklistNext(quicklistIter *iter, quicklistEntry *node); // The next position of the iterator
void quicklistReleaseIterator(quicklistIter *iter); // Release the iterator
quicklist *quicklistDup(quicklist *orig); / / to heavy
int quicklistIndex(const quicklist *quicklist, const long long index,
quicklistEntry *entry); // Find the subscript index of the entry
void quicklistRewind(quicklist *quicklist, quicklistIter *li);
void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
void quicklistRotate(quicklist *quicklist); / / select quicklist
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
unsigned int *sz, long long *sval,
void *(*saver)(unsigned char *data, unsigned int sz));
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
unsigned int *sz, long long *slong); / / data pop
unsigned long quicklistCount(const quicklist *ql);
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); // Compare the sizes
size_t quicklistGetLzf(const quicklistNode *node, void **data); / / LZF node
Copy the codeThe resources
- Men_wen Redis source Code Analysis and annotations (7) — QuickList
- Redis internal data structure details (5) – QuickList
This article is a Redis source code analysis series of blog posts, but also with the corresponding Redis Chinese annotated version, there are students who want to further study Redis, welcome star and attention. Redis Chinese Annotated version warehouse: github.com/xindoo/Redi… IO /s/1h Redis source code analysis column: zxs. IO /s/1h If you find this article useful, welcome to three links.