今天我們來聊聊Redis中一個(gè)非常有趣且實(shí)用的數(shù)據(jù)結(jié)構(gòu)——有序集合(zset)。就像我們平時(shí)在超市購物時(shí)，商品會(huì)按照價(jià)格從低到高排列一樣，zset也能幫我們維護(hù)一個(gè)有序的數(shù)據(jù)集合。那么Redis是如何實(shí)現(xiàn)這種高效的有序結(jié)構(gòu)的呢？讓我們一起來探索它的底層實(shí)現(xiàn)原理。

1. zset的基本概念

在開始深入之前，我們先簡單回顧一下zset的基本特性。zset是Redis提供的一種有序集合數(shù)據(jù)結(jié)構(gòu)，它類似于普通的集合(set)，但每個(gè)成員都會(huì)關(guān)聯(lián)一個(gè)分?jǐn)?shù)(score)，Redis會(huì)根據(jù)這個(gè)分?jǐn)?shù)對(duì)集合中的成員進(jìn)行從小到大的排序。

zset在實(shí)際應(yīng)用中非常有用，比如我們可以用它來實(shí)現(xiàn)：

• 排行榜系統(tǒng)（按分?jǐn)?shù)排序）
• 帶權(quán)重的任務(wù)隊(duì)列
• 時(shí)間線功能（按時(shí)間戳排序）
• 范圍查詢（如查找分?jǐn)?shù)在80-90之間的學(xué)生）

zset的一個(gè)關(guān)鍵特性是：雖然成員是唯一的，但分?jǐn)?shù)可以重復(fù)。這就像班級(jí)里每個(gè)學(xué)生學(xué)號(hào)唯一，但可以有多個(gè)學(xué)生考同樣的分?jǐn)?shù)。

2. zset的底層實(shí)現(xiàn)結(jié)構(gòu)

理解了zset的基本概念后，我們來看看Redis是如何實(shí)現(xiàn)它的。Redis的zset實(shí)際上使用了兩種數(shù)據(jù)結(jié)構(gòu)組合來實(shí)現(xiàn)：

2.1 哈希表(Hash Table)

Redis使用一個(gè)哈希表來存儲(chǔ)成員(member)到分?jǐn)?shù)(score)的映射關(guān)系。這就像我們有一個(gè)學(xué)生名冊(cè)，可以快速通過學(xué)生姓名查找到他的考試成績。

哈希表的優(yōu)勢(shì)在于：

• O(1)時(shí)間復(fù)雜度查找成員對(duì)應(yīng)的分?jǐn)?shù)
• 快速判斷某個(gè)成員是否存在
• 高效更新成員的分?jǐn)?shù)

2.2 跳躍表(Skip List)或壓縮列表(Zip List)

為了維護(hù)成員的有序性，Redis會(huì)根據(jù)數(shù)據(jù)量的大小選擇使用跳躍表或壓縮列表：

• 當(dāng)元素?cái)?shù)量較少或元素較小時(shí)，使用壓縮列表(Zip List)
• 當(dāng)元素?cái)?shù)量超過閾值或元素較大時(shí)，使用跳躍表(Skip List)

這種設(shè)計(jì)是Redis典型的"小數(shù)據(jù)優(yōu)化"思想，對(duì)于小數(shù)據(jù)集使用更緊湊的存儲(chǔ)方式，對(duì)于大數(shù)據(jù)集則使用性能更好的結(jié)構(gòu)。

以上流程圖說明了zset的底層實(shí)現(xiàn)結(jié)構(gòu)。它同時(shí)使用了哈希表和有序結(jié)構(gòu)（可能是壓縮列表或跳躍表）來滿足不同的操作需求。

3. 壓縮列表實(shí)現(xiàn)細(xì)節(jié)

現(xiàn)在我們來詳細(xì)看看zset在小數(shù)據(jù)情況下的實(shí)現(xiàn)——壓縮列表(Zip List)。壓縮列表是Redis為了節(jié)省內(nèi)存而設(shè)計(jì)的一種特殊編碼方式。

