欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Redis之quicklist源码分析

程序员文章站 2022-07-10 21:59:33
一、quicklist简介 Redis列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)。 一个列表最多可以包含 232 - 1 个元素 (4294967295, 每个列表超过40亿个元素)。 其底层实现所依赖的内部数据结构就是quicklist,主要特 ......

一、quicklist简介

redis列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)。

一个列表最多可以包含 232 - 1 个元素 (4294967295, 每个列表超过40亿个元素)。

其底层实现所依赖的内部数据结构就是quicklist,主要特点有:

1. list是一个双向链表。

2. 在list的两端追加和删除数据极为方便,时间复杂度为o(1)。

3. list也支持在任意中间位置的存取操作,时间复杂度为o(n)。

 

在看源码之前(版本3.2.2),我们先看一下quicklist中的几个主要数据结构:

一个quicklist由多个quicklistnode组成,每个quicklistnode指向一个ziplist,一个ziplist包含多个entry元素,每个entry元素就是一个list的元素,示意图如下:

Redis之quicklist源码分析

 

 

                        图1:quicklist

 二、quicklist数据结构源码

下面分别看下quicklist、quicklistnode的源码(代码文件是quicklist.h,ziplist后面文章再分析):

quicklist:

/* 
   quicklist结构占用32个字节(64位系统),其中字段:
   head:指向第一个quicklistnode。
   tail:指向最后一个quicklistnode。
   count:在所有ziplist中entry的个数总和。
   len:quicklistnode的个数。
   fill:ziplist大小限定,由server.list_max_ziplist_size给定。
   compress:节点压缩深度设置,由server.list-compress-depth给定,0表示关闭压缩。
 */
typedef struct quicklist {
    quicklistnode *head;
    quicklistnode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistnodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistnode:

/*
 prev: 指向前一个quicklistnode。
 next: 指向下一个quicklistnode。
 zl: 指向当前节点的ziplist。
 sz:ziplist占用空间的字节数。
 count: ziplist中元素个数。
 encoding:编码类型,raw==1 or lzf==2。
 container:容器类型,none==1 or ziplist==2
 recompress:bool类型,true表示该节点数据临时被解压了。
 attempted_compress: bool类型,用于测试阶段。
 extra: 填充字典,将来可能会用到。
 */
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;

 

 

三、quicklist的增删改查

1. 创建quicklist

在执行push命令时(例如lpush),发现无此key时,会创建并初始化quicklist,如下:

 

void pushgenericcommand(client *c, int where) {
    int j, waiting = 0, pushed = 0;
    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++) {
        c->argv[j] = tryobjectencoding(c->argv[j]);
        if (!lobj) {  // key不存在,则首先创建key对象并加入db中
            lobj = createquicklistobject(); // 初始化quicklist对象
            quicklistsetoptions(lobj->ptr, server.list_max_ziplist_size,
                                server.list_compress_depth); // 使用redis server的配置项做初始化
            dbadd(c->db,c->argv[1],lobj); // 把quicklist添加到redis db中
        }
        // 把新元素加入list中
        listtypepush(lobj,c->argv[j],where);
        pushed++;
    }
    addreplylonglong(c, waiting + (lobj ? listtypelength(lobj) : 0));
    if (pushed) {
        char *event = (where == list_head) ? "lpush" : "rpush";

        signalmodifiedkey(c->db,c->argv[1]);
        notifykeyspaceevent(notify_list,event,c->argv[1],c->db->id);
    }
    server.dirty += pushed;
}

 

再看下createquicklistobject:

/* create a new quicklist.
 * free 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;
    return quicklist;
}

 

2. 添加元素

继续看上面源码中的listtypepush方法:

void listtypepush(robj *subject, robj *value, int where) {
    if (subject->encoding == obj_encoding_quicklist) {
        int pos = (where == list_head) ? quicklist_head : quicklist_tail;
        value = getdecodedobject(value);
        size_t len = sdslen(value->ptr);// 计算新元素长度
        quicklistpush(subject->ptr, value->ptr, len, pos); // 加入到quicklist
        decrrefcount(value); 
    } else {
        serverpanic("unknown list encoding");
    }
}

继续看quicklistpush:

/* wrapper to allow argument-based switching between head/tail pop */
void quicklistpush(quicklist *quicklist, void *value, const size_t sz,
                   int where) {
    if (where == quicklist_head) {  // 添加到list头部
        quicklistpushhead(quicklist, value, sz);
    } else if (where == quicklist_tail) {  // 添加到list尾部
        quicklistpushtail(quicklist, value, sz);
    }
}

/* add new entry to head node of quicklist.
 *
 * returns 0 if used existing head.
 * returns 1 if new head created. 
 在quicklist的头部节点添加新元素:
 如果新元素添加在head中,返回0,否则返回1.
 */
