redis 5.0.7 源碼閱讀——壓縮列表ziplist

来源:https://www.cnblogs.com/chinxi/archive/2020/02/08/12272173.html
-Advertisement-
Play Games

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,操作類似。

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 首先我們先來說說這個ONNX ONNX是一種針對機器學習所設計的開放式的文件格式,用於存儲訓練好的模型。它使得不同的人工智慧框架(如Pytorch, MXNet)可以採用相同格式存儲模型數據並交互。 ONNX的規範及代碼主要由微軟,亞馬遜 ,Facebook 和 IBM 等公司共同開發,以開放源代碼 ...
  • 前言 最近的新型冠狀病毒流行讓很多人主動在家隔離,希望疫情能快點消退。武漢加油,中國必勝! Asp.Net Core 提供了內置的網站國際化(全球化與本地化)支持,微軟還內置了基於 resx 資源字元串的國際化服務組件。可以在入門教程中找到相關內容。 但是內置實現方式有一個明顯缺陷,resx 資源是 ...
  • 一、前言 在平時的開發中,當用戶修改數據時,一直沒有很好的辦法來記錄具體修改了那些信息,只能暫時採用將類序列化成 json 字元串,然後全塞入到日誌中的方式,此時如果我們想要知道用戶具體改變了哪幾個欄位的值的話就很困難了。因此,趁著這個假期,就來解決這個一直遺留的小問題,本篇文章記錄了我目前實現的方 ...
  • 很久沒有寫過 .NET Core 相關的文章了,目前關店在家休息所以有些時間寫一篇新的
  • 首先,先看我個人的項目結構。 這個webapi項目是專門作為圖片上傳的業務處理,而其中分為兩個控制器:單圖片上傳和多圖片上傳。在接下來的內容主要還是針對單文件上傳,對於多文件的上傳,我暫且尚未研究成功。 其中pictureoptions類,由於我把關於圖片上傳相關的配置項(保存路徑、限制的文件類型和 ...
  • 編譯安裝 Centos8下PHP源碼編譯和通過yum安裝的區別和以後的選擇 其實這兩種方法各有千秋: yum安裝: 從yum安裝來說吧,yum相當於是自動化幫你安裝,你不用管軟體的依賴關係,在yum安裝過程是幫你把軟體的全部依賴關係幫你傻瓜式的解決了。而且現在Centos7的服務啟動已經換成syst ...
  • 這裡分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農曆年分二十四節氣,希望在每個交節之日準時發佈一期 ...
  • Shell腳本基礎入門 Bash註釋 Bash只支持單行註釋,使用 開頭的都被當作註釋語句: 通過Bash的一些特性,可以取巧實現多行註釋: 所以,預設情況下讀寫數據都是終端,例如: 改變文件描述符對應的目標,可以改變數據的流向。比如標準輸入fd=1預設流向是終端設備,若將其改為/tmp/a.log ...
一周排行
    -Advertisement-
    Play Games
  • Dapr Outbox 是1.12中的功能。 本文只介紹Dapr Outbox 執行流程,Dapr Outbox基本用法請閱讀官方文檔 。本文中appID=order-processor,topic=orders 本文前提知識:熟悉Dapr狀態管理、Dapr發佈訂閱和Outbox 模式。 Outbo ...
  • 引言 在前幾章我們深度講解了單元測試和集成測試的基礎知識,這一章我們來講解一下代碼覆蓋率,代碼覆蓋率是單元測試運行的度量值,覆蓋率通常以百分比表示,用於衡量代碼被測試覆蓋的程度,幫助開發人員評估測試用例的質量和代碼的健壯性。常見的覆蓋率包括語句覆蓋率(Line Coverage)、分支覆蓋率(Bra ...
  • 前言 本文介紹瞭如何使用S7.NET庫實現對西門子PLC DB塊數據的讀寫,記錄了使用電腦模擬,模擬PLC,自至完成測試的詳細流程,並重點介紹了在這個過程中的易錯點,供參考。 用到的軟體: 1.Windows環境下鏈路層網路訪問的行業標準工具(WinPcap_4_1_3.exe)下載鏈接:http ...
  • 從依賴倒置原則(Dependency Inversion Principle, DIP)到控制反轉(Inversion of Control, IoC)再到依賴註入(Dependency Injection, DI)的演進過程,我們可以理解為一種逐步抽象和解耦的設計思想。這種思想在C#等面向對象的編 ...
  • 關於Python中的私有屬性和私有方法 Python對於類的成員沒有嚴格的訪問控制限制,這與其他面相對對象語言有區別。關於私有屬性和私有方法,有如下要點: 1、通常我們約定,兩個下劃線開頭的屬性是私有的(private)。其他為公共的(public); 2、類內部可以訪問私有屬性(方法); 3、類外 ...
  • C++ 訪問說明符 訪問說明符是 C++ 中控制類成員(屬性和方法)可訪問性的關鍵字。它們用於封裝類數據並保護其免受意外修改或濫用。 三種訪問說明符: public:允許從類外部的任何地方訪問成員。 private:僅允許在類內部訪問成員。 protected:允許在類內部及其派生類中訪問成員。 示 ...
  • 寫這個隨筆說一下C++的static_cast和dynamic_cast用在子類與父類的指針轉換時的一些事宜。首先,【static_cast,dynamic_cast】【父類指針,子類指針】,兩兩一組,共有4種組合:用 static_cast 父類轉子類、用 static_cast 子類轉父類、使用 ...
  • /******************************************************************************************************** * * * 設計雙向鏈表的介面 * * * * Copyright (c) 2023-2 ...
  • 相信接觸過spring做開發的小伙伴們一定使用過@ComponentScan註解 @ComponentScan("com.wangm.lifecycle") public class AppConfig { } @ComponentScan指定basePackage,將包下的類按照一定規則註冊成Be ...
  • 操作系統 :CentOS 7.6_x64 opensips版本: 2.4.9 python版本:2.7.5 python作為腳本語言,使用起來很方便,查了下opensips的文檔,支持使用python腳本寫邏輯代碼。今天整理下CentOS7環境下opensips2.4.9的python模塊筆記及使用 ...