一、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的元素,示意圖如下:
圖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深度歷險:核心原理與應用實踐》,特此感謝!