int quicklistpushhead(quicklist *quicklist, void *value, size_t sz) {
    quicklistnode *orig_head = quicklist->head;
    // 如果head不为空,且空间大小满足新元素的存储要求,则新元素添加到head中,否则新加一个quicklistnode
    if (likely(
            _quicklistnodeallowinsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->zl =
            ziplistpush(quicklist->head->zl, value, sz, ziplist_head);
        quicklistnodeupdatesz(quicklist->head);
    } else {
        // 创建新的quicklistnode
        quicklistnode *node = quicklistcreatenode();
        // 把新元素添加到新建的ziplist中
        node->zl = ziplistpush(ziplistnew(), value, sz, ziplist_head);
        // 更新ziplist的长度到quicklistnode的sz字段,再把新node添加到quicklist中,即添加到原head前面
        quicklistnodeupdatesz(node);
        _quicklistinsertnodebefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

ziplistpush会把新元素添加到ziplist中,这部分代码后面文章再分析。

3. 获取元素

获取元素方法是quicklistpop方法(quicklist.c),如下:

/* default pop function
 *
 * returns malloc'd value from quicklist */
int quicklistpop(quicklist *quicklist, int where, unsigned char **data,
                 unsigned int *sz, long long *slong) {
    unsigned char *vstr;
    unsigned int vlen;
    long long vlong;
    if (quicklist->count == 0)
        return 0;
    // pop一个元素
    int ret = quicklistpopcustom(quicklist, where, &vstr, &vlen, &vlong,
                                 _quicklistsaver);
    if (data)
        *data = vstr;
    if (slong)
        *slong = vlong;
    if (sz)
        *sz = vlen;
    return ret;
}

具体实现在quicklistpopcustom:

/* pop from quicklist and return result in 'data' ptr.  value of 'data'
 * is the return value of 'saver' function pointer if the data is not a number.
 *
 * if the quicklist element is a long long, then the return value is returned in
 * 'sval'.
 *
 * return value of 0 means no elements available.
 * return value of 1 means check 'data' and 'sval' for values.
 * if 'data' is set, use 'data' and 'sz'.  otherwise, use 'sval'. 
 如果quicklist中无元素,返回0,否则返回1.
 当返回1时,需要检查data和sval两个字段:
 1. 如果是string类型,则把结果地址保存在data指针中,长度保存在sz。
 2. 如果是long long类型,则把值保存在sval字段中。
 */
int quicklistpopcustom(quicklist *quicklist, int where, unsigned char **data,
                       unsigned int *sz, long long *sval,
                       void *(*saver)(unsigned char *data, unsigned int sz)) {
    unsigned char *p;
    unsigned char *vstr;
    unsigned int vlen;
    long long vlong;
    int pos = (where == quicklist_head) ? 0 : -1;

    if (quicklist->count == 0)
        return 0;

    if (data)
        *data = null;
    if (sz)
        *sz = 0;
    if (sval)
        *sval = -123456789;

    quicklistnode *node;
    if (where == quicklist_head && quicklist->head) {
        node = quicklist->head;
    } else if (where == quicklist_tail && quicklist->tail) {
        node = quicklist->tail;
    } else {
        return 0;
    }
    // p: 0 取ziplist的第一个元素; -1 取ziplist的最后一个元素;
    p = ziplistindex(node->zl, pos);
    if (ziplistget(p, &vstr, &vlen, &vlong)) {
        if (vstr) {
            if (data)
                *data = saver(vstr, vlen);
            if (sz)
                *sz = vlen;
        } else {
            if (data)
                *data = null;
            if (sval)
                *sval = vlong;
        }
        // 从quicklist中删除该元素
        quicklistdelindex(quicklist, node, &p);
        return 1;
    }
    return 0;
}

再看下quicklistdelindex:

/* delete one entry from list given the node for the entry and a pointer
 * to the entry in the node.
 *
 * note: quicklistdelindex() *requires* uncompressed nodes because you
 *       already had to get *p from an uncompressed node somewhere.
 *
 * returns 1 if the entire node was deleted, 0 if node still exists.
 * also updates in/out param 'p' with the next offset in the ziplist. 
 从quicklistnode中删除一个entry:
 1. 从ziplist中删除entry。
 2. quicklistnode中的entry个数减1:
    如果quicklistnode中entry个数为0,则从quicklist中删除当前的quicklistnode。
    否则,更新quicklistnode中的sz字段。
 */
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;
}

 

至此,quicklist的主体结构代码,和主要的两个方法push和pop的代码就分析结束了,下一篇分析quicklist底层存储ziplist的源代码。

本篇内容参考了钱文品的《redis深度历险:核心原理与应用实践》,特此感谢!