Redis之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的元素,示意图如下:
图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深度历险:核心原理与应用实践》,特此感谢!
上一篇: 都是我的错
下一篇: 判断Input上传文件类型,文件大小