京東雲開發者| Redis資料結構(二)-List、Hash、Set及Sorted Set的結構實現

1 引言

之前介紹了Redis的資料儲存及String型別的實現，接下來再來看下List、Hash、Set及Sorted Set的資料結構的實現。

2 List

List型別通常被用作非同步訊息佇列、文章列表查詢等；儲存有序可重複資料或做為簡單的訊息推播機制時，可以使用Redis的List型別。對於這些資料的儲存通常會使用連結串列或者陣列作為儲存結構。

• 使用陣列儲存，隨機存取節點通過索引定位時間複雜度為O(1)。但在初始化時需要分配連續的記憶體空間；在增加資料時，如果超過當前分配空間，需要將資料整體搬遷移到新陣列中。
• 使用連結串列儲存，在進行前序遍歷或後續遍歷，當前節點中要儲存前指標和後指標，這兩個指標在分別需要8byte共16byte空間儲存，存在大量節點會因指標占用過多空間。連結串列雖然不需要連續空間儲存可以提高記憶體利用率，但頻繁的增加和刪除操作會使記憶體碎片化，影響資料讀寫速率。

如果我們能夠將連結串列和陣列的特點結合起來就能夠很好處理List型別的資料儲存。

2.1 ZipList

3.2之前Redis使用的是ZipList，具體結構如下：

• zlbytes: 4byte 記錄整個壓縮列表佔用的記憶體位元組數：在對壓縮列表進行記憶體重分配， 或者計算 zlend 的位置時使用。
• zltail：4byte 記錄壓縮列表表尾節點距離壓縮列表的起始地址有多少位元組： 通過這個偏移量，程式無須遍歷整個壓縮列表就可以確定表尾節點的地址。
• zllen：2byte 記錄了壓縮列表包含的節點數量： 當這個屬性的值小於 UINT16_MAX（65535）時， 這個屬性的值就是壓縮列表包含節點的數量； 當這個值等於UINT16_MAX 時，節點的真實數量需要遍歷整個壓縮列表才能計算得出。
• entry X：壓縮列表包含的各個節點，節點的長度由節點儲存的內容決定。包含屬性如下：
• prerawlen：記錄前一個節點所佔記憶體的位元組數，方便查詢上一個元素地址
• len：data根據len的首個byte選用不同的資料型別來儲存data
• data：本元素的資訊
• zlend: 尾節點 恆等於255

ziplist是一個連續的記憶體塊，由表頭、若干個entry節點和壓縮列表尾部識別符號zlend組成，通過一系列編碼規則，提高記憶體的利用率，使用於儲存整數和短字串。每次增加和刪除資料時，所有資料都在同一個ziplist中都會進行搬移操作。如果將一個組資料按閾值進行拆分出多個資料，就能保證每次只操作某一個ziplist。3.2之後使用的quicklist與ziplist。

2.2 QuickList

quicklist就是維護了一種宏觀上的雙端連結串列(類似於B樹)，連結串列的節點為對ziplist包裝的quicklistNode，每個quciklistNode都會通過前後指標相互指向，quicklist包含頭、尾quicklistNode的指標。

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 : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
   ...
} quicklist;

• *head：表頭節點
• *tail：表尾節點
• count：節點包含entries數量
• len：quicklistNode節點計數器
• fill：儲存ziplist的大小，組態檔設定
• compress：儲存壓縮程度值，組態檔設定

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 */
    。。。
} quicklistNode;

• *prev：前置節點
• *next：後置節點
• *zl：不進行壓縮時指向一個ziplist結構，壓縮時指向quicklistLZF結構(具體內容請參考下方連結)
• sz：ziplist個數
• count：ziplist中包含的節點數

在redis.conf通過設定每個ziplist的最大容量，quicklist的資料壓縮範圍,提升資料存取效率,單個ziplist節點最大能儲存量，超過則進行分裂，將資料儲存在新的ziplist節點中