3.1 壓縮列表的結(jié)構(gòu)

壓縮列表是一塊連續(xù)的內(nèi)存空間，它按照特定的格式存儲(chǔ)數(shù)據(jù)。想象一下，這就像我們把所有數(shù)據(jù)整齊地打包在一個(gè)行李箱里，而不是分散放在房間各處。

一個(gè)壓縮列表包含以下部分：

+--------+--------+--------+--------+--------+--------+--------+--------+
| zlbytes | zltail | zllen  | entry1 | entry2 |  ...   | entryN | zlend  |
+--------+--------+--------+--------+--------+--------+--------+--------+
    

其中：

• zlbytes: 整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)
• zltail: 最后一個(gè)節(jié)點(diǎn)的偏移量，方便快速定位
• zllen: 節(jié)點(diǎn)數(shù)量
• entry1..N: 各個(gè)節(jié)點(diǎn)數(shù)據(jù)
• zlend: 結(jié)束標(biāo)記(0xFF)

3.2 壓縮列表中的元素存儲(chǔ)

在zset中使用壓縮列表時(shí)，每個(gè)成員和它的分?jǐn)?shù)會(huì)作為兩個(gè)連續(xù)的節(jié)點(diǎn)存儲(chǔ)。這就像我們把學(xué)生的姓名和成績寫在相鄰的兩張卡片上。

例如，存儲(chǔ)一個(gè)zset {“alice”: 85, “bob”: 92}，在壓縮列表中的布局如下：

+-------+-------+-------+-------+-------+-------+-------+-------+
| ... | 85  | alice | 92  | bob  | ... |
+-------+-------+-------+-------+-------+-------+-------+-------+
    

這種存儲(chǔ)方式非常緊湊，沒有額外的指針開銷，因此在小數(shù)據(jù)量時(shí)非常高效。

需要注意的是，當(dāng)zset使用壓縮列表存儲(chǔ)時(shí)，所有操作都需要遍歷整個(gè)列表，因此時(shí)間復(fù)雜度是O(N)。這就是為什么Redis會(huì)在數(shù)據(jù)量大時(shí)切換到跳躍表的原因。

4. 跳躍表實(shí)現(xiàn)細(xì)節(jié)

當(dāng)zset中的元素?cái)?shù)量超過zset-max-ziplist-entries（默認(rèn)128）或元素大小超過zset-max-ziplist-value（默認(rèn)64字節(jié)）時(shí)，Redis會(huì)將底層結(jié)構(gòu)轉(zhuǎn)換為跳躍表(Skip List)。

4.1 跳躍表的基本概念

跳躍表是一種概率平衡的數(shù)據(jù)結(jié)構(gòu)，可以看作是多層鏈表。想象一下地鐵系統(tǒng)：有普通站（每站都停）和快速站（只停大站），這樣乘客可以根據(jù)需要選擇不同速度的線路。

一個(gè)簡單的跳躍表示例：

Level 3: 1 --------------------------------> 9
Level 2: 1 ------------> 5 ------------> 9
Level 1: 1 ---> 3 ---> 5 ---> 7 ---> 9
Level 0: 1->2->3->4->5->6->7->8->9
    

在這個(gè)結(jié)構(gòu)中，查找時(shí)可以跳過一些節(jié)點(diǎn)，從而將查找時(shí)間復(fù)雜度從O(N)降低到O(logN)。

4.2 Redis中跳躍表的具體實(shí)現(xiàn)

Redis中的跳躍表實(shí)現(xiàn)包含兩個(gè)主要結(jié)構(gòu)：

1. zskiplistNode（跳躍表節(jié)點(diǎn)）

typedef struct zskiplistNode {
    robj *obj;                  // 成員對(duì)象
    double score;               // 分?jǐn)?shù)
    struct zskiplistNode *backward; // 后退指針
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前進(jìn)指針
        unsigned int span;             // 跨度
    } level[];                  // 層級(jí)數(shù)組
} zskiplistNode;
    

