來源：cnblogs.com/lonely-wolf/p/14281136.html

前言

正常情況下我們選擇使用 Redis 就是為了提升查詢速度，然而讓人意外的是，Redis 當(dāng)中卻有一種比較有意思的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)通過犧牲部分讀寫速度來達(dá)到節(jié)省內(nèi)存的目的，這就是 ziplist（壓縮列表），Redis 為什么要這么做呢？難道真的是覺得自己的速度太快了，犧牲一點(diǎn)速度也不影響嗎？

什么是壓縮列表

ziplist 是為了節(jié)省內(nèi)存而設(shè)計(jì)出來的一種數(shù)據(jù)結(jié)構(gòu)。ziplist 是由一系列特殊編碼組成的連續(xù)內(nèi)存塊的順序型數(shù)據(jù)結(jié)構(gòu)，一個(gè) ziplist 可以包含任意多個(gè) entry，而每一個(gè) entry 又可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

ziplist 作為一種列表，其和普通的雙端列表，如 linkedlist 的最大區(qū)別就是 ziplist 并不存儲(chǔ)前后節(jié)點(diǎn)的指針，而 linkedlist 一般每個(gè)節(jié)點(diǎn)都會(huì)維護(hù)一個(gè)指向前置節(jié)點(diǎn)和一個(gè)指向后置節(jié)點(diǎn)的指針。那么 ziplist 不維護(hù)前后節(jié)點(diǎn)的指針，它又是如何尋找前后節(jié)點(diǎn)的呢？

ziplist 雖然不維護(hù)前后節(jié)點(diǎn)的指針，但是它卻維護(hù)了上一個(gè)節(jié)點(diǎn)的長度和當(dāng)前節(jié)點(diǎn)的長度，然后每次通過長度來計(jì)算出前后節(jié)點(diǎn)的位置。既然涉及到了計(jì)算，那么相對(duì)于直接存儲(chǔ)指針的方式肯定有性能上的損耗，這就是一種典型的用時(shí)間來換取空間的做法。

因?yàn)槊看巫x取前后節(jié)點(diǎn)都需要經(jīng)過計(jì)算才能得到前后節(jié)點(diǎn)的位置，所以會(huì)消耗更多的時(shí)間，而在 Redis 中，一個(gè)指針是占了 8 個(gè)字節(jié)，但是大部分情況下，如果直接存儲(chǔ)長度是達(dá)不到 8 個(gè)字節(jié)的，所以采用存儲(chǔ)長度的設(shè)計(jì)方式在大部分場景下是可以節(jié)省內(nèi)存空間的。

ziplist 的存儲(chǔ)結(jié)構(gòu)

ziplist 的組成結(jié)構(gòu)為：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

其中 zlbytes，zltail，zllen 為 ziplist 的 head 部分，entry 為 ziplist 的 entries 部分，每一個(gè) entry 代表一個(gè)數(shù)據(jù)，最后 zlend 表示 ziplist 的 end 部分，如下圖所示：

ziplist 中每個(gè)屬性代表的含義如下表格所示：

entry 存儲(chǔ)結(jié)構(gòu)

ziplist 的 head 和 end 存的都是長度和標(biāo)記，而 entry 存儲(chǔ)的是具體元素，這又是經(jīng)過特殊的設(shè)計(jì)的一種存儲(chǔ)格式，每個(gè) entry 都以包含兩段信息的元數(shù)據(jù)作為前綴，每一個(gè) entry 的組成結(jié)構(gòu)為：

<prevlen> <encoding> <entry-data>

prevlen

prevlen 屬性存儲(chǔ)了前一個(gè) entry 的長度，通過此屬性能夠從后到前遍歷列表。 prevlen 屬性的長度可能是 1 字節(jié)也可能是 5 字節(jié)：

當(dāng)鏈表的前一個(gè) entry 占用字節(jié)數(shù)小于 254，此時(shí) prevlen 只用 1 個(gè)字節(jié)進(jìn)行表示。

