在上一篇文章《Redis列表实现原理之ziplist结构》,我们分析了ziplist结构如何使用一块完整的内存存储列表数据。
同时也提出了一个问题:如果链表很长,ziplist中每次插入或删除节点时都需要进行大量的内存拷贝,这个性能是无法接受的。
本文分析quicklist结构如何解决这个问题,并实现Redis的列表类型。
quicklist的设计思想很简单,将一个长ziplist拆分为多个短ziplist,避免插入或删除元素时导致大量的内存拷贝。
ziplist存储数据的形式更类似于数组,而quicklist是真正意义上的链表结构,它由quicklistNode节点链接而成,在quicklistNode中使用ziplist存储数据。
提示:本文以下代码如无特殊说明,均位于quicklist.h/quicklist.c中。
本文以下说的“节点”,如无特殊说明,都指quicklistNode节点,而不是ziplist中的节点。
quicklistNode的定义如下:
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
unsigned int sz;
unsigned int count : 16;
unsigned int encoding : 2;
unsigned int container : 2;
unsigned int recompress : 1;
unsigned int attempted_compress : 1;
unsigned int extra : 10;
} quicklistNode;
当链表很长时,中间节点数据访问频率较低。这时Redis会将中间节点数据进行压缩,进一步节省内存空间。Redis采用是无损压缩算法—LZF算法。
压缩后的节点定义如下:
typedef struct quicklistLZF {
unsigned int sz;
char compressed[];
} quicklistLZF;
quicklist的定义如下:
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : QL_FILL_BITS;
unsigned int compress : QL_COMP_BITS;
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
quicklist的结构如图2-5所示。
插入元素到quicklist头部:
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
// [1]
if (likely(
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
// [2]
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
// [3]
quicklistNodeUpdateSz(quicklist->head);
} else {
// [4]
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);
}
参数说明:
【1】判断head节点ziplist是否已满,_quicklistNodeAllowInsert函数中根据quicklist.fill属性判断节点是否已满。
【2】head节点未满,直接调用ziplistPush函数,插入元素到ziplist中。
【3】更新quicklistNode.sz属性。
【4】head节点已满,创建一个新节点,将元素插入新节点的ziplist中,再将该节点头插入quicklist中。
也可以在quicklist的指定位置插入元素:
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;
...
// [1]
if (!_quicklistNodeAllowInsert(node, fill, sz)) {
full = 1;
}
if (after && (entry->offset == node->count)) {
at_tail = 1;
if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
full_next = 1;
}
}
if (!after && (entry->offset == 0)) {
at_head = 1;
if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
full_prev = 1;
}
}
// [2]
...
}
参数说明:
【1】根据参数设置以下标志。
【2】根据上面的标志进行处理,代码较烦琐,这里不再列出。
这里的执行逻辑如表2-2所示。
条件 | 条件说明 | 处理方式 |
---|---|---|
!full && after | 待插入节点未满,ziplist尾插 | 再次检查ziplist插入位置是否存在后驱元素,如果不存在则调用ziplistPush函数插入元素(更快),否则调用ziplistInsert插入元素 |
!full && !after | 待插入节点未满,非ziplist尾插 | 调用ziplistInsert函数插入元素 |
full && at_tail && node -> next && !full_next && after | 待插入节点已满,尾插,后驱节点未满 | 将元素插入后驱节点ziplist中 |
full && at_head && node -> prev && !full_prev && !after | 待插入节点已满,ziplist头插,前驱节点未满 | 将元素插入前驱节点ziplist中 |
full && ((at_tail && node -> next && full_next && after) ||(at_head && node->prev && full_prev && !after)) | 满足以下条件:(1)待插入节点已满 (2)尾插且后驱节点已满,或者头插且前驱节点已满 | 构建一个新节点,将元素插入新节点,并根据after参数将新节点插入quicklist中 |
full | 待插入节点已满,并且在节点ziplist中间插入 | 将插入节点的数据拆分到两个节点中,再插入拆分后的新节点中 |
我们只看最后一种场景的实现:
// [1]
quicklistDecompressNodeForUse(node);
// [2]
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);
// [3]
__quicklistInsertNode(quicklist, node, new_node, after);
// [4]
_quicklistMergeNodes(quicklist, node);
【1】如果节点已压缩,则解压节点。
【2】从插入节点中拆分出一个新节点,并将元素插入新节点中。
【3】将新节点插入quicklist中。
【4】尝试合并节点。_quicklistMergeNodes尝试执行以下操作:
quicklist常用的函数如表2-3所示。
函数 | 作用 |
---|---|
quicklistCreate、quicklistNew | 创建一个空的quicklist |
quicklistPushHead,quicklistPushTail | 在quicklist头部、尾部插入元素 |
quicklistIndex | 查找给定索引的quicklistEntry节点 |
quicklistDelEntry | 删除给定的元素 |
配置说明
ziplist由于结构紧凑,能高效使用内存,所以在Redis中被广泛使用,可用于保存用户列表、散列、有序集合等数据。
列表类型只有一种编码格式OBJ_ENCODING_QUICKLIST,使用quicklist存储数据(redisObject.ptr指向quicklist结构)。列表类型的实现代码在t_list.c中,读者可以查看源码了解实现更多细节。
总结
本文内容摘自作者新书《Redis核心原理与实践》。本书通过深入分析Redis 6.0源码,总结了Redis核心功能的设计与实现。通过阅读本书,读者可以深入理解Redis内部机制及最新特性,并学习到Redis相关的数据结构与算法、Unix编程、存储系统设计,分布式系统架构等一系列知识。
经过该书编辑同意,我会继续发布书中部分章节内容,作为书的预览内容,欢迎大家查阅,谢谢。
语雀平台预览:《Redis核心原理与实践》
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。