Redis 整數(shù)集合

整數(shù)集合

整數(shù)集合（intset）用于有序、無重復(fù)地保存多個(gè)整數(shù)值，根據(jù)元素的值，自動(dòng)選擇該用什么長度的整數(shù)類型來保存元素。

舉個(gè)例子，如果在一個(gè) intset 里面，最長的元素可以用 int16_t 類型來保存，那么這個(gè) intset 的所有元素都以 int16_t 類型來保存。

另一方面，如果有一個(gè)新元素要加入到這個(gè) intset ，并且這個(gè)元素不能用 int16_t 類型來保存 ——比如說，新元素的長度為 int32_t ，那么這個(gè) intset 就會(huì)自動(dòng)進(jìn)行“升級(jí)”：先將集合中現(xiàn)有的所有元素從 int16_t 類型轉(zhuǎn)換為 int32_t 類型，接著再將新元素加入到集合中。

根據(jù)需要，intset 可以自動(dòng)從 int16_t 升級(jí)到 int32_t 或 int64_t ，或者從 int32_t 升級(jí)到 int64_t 。

整數(shù)集合的應(yīng)用

Intset 是集合鍵的底層實(shí)現(xiàn)之一，如果一個(gè)集合：

1. 只保存著整數(shù)元素；
2. 元素的數(shù)量不多；

那么 Redis 就會(huì)使用 intset 來保存集合元素。

具體的信息請參考《集合》。

數(shù)據(jù)結(jié)構(gòu)和主要操作

以下是 intset.h/intset 類型的定義：

typedef struct intset {

    // 保存元素所使用的類型的長度
    uint32_t encoding;

    // 元素個(gè)數(shù)
    uint32_t length;

    // 保存元素的數(shù)組
    int8_t contents[];

} intset;

encoding 的值可以是以下三個(gè)常量之一（定義位于 intset.c ）：

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

contents 數(shù)組是實(shí)際保存元素的地方，數(shù)組中的元素有以下兩個(gè)特性：

• 元素不重復(fù)；
• 元素在數(shù)組中由小到大排列；

contents 數(shù)組的 int8_t 類型聲明比較容易讓人誤解，實(shí)際上， intset 并不使用 int8_t 類型來保存任何元素，結(jié)構(gòu)中的這個(gè)類型聲明只是作為一個(gè)占位符使用：在對(duì) contents 中的元素進(jìn)行讀取或者寫入時(shí)，程序并不是直接使用 contents 來對(duì)元素進(jìn)行索引，而是根據(jù) encoding 的值，對(duì) contents 進(jìn)行類型轉(zhuǎn)換和指針運(yùn)算，計(jì)算出元素在內(nèi)存中的正確位置。在添加新元素，進(jìn)行內(nèi)存分配時(shí)，分配的空間也是由 encoding 的值決定。

下表列出了處理 intset 的一些主要操作，以及這些操作的算法復(fù)雜度：

intset 運(yùn)行實(shí)例

讓我們跟蹤一個(gè) intset 的創(chuàng)建和添加過程，借此了解 intset 的運(yùn)作方式。

創(chuàng)建新 intset

intset.c/intsetNew 函數(shù)創(chuàng)建一個(gè)新的 intset ，并設(shè)置初始化值：

intset *is = intsetNew();

// intset->encoding = INTSET_ENC_INT16;
// intset->length 0;
// intset->contents = [];

注意 encoding 使用 INTSET_ENC_INT16 作為初始值。

添加新元素到 intset

創(chuàng)建 intset 之后，就可以對(duì)它添加新元素了。

添加新元素到 intset 的工作由 intset.c/intsetAdd 函數(shù)完成，需要處理以下三種情況：

1. 元素已存在于集合，不做動(dòng)作；
2. 元素不存在于集合，并且添加新元素并不需要升級(jí)；
3. 元素不存在于集合，但是要在升級(jí)之后，才能添加新元素；

并且， intsetAdd 需要維持 intset->contents 的以下性質(zhì)：

1. 確保數(shù)組中沒有重復(fù)元素；
2. 確保數(shù)組中的元素按由小到大排序；

整個(gè) intsetAdd 的執(zhí)行流程可以表示為下圖：

check_encoding; upgrade [label="調(diào)用\n intsetUpgradeAndAdd\n升級(jí)集合\n并將新元素\n添加到升級(jí)后的集合中"]; check_encoding -> upgrade [label="不適用"]; value_exists [label="元素已經(jīng)存在于集合？", shape = diamond, fillcolor = "#95BBE3"]; check_encoding -> value_exists [label="適用"]; insert_fail [label="添加失敗，元素已存在"]; realloc_and_move [label="為新元素分配內(nèi)存\n并對(duì) contents 數(shù)組中現(xiàn)有的元素進(jìn)行移動(dòng)，\n確保新元素會(huì)被放到有序數(shù)組正確的位置上"]; value_exists -> insert_fail [label="是"]; value_exists -> realloc_and_move [label="否"]; done [label="將新元素的值保存到 contents 數(shù)組中\(zhòng)n更新 length 計(jì)數(shù)器"]; realloc_and_move -> done;}" />

