整數集合 · Redis 設計與實現（第一版）

# 整數集合 [TOC=2,3] 整數集合（intset）用于有序、無重復地保存多個整數值，根據元素的值，自動選擇該用什么長度的整數類型來保存元素。舉個例子，如果在一個 intset 里面，最長的元素可以用 `int16_t` 類型來保存，那么這個 intset 的所有元素都以 `int16_t` 類型來保存。另一方面，如果有一個新元素要加入到這個 intset ，并且這個元素不能用 `int16_t` 類型來保存 ——比如說，新元素的長度為 `int32_t` ，那么這個 intset 就會自動進行“升級”：先將集合中現有的所有元素從 `int16_t` 類型轉換為 `int32_t` 類型，接著再將新元素加入到集合中。根據需要，intset 可以自動從 `int16_t` 升級到 `int32_t` 或 `int64_t` ，或者從 `int32_t` 升級到 `int64_t` 。 ### 整數集合的應用 Intset 是集合鍵的底層實現之一，如果一個集合： 1. 只保存著整數元素； 1. 元素的數量不多；那么 Redis 就會使用 intset 來保存集合元素。具體的信息請參考《[集合](#)》。 ### 數據結構和主要操作以下是 `intset.h/intset` 類型的定義： ~~~ typedef struct intset { // 保存元素所使用的類型的長度 uint32_t encoding; // 元素個數 uint32_t length; // 保存元素的數組 int8_t contents[]; } intset; ~~~ `encoding` 的值可以是以下三個常量之一（定義位于 `intset.c` ）： ~~~ #define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t)) ~~~ `contents` 數組是實際保存元素的地方，數組中的元素有以下兩個特性： - 元素不重復； - 元素在數組中由小到大排列； `contents` 數組的 `int8_t` 類型聲明比較容易讓人誤解，實際上， `intset` 并不使用 `int8_t` 類型來保存任何元素，結構中的這個類型聲明只是作為一個占位符使用：在對 `contents` 中的元素進行讀取或者寫入時，程序并不是直接使用 `contents` 來對元素進行索引，而是根據 `encoding` 的值，對 `contents` 進行類型轉換和指針運算，計算出元素在內存中的正確位置。在添加新元素，進行內存分配時，分配的空間也是由 `encoding` 的值決定。下表列出了處理 `intset` 的一些主要操作，以及這些操作的算法復雜度： | 操作 | 函數 | 復雜度 | |-----|-----|-----| | 創建 intset | `intsetNew` | \(\theta(1)\) | | 刪除 intset | 無 | 無 | | 添加新元素（不升級） | `intsetAdd` | \(O(N)\) | | 添加新元素（升級） | `intsetUpgradeAndAdd` | \(O(N)\) | | 按索引獲取元素 | `_intsetGet` | \(\theta(1)\) | | 按索引設置元素 | `_intsetSet` | \(\theta(1)\) | | 查找元素，返回索引 | `intsetSearch` | \(O(\lg N)\) | | 刪除元素 | `intsetRemove` | \(O(N)\) | ### intset 運行實例讓我們跟蹤一個 `intset` 的創建和添加過程，借此了解 `intset` 的運作方式。 ### 創建新 intset `intset.c/intsetNew` 函數創建一個新的 `intset` ，并設置初始化值： ~~~ intset *is = intsetNew(); // intset->encoding = INTSET_ENC_INT16; // intset->length 0; // intset->contents = []; ~~~ 注意 `encoding` 使用 `INTSET_ENC_INT16` 作為初始值。 ### 添加新元素到 intset 創建 `intset` 之后，就可以對它添加新元素了。添加新元素到 `intset` 的工作由 `intset.c/intsetAdd` 函數完成，需要處理以下三種情況： 1. 元素已存在于集合，不做動作； 1. 元素不存在于集合，并且添加新元素并不需要升級； 1. 元素不存在于集合，但是要在升級之后，才能添加新元素；并且， `intsetAdd` 需要維持 `intset->contents` 的以下性質： 1. 確保數組中沒有重復元素； 1. 確保數組中的元素按由小到大排序；整個 `intsetAdd` 的執行流程可以表示為下圖： ![digraph intsetAdd { node [shape=plaintext, style = filled]; edge [style = bold]; start [label="intsetAdd", fillcolor = "#A8E270"]; check_encoding [label="集合當前的編碼類型\n是否適用于新元素？", shape = diamond, fillcolor = "#95BBE3"]; start -> check_encoding; upgrade [label="調用\n intsetUpgradeAndAdd\n升級集合\n并將新元素\n添加到升級后的集合中"]; check_encoding -> upgrade [label="不適用"]; value_exists [label="元素已經存在于集合？", shape = diamond, fillcolor = "#95BBE3"]; check_encoding -> value_exists [label="適用"]; insert_fail [label="添加失敗，元素已存在"]; realloc_and_move [label="為新元素分配內存\n并對 contents 數組中現有的元素進行移動，\n確保新元素會被放到有序數組正確的位置上"]; value_exists -> insert_fail [label="是"]; value_exists -> realloc_and_move [label="否"]; done [label="將新元素的值保存到 contents 數組中\n更新 length 計數器"]; realloc_and_move -> done;}](https://box.kancloud.cn/2015-09-13_55f4effc1c540.svg) 以下兩個小節分別演示添加操作在升級和不升級兩種情況下的執行過程。 ### 添加新元素到 intset （不需要升級）如果 intset 現有的編碼方式適用于新元素，則可直接將新元素添加到 intset ，無須對 intset 進行升級。以下代碼演示了將三個 `int16_t` 類型的整數添加到集合的過程，以及在添加過程中，集合的狀態： ~~~ intset *is = intsetNew(); intsetAdd(is, 10, NULL); // is->encoding = INTSET_ENC_INT16; // is->length = 1; // is->contents = [10]; intsetAdd(is, 5, NULL); // is->encoding = INTSET_ENC_INT16; // is->length = 2; // is->contents = [5, 10]; intsetAdd(is, 12, NULL); // is->encoding = INTSET_ENC_INT16; // is->length = 3; // is->contents = [5, 10, 12] ~~~ 因為添加的三個元素都可以表示為 `int16_t` ，因此 `is->encoding` 一直都是 `INTSET_ENC_INT16` 。另一方面， `is->length` 和 `is->contents` 的值，則隨著新元素的加入而被修改。 ### 添加新元素到 intset （需要升級）當要添加新元素到 intset ，并且 intset 當前的編碼，不適用于新元素的編碼時，就需要對 intset 進行升級。以下代碼演示了帶升級的添加操作的執行過程： ~~~ intset *is = intsetNew(); intsetAdd(is, 1, NULL); // is->encoding = INTSET_ENC_INT16; // is->length = 1; // is->contents = [1]; // 所有值使用 int16_t 保存 intsetAdd(is, 65535, NULL); // is->encoding = INTSET_ENC_INT32; // 升級 // is->length = 2; // is->contents = [1, 65535]; // 所有值使用 int32_t 保存 intsetAdd(is, 70000, NULL); // is->encoding = INTSET_ENC_INT32; // is->length = 3; // is->contents = [1, 65535, 70000]; intsetAdd(is, 4294967295, NULL); // is->encoding = INTSET_ENC_INT64; // 升級 // is->length = 4; // is->contents = [1, 65535, 70000, 4294967295]; // 所有值使用 int64_t 保存 ~~~ 在添加 `65535` 和 `4294967295` 之后，`encoding` 屬性的值，以及 `contents` 數組保存值的方式，都被改變了。 ### 升級添加新元素時，如果 `intsetAdd` 發現新元素，不能用現有的編碼方式來保存，便會將升級集合和添加新元素的任務轉交給 `intsetUpgradeAndAdd` 來完成： ![digraph g { edge [style = bold]; node [shape = plaintext, style = filled]; add [label = "添加新元素到 intset", fillcolor = "#A8E270"]; upgrade_or_not [label = "intset 需要升級？", shape = diamond, fillcolor = "#95BBE3"]; add -> upgrade_or_not; upgrade_or_not -> intsetAdd [label = "不需要"]; upgrade_or_not -> intsetUpgradeAndAdd [label = "需要"];}](https://box.kancloud.cn/2015-09-13_55f4effc250eb.svg) `intsetUpgradeAndAdd` 需要完成以下幾個任務： 1. 對新元素進行檢測，看保存這個新元素需要什么類型的編碼； 1. 將集合 `encoding` 屬性的值設置為新編碼類型，并根據新編碼類型，對整個 `contents` 數組進行內存重分配。 1. 調整 `contents` 數組內原有元素在內存中的排列方式，從舊編碼調整為新編碼。 1. 將新元素添加到集合中。整個過程中，最復雜的就是第三步，讓我們用一個例子來理解這個步驟。 ### 升級實例假設有一個 `intset` ，里面有三個用 `int16_t` 方式保存的數值，分別是 `1` 、 `2` 和 `3` ，結構如下： ~~~ intset->encoding = INTSET_ENC_INT16; intset->length = 3; intset->contents = [1, 2, 3]; ~~~ 其中， `intset->contents` 在內存中的排列如下： ~~~ bit 0 15 31 47 value | 1 | 2 | 3 | ~~~ 現在，我們將一個長度為 `int32_t` 的值 `65535` 加入到集合中， `intset` 需要執行以下步驟： 1. 將 `encoding` 屬性設置為 `INTSET_ENC_INT32` 。 1. 根據 `encoding` 屬性的值，對 `contents` 數組進行內存重分配。重分配完成之后， `contents` 在內存中的排列如下： ~~~ bit 0 15 31 47 63 95 127 value | 1 | 2 | 3 | ? | ? | ? | ~~~ `contents` 數組現在共有可容納 4 個 `int32_t` 值的空間。 1. 因為原來的 3 個 `int16_t` 值還“擠在” `contents` 前面的 48 個位里，所以程序需要移動它們并轉換類型，讓它們適應集合的新編碼方式。首先是移動 `3` ： ~~~ bit 0 15 31 47 63 95 127 value | 1 | 2 | 3 | ? | 3 | ? | | ^ | | +-------------+ int16_t -> int32_t ~~~ 接著移動 `2` ： ~~~ bit 0 15 31 47 63 95 127 value | 1 | 2 | 2 | 3 | ? | | ^ | | +-------+ int16_t -> int32_t ~~~ 最后，移動 `1` ： ~~~ bit 0 15 31 47 63 95 127 value | 1 | 2 | 3 | ? | | ^ V | int16_t -> int32_t ~~~ 1. 最后，將新值 65535 添加到數組： ~~~ bit 0 15 31 47 63 95 127 value | 1 | 2 | 3 | 65535 | ^ | add ~~~ 將 `intset->length` 設置為 `4` 。至此，集合的升級和添加操作完成，現在的 `intset` 結構如下： ~~~ intset->encoding = INTSET_ENC_INT32; intset->length = 4; intset->contents = [1, 2, 3, 65535]; ~~~ ### 關于升級關于升級操作，有兩點需要提醒一下： ### 第一，從較短整數到較長整數的轉換，并不會更改元素里面的值。在 C 語言中，從長度較短的帶符號整數到長度較長的帶符號整數之間的轉換（比如從 `int16_t` 轉換為 `int32_t` ）總是可行的（不會溢出）、無損的。另一方面，從較長整數到較短整數之間的轉換，可能是有損的（比如從 `int32_t` 轉換為 `int16_t` ）。因為 intset 只進行從較短整數到較長整數的轉換（也即是，只“升級”，不“降級”），因此，“升級”操作并不會修改元素原有的值。 ### 第二，集合編碼元素的方式，由元素中長度最大的那個值來決定。就像前面演示的例子一樣，當要將一個 `int32_t` 編碼的新元素添加到集合時，集合原有的所有 `int16_t` 編碼的元素，都必須轉換為 `int32_t` 。盡管這個集合真正需要用 `int32_t` 長度來保存的元素只有一個，但整個集合的所有元素都必須轉換為這種類型。 ### 關于元素移動在進行升級的過程中，需要對數組內的元素進行“類型轉換”和“移動”操作。其中，移動不僅出現在升級（`intsetUpgradeAndAdd`）操作中，還出現其他對 `contents` 數組內容進行增刪的操作上，比如 `intsetAdd` 和 `intsetRemove` ，因為這種移動操作需要處理 intset 中的所有元素，所以這些函數的復雜度都不低于 \(O(N)\) 。 ### 其他操作以下是一些關于 intset 其他操作的討論。 ### 讀取有兩種方式讀取 `intset` 的元素，一種是 `_intsetGet` ，另一種是 `intsetSearch` ： - `_intsetGet` 接受一個給定的索引 `pos` ，并根據 `intset->encoding` 的值進行指針運算，計算出給定索引在 `intset->contents` 數組上的值。 - `intsetSearch` 則使用[二分查找](http://en.wikipedia.org/wiki/Binary_search_algorithm) [http://en.wikipedia.org/wiki/Binary_search_algorithm]算法，判斷一個給定元素在 `contents` 數組上的索引。 ### 寫入除了前面介紹過的 `intsetAdd` 和 `intsetUpgradeAndAdd` 之外， `_intsetSet` 也對集合進行寫入操作：它接受一個索引 `pos` ，以及一個 `new_value` ，將 `contents` 數組 `pos` 位置的值設為 `new_value` 。 ### 刪除刪除單個元素的工作由 `intsetRemove` 操作，它先調用 `intsetSearch` 找到需要被刪除的元素在 `contents` 數組中的索引，然后使用內存移位操作，將目標元素從內存中抹去，最后，通過內存重分配，對 `contents` 數組的長度進行調整。 ### 降級 Intset 不支持降級操作。 Intset 定位為一種受限的中間表示，只能保存整數值，而且元素的個數也不能超過 `redis.h/REDIS_SET_MAX_INTSET_ENTRIES` （目前版本值為 `512` ）這些條件決定了它被保存的時間不會太長，因此沒有必要進行太復雜的操作，當然，如果內存確實十分緊張的話，給 intset 添加降級功能也是可以實現的，不過這可能會讓 `intset` 的代碼增長一倍。 ### 小結 - Intset 用于有序、無重復地保存多個整數值，會根據元素的值，自動選擇該用什么長度的整數類型來保存元素。 - 當一個位長度更長的整數值添加到 intset 時，需要對 intset 進行升級，新 intset 中每個元素的位長度，會等于新添加值的位長度，但原有元素的值不變。 - 升級會引起整個 intset 進行內存重分配，并移動集合中的所有元素，這個操作的復雜度為 \(O(N)\) 。 - Intset 只支持升級，不支持降級。 - Intset 是有序的，程序使用二分查找算法來實現查找操作，復雜度為 \(O(\lg N)\) 。