redis學習筆記-list原理

list 基本功能

圖表來自：https://www.cnblogs.com/amyzhu/p/13466311.html

單鍊錶

在學習redis 的list 實作之前，我們先來看看單鍊錶list 怎麼實作：

每一個節點都有一個向後的指標（引用）指向下一個節點，最後一個節點指向NULL表示結束，有一個Head（頭）指標指向第一個節點表示開始。

類似於這樣，新建和刪除雖然只需要O(1) ，但是查找需要O(n) 的時間；無法反向查找，一旦錯過需要從頭開始。

增加一個節點：

刪除一個節點：

雙向鍊錶

雙向鍊錶也叫雙鍊錶，是鍊錶的一種，它的每個資料結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鍊錶中的任一個結點開始，都可以很方便地存取它的前驅結點和後繼結點。

特點：

1. #每次都在插入或刪除某個節點時, 需要處理四個節點的引用, 而不是兩個. 實現起來要困難一些

2. #相對於單向鍊錶, 必然佔用內存空間更大一些.

3. 既可以從頭到尾遍歷到尾, 又可以從尾遍歷到頭

這好像就解決redis 可以實現前後都可以遍歷的問題了。

那我們來看看redis 的鍊錶## 怎麼處理的：

再來看它的結構體定義原始碼

#ListNode：

typedef struct listNode
{
    // 前驱节点
    struct listNode *prev;
    // 后继节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

List：

typedef struct listNode
{
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void *(*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr,void *key)
} list;

redis 鍊錶的特性：

• 雙向無環：鍊錶節點帶有前驅、後繼指標取得某個節點的前驅、後繼節點的時間複雜度為O(1)，表頭節點的前驅指標和表尾節點的後繼指標都指向NULL，對鍊錶的存取以NULL為終點。

• 長度計數器：透過List結構的len屬性取得節點數量的時間複雜度為O(1)。

由於 list 還存在一個記憶體分配不連續，並引發的記憶體碎片的問題，是否有辦法讓他們的記憶體優化一下？

redis 壓縮列表

ZipList不是基礎資料結構，是Redis自己設計的一種資料儲存結構。它有點類似數組，透過一片連續的記憶體空間來儲存資料。

與陣列不同的是，它允許所儲存的清單元素所佔據的記憶體空間不同。說到壓縮這兩個字，大家第一時間可能想到的就是節省記憶體。之所以說這種儲存結構節省內存，是相對數組而言的。

我們都知道，陣列要求每個元素儲存空間的大小相同，如果我們要儲存不同長度的字串，就要以最大長度的字串所佔的儲存空間作為字串陣列每個元素儲存空間的大小（假如是50位元組）。

因此在字元數數值中儲存小於50位元組長度的字串時就會浪費一部分儲存空間。

陣列 的優點就是佔用一片連續的空間，可以善用CPU快取快速存取資料。

如果既想保留陣列的這種優勢又想節省儲存空間，那麼我們可以壓縮陣列：

不過，有一個問題，在遍歷壓縮列表的時候我們並不知道每個元素佔用的記憶體大小是多少，因此無法計算出下一個元素的特定起始位置。

但是轉念一想，如果每個元素訪問之前我們能有它的長度，那麼不就可以解決這個問題了嘛。

接下來我們來看看Redis如何透過實作ZipList使之結合既保留了陣列的優點又節省了記憶體。

• zlbytes：压缩列表的字节长度，是uint32_t类型，占4字节，因此压缩列表最多有232-1字节，可以通过该值计算zlend的位置，也可以在内存重新分配的时候使用。

• zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，是uint32_t类型，占4字节，可以通过该值快速定位到列表尾元素的位置。

• zllen：压缩列表元素的个数，是uint16_t类型，占2字节，表示最多存储的元素个数为216-1=65 535，如果需要计算总数量，则需要遍历整个压缩列表。

• entryx：压缩列表存储的元素，既可以是字节数组，也可以是整数，长度不限。

• zlend：压缩列表的结尾，是uint8_t类型，占1字节，恒为0xFF。

• previous_entry_length：表示前一个元素的字节长度，占1字节或者5字节，当前元素的长度小于254时用1字节，大于等于254时用5字节，previous_entry_length 字段的第一个字节固定是0xFE，后面的4字节才是真正的前一个元素的长度。

• encoding：表示元素当前的编码，有整数或者字节数。为了节省内存，encoding字段长度可变。

• content：表示当前元素的内容。

ZipList变量的读取和赋值都是通过宏来实现的，代码片段如下：

//返回整个压缩列表的总字节
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//返回压缩列表的tail_offset变量，方便获取最后一个节点的位置
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//返回压缩列表的节点数量
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

//返回压缩列表的表头的字节数
//（内存字节数zlbytes，最后一个节点地址ztail_offset,节点总数量zllength）
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

//返回压缩列表最后结尾的字节数
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

//返回压缩列表首节点地址
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

//返回压缩列表尾节点地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

//返回压缩列表最后结尾的地址
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

对此，可以通过定义的结构体和对应的操作定义知道大概 redis 设计 压缩list 的思路；

这种方式虽然节约了空间，但是会存在每次插入和创建存在内存重新分配的问题。

quicklist

quicklist是Redis 3.2中新引入的数据结构，能够在时间效率和空间效率间实现较好的折中。Redis中对quciklist的注释为A doubly linked list of ziplists。顾名思义，quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。

当ziplist节点个数过多，quicklist退化为双向链表，一个极端的情况就是每个ziplist节点只包含一个entry，即只有一个元素。当ziplist元素个数过少时，quicklist可退化为ziplist，一种极端的情况就是quicklist中只有一个ziplist节点。

quicklist 结构定义:

typedef struct quicklist {
    // 指向quicklist的首节点
    quicklistNode *head;
    // 指向quicklist的尾节点
    quicklistNode *tail;
    // quicklist中元素总数
    unsigned long count;        /* total count of all entries in all ziplists */
    // quicklistNode节点个数
    unsigned long len;          /* number of quicklistNodes */
    // ziplist大小设置，存放list-max-ziplist-size参数的值
    int fill : 16;              /* fill factor for individual nodes */
    // 节点压缩深度设置，存放list-compress-depth参数的值
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: 4;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

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

redis为了节省内存空间，会将quicklist的节点用LZF压缩后存储，但这里不是全部压缩，可以配置compress的值，compress为0表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩；compress如果是1，表示从两端开始，有1个节点不做LZF压缩。compress默认是0(不压缩)，具体可以根据你们业务实际使用场景去配置。

redis 的配置文件可以配置该参数

list-compress-depth 0

還有個fill字段，它的意義是每個quicknode的節點最大容量 ，不同的數值有不同的意義，預設是-2，當然也可以配置為其他數值；

list-max-ziplist-size -2

• 當值為正數時，表示quicklistNode節點上的ziplist的長度。例如當這個值為5時，每個quicklistNode節點的ziplist最多包含5個資料項目

• #當值為負數時，表示依照位元組數來限制quicklistNode節點上的ziplist的長度，可選值為-1 到-5。

為什麼會有設定提供出來？

• ziplist越短，記憶體碎片增多，影響儲存效率。當一個ziplist只存一個元素時，quicklist又退化成雙向鍊錶了

• ziplist越長，為ziplist分配大的連續的記憶體空間難度也就越大，會造成很多小塊的記憶體空間被浪費，當quicklist只有一個節點，元素都存在一個ziplist上時，quicklist又退化成ziplist了

#結束語

雖然沒有完全去理解它的原始碼，但我們也可以透過這篇文章來熟悉redis 的一個設計想法。並知道它是怎麼一步一步優化過來的。讓我們有一個大概的表現認知。