-5: max size: 64 Kb <— not recommended for normal workloads

-4: max size: 32 Kb <— not recommended

-3: max size: 16 Kb <— probably not recommended

-2: max size: 8 Kb <— good

-1: max size: 4 Kb <— good

List-max-ziplist-size -2
0代表所有節點，都不進行壓縮，1.代表從頭節點往後一個，尾結點往前一個不用壓縮，其它值以此類推
List-compress-depth 1

Redis 的連結串列實現的特性可以總結如下：

• 雙端：連結串列節點帶有prev和next指標， 獲取某個節點的前置節點和後置節點的複雜度都是O(1) 。
• 無環：表頭節點的prev指標和表尾節點的next指標都指向NULL，對連結串列的存取以NULL為終點。
• 帶表頭指標和表尾指標：通過list結構的head指標和tail指標，程式獲取連結串列的表頭節點和表尾節點的複雜度為O(1) 。
• 帶連結串列長度計數器：程式使用list結構的len屬性來對list持有的連結串列節點進行計數，程式獲取連結串列中節點數量的複雜度為O(1)。

3 Hash

儲存一個物件，可以直接將該物件進行序列化後使用String型別儲存，再通過反序列化獲取物件。對於只需要獲取物件的某個屬性的場景，可以將將每個屬性分別儲存；但這樣在Redis的dict中就會存在大量的key，對於鍵時效後的回收效率存在很大影響。使用Map結構就可以再dict的儲存中只存在一個key並將屬性與值再做關聯。

Redis的Hash資料結構也是使用的dict(具體實現可以檢視上一篇，淺談Redis資料結構(上)-Redis資料儲存及String型別的實現)實現。當資料量比較小，或者單個元素比較小時，底層使用ziplist儲存，資料量大小和元素數量有如下設定：

ziplist元素個數超過512，將改為hashtable編碼
hash-max-ziplist-entries 512
單個元素大小超過64byte時，將改為hashtable編碼
hash-max-ziplist-value 64

4 Set

Set型別可以在對不重複集合操作時使用，可以判斷元素是否存在於集合中。Set資料結構底層實現為value為null的dict，當資料可以使用整形表示時，Set集合將被編碼為intset結構。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

整數集合是一個有序的，儲存整型資料的結構。整型集合在Redis中可以儲存xxxx的整型資料，並且可以保證集合中不會出現重複資料。

使用intset可以節省空間，會根據最大元素範圍確定所有元素型別；元素有序儲存在判斷某個元素是否存在時可以基於二分查詢。但在以下任意條件不滿足時將會使用hashtable儲存資料。

• 元素個數大於設定的set-max-inset-entries值
• 元素無法用整型表示

5 Sorted Set

連續空間儲存資料，每次增加資料都會對全量資料進行搬運。對於有序連結串列查詢指定元素，只能通過頭、尾節點遍歷方式進行查詢，如果將每個資料增加不定層數的索引，索引之間相互關聯，尋找指定或範圍的元素時就可以通過遍歷層級的索引來確定元素所處範圍，減少空間複雜度。跳躍表是一種可以對有序連結串列進行近似二分查詢的資料結構，redis 在兩個地方用到了跳躍表，一個是實現有序集合，另一個是在叢集節點中用作內部資料結構。

跳躍表 ( skiplist ) 是一種有序資料結構，自動去重的集合資料型別，ZSet資料結構底層實現為字典(dict) + 跳錶(skiplist)。它通過在每個節點中維持多個指向其他節點的指標，從而達到快速存取節點的目的。支援平均O ( logN ) 、最壞 O(N) 複雜度的節點查詢，還可以通過順序性操作來批次處理節點。

資料比較少時，用ziplist編碼結構儲存，包含的元素數量比較多，又或者有序集合中元素的成員(member) 是比較長的字串時，Redis 就會使用跳躍表來作為有序集合鍵的底層實現。

