redis源碼分析系列文章
[Redis源碼系列]在Liunx安裝和常見API
為什麼要從Redis源碼分析
String底層實作——動态字元串SDS
雙向連結清單都不懂，還說懂Redis?
面試官：說說Redis的Hash底層 我：......（來自閱文的面試題）
Redis的跳躍表确定不了解下
多圖解釋Redis的整數集合intset更新過程
前言
hello，大家好，又見面啦😊。
前面幾周我們一起看了Redis底層資料結構，如
動态字元串SDS
，
雙向連結清單Adlist
，
字典Dict
，
跳躍表
，
整數集合intset
，如果有對Redis常見的類型或底層資料結構不明白的請看上面傳送門。
今天來說下zset的底層實作
壓縮表(在資料庫量小的時候用)
，如果有對zset不明白的，看上面的傳送門哈。
壓縮清單的概念提出
傳統的數組
同之前的底層資料一樣，壓縮清單也是由Redis設計的一種資料存儲結構。
他有點類似于數組，都是通過一片連續的記憶體空間來存儲資料。但是其和數組也有點差別，數組存儲不同長度的字元時，會選擇最大的字元長度作為每個節點的記憶體大小。
如下圖，一共五個元素，每個元素的長度都是不一樣的，這個時候選擇最大值5作為每個元素的記憶體大小，如果選擇小于5的，那麼第一個元素hello，第二個元素world就不能完整存儲，資料會丢失。
存在的問題
上面已經提到了
需要用最大長度的字元串大小
作為
整個數組所有元素的記憶體大小
，如果隻有一個元素的長度超大，但是其他的元素長度都比較小，那麼我們所有元素的記憶體都用超大的數字就會導緻記憶體的浪費。
那麼我們應該如何改進呢？
引出壓縮清單
Redis引入了壓縮清單的概念，即多大的元素使用多大的記憶體，一切從實際出發，拒絕浪費。
如下圖，根據每個節點的實際存儲的内容決定記憶體的大小，即第一個節點占用5個位元組，第二個節點占用5個位元組，第三個節點占用1個位元組，第四個節點占用4個位元組，第五個節點占用3個位元組。
還有一個問題，我們在周遊的時候不知道每個元素的大小，無法準确計算出下一個節點的具體位置。實際存儲不會出現上圖的橫線，我們并不知道什麼時候目前節點結束，什麼時候到了下一個節點。是以在redis中添加length屬性，用來記錄前一個節點的長度。
如下圖，如果需要從頭開始周遊，取某個節點後面的數字，比如取“hello”的起始位址，但是不知道其結束位址在哪裡，我們取後面數字5，即可知道"hello"占用了5個位元組，即可順利找到下一節點“world”的起始位置。
壓縮清單圖解分析
整個壓縮清單圖解如下，大家可以大概看下，具體的後面部分會詳細說明。
表頭
表頭包括四個部分，分别是記憶體位元組數zlbytes，尾節點距離起始位址的位元組數zltail_offset，節點數量zllength，标志結束的記号zlend。
- zlbytes：記錄整個壓縮清單占用的記憶體位元組數。
- zltail_offset：記錄壓縮清單尾節點距離壓縮清單的起始位址的位元組數
（目的是為了直接定位到尾節點，友善反向查詢）
- zllength：記錄了壓縮清單的節點數量。即在上圖中節點數量為2。
- zlend：儲存一個常數255(0xFF)，标記壓縮清單的末端。
資料節點
資料節點包括三個部分，分别是前一個節點的長度prev_entry_len，目前資料類型和編碼格式encoding，具體資料指針value。
- prev_entry_len：記錄前驅節點的長度。
- encoding：記錄目前資料類型和編碼格式。
- value：存放具體的資料。
壓縮清單的具體實作
壓縮清單的構成
Redis并沒有像之前的字元串SDS，字典，跳躍表等結構一樣，封裝一個結構體來儲存壓縮清單的資訊。而是通過定義一系列宏來對資料進行操作。
也就是說壓縮清單是一堆位元組碼，咱也看不懂，Redis通過位元組之間的定位和計算來擷取資料的。
//傳回整個壓縮清單的總位元組
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
//傳回壓縮清單的tail_offset變量，友善擷取最後一個節點的位置
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
//傳回壓縮清單的節點數量
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
//傳回壓縮清單的表頭的位元組數
//（記憶體位元組數zlbytes，最後一個節點位址ztail_offset,節點總數量zllength）
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//傳回壓縮清單最後結尾的位元組數
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
//傳回壓縮清單首節點位址
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
//傳回壓縮清單尾節點位址
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
//傳回壓縮清單最後結尾的位址
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
壓縮清單節點的構成
我們看下面的代碼，重點看注釋，Note that this is not how the data is actually encoded，這句話說明這并不是資料的實際存儲格式。
是不是有點逗，定義了卻沒使用。
因為，這個結構存儲實在是太浪費空間了。這個結構32位機占用了25（int類型5個，每個int占4個位元組，char類型1個，每個char占用1個位元組，char*類型1個，每個char*占用4個位元組，是以總共5*4+1*1+1*4=25）個位元組，在64位機占用了29（int類型5個，每個int占4個位元組，char類型1個，每個char占用1個位元組，char*類型1個，每個char*占用8個位元組，是以總共5*4+1*1+1*8=29個位元組）。這不符合壓縮清單的設計目的。
/* We use this function to receive information about a ziplist entry.
* Note that this is not how the data is actually encoded, is just what we
* get filled by a function in order to operate more easily. */
typedef struct zlentry {
unsigned int prevrawlensize; //記錄prevrawlen需要的位元組數
unsigned int prevrawlen; //記錄上個節點的長度
unsigned int lensize; //記錄len需要的位元組數
unsigned int len; //記錄節點長度
unsigned int headersize; //prevrawlensize+lensize
unsigned char encoding; //編碼格式
unsigned char *p; //具體的資料指針
} zlentry;
是以Redis對上述結構進行了改進了，抽象合并了三個參數。
prev_entry_len
:prevrawlensize和prevrawlen的總和。
如果前一個節點長度小于254位元組，那麼prev_entry_len使用一個位元組表示。
如果前一個節點長度大于等于254位元組，那麼prev_entry_len使用五個位元組表示。第一個位元組為常數oxff，後面四位為真正的前一個節點的長度。
encoding
：lensize和len的總和。Redis通過設定了一組宏定義，使其能夠具有lensize和len兩種功能。（具體即不展開了）
value
：具體的資料。
壓縮清單的優點
節約記憶體。
壓縮清單的缺點
因為壓縮表是緊湊存儲的，沒有多餘的空間。這就意味着插入一個新的元素就需要調用函數擴充記憶體。過程中可能需要重新配置設定新的記憶體空間，并将之前的内容一次性拷貝到新的位址。
如果資料量太多，重新配置設定記憶體和拷貝資料會有很大的消耗。是以壓縮表不适合存儲大型字元串，并且資料元素不能太多。
壓縮清單的連鎖更新過程圖解（重點）
前面提到每個節點entry都會有一個prevlen字段存儲前一個節點entry的長度，如果内容小于254，prevlen用一個位元組存儲，如果大于254，就用五個位元組存儲。這意味着如果某個entry經過操作從253位元組變成了254位元組，那麼他的下一個節點entry的pervlen字段就要更新，從1個位元組擴充到5個位元組；如果這個entry的長度本來也是253位元組，那麼後面entry的prevlen字段還得繼續更新。
如果每個節點entry都存儲的253個位元組的内容，那麼第一個entry修改後會導緻後續所有的entry的級聯更新，這是一個比較損耗資源的操作。
是以，發生級聯更新的前提是有連續的250-253位元組長度的節點。
步驟一
比如一開始的壓縮表呈現下圖所示（XXXX表示字元串），現在想要把第二個資料的改大點，哪個時候就會發生級聯更新了。
步驟二
我們想要配置設定四個長度的大小給第三個資料的prevlen，因為第二個元素的prevlen字段是表示他前一個元素的大小。
步驟三
調整完發現第三個元素的長度增加了，是以第四個元素的prevlen字段也需要修改。
步驟四
調整完發現第四個元素的長度增加了，是以把第五個元素的prevlen字段也需要修改。
壓縮清單的源碼分析
建立空的壓縮表ziplistNew
主要的步驟是配置設定記憶體空間，初始化屬性，設定結束标記為常量，最後傳回壓縮表。
unsigned char *ziplistNew(void) {
//表頭加末端大小
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//為上面兩部分（表頭和末端）配置設定空間
unsigned char *zl = zmalloc(bytes);
//初始化表屬性
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;
//設定子產品，指派為常量
zl[bytes-1] = ZIP_END;
return zl;
}
級聯更新（重點）
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
size_t offset, noffset, extra;
unsigned char *np;
zlentry cur, next;
//while循環，當到最後一個節點的時候結束循環
while (p[0] != ZIP_END) {
//将節點資料儲存在cur中
zipEntry(p, &cur);
//取前節點長度編碼所占位元組數，和目前節點長度編碼所占位元組數，在加上目前節點的value長度
//rawlen = prev_entry_len + encoding + value
rawlen = cur.headersize + cur.len;
rawlensize = zipStorePrevEntryLength(NULL,rawlen);
//如果沒有下一個節點則跳出循環
if (p[rawlen] == ZIP_END) break;
//取出後面一個節點放在next中
zipEntry(p+rawlen, &next);
//當next的prevrawlen，即儲存的上一個節點等于rawlen，說明不需要調整，現在的長度合适
if (next.prevrawlen == rawlen) break;
//如果next對前一個節點長度的編碼所需的位元組數next.prevrawlensize小于上一個節點長度進行編碼所需要的長度
//是以要對next節點的header部分進行擴充，以便能夠表示前一個節點的長度
if (next.prevrawlensize < rawlensize) {
//記錄目前指針的偏移量
offset = p-zl;
///需要擴充的位元組數
extra = rawlensize-next.prevrawlensize;
//調整壓縮清單的空間大小
zl = ziplistResize(zl,curlen+extra);
//還原p指向的位置
p = zl+offset;
//next節點的新位址
np = p+rawlen;
//記錄next節點的偏移量
noffset = np-zl;
//更新壓縮清單的表頭tail_offset成員，如果next節點是尾節點就不用更新
if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
}
//移動next節點到新位址，為前驅節點cur騰出空間
memmove(np+rawlensize,
np+next.prevrawlensize,
curlen-noffset-next.prevrawlensize-1);
//将next節點的header以rawlen長度進行重新編碼，更新prevrawlensize和prevrawlen
zipStorePrevEntryLength(np,rawlen);
//更新p指針，移動到next節點，處理next的next節點
p += rawlen;
//更新壓縮清單的總位元組數
curlen += extra;
} else {
// 如果需要的記憶體反而更少了則強制保留現有記憶體不進行縮小
// 僅浪費一點記憶體卻省去了大量移動複制操作而且後續增大時也無需再擴充
if (next.prevrawlensize > rawlensize) {
zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
} else {
zipStorePrevEntryLength(p+rawlen,rawlen);
}
/* Stop here, as the raw length of "next" has not changed. */
break;
}
}
return zl;
}
結語
該篇主要講了Redis的zset資料類型的底層實作壓縮表，先從壓縮表是什麼，剖析了其主要組成部分，進而通過多幅過程圖解釋了壓縮表是如何層級更新的，最後結合源碼對壓縮表進行描述，如建立過程，更新過程，中間穿插例子和過程圖。
如果覺得寫得還行，麻煩給個贊👍，您的認可才是我寫作的動力！
如果覺得有說的不對的地方，歡迎評論指出。
好了，拜拜咯。