共計 7682 個字符，預計需要花費 20 分鐘才能閱讀完成。
本篇文章為大家展示了 Redis 中內部數據結構 intset 的作用是什么，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
intset 數據結構簡介
intset 顧名思義，是由整數組成的集合。實際上，intset 是一個由整數組成的有序集合，從而便于在上面進行二分查找，用于快速地判斷一個元素是否屬于這個集合。它在內存分配上與
ziplist 有些類似，是連續的一整塊內存空間，而且對于大整數和小整數（按絕對值）采取了不同的編碼，盡量對內存的使用進行了優化。
intset 的數據結構定義如下（出自 intset.h 和 intset.c）：
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];} intset;
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))各個字段含義如下：
encoding: 數據編碼，表示 intset 中的每個數據元素用幾個字節來存儲。它有三種可能的取值：INTSET_ENC_INT16 表示每個元素用 2 個字節存儲，INTSET_ENC_INT32 表示每個元素用 4 個字節存儲，INTSET_ENC_INT64 表示每個元素用 8 個字節存儲。因此，intset 中存儲的整數最多只能占用 64bit。
length: 表示 intset 中的元素個數。encoding 和 length 兩個字段構成了 intset 的頭部（header）。
contents: 是一個柔性數組（
flexible array member），表示 intset 的 header 后面緊跟著數據元素。這個數組的總長度（即總字節數）等于 encoding * length。柔性數組在 Redis 的很多數據結構的定義中都出現過（例如
sds,
quicklist,
skiplist），用于表達一個偏移量。contents 需要單獨為其分配空間，這部分內存不包含在 intset 結構當中。
其中需要注意的是，intset 可能會隨著數據的添加而改變它的數據編碼：
最開始，新創建的 intset 使用占內存最小的 INTSET_ENC_INT16（值為 2）作為數據編碼。
每添加一個新元素，則根據元素大小決定是否對數據編碼進行升級。
下圖給出了一個添加數據的具體例子（點擊看大圖）。
在上圖中：
新創建的 intset 只有一個 header，總共 8 個字節。其中 encoding = 2,
length = 0。
添加 13, 5 兩個元素之后，因為它們是比較小的整數，都能使用 2 個字節表示，所以 encoding 不變，值還是 2。
當添加 32768 的時候，它不再能用 2 個字節來表示了（2 個字節能表達的數據范圍是 -215~215-1，而 32768 等于 215，超出范圍了），因此 encoding 必須升級到 INTSET_ENC_INT32（值為 4），即用 4 個字節表示一個元素。
在添加每個元素的過程中，intset 始終保持從小到大有序。
與
ziplist 類似，intset 也是按小端（little endian）模式存儲的（參見維基百科詞條
Endianness）。比如，在上圖中 intset 添加完所有數據之后，表示 encoding 字段的 4 個字節應該解釋成 0x00000004，而第 5 個數據應該解釋成 0x000186A0 = 100000。
intset 與
ziplist 相比：
ziplist 可以存儲任意二進制串，而 intset 只能存儲整數。
ziplist 是無序的，而 intset 是從小到大有序的。因此，在 ziplist 上查找只能遍歷，而在 intset 上可以進行二分查找，性能更高。
ziplist 可以對每個數據項進行不同的變長編碼（每個數據項前面都有數據長度字段 len），而 intset 只能整體使用一個統一的編碼（encoding）。
intset 的查找和添加操作
要理解 intset 的一些實現細節，只需要關注 intset 的兩個關鍵操作基本就可以了：查找（intsetFind）和添加（intsetAdd）元素。
intsetFind 的關鍵代碼如下所示（出自 intset.c）：
uint8_t intsetFind(intset *is, int64_t value) { uint8_t valenc = _intsetValueEncoding(value);
return valenc = intrev32ifbe(is- encoding) intsetSearch(is,value,NULL);
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;
/* The value can never be found when the set is empty */
if (intrev32ifbe(is- length) == 0) { if (pos) *pos = 0;
return 0;
} else {
/* Check for the case where we know we cannot find the value,
* but do know the insert position. */
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;
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;
return 1;
} else { if (pos) *pos = min;
return 0;
}
}關于以上代碼，我們需要注意的地方包括：
intsetFind 在指定的 intset 中查找指定的元素 value，找到返回 1，沒找到返回 0。
_intsetValueEncoding 函數會根據要查找的 value 落在哪個范圍而計算出相應的數據編碼（即它應該用幾個字節來存儲）。
如果 value 所需的數據編碼比當前 intset 的編碼要大，則它肯定在當前 intset 所能存儲的數據范圍之外（特別大或特別小），所以這時會直接返回 0；否則調用 intsetSearch 執行一個二分查找算法。
intsetSearch 在指定的 intset 中查找指定的元素 value，如果找到，則返回 1 并且將參數 pos 指向找到的元素位置；如果沒找到，則返回 0 并且將參數 pos 指向能插入該元素的位置。
intsetSearch 是對于二分查找算法的一個實現，它大致分為三個部分：
特殊處理 intset 為空的情況。
特殊處理兩個邊界情況：當要查找的 value 比最后一個元素還要大或者比第一個元素還要小的時候。實際上，這兩部分的特殊處理，在二分查找中并不是必須的，但它們在這里提供了特殊情況下快速失敗的可能。
真正執行二分查找過程。注意：如果最后沒找到，插入位置在 min 指定的位置。
代碼中出現的 intrev32ifbe 是為了在需要的時候做大小端轉換的。前面我們提到過，intset 里的數據是按小端（little endian）模式存儲的，因此在大端（big endian）機器上運行時，這里的 intrev32ifbe 會做相應的轉換。
這個查找算法的總的時間復雜度為 O(log n)。
而 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;
/* Upgrade encoding if necessary. If we need to upgrade, we know that
* this value should be either appended (if 0) or prepended (if 0),
* because it lies outside the range of existing values. */
if (valenc intrev32ifbe(is- encoding)) {
/* This always succeeds, so we don t need to curry *success. */
return intsetUpgradeAndAdd(is,value);
} else {
/* Abort if the value is already present in the set.
* This call will populate pos with the right position to insert
* the value when it cannot be found. */
if (intsetSearch(is,value, pos)) { if (success) *success = 0;
return is;
}
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;
}關于以上代碼，我們需要注意的地方包括：
intsetAdd 在 intset 中添加新元素 value。如果 value 在添加前已經存在，則不會重復添加，這時參數 success 被置為 0；如果 value 在原來 intset 中不存在，則將 value 插入到適當位置，這時參數 success 被置為 0。
如果要添加的元素 value 所需的數據編碼比當前 intset 的編碼要大，那么則調用 intsetUpgradeAndAdd 將 intset 的編碼進行升級后再插入 value。
調用 intsetSearch，如果能查到，則不會重復添加。
如果沒查到，則調用 intsetResize 對 intset 進行內存擴充，使得它能夠容納新添加的元素。因為 intset 是一塊連續空間，因此這個操作會引發內存的 realloc（參見
http://man.cx/realloc）。這有可能帶來一次數據拷貝。同時調用 intsetMoveTail 將待插入位置后面的元素統一向后移動 1 個位置，這也涉及到一次數據拷貝。值得注意的是，在 intsetMoveTail 中是調用 memmove 完成這次數據拷貝的。memmove 保證了在拷貝過程中不會造成數據重疊或覆蓋，具體參見
http://man.cx/memmove。
intsetUpgradeAndAdd 的實現中也會調用 intsetResize 來完成內存擴充。在進行編碼升級時，intsetUpgradeAndAdd 的實現會把原來 intset 中的每個元素取出來，再用新的編碼重新寫入新的位置。
注意一下 intsetAdd 的返回值，它返回一個新的 intset 指針。它可能與傳入的 intset 指針 is 相同，也可能不同。調用方必須用這里返回的新的 intset，替換之前傳進來的舊的 intset 變量。類似這種接口使用模式，在 Redis 的實現代碼中是很常見的，比如我們之前在介紹
ziplist 的時候都碰到過類似的情況。
顯然，這個 intsetAdd 算法總的時間復雜度為 O(n)。
Redis 的 set
為了更好地理解 Redis 對外暴露的 set 數據結構，我們先看一下 set 的一些關鍵的命令。下面是一些命令舉例：
上面這些命令的含義：
sadd 用于分別向集合 s1 和 s2 中添加元素。添加的元素既有數字，也有非數字（”a”和”b”）。
sismember 用于判斷指定的元素是否在集合內存在。
sinter,
sunion 和 sdiff 分別用于計算集合的交集、并集和差集。
我們前面提到過，set 的底層實現，隨著元素類型是否是整型以及添加的元素的數目多少，而有所變化。例如，具體到上述命令的執行過程中，集合 s1 的底層數據結構會發生如下變化：
在開始執行完 sadd s1 13 5 之后，由于添加的都是比較小的整數，所以 s1 底層是一個 intset，其數據編碼 encoding = 2。
在執行完 sadd s1 32768 10 100000 之后，s1 底層仍然是一個 intset，但其數據編碼 encoding 從 2 升級到了 4。
在執行完 sadd s1 a b 之后，由于添加的元素不再是數字，s1 底層的實現會轉成一個 dict。
我們知道，dict 是一個用于維護 key 和 value 映射關系的數據結構，那么當 set 底層用 dict 表示的時候，它的 key 和 value 分別是什么呢？實際上，key 就是要添加的集合元素，而 value 是 NULL。
除了前面提到的由于添加非數字元素造成集合底層由 intset 轉成 dict 之外，還有兩種情況可能造成這種轉換：
添加了一個數字，但它無法用 64bit 的有符號數來表達。intset 能夠表達的最大的整數范圍為 -264~264-1，因此，如果添加的數字超出了這個范圍，這也會導致 intset 轉成 dict。
添加的集合元素個數超過了 set-max-intset-entries 配置的值的時候，也會導致 intset 轉成 dict（具體的觸發條件參見 t_set.c 中的 setTypeAdd 相關代碼）。
對于小集合使用 intset 來存儲，主要的原因是節省內存。特別是當存儲的元素個數較少的時候，dict 所帶來的內存開銷要大得多（包含兩個哈希表、鏈表指針以及大量的其它元數據）。所以，當存儲大量的小集合而且集合元素都是數字的時候，用 intset 能節省下一筆可觀的內存空間。
實際上，從時間復雜度上比較，intset 的平均情況是沒有 dict 性能高的。以查找為例，intset 是 O(log n) 的，而 dict 可以認為是 O(1) 的。但是，由于使用 intset 的時候集合元素個數比較少，所以這個影響不大。
Redis set 的并、交、差算法
Redis set 的并、交、差算法的實現代碼，在 t_set.c 中。其中計算交集調用的是 sinterGenericCommand，計算并集和差集調用的是 sunionDiffGenericCommand。它們都能同時對多個（可以多于 2 個）集合進行運算。當對多個集合進行差集運算時，它表達的含義是：用第一個集合與第二個集合做差集，所得結果再與第三個集合做差集，依次向后類推。
我們在這里簡要介紹一下三個算法的實現思路。
交集
計算交集的過程大概可以分為三部分：
檢查各個集合，對于不存在的集合當做空集來處理。一旦出現空集，則不用繼續計算了，最終的交集就是空集。
對各個集合按照元素個數由少到多進行排序。這個排序有利于后面計算的時候從最小的集合開始，需要處理的元素個數較少。
對排序后第一個集合（也就是最小集合）進行遍歷，對于它的每一個元素，依次在后面的所有集合中進行查找。只有在所有集合中都能找到的元素，才加入到最后的結果集合中。
需要注意的是，上述第 3 步在集合中進行查找，對于 intset 和 dict 的存儲來說時間復雜度分別是 O(log n) 和 O(1)。但由于只有小集合才使用 intset，所以可以粗略地認為 intset 的查找也是常數時間復雜度的。因此，如 Redis 官方文檔上所說（
http://redis.io/commands/sinter），sinter 命令的時間復雜度為：
O(N*M) worst case where N is the cardinality of the smallest set and M is the number of sets.
并集
計算并集最簡單，只需要遍歷所有集合，將每一個元素都添加到最后的結果集合中。向集合中添加元素會自動去重。
由于要遍歷所有集合的每個元素，所以 Redis 官方文檔給出的 sunion 命令的時間復雜度為（
http://redis.io/commands/sunion）：
O(N) where N is the total number of elements in all given sets.
注意，這里同前面討論交集計算一樣，將元素插入到結果集合的過程，忽略 intset 的情況，認為時間復雜度為 O(1)。
差集
計算差集有兩種可能的算法，它們的時間復雜度有所區別。
第一種算法：
對第一個集合進行遍歷，對于它的每一個元素，依次在后面的所有集合中進行查找。只有在所有集合中都找不到的元素，才加入到最后的結果集合中。
這種算法的時間復雜度為 O(N*M)，其中 N 是第一個集合的元素個數，M 是集合數目。
第二種算法：
將第一個集合的所有元素都加入到一個中間集合中。
遍歷后面所有的集合，對于碰到的每一個元素，從中間集合中刪掉它。
最后中間集合剩下的元素就構成了差集。
這種算法的時間復雜度為 O(N)，其中 N 是所有集合的元素個數總和。
在計算差集的開始部分，會先分別估算一下兩種算法預期的時間復雜度，然后選擇復雜度低的算法來進行運算。還有兩點需要注意：
在一定程度上優先選擇第一種算法，因為它涉及到的操作比較少，只用添加，而第二種算法要先添加再刪除。
如果選擇了第一種算法，那么在執行該算法之前，Redis 的實現中對于第二個集合之后的所有集合，按照元素個數由多到少進行了排序。這個排序有利于以更大的概率查找到元素，從而更快地結束查找。
上述內容就是 Redis 中內部數據結構 intset 的作用是什么，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注丸趣 TV 行業資訊頻道。
