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 中。

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

查看所有标签

猜你喜欢:

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

码农书籍

计算群体智能基础

恩格尔伯里特 / 谭营 / 2009-10 / 69.00元

《计算群体智能基础》全面系统地介绍了计算群体智能中的粒子群优化(PSO)和蚁群优化(ACO)的基本概念、基本模型、理论分析及其应用。在简要介绍基本优化理论和总结各类优化问题之后，重点介绍了社会网络结构如何在个体间交换信息以及个体聚集行为如何形成一个功能强大的有机体。在概述了进化计算后，重点论述了粒子群优化和蚁群优化的基本模型及其各种变体，给出了分析粒子群优化模型的一种通用方法，证明了基于蚂蚁行为实......一起来看看《计算群体智能基础》这本书的介绍吧!

码农工具