Redis-list类型

栏目: 数据库 · 发布时间: 5年前

内容简介：存储list的编码只有一种虽然编码只有一种，但是除quicklist这个结构之外，还用到了ziplist。以quicklist的编码方式存储list，存储结构是

存储list的编码只有一种 quicklist （redis4.0），原来的linkedlist已经不用了。

虽然编码只有一种，但是除quicklist这个结构之外，还用到了ziplist。

quicklist

以quicklist的编码方式存储list，存储结构是 元素为ziplist的链表 ，而ziplist存储了一个或多个entry，entry里面即为存储的值。

简单的示意图如下：

Redis-list类型

ziplist和quicklistNode中均存储了对应单元内entry的数量，很方便range操作。

同时，插入也非常便捷，只要往ziplist里面添加内容即可，如果ziplist放不下，插入一个quicklistNode再往其ziplist中填写即可。

quicklist定义如下：

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 : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode结构：

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;

ziplist和sds一样，没有对应的结构体，结构注释如下：

/* <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> */
/* ziplist    尾部偏移 entry数							1byte结束标志

顺便提一下，在写这篇文章的时候在quicklist.c中发现一个quicklistEntry的结构，不过文件中有一个注释

/* Node, quicklist, and Iterator are the only data structures used currently. */

源码

相关的结构已经在上面列出来了，下面分析一下lpush这个命令的执行过程，以 lpush names Taylor Ed Alan 为例。

lpush

和上次分析String一样，很容易地能在server.c中找到lpush命令对应的处理函数 lpushCommand 。

// t_list.c
void lpushxCommand(client *c) {
    pushxGenericCommand(c,LIST_HEAD);
}

void pushGenericCommand(client *c, int where) {
    int j, 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++) {
        if (!lobj) {
            // 如果之前不存在这个list，创建一个Quicklist
            lobj = createQuicklistObject();		//#关键点一
            // 这个函数设置了quicklist struct中的两个字段
            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++;
    }
    
    // 忽略一些代码...
}

关键点一–quicklist的创建

在使用lpush命令的时候，如果之前不存在这样一个list，那么将会调用createQuicklistObject创建一个list。

Note:从上面可以看出初始的list就是quicklist。

// object.c
robj *createQuicklistObject(void) {
    quicklist *l = quicklistCreate();	// 先创建一个quicklist
    robj *o = createObject(OBJ_LIST,l);	// 然后由这个quicklist创建robj对象
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}

// quicklist.c
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;
}

// object.c
robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}

关键点二–添加元素

添加元素的代码在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);
        decrRefCount(value);
    } else {
        serverPanic("Unknown list encoding");
    }
}

quicklistPush：

// quicklist.c
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                   int where) {
    if (where == QUICKLIST_HEAD) {
        quicklistPushHead(quicklist, value, sz);
    } else if (where == QUICKLIST_TAIL) {
        quicklistPushTail(quicklist, value, sz);
    }
}

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    // 这个likely和可能会遇到的unlikely在阅读源码时可以忽略
    // 他们的作用是给编译器提示，使其合理安排分支的顺序
    // 利用cpu的分支预测功能来提高性能，具体的就不展开了
    if (likely(		
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        // 这个if分支是直接在ziplist中插入数据
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        // 这个else分支，先生成一个node，把node插入到list中，然后在node的ziplist中插入数据
        quicklistNode *node = quicklistCreateNode();	// 新增一个list执行这里
        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);
}

关键点三–插入到ziplist还是新建node

上面在添加元素的时候，进行了一次判断，判断逻辑如下：

插入新quicklistNode的情况：

传入的node为NULL时
数据插入到ziplist中后导致ziplist过大时

判断代码在 _quicklistNodeAllowInsert 中。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

工程问题C++语言求解

Delores M.Etter、Jeanine A.Ingber / 冯力、周凯 / 机械工业出版社 / 2014-8 / 79元

本书介绍了如何利用ANSIC++编程语言以基于对象的编程方式来解决工程问题。书中引用了大量来自于不同工程、科学和计算机科学领域的示例，是一本理论和实践结合紧密的教材。针对C++基本语法的各个部分，由浅入深地进行讲解。每讲解一部分基础知识，同时会结合多个相关实例，实例内容详实，紧贴所讲内容，使读者能够立刻对所学知识进行练习，实战性强。一起来看看《工程问题C++语言求解》这本书的介绍吧!

码农工具