前言
壓縮列表（ziplist）是由一系列特殊編碼的內(nèi)存塊構(gòu)成的列表，它對(duì)于Redis的數(shù)據(jù)存儲(chǔ)優(yōu)化有著非常重要的作用。這篇文章總結(jié)一下redis中使用非常多的一個(gè)數(shù)據(jù)結(jié)構(gòu)壓縮鏈表ziplist。該數(shù)據(jù)結(jié)構(gòu)在redis中說(shuō)是無(wú)處不在也毫不過(guò)分，除了鏈表以外，很多其他數(shù)據(jù)結(jié)構(gòu)也是用它進(jìn)行過(guò)渡的，比如前面文章提到的SortedSet。下面話不多說(shuō)了，來(lái)一起看看詳細(xì)的介紹吧。
一、壓縮鏈表ziplist數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介
首先從整體上看下ziplist的結(jié)構(gòu)，如下圖：
壓縮鏈表ziplist結(jié)構(gòu)圖
可以看出字段很多，字節(jié)大小也不同，但這也就是壓縮鏈表的精髓所在了，我們依次總結(jié)一下。
| 字段 | 含義 |
|---|---|
| zlbytes | 該字段是壓縮鏈表的第一個(gè)字段，是無(wú)符號(hào)整型，占用4個(gè)字節(jié)。用于表示整個(gè)壓縮鏈表占用的字節(jié)數(shù)（包括它自己）。 |
| zltail | 無(wú)符號(hào)整型，占用4個(gè)字節(jié)。用于存儲(chǔ)從壓縮鏈表頭部到最后一個(gè)entry（不是尾元素zlend）的偏移量，在快速跳轉(zhuǎn)到鏈表尾部的場(chǎng)景使用。 |
| zllen | 無(wú)符號(hào)整型，占用2個(gè)字節(jié)。用于存儲(chǔ)壓縮鏈表中包含的entry總數(shù)。 |
| zlend | 特殊的entry，用來(lái)表示壓縮鏈表的末尾。占用一個(gè)字節(jié)，值恒為255。 |
總結(jié)為ziplist的頭跟尾，下面再總結(jié)一下重中之重的entry字段。
一般來(lái)說(shuō)，一個(gè)entry由prevlen，encoding，entry-data三個(gè)字段組成，但當(dāng)entry是個(gè)很小的整數(shù)時(shí)，會(huì)根據(jù)編碼省略掉entry-data字段。下面依次進(jìn)行總結(jié)：
首先是字段prevlen：表示前一個(gè)entry的長(zhǎng)度，有兩種編碼方式。
- 當(dāng)長(zhǎng)度小于255字節(jié)時(shí)，用一個(gè)字節(jié)存儲(chǔ)。
- 當(dāng)長(zhǎng)度大于等于255時(shí)，用五個(gè)字節(jié)進(jìn)行存儲(chǔ)，其中第一個(gè)字節(jié)會(huì)被設(shè)置為255表示前一個(gè)entry的長(zhǎng)度由后面四個(gè)字節(jié)表示。
然后是字段encoding：它會(huì)根據(jù)當(dāng)前元素內(nèi)容的不同會(huì)采用不同的編碼方式，如下：
1、如果元素內(nèi)容為字符串，encoding的值分別為：
00xx xxxx ：00開頭表示該字符串的長(zhǎng)度用6個(gè)bit表示。
01xx xxxx | xxxx xxxx ：01開頭表示字符串的長(zhǎng)度由14bit表示，這14個(gè)bit采用大端存儲(chǔ)。
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10開頭表示后續(xù)的四個(gè)字節(jié)為字符串長(zhǎng)度，這32個(gè)bit采用大端存儲(chǔ)。
2、如果元素內(nèi)容為數(shù)字，encoding的值分別為：
1100 0000：表示數(shù)字占用后面2個(gè)字節(jié)。
1101 0000：表示數(shù)字占用后面4個(gè)字節(jié)。
1110 0000：表示數(shù)字占用后面8個(gè)字節(jié)。
1111 0000 ：表示數(shù)字占用后面3個(gè)字節(jié)。
1111 1110 ：表示數(shù)字占用后面1個(gè)字節(jié)。
1111 1111 ：表示壓縮鏈表中最后一個(gè)元素（特殊編碼）。
1111 xxxx ：表示只用后4位表示0~12的整數(shù)，由于0000，1110跟1111三種已經(jīng)被占用，也就是說(shuō)這里的xxxx四位只能表示0001~1101，轉(zhuǎn)換成十進(jìn)制就是數(shù)字1~13，但是redis規(guī)定它用來(lái)表示0~12，因此當(dāng)遇到這個(gè)編碼時(shí)，我們需要取出后四位然后減1來(lái)得到正確的值。
最后是字段entry-data：如果元素的值為字符串，則保存元素本身的值。如果元素的值為很小的數(shù)字（按上面編碼規(guī)則即0~12），則沒(méi)有該字段。
壓縮鏈表的編碼非常復(fù)雜，但這也正是該數(shù)據(jù)結(jié)構(gòu)的精髓所在，一起來(lái)看一個(gè)例子吧：
注：這個(gè)例子是redis源碼中提到的
|
1
2
3
4
5
6
|
//由元素2，5組成的壓縮鏈表[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end//字符串"Hello World"編碼后的內(nèi)容[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64] |
上面是一段用十六進(jìn)制表示2，5兩個(gè)元素組成的壓縮鏈表。
- 首先前四個(gè)字節(jié)表示整個(gè)ziplist占用的字節(jié)數(shù)，因?yàn)閞edis采用小端存儲(chǔ)，所以15個(gè)字節(jié)表示為0f 00 00 00。
- 接下來(lái)的4個(gè)字節(jié)表示末尾元素偏移量，是從ziplist頭（zlbytes）開始到最后一個(gè)元素（注：不是尾節(jié)點(diǎn)）的偏移量，也是采用小端存儲(chǔ)，因此表示為0c 00 00 00。
- 再后面是由兩個(gè)字節(jié)組成的表示元素個(gè)數(shù)的zllen字段，在我們這個(gè)例子中有兩個(gè)元素，加上小端存儲(chǔ)，所以表示為02 00。
- 接下來(lái)是元素本身，首先由一個(gè)變長(zhǎng)的字端表示前一個(gè)元素的長(zhǎng)度，2作為第一個(gè)元素，它前一個(gè)元素的大小就是0，因此占用一個(gè)字節(jié)00。按照我們上面說(shuō)的編碼規(guī)則，元素2跟5屬于0~12之間的數(shù)字，需要使用1111 xxxx格式進(jìn)行編碼，2轉(zhuǎn)成二進(jìn)制為0010，再加上1就是0011（加1的原因上面已經(jīng)說(shuō)明），組合起來(lái)元素2就表示為00 f3。同理元素5表示為02 f6。
- 最后就是尾元素，使用未被占用的編碼1111 1111即255。
接下來(lái)我們?cè)谶@個(gè)壓縮鏈表末尾插入一個(gè)字符串元素Hello World，先看看該如何編碼該字符串，按照約定的編碼規(guī)則，首先要用字節(jié)表示前一個(gè)元素的長(zhǎng)度，這里前一個(gè)元素時(shí)5，總共占用了兩個(gè)字節(jié)，因此首先用一個(gè)字節(jié)表示前一個(gè)元素的長(zhǎng)度02，接下來(lái)是字符串的編碼，我們要加入的字符串長(zhǎng)度為11（空格也算），轉(zhuǎn)換成二進(jìn)制就是1011，按照字符串的編碼規(guī)則，使用0000 1011表示，轉(zhuǎn)為十六進(jìn)制就是0b，最后再加上我們字符串本身的ASCII碼，綜合起來(lái)就得出該字符串的編碼：[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。
此時(shí)整個(gè)壓縮鏈表就變?yōu)椋?/p>
|
1
2
3
|
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff] | | | | | | | zlbytes zltail entries "2" "5" "Hello World" end |
二、壓縮鏈表ziplist命令源碼分析
搞明白上面的編碼規(guī)則以后，我們?cè)賮?lái)看下壓縮鏈表ziplist的部分操作源碼，本文就創(chuàng)建壓縮鏈表，插入元素，刪除元素，查找元素四個(gè)操作來(lái)總結(jié)一下壓縮鏈表的基本原理。
首先是創(chuàng)建：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//定義由zlbytes，zltail跟zllen組成的壓縮鏈表的頭大小#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))//創(chuàng)建一個(gè)壓縮鏈表，并且返回指向該鏈表的指針unsigned char *ziplistNew(void) { //這里之所以+1是因?yàn)槲苍卣加靡粋€(gè)字節(jié)，這也是一個(gè)壓縮鏈表最小尺寸 unsigned int bytes = ZIPLIST_HEADER_SIZE+1; //分配內(nèi)存 unsigned char *zl = zmalloc(bytes); //設(shè)置鏈表大小 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); //設(shè)置最后一個(gè)元素的偏移量 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); //設(shè)置元素個(gè)數(shù) ZIPLIST_LENGTH(zl) = 0; //設(shè)置尾元素（上面只是申請(qǐng)空間） zl[bytes-1] = ZIP_END; return zl;} |
創(chuàng)建壓縮鏈表的邏輯很簡(jiǎn)單，就是申請(qǐng)固定的包含頭尾節(jié)點(diǎn)的空間，然后初始化鏈表上下文。
與創(chuàng)建相比，添加元素的源碼就非常冗長(zhǎng)了，為了便于理解，在看源碼之前我們先自己梳理一下添加元素的邏輯。
- 首先我們要找到指定插入位置的前一個(gè)元素的大小，因?yàn)樵搶傩允切略氐慕M成部分之一。
- 然后我們要對(duì)當(dāng)前元素進(jìn)行編碼來(lái)獲得相應(yīng)的encoding字段跟實(shí)際元素值的字段。
- 新插入元素的后繼元素的prevlen字段要更新，因?yàn)樗懊娴脑匾呀?jīng)改變。這里可能引起級(jí)聯(lián)更新（刪除元素也有該問(wèn)題），原因就是prevlen字段大小是可變的。
上面三步是核心步驟，其余的還有更新尾節(jié)點(diǎn)偏移量，修改鏈表元素個(gè)數(shù)等操作。當(dāng)然，由于壓縮鏈表是基于數(shù)組實(shí)現(xiàn)的，因此在插入或刪除元素的時(shí)候內(nèi)存拷貝也是必不可少的。
總結(jié)好上面的步驟以后，我們開始一步一步分析源碼，比較長(zhǎng)，慢慢看：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
//四個(gè)參數(shù)依次是：壓縮鏈表，插入位置（新元素插入p元素后面），元素值，元素長(zhǎng)度unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { //這里是保存當(dāng)前鏈表的長(zhǎng)度 size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen; unsigned int prevlensize, prevlen = 0; size_t offset; int nextdiff = 0; unsigned char encoding = 0; long long value = 123456789; zlentry tail; //1. 這段邏輯目的就是獲取前置元素的長(zhǎng)度 if (p[0] != ZIP_END) { //如果插入位置的元素不是尾元素,則獲取該元素的長(zhǎng)度 //這里為了后面使用方便進(jìn)行了拆分，prevlensize保存encoding字段的長(zhǎng)度，prevlen保存元素本身的長(zhǎng)度 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); } else { //如果插入位置的元素是尾元素，那么需要把新元素插入鏈表尾端 //獲取到鏈表最后一個(gè)元素（注：最后一個(gè)元素不等于尾元素） unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); if (ptail[0] != ZIP_END) { //如果最后一個(gè)元素不是尾元素，則該元素為新元素的前置元素，獲取該元素長(zhǎng)度 prevlen = zipRawEntryLength(ptail); } //否則說(shuō)明鏈表還沒(méi)有任何元素，即新元素的前置元素長(zhǎng)度為0 } //2. 對(duì)新元素進(jìn)行編碼，獲取新元素的總大小 if (zipTryEncoding(s,slen,&value,&encoding)) { //如果是數(shù)字，則按數(shù)字進(jìn)行編碼 reqlen = zipIntSize(encoding); } else { //元素長(zhǎng)度即為字符串長(zhǎng)度 reqlen = slen; } //新元素總長(zhǎng)度為值的長(zhǎng)度加上前置元素跟encoding元素的長(zhǎng)度 reqlen += zipStorePrevEntryLength(NULL,prevlen); reqlen += zipStoreEntryEncoding(NULL,encoding,slen); //如果插入的位置不是鏈表尾，則要對(duì)新元素的后續(xù)元素的prevlen字段進(jìn)行判斷 //根據(jù)上面的編碼規(guī)則，該字段可能需要擴(kuò)容 int forcelarge = 0; nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; if (nextdiff == -4 && reqlen < 4) { nextdiff = 0; forcelarge = 1; } //按照新計(jì)算出的數(shù)組大小進(jìn)行擴(kuò)容，由于新數(shù)組的地址可能會(huì)改變，因此這里記錄舊的偏移量 offset = p-zl; zl = ziplistResize(zl,curlen+reqlen+nextdiff); //在新數(shù)組上計(jì)算插入位置 p = zl+offset; //如果新插入的元素不是在鏈表末尾 if (p[0] != ZIP_END) { //把新元素后繼元素復(fù)制到新的數(shù)組中，-1為尾元素 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); //新元素的后繼元素的prevlen字段 if (forcelarge) zipStorePrevEntryLengthLarge(p+reqlen,reqlen); else zipStorePrevEntryLength(p+reqlen,reqlen); //更新最后一個(gè)元素的偏移量 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); //當(dāng)新元素的后繼元素不止有一個(gè)時(shí)，新的尾元素偏移量需要加上nextdiff zipEntry(p+reqlen, &tail); if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); } } else { //新元素插入到鏈表尾端，更新尾端偏移量 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); } //nextdiff !=0表示后繼元素的長(zhǎng)度發(fā)生變化，因此我們需要級(jí)聯(lián)更新后繼元素的后繼元素 if (nextdiff != 0) { offset = p-zl; zl = __ziplistCascadeUpdate(zl,p+reqlen); p = zl+offset; } //把新元素寫入鏈表 p += zipStorePrevEntryLength(p,prevlen); p += zipStoreEntryEncoding(p,encoding,slen); if (ZIP_IS_STR(encoding)) { memcpy(p,s,slen); } else { zipSaveInteger(p,value,encoding); } //壓縮鏈表存儲(chǔ)元素?cái)?shù)量+1 ZIPLIST_INCR_LENGTH(zl,1); return zl;} |
分析完插入元素的邏輯，長(zhǎng)舒一口氣，真的很長(zhǎng)，細(xì)節(jié)也很多。
接下來(lái)在再看下刪除元素的過(guò)程，與添加相比，刪除相對(duì)要簡(jiǎn)單一些，清空當(dāng)前元素以后，需要把后繼元素一個(gè)一個(gè)拷貝上來(lái)（這也是數(shù)組跟鏈表兩個(gè)數(shù)據(jù)結(jié)構(gòu)的差別），然后注意是否需要級(jí)聯(lián)更新，上代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
//參數(shù)依次為：壓縮鏈表，刪除元素的其實(shí)位置，刪除元素的個(gè)數(shù)unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) { unsigned int i, totlen, deleted = 0; size_t offset; int nextdiff = 0; zlentry first, tail; //讀取p指向的元素保存在first中 zipEntry(p, &first); for (i = 0; p[0] != ZIP_END && i < num; i++) { //統(tǒng)計(jì)總共刪除的長(zhǎng)度 p += zipRawEntryLength(p); //統(tǒng)計(jì)實(shí)際刪除元素的個(gè)數(shù) deleted++; } //需要?jiǎng)h除元素的字節(jié)數(shù) totlen = p-first.p; if (totlen > 0) { if (p[0] != ZIP_END) { //判斷元素大小是否有改變 nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); //修改刪除元素之后的元素的prevlen字段 p -= nextdiff; zipStorePrevEntryLength(p,first.prevrawlen); //更新末尾元素的偏移量 ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen); //當(dāng)刪除元素的后繼元素不止有一個(gè)時(shí)，新的末尾元素偏移量需要加上nextdiff zipEntry(p, &tail); if (p[tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); } //把后面剩余的元素移動(dòng)至前面 memmove(first.p,p, intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1); } else { //直接刪除到鏈表末尾，因此不需要內(nèi)存拷貝，只需修改最后一個(gè)元素的偏移量 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe((first.p-zl)-first.prevrawlen); } //resize數(shù)組大小 offset = first.p-zl; zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff); //修改鏈表元素個(gè)數(shù) ZIPLIST_INCR_LENGTH(zl,-deleted); p = zl+offset; //nextdiff != 0表示元素大小發(fā)生變化，需要進(jìn)行級(jí)聯(lián)更新 if (nextdiff != 0) zl = __ziplistCascadeUpdate(zl,p); } return zl;} |
最后我們看下元素的查找操作：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
//參數(shù)依次為：壓縮鏈表，要查找元素的值，要查找元素的長(zhǎng)度，每次比較之間跳過(guò)的元素個(gè)數(shù)unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) { int skipcnt = 0; unsigned char vencoding = 0; long long vll = 0; //只要還沒(méi)到尾元素就不斷循環(huán) while (p[0] != ZIP_END) { unsigned int prevlensize, encoding, lensize, len; unsigned char *q; //查詢鏈表當(dāng)前元素的prevlen字段 ZIP_DECODE_PREVLENSIZE(p, prevlensize); //查詢鏈表當(dāng)前元素的encoding字段 ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len); q = p + prevlensize + lensize; //已到達(dá)需要比較的元素位置 if (skipcnt == 0) { //如果鏈表中的當(dāng)前元素時(shí)字符串 if (ZIP_IS_STR(encoding)) { //跟要查找的字符串進(jìn)行比較 if (len == vlen && memcmp(q, vstr, vlen) == 0) { //匹配成功，則要查找元素的指針 return p; } } else { //如果當(dāng)前元素為數(shù)字且vencoding為0 if (vencoding == 0) { //嘗試對(duì)要查找的值進(jìn)行數(shù)字編碼 if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) { //如果編碼失敗，則說(shuō)明要查找的元素根本不是數(shù)字 //然后把vencoding設(shè)置為最大值，起一個(gè)標(biāo)記作用 //也就是說(shuō)后面就不用嘗試把要查找的值編碼成數(shù)字了 vencoding = UCHAR_MAX; } assert(vencoding); } //如果vencoding != UCHAR_MAX，則說(shuō)明要查找的元素成功編碼為數(shù)字 if (vencoding != UCHAR_MAX) { //按數(shù)字取出當(dāng)前鏈表中的元素 long long ll = zipLoadInteger(q, encoding); if (ll == vll) { //如果兩個(gè)數(shù)字相等，則返回元素指針 return p; } } } //重置需要跳過(guò)的元素個(gè)數(shù) skipcnt = skip; } else { //跳過(guò)元素 skipcnt--; } //遍歷下個(gè)元素 p = q + len; } //遍歷完整個(gè)鏈表，沒(méi)有找到元素 return NULL;} |
到這里就把壓縮鏈表的創(chuàng)建，添加，刪除，查找四個(gè)基本操作原理總結(jié)完了。
三、壓縮鏈表ziplist數(shù)據(jù)結(jié)構(gòu)總結(jié)
壓縮鏈表ziplist在redis中的應(yīng)用非常廣泛，它算是redis中最具特色的數(shù)據(jù)結(jié)構(gòu)了。該數(shù)據(jù)結(jié)構(gòu)的精髓其實(shí)就在于文章第一部分總結(jié)的編碼規(guī)則，先理清楚這部分內(nèi)容，后面的源碼可以簡(jiǎn)單看下加深理解。
不得不說(shuō)源碼部分著實(shí)有點(diǎn)冗長(zhǎng)，確實(shí)需要耐心，我自己在讀的過(guò)程中也很頭大。如果對(duì)源碼感興趣的話，建議按我的方法，先自己梳理某個(gè)操作（例如上面提到的插入元素）需要做哪些事情，然后再看代碼可能會(huì)更好理解一些。
最后留一個(gè)小問(wèn)題，既然redis中的ziplist對(duì)內(nèi)存利用率如此之高，那為什么還要提供普通的鏈表結(jié)構(gòu)供用戶使用呢？
這個(gè)問(wèn)題沒(méi)有標(biāo)準(zhǔn)答案，仁者見(jiàn)仁智者見(jiàn)智吧~
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)服務(wù)器之家的支持。
原文鏈接：http://www.jianshu.com/p/565795f43eed