<prevlen from 0 to 253> <encoding> <entry>

當(dāng)鏈表的前一個(gè) entry 占用字節(jié)數(shù)大于等于 254，此時(shí) prevlen 用 5 個(gè)字節(jié)來表示，其中第 1 個(gè)字節(jié)的值固定是 254（相當(dāng)于是一個(gè)標(biāo)記，代表后面跟了一個(gè)更大的值），后面 4 個(gè)字節(jié)才是真正存儲(chǔ)前一個(gè) entry 的占用字節(jié)數(shù)。

0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>

注意：1 個(gè)字節(jié)完全你能存儲(chǔ) 255 的大小，之所以只取到 254 是因?yàn)?nbsp;zlend 就是固定的 255，所以 255 這個(gè)數(shù)要用來判斷是否是 ziplist 的結(jié)尾。

encoding

encoding 屬性存儲(chǔ)了當(dāng)前 entry 所保存數(shù)據(jù)的類型以及長度。encoding 長度為 1 字節(jié)，2 字節(jié)或者 5 字節(jié)長。前面我們提到，每一個(gè) entry 中可以保存字節(jié)數(shù)組和整數(shù)，而 encoding 屬性的第 1 個(gè)字節(jié)就是用來確定當(dāng)前 entry 存儲(chǔ)的是整數(shù)還是字節(jié)數(shù)組。當(dāng)存儲(chǔ)整數(shù)時(shí)，第 1 個(gè)字節(jié)的前兩位總是 11，而存儲(chǔ)字節(jié)數(shù)組時(shí)，則可能是 00、01 和 10 三種中的一種。

當(dāng)存儲(chǔ)整數(shù)時(shí)，第 1 個(gè)字節(jié)的前 2 位固定為 11，其他位則用來記錄整數(shù)值的類型或者整數(shù)值（下表所示的編碼中前兩位均為 11）：

注意：xxxx 四位編碼范圍是 0000-1111，但是 0000，1111 和 1110 已經(jīng)被表格中前面表示的數(shù)據(jù)類型占用了，所以實(shí)際上的范圍是 0001-1101，此時(shí)能保存數(shù)據(jù) 1-13，再減去 1 之后范圍就是 0-12。至于為什么要減去 1 是從使用習(xí)慣來說 0 是一個(gè)非常常用的數(shù)據(jù)，所以才會(huì)選擇統(tǒng)一減去 1 來存儲(chǔ)一個(gè) 0-12 的區(qū)間而不是直接存儲(chǔ) 1-13 的區(qū)間。

當(dāng)存儲(chǔ)字節(jié)數(shù)組時(shí)，第 1 個(gè)字節(jié)的前 2 位為 00、01 或者 10，其他位則用來記錄字節(jié)數(shù)組的長度：

entry-data

entry-data 存儲(chǔ)的是具體數(shù)據(jù)。當(dāng)存儲(chǔ)小整數(shù)（0-12）時(shí)，因?yàn)?nbsp;encoding 就是數(shù)據(jù)本身，此時(shí) entry-data 部分會(huì)被省略，省略了 entry-data 部分之后的 ziplist 中的 entry 結(jié)構(gòu)如下：

<prevlen> <encoding>

壓縮列表中 entry 的數(shù)據(jù)結(jié)構(gòu)定義如下（源碼 ziplist.c 文件內(nèi)），當(dāng)然實(shí)際存儲(chǔ)并沒有直接使用到這個(gè)結(jié)構(gòu)定義，這個(gè)結(jié)構(gòu)只是用來接收數(shù)據(jù)，所以大家了解一下就可以了：

