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
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...