在 Redis中，Set（集合）以其獨(dú)特的特性和高效的操作模式，在實(shí)際應(yīng)用中得到了廣泛的使用。本文將深入分析 Redis Set 的原理、源碼實(shí)現(xiàn)，并通過示例展示其在實(shí)際應(yīng)用中的使用方式。

一、什么是 Redis Set?

在 Redis 中，Set 是一種無序且不允許重復(fù)元素的數(shù)據(jù)結(jié)構(gòu)，它支持豐富的集合操作，如交集、并集和差集等。這使得 Redis Set 非常適合用于社交網(wǎng)絡(luò)中的好友列表、標(biāo)簽管理、實(shí)時(shí)推薦系統(tǒng)等場景。

Redis Set 的特點(diǎn)：

• 無序性：Set 中的元素是無序的，這意味著無法通過索引訪問特定元素。
• 唯一性：Set 中的每個(gè)元素都是唯一的，重復(fù)元素會被自動去重。
• 高效的元素操作：Redis 提供了豐富且高效的命令用于對 Set 進(jìn)行操作，如添加、刪除、獲取元素等。
• 豐富的集合操作：支持集合的交集、并集、差集等高級操作。

二、底層實(shí)現(xiàn)原理

Redis 對 Set 的實(shí)現(xiàn)高度優(yōu)化，以滿足不同場景下的性能需求，具體來說，Redis 使用了兩種內(nèi)部數(shù)據(jù)結(jié)構(gòu)來表示 Set：

• 整數(shù)集合（Intset）
• 哈希表（Hashtable）

1. Intset（整數(shù)集合）

當(dāng)一個(gè) Set 中的所有元素都是整數(shù)，并且數(shù)量較少時(shí)，Redis 會選擇使用 Intset 來存儲。這種表示方式節(jié)省內(nèi)存，并且在元素較少的情況下提供了較快的訪問速度。

結(jié)構(gòu)特點(diǎn)：

• 連續(xù)存儲：Intset 使用連續(xù)的內(nèi)存塊存儲整數(shù)，類似于一個(gè)整數(shù)數(shù)組。
• 有序性：為了優(yōu)化查找操作，Intset 會保持內(nèi)部元素的有序性，使得二分查找成為可能。
• 內(nèi)存緊湊：由于只是存儲連續(xù)的整數(shù)，內(nèi)存占用較低。

Intset 的優(yōu)勢：

• 節(jié)省內(nèi)存：對于小規(guī)模的整數(shù) Set，Intset 比哈希表節(jié)省大量內(nèi)存。
• 快速查找：有序的結(jié)構(gòu)使得二分查找的時(shí)間復(fù)雜度為 O(log N)。

Intset 的限制：

• 僅支持整數(shù)：如果 Set 中包含非整數(shù)元素，無法使用 Intset。
• 動態(tài)擴(kuò)展限制：當(dāng)元素?cái)?shù)量超過閾值，或者出現(xiàn)非整數(shù)元素時(shí)，需要轉(zhuǎn)換為哈希表。

2. Hashtable（哈希表）

當(dāng) Set 中包含非整數(shù)元素，或元素?cái)?shù)量超過某個(gè)閾值時(shí)，Redis 會將 Set 的內(nèi)部實(shí)現(xiàn)轉(zhuǎn)換為哈希表。這種表示方式雖然在內(nèi)存占用上稍大，但是支持更豐富的操作和更大的元素規(guī)模。

結(jié)構(gòu)特點(diǎn)：

• 散列表存儲：使用開放定址哈希表來存儲元素，支持快速的插入、刪除和查找。
• 支持多種元素類型：不僅支持整數(shù)，還支持字符串等其他數(shù)據(jù)類型。
• 無序性：與 Intset 一樣，哈希表中的元素也是無序的。

Hashtable 的優(yōu)勢：

• 高效的操作：哈希表提供了接近 O(1) 的時(shí)間復(fù)雜度，適用于大規(guī)模數(shù)據(jù)操作。
• 靈活性強(qiáng)：支持多種數(shù)據(jù)類型，適用于不同的應(yīng)用場景。

