Redis
Redis 经典五大类源码及底层实现
List 数据结构介绍

Redis6

案例

127.0.0.1:6379> config get list*
1) "list-compress-depth"
2) "0"
3) "list-max-ziplist-size"
4) "-2"
127.0.0.1:6379> type list1
list
127.0.0.1:6379>

  • ziplist 压缩配置：list-compress-depth 0

    表示一个 quicklist 两端不被压缩的节点个数。这里的节点是指 quicklist 双向链表的节点，而不是指 ziplist 里面的数据项个数，参数 list-compress-depth 的取值含义如下：

    • 0：是个特殊值，表示都不压缩。这是Redis的默认值。
    • 1：表示 quicklist 两端各有 1 个节点不压缩，中间的节点压缩。
    • 2：表示 quicklist 两端各有 2 个节点不压缩，中间的节点压缩。
    • 3：表示 quicklist 两端各有 3 个节点不压缩，中间的节点压缩。
    • 依此类推…

  • ziplist 中 entry 配置：list-max-ziplist-size -2

    当取正值的时候，表示按照数据项个数来限定每个 quicklist 节点上的 ziplist 长度。比如，当这个参数配置成 5 的时候，表示每个 quicklist 节点的 ziplist 最多包含 5 个数据项。当取负值的时候，表示按照占用字节数来限定每个 quicklist 节点上的 ziplist 长度。这时，它只能取 -1 到 -5 这五个值，每个值含义如下：

    • -5：每个 quicklist 节点上的 ziplist 大小不能超过 64 Kb。（注：1kb => 1024 bytes）
    • -4：每个 quicklist 节点上的 ziplist 大小不能超过 32 Kb。
    • -3：每个 quicklist 节点上的 ziplist 大小不能超过 16 Kb。
    • -2：每个 quicklist 节点上的 ziplist 大小不能超过 8 Kb。（-2 是 Redis 给出的默认值）
    • -1：每个 quicklist 节点上的 ziplist 大小不能超过 4 Kb。

List 的编码格式

list 用 quicklist 来存储，quicklist 存储了一个双向链表，每个节点都是一个 ziplist。

Redis-List-数据结构介绍-quicklist

在 Redis3.0 之前，list 采用的底层数据结构是 ziplist 压缩列表和 linkedList 双向链表，在高版本的 Redis 中底层数据结构是 quicklist（替换了 ziplist 和 linkedList），而 quicklist 也用到了 ziplist。

结论：quicklist 就是 【双向链表 + 压缩列表】组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

在较早版本的 Redis 中，list 有两种底层实现：

  • 当列表对象中元素的长度比较小或者数量比较少的时候，采用压缩列表 ziplist 来存储
  • 当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表 linkedlist 来存储

两者各有优缺点：

  • ziplist 的优点就是内存紧凑，访问效率高，缺点是更新效率低，并且数据量较大时，可能导致大量的内存复制
  • linkedlist 的优点就是节点修改的效率高，但是需要额外的内存开销，并且节点较多时，会产生大量的内存碎片

为了结合两者的优点，在 Redis 3.2 之后，list 的底层实现变为快速列表 quicklist。

quicklist 总纲

quicklist 实际上是 zipList 和 linkedList 的混合体，它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。

Redis-List-数据结构介绍-quicklist数据结构图

源码分析

  • quicklist.h，head 和 tail 指向双向列表的表头和表尾

    • 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.
 * 'bookmakrs 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 ziplists */
    unsigned long len;          /* number of quicklistNodes */
    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 ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * 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 *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

  • quicklistNode 中的 *zl 指向一个 ziplist，一个 ziplist 可以存放多个元素

    Redis-List-数据结构介绍-quicklistNode数据结构图

Redis7

案例

127.0.0.1:6379> config get list*
1) "list-compress-depth"
2) "0"
3) "list-max-ziplist-size"
4) "-2"
5) "list-max-listpack-size"
6) "-2"
127.0.0.1:6379>

listpack 紧凑列表，是用来替代 ziplist 的新版数据结构，在 7.0 版本已经没有 ziplist 的配置了（6.0 版本仅部分数据类型作为过渡阶段在使用）。

源码说明

lpush 命令执行后直接调用 pushGenericCommand 函数

t_list.c
/* Implements LPUSH/RPUSH/LPUSHX/RPUSHX. 
* 'xx': push if key exists. */
void pushGenericCommand(client *c, int where, int xx) {
    int j;
 
    robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
    if (checkType(c,lobj,OBJ_LIST)) return;
    if (!lobj) {
        if (xx) {
            addReply(c, shared.czero);
            return;
        }
 
        lobj = createQuicklistObject();
        quicklistSetOptions(lobj->ptr, server.list_max_listpack_size,
                            server.list_compress_depth); // ⭐️ 读出 size 深度
        dbAdd(c->db,c->argv[1],lobj);
    }
 
    for (j = 2; j < c->argc; j++) {
        listTypePush(lobj,c->argv[j],where);
        server.dirty++;
    }
 
    addReplyLongLong(c, listTypeLength(lobj));
 
    char *event = (where == LIST_HEAD) ? "lpush" : "rpush";
    signalModifiedKey(c,c->db,c->argv[1]);
    notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
}
 
/* LPUSH <key> <element> [<element> ...] */
void lpushCommand(client *c) {
    pushGenericCommand(c,LIST_HEAD,0);
}
Redis6 t_list.c
void pushGenericCommand(client *c, int where) {
    int j, pushed = 0;
 
    for (j = 2; j < c->argc; j++) {
        if (sdslen(c->argv[j]->ptr) > LIST_MAX_ITEM_SIZE) {
            addReplyError(c, "Element too large");
            return;
        }
    }
 
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
 
    if (lobj && lobj->type != OBJ_LIST) {
        addReply(c,shared.wrongtypeerr);
        return;
    }
 
    for (j = 2; j < c->argc; j++) {
        if (!lobj) {
            lobj = createQuicklistObject();
            quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
                                server.list_compress_depth); // ⭐️
            dbAdd(c->db,c->argv[1],lobj);
        }
        listTypePush(lobj,c->argv[j],where);
        pushed++;
    }
    addReplyLongLong(c, (lobj ? listTypeLength(lobj) : 0));
    if (pushed) {
        char *event = (where == LIST_HEAD) ? "lpush" : "rpush";
 
        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
    }
    server.dirty += pushed;
}
 
void lpushCommand(client *c) {
    pushGenericCommand(c,LIST_HEAD);
}
object.c
robj *createQuicklistObject(void) {
    quicklist *l = quicklistCreate();
    robj *o = createObject(OBJ_LIST,l);
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}

List 的编码格式

  • list 用 quicklist 来存储，quicklist 存储了一个双向链表，每个节点都是一个 listpack
  • quicklist 是 listpack 和 linkedlist 的结合体
Hash 数据结构介绍Set ZSet 数据结构介绍