一 前言

List 列表是簡(jiǎn)單的字符串列表，按照插入順序排序，可以從頭部或尾部向 List 列表添加元素。最大長度為 2^32 - 1，也即每個(gè)列表支持超過 40 億個(gè)元素。

Redis 的 List 類型有多種實(shí)現(xiàn)方式，由雙向鏈表或壓縮列表（v7.0 由 listpack 替代）實(shí)現(xiàn)的。這篇文章就是介紹其中一種實(shí)現(xiàn) ziplist - 壓縮列表。

ziplist 被設(shè)計(jì)成一種內(nèi)存緊湊型的數(shù)據(jù)結(jié)構(gòu)，占用一塊連續(xù)的內(nèi)存空間，不僅可以利用 CPU 緩存，而且會(huì)針對(duì)不同長度的數(shù)據(jù)，進(jìn)行相應(yīng)編碼，這種方法可以有效地節(jié)省內(nèi)存開銷。

二 源碼解讀

一如既往，關(guān)于 ziplist 的定義和實(shí)現(xiàn)還是放在一對(duì)文件中，分別是 ziplist.h 和 ziplist.c。在 ziplist.c 文件的頭部有著這么一段注釋介紹什么是 ziplist。

ziplist 是一個(gè)經(jīng)過特殊編碼的雙向鏈表，旨在提高內(nèi)存效率。 它存儲(chǔ)字符串和整數(shù)值，其中整數(shù)被編碼為實(shí)際整數(shù)而不是一系列字符。 它允許在 O(1) 時(shí)間內(nèi)在列表的任一側(cè)進(jìn)行推送和彈出操作。 但是，由于每個(gè)操作都需要重新分配 ziplist 使用的內(nèi)存，因此實(shí)際復(fù)雜性與 ziplist 使用的內(nèi)存量有關(guān)。

從這段話得到：對(duì)于不同的數(shù)據(jù)類型有著不同的編碼方式，理解為會(huì)對(duì)數(shù)據(jù)進(jìn)行壓縮，從而達(dá)到減少內(nèi)存使用的目的。但是隨著存儲(chǔ)的 value 數(shù)據(jù)級(jí)增加，使用 ziplist 所付出的代價(jià)也隨之增加。

2.1 ziplist 布局

ziplist 是一個(gè)特殊雙向鏈表，不像普通的鏈表使用前后指針關(guān)聯(lián)在一起，它是存儲(chǔ)在連續(xù)內(nèi)存上的。

/* 創(chuàng)建一個(gè)空的 ziplist. */
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

整體的結(jié)構(gòu)布局如下圖：

• zlbytes: 32 位無符號(hào)整型，記錄 ziplist 整個(gè)結(jié)構(gòu)體的占用空間大小。當(dāng)然了也包括 zlbytes 本身。這個(gè)結(jié)構(gòu)有個(gè)很大的用處，就是當(dāng)需要修改 ziplist 時(shí)候不需要遍歷即可知道其本身的大小。 這個(gè) SDS 中記錄字符串的長度有相似之處，這些好的設(shè)計(jì)往往在平時(shí)的開發(fā)中可以采納一下。
• zltail: 32 位無符號(hào)整型, 記錄整個(gè) ziplist 中最后一個(gè) entry 的偏移量。所以在尾部進(jìn)行 POP 操作時(shí)候不需要先遍歷一次。
• zllen: 16 位無符號(hào)整型, 記錄 entry 的數(shù)量， 所以只能表示 2^16。但是 Redis 作了特殊的處理：當(dāng)實(shí)體數(shù)超過 2^16 ,該值被固定為 2^16 - 1。 所以這種時(shí)候要知道所有實(shí)體的數(shù)量就必須要遍歷整個(gè)結(jié)構(gòu)了。
• entry: 真正存數(shù)據(jù)的結(jié)構(gòu)。
• zlend: 8 位無符號(hào)整型, 固定為 255 (0xFF)。為 ziplist 的結(jié)束標(biāo)識(shí)。

2.2 entry 節(jié)點(diǎn)

每個(gè) entry 都包含兩條信息的元數(shù)據(jù)為前綴：
第一元數(shù)據(jù)用來存儲(chǔ)前一個(gè) entry 的長度，以便能夠從后向前遍歷列表。
第二元數(shù)據(jù)是表示 entry 的編碼形式。 用來表示 entry 類型，整數(shù)或字符串，在字符串的情況下，它還表示字符串有效的長度。

