本篇博客參考：
Redis 深度歷險(xiǎn)：核心原理與應(yīng)用實(shí)踐
Redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)詳解(4)——ziplist
上篇博客中，我給大家蜻蜓點(diǎn)水般的介紹了Redis中SDS的奧秘烤送，說(shuō)明Redis之所以那么快袁滥，還有一個(gè)很重要凿将、但是經(jīng)常被大家忽視的一點(diǎn)份帐，那就是Redis精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)桥状。本篇博客，還是繼續(xù)這個(gè)話題，給大家介紹下Redis另外一種底層數(shù)據(jù)結(jié)構(gòu)：ziplist嵌戈。
在Redis中，有五種基本數(shù)據(jù)類型听皿，除了上篇博客提到的String熟呛，還有l(wèi)ist，hash尉姨，zset庵朝，set，其中l(wèi)ist，hash九府，zset都間接或者直接使用了ziplist椎瘟，所以說(shuō)理解ziplist也是相當(dāng)重要的。
ziplist是什么意思
我剛開(kāi)始看ziplist的時(shí)候侄旬，總覺(jué)得zip這個(gè)單詞甚是熟悉肺蔚，好像在日常使用電腦的時(shí)候經(jīng)常看到儡羔，于是我百度了下：
哦哦宣羊，怪不得那么熟悉，原來(lái)就是“壓縮”的意思汰蜘，那ziplist就可以翻譯成“壓縮列表”了仇冯。
為什么要有ziplist
有兩點(diǎn)原因：
- 普通的雙向鏈表，會(huì)有兩個(gè)指針族操，在存儲(chǔ)數(shù)據(jù)很小的情況下赞枕，我們存儲(chǔ)的實(shí)際數(shù)據(jù)的大小可能還沒(méi)有指針占用的內(nèi)存大，是不是有點(diǎn)得不償失坪创？而且Redis是基于內(nèi)存的，而且是常駐內(nèi)存的姐赡，內(nèi)存是彌足珍貴的莱预，所以Redis的開(kāi)發(fā)者們肯定要使出渾身解數(shù)優(yōu)化占用內(nèi)存，于是项滑，ziplist出現(xiàn)了依沮。
- 鏈表在內(nèi)存中，一般是不連續(xù)的枪狂，遍歷相對(duì)比較慢危喉，而ziplist可以很好的解決這個(gè)問(wèn)題。
來(lái)看看ziplist的存在
zadd programmings 1.0 go 2.0 python 3.0 java
創(chuàng)建了一個(gè)zset州疾，里面有三個(gè)元素辜限，然后看下它采用的數(shù)據(jù)結(jié)構(gòu)：
debug object programmings
"Value at:0x7f404ac30c60 refcount:1 encoding:ziplist serializedlength:36 lru:2689815 lru_seconds_idle:9"
HSET website google "www.g.cn
創(chuàng)建了一個(gè)hash，只有一個(gè)元素严蓖，看下它采用的數(shù)據(jù)結(jié)構(gòu)：
debug object website
"Value at:0x7f404ac30ac0 refcount:1 encoding:ziplist serializedlength:30 lru:2690274 lru_seconds_idle:14"
可以很清楚的看到薄嫡，zset和hash都采用了ziplist數(shù)據(jù)結(jié)構(gòu)。
當(dāng)滿足一定的條件颗胡，zset和hash就不再使用ziplist數(shù)據(jù)結(jié)構(gòu)了：
debug object website
"Value at:0x7f404ac30ac0 refcount:1 encoding:hashtable serializedlength:180 lru:2690810 lru_seconds_idle:2"
可以看到毫深，hash的底層數(shù)據(jù)結(jié)構(gòu)變成了hashtable。
szet就不做實(shí)驗(yàn)了毒姨，感興趣的小伙伴們可以自己實(shí)驗(yàn)下哑蔫。
至于這個(gè)轉(zhuǎn)換條件是什么，放到后面再說(shuō)。
好奇的你們闸迷，肯定會(huì)嘗試看下list的底層數(shù)據(jù)結(jié)構(gòu)是什么嵌纲，發(fā)現(xiàn)并不是ziplist：
LPUSH languages python
debug object languages
"Value at:0x7f404c4763d0 refcount:1 encoding:quicklist serializedlength:21 lru:2691722 lru_seconds_idle:22 ql_nodes:1 ql_avg_node:1.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:19"
可以看到，list采用的底層數(shù)據(jù)結(jié)構(gòu)是quicklist稿黍，并不是ziplist疹瘦。
在低版本的Redis中，list采用的底層數(shù)據(jù)結(jié)構(gòu)是ziplist+linkedList巡球，高版本的Redis中言沐，quicklist替換了ziplist+linkedList，而quicklist也用到了ziplist酣栈，所以可以說(shuō)list間接使用了ziplist數(shù)據(jù)結(jié)構(gòu)险胰。這個(gè)quicklist是什么，不是本篇博客的內(nèi)容矿筝，暫且不表起便。
探究ziplist
ziplist源碼：ziplist源碼
ziplist源碼的注釋寫(xiě)的非常清楚，如果英語(yǔ)比較好窖维，可以直接看上面的注釋榆综，如果你英語(yǔ)不是太好，或者沒(méi)有一定的鉆研精神铸史，還是看看我寫(xiě)的博客吧鼻疮。
ziplist布局
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
這是在注釋中說(shuō)明的ziplist布局，我們一個(gè)個(gè)來(lái)看琳轿，這些字段是什么：
- zlbytes：32bit無(wú)符號(hào)整數(shù)判沟，表示ziplist占用的字節(jié)總數(shù)（包括<zlbytes>本身占用的4個(gè)字節(jié)）；
- zltail：32bit無(wú)符號(hào)整數(shù)崭篡，記錄最后一個(gè)entry的偏移量挪哄，方便快速定位到最后一個(gè)entry；
- zllen：16bit無(wú)符號(hào)整數(shù)琉闪，記錄entry的個(gè)數(shù)迹炼；
- entry：存儲(chǔ)的若干個(gè)元素，可以為字節(jié)數(shù)組或者整數(shù)颠毙；
- zlend：ziplist最后一個(gè)字節(jié)疗涉，是一個(gè)結(jié)束的標(biāo)記位，值固定為255吟秩。
Redis通過(guò)以下宏定義實(shí)現(xiàn)了對(duì)ziplist各個(gè)字段的存仍劭邸：
// 假設(shè)char *zl 指向ziplist首地址
// 指向zlbytes字段
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
// 指向zltail字段(zl+4)
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
// 指向zllen字段(zl+(4*2))
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
// 指向ziplist中尾元素的首地址
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// 指向zlend字段，指恒為255（0xFF）
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
entry的構(gòu)成
從ziplist布局中涵防，我們可以很清楚的知道闹伪，我們的數(shù)據(jù)被保存在ziplist中的一個(gè)個(gè)entry中沪铭，我們下面來(lái)看看entry的構(gòu)成。
<prevlen> <encoding> <entry-data>
我們?cè)賮?lái)看看這三個(gè)字段是什么：
- prevlen：前一個(gè)元素的字節(jié)長(zhǎng)度偏瓤，便于快速找到前一個(gè)元素的首地址杀怠，假如當(dāng)前元素的首地址是x，那么(x-prevlen)就是前一個(gè)元素的首地址厅克。
- encoding：當(dāng)前元素的編碼赔退，這個(gè)字段實(shí)在是太復(fù)雜了，我們放到后面再說(shuō)证舟；
- entry-data：實(shí)際存儲(chǔ)的數(shù)據(jù)硕旗。
prevlen
prevlen字段是變長(zhǎng)的：
- 前一個(gè)元素的長(zhǎng)度小于254字節(jié)時(shí)，prevlen用1個(gè)字節(jié)表示女责；
- 前一個(gè)元素的長(zhǎng)度大于等于254字節(jié)時(shí)漆枚，prevlen用5個(gè)字節(jié)進(jìn)行表示，此時(shí)抵知，prevlen的第一個(gè)字節(jié)是固定的254（0xFE）（作為這種情況的一個(gè)標(biāo)志）墙基，后面4個(gè)字節(jié)才表示前一個(gè)元素的長(zhǎng)度。
encoding
下面就要介紹下encoding這個(gè)字段了刷喜，在此之前残制，大家可以到陽(yáng)臺(tái)吹吹風(fēng)，喝口熱水掖疮，再做個(gè)深呼吸痘拆，最后再做一個(gè)心理準(zhǔn)備，因?yàn)檫@個(gè)字段實(shí)在是太復(fù)雜了氮墨，搞不好，看的時(shí)候吐葵，一下子吐了规揪。。温峭。如果實(shí)在無(wú)法理解猛铅，直接略過(guò)這一段吧。
Redis為了節(jié)約空間凤藏，對(duì)encoding字段進(jìn)行了相當(dāng)復(fù)雜的設(shè)計(jì)奸忽，Redis通過(guò)encoding來(lái)判斷存儲(chǔ)數(shù)據(jù)的類型，下面我們就來(lái)看看Redis是如何根據(jù)encoding來(lái)判斷存儲(chǔ)數(shù)據(jù)的類型的：
-
00xxxxxx最大長(zhǎng)度位 63 的短字符串揖庄，后面的6個(gè)位存儲(chǔ)字符串的位數(shù)栗菜； -
01xxxxxx xxxxxxxx中等長(zhǎng)度的字符串，后面14個(gè)位來(lái)表示字符串的長(zhǎng)度蹄梢； -
10000000 aaaaaaaa bbbbbbbb cccccccc dddddddd特大字符串疙筹，需要使用額外 4 個(gè)字節(jié)來(lái)表示長(zhǎng)度。第一個(gè)字節(jié)前綴是10，剩余 6 位沒(méi)有使用而咆，統(tǒng)一置為零霍比； -
11000000表示 int16； -
11010000表示 int32暴备； -
11100000表示 int64悠瞬； -
11110000表示 int24； -
11111110表示 int8涯捻； -
11111111表示 ziplist 的結(jié)束浅妆，也就是 zlend 的值 0xFF； -
1111xxxx表示極小整數(shù)汰瘫，xxxx 的范圍只能是 (0001~1101), 也就是1~13狂打。
如果是第10種情況，那么entry的構(gòu)成就發(fā)生變化了：
<prevlen> <encoding>
因?yàn)閿?shù)據(jù)已經(jīng)存儲(chǔ)在encoding字段中了混弥。
可以看出Redis根據(jù)encoding字段的前兩位來(lái)判斷存儲(chǔ)的數(shù)據(jù)是字符串（字節(jié)數(shù)組）還是整型趴乡，如果是字符串，還可以通過(guò)encoding字段的前兩位來(lái)判斷字符串的長(zhǎng)度蝗拿；如果是整形晾捏，則要通過(guò)后面的位來(lái)判斷具體長(zhǎng)度。
entry的結(jié)構(gòu)體
我們上面說(shuō)了那么多關(guān)于entry的點(diǎn)點(diǎn)滴滴哀托，下面將要說(shuō)的內(nèi)容可能會(huì)顛覆你三觀惦辛，我們?cè)谠创a中可以看到entry的結(jié)構(gòu)體，上面有一個(gè)注釋非常重要：
/* We use this function to receive information about a ziplist entry.
* Note that this is not how the data is actually encoded, is just what we
* get filled by a function in order to operate more easily. */
typedef struct zlentry {
unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
unsigned int prevrawlen; /* Previous entry len. */
unsigned int lensize; /* Bytes used to encode this entry type/len.
For example strings have a 1, 2 or 5 bytes
header. Integers always use a single byte.*/
unsigned int len; /* Bytes used to represent the actual entry.
For strings this is just the string length
while for integers it is 1, 2, 3, 4, 8 or
0 (for 4 bit immediate) depending on the
number range. */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
the entry encoding. However for 4 bits
immediate integers this can assume a range
of values and must be range-checked. */
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
重點(diǎn)看上面的注釋仓手。一句話解釋：這個(gè)結(jié)構(gòu)體雖然定義出來(lái)了胖齐，但是沒(méi)有被使用，因?yàn)槿绻娴倪@么使用的話嗽冒，那么entry占用的內(nèi)存就太大了呀伙。
ziplist的存儲(chǔ)形式
Redis并沒(méi)有像上篇博客介紹的SDS一樣，封裝一個(gè)結(jié)構(gòu)體來(lái)保存ziplist添坊，而是通過(guò)定義一系列宏來(lái)對(duì)數(shù)據(jù)進(jìn)行操作剿另，也就是說(shuō)ziplist是一堆字節(jié)數(shù)據(jù)，上面所說(shuō)的ziplist的布局和ziplist中的entry的布局只是抽象出來(lái)的概念贬蛙。
為什么不能一直是ziplist
在文章比較前面的部分雨女，我們做了實(shí)驗(yàn)來(lái)證明，滿足一定的條件后阳准，zset氛堕、hash的底層存儲(chǔ)結(jié)構(gòu)不再是ziplist，既然ziplist那么牛逼野蝇，Redis的開(kāi)發(fā)者也花了那么多精力在ziplist的設(shè)計(jì)上面岔擂，為什么zset位喂、hash的底層存儲(chǔ)結(jié)構(gòu)不能一直是ziplist呢？
因?yàn)閦iplist是緊湊存儲(chǔ)乱灵，沒(méi)有冗余空間塑崖，意味著新插入元素，就需要擴(kuò)展內(nèi)存痛倚，這就分為兩種情況：
- 分配新的內(nèi)存规婆，將原數(shù)據(jù)拷貝到新內(nèi)存；
- 擴(kuò)展原有內(nèi)存蝉稳。
所以ziplist 不適合存儲(chǔ)大型字符串抒蚜，存儲(chǔ)的元素也不宜過(guò)多。
ziplist存儲(chǔ)界限
那么滿足什么條件后耘戚，zset嗡髓、hash的底層存儲(chǔ)結(jié)構(gòu)不再是ziplist呢？在配置文件中可以進(jìn)行設(shè)置：
hash-max-ziplist-entries 512 # hash 的元素個(gè)數(shù)超過(guò) 512 就必須用標(biāo)準(zhǔn)結(jié)構(gòu)存儲(chǔ)
hash-max-ziplist-value 64 # hash 的任意元素的 key/value 的長(zhǎng)度超過(guò) 64 就必須用標(biāo)準(zhǔn)結(jié)構(gòu)存儲(chǔ)
zset-max-ziplist-entries 128 # zset 的元素個(gè)數(shù)超過(guò) 128 就必須用標(biāo)準(zhǔn)結(jié)構(gòu)存儲(chǔ)
zset-max-ziplist-value 64 # zset 的任意元素的長(zhǎng)度超過(guò) 64 就必須用標(biāo)準(zhǔn)結(jié)構(gòu)存儲(chǔ)
對(duì)于這個(gè)配置收津，我只是一個(gè)搬運(yùn)工饿这，并沒(méi)有去實(shí)驗(yàn)，畢竟沒(méi)有人會(huì)去修改這個(gè)吧撞秋，感興趣的小伙伴可以試驗(yàn)下长捧。
ziplist元素太多，怎么辦
在介紹ziplist布局的時(shí)候吻贿，說(shuō)到ziplist用兩個(gè)位來(lái)記錄ziplist的元素個(gè)數(shù)串结，如果元素個(gè)數(shù)實(shí)在太多，兩個(gè)位不夠怎么辦呢舅列？這種情況下肌割，求ziplist元素的個(gè)數(shù)只能遍歷了。
看到了吧帐要，Redis真不是想象中的那么簡(jiǎn)單把敞，需要研究的東西還是挺多，也挺復(fù)雜的宠叼，如果我們不去學(xué)習(xí)，可能覺(jué)得自己完全掌握了Redis其爵，但是一旦開(kāi)始學(xué)習(xí)了冒冬，才發(fā)現(xiàn)我們先前掌握的只是皮毛。驗(yàn)證了一句話摩渺，知道的越多简烤，不知道的越多。
本篇博客到這里就結(jié)束了摇幻。
