一, 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 的源代码.
来源: https://www.cnblogs.com/xinghebuluo/p/12722103.html