typedef struct zlentry {
    unsigned int prevrawlensize; /* 用于編碼前一個(gè)節(jié)點(diǎn)字節(jié)長度*/
    unsigned int prevrawlen;     
    unsigned int lensize;        /* 用于編碼此節(jié)點(diǎn)類型/長度的字節(jié)。
    								例如，字符串有1、2或5個(gè)字節(jié)標(biāo)題。
    								整數(shù)總是使用一個(gè)字節(jié)。
    							*/
    unsigned int len;            /* 用于表示節(jié)點(diǎn)實(shí)際的字節(jié)。
									對(duì)于字符串，這只是字符串長度
									而對(duì)于整數(shù)，它是1、2、3、4、8或
									0,具體取決于數(shù)字范圍。 
								*/
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* 設(shè)置為ZIP_STR_*或ZIP_INT_*，具體取決于節(jié)點(diǎn)編碼。*/
    unsigned char *p;            /* 第一個(gè)節(jié)點(diǎn)的地址指針，prev-entry-len */
} zlentry;

所以一個(gè)完整的 ziplist 是這樣存儲(chǔ)的：

2.2.1 prelen

• 記錄前一個(gè) entry 的長度。若前一個(gè) entry 的長度小于 254 , 則使用 1 個(gè)字節(jié)的 8 位無符號(hào)整數(shù)來表示。
• 若前一個(gè) entry 長度大于等于 254，則使用 5 個(gè)字節(jié)來表示。第 1 個(gè)字節(jié)固定為 254 (FE) 作為標(biāo)識(shí)，剩余 4 字節(jié)則用來表示前一個(gè) entry 的實(shí)際大小。

1. 前一個(gè) entry 大小不超過 253。

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

2. 前一個(gè) entry 大小超過 253。

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

2.2.2 encoding 編碼

entry 的編碼字段取決于具體值的內(nèi)容，分為字符串、數(shù)字兩種類型單獨(dú)處理。

1. 當(dāng) entry 是字符串時(shí)，有 3 種編碼方式。編碼第 1 個(gè)字節(jié)的前 2 位將保存用于存儲(chǔ)字符串長度的編碼類型，后面是字符串的實(shí)際長度。

1. 長度小于或等于 63 字節(jié)（6 位）的字符串值。 “pppppp”表示無符號(hào)的 6 位數(shù)據(jù)長度。
|00pppppp| - 1 byte
2. 長度小于或等于 16383 字節(jié)（14 位）的字符串值。14 位的數(shù)據(jù)采用  big endian 存儲(chǔ)。
big endian 是一種字節(jié)序方式，有Little-Endian、Big-Endian兩種。
|01pppppp|qqqqqqqq| - 2 bytes
3. 長度大于或等于 16384 字節(jié)的字符串值。
采用 big endian 存儲(chǔ)且可表示的字符串長度最大2^32-1，所以第一個(gè)字節(jié)沒有用到，所以低6位沒有用，所以都是0。
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes 

2. 當(dāng) entry 是整數(shù)時(shí)，有 6 種編碼方式。前 2 位都固定為 1，接下來的 2 位用于指定將在此標(biāo)頭后存儲(chǔ)哪種類型的整數(shù)。

與 ziplist 標(biāo)頭一樣，所有整數(shù)都以 Little-Endian 序表示，即使此代碼是在 Big-Endian 系統(tǒng)中編譯的。

1. 整數(shù)編碼為 int16_t（2 字節(jié)）。
|11000000| - 3 bytes
2. 整數(shù)編碼為int32_t（4個(gè)字節(jié)）。
|11010000| - 5 bytes
3. 整數(shù)編碼為 int64_t（8 字節(jié)）。
|11100000| - 9 bytes
4. 整數(shù)編碼為24位帶符號(hào)（3個(gè)字節(jié)）。
|11110000| - 4 bytes
5. 整數(shù)編碼為 8 位有符號(hào)（1 字節(jié)）。
|11111110| - 2 bytes
6. 0到12的無符號(hào)整數(shù)。編碼后的值實(shí)際上是1到13，因?yàn)?000和1111不能用，所以要從編碼后的4位值中減去1才能得到正確的值。
|1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer

3. 結(jié)尾編碼標(biāo)識(shí)

1. 表示 ziplist 結(jié)尾的標(biāo)識(shí)。
|11111111|

三 連鎖更新

連鎖更新是 ziplist 一個(gè)比較大的缺點(diǎn)，這也是在 v7.0 被 listpack 所替代的一個(gè)重要原因。

ziplist 在更新或者新增時(shí)候，如空間不夠則需要對(duì)整個(gè)列表進(jìn)行重新分配。當(dāng)新插入的元素較大時(shí)，可能會(huì)導(dǎo)致后續(xù)元素的 prevlen 占用空間都發(fā)生變化，從而引起「連鎖更新」問題，導(dǎo)致每個(gè)元素的空間都要重新分配，造成訪問壓縮列表性能的下降。

ziplist 節(jié)點(diǎn)的 prevlen 屬性會(huì)根據(jù)前一個(gè)節(jié)點(diǎn)的長度進(jìn)行不同的空間大小分配：

• 如果前一個(gè)節(jié)點(diǎn)的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個(gè)長度值。
• 如果前一個(gè)節(jié)點(diǎn)的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個(gè)長度值。

假設(shè)有這樣的一個(gè) ziplist，每個(gè)節(jié)點(diǎn)都是等于 253 字節(jié)的。新增了一個(gè)大于等于 254 字節(jié)的新節(jié)點(diǎn)，由于之前的節(jié)點(diǎn) prevlen 長度是 1 個(gè)字節(jié)。

為了要記錄新增節(jié)點(diǎn)的長度所以需要對(duì)節(jié)點(diǎn) 1 進(jìn)行擴(kuò)展，由于節(jié)點(diǎn) 1 本身就是 253 字節(jié)，再加上擴(kuò)展為 5 字節(jié)的 pervlen 則長度超過了 254 字節(jié)，這時(shí)候下一個(gè)節(jié)點(diǎn)又要進(jìn)行擴(kuò)展了。噩夢(mèng)就開始了。

四 總結(jié)

• ziplist 為了節(jié)省內(nèi)存，采用了緊湊的連續(xù)存儲(chǔ)。所以在修改操作下并不能像一般的鏈表那么容易，需要從新分配新的內(nèi)存，然后復(fù)制到新的空間。
• ziplist 是一個(gè)雙向鏈表，可以在時(shí)間復(fù)雜度為 O(1) 從下頭部、尾部進(jìn)行 pop 或 push。
• 新增或更新元素可能會(huì)出現(xiàn)連鎖更新現(xiàn)象。
• 不能保存過多的元素，否則查詢效率就會(huì)降低。

其實(shí)使用中并沒有直接指定是否使用這種數(shù)據(jù)結(jié)構(gòu)，但是可以設(shè)置何種情況下使用它?？梢栽?Redis 的配置文件中進(jìn)行設(shè)置。

支持的數(shù)據(jù)類型有 List 對(duì)象、Hash 對(duì)象、Zset 對(duì)象，有以下可選設(shè)置項(xiàng)：

• hash-max-ziplist-entries：hash 類型元素?cái)?shù)量超過指定數(shù)據(jù)后時(shí)候。使用 hash 存儲(chǔ)， 否則使用壓縮表。
• hash-max-ziplist-value： hash 類型元素長度超過指定數(shù)據(jù)后時(shí)候。 使用 hash 存儲(chǔ)，否則使用壓縮鏈表。
• zset-max-ziplist-entries：zset 類型 壓縮列表 ziplist 最大限制元素?cái)?shù)。超過指定值將會(huì)使用跳表 skiplist + dict 來存儲(chǔ)。
• zset-max-ziplist-value：set 類型 壓縮列表 ziplist 最大限制大小。超過指定將會(huì)使用跳表 skiplist+dict 來存儲(chǔ)。
• list-max-ziplist-value: list 保存的所有字符串元素的長度都小于64字節(jié)。
• list-max-ziplist-entries：list 保存的元素?cái)?shù)量小于512個(gè)。

到此這篇關(guān)于Redis中ziplist壓縮列表的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Redis ziplist壓縮列表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！