Hashtable 的限制：

• 內(nèi)存占用較大：相比 Intset，哈希表的內(nèi)存消耗更高。
• 無序性：盡管支持高效的操作，但無法保證元素的順序。

3. 內(nèi)部轉(zhuǎn)換機(jī)制

Redis 為了優(yōu)化性能和內(nèi)存利用，會根據(jù) Set 的實(shí)際內(nèi)容和規(guī)模動態(tài)地在 Intset 和 Hashtable 之間進(jìn)行轉(zhuǎn)換。具體來說：

• 從 Intset 到 Hashtable：當(dāng) Set 中的元素個(gè)數(shù)超過 set-max-intset-entries（默認(rèn) 512），或者出現(xiàn)非整數(shù)元素時(shí)，會將內(nèi)部表示從 Intset 轉(zhuǎn)換為 Hashtable。
• 從 Hashtable 到 Intset：當(dāng)使用于 Hashtable 的元素?cái)?shù)量降至 set-min-intset-entries（默認(rèn) 128）以下，并且所有元素都是整數(shù)時(shí)，會將內(nèi)部表示從 Hashtable 轉(zhuǎn)換為 Intset。

這種動態(tài)轉(zhuǎn)換機(jī)制保證了 Redis 在不同階段都能以最佳的方式管理 Set，兼顧性能和內(nèi)存利用。

三、源碼分析

為了深入理解 Redis Set 的實(shí)現(xiàn)原理，我們需要分析 Redis 的源代碼。以下分析基于 Redis 6.0 版本，但大部分實(shí)現(xiàn)邏輯在后續(xù)版本中保持穩(wěn)定。

1. 數(shù)據(jù)結(jié)構(gòu)定義

在 Redis 的源代碼中，Set 的實(shí)現(xiàn)主要涉及以下幾個(gè)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)：

• robj：Redis 的通用對象結(jié)構(gòu)，用于表示不同的數(shù)據(jù)類型，包括 Set。
• intset：表示 Intset 的結(jié)構(gòu)。
• dict：Redis 的哈希表實(shí)現(xiàn)，表示 Hashtable。

以下是相關(guān)結(jié)構(gòu)的簡化定義。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; // 最近使用時(shí)間
    int refcount;
    void *ptr;
} robj;

typedefstruct intset {
    uint32_t encoding;
    uint32_t length;
    int32_t contents[];
} intset;

typedefstruct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
} dictEntry;

typedefstruct dicthdr {
    int size;
    dictEntry *table;
    dictEntry **buckets;
    // 其他成員...
} dict;

2. 創(chuàng)建和銷毀 Set對象

當(dāng)調(diào)用 SADD、SREM 等命令時(shí)，Redis 首先會檢查目標(biāo)鍵是否存在。如果不存在，會調(diào)用 createSetObject 來創(chuàng)建一個(gè)新的 Set 對象。

• 創(chuàng)建 Set 對象的代碼片段：

robj *createSetObject(void) {
    intset *is = intsetNew();
    robj *o = createObject(OBJ_SET, is);
    o->encoding = OBJ_ENCODING_INTSET;
    return o;
}

intset *intsetNew(void) {
    intset *is = malloc(sizeof(intset));
    is->encoding = INTSET_ENC_INT32;
    is->length = 0;
    return is;
}

• 銷毀 Set 對象的代碼片段：

void freeSetObject(robj *set) {
    if (set->encoding == OBJ_ENCODING_INTSET) {
        intsetDel(set->ptr);
    } else {
        dictRelease(set->ptr);
    }
    decrRefCount(set);
}

3. Set 操作命令的實(shí)現(xiàn)

以 SADD 命令為例，其實(shí)現(xiàn)涉及以下幾個(gè)步驟：

(1) 查找或創(chuàng)建 Set 對象：如果目標(biāo)鍵不存在，創(chuàng)建一個(gè)新的 Set 對象。

(2) 判斷編碼類型：根據(jù)當(dāng)前 Set 的編碼類型（Intset 或 Hashtable），調(diào)用相應(yīng)的添加元素函數(shù)。

(3) 添加元素：

