多圖解釋Redis的整數集合intset升級過程
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是如何升級的,最後結合源碼對整數集合進行描述,如創建過程,升級過程,中間穿插例子和過程圖。
如果覺得寫得還行,麻煩給個贊,您的認可才是我寫作的動力!
如果覺得有說的不對的地方,歡迎評論指出。
好了,拜拜咯。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※想知道最厲害的網頁設計公司"嚨底家"!
※幫你省時又省力,新北清潔一流服務好口碑
※別再煩惱如何寫文案,掌握八大原則!