redis 5.0.7 原始碼閱讀——壓縮串列ziplist

redis中壓縮串列ziplist相關的檔案為：ziplist.h與ziplist.c

壓縮串列是redis專門開發出來為了節約記憶體的記憶體編碼資料結構，原始碼中關于壓縮串列介紹的注釋也寫得比較詳細，

一、資料結構

壓縮串列的整體結構如下（借用redis原始碼注釋）：

1 /*
2 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
3 */

各個部分的含義：

關于entry，借用redis原始碼注釋的結構改造一下：

1 /*
2 <prevlen> <encoding> [<entry-data>]
3 */

prevlen表示的是前一個entry的長度，用于反向遍歷，即從最后一個元素遍歷到第一個元素，因每個entry的長度是不確定的，所以要記錄一下前一個entry的長度，prevlen本身的長度也是不定的，與前一entry的實際長度有關，若長度小于254，只需要1B就可以了，若實際長度大于等于254，則需要5B，第1B固定為254，后面4B存盤實際長度，

encoding則與entry存盤的data有關，

如一個具體的ziplist，有兩個成員“2”與“5”：

/*
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
      |             |          |       |       |     |
   zlbytes        zltail     zllen    "2"     "5"   end
*/

zlbytes值為15，表示這個ziplist總長為15B

zltail的值為12，表示最后一個entry的偏移量為12

zllen的值為2，表示一共有兩個entry

第一個entry的prevlen為0，因為第一個成員之前沒有其它成員了，所以是0，占1B，值為“2”，可以用數字表示，且是介于[0,12]之間，故使用1111xxxx的encoding方式，無entry-data，2的二進制編碼為0010，+1后為0011，實際為11110011，即0xF3，同理，5的encoding為0xF6，做為第二個entry，其前一個entry的總長為2，故其prevlen值為2，

zlend固定是0xFF，

二、基本操作

redis中使用了大量的宏定義與函式配合操作ziplist，

1、創建

 1 #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
 2 #define ZIPLIST_END_SIZE        (sizeof(uint8_t))
 3 #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
 4 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
 5 #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
 6 #define ZIP_END 255 
 7 
 8 
 9 unsigned char *ziplistNew(void) {
10     unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
11     unsigned char *zl = zmalloc(bytes);
12     ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
13     ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
14     ZIPLIST_LENGTH(zl) = 0;
15     zl[bytes-1] = ZIP_END;
16     return zl;
17 }

新創建的ziplist，沒有entry，只有zlbytes、zltail、zllen與zlend：

1 /*
2 [0b 00 00 00] [0a 00 00 00] [00 00] [ff]
3       |             |          |     |
4    zlbytes        zltail     zllen  end
5 */

2、插入

假設有以下ziplist：

1 /*
2 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
3       |             |          |       |       |     |
4    zlbytes        zltail     zllen    "2"     "5"   end
5 */

要在"2"與"5"之間插入節點“3”，則：

a.獲取所要插入位置當前節點“5”的prevlen=2，prevlen_size=1

若要插入的位置是end處，則取出zltail進行偏移，取到“5”節點，直接進行計算，而如果當前是個空ziplist，直接就是0了，

b.獲取節點“3”的實際長度，若其為純數字，則可以使用數字存盤，節約記憶體，否則直接使用外部傳入的，string的長度，

這里有一點：

 1 int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
 2     long long value;
 3 
 4     if (entrylen >= 32 || entrylen == 0) return 0;
 5     if (string2ll((char*)entry,entrylen,&value)) {
 6         /* Great, the string can be encoded. Check what's the smallest
 7          * of our encoding types that can hold this value. */
 8         if (value >= 0 && value <= 12) {
 9             *encoding = ZIP_INT_IMM_MIN+value;
10         } else if (value >= INT8_MIN && value <= INT8_MAX) {
11             *encoding = ZIP_INT_8B;
12         } else if (value >= INT16_MIN && value <= INT16_MAX) {
13             *encoding = ZIP_INT_16B;
14         } else if (value >= INT24_MIN && value <= INT24_MAX) {
15             *encoding = ZIP_INT_24B;
16         } else if (value >= INT32_MIN && value <= INT32_MAX) {
17             *encoding = ZIP_INT_32B;
18         } else {
19             *encoding = ZIP_INT_64B;
20         }
21         *v = value;
22         return 1;
23     }
24     return 0;
25 }