2. zskiplist（跳躍表）

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 頭尾節(jié)點(diǎn)
    unsigned long length;       // 節(jié)點(diǎn)數(shù)量
    int level;                  // 當(dāng)前最大層數(shù)
} zskiplist;
    

跳躍表在Redis中的實(shí)際內(nèi)存布局如下圖所示：

[圖片位置1：Redis跳躍表內(nèi)存布局示意圖]

4.3 跳躍表的操作原理

讓我們以插入操作為例，看看跳躍表是如何工作的：

以上流程圖說明了在跳躍表中插入一個(gè)新元素的完整過程。關(guān)鍵在于從高層開始快速定位，然后逐步精確到插入位置，最后通過隨機(jī)算法決定新節(jié)點(diǎn)的層數(shù)。

4.4 為什么Redis選擇跳躍表而不是平衡樹

很多同學(xué)可能會(huì)問，為什么Redis不使用更常見的平衡樹（如AVL樹或紅黑樹）來實(shí)現(xiàn)有序集合呢？這主要有以下幾個(gè)原因：

1. 實(shí)現(xiàn)簡單：跳躍表的實(shí)現(xiàn)比平衡樹簡單得多，代碼更易于維護(hù)
2. 范圍查詢高效：跳躍表在范圍查詢時(shí)非常高效，因?yàn)榈讓邮且粋€(gè)鏈表
3. 并發(fā)友好：跳躍表比平衡樹更容易實(shí)現(xiàn)無鎖并發(fā)操作
4. 性能相當(dāng)：對(duì)于大多數(shù)操作，跳躍表的平均時(shí)間復(fù)雜度與平衡樹相同

5. zset的常用操作分析

了解了zset的底層結(jié)構(gòu)后，我們來看看一些常用操作在這些結(jié)構(gòu)上是如何執(zhí)行的。

5.1 ZADD操作

ZADD key score member 是向zset中添加元素的基本命令。它的執(zhí)行流程如下：

檢查zset是否存在，不存在則創(chuàng)建

如果底層是壓縮列表：

• 檢查是否需要轉(zhuǎn)換為跳躍表（根據(jù)元素?cái)?shù)量和大小）
• 如果不需要轉(zhuǎn)換，則遍歷壓縮列表查找插入位置
• 插入新元素（可能需要重新分配內(nèi)存）

如果底層是跳躍表：

• 使用跳躍表查找算法定位插入位置
• 創(chuàng)建新節(jié)點(diǎn)并插入到適當(dāng)位置
• 更新哈希表中的member->score映射

5.2 ZRANGE操作

ZRANGE key start stop 用于獲取指定范圍內(nèi)的元素。它的執(zhí)行流程：

檢查zset是否存在

如果底層是壓縮列表：

• 從頭開始遍歷到start位置
• 繼續(xù)遍歷直到stop位置，收集結(jié)果

如果底層是跳躍表：

• 從頭節(jié)點(diǎn)開始，利用跳躍表的層級(jí)快速定位到start位置
• 沿著最底層鏈表遍歷到stop位置

5.3 ZSCORE操作

ZSCORE key member 用于獲取成員的分?jǐn)?shù)。這個(gè)操作非常高效，因?yàn)樗苯油ㄟ^哈希表查找：

1. 在哈希表中查找member對(duì)應(yīng)的score
2. 返回結(jié)果（無論底層是壓縮列表還是跳躍表，這一步都是O(1)）

從這些操作中我們可以看到，Redis巧妙地結(jié)合了哈希表和有序結(jié)構(gòu)的優(yōu)勢(shì)：哈希表提供快速的成員查找，有序結(jié)構(gòu)維護(hù)排序和范圍查詢能力。

6. zset的內(nèi)存優(yōu)化技巧

在實(shí)際使用中，我們經(jīng)常需要考慮如何優(yōu)化zset的內(nèi)存使用。下面分享幾個(gè)實(shí)用的技巧：

6.1 合理設(shè)置ziplist參數(shù)

我們可以根據(jù)實(shí)際數(shù)據(jù)特點(diǎn)調(diào)整這兩個(gè)參數(shù)：

