壓縮列表（ziplist）是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且每個(gè)列表項(xiàng)要么就是小整數(shù)值，要么就是長度比較短的字符串，那么 Redis 就會(huì)使用壓縮列表來做列表鍵的底層實(shí)現(xiàn)。
原文是這么說的，但是這本書是基于 Redis 2.9 來寫的，而我用的是 Redis 6.2，發(fā)現(xiàn)上面說到的情況并不是使用了 ziplist，而是使用了 quicklist. 當(dāng)然，這并不影響我們了解 ziplist.
127.0.0.1:6379> rpush numlst 1 3 5 "haha"
(integer) 4
127.0.0.1:6379> object encoding numlst
"quicklist"
The struct of ziplist
壓縮列表是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)（entry），每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
|---|
| 屬性 | 類型 | 長度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字節(jié) | 記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù) |
| zltail | uint32_t | 4 字節(jié) | 記錄壓縮列表表尾節(jié)點(diǎn)舉例壓縮列表的起始地址有多少字節(jié) |
| zllen | uint16_t | 2 字節(jié) | 記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量。當(dāng) zllen 的值等于 UINT16_MAX 時(shí)，節(jié)點(diǎn)的真實(shí)數(shù)量需要遍歷整個(gè)壓縮列表才能計(jì)算得出 |
| entryX | 列表節(jié)點(diǎn) | 不定 | 壓縮列表包含的各個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的長度由節(jié)點(diǎn)保存的內(nèi)容決定 |
| zlend | uint8_t | 1 字節(jié) | 特殊值 0xFF，用于標(biāo)記壓縮列表的末端 |
The struct of ziplist node
前面說到，每個(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ù)值則可以是以下 6 種長度之一：
- 4 位長，介于 0 至 12 之間的無符號(hào)整數(shù)；（為啥不是 15 ？）
- 1 字節(jié)長的有符號(hào)整數(shù)；（也就是 int8_t）
- 3 字節(jié)長的有符號(hào)整數(shù)；
- int16_t 類型整數(shù)；
- int32_t 類型整數(shù)；
- int64_t 類型整數(shù)；
typedef struct zlentry {
void* previous_entry_length;
void* encoding;
void* content;
} zlentry;
-
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)的長度 >= 254 字節(jié)，那么previous_entry_length屬性的長度為 5 字節(jié)：其中屬性的第一個(gè)字節(jié)會(huì)被設(shè)置為 0xFE，而之后的 4 個(gè)字節(jié)則用于保存前一節(jié)點(diǎn)的長度。
因?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)的起始位置。壓縮列表的從表尾向表頭遍歷就是使用這一原理實(shí)現(xiàn)的。
連鎖更新
發(fā)生連鎖更新的條件：在一個(gè)壓縮列表中，有多個(gè)連續(xù)的、長度介于 250 字節(jié)到 253 字節(jié)之間的節(jié)點(diǎn) e1 至 eN，如果我們將一個(gè)長度 >= 254 字節(jié)的新節(jié)點(diǎn) new 設(shè)置為壓縮列表的表頭節(jié)點(diǎn)，那么從 e1 節(jié)點(diǎn)開始，每個(gè)節(jié)點(diǎn)的 previous_entry_length 都需要被擴(kuò)展成為 5 字節(jié)，這就是連鎖更新。
除了添加新節(jié)點(diǎn)可能會(huì)引發(fā)連鎖更新之外，刪除節(jié)點(diǎn)也可能會(huì)引發(fā)連鎖更新。
因?yàn)檫B鎖更新在最壞情況下需要對壓縮列表執(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ì)對性能造成任何影響。
