Redis 整數集合的具體使用(intset)

一、集合概述

        對於集合,STL 的 set 相信大傢都不陌生,它的底層實現是紅黑樹。無論插入、刪除、查找都是 O(log n) 的時間復雜度。當然,如果用哈希表來實現集合,插入、刪除、查找都可以達到 O(1)。那麼為什麼集合要用紅黑樹和沒有用哈希表呢?我想,最大的可能是基於集合自身的特性,集合有它特有的操作:求交、求並、求差。這三個操作對於哈希表來說都是 O(n) 的。基於這一點,相比無序的哈希表來說,采用有序的紅黑樹會更加合適。

二、Redis 整數集合(intset)

        今天要講的整數集合,又稱為 intset,是 Redis 特有的數據結構。它的實現既不是紅黑樹,也不是哈希表。就是簡單的數組加上內存編碼。當存儲元素較少( 元素個數上限定義在server.h 的 OBJ_SET_MAX_INTSET_ENTRIES 宏定義值為512)且均為整型時,才會使用到整數集合。它的查找是 O(log n) 的,插入和刪除都是 O(n) 的。但是由於存儲元素相對較少的時候,O(log n) 和 O(n) 差距不是很大,但是用 Redis 的這種整數集合,相比紅黑樹和哈希表來說,可以大大減少內存。
        所以,Redis 的 整數集合 intset 的存在主要還是為瞭節省內存。

1、intset 結構定義

        intset 結構定義在 intset.h 中:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
 
typedef struct intset {
    uint32_t encoding;      /* a */
    uint32_t length;        /* b */
    int8_t contents[];      /* c */
} intset;

        a) encoding 指定瞭編碼方式,總共有 INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64 三種。從宏定義可以看出,這三個值分別為 2、4、8。從字面意思可以看出三者能表示的范圍是 16位整數、32位整數 以及 64位整數。
        b) length 存儲瞭整數集合的元素個數。
        c) contents 為整數集合的柔性數組,元素類型並不一定是 int8_t 類型的。 contents 不占用結構體的大小,它隻作為整數集合數據的首指針。整數集合中的元素按照從小到大的順序在 contents 中排列起來。

2、編碼方式

        首先,我們來理解編碼方式 encoding 的含義。需要明確的一點是,對於一個整數集合來說,所有的元素的編碼一定是一致的(否則每個數都得存一個編碼,而不是將它存在 intset 結構體內瞭),那麼整個整數集合的編碼取決於集合中“絕對值”最大的那個數(之所以是絕對值,因為整數包含正數和負數)。
        通過那個絕對值最大的整數來獲取編碼,實現如下:

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;
}

        這段代碼的含義是,如果整數 v 不能用 32位整數表示,那麼就需要用 INTSET_ENC_INT64 編碼;如果不能用 16位整數表示,那麼就需要用 INTSET_ENC_INT32 編碼;否則,采用 INTSET_ENC_INT16 編碼就行。核心就是:能用2個字節表示就不用4個字節,能用4個字節表示就不用8個字節,能省則省。
        幾個宏定義在 stdint.h 中,如下:

/* Minimum of signed integral types. */ 
# define INT16_MIN      (-32767-1)  
# define INT32_MIN      (-2147483647-1)  
 
/* Maximum of signed integral types. */  
# define INT16_MAX      (32767)  
# define INT32_MAX      (2147483647)  

3、編碼升級

        當前編碼方式不足以存儲更大位數的整數時,需要升級編碼。舉個例子,下圖所示的四個數字都在 [ -32768, 32767 ] 范圍內,所以采用 INTSET_ENC_INT16 編碼即可。contents 的數組長度為 sizeof(int16_t) * 4 = 2 * 4 = 8 個字節 ( 即64個二進制位 )。

        然後我們插入一個數,它的值為 32768,比 INT16_MAX 大1,所以它需要采用 INTSET_ENC_INT32 編碼,而整數集合中所有的數的編碼需要保持一致。那麼,所有數的編碼都需要轉為 INTSET_ENC_INT32 編碼。這就是 “升級”。如圖所示:

        升級完後,contents 數組的長度變為 sizeof(int32_t) * 5 = 4 * 5 = 20 個字節 ( 即160個二進制位 )。而且每個元素占用的內存都擴大一倍,所在的相對位置也發生瞭變化,導致所有的元素都需要往高位內存遷移。
        那我們一開始就把所有的整數集合都用 INTSET_ENC_INT64 來編碼不就好瞭,還省得麻煩。原因是 Redis 設計 intset 的初衷還是為瞭節省內存,設想一個集合的元素永遠都不會超過 16位 整數,那麼用 64位整數的話,相當於浪費瞭 3倍 的內存。

