redis中壓縮列表ziplist相關的文件為:ziplist.h與ziplist.c 壓縮列表是redis專門開發出來為了節約記憶體的記憶體編碼數據結構。源碼中關於壓縮列表介紹的註釋也寫得比較詳細。 一、數據結構 壓縮列表的整體結構如下(借用redis源碼註釋): 1 /* 2 <zlbytes> < ...
redis中壓縮列表ziplist相關的文件為:ziplist.h與ziplist.c
壓縮列表是redis專門開發出來為了節約記憶體的記憶體編碼數據結構。源碼中關於壓縮列表介紹的註釋也寫得比較詳細。
一、數據結構
壓縮列表的整體結構如下(借用redis源碼註釋):
1 /* 2 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> 3 */
各個部分的含義:
項 | 類型 | 長度 | 用途 |
zlbytes | uint32_t | 4B | ziplist總位元組數,包括zlbytes |
zltail | uint32_t | 4B | 最後一個entry的偏移量 |
zllen | uint16_t | 2B | entry數量 |
zlend | uint8_t | 1B | ziplist固定結尾,值固定為0xFF |
entry | 不定 | 不定 | ziplist的各節點,具體結構不定 |
關於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有關。
encoding前兩位 | encoding內容 | encoding長度 | entry-data類型 | entry-data長度 |
00 | |00pppppp| | 1B | string | 6b能表示的數字,0~63,encoding中存儲的長度為大端位元組序 |
01 | |01pppppp|qqqqqqqq| | 2B | string | 14b能表示的數字,64~16383,encoding中存儲的長度為大端位元組序 |
10 | |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| | 5B | string | int32能表示的數字,16384~2^32-1,encoding中存儲的長度為大端位元組序 |
11 | |11000000| | 1B | int16 | 2B |
11 | |11010000| | 1B | int32 | 4B |
11 | |11100000| | 1B | int64 | 8B |
11 | |11110000| | 1B | int24 | 3B |
11 | |11111110| | 1B | int8 | 1B |
11 | |1111xxxx| | 1B | 無 | xxxx在[0001,1101]之間,表示0~12的數字,存儲時進行+1操作 |
11 | |11111111| | 1B | 無 | End of ziplist special entry(源碼註釋) |
如一個具體的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,操作類似。