redis源碼分析系列文章
[Redis源碼系列]在Liunx安裝和常見API
為什麼要從Redis源碼分析
String底層實現——動態字符串SDS
雙向鏈表都不懂，還說懂Redis?
面試官：說說Redis的Hash底層 我：……（來自閱文的面試題）
Redis的跳躍表確定不了解下
前言
大噶好，今天仍然是元氣滿滿的一天，拋開永遠寫不完的需求，拒絕要求賊變態的客戶，單純的學習技術，感受技術的魅力。（哈哈哈，皮一下很開森）
前面幾周我們一起看了Redis底層數據結構，如動態字符串SDS，雙向鏈表Adlist，字典Dict，跳躍表，如果有對Redis常見的類型或底層數據結構不明白的請看上面傳送門。
今天來說下set的底層實現整數集合，如果有對set不明白的，常見的API使用這篇就不講了，看上面的傳送門哈。
整數集合概念
整數集合是Redis設計的一種底層結構，是set的底層實現，當集合中只包含整數值元素，並且這個集合元素數據不多時，會使用這種結構。但是如果不滿足剛才的條件，會使用其他結構，這邊暫時不講哈。
下圖為整數集合的實際組成，包括三個部分，分別是編碼格式encoding，包含元素數量length，保存元素的數組contents。（這邊只需要簡單看下，下面針對每個模塊詳細說明哈）
整數集合的實現
我們看下intset.h裏面關於整數集合的定義，上代碼哈：
//整數集合結構體 typedef struct intset { uint32_t encoding; //編碼格式，有如下三種格式，初始值默認為INTSET_ENC_INT16 uint32_t length; //集合元素數量 int8_t contents[]; //保存元素的數組，元素類型並不一定是ini8_t類型，柔性數組不佔intset結構體大小，並且數組中的元素從小到大排列。 } intset; #define INTSET_ENC_INT16 (sizeof(int16_t)) //16位，2個字節，表示範圍-32,768~32,767 #define INTSET_ENC_INT32 (sizeof(int32_t)) //32位，4個字節，表示範圍-2,147,483,648~2,147,483,647 #define INTSET_ENC_INT64 (sizeof(int64_t)) //64位，8個字節，表示範圍-9,223,372,036,854,775,808~9,223,372,036,854,775,807
編碼格式encoding
包括INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64三種類型，其分別對應着不同的範圍，具體看上面代碼的註釋信息。
因為插入的數據的大小是不一樣的，為了盡可能的節約內存（畢竟都是錢，平時要省着點用），所以我們需要使用不同的類型來存儲數據。
集合元素數量length
記錄了保存數據contents的長度，即有多少個元素。
保存元素的數組contents
真正存儲數據的地方，數組是按照從小到大有序排序的，並且不包含任何重複項（因為set是不含重複項，所以其底層實現也是不含包含項的）。
整數集合升級過程(重點，手動標星)
上面的圖我們重新看下，編碼格式encoding為INTSET_ENC_INT16，即每個數據佔16位。長度length為4，即數組content裏面有四個元素，分別是1，2，3，4。如果我們要添加一個数字位40000，很明顯超過編碼格式為INTSET_ENC_INT16的範圍-32,768~32,767，應該是編碼格式為INTSET_ENC_INT32。那麼他是如何升級的呢，從INTSET_ENC_INT16升級到INTSET_ENC_INT32的呢？
1.了解舊的存儲格式
首先我們看下1，2，3，4這四個元素是如何存儲的。首先要知道一共有多少位，計算規則為length*編碼格式的位數，即4*16=64。所以每個元素佔用了16位。
2.確定新的編碼格式
新的元素為40000，已經超過了INTSET_ENC_INT16的範圍-32,768~32,767，所以新的編碼格式為INTSET_ENC_INT32。
3.根據新的編碼格式新增內存
上面已經說明了編碼格式為INTSET_ENC_INT32，計算規則為length*編碼格式的位數，即5*32=160。所以新增的位數為64-159。
4.根據編碼格式設置對應的值
從上面知道按照新的編碼格式，每個數據應該佔用32位，但是舊的編碼格式，每個數據佔用16位。所以我們從後面開始，每次獲取32位用來存儲數據。
這樣說太難懂了，看下圖。
首先，那最後32位，即128-159存儲40000。那麼第49-127是空着的。
接着，取空着的49-127最後的32位，即96到127這32位，用來存儲4。那麼之前4存儲的位置48-63和49-127剩下的64-95這兩部分組成了一個大部分，即48-95，現在空着啦。
在接着在48-95這個大部分，再取后32位，即64-95，用來存儲3。那麼之前3存儲位置32-47和48-95剩下的48-63這兩部分組成了一個大部分，即32-63，現在空着啦。
再接着，將32-63這個大部分，再取后32位，即還是32-63，用來存儲2。那麼之前2存儲位置16-31空着啦。
最後，將16-31和原來0-31合起來，存儲1。
至此，整個升級過程結束。整體來說，分為3步，確定新的編碼格式，新增需要的內存空間，從后往前調整數據。
這邊有個小問題，為啥要從后往前調整數據呢？
原因是如果從前往後，數據可能會覆蓋。也拿上面個例子來說，數據1在0-15位，數據2在16-31位，如果從前往後，我們知道新的編碼格式INTSET_ENC_INT32要求每個元素佔用32位，那麼數據1應該佔用0-31，這個時候數據2就被覆蓋了，以後就不知道數據2啦。
但是從后往前，因為後面新增了一些內存，所以不會發生覆蓋現象。
升級的優點
節約內存
整數集合既可以讓集合保存三種不同類型的值，又可以確保升級操作只在有需要的時候進行，這樣就節省了內存。
不支持降級
一旦對數組進行升級，編碼就會一直保存升級后的狀態。即使後面把40000刪掉了，編碼格式還是不會將會INTSET_ENC_INT16。
整數集合的源碼分析
創建一個空集合 intsetnew
這個方法比較簡單，是初始化整數集合的步驟，即下圖部分。
主要的步驟是分配內存空間，設置默認編碼格式，以及初始化數組長度length。
intset *intsetNew(void) { intset *is = zmalloc(sizeof(intset));//分配內存空間 is->encoding = intrev32ifbe(INTSET_ENC_INT16);//設置默認編碼格式INTSET_ENC_INT16 is->length = 0;//初始化length return is; }
添加元素並升級insetAdd流程圖（重點）
添加元素並升級insetAdd源碼分析
可以根據上面的流程圖，對照着下面的源碼分析，這邊就不寫啦哈。
//添加元素 //輸入參數*is為原整數集合 //value為要添加的元素 //*success為是否添加成功的標誌量 ，1表示成功，0表示失敗 intset *intsetAdd(intset *is, int64_t value, uint8_t *success) { //確定要添加的元素的編碼格式 uint8_t valenc = _intsetValueEncoding(value); uint32_t pos; //如果success沒有初始值，則初始化為1 if (success) *success = 1; //如果新的編碼格式大於現在的編碼格式，則升級並添加元素 if (valenc > intrev32ifbe(is->encoding)) { //調用另一個方法 return intsetUpgradeAndAdd(is,value); } else { //如果編碼格式不變，則調用查詢方法 //輸入參數is為原整數集合 //value為要添加的數據 //pos為位置 if (intsetSearch(is,value,&pos)) {//如果找到了，則直接返回，因為數據是不可重複的。 if (success) *success = 0; return is; } //設置length is = intsetResize(is,intrev32ifbe(is->length)+1); if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1); } //設置數據 _intsetSet(is,pos,value); is->length = intrev32ifbe(intrev32ifbe(is->length)+1); return is; } //#define INT8_MAX 127 //#define INT16_MAX 32767 //#define INT32_MAX 2147483647 //#define INT64_MAX 9223372036854775807LL static uint8_t _intsetValueEncoding(int64_t v) { if (v < INT32_MIN || v > INT32_MAX) return INTSET_ENC_INT64; else if (v < INT16_MIN || v > INT16_MAX) return INTSET_ENC_INT32; else return INTSET_ENC_INT16; } //根據輸入參數value的編碼格式，對整數集合is的編碼格式升級 static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { //當前集合的編碼格式 uint8_t curenc = intrev32ifbe(is->encoding); //根據對value解析獲取新的編碼格式 uint8_t newenc = _intsetValueEncoding(value); //獲取集合元素數量 int length = intrev32ifbe(is->length); //如果要添加的數據小於0，則prepend為1，否則為0 int prepend = value < 0 ? 1 : 0; //設置集合為新的編碼格式，並根據編碼格式重新設置內存 is->encoding = intrev32ifbe(newenc); is = intsetResize(is,intrev32ifbe(is->length)+1); //逐步循環，直到length小於0，挨個重新設置每個值，從后往前 while(length--) _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc)); //如果value為負數，則放在最前面 if (prepend) _intsetSet(is,0,value); else//如果value為整數，設置最末尾的元素為value _intsetSet(is,intrev32ifbe(is->length),value); //重新設置length is->length = intrev32ifbe(intrev32ifbe(is->length)+1); return is; } //找到is集合中值為value的下標，返回1，並保存在pos中，沒有找到返回0，並將pos設置為value可以插入到數組的位置 static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { int min = 0, max = intrev32ifbe(is->length)-1, mid = -1; int64_t cur = -1; //如果集合為空，那麼位置pos為0 if (intrev32ifbe(is->length) == 0) { if (pos) *pos = 0; return 0; } else { //因為數據是有序集合，如果要添加的數據大於最後一個数字，那麼直接把要添加的值放在最後即可，返回最大值下標 if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) { if (pos) *pos = intrev32ifbe(is->length); return 0; } else if (value < _intsetGet(is,0)) { //如果這個數據小於數組下標為0的數據，即為最小值 ，返回0 if (pos) *pos = 0; return 0; } } //有序集合採用二分法 while(max >= min) { mid = ((unsigned int)min + (unsigned int)max) >> 1; cur = _intsetGet(is,mid); if (value > cur) { min = mid+1; } else if (value < cur) { max = mid-1; } else { break; } } //確定找到 if (value == cur) { if (pos) *pos = mid;//設置參數pos，返回1，即找到位置 return 1; } else {//如果沒找到，則min和max相鄰，隨便設置都行，並返回0 if (pos) *pos = min; return 0; } }
結語
該篇主要講了Redis的SET數據類型的底層實現整數集合，先從整數集合是什麼，，剖析了其主要組成部分，進而通過多幅過程圖解釋了intset是如何升級的，最後結合源碼對整數集合進行描述，如創建過程，升級過程，中間穿插例子和過程圖。
如果覺得寫得還行，麻煩給個贊，您的認可才是我寫作的動力！
如果覺得有說的不對的地方，歡迎評論指出。
好了，拜拜咯。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※想知道最厲害的網頁設計公司"嚨底家"!
※幫你省時又省力,新北清潔一流服務好口碑
※別再煩惱如何寫文案,掌握八大原則!