typedef struct zlentry {
    unsigned int prevrawlensize;//存儲(chǔ)prevrawlen所占用的字節(jié)數(shù)
    unsigned int prevrawlen;//存儲(chǔ)上一個(gè)鏈表節(jié)點(diǎn)需要的字節(jié)數(shù)
    unsigned int lensize;//存儲(chǔ)len所占用的字節(jié)數(shù)
    unsigned int len;//存儲(chǔ)鏈表當(dāng)前節(jié)點(diǎn)的字節(jié)數(shù)
    unsigned int headersize;//當(dāng)前鏈表節(jié)點(diǎn)的頭部大小(prevrawlensize + lensize)即非數(shù)據(jù)域的大小
    unsigned char encoding;//編碼方式
    unsigned char *p;//指向當(dāng)前節(jié)點(diǎn)的起始位置(因?yàn)榱斜韮?nèi)的數(shù)據(jù)也是一個(gè)字符串對(duì)象)
} zlentry;

ziplist 數(shù)據(jù)示例

上面講解了大半天，可能大家都覺得枯燥無味了，也可能會(huì)覺得云里霧里，這個(gè)沒有關(guān)系，這些只要心里有個(gè)概念，用到的時(shí)候再查詢對(duì)應(yīng)資料就可以了，并不需要全部記住，接下來讓我們一起通過兩個(gè)例子來體會(huì)一下 ziplist 到底是如何來組織存儲(chǔ)數(shù)據(jù)的。

下面就是一個(gè)壓縮列表的存儲(chǔ)示例，這個(gè)壓縮列表里面存儲(chǔ)了 2 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)中存儲(chǔ)的是整數(shù) 2 和 5：

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
      |             |          |       |       |     |
   zlbytes        zltail     zllen    "2"     "5"   end

第一組 4 個(gè)字節(jié)為 zlbytes 部分，0f 轉(zhuǎn)成二進(jìn)制就是 1111 也就是 15，代表整個(gè) ziplist 長度是 15 個(gè)字節(jié)。
第二組 4 個(gè)字節(jié) zltail 部分，0c 轉(zhuǎn)成二進(jìn)制就是 1100 也就是 12，這里記錄的是壓縮列表尾節(jié)點(diǎn)距離起始地址有多少個(gè)字節(jié)，也就是就是說 [02 f6] 這個(gè)尾節(jié)點(diǎn)距離起始位置有 12 個(gè)字節(jié)。
第三組 2 個(gè)字節(jié)就是記錄了當(dāng)前 ziplist 中 entry 的數(shù)量，02 轉(zhuǎn)成二進(jìn)制就是 10，也就是說當(dāng)前 ziplist 有 2 個(gè)節(jié)點(diǎn)。
第四組 2 個(gè)字節(jié) [00 f3] 就是第一個(gè) entry，00 表示 0，因?yàn)檫@是第 1 個(gè)節(jié)點(diǎn)，所以前一個(gè)節(jié)點(diǎn)長度為 0，f3 轉(zhuǎn)成二進(jìn)制就是 11110011，剛好對(duì)應(yīng)了表格中的編碼 1111xxxx，所以后面四位就是存儲(chǔ)了一個(gè) 0-12位的整數(shù)。0011 轉(zhuǎn)成十進(jìn)制就是 3，減去 1 得到 2，所以第一個(gè) entry 存儲(chǔ)的數(shù)據(jù)就是 2。
第五組 2 個(gè)字節(jié) [02 f6] 就是第二個(gè) entry，02 即為 2，表示前一個(gè)節(jié)點(diǎn)的長度為 2，注意，因?yàn)檫@里算出來的結(jié)果是小于 254，所以就代表了這里只用到了 1 個(gè)字節(jié)來存儲(chǔ)上一個(gè)節(jié)點(diǎn)的長度（如果等于 254，這說明接下來 4 個(gè)字節(jié)才存儲(chǔ)的是長度），所以后面的 f6 就是當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，轉(zhuǎn)換成二進(jìn)制為 11110110，對(duì)應(yīng)了表格中的編碼 1111xxxx，同樣的后四位 0110 存儲(chǔ)的是真實(shí)數(shù)據(jù)，計(jì)算之后得出是5。
最后一組1個(gè)字節(jié)[ff]轉(zhuǎn)成二進(jìn)制就是 11111111，代表這是整個(gè) ziplist 的結(jié)尾。