在嘗試使用數字編碼的時候，如果len >= 32，則直接不嘗試，并不清楚這個32是怎么來的，

本例中，“3”可以直接使用數字編碼，且在[0,12]之間，故沒有entry-data

c.獲得本entry的總長度，即prevlen、encoding、entry-data長度和，本處為1+1=2

d.判斷一下插入后，后一個entry的prevlen是否足夠存盤新entry的長度，新長度為2，原entry的prevlen只有1B，足夠，

此處需要注意，如果原本是5B的prevlen，當前1B就足夠存盤，則不做任何處理，強制使用5B來存盤1B能存盤的數字，而如果原來是1B，當前要5B，則還需要4B空間，

e.重新分配ziplist空間，新增加的位元組數，為c、d兩步之和，此處只需要額外2B的空間，

分配空間后：

1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] [00 ff]
3       |             |          |       |       |     |
4    zlbytes        zltail     zllen    "2"     "5"   end
5 */

重新分配空間會自動設定zlend與zlbytes

f.將“5”及之后的節點（不包括zlend）往后移：

1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "5"     "5"  
5 */

g.修正當前“5”所在位置的prevlen=2：

1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "5"     "5"  
5 */

h.修改zltail：

1 /*
2 [11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "5"     "5"  
5 */

i.填寫新entry：

1 /*
2 [11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f4] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "3"     "5"  
5 */

j.更新zllen：

1 /*
2 [11 00 00 00] [0e 00 00 00] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "3"     "5"  
5 */

若在此基礎上，在“3”前，插入的是一個長度為256的string X，則：

a.獲取“3”的prevlen與prevlen_size

prevlen=2，prevlen_size=1

b.長度大于32，使用string進行存盤，實際長度data_len=256

c.獲取entry總長度

此處prevlen長度為1B，encoding長度為2B ，entry-data長度為256B，共1+2+256=259

d.判斷一下插入后，后一個entry的prevlen是否足夠存盤新entry的長度，新長度為259，超過了254，需要5B，而原本只有1B，還差了4B，即，nextdiff=4

e.分配空間，新增加位元組數為259+4=263，共280B，即0x118

分配空間后：

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [ff]
3    |      |      |       |       |       |      |   
4 zlbytes zltail zllen    "2"     "3"     "5"    263B
5    4B     4B
6 */

f.memmove操作

ziplist中的memmove操作：

1 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

操作完之后：

1 /*
2 [...] [00 f3] [02 f4] [02 f6] [...] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3   |      |       |       |      |              |       |       |
4 header  "2"     "3"     "5"    255B           "2"     "3"     "5"  
5  10B 
6 */

其中header為zlbytes、zltail與tllen

其實與以下寫法相同效果：

1 memmove(p+reqlen+nextdiff,p,curlen-offset-1+nextdiff);

這種寫法操作完之后：

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [02 f4] [02 f6] [ff]
3    |      |      |       |       |       |      |      |       |
4 zlbytes zltail zllen    "2"     "3"     "5"    259B   "3"     "5"  
5    4B     4B
6 */

目的是一樣的，把原來的節點移至正確的位置上，

g.修正當前“3”所在位置的prevlen=259，即0X103：

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [02 f6] [ff]
3    |      |      |       |      |            |             |
4 zlbytes zltail zllen    "2"    259B         "3"           "5"  
5    4B     4B
6 */

h.此時節點"3"的長度發生變化，需要更新其后一個節點"5"的prevlen：

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [06 f6] [ff]
3    |      |      |       |      |            |             |
4 zlbytes zltail zllen    "2"    259B         "3"           "5"  
5    4B     4B
6 */

i.修改zltail：

1 /*
2 [0x118] [0x115] [03 00] [00 f3] [...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |      |            |             |
4 zlbytes  zltail  zllen    "2"    259B         "3"           "5"  
5    4B      4B
6 */

