構(gòu)成
壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的测蘑， 由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)墨礁。
一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)（entry）， 每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。
圖 7-2 展示了一個(gè)壓縮列表示例：
- 列表 zlbytes 屬性的值為 0x50 （十進(jìn)制 80）， 表示壓縮列表的總長為 80 字節(jié)实昨。
- 列表 zltail 屬性的值為 0x3c （十進(jìn)制 60）， 這表示如果我們有一個(gè)指向壓縮列表起始地址的指針 p 盐固， 那么只要用指針 p 加上偏移量 60 荒给， 就可以計(jì)算出表尾節(jié)點(diǎn) entry3 的地址。
- 列表 zllen 屬性的值為 0x3 （十進(jìn)制 3）刁卜， 表示壓縮列表包含三個(gè)節(jié)點(diǎn)志电。
圖 7-3 展示了另一個(gè)壓縮列表示例：
- 列表 zlbytes 屬性的值為 0xd2 （十進(jìn)制 210）， 表示壓縮列表的總長為 210 字節(jié)蛔趴。
- 列表 zltail 屬性的值為 0xb3 （十進(jìn)制 179）溪北， 這表示如果我們有一個(gè)指向壓縮列表起始地址的指針 p ， 那么只要用指針 p 加上偏移量 179 夺脾， 就可以計(jì)算出表尾節(jié)點(diǎn) entry5 的地址之拨。
- 列表 zllen 屬性的值為 0x5 （十進(jìn)制 5）， 表示壓縮列表包含五個(gè)節(jié)點(diǎn)咧叭。
每個(gè)壓縮列表節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值蚀乔， 其中， 字節(jié)數(shù)組可以是以下三種長度的其中一種：
- 長度小于等于 63 （2^{6}-1）字節(jié)的字節(jié)數(shù)組菲茬；
- 長度小于等于 16383 （2^{14}-1） 字節(jié)的字節(jié)數(shù)組吉挣；
- 長度小于等于 4294967295 （2^{32}-1）字節(jié)的字節(jié)數(shù)組；
而整數(shù)值則可以是以下六種長度的其中一種：
- 4 位長婉弹，介于 0 至 12 之間的無符號(hào)整數(shù)睬魂；
- 1 字節(jié)長的有符號(hào)整數(shù)；
- 3 字節(jié)長的有符號(hào)整數(shù)镀赌；
- int16_t 類型整數(shù)氯哮；
- int32_t 類型整數(shù)；
- int64_t 類型整數(shù)商佛。
每個(gè)壓縮列表節(jié)點(diǎn)都由 previous_entry_length 喉钢、 encoding 、 content 三個(gè)部分組成良姆， 如圖 7-4 所示肠虽。
壓縮列表節(jié)點(diǎn)介紹
節(jié)點(diǎn)的 previous_entry_length 屬性以字節(jié)為單位， 記錄了壓縮列表中前一個(gè)節(jié)點(diǎn)的長度玛追。
previous_entry_length 屬性的長度可以是 1 字節(jié)或者 5 字節(jié)：
- 如果前一節(jié)點(diǎn)的長度小于 254 字節(jié)税课， 那么 previous_entry_length 屬性的長度為 1 字節(jié)： 前一節(jié)點(diǎn)的長度就保存在這一個(gè)字節(jié)里面闲延。
- 如果前一節(jié)點(diǎn)的長度大于等于 254 字節(jié)， 那么 previous_entry_length 屬性的長度為 5 字節(jié)： 其中屬性的第一字節(jié)會(huì)被設(shè)置為 0xFE （十進(jìn)制值 254）韩玩， 而之后的四個(gè)字節(jié)則用于保存前一節(jié)點(diǎn)的長度慨代。
圖 7-5 展示了一個(gè)包含一字節(jié)長 previous_entry_length 屬性的壓縮列表節(jié)點(diǎn)， 屬性的值為 0x05 啸如， 表示前一節(jié)點(diǎn)的長度為 5 字節(jié)。
圖 7-6 展示了一個(gè)包含五字節(jié)長 previous_entry_length 屬性的壓縮節(jié)點(diǎn)氮惯， 屬性的值為 0xFE00002766 叮雳， 其中值的最高位字節(jié) 0xFE 表示這是一個(gè)五字節(jié)長的 previous_entry_length 屬性， 而之后的四字節(jié) 0x00002766 （十進(jìn)制值 10086 ）才是前一節(jié)點(diǎn)的實(shí)際長度妇汗。
因?yàn)楣?jié)點(diǎn)的 previous_entry_length 屬性記錄了前一個(gè)節(jié)點(diǎn)的長度帘不， 所以程序可以通過指針運(yùn)算， 根據(jù)當(dāng)前節(jié)點(diǎn)的起始地址來計(jì)算出前一個(gè)節(jié)點(diǎn)的起始地址杨箭。
舉個(gè)例子寞焙， 如果我們有一個(gè)指向當(dāng)前節(jié)點(diǎn)起始地址的指針 c ， 那么我們只要用指針 c 減去當(dāng)前節(jié)點(diǎn) previous_entry_length 屬性的值互婿， 就可以得出一個(gè)指向前一個(gè)節(jié)點(diǎn)起始地址的指針 p 捣郊， 如圖 7-7 所示。
壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實(shí)現(xiàn)的： 只要我們擁有了一個(gè)指向某個(gè)節(jié)點(diǎn)起始地址的指針慈参， 那么通過這個(gè)指針以及這個(gè)節(jié)點(diǎn)的 previous_entry_length 屬性呛牲， 程序就可以一直向前一個(gè)節(jié)點(diǎn)回溯， 最終到達(dá)壓縮列表的表頭節(jié)點(diǎn)驮配。
圖 7-8 展示了一個(gè)從表尾節(jié)點(diǎn)向表頭節(jié)點(diǎn)進(jìn)行遍歷的完整過程：
- 首先娘扩，我們擁有指向壓縮列表表尾節(jié)點(diǎn) entry4 起始地址的指針 p1 （指向表尾節(jié)點(diǎn)的指針可以通過指向壓縮列表起始地址的指針加上 zltail 屬性的值得出）；
- 通過用 p1 減去 entry4 節(jié)點(diǎn) previous_entry_length 屬性的值壮锻， 我們得到一個(gè)指向 entry4 前一節(jié)點(diǎn) entry3 起始地址的指針 p2 琐旁；
- 通過用 p2 減去 entry3 節(jié)點(diǎn) previous_entry_length 屬性的值， 我們得到一個(gè)指向 entry3 前一節(jié)點(diǎn) entry2 起始地址的指針 p3 猜绣；
- 通過用 p3 減去 entry2 節(jié)點(diǎn) previous_entry_length 屬性的值灰殴， 我們得到一個(gè)指向 entry2 前一節(jié)點(diǎn) entry1 起始地址的指針 p4 ， entry1 為壓縮列表的表頭節(jié)點(diǎn)掰邢；
- 最終验懊， 我們從表尾節(jié)點(diǎn)向表頭節(jié)點(diǎn)遍歷了整個(gè)列表。
encoding
節(jié)點(diǎn)的 encoding 屬性記錄了節(jié)點(diǎn)的 content 屬性所保存數(shù)據(jù)的類型以及長度：
- 一字節(jié)尸变、兩字節(jié)或者五字節(jié)長义图， 值的最高位為 00 、 01 或者 10 的是字節(jié)數(shù)組編碼： 這種編碼表示節(jié)點(diǎn)的 content 屬性保存著字節(jié)數(shù)組召烂， 數(shù)組的長度由編碼除去最高兩位之后的其他位記錄碱工；
- 一字節(jié)長， 值的最高位以 11 開頭的是整數(shù)編碼： 這種編碼表示節(jié)點(diǎn)的 content 屬性保存著整數(shù)值， 整數(shù)值的類型和長度由編碼除去最高兩位之后的其他位記錄怕篷；
表 7-2 記錄了所有可用的字節(jié)數(shù)組編碼历筝， 而表 7-3 則記錄了所有可用的整數(shù)編碼。 表格中的下劃線 _ 表示留空廊谓， 而 b 梳猪、 x 等變量則代表實(shí)際的二進(jìn)制數(shù)據(jù)， 為了方便閱讀蒸痹， 多個(gè)字節(jié)之間用空格隔開春弥。
content
節(jié)點(diǎn)的 content 屬性負(fù)責(zé)保存節(jié)點(diǎn)的值， 節(jié)點(diǎn)值可以是一個(gè)字節(jié)數(shù)組或者整數(shù)叠荠， 值的類型和長度由節(jié)點(diǎn)的 encoding 屬性決定匿沛。
圖 7-9 展示了一個(gè)保存字節(jié)數(shù)組的節(jié)點(diǎn)示例：
- 編碼的最高兩位 00 表示節(jié)點(diǎn)保存的是一個(gè)字節(jié)數(shù)組；
- 編碼的后六位 001011 記錄了字節(jié)數(shù)組的長度 11 榛鼎；
-
content 屬性保存著節(jié)點(diǎn)的值 "hello world" 逃呼。
圖 7-10 展示了一個(gè)保存整數(shù)值的節(jié)點(diǎn)示例：
- 編碼 11000000 表示節(jié)點(diǎn)保存的是一個(gè) int16_t 類型的整數(shù)值；
-
content 屬性保存著節(jié)點(diǎn)的值 10086 者娱。
image.png
連鎖更新
前面說過抡笼， 每個(gè)節(jié)點(diǎn)的 previous_entry_length 屬性都記錄了前一個(gè)節(jié)點(diǎn)的長度：
- 如果前一節(jié)點(diǎn)的長度小于 254 字節(jié)， 那么 previous_entry_length 屬性需要用 1 字節(jié)長的空間來保存這個(gè)長度值黄鳍。
- 如果前一節(jié)點(diǎn)的長度大于等于 254 字節(jié)蔫缸， 那么 previous_entry_length 屬性需要用 5 字節(jié)長的空間來保存這個(gè)長度值。
現(xiàn)在际起， 考慮這樣一種情況： 在一個(gè)壓縮列表中拾碌， 有多個(gè)連續(xù)的、長度介于 250 字節(jié)到 253 字節(jié)之間的節(jié)點(diǎn) e1 至 eN 街望， 如圖 7-11 所示校翔。
因?yàn)?e1 至 eN 的所有節(jié)點(diǎn)的長度都小于 254 字節(jié)， 所以記錄這些節(jié)點(diǎn)的長度只需要 1 字節(jié)長的 previous_entry_length 屬性灾前， 換句話說防症， e1 至 eN 的所有節(jié)點(diǎn)的 previous_entry_length 屬性都是 1 字節(jié)長的。
這時(shí)哎甲， 如果我們將一個(gè)長度大于等于 254 字節(jié)的新節(jié)點(diǎn) new 設(shè)置為壓縮列表的表頭節(jié)點(diǎn)蔫敲， 那么 new 將成為 e1 的前置節(jié)點(diǎn)， 如圖 7-12 所示炭玫。
因?yàn)?e1 的 previous_entry_length 屬性僅長 1 字節(jié)奈嘿， 它沒辦法保存新節(jié)點(diǎn) new 的長度， 所以程序?qū)?duì)壓縮列表執(zhí)行空間重分配操作吞加， 并將 e1 節(jié)點(diǎn)的 previous_entry_length 屬性從原來的 1 字節(jié)長擴(kuò)展為 5 字節(jié)長裙犹。
現(xiàn)在尽狠， 麻煩的事情來了 —— e1 原本的長度介于 250 字節(jié)至 253 字節(jié)之間， 在為 previous_entry_length 屬性新增四個(gè)字節(jié)的空間之后叶圃， e1 的長度就變成了介于 254 字節(jié)至 257 字節(jié)之間袄膏， 而這種長度使用 1 字節(jié)長的 previous_entry_length 屬性是沒辦法保存的。
因此掺冠， 為了讓 e2 的 previous_entry_length 屬性可以記錄下 e1 的長度沉馆， 程序需要再次對(duì)壓縮列表執(zhí)行空間重分配操作， 并將 e2 節(jié)點(diǎn)的 previous_entry_length 屬性從原來的 1 字節(jié)長擴(kuò)展為 5 字節(jié)長德崭。
正如擴(kuò)展 e1 引發(fā)了對(duì) e2 的擴(kuò)展一樣斥黑， 擴(kuò)展 e2 也會(huì)引發(fā)對(duì) e3 的擴(kuò)展， 而擴(kuò)展 e3 又會(huì)引發(fā)對(duì) e4 的擴(kuò)展……為了讓每個(gè)節(jié)點(diǎn)的 previous_entry_length 屬性都符合壓縮列表對(duì)節(jié)點(diǎn)的要求接癌， 程序需要不斷地對(duì)壓縮列表執(zhí)行空間重分配操作， 直到 eN 為止扣讼。
Redis 將這種在特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作稱之為“連鎖更新”（cascade update）缺猛， 圖 7-13 展示了這一過程。
除了添加新節(jié)點(diǎn)可能會(huì)引發(fā)連鎖更新之外椭符， 刪除節(jié)點(diǎn)也可能會(huì)引發(fā)連鎖更新荔燎。
考慮圖 7-14 所示的壓縮列表， 如果 e1 至 eN 都是大小介于 250 字節(jié)至 253 字節(jié)的節(jié)點(diǎn)销钝， big 節(jié)點(diǎn)的長度大于等于 254 字節(jié)（需要 5 字節(jié)的 previous_entry_length 來保存）有咨， 而 small 節(jié)點(diǎn)的長度小于 254 字節(jié)（只需要 1 字節(jié)的 previous_entry_length 來保存）， 那么當(dāng)我們將 small 節(jié)點(diǎn)從壓縮列表中刪除之后蒸健， 為了讓 e1 的 previous_entry_length 屬性可以記錄 big 節(jié)點(diǎn)的長度座享， 程序?qū)U(kuò)展 e1 的空間， 并由此引發(fā)之后的連鎖更新似忧。
因?yàn)檫B鎖更新在最壞情況下需要對(duì)壓縮列表執(zhí)行 N 次空間重分配操作渣叛， 而每次空間重分配的最壞復(fù)雜度為 O(N) ， 所以連鎖更新的最壞復(fù)雜度為 O(N^2) 盯捌。
要注意的是淳衙， 盡管連鎖更新的復(fù)雜度較高， 但它真正造成性能問題的幾率是很低的：
- 首先饺著， 壓縮列表里要恰好有多個(gè)連續(xù)的箫攀、長度介于 250 字節(jié)至 253 字節(jié)之間的節(jié)點(diǎn)， 連鎖更新才有可能被引發(fā)幼衰， 在實(shí)際中靴跛， 這種情況并不多見；
- 其次渡嚣， 即使出現(xiàn)連鎖更新汤求， 但只要被更新的節(jié)點(diǎn)數(shù)量不多俏险， 就不會(huì)對(duì)性能造成任何影響： 比如說， 對(duì)三五個(gè)節(jié)點(diǎn)進(jìn)行連鎖更新是絕對(duì)不會(huì)影響性能的扬绪；
因?yàn)橐陨显颍?ziplistPush 等命令的平均復(fù)雜度僅為 O(N) 竖独， 在實(shí)際中， 我們可以放心地使用這些函數(shù)挤牛， 而不必?fù)?dān)心連鎖更新會(huì)影響壓縮列表的性能莹痢。
重點(diǎn)回顧
- 壓縮列表是一種為節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)。
- 壓縮列表被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一墓赴。
- 壓縮列表可以包含多個(gè)節(jié)點(diǎn)竞膳，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者整數(shù)值。
- 添加新節(jié)點(diǎn)到壓縮列表诫硕， 或者從壓縮列表中刪除節(jié)點(diǎn)坦辟， 可能會(huì)引發(fā)連鎖更新操作， 但這種操作出現(xiàn)的幾率并不高章办。
