多圖解釋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-6349-127剩下的64-95這兩部分組成了一個大部分,即48-95,現在空着啦。

在接着在48-95這個大部分,再取后32位,即64-95,用來存儲3。那麼之前3存儲位置32-4748-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是如何升級的,最後結合源碼對整數集合進行描述,如創建過程,升級過程,中間穿插例子和過程圖。

如果覺得寫得還行,麻煩給個贊,您的認可才是我寫作的動力!

如果覺得有說的不對的地方,歡迎評論指出。

好了,拜拜咯。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※想知道最厲害的網頁設計公司"嚨底家"!

※幫你省時又省力,新北清潔一流服務好口碑

※別再煩惱如何寫文案,掌握八大原則!

您可能也會喜歡…