三、整數集合常用操作

1、創建集合

        創建一個整數集合 intsetNew,實現在 intset.c 中:

intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

       初始創建的整數集合為空集合,用 zmalloc 進行內存分配後,定義編碼為 INTSET_ENC_INT16,這樣可以使內存盡量小。這裡需要註意的是,intset 的存儲直接涉及到內存編碼,所以需要考慮主機的字節序問題(相關資料請參閱:字節序)。
       intrev32ifbe 的意思是 int32 reversal if big endian。即 如果當前主機字節序為大端序,那麼將它的內存存儲進行翻轉操作。簡言之,intset 的所有成員存儲方式都采用小端序。所以創建一個空的整數集合,內存分佈如下:

       瞭解瞭整數集合的內存編碼以後,我們來看看它的 設置 (set)和 獲取(get)。

2、元素設置

       設置 的含義就是給定整數集合以及一個位置和值,將值設置到這個整數集合的對應位置上。_intsetSet 實現如下:

static void _intsetSet(intset *is, int pos, int64_t value) {
    uint32_t encoding = intrev32ifbe(is->encoding);          /* a */
 
    if (encoding == INTSET_ENC_INT64) {
        ((int64_t*)is->contents)[pos] = value;               /* b */
        memrev64ifbe(((int64_t*)is->contents)+pos);          /* c */
    } else if (encoding == INTSET_ENC_INT32) {
        ((int32_t*)is->contents)[pos] = value;
        memrev32ifbe(((int32_t*)is->contents)+pos);
    } else {
        ((int16_t*)is->contents)[pos] = value;
        memrev16ifbe(((int16_t*)is->contents)+pos);
    }
}

       a) 大端序和小端序隻是存儲方式,encoding 在存儲的時候進行瞭一次 intrev32ifbe 轉換,取出來用的時候需要再進行一次 intrev32ifbe 轉換(其實就是序列化和反序列化)。
       b) 根據 encoding 的類型,將 contents 轉換成指定類型的指針,然後用 pos 進行索引找到對應的內存位置,然後將 value 的值設置到對應的內存中。
       c) memrev64ifbe 的實現參見 字節序 的 memrev64 函數,即將對應內存的值轉換成小端序存儲。

3、元素獲取

       獲取 的含義就是給定整數集合以及一個位置,返回給定位置的元素的值。_intsetGet 實現如下:

static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;
 
    if (enc == INTSET_ENC_INT64) {
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));   /* a */
        memrev64ifbe(&v64);                                      /* b */
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}
 
static int64_t _intsetGet(intset *is, int pos) {
    return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}

       a) 根據 encoding 的類型,將 contents 轉換成指定類型的指針,然後用 pos 進行索引找到對應的內存位置,將內存位置上的值拷貝到臨時變量中;
       b) 由於是直接的內存拷貝,所以取出來的值還是小端序的,那麼在大端序的主機上得到的值是不對的,所以需要再做一次 memrev64ifbe 轉換將值還原。

 4、元素查找

       由於整數集合是有序集合,所以查找某個元素是否在整數集合中,Redis 采用的是二分查找。intsetSearch 實現如下:

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;
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;                                        /* a */
        return 0;
    } else {                                                      /* b */
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }
    while(max >= min) {                                          
        mid = ((unsigned int)min + (unsigned int)max) >> 1;       /* c */
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }
    if (value == cur) {                                           /* d */
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

       a) 整數集合為空,返回0表示查找失敗;
       b) value 的值比整數集合中的最大值還大,或者比最小值還小,則返回0表示查找失敗;
       c) 執行二分查找,將找到的值存在 cur 中;
       d) 如果找到則返回1,表示查找成功,並且將 pos 設置為 mid 並返回;如果沒找到則返回一個需要插入的位置。

5、內存重分配

       由於 contents 的內存是動態分配的,所以每次進行元素插入或者刪除的時候,都需要重新分配內存,這個實現放在 intsetResize 中,實現如下:

static intset *intsetResize(intset *is, uint32_t len) {
    uint32_t size = len*intrev32ifbe(is->encoding);
    is = zrealloc(is,sizeof(intset)+size);
    return is;
}

       encoding 本身表示字節個數,所以乘上集合個數 len 就是 contents 數組需要的總字節數瞭,調用 zrealloc 進行內存重分配,然後返回重新分配後的地址。
       註意:zrealloc 的返回值必須返回出去,因為 intset 在進行內存重分配以後,地址可能就變瞭。即 is = zrealloc(is, …) 中,此 is 非彼 is。所以,所有調用 intsetResize 的函數都需要連帶的返回新的 intset 指針。