元素個數超過128，將用skiplist編碼
zset-max-ziplist-entries 128

單個元素大小超過64 byte，將用skiplist編碼
zset-max-ziplist-value 64

5.1 跳躍表

zset結構如下：

typedef struct zset {
    // 字典，儲存資料元素
    dict *dict;
    // 跳躍表，實現範圍查詢
    zskiplist *zsl;
} zset;
robj *createZsetObject(void) {
    // 分配空間
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;
    // dict用來查詢資料到分數的對應關係，zscore可以直接根據元素拿到分值
    zs->dict = dictCreate(&zsetDictType,NULL);
    // 建立skiplist
    zs->zsl = zslCreate();
    o = createObject(OBJ_ZSET,zs);
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}

zskiplist

typedef struct zskiplist {
    // 頭、尾節點;頭節點不儲存元素，擁有最高層高
    struct zskiplistNode *header, *tail;
    unsigned long length;
    // 層級,所有節點中的最高層高
    int level;
} zskiplist;
typedef struct zskiplistNode {
    // 元素member值
    sds ele;
    // 分值
    double score;
    // 後退指標
    struct zskiplistNode *backward;
    // 節點中用 L1、L2、L3 等字樣標記節點的各個層， L1代表第一層， L2代表第二層，以此類推。
    struct zskiplistLevel {
        // 指向本層下一個節點，尾節點指向null
        struct zskiplistNode *forward;
        // *forward指向的節點與本節點之間的元素個數，span值越大，跳過的節點個數越多
        unsigned long span;
    } level[];
} zskiplistNode;

結構圖如下：

5.2 建立節點及插入流程

SkipList初始化，建立一個有最高層級的空節點：

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    // 分配空間
    zsl = zmalloc(sizeof(*zsl));
    // 設定起始層次
    zsl->level = 1;
    // 元素個數
    zsl->length = 0;
    // 初始化表頭，表頭不儲存元素，擁有最高的層級
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    // 初始化層高
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    // 設定表頭後退指標為NULL
    zsl->header->backward = NULL;
    // 初始表尾為NULL
    zsl->tail = NULL;
    return zsl;
}

新增元素：

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    serverAssert(!isnan(score));
    x = zsl->header;
    // 遍歷所有層高，尋找插入點：高位 -> 低位
    for (i = zsl->level-1; i >= 0; i--) {
        // 儲存排位，便於更新
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
                // 找到第一個比新分值大的節點，前面一個位置即是插入點
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    // 相同分值則按字典順序排序
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            // 累加跨度
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        // 每一層的拐點
        update[i] = x;
    }
    // 隨機生成層高，以25%的概率決定是否出現下一層，越高的層出現概率越低
    level = zslRandomLevel();
    // 隨機層高大於當前的最大層高，則初始化新的層高
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    // 建立新的節點
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        // 插入新節點，將新節點的當前層前指標更新為被修改節點的前指標
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;


        // 新節點跨度為後一節點的跨度 - 兩個節點之間的跨度
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    // 新節點加入，更新頂層 span
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    // 更新後退指標和尾指標
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x
}

5.3 SkipList與平衡樹的比較

skiplist是為了實現sorted set相關功能，紅黑樹也能實現，並且sorted set會儲存更多的冗餘資料。Redis作者antirez曾回答過這個問題，原文見https://news.ycombinator.com/item?id=1171423

大致內容如下：

skiplist只需要調整下節點到更高level的概率，就可以做到比B樹更少的記憶體消耗。
sorted set面對大量的zrange和zreverange操作，作為單連結串列遍歷的實現效能不亞於其它的平衡樹。
實現比較簡單。

6 參考學習

• 《Redis 設計與實現》：https://www.w3cschool.cn/hdclil/cnv2lozt.html
• 雙端列表：https://blog.csdn.net/qq_20853741/article/details/111946054

---

作者：盛旭