以下兩個(gè)小節(jié)分別演示添加操作在升級(jí)和不升級(jí)兩種情況下的執(zhí)行過程。

添加新元素到 intset （不需要升級(jí)）

如果 intset 現(xiàn)有的編碼方式適用于新元素，則可直接將新元素添加到 intset ，無須對(duì) intset 進(jìn)行升級(jí)。

以下代碼演示了將三個(gè) int16_t 類型的整數(shù)添加到集合的過程，以及在添加過程中，集合的狀態(tài)：

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]

因?yàn)樘砑拥娜齻€(gè)元素都可以表示為 int16_t ，因此 is->encoding 一直都是 INTSET_ENC_INT16 。

另一方面， is->length 和 is->contents 的值，則隨著新元素的加入而被修改。

添加新元素到 intset （需要升級(jí)）

當(dāng)要添加新元素到 intset ，并且 intset 當(dāng)前的編碼，不適用于新元素的編碼時(shí)，就需要對(duì) intset 進(jìn)行升級(jí)。

以下代碼演示了帶升級(jí)的添加操作的執(zhí)行過程：

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;     // 升級(jí)
// 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;                 // 升級(jí)
// is->length = 4;
// is->contents = [1, 65535, 70000, 4294967295];    // 所有值使用 int64_t 保存

在添加 65535 和 4294967295 之后，encoding 屬性的值，以及 contents 數(shù)組保存值的方式，都被改變了。

升級(jí)

添加新元素時(shí)，如果 intsetAdd 發(fā)現(xiàn)新元素，不能用現(xiàn)有的編碼方式來保存，便會(huì)將升級(jí)集合和添加新元素的任務(wù)轉(zhuǎn)交給 intsetUpgradeAndAdd 來完成：

upgrade_or_not; upgrade_or_not -> intsetAdd [label = "不需要"]; upgrade_or_not -> intsetUpgradeAndAdd [label = "需要"];}" />

intsetUpgradeAndAdd 需要完成以下幾個(gè)任務(wù)：

1. 對(duì)新元素進(jìn)行檢測，看保存這個(gè)新元素需要什么類型的編碼；
2. 將集合 encoding 屬性的值設(shè)置為新編碼類型，并根據(jù)新編碼類型，對(duì)整個(gè) contents 數(shù)組進(jìn)行內(nèi)存重分配。
3. 調(diào)整 contents 數(shù)組內(nèi)原有元素在內(nèi)存中的排列方式，從舊編碼調(diào)整為新編碼。
4. 將新元素添加到集合中。

整個(gè)過程中，最復(fù)雜的就是第三步，讓我們用一個(gè)例子來理解這個(gè)步驟。

升級(jí)實(shí)例

假設(shè)有一個(gè) intset ，里面有三個(gè)用 int16_t 方式保存的數(shù)值，分別是 1 、 2 和 3 ，結(jié)構(gòu)如下：

intset->encoding = INTSET_ENC_INT16;
intset->length = 3;
intset->contents = [1, 2, 3];

其中， intset->contents 在內(nèi)存中的排列如下：

bit     0    15    31    47
value   |  1  |  2  |  3  |

現(xiàn)在，我們將一個(gè)長度為 int32_t 的值 65535 加入到集合中， intset 需要執(zhí)行以下步驟：

1. 將 encoding 屬性設(shè)置為 INTSET_ENC_INT32 。

2. 根據(jù) encoding 屬性的值，對(duì) contents 數(shù)組進(jìn)行內(nèi)存重分配。

重分配完成之后， contents 在內(nèi)存中的排列如下：

bit     0    15    31    47     63        95       127
value   |  1  |  2  |  3  |  ?  |    ?    |    ?    |

contents 數(shù)組現(xiàn)在共有可容納 4 個(gè) int32_t 值的空間。

1. 因?yàn)樵瓉淼?3 個(gè) int16_t 值還“擠在” contents 前面的 48 個(gè)位里， 所以程序需要移動(dòng)它們并轉(zhuǎn)換類型， 讓它們適應(yīng)集合的新編碼方式。

首先是移動(dòng) 3 ：

bit     0    15    31    47     63        95       127
value   |  1  |  2  |  3  |  ?  |    3    |    ?    |
                       |             ^
                       |             |
                       +-------------+
                     int16_t -> int32_t

接著移動(dòng) 2 ：

bit     0    15    31   47     63        95       127
value   |  1  |  2  |    2     |    3    |    ?    |
                 |       ^
                 |       |
                 +-------+
            int16_t -> int32_t

最后，移動(dòng) 1 ：

bit     0   15    31   47     63        95       127
value   |    1     |    2     |    3    |    ?    |
            | ^
            V |
    int16_t -> int32_t

1. 最后，將新值 65535 添加到數(shù)組：

bit     0   15    31   47     63        95       127
value   |    1     |    2     |    3    |  65535  |
                                             ^
                                             |
                                            add

將 intset->length 設(shè)置為 4 。

至此，集合的升級(jí)和添加操作完成，現(xiàn)在的 intset 結(jié)構(gòu)如下：

intset->encoding = INTSET_ENC_INT32;
intset->length = 4;
intset->contents = [1, 2, 3, 65535];

