Redis數據結構之整數集合

• 2020 年 11 月 22 日
• 筆記
• C, Redis, 數據結構

1、整數集合

Redis 中有集合（set）的操作，常用的指令有 SADD、SCARD 等，而在底層的實現中，整數集合（intset）就是 Redis 集合的實現方式之一。

Redis 的集合是有序集合，intset 也是有序的。

根據 Redis 對集合的操作，我們可以大致想像出，intset 需要哪些功能：

1. 添加/移除元素要快；
2. 查找元素要快；
3. 方便兩個集合對比；
4. 統計元素個數；
5. 佔用內存要少；

Redis 作為高性能數據庫，佔用內存和操作快速是最主要的功能。intset 為了保證除了在保證快速的同時，使用升級來保證能夠存儲數據但是又節省空間的需求。

Redis 的 intset 相對來說比較簡單，下面也就大致的描述一下

2、intset的實現

intset 聲明位於源碼目錄下 intset.h 文件中，聲明如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

contents： contents 是一個柔性數組，這裡不多說，它裏面存儲的就是 intset 的所有整數項；

需要注意的是，雖然 contents 是 int8_t，不表示 contents 內部只能存 int8_t 類型的數據，後面會細說；

length： length 記錄了整個集合的元素數量，即 contents 數組的長度，當需要獲取元素個數的時候，直接返回這個值就行了，時間複雜度 O(1)；

encoding： encoding 決定該集合存儲的整數的類型，它的值有三種，如下：

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

可以看到，encoding 其實就可以表示 int8_t、int16_t、int32_t 和 int64_t（32位編譯器下分別表示佔用1一個、2個、4個 和 8個位元組，換做大部分人能認識的就是 char、short、int 和 long），其實可以看出來，encoding 就是這幾種類型的佔用內存，所以，如果如要計算集合中的所有元素所佔的內存，只需要用 length * encoding 就可以了

Redis 中使用 encoding 無非是為了節約內存，假如所有元素都是 int8_t，開闢了 int16_t 的空間，白白的就是在浪費內存嘛。

2.1、intset數據的存儲

那麼，contents 數組內是如何兼容不同類型的整數呢？我們都知道，C語言中最小的數據結構 char 佔8位，而16、32、64位均是8位的整數倍，所以我們只需要知道當前數組存儲的數據類型，就可以根據自己位計算出數據來，而不關注這個數組的長度了。

比如，現在 contents 數組共佔16位，從低到高分別是：

如果 encoding 表示8位元素，那麼，這裡可以得出兩個 int8_t 數據出來，分別是 229 和 141；

如果 encoding 表示16位元素，那麼，這裡可以得出一個 int16_t 數據出來，是 58765；

可見，不是說 contents 數組的類型是 int8_t 就只能存8位的數據，但是，contents 只能存儲一種類型的數據。

3、升級和降級

當我們需要將一個新的元素放入到集合中，並且這個新的數據比集合中的其他元素的類型的最大值還要大的時候，Redis 就需要統一使用較大的類型來存儲了，即需要擴容，這在 Redis 中叫做升級（upgrade）。

Redis 中升級集合併添加新元素總共需要三步：

1. 根據新元素的大小，確定數組的類型，並為數組分配空間；
2. 將底層已存在的舊有轉換成新的類型，並按照原先的順序，放置在固定的內存位置上；
3. 將新元素放在數組裡。

因為集合中的元素都是有序的，就算我們不需要進行升級，仍然需要從頭遍曆元素，也就是還是上面三步，所以插入元素的時間複雜度為 O(N)。

一旦出現需要升級操作，則表示新元素一定比舊有的元素要大，所以新元素放在最後就好。

舉個例子，現在有一個集合，其中有三個 int8_t 類型的元素：1、2、3，則 intset 中 encoding 值小於 INTSET_ENC_INT16，length 為3，contents 數組所佔內存為 8 * 3 = 24bit，即3個位元組，數據占內存位置如下：

現在插入一個 int16_t 類型的元素 32，我們發現，encoding 的值小於 INTSET_ENC_INT16，所以需要擴容，content 重新分配內存，16 *4 = 64bit，即8個位元組。擴容後的內存如下：

隨後，將原先的1、2、3轉換成 int16_t 類型，並按照原先的順序放置在固定位置，如下：

最後，將新元素放在數字的最後，即

元素放置完畢，encoding 值變為 INTSET_ENC_INT16， length 變為 4

Redis 的 intset 是不支持降級操作的，一旦數據升級，就會保持升級之後的類型，哪怕唯一個佔用內存大的元素被刪除了，剩下的元素仍然佔用大的類型的元素佔用的內存。

4、inset操作API

intset.h 文件中聲明了 intset 操作的API，整理如下：