• 如果是 Intset，嘗試將元素轉(zhuǎn)換為整數(shù)并添加；如果轉(zhuǎn)換失敗或超出容量，轉(zhuǎn)換為 Hashtable。
• 如果是 Hashtable，直接進(jìn)行添加。

(4) 返回結(jié)果：返回成功添加的元素?cái)?shù)量。

SADD 命令的關(guān)鍵實(shí)現(xiàn)代碼：

int setTypeAdd(robj *subject, robj *value) {
    if (subject->encoding == OBJ_ENCODING_INTSET) {
        longlong ll;
        if (getLongLongFromObject(value, &ll)) {
            if (intsetFind(subject->ptr, ll)) return0;
            subject->ptr = intsetAdd(subject->ptr, ll, INTSET_NONE);
            return1;
        }
        // 轉(zhuǎn)換為 hashtable
        setTypeConvert(subject, OBJ_ENCODING_HT);
    }
    if (subject->encoding == OBJ_ENCODING_HT) {
        dict *dict = subject->ptr;
        return dictAdd(dict, value, NULL) == DICT_OK;
    }
    return0;
}

4. Set的集合操作

Redis 支持多種集合操作，如交集（SINTER）、并集（SUNION）和差集（SDIFF）。這些操作通常涉及多個(gè) Set 對象的迭代和元素比較。

以 SINTER 為例，其實(shí)現(xiàn)步驟如下：

• 獲取所有參與的 Set 對象。
• 選擇最小的 Set 作為基準(zhǔn)以優(yōu)化性能。
• 遍歷基準(zhǔn) Set 的元素，對每個(gè)元素在其他 Set 中進(jìn)行查找。
• 將存在于所有 Set 中的元素添加到結(jié)果 Set。
• 返回結(jié)果。

SINTER 命令的關(guān)鍵實(shí)現(xiàn)代碼：

robj *sinterCommand(client *c) {
    robj **sets = c->argv + 1;
    int setnum = c->argc - 1;
    robj *s = setTypeIntersection(sets, setnum);
    addReplySet(c, s);
    decrRefCount(s);
    return C_OK;
}

robj *setTypeIntersection(robj **sets, int setnum) {
    // 選擇最小的 Set 作為基準(zhǔn)
    robj *minset = selectMinSet(sets, setnum);
    robj *result = createSetObject();
    // 遍歷基準(zhǔn) Set 的元素
    if (minset->encoding == OBJ_ENCODING_INTSET) {
        intset *is = minset->ptr;
        for (int i = 0; i < is->length; i++) {
            longlong ll;
            intsetGet(is, i, &ll);
            robj *ele = createStringObjectFromLongLong(ll);
            int exists = 1;
            for (int j = 0; j < setnum; j++) {
                if (j == index of minset) continue;
                if (!setTypeIsMember(sets[j], ele)) {
                    exists = 0;
                    break;
                }
            }
            if (exists) setTypeAdd(result, ele);
            decrRefCount(ele);
        }
    } else {
        // 哈希表遍歷邏輯
    }
    return result;
}

5. 內(nèi)部轉(zhuǎn)換邏輯

如前所述，當(dāng) Set 的大小或元素類型發(fā)生變化時(shí)，Redis 會在 Intset 和 Hashtable 之間轉(zhuǎn)換。這一過程涉及內(nèi)存重新分配和數(shù)據(jù)拷貝。

從 Intset 到 Hashtable 的轉(zhuǎn)換：

void setTypeConvert(robj *set, int encoding) {
    if (set->encoding == encoding) return;
    if (encoding == OBJ_ENCODING_HT) {
        dict *dict = dictCreate(&setDictType, NULL);
        void *iter = setTypeInitIterator(set);
        robj *ele;
        while((ele = setTypeNext(set, iter)) != NULL) {
            dictAdd(dict, ele, NULL);
        }
        setTypeReleaseIterator(iter);
        set->encoding = OBJ_ENCODING_HT;
        set->ptr = dict;
    }
    // 其他轉(zhuǎn)換邏輯...
}

從 Hashtable 到 Intset 的轉(zhuǎn)換：

