摘要：前言在上一章中我們介紹了的一些內(nèi)部原理在這一章中我們?cè)賮碛懻撛谖宸N數(shù)據(jù)結(jié)構(gòu)中的基本使用和一些內(nèi)部實(shí)現(xiàn)基本介紹的呢相當(dāng)于中的也是雙向鏈表具有一些和同樣的特征比如插入和刪除一條很快時(shí)間復(fù)雜度為獲取頭結(jié)點(diǎn)和尾節(jié)點(diǎn)也很快時(shí)間復(fù)雜度也為隨機(jī)讀取則相對(duì)

在上一章中我們介紹了 String 的一些內(nèi)部原理,在這一章中我們?cè)賮碛懻撛谖宸N數(shù)據(jù)結(jié)構(gòu)中 List 的基本使用和一些內(nèi)部實(shí)現(xiàn).

Redis的List 呢相當(dāng)于 Java 中的 LinkedList,也是雙向鏈表.具有一些和 LinkedList 同樣的特征,比如插入和刪除一條很快,時(shí)間復(fù)雜度為 O(1),獲取頭結(jié)點(diǎn)和尾節(jié)點(diǎn)也很快,時(shí)間復(fù)雜度也為 O(1),隨機(jī)讀取則相對(duì)較慢時(shí)間復(fù)雜度為 O(n).常用作消息隊(duì)列.

當(dāng)做隊(duì)列使用時(shí),遵循先進(jìn)先出原則:

> rpush books python java golang
(integer) 3
> lpop books
"python"
> lpop books
"java"

當(dāng)做棧使用時(shí),遵循先進(jìn)后出原則:

> rpush books python java golang
(integer) 3
> rpop books
"golang"
> rpop books
"java"

同時(shí)還可以通過 get(index)的方法獲取:

> rpush books python java golang
(integer) 3
> lindex books 0
"python"
> lindex books -1
"golang"

index從 0 開始,可以為負(fù)數(shù) -1 代表倒數(shù)第一個(gè)元素

上述部分我們把 Redis 中的 List當(dāng)做 Java 中的 LinkedList 操作,因?yàn)橛泻芏嘞嗤牟糠?但實(shí)際上在 Redis 中鏈表的內(nèi)部實(shí)現(xiàn)可不是一個(gè)簡單的雙向鏈表.在數(shù)據(jù)量較少的時(shí)候它的底層存儲(chǔ)結(jié)構(gòu)為一塊連續(xù)內(nèi)存,稱之為ziplist(壓縮列表).當(dāng)數(shù)據(jù)量較多的時(shí)候?qū)?huì)變成鏈表的結(jié)構(gòu).后來因?yàn)殒湵硇枰?prev 和 next 兩個(gè)指針占用內(nèi)存很多,改用 ziplist+鏈表的混合結(jié)構(gòu),稱之為 quicklist(快速鏈表).在新的版本中 Redis 鏈表統(tǒng)一使用 quicklist來存儲(chǔ).下面我們就來詳細(xì)介紹這種數(shù)據(jù)結(jié)構(gòu).

先來看看 ziplist 的數(shù)據(jù)結(jié)構(gòu):

struct ziplist{
    int32 zlbytes;            //壓縮列表占用字節(jié)數(shù)
    int32 zltail_offset;    //最后一個(gè)元素距離起始位置的偏移量,用于快速定位到最后一個(gè)節(jié)點(diǎn)
    int16 zllength;            //元素個(gè)數(shù)
    T[] entries;            //元素內(nèi)容
    int8 zlend;                //結(jié)束位 0xFF
}

如圖所示:

有了 ztail_offset 就可以快速的定位到最后一個(gè)節(jié)點(diǎn),這樣就可以倒序遍歷了.也就是說 ziplist支持雙向遍歷.

下面再來看下 entry 的內(nèi)部實(shí)現(xiàn):

struct entry{
    int prevlen;            //前一個(gè) entry 的長度
    int encoding;            //元素類型編碼
    optional byte[] content;    //元素內(nèi)容
}

當(dāng) ziplist 倒序遍歷的時(shí)候,就是通過這個(gè)pervlen定位到前一個(gè)元素位置的.

encoding 保存了 content 的編碼類型.

content 則是保存的元素內(nèi)容,它是optional 類型表示是這個(gè)字段是可選的.當(dāng)content 是很小的整數(shù)時(shí),他會(huì)內(nèi)聯(lián)到 encoding 字段的尾部.

quicklist 是 ziplist 和鏈表的混合體.下面是 quicklist和 node 的部分?jǐn)?shù)據(jù)結(jié)構(gòu):

struct quicklist{
    quicklistNode* head;    //指向頭結(jié)點(diǎn)
    quicklistNode* tail;    //指向尾節(jié)點(diǎn)
    long count;                //元素總數(shù)
    int nodes;                //quicklistNode節(jié)點(diǎn)的個(gè)數(shù)
    int compressDepth;        //壓縮算法深度
    ...
}

為了節(jié)約空間 Redis 還會(huì)對(duì) ziplist 使用 LZF 算法進(jìn)行壓縮,可以選擇壓縮深度.我們待會(huì)在說.

如上圖所示,quicklist含有兩個(gè) quicklistNode 代表頭結(jié)點(diǎn)和尾節(jié)點(diǎn),其中每個(gè)head 和 tail 之間是雙向鏈表.每個(gè)quicklistNode指向一個(gè) ziplist.

struct quicklistNode{
    quicklistNode* prev;    //前一個(gè)節(jié)點(diǎn)
    quicklistNode* next;    //后一個(gè)節(jié)點(diǎn)
    ziplist* zl;            //壓縮列表
    int32 size;                //ziplist大小
    int16 count;            //ziplist 中元素?cái)?shù)量
    int2 encoding;            //編碼形式 存儲(chǔ) ziplist 還是進(jìn)行 LZF 壓縮儲(chǔ)存
    ...
}

在 quicklist 中每個(gè) ziplist 默認(rèn)大小是 8kb,超出這個(gè)字節(jié)就會(huì)增加一個(gè) ziplist.這個(gè)默認(rèn)大小是可配置的,由list-max-ziplist-size決定.

上面說到 ziplist 可以使用 LZF 算法壓縮,通過list-compress-depth配置.默認(rèn)情況下quicklist 的壓縮深度是 0,也就是不壓縮.配置為 1 的話代表從頭/尾開始第 1 個(gè)ziplsit 進(jìn)行壓縮.

下章預(yù)告,Redis 數(shù)據(jù)結(jié)構(gòu)之 Hash