Redis 源碼簡潔剖析 05 – ziplist 壓縮列表
ziplist 是什麼
壓縮列表，記憶體緊湊的數據結構，佔用一塊連續的記憶體空間。一個 ziplist 可以包含多個節點（entry）， 每個節點可以保存一個長度受限的字元數組（不以 \0 結尾的 char 數組）或者整數， 包括：
-
字元數組
- 長度小於等於
63（2^6-1）位元組的字元數組 - 長度小於等於
16383（12^14-1） 位元組的字元數組 - 長度小於等於
4294967295（2^32-1）位元組的字元數組
- 長度小於等於
-
整數
4位長，介於0至12之間的無符號整數1位元組長，有符號整數3位元組長，有符號整數int16_t類型整數int32_t類型整數int64_t類型整數
Redis 哪些數據結構使用了 ziplist？
- 哈希鍵
- 列表鍵
- 有序集合鍵
ziplist 特點
優點
- 節省記憶體
缺點
- 不能保存過多的元素，否則訪問性能會下降
- 不能保存過大的元素，否則容易導致記憶體重新分配，甚至引起連鎖更新
ziplist 數據結構
啥都不說了，都在注釋里。
// ziplist 中的元素，是 string 或者 integer
typedef struct {
// 如果元素是 string，slen 就表示長度
unsigned char *sval;
unsigned int slen;
// 如果是 integer，sval 是 NULL，lval 就是 integer 的值
long long lval;
} ziplistEntry;
為了方便地取出 ziplist 的各個域以及一些指針地址， ziplist 模組定義了以下宏：
// 取出 zlbytes 的值
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
// 取出 zltail 的值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
// 取出 zllen 的值
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
// 返回 ziplist header 部分的長度，總是固定的 10 位元組
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
// 返回 ziplist end 部分的長度，總是固定的 1 位元組
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
// 返回到達 ziplist 第一個節點（表頭）的地址
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
// 返回到達 ziplist 最後一個節點（表尾）的地址
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// 返回 ziplist 的末端，也即是 zlend 之前的地址
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
ziplist 節點
typedef struct zlentry {
// 前一個節點的長度，通過這個值，可以進行指針計算，從而跳轉到上一個節點
unsigned int prevrawlen;
unsigned int prevrawlensize;
// entry 的編碼方式
// 1. entry 是 string，可能是 1 2 5 個位元組的 header
// 2. entry 是 integer，固定為 1 位元組
unsigned int lensize;
// 實際 entry 的位元組數
// 1. entry 是 string，則表示 string 的長度
// 2. entry 是 integer，則根據數值範圍，可能是 1, 2, 3, 4, 8
unsigned int len;
// prevrawlensize + lensize
unsigned int headersize;
// ZIP_STR_* 或者 ZIP_INT_*
unsigned char encoding;
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
pre_entry_length
記錄前一個節點的長度。通過這個值，可以進行指針計算，從而跳轉到上一個節點。
area |<---- previous entry --->|<--------------- current entry ---------------->|
size 5 bytes 1 byte ? ? ?
+-------------------------+-----------------------------+--------+---------+
component | ... | pre_entry_length | encoding | length | content |
| | | | | |
value | | 0000 0101 | ? | ? | ? |
+-------------------------+-----------------------------+--------+---------+
^ ^
address | |
p = e - 5 e
以上圖為例，從當前節點的指針 e，減去 pre_entry_length 的值（0000 0101 的十進位值，5），就可以得到指向前一個節點的地址 p。
encoding 和 length
encoding 和 length 兩部分一起決定了 content 部分所保存的數據的類型（以及長度）。
其中， encoding 域的長度為兩個 bit ， 它的值可以是 00 、 01 、 10 和 11 ：
00、01和10表示content部分保存著字元數組。11表示content部分保存著整數。
以 00 、 01 和 10 開頭的字元數組的編碼方式如下：
表格中的下劃線 _ 表示留空，而變數 b 、 x 等則代表實際的二進位數據。為了方便閱讀，多個位元組之間用空格隔開。
11 開頭的整數編碼如下：
content
content 部分保存著節點的內容，類型和長度由 encoding 和 length 決定。
以下是一個保存著字元數組 hello world 的節點的例子：
area |<---------------------- entry ----------------------->|
size ? 2 bit 6 bit 11 byte
+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | ? | 00 | 001011 | hello world |
+------------------+----------+--------+---------------+
encoding 域的值 00 表示節點保存著一個長度小於等於 63 位元組的字元數組， length 域給出了這個字元數組的準確長度 —— 11 位元組（的二進位 001011）， content 則保存著字元數組值 hello world 本身（為了方便表示， content 部分使用字元而不是二進位表示）。
以下是另一個節點，它保存著整數 10086 ：
area |<---------------------- entry ----------------------->|
size ? 2 bit 6 bit 2 bytes
+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | ? | 11 | 000000 | 10086 |
+------------------+----------+--------+---------------+
encoding 域的值 11 表示節點保存的是一個整數； 而 length 域的值 000000 表示這個節點的值的類型為 int16_t ； 最後， content 保存著整數值 10086 本身（為了方便表示， content 部分用十進位而不是二進位表示）。
ziplist 基本操作
創建新 ziplist
創建一個新的 ziplist，時間複雜度是 O(1)。
/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
// header 和 end 需要的位元組數
unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
// 分配 bytes 長度的記憶體
unsigned char *zl = zmalloc(bytes);
// 賦值 zlbytes
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
// 賦值 zltail
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
// 賦值 zllen
ZIPLIST_LENGTH(zl) = 0;
// 賦值 zlend
zl[bytes-1] = ZIP_END;
return zl;
}
area |<---- ziplist header ---->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 1 byte
+---------+--------+-------+-----------+
component | zlbytes | zltail | zllen | zlend |
| | | | |
value | 1011 | 1010 | 0 | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
空白 ziplist 的表頭、表尾和末端處於同一地址。
創建了 ziplist 之後， 就可以往裡面添加新節點了， 根據新節點添加位置的不同， 這個工作可以分為兩類來進行：
- 將節點添加到 ziplist 末端：在這種情況下，新節點的後面沒有任何節點。
- 將節點添加到某個/某些節點的前面：在這種情況下，新節點的後面有至少一個節點。
以下兩個小節分別討論這兩種情況。
將節點添加到末端
將新節點添加到 ziplist 的末端需要執行以下三個步驟：
- 記錄到達 ziplist 末端所需的偏移量（因為之後的記憶體重分配可能會改變 ziplist 的地址，因此記錄偏移量而不是保存指針）
- 根據新節點要保存的值，計算出編碼這個值所需的空間大小，以及編碼它前一個節點的長度所需的空間大小，然後對 ziplist 進行記憶體重分配。
- 設置新節點的各項屬性：
pre_entry_length、encoding、length和content。 - 更新 ziplist 的各項屬性，比如記錄空間佔用的
zlbytes，到達表尾節點的偏移量zltail，以及記錄節點數量的zllen。
舉個例子，假設現在要將一個新節點添加到只含有一個節點的 ziplist 上，程式首先要執行步驟 1 ，定位 ziplist 的末端：
area |<---- ziplist header ---->|<--- entries -->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 1 bytes
+---------+--------+-------+----------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | zlend |
| | | | | |
value | 10000 | 1010 | 1 | ? | 1111 1111 |
+---------+--------+-------+----------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
然後執行步驟 2 ，程式需要計算新節點所需的空間：
假設我們要添加到節點裡的值為字元數組 hello world ， 那麼保存這個值共需要 12 位元組的空間：
- 11 位元組用於保存字元數組本身；
- 另外 1 位元組中的 2 bit 用於保存類型編碼
00， 而其餘 6 bit 則保存字元數組長度11的二進位001011。
另外，節點還需要 1 位元組， 用於保存前一個節點的長度 5 （二進位 101 ）。
合算起來，為了添加新節點， ziplist 總共需要多分配 13 位元組空間。 以下是分配完成之後， ziplist 的樣子：
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 10000 | 1010 | 1 | ? | pre_entry_length | 1111 1111 |
| | | | | ? | |
| | | | | | |
| | | | | encoding | |
| | | | | ? | |
| | | | | | |
| | | | | length | |
| | | | | ? | |
| | | | | | |
| | | | | content | |
| | | | | ? | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
步驟三，更新新節點的各項屬性（為了方便表示， content 的內容使用字元而不是二進位來表示）：
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 10000 | 1010 | 1 | ? | pre_entry_length | 1111 1111 |
| | | | | 101 | |
| | | | | | |
| | | | | encoding | |
| | | | | 00 | |
| | | | | | |
| | | | | length | |
| | | | | 001011 | |
| | | | | | |
| | | | | content | |
| | | | | hello world | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
最後一步，更新 ziplist 的 zlbytes 、 zltail 和 zllen 屬性：
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 11101 | 1111 | 10 | ? | pre_entry_length | 1111 1111 |
| | | | | 101 | |
| | | | | | |
| | | | | encoding | |
| | | | | 00 | |
| | | | | | |
| | | | | length | |
| | | | | 001011 | |
| | | | | | |
| | | | | content | |
| | | | | hello world | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^ ^
| | |
address | ZIPLIST_ENTRY_TAIL ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_HEAD
將節點添加到某個/某些節點的前面
比起將新節點添加到 ziplist 的末端， 將一個新節點添加到某個/某些節點的前面要複雜得多， 因為這種操作除了將新節點添加到 ziplist 以外， 還可能引起後續一系列節點的改變。
舉個例子，假設我們要將一個新節點 new 添加到節點 prev 和 next 之間：
add new entry here
|
V
+----------+----------+----------+----------+----------+
| | | | | |
| prev | next | next + 1 | next + 2 | ... |
| | | | | |
+----------+----------+----------+----------+----------+
程式首先為新節點擴大 ziplist 的空間：
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | ??? | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
|<-------->|
expand
space
然後設置 new 節點的各項值 —— 到目前為止，一切都和前面介紹的添加操作一樣：
set value,
property,
length,
etc.
|
v
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | new | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
現在，新的 new 節點取代原來的 prev 節點， 成為了 next 節點的新前驅節點， 不過， 因為這時 next 節點的 pre_entry_length 域編碼的仍然是 prev 節點的長度， 所以程式需要將 new 節點的長度編碼進 next 節點的 pre_entry_length 域里， 這裡會出現三種可能：
next的pre_entry_length域的長度正好能夠編碼new的長度（都是 1 位元組或者都是 5 位元組）next的pre_entry_length只有 1 位元組長，但編碼new的長度需要 5 位元組next的pre_entry_length有 5 位元組長，但編碼new的長度只需要 1 位元組
對於情況 1 和 3 ， 程式直接更新 next 的 pre_entry_length 域。
如果是第二種情況， 那麼程式必須對 ziplist 進行記憶體重分配， 從而擴展 next 的空間。 然而，因為 next 的空間長度改變了， 所以程式又必須檢查 next 的後繼節點 —— next+1 ， 看它的 pre_entry_length 能否編碼 next 的新長度， 如果不能的話，程式又需要繼續對 next+1 進行擴容。
這就是說， 在某個/某些節點的前面添加新節點之後， 程式必須沿著路徑挨個檢查後續的節點，是否滿足新長度的編碼要求， 直到遇到一個能滿足要求的節點（如果有一個能滿足，則這個節點之後的其他節點也滿足）， 或者到達 ziplist 的末端 zlend 為止。
刪除節點
刪除節點和添加操作的步驟類似。
- 定位目標節點，並計算節點的空間長度
target-size：
target start here
|
V
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | target | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
|<-------->|
target-size
- 進行記憶體移位，覆蓋
target原本的數據，然後通過記憶體重分配，收縮多餘空間：
target start here
|
V
+----------+----------+----------+----------+----------+
| | | | | |
| prev | next | next + 1 | next + 2 | ... |
| | | | | |
+----------+----------+----------+----------+----------+
| <------------------------------------------ memmove
- 檢查
next、next+1等後續節點能否滿足新前驅節點的編碼。和添加操作一樣，刪除操作也可能會引起連鎖更新。
參考鏈接
Redis 源碼簡潔剖析系列
Java 編程思想-最全思維導圖-GitHub 下載鏈接，需要的小夥伴可以自取~
原創不易，希望大家轉載時請先聯繫我，並標註原文鏈接。