關(guān)于升級(jí)

關(guān)于升級(jí)操作，有兩點(diǎn)需要提醒一下：

第一，從較短整數(shù)到較長整數(shù)的轉(zhuǎn)換，并不會(huì)更改元素里面的值。

在 C 語言中，從長度較短的帶符號(hào)整數(shù)到長度較長的帶符號(hào)整數(shù)之間的轉(zhuǎn)換（比如從 int16_t 轉(zhuǎn)換為 int32_t ）總是可行的（不會(huì)溢出）、無損的。

另一方面，從較長整數(shù)到較短整數(shù)之間的轉(zhuǎn)換，可能是有損的（比如從 int32_t 轉(zhuǎn)換為 int16_t ）。

因?yàn)?intset 只進(jìn)行從較短整數(shù)到較長整數(shù)的轉(zhuǎn)換（也即是，只“升級(jí)”，不“降級(jí)”），因此，“升級(jí)”操作并不會(huì)修改元素原有的值。

第二，集合編碼元素的方式，由元素中長度最大的那個(gè)值來決定。

就像前面演示的例子一樣，當(dāng)要將一個(gè) int32_t 編碼的新元素添加到集合時(shí)，集合原有的所有 int16_t 編碼的元素，都必須轉(zhuǎn)換為 int32_t 。

盡管這個(gè)集合真正需要用 int32_t 長度來保存的元素只有一個(gè)，但整個(gè)集合的所有元素都必須轉(zhuǎn)換為這種類型。

關(guān)于元素移動(dòng)

在進(jìn)行升級(jí)的過程中，需要對(duì)數(shù)組內(nèi)的元素進(jìn)行“類型轉(zhuǎn)換”和“移動(dòng)”操作。

其中，移動(dòng)不僅出現(xiàn)在升級(jí)（intsetUpgradeAndAdd）操作中，還出現(xiàn)其他對(duì) contents 數(shù)組內(nèi)容進(jìn)行增刪的操作上，比如 intsetAdd 和 intsetRemove ，因?yàn)檫@種移動(dòng)操作需要處理 intset 中的所有元素，所以這些函數(shù)的復(fù)雜度都不低于 (O(N)) 。

其他操作

以下是一些關(guān)于 intset 其他操作的討論。

讀取

有兩種方式讀取 intset 的元素，一種是 _intsetGet ，另一種是 intsetSearch ：

• _intsetGet 接受一個(gè)給定的索引 pos ，并根據(jù) intset->encoding 的值進(jìn)行指針運(yùn)算，計(jì)算出給定索引在 intset->contents 數(shù)組上的值。
• intsetSearch 則使用二分查找 [http://en.wikipedia.org/wiki/Binary_search_algorithm]算法，判斷一個(gè)給定元素在 contents 數(shù)組上的索引。

寫入

除了前面介紹過的 intsetAdd 和 intsetUpgradeAndAdd 之外， _intsetSet 也對(duì)集合進(jìn)行寫入操作：它接受一個(gè)索引 pos ，以及一個(gè) new_value ，將 contents 數(shù)組 pos 位置的值設(shè)為 new_value 。

刪除

刪除單個(gè)元素的工作由 intsetRemove 操作，它先調(diào)用 intsetSearch 找到需要被刪除的元素在 contents 數(shù)組中的索引，然后使用內(nèi)存移位操作，將目標(biāo)元素從內(nèi)存中抹去，最后，通過內(nèi)存重分配，對(duì) contents 數(shù)組的長度進(jìn)行調(diào)整。

降級(jí)

Intset 不支持降級(jí)操作。

Intset 定位為一種受限的中間表示，只能保存整數(shù)值，而且元素的個(gè)數(shù)也不能超過 redis.h/REDIS_SET_MAX_INTSET_ENTRIES （目前版本值為 512 ）這些條件決定了它被保存的時(shí)間不會(huì)太長，因此沒有必要進(jìn)行太復(fù)雜的操作，

當(dāng)然，如果內(nèi)存確實(shí)十分緊張的話，給 intset 添加降級(jí)功能也是可以實(shí)現(xiàn)的，不過這可能會(huì)讓 intset 的代碼增長一倍。

小結(jié)

• Intset 用于有序、無重復(fù)地保存多個(gè)整數(shù)值，會(huì)根據(jù)元素的值，自動(dòng)選擇該用什么長度的整數(shù)類型來保存元素。
• 當(dāng)一個(gè)位長度更長的整數(shù)值添加到 intset 時(shí)，需要對(duì) intset 進(jìn)行升級(jí)，新 intset 中每個(gè)元素的位長度，會(huì)等于新添加值的位長度，但原有元素的值不變。
• 升級(jí)會(huì)引起整個(gè) intset 進(jìn)行內(nèi)存重分配，并移動(dòng)集合中的所有元素，這個(gè)操作的復(fù)雜度為 (O(N)) 。
• Intset 只支持升級(jí)，不支持降級(jí)。
• Intset 是有序的，程序使用二分查找算法來實(shí)現(xiàn)查找操作，復(fù)雜度為 (O(\lg N)) 。