6、編碼升級

       編碼升級一定發生在元素插入,並且插入的元素的絕對值比整數集合中的元素都大的時候,所以我們把升級後的元素插入和編碼升級放在一個函數實現,名曰 intsetUpgradeAndAdd,實現如下:

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);                             
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;                                         /* a */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);                        /* b */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));   /* c */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);                       /* d */
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

       a) curenc 記錄升級前的編碼,newenc 記錄升級後的編碼;
       b) 將整數集合 is 的編碼設置成新的編碼後,進行內存重分配;
       c) 獲取原先內存中的數據,設置到新內存中(註意:由於兩段內存空間是重疊的,而且新內存的長度一定大於原先內存,所以需要從後往前進行拷貝);
       d) 當插入的值 value 為負數的時候,為瞭保證集合的有序性,需要插入到 contents 的頭部;反之,插入到尾部;當 value 為負數時 prepend 為1,這樣就可以保證在內存拷貝的時候將第 0 個位置留空。
       如圖展示瞭一個 (-32768, 0, 1, 32767) 的整數集合在插入數字 32768 後的升級的完整過程:

        整數集合升級的時間復雜度是 O(n) 的,但是在整數集合的生命期內,升級最多發生兩次(從 INTSET_ENC_INT16 到 INTSET_ENC_INT32 以及 從 INTSET_ENC_INT32 到 INTSET_ENC_INT64)。

7、內存遷移

        絕大多數情況都是在執行 插入 、刪除 、查找 操作。插入 和 刪除 會涉及到連續內存的移動。Redis 的內部實現中有一個函數 intsetMoveTail 就是用來實現內存移動的。

static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    uint32_t bytes = intrev32ifbe(is->length)-from;   /* a */
    uint32_t encoding = intrev32ifbe(is->encoding);
 
    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;                   
        dst = (int64_t*)is->contents+to;              
        bytes *= sizeof(int64_t);                     /* b */
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }
    memmove(dst,src,bytes);                           /* c */
}

       a) 統計從 from 到結尾,有多少個元素;
       b) 根據不同的編碼,計算出需要拷貝的內存字節數 bytes,以及拷貝源位置 src,拷貝目標位置 dst;
       c) memmove 是 string.h 中的函數:src指向的內存區域拷貝 bytes 個字節到 dst 所指向的內存區域,這個函數是支持內存重疊的;

8、元素插入

       最後,講整數集合的插入和刪除,插入調用的是 intsetAdd,在 intset.c 中實現:

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;
    if (valenc > intrev32ifbe(is->encoding)) {                               /* a */
        return intsetUpgradeAndAdd(is,value);
    } else {
        if (intsetSearch(is,value,&pos)) {                                
            if (success) *success = 0;                                       /* b */
            return is;
        }
        is = intsetResize(is,intrev32ifbe(is->length)+1);                    /* c */
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);    /* d */
    }
    _intsetSet(is,pos,value);                                                 
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);                   /* e */
    return is;
}

       a) 插入的數值 value 的內存編碼大於現有集合的編碼,直接調用 intsetUpgradeAndAdd 進行編碼升級;
       b) 集合元素是不重復的,如果 intsetSearch 能夠找到,則將 success 置為0,表示此次插入失敗;
       c) 如果 intsetSearch 找不到,將 intset 進行內存重分配,即 長度 加 1。
       d) pos 為 intsetSearch 過程中找到的 value 將要插入的位置,我們將 pos 以後的內存向後移動1個單位 (這裡的1個單位可能是2個字節、4個字節或者8個字節,取決於當前整數集合的內存編碼)。
       e) 調用 _intsetSet 將 value 的值設置到 pos 的位置上,然後給成員變量 length 加 1。最後返回 intset 指針首地址,因為其間進行瞭 intsetResize,傳入的 intset 指針和返回的有可能不是同一個瞭。

 9、元素刪除

       刪除元素調用的是 intsetRemove ,實現如下:

intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {  /* a */
        uint32_t len = intrev32ifbe(is->length);
        if (success) *success = 1;
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);                        /* b */
        is = intsetResize(is,len-1);                                            /* c */
        is->length = intrev32ifbe(len-1); 
    }
    return is;
}

       a) 當整數集合中存在 value 這個元素時才能執行刪除操作;
       b) 如果能通過 intsetSearch 找到元素,那麼它的位置就在 pos 上,這是通過 intsetMoveTail 將內存往前挪;
       c) intsetResize 重新分配內存,並且將集合長度減1;

到此這篇關於Redis 整數集合的具體使用的文章就介紹到這瞭,更多相關Redis 整數集合內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: