一、前言：無序、唯一、高效的集合

在 Redis 的五大數(shù)據(jù)類型中，Set（集合） 是一個非常獨特且強大的存在。它天生具備兩個核心特性：

• 元素唯一性：自動去重，確保集合內(nèi)不存在重復(fù)元素。
• 無序性：元素沒有固定的順序（盡管 SMEMBERS 返回的順序是穩(wěn)定的）。

基于這兩個特性，Set 被廣泛應(yīng)用于：

• 標簽系統(tǒng)（用戶興趣標簽、文章分類）
• 共同好友/關(guān)注（SINTER 交集運算）
• 抽獎池（SRANDMEMBER 隨機抽?。?/li>
• 全局去重（如爬蟲 URL 去重）

但你是否想過，Redis 是如何在底層高效地實現(xiàn)“唯一性”和“快速查找”的？答案就藏在它的兩種精巧數(shù)據(jù)結(jié)構(gòu)中。

核心價值：

Redis Set 的底層會根據(jù)數(shù)據(jù)特征，在 IntSet（整數(shù)集合）和 Dict（字典）之間智能切換，以實現(xiàn)內(nèi)存效率與操作性能的最佳平衡！

本文將帶你：

• 拆解 IntSet 的緊湊內(nèi)存布局
• 揭秘 Dict 如何實現(xiàn) O(1) 的唯一性校驗
• 理解編碼轉(zhuǎn)換背后的閾值邏輯

二、Set 的雙重身份：IntSet 與 Dict

Redis Set 并非只有一種底層實現(xiàn)，而是擁有兩種編碼（encoding），由 redisObject 的 encoding 字段決定：

這種設(shè)計體現(xiàn)了 Redis “因地制宜” 的優(yōu)化哲學：對簡單、規(guī)則的數(shù)據(jù)用最省空間的結(jié)構(gòu)；對復(fù)雜、龐大的數(shù)據(jù)用最高效的結(jié)構(gòu)。

三、編碼一：IntSet - 整數(shù)的極致壓縮

3.1 誕生背景

當一個 Set 中的所有元素都是整數(shù)時，使用通用的哈希表（Dict）來存儲顯得有些“大材小用”。因為哈希表需要為每個元素存儲一個完整的 dictEntry 結(jié)構(gòu)（包含 key, value, next 指針等），內(nèi)存開銷較大。

為了極致節(jié)省內(nèi)存，Redis 引入了 IntSet。

3.2 源碼結(jié)構(gòu)

typedef struct intset {
    uint32_t encoding; // 編碼方式：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
    uint32_t length;   // 元素個數(shù)
    int8_t contents[]; // 柔性數(shù)組，存儲實際的整數(shù)數(shù)據(jù)
} intset;

關(guān)鍵特性：

• 內(nèi)存連續(xù)：所有整數(shù)緊密排列在 contents 數(shù)組中，無任何指針開銷。
• 有序存儲：內(nèi)部元素按從小到大排序，為二分查找提供可能。
• 類型升級：encoding 字段決定了每個整數(shù)占用的字節(jié)數(shù)（2/4/8字節(jié)）。

3.3 類型升級機制（核心！）

IntSet 最精妙的設(shè)計在于其動態(tài)類型升級能力。

• 初始狀態(tài)：插入第一個整數(shù) 5，encoding = INTSET_ENC_INT16，每個元素占 2 字節(jié)。
• 插入更大整數(shù)：當插入一個超出當前 encoding 范圍的整數(shù)（如 70000，超過了 int16 的最大值 32767）時，IntSet 會自動將整個集合升級到 INTSET_ENC_INT32。

過程：

• 申請一塊新的、更大的內(nèi)存空間。
• 將原有所有元素按新類型（如 int32）重新寫入新空間。
• 更新 encoding 和 length 字段。
• 釋放舊內(nèi)存。

注意：這個過程需要 O(N) 的時間復(fù)雜度和額外的內(nèi)存，但只會在必要時發(fā)生一次，之后的插入操作又恢復(fù) O(log N)（二分查找+插入）。

3.4 內(nèi)存優(yōu)勢

假設(shè)一個 Set 包含 1000 個 int16 范圍內(nèi)的整數(shù)：

• IntSet：8 (header) + 1000 * 2 = 2008 bytes
• Dict：每個 dictEntry 至少需要 8(key)+8(value)+8(next) = 24字節(jié)，加上哈希表本身的桶數(shù)組，總內(nèi)存輕松超過 24000+ bytes。

內(nèi)存節(jié)省高達 90% 以上！

四、編碼二：Dict - 通用的高性能解決方案

一旦 Set 不再滿足 IntSet 的苛刻條件（出現(xiàn)非整數(shù)，或整數(shù)太多），Redis 會立即將其轉(zhuǎn)換為 Dict（字典）。

4.1 為什么是 Dict？

Dict 是 Redis 的基石數(shù)據(jù)結(jié)構(gòu)之一，它是一個哈希表，天然具備以下特性：

• O(1) 平均時間復(fù)雜度：用于添加 (SADD)、刪除 (SREM)、查找 (SISMEMBER) 操作。
• 天然去重：哈希表的 key 本身就是唯一的，完美契合 Set 的“元素唯一”要求。

4.2 Dict 在 Set 中的特殊用法

在 Set 的場景下，Dict 的使用非常巧妙：

• Key：存儲 Set 的元素（字符串或序列化后的整數(shù)）。
• Value：統(tǒng)一設(shè)置為 NULL 指針。

// 偽代碼示意
dict *d = dictCreate(&setDictType, NULL);
dictAdd(d, "element1", NULL);
dictAdd(d, "element2", NULL);

? 優(yōu)勢：這樣既利用了 Dict 的高效哈希和唯一性保證，又省去了 Value 的內(nèi)存開銷。

4.3 漸進式 Rehash

Dict 本身也有一套精妙的擴容/縮容機制（漸進式 rehash），確保在數(shù)據(jù)量巨大時，單次操作的延遲依然很低。這部分內(nèi)容在此不展開，但它保證了即使 Set 包含百萬級元素，性能依然穩(wěn)定。

五、編碼轉(zhuǎn)換：閾值與觸發(fā)條件

Redis 通過兩個配置項來控制 Set 何時從 intset 轉(zhuǎn)換為 hashtable：

設(shè)計考量：

• 512 這個閾值：是內(nèi)存效率和操作性能的平衡點。超過 512 個元素后，IntSet 的 O(log N) 查找和 O(N) 的插入（因需移動內(nèi)存）開銷開始顯現(xiàn)，而 Dict 的 O(1) 優(yōu)勢則愈發(fā)明顯。
• 即時轉(zhuǎn)換：保證了數(shù)據(jù)模型的一致性。一旦數(shù)據(jù)不再是“純整數(shù)”，就必須切換到通用模型。

六、動手實驗：觀察 Set 的編碼變化

6.1 驗證 IntSet

# 添加純整數(shù)
> SADD myset 1 2 3 100 200
(integer) 5

# 查看編碼
> OBJECT ENCODING myset
"intset"

6.2 觸發(fā)轉(zhuǎn)換：插入非整數(shù)

# 插入一個字符串
> SADD myset "hello"
(integer) 1

# 編碼已變?yōu)?hashtable
> OBJECT ENCODING myset
"hashtable"

6.3 觸發(fā)轉(zhuǎn)換：超過閾值

# 創(chuàng)建一個腳本，添加513個整數(shù)
> for i in {1..513}; do redis-cli SADD big_intset $i; done

# 查看編碼（應(yīng)為 hashtable）
> OBJECT ENCODING big_intset
"hashtable"

七、總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論