# 修改redis.conf或通過CONFIG SET命令
zset-max-ziplist-entries 256  # 默認(rèn)128
zset-max-ziplist-value 128    # 默認(rèn)64
    

上述配置將允許更多的元素或更大的元素使用壓縮列表存儲(chǔ)。但要注意：

• 增加這些值會(huì)節(jié)省內(nèi)存，但可能降低操作性能
• 需要根據(jù)實(shí)際數(shù)據(jù)特點(diǎn)進(jìn)行測(cè)試和權(quán)衡

6.2 使用更短的成員名稱

由于成員名稱存儲(chǔ)在內(nèi)存中，使用更短的名稱可以顯著節(jié)省內(nèi)存。例如：

• 使用用戶ID而不是用戶名
• 使用縮寫或編碼代替完整名稱

6.3 考慮使用整數(shù)分?jǐn)?shù)

如果業(yè)務(wù)允許，使用整數(shù)而不是浮點(diǎn)數(shù)作為分?jǐn)?shù)可以節(jié)省一些內(nèi)存。

6.4 定期清理過期數(shù)據(jù)

對(duì)于排行榜等場(chǎng)景，可以定期移除排名靠后的數(shù)據(jù)，保持zset的大小可控。

7. 實(shí)際應(yīng)用案例

讓我們看一個(gè)實(shí)際的排行榜實(shí)現(xiàn)案例，展示如何充分利用zset的特性。

7.1 游戲排行榜實(shí)現(xiàn)

假設(shè)我們要實(shí)現(xiàn)一個(gè)游戲玩家積分排行榜，支持以下功能：

• 記錄玩家分?jǐn)?shù)
• 獲取前10名玩家
• 查詢玩家排名
• 查詢分?jǐn)?shù)段內(nèi)的玩家

Redis命令實(shí)現(xiàn)：

# 添加或更新玩家分?jǐn)?shù)
ZADD leaderboard 3500 "player1"
ZADD leaderboard 2800 "player2"
ZADD leaderboard 4200 "player3"

# 獲取前10名玩家（按分?jǐn)?shù)從高到低）
ZREVRANGE leaderboard 0 9 WITHSCORES

# 查詢特定玩家排名（從0開始）
ZREVRANK leaderboard "player1"

# 查詢分?jǐn)?shù)在3000-4000之間的玩家
ZRANGEBYSCORE leaderboard 3000 4000 WITHSCORES
    

上述代碼展示了如何使用zset實(shí)現(xiàn)一個(gè)完整的排行榜系統(tǒng)。考慮到排行榜需要頻繁更新和查詢，zset的O(logN)操作復(fù)雜度非常適合這種場(chǎng)景。

總結(jié)

通過今天的探討，我們對(duì)Redis中zset的底層實(shí)現(xiàn)有了深入的理解。讓我們總結(jié)一下本文的主要內(nèi)容：

1. zset的基本概念：有序集合，成員唯一但分?jǐn)?shù)可重復(fù)
2. 底層結(jié)構(gòu)：哈希表+有序結(jié)構(gòu)（壓縮列表或跳躍表）
3. 壓縮列表實(shí)現(xiàn)：小數(shù)據(jù)時(shí)使用，內(nèi)存緊湊但操作復(fù)雜度高
4. 跳躍表實(shí)現(xiàn)：大數(shù)據(jù)時(shí)使用，O(logN)時(shí)間復(fù)雜度，支持高效范圍查詢
5. 操作分析：不同操作在不同結(jié)構(gòu)上的執(zhí)行流程
6. 優(yōu)化技巧：合理配置參數(shù)、縮短成員名稱等
7. 實(shí)際應(yīng)用：排行榜系統(tǒng)的完整實(shí)現(xiàn)

Redis的zset通過巧妙的雙結(jié)構(gòu)設(shè)計(jì)，既保證了高效的成員查找，又維護(hù)了良好的排序特性，是很多有序場(chǎng)景的理想選擇。

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

最新評(píng)論