void setTypeConvertToIntset(robj *set) {
    if (!setTypeCanEncodeIntset(set)) return;
    intset *is = intsetNew();
    dict *dict = set->ptr;
    dictIterator *di = dictGetIterator(dict);
    dictEntry *de;
    while ((de = dictNext(di)) != NULL) {
        longlong ll;
        if (getLongLongFromObj(de->key, &ll)) {
            is = intsetAdd(is, ll, INTSET_NONE);
        } else {
            dictReleaseIterator(di);
            intsetDel(is);
            return;
        }
    }
    dictReleaseIterator(di);
    dictRelease(set->ptr);
    set->ptr = is;
    set->encoding = OBJ_ENCODING_INTSET;
}

6. 內(nèi)存管理和優(yōu)化

Redis 對 Set 的內(nèi)存管理進(jìn)行了深度優(yōu)化，以確保在不同的使用場景下都能高效地利用內(nèi)存。具體措施包括：

• 共享對象：對于經(jīng)常使用的小整數(shù)，Redis 通過對象共享機(jī)制（Shared Objects）減少內(nèi)存占用。
• 內(nèi)存分配器優(yōu)化：Redis 使用 jemalloc 作為默認(rèn)的內(nèi)存分配器，通過優(yōu)化內(nèi)存分配策略提升性能。
• 惰性刪除：在哈希表中刪除元素時(shí)，Redis 采用惰性刪除策略，避免高頻次的重新哈希操作。

四、Redis Set 的使用示例

為了更好地理解 Redis Set的實(shí)用性，下面我們將通過幾個(gè)具體的示例展示它在實(shí)際應(yīng)用中的使用方式。

1. 用戶興趣標(biāo)簽管理

假設(shè)有一個(gè)應(yīng)用需要管理用戶的興趣標(biāo)簽，Set 是理想的選擇，因?yàn)樗苡行У乇ＷC標(biāo)簽的唯一性，并支持高效的添加、刪除和查詢操作。

示例場景：

• 一個(gè)用戶可以擁有多個(gè)興趣標(biāo)簽，如“音樂”、“編程”、“旅游”等。
• 用戶可以添加或刪除興趣標(biāo)簽。
• 需要查詢用戶的所有興趣標(biāo)簽。

Redis 命令示例：

# 添加興趣標(biāo)簽
SADD user:1000:tags "音樂" "編程" "旅游"

# 刪除一個(gè)標(biāo)簽
SREM user:1000:tags "旅游"

# 獲取所有標(biāo)簽
SMEMBERS user:1000:tags

# 判斷用戶是否有某個(gè)標(biāo)簽
SISMEMBER user:1000:tags "編程"

示例解釋：

• SADD 命令用于添加一個(gè)或多個(gè)元素到 Set 中。重復(fù)的元素會被自動忽略。
• SREM 命令用于從 Set 中刪除一個(gè)或多個(gè)元素。
• SMEMBERS 命令返回 Set 中的所有成員。
• SISMEMBER 命令用于檢查一個(gè)元素是否存在于 Set 中。

2. 共同好友推薦

在社交網(wǎng)絡(luò)中，推薦共同好友是一個(gè)常見功能。Set 的交集操作為實(shí)現(xiàn)這一功能提供了高效的手段。

示例場景：

• 用戶 A 和用戶 B 的好友列表都是 Redis 的 Set。
• 需要找出 A 和 B 的共同好友數(shù)量。

Redis 命令示例：

# 用戶 A 的好友列表
SADD user:A:friends "User1" "User2" "User3" "User4"

# 用戶 B 的好友列表
SADD user:B:friends "User3" "User4" "User5" "User6"

# 獲取共同好友
SINTER user:A:friends user:B:friends

示例解釋：SINTER 命令返回所有給定集合的交集成員。在本例中，即為用戶 A 和用戶 B 的共同好友。

3. 實(shí)時(shí)在線用戶統(tǒng)計(jì)

在實(shí)時(shí)應(yīng)用中，經(jīng)常需要統(tǒng)計(jì)當(dāng)前在線的用戶列表。Set 的添加、刪除和計(jì)數(shù)功能使其成為理想的選擇。

