Redis之quicklist源碼分析

一、quicklist簡介

Redis清單是簡單的字元串清單，按照插入順序排序。你可以添加一個元素到清單的頭部（左邊）或者尾部（右邊）。

一個清單最多可以包含 232 - 1 個元素 (4294967295, 每個清單超過40億個元素)。

其底層實作所依賴的内部資料結構就是quicklist，主要特點有：

list是一個雙向連結清單。
在list的兩端追加和删除資料極為友善，時間複雜度為O(1)。
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的增删改查

建立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(). */

*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;

添加元素

繼續看上面源碼中的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中，這部分代碼後面文章再分析。

擷取元素

擷取元素方法是quicklistPop方法（quicklist.c），如下：

/* Default pop function

Returns malloc'd value from quicklist */

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兩個字段：

如果是string類型，則把結果位址儲存在data指針中，長度儲存在sz。
如果是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：

從ziplist中删除entry。
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://github.com/tomliugen

原文位址

https://www.cnblogs.com/xinghebuluo/p/12722103.html

Redis之quicklist源碼分析

繼續閱讀

OS-written test2

壓縮編碼M-JPEG、MPEG4、H.264

redis管理常用指令

django短信驗證碼的後端實作

Redis訂閱了一段時間後訂閱失效了（ redisTemplate.convertAndSend）

2022秋招面試總結（cpp+java+測開）百度測開一面位元組後端一面蝦皮後端一面蝦皮後端二面

轉詳解C#資料庫存取圖檔三大方式

BMP檔案結構及圖像每行位元組計算方法

磁盤結構及在Linux中的命名

資料遷移方法資料遷移原則資料遷移之雙寫方案資料遷移之級聯同步方案

微服務-性能壓測\緩存redis和分布式鎖redisson和SpringCache

Nacos 2.0 更新前後性能對比壓測

Spring資料和Redis

redis叢集資料一緻性_RedisRaft為Redis叢集帶來強大的資料一緻性

supervisor 管理redis 和httpd 環境centos7

Redis簡介一(單機版)發展曆程Redis