之前我们已经讨论过 Sorted Set 在 Redis 的实现,学习到了 Redis 在不同数据量的时候使用了不同的结构来优化存储和性能,并且使用两种不同的数据结构的组合来进一步优化。而今天要讨论的 List 也如出一辙。
List 就是我们常见的列表,在很多语言中都有实现,无论是数组还是链表,它最终的表现形式都差不多,都是一个“长长的数据”,而对于不同的底层实现,所对应的操作带来的性能也不同。比如在 java 中就有 LinkedList 和 ArrayList。而 Redis 是如何做的呢?
如果你对 Redis 的 List 使用并不是很熟悉,建议下查看一下它所有支持的命令 https://redis.io/commands/?group=list
在 Redis 的老版本中 list 的实现和 Sorted Set 策略类似,对于不同数据量的情况下实现是不一样的。在数据量小的时候,使用的也是 ziplist
也就是压缩列表(可以看做数组),而当数据量变大触发条件时,就变成了 linkedlist
也就是双向链表。
ziplist 就是通过数据的长度来定位前一个和后一个数据,从而减少了双向链表中的前后指针。
而新版本中 Redis 使用了 quicklist
来实现,所以我们主要讨论的是 quicklist
是如何实现的。
首先要看的肯定是结构定义
/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
* 'count' is the number of total entries.
* 'len' is the number of quicklist nodes.
* 'compress' is: 0 if compression disabled, otherwise it's the number
* of quicklistNodes to leave uncompressed at ends of quicklist.
* 'fill' is the user-requested (or default) fill factor.
* 'bookmarks are an optional feature that is used by realloc this struct,
* so that they don't consume memory when not used. */
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* total count of all entries in all listpacks */
unsigned long len; /* number of quicklistNodes */
signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */
unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
我们抓重点:
不错,已经“很链表”了,那么我们问题的关键就放到了 quicklistNode
的结构上来了。
/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
* We use bit fields keep the quicklistNode at 32 bytes.
* count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k).
* encoding: 2 bits, RAW=1, LZF=2.
* container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items).
* recompress: 1 bit, bool, true if node is temporary decompressed for usage.
* attempted_compress: 1 bit, boolean, used for verifying during testing.
* extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *entry;
size_t sz; /* entry size in bytes */
unsigned int count : 16; /* count of items in listpack */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* PLAIN==1 or PACKED==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
unsigned int extra : 9; /* more bits to steal for future usage */
} quicklistNode;
看到 prev 和 next 就很“双向链表”了,我看到这里的时候都要开始奇怪了,如果就这样也没必要改了吧。既然从结构上看不出来,我们就来看看方法里面是如何实现的来判断它具体节点的连接关系。
/* Add new entry to tail node of quicklist.
*
* Returns 0 if used existing tail.
* Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_tail = quicklist->tail;
if (unlikely(isLargeElement(sz))) {
__quicklistInsertPlainNode(quicklist, quicklist->tail, value, sz, 1);
return 1;
}
if (likely(
_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
quicklist->tail->entry = lpAppend(quicklist->tail->entry, value, sz);
quicklistNodeUpdateSz(quicklist->tail);
} else {
quicklistNode *node = quicklistCreateNode();
node->entry = lpAppend(lpNew(0), value, sz);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
}
quicklist->count++;
quicklist->tail->count++;
return (orig_tail != quicklist->tail);
}
从这里我们就可以看出端倪了,先不管判断条件,我们看到有两个分支:
OK,先不管 lpAppend
方法,大致就有感觉了,并不是一个普通的双链表,对于双链表中的每个节点来说都是一个新的结构,满足一定条件才会创建新的 node。所以,quicklist 解决问题的方式是压缩存储,原本的普通的双链会很长,将一些元素合并起来组成一个个 node,将这些 node 再连起来。嗯(我当时真感叹一下,是个不择手段的设计)
那么就留下了两个问题:
lpAppend
里面究竟干了什么事情?我们想到的肯定是和大小有关系,如果数据太多肯定就存不下了,看到分支的判断方法 _quicklistNodeAllowInsert
REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
const int fill, const size_t sz) {
if (unlikely(!node))
return 0;
if (unlikely(QL_NODE_IS_PLAIN(node) || isLargeElement(sz)))
return 0;
/* Estimate how many bytes will be added to the listpack by this one entry.
* We prefer an overestimation, which would at worse lead to a few bytes
* below the lowest limit of 4k (see optimization_level).
* Note: No need to check for overflow below since both `node->sz` and
* `sz` are to be less than 1GB after the plain/large element check above. */
size_t new_sz = node->sz + sz + SIZE_ESTIMATE_OVERHEAD;
if (unlikely(quicklistNodeExceedsLimit(fill, new_sz, node->count + 1)))
return 0;
return 1;
}
ok,非常简单和清晰的注释,isLargeElement
结合注释,太大的元素,比如 1GB,那肯定单独创建 node 实在了,没话说。the lowest limit of 4k
好了,破案了。
最后,注意一个细节 listpack
?是什么?没错,它就是我们下一个问题的答案
在老版本里面,都会告诉你,quicklist 就是双链套 ziplist,没错在老版本确实是这样实现的,而我只会告诉你看最新的源码,学的才是最多的。redis 已经慢慢在用 listpack 替换掉 ziplist 了。听我下面慢慢道来。
ziplist 其实最大的一个问题就是连锁更新,由于 ziplist 利用数据长度来定位前后元素,通过计算长度来得到下一个元素的位置。那么势必问题就是当数据更新时,长度也更新,前一个数据的更新会导致后面数据一起动,一起挪动位置。 虽然我们知道在列表中直接更新某个数据并非常见,但确实当真正出现这样场景的时候就会变的非常困难。而原本的双链表由于保存的时指针,更新数据非常容易。指针都不用动。
那想要避免这个问题,就需要对 list 的编码方式重新设计。
这个数据结构的设计理念可以参考:https://github.com/antirez/listpack/blob/master/listpack.md
/* Each entry in the listpack is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
uint32_t slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} listpackEntry;
单个元素的结构是:
<encoding-type><element-data><element-tot-len>
| |
+--------------------------------------------+
(This is an element)
就这样?对就这样。设计的关键点主要就是编码方式,它通过 11110001
这样的形式来告诉你后面的数据是什么类型的数据,保存数据的位数是多少。
举例来说:11110001 表示一个 16 位整数,数据记录在后续 2 个字节的 data 中。
ziplist 由于通过长度来找到后一个元素的位置,当数据变化是长度跟着一起变了。而 listpack 要注意了,它保存的是编码方式,而对于相同类型的数据,比如 16 位整数,后面存储的位置是固定的就是 2 个字节,即使数据变了,那也还是那个位置。相对应的,从后向前查找时与 ziplist 是一致的通过 element-tot-len 能找到前一个元素的位置,不会影响。
在看 Redis List 实现之前,我经常会觉得,不就是个 list 的嘛,弄个数组一下不就搞定了?但对于追求极致性能和巨大内存压力的缓存来说,能优化一点就要尽力去优化一点。对于 List 我们能学到:
这两点是我们能从中学到的,虽然我们不一定会遇到如此要求下的极致优化,但这样的思路又让我们有了更厉害的武器。