示例場景：

• 當(dāng)用戶上線時(shí)，將用戶 ID 添加到在線用戶 Set 中。
• 當(dāng)用戶下線時(shí)，從 Set 中移除用戶 ID。
• 統(tǒng)計(jì)當(dāng)前在線用戶數(shù)量。

Redis 命令示例：

# 用戶上線
SADD online_users "User1"

# 用戶下線
SREM online_users "User1"

# 獲取在線用戶數(shù)量
SCARD online_users

# 獲取所有在線用戶
SMEMBERS online_users

示例解釋：SCARD 命令返回 Set 中的元素?cái)?shù)量，用于統(tǒng)計(jì)在線用戶數(shù)量。

4. 關(guān)鍵詞去重

在數(shù)據(jù)處理過程中，常常需要對關(guān)鍵詞進(jìn)行去重。Set 的唯一性保證了關(guān)鍵詞的唯一性，適合用于此類場景。

示例場景：從大規(guī)模文本中提取關(guān)鍵詞，并存儲到 Redis 的 Set 中，自動去除重復(fù)關(guān)鍵詞。

Redis 命令示例：

# 假設(shè)從文本中提取到以下關(guān)鍵詞
SADD keywords "redis" "數(shù)據(jù)庫" "緩存" "redis" "NoSQL"

# 獲取去重后的關(guān)鍵詞
SMEMBERS keywords

示例解釋：重復(fù)的"redis"關(guān)鍵詞在 Set 中只會存儲一次，確保關(guān)鍵詞的唯一性。

五、擴(kuò)展與高級功能

Redis Set 作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，還支持一些擴(kuò)展和高級功能，進(jìn)一步增強(qiáng)了其應(yīng)用的靈活性和 powerfulness。

1. 集合的交集、并集和差集

Redis 提供了 SINTER, SUNION, SDIFF 等命令，用于執(zhí)行集合的交集、并集和差集操作。這些操作在群組管理、標(biāo)簽分析等場景中非常有用。

示例：

# 交集
SINTER group:admins group:active

# 并集
SUNION group:admins group:employees

# 差集
SDIFF group:admins group:external

2. 隨機(jī)元素獲取

有時(shí)需要從 Set 中隨機(jī)獲取一個(gè)或多個(gè)元素，Redis 提供了 SRANDMEMBER 命令來滿足這一需求。

示例：

# 隨機(jī)獲取一個(gè)元素
SRANDMEMBER myset

# 隨機(jī)獲取兩個(gè)元素
SRANDMEMBER myset 2

3. 元素迭代

通過 SSCAN 命令，可以對 Set 進(jìn)行迭代，適用于處理大規(guī)模 Set 的場景，有助于避免長時(shí)間阻塞 Redis 服務(wù)。

示例：

# 迭代 Set 中的元素
SSCAN myset 0 MATCH pattern* COUNT 100

4. 結(jié)合其他數(shù)據(jù)結(jié)構(gòu)

Redis 允許將 Set 與其他數(shù)據(jù)結(jié)構(gòu)組合使用，構(gòu)建更加復(fù)雜和高效的數(shù)據(jù)模型。例如，使用 Hash 和 Set 結(jié)合，管理用戶的詳細(xì)信息和興趣標(biāo)簽。

示例：

# 存儲用戶詳細(xì)信息
HSET user:1000:name "Alice" user:1000:age 30

# 存儲用戶興趣標(biāo)簽
SADD user:1000:tags "音樂" "編程" "旅游"

# 查詢用戶信息和興趣標(biāo)簽
HGETALL user:1000:name
SMEMBERS user:1000:tags

六、總結(jié)

本文，我們詳細(xì)分析了 Redis 的 Set數(shù)據(jù)結(jié)構(gòu)，通過深入分析其底層實(shí)現(xiàn)原理，包括 Intset 和 Hashtable 的動態(tài)轉(zhuǎn)換機(jī)制，以及其相關(guān)的源碼，可以幫助我們更好地利用 Redis Set，實(shí)現(xiàn)高性能、高可靠的應(yīng)用系統(tǒng)。