假如這時(shí)候又添加了一個(gè) Hello World 字符串到列表中，那么就會(huì)新增一個(gè) entry，如下所示：

[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

第一組的 1 個(gè)字節(jié) 02 轉(zhuǎn)成十進(jìn)制就是 2 ，表示前一個(gè)節(jié)點(diǎn)（即上面示例中的 [02 f6]）長度是 2。
第二組的2 個(gè)字節(jié) 0b 轉(zhuǎn)成二進(jìn)制為 00001011，以 00 開頭，符合編碼 00pppppp，而除掉最開始的兩位 00，計(jì)算之后得到十進(jìn)制 11，這就說明后面字節(jié)數(shù)組的長度是 11。
第三組剛好是 11 個(gè)字節(jié)，對(duì)應(yīng)了上面的長度，所以這里就是真正存儲(chǔ)了 Hello World 的字節(jié)數(shù)組。

ziplist 連鎖更新問題

上面提到 entry 中的 prevlen 屬性可能是 1 個(gè)字節(jié)也可能是 5 個(gè)字節(jié)，那么我們來設(shè)想這么一種場景：假設(shè)一個(gè) ziplist 中，連續(xù)多個(gè) entry 的長度都是一個(gè)接近但是又不到 254 的值（介于 250~253 之間），那么這時(shí)候 ziplist 中每個(gè)節(jié)點(diǎn)都只用了 1 個(gè)字節(jié)來存儲(chǔ)上一個(gè)節(jié)點(diǎn)的長度，假如這時(shí)候添加了一個(gè)新節(jié)點(diǎn)，如 entry1 ，其長度大于 254 個(gè)字節(jié)，此時(shí) entry1 的下一個(gè)節(jié)點(diǎn) entry2 的 prelen 屬性就必須要由 1 個(gè)字節(jié)變?yōu)?nbsp;5 個(gè)字節(jié)，也就是需要執(zhí)行空間重分配，而此時(shí) entry2 因?yàn)樵黾恿?nbsp;4 個(gè)字節(jié)，導(dǎo)致長度又大于 254 個(gè)字節(jié)了，那么它的下一個(gè)節(jié)點(diǎn) entry3 的 prelen 屬性也會(huì)被改變?yōu)?nbsp;5 個(gè)字節(jié)。依此類推，這種產(chǎn)生連續(xù)多次空間重分配的現(xiàn)象就稱之為連鎖更新。同樣的，不僅僅是新增節(jié)點(diǎn)，執(zhí)行刪除節(jié)點(diǎn)操作同樣可能會(huì)發(fā)生連鎖更新現(xiàn)象。

雖然 ziplist 可能會(huì)出現(xiàn)這種連鎖更新的場景，但是一般如果只是發(fā)生在少數(shù)幾個(gè)節(jié)點(diǎn)之間，那么并不會(huì)嚴(yán)重影響性能，而且這種場景發(fā)生的概率也比較低，所以實(shí)際使用時(shí)不用過于擔(dān)心。

總結(jié)

本文主要講解了 Redis 當(dāng)中的 ziplist（壓縮列表），一種用時(shí)間換取空間的數(shù)據(jù)結(jié)構(gòu)，在介紹壓縮列表存儲(chǔ)結(jié)構(gòu)的同時(shí)通過一個(gè)存儲(chǔ)示例來分析了 ziplist 是如何存儲(chǔ)數(shù)據(jù)的，最后介紹了 ziplist 中可能發(fā)生的連鎖更新問題。

犧牲速度來節(jié)省內(nèi)存，Redis是覺得自己太快了嗎？

前言