j.填寫新entry：

encoding值為：01000001 00000000 即0x4100，大端位元組序

填寫后：

1 /*
2 [0x118] [0x115] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

k.更新zllen：

1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

若有連續幾個entry的長度在[250,253]B之間，在插入新節點后可能存在連鎖更新的情況，

如以下ziplist（只保留部分entry，其余節點省略）：

1 /*
2 ... [FD 40 FA ...] [FD 40 FA ...] ...
3           |              |
4        E1 253B        E2 253B
5 */

E1的prevlen為FD，即長度為253，此時在E1之前插入一個長度為256的節點，E1需要增加prevlen的長度，從而導致E1整體長度增加，

E2的prevlen為FD，即E1的長度為253，增加4個節點之后為257，E2也需要增加prevlen的長度，

之后還可能會有E3，E4等entry需要處理，產生了連鎖反應，直到到了以下情況才會停止：

i.到了zlend

ii.不需要繼續擴展

iii.需要減少prevlen位元組數時

連鎖更新時需要多次重新分配空間，最壞情況下有n個節點的ziplist，需要分配n次空間，而每次分配的最壞情況時間復雜度為O(n)，故連鎖更新的最壞情況時間復雜度為O(n^2)，

3、查找

ziplist的查找程序其實是一次遍歷，依次決議出prevlen、encoding與entry-data，然后根據encoding型別，決定是要用strcmp，還是直接使用數字的比較，在首次進行數字比較的時候，會把傳入要查找的串，嘗試一次轉換成數字的操作，如果無法轉換，就會跳過數字比較操作，

查找操作支持每隔幾個entry才做一次比較操作，如，查找每5個entry中，值為“1”的entry，

4、洗掉

如有以下ziplist：

1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

洗掉的是節點“5”，因是最后一個節點，則只要先修改zltail：

1 /*
2 [0x118] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

然后resize：

1 /*
2 [0x116] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3    |       |       |       |          |                 |         
4 zlbytes  zltail  zllen    "2"         X                "3"        
5    4B      4B                        259B
6 */

最后修改zllen即可：

1 /*
2 [0x116] [0x10F] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3    |       |       |       |          |                 |         
4 zlbytes  zltail  zllen    "2"         X                "3"        
5    4B      4B                        259B
6 */

如果是這個ziplist：

1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00 00 01 03 f4] [06 f3] [02 f6] [ff]
3    |       |       |          |                 |             |       |
4 zlbytes  zltail  zllen        X                "3"           "2"     "5"  
5    4B      4B                259B
6 */

如果洗掉是的節點"3"，則先要計算洗掉后，"3"節點后的"2"節點的prevlen長度是否足夠，然后直接寫入，此時長度不夠，并不會直接重新分配空間，而是直接使用之前"3"節的最后4B空間：

1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3    |       |       |          |           |             |             |
4 zlbytes  zltail  zllen        X           2B           "2"           "5"  
5    4B      4B                259B
6 */

然后修改zltail：

1 /*
2 [0x118] [0x113] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3    |       |       |          |           |             |             |
4 zlbytes  zltail  zllen        X           2B           "2"           "5"  
5    4B      4B                259B
6 */

接著進行memmove操作：

1 /*
2 [0x118] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [02 f6] [ff]
3    |       |       |          |                 |             |       | 
4 zlbytes  zltail  zllen        X                "2"           "5"     "5"
5    4B      4B                259B
6 */

resize操作：

1 /*
2 [0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [ff]
3    |       |       |          |                 |             |   
4 zlbytes  zltail  zllen        X                "2"           "5"  
5    4B      4B                259B
6 */

最后要更新節點"2"及其之后entry的prevlen：

1 /*
2 [0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [06 f6] [ff]
3    |       |       |          |                 |             |   
4 zlbytes  zltail  zllen        X                "2"           "5"  
5    4B      4B                259B
6 */

注意此時更新也是有可能產生連鎖反應，

洗掉操作支持洗掉從指定位置開始，連續n個entry，操作類似，

標籤：NoSQL

上一篇：redis五大資料型別

下一篇：[MongoDB]mongodb的命令列操作