| 屬性 | 類型 | 長 度 | 說明 |
|---|---|---|---|
| zlbytes | uint32_t | 4字節(jié) | 記錄壓縮列表占用內(nèi)存字節(jié)數(shù)（包括本身所占用的 4 個字節(jié)）。 |
| zltail | uint32_t | 4字節(jié) | 記錄壓縮列表尾節(jié)點距離壓縮列表的起始地址有多少個字節(jié)（通過這個值可以計算出尾節(jié)點的地址） |
| zllen | uint16_t | 2字節(jié) | 記錄壓縮列表中包含的節(jié)點數(shù)量，當列表值超過可以存儲的最大值（65535）時，此值固定存儲 65535（即 2 的 16 次方 減 1），因此此時需要遍歷整個壓縮列表才能計算出真實節(jié)點數(shù)。 |
| entry | 節(jié)點 | - | 壓縮列表中的各個節(jié)點，長度由存儲的實際數(shù)據(jù)決定。 |
| zlend | uint8_t | 1字節(jié) | 特殊字符 0xFF（即十進制 255），用來標記壓縮列表的末端（其他正常的節(jié)點沒有被標記為 255 的，因為 255 用來標識末尾，后面可以看到，正常節(jié)點都是標記為 254）。 |
ziplist 的 head 和 end 存的都是長度和標記，而 entry 存儲的是具體元素，這又是經(jīng)過特殊的設(shè)計的一種存儲格式，每個 entry 都以包含兩段信息的元數(shù)據(jù)作為前綴，每一個 entry 的組成結(jié)構(gòu)為：
prevlen> encoding> entry-data>
prevlen 屬性存儲了前一個 entry 的長度，通過此屬性能夠從后到前遍歷列表。 prevlen 屬性的長度可能是 1 字節(jié)也可能是 5 字節(jié)：
當鏈表的前一個 entry 占用字節(jié)數(shù)小于 254，此時 prevlen 只用 1 個字節(jié)進行表示。
prevlen from 0 to 253> encoding> entry>
當鏈表的前一個 entry 占用字節(jié)數(shù)大于等于 254，此時 prevlen 用 5 個字節(jié)來表示，其中第 1 個字節(jié)的值固定是 254（相當于是一個標記，代表后面跟了一個更大的值），后面 4 個字節(jié)才是真正存儲前一個 entry 的占用字節(jié)數(shù)。
0xFE 4 bytes unsigned little endian prevlen> encoding> entry>
注意：1 個字節(jié)完全你能存儲 255 的大小，之所以只取到 254 是因為 zlend 就是固定的 255，所以 255 這個數(shù)要用來判斷是否是 ziplist 的結(jié)尾。
encoding 屬性存儲了當前 entry 所保存數(shù)據(jù)的類型以及長度。encoding 長度為 1 字節(jié)，2 字節(jié)或者 5 字節(jié)長。前面我們提到，每一個 entry 中可以保存字節(jié)數(shù)組和整數(shù)，而 encoding 屬性的第 1 個字節(jié)就是用來確定當前 entry 存儲的是整數(shù)還是字節(jié)數(shù)組。當存儲整數(shù)時，第 1 個字節(jié)的前兩位總是 11，而存儲字節(jié)數(shù)組時，則可能是 00、01 和 10 三種中的一種。
當存儲整數(shù)時，第 1 個字節(jié)的前 2 位固定為 11，其他位則用來記錄整數(shù)值的類型或者整數(shù)值（下表所示的編碼中前兩位均為 11）：
| 編碼 | 長度 | entry保存的數(shù)據(jù) |
|---|---|---|
| 11000000 | 1字節(jié) | int16_t類型整數(shù) |
| 11010000 | 1字節(jié) | int32_t類型整數(shù) |
| 11100000 | 1字節(jié) | int64_t類型整數(shù) |
| 11110000 | 1字節(jié) | 24位有符號整數(shù) |
| 11111110 | 1字節(jié) | 8位有符號整數(shù) |
| 1111xxxx | 1字節(jié) | xxxx 代表區(qū)間 0001-1101，存儲了一個介于 0-12 之間的整數(shù)，此時 entry-data 屬性被省略 |
注意：xxxx 四位編碼范圍是 0000-1111，但是 0000，1111 和 1110 已經(jīng)被表格中前面表示的數(shù)據(jù)類型占用了，所以實際上的范圍是 0001-1101，此時能保存數(shù)據(jù) 1-13，再減去 1 之后范圍就是 0-12。至于為什么要減去 1 是從使用習(xí)慣來說 0 是一個非常常用的數(shù)據(jù)，所以才會選擇統(tǒng)一減去 1 來存儲一個 0-12 的區(qū)間而不是直接存儲 1-13 的區(qū)間。
當存儲字節(jié)數(shù)組時，第 1 個字節(jié)的前 2 位為 00、01 或者 10，其他位則用來記錄字節(jié)數(shù)組的長度：
| 編碼 | 長度 | entry保存的數(shù)據(jù) |
|---|---|---|
| 00pppppp | 1字節(jié) | 長度小于等于 63 字節(jié)（6 位）的字節(jié)數(shù)組 |
| 01pppppp qqqqqqqq | 2字節(jié) | 長度小于等于 16383 字節(jié)（14 位）的字節(jié)數(shù)組 |
| 10000000 qqqqqqqq rrrrrrrr ssssssss tttttttt | 5字節(jié) | 長度小于等于 2 的 32 次方減 1 （32 位）的字節(jié)數(shù)組，其中第 1 個字節(jié)的后 6 位設(shè)置為 0，暫時沒有用到，后面的 32 位（4 個字節(jié)）存儲了數(shù)據(jù) |
entry-data 存儲的是具體數(shù)據(jù)。當存儲小整數(shù)（0-12）時，因為 encoding 就是數(shù)據(jù)本身，此時 entry-data 部分會被省略，省略了 entry-data 部分之后的 ziplist 中的 entry 結(jié)構(gòu)如下：
prevlen> encoding>
壓縮列表中 entry 的數(shù)據(jù)結(jié)構(gòu)定義如下（源碼 ziplist.c 文件內(nèi)），當然實際存儲并沒有直接使用到這個結(jié)構(gòu)定義，這個結(jié)構(gòu)只是用來接收數(shù)據(jù)，所以大家了解一下就可以了：
typedef struct zlentry {
unsigned int prevrawlensize;//存儲prevrawlen所占用的字節(jié)數(shù)
unsigned int prevrawlen;//存儲上一個鏈表節(jié)點需要的字節(jié)數(shù)
unsigned int lensize;//存儲len所占用的字節(jié)數(shù)
unsigned int len;//存儲鏈表當前節(jié)點的字節(jié)數(shù)
unsigned int headersize;//當前鏈表節(jié)點的頭部大小(prevrawlensize + lensize)即非數(shù)據(jù)域的大小
unsigned char encoding;//編碼方式
unsigned char *p;//指向當前節(jié)點的起始位置(因為列表內(nèi)的數(shù)據(jù)也是一個字符串對象)
} zlentry;
上面講解了大半天，可能大家都覺得枯燥無味了，也可能會覺得云里霧里，這個沒有關(guān)系，這些只要心里有個概念，用到的時候再查詢對應(yīng)資料就可以了，并不需要全部記住，接下來讓我們一起通過兩個例子來體會一下 ziplist 到底是如何來組織存儲數(shù)據(jù)的。
下面就是一個壓縮列表的存儲示例，這個壓縮列表里面存儲了 2 個節(jié)點，節(jié)點中存儲的是整數(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 個字節(jié)為 zlbytes 部分，0f 轉(zhuǎn)成二進制就是 1111 也就是 15，代表整個 ziplist 長度是 15 個字節(jié)。第二組 4 個字節(jié) zltail 部分，0c 轉(zhuǎn)成二進制就是 1100 也就是 12，這里記錄的是壓縮列表尾節(jié)點距離起始地址有多少個字節(jié)，也就是就是說 [02 f6] 這個尾節(jié)點距離起始位置有 12 個字節(jié)。第三組 2 個字節(jié)就是記錄了當前 ziplist 中 entry 的數(shù)量，02 轉(zhuǎn)成二進制就是 10，也就是說當前 ziplist 有 2 個節(jié)點。第四組 2 個字節(jié) [00 f3] 就是第一個 entry，00 表示 0，因為這是第 1 個節(jié)點，所以前一個節(jié)點長度為 0，f3 轉(zhuǎn)成二進制就是 11110011，剛好對應(yīng)了表格中的編碼 1111xxxx，所以后面四位就是存儲了一個 0-12位的整數(shù)。0011 轉(zhuǎn)成十進制就是 3，減去 1 得到 2，所以第一個 entry 存儲的數(shù)據(jù)就是 2。第五組 2 個字節(jié) [02 f6] 就是第二個 entry，02 即為 2，表示前一個節(jié)點的長度為 2，注意，因為這里算出來的結(jié)果是小于 254，所以就代表了這里只用到了 1 個字節(jié)來存儲上一個節(jié)點的長度（如果等于 254，這說明接下來 4 個字節(jié)才存儲的是長度），所以后面的 f6 就是當前節(jié)點的數(shù)據(jù)，轉(zhuǎn)換成二進制為 11110110，對應(yīng)了表格中的編碼 1111xxxx，同樣的后四位 0110 存儲的是真實數(shù)據(jù)，計算之后得出是5。最后一組1個字節(jié)[ff]轉(zhuǎn)成二進制就是 11111111，代表這是整個 ziplist 的結(jié)尾。
假如這時候又添加了一個 Hello World 字符串到列表中，那么就會新增一個 entry，如下所示：
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
第一組的 1 個字節(jié) 02 轉(zhuǎn)成十進制就是 2 ，表示前一個節(jié)點（即上面示例中的 [02 f6]）長度是 2。第 二組的2 個字節(jié) 0b 轉(zhuǎn)成二進制為 00001011，以 00 開頭，符合編碼 00pppppp，而除掉最開始的兩位 00，計算之后得到十進制 11，這就說明后面字節(jié)數(shù)組的長度是 11。第三組剛好是 11 個字節(jié)，對應(yīng)了上面的長度，所以這里就是真正存儲了 Hello World 的字節(jié)數(shù)組。
上面提到 entry 中的 prevlen 屬性可能是 1 個字節(jié)也可能是 5 個字節(jié)，那么我們來設(shè)想這么一種場景：假設(shè)一個 ziplist 中，連續(xù)多個 entry 的長度都是一個接近但是又不到 254 的值（介于 250~253 之間），那么這時候 ziplist 中每個節(jié)點都只用了 1 個字節(jié)來存儲上一個節(jié)點的長度，假如這時候添加了一個新節(jié)點，如 entry1 ，其長度大于 254 個字節(jié)，此時 entry1 的下一個節(jié)點 entry2 的 prelen 屬性就必須要由 1 個字節(jié)變?yōu)?5 個字節(jié)，也就是需要執(zhí)行空間重分配，而此時 entry2 因為增加了 4 個字節(jié)，導(dǎo)致長度又大于 254 個字節(jié)了，那么它的下一個節(jié)點 entry3 的 prelen 屬性也會被改變?yōu)?5 個字節(jié)。依此類推，這種產(chǎn)生連續(xù)多次空間重分配的現(xiàn)象就稱之為連鎖更新。同樣的，不僅僅是新增節(jié)點，執(zhí)行刪除節(jié)點操作同樣可能會發(fā)生連鎖更新現(xiàn)象。
雖然 ziplist 可能會出現(xiàn)這種連鎖更新的場景，但是一般如果只是發(fā)生在少數(shù)幾個節(jié)點之間，那么并不會嚴重影響性能，而且這種場景發(fā)生的概率也比較低，所以實際使用時不用過于擔(dān)心。
本文主要講解了 Redis 當中的 ziplist（壓縮列表），一種用時間換取空間的數(shù)據(jù)結(jié)構(gòu)，在介紹壓縮列表存儲結(jié)構(gòu)的同時通過一個存儲示例來分析了 ziplist 是如何存儲數(shù)據(jù)的，最后介紹了 ziplist 中可能發(fā)生的連鎖更新問題。
到此這篇關(guān)于壓縮列表犧牲速度來節(jié)省內(nèi)存，Redis是膨脹了嗎的文章就介紹到這了,更多相關(guān)Redis壓縮列表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
上一篇：Redis憑啥可以這么快