Redis Sorted Set 底層實現原理深度解讀與排行榜實戰

作者：就是碼哥呀 2023-07-17 08:32:40

數據庫 Redis

Sorted Sets 與 Sets 類似，是一種集合類型，集合中不會出現重復的數據（member）。區別在于 Sorted Sets 元素由兩部分組成，分別是 member 和 score。

我是碼哥，可以叫我靚仔。今天給大家簡單聊聊 Redis Sorted Set 數據類型底層的實現原理和游戲排行榜實戰。特別簡單，一點也不深入，也就 7 張圖，粉絲可放心食用，哈哈哈哈哈~~~~。

1、是什么

Sorted Sets 與 Sets 類似，是一種集合類型，集合中不會出現重復的數據（member）。區別在于 Sorted Sets 元素由兩部分組成，分別是 member 和 score。

member 會關聯一個 double 類型的分數（score），sorted sets 默認會根據這個 score 對 member 進行從小到大的排序，如果 member 關聯的分數 score 相同，則按照字符串的字典順序排序。

這是規則，得記下來。

常見的使用場景：

排行榜，比如維護大型在線游戲中根據分數排名的 Top 10 有序列表。
速率限流器，根據排序集合構建滑動窗口速率限制器。
延遲隊列，score 存儲過期時間，從小到大排序，最靠前的就是最先到期的數據。

2、修煉心法

Sorted Sets 底層有兩種方式來存儲數據。

在 7.0 版本之前是 ziplist，之后被 listpack 代替，使用 listpack 存儲的條件是集合元素個數小于等于 zset-max-listpack-entries 配置值（默認 128），且 member 占用字節大小小于 zset-max-listpack-value 配置值（默認 64）時使用 listpack 存儲，member 和 score 緊湊排列作為 listpack 的一個元素進行存儲。
不滿足上述條件，使用 skiplist + dict（散列表）組合方式存儲，數據會插入 skiplist 的同時也會向 dict（散列表）中插入數據，是一種用空間換時間的思路。散列表的 key 存放的是元素的 member，value 存儲的是 member 關聯的 score。

MySQL：“也就是說 listpack 適用于元素個數不多且元素內容不大的場景。

對，使用 listpack 存儲的目的就是節省內存。

Sorted Sets 能支持高效的范圍查詢，正是因為采用了 skiplist 跳表，比如 ZRANGE 命令時時間復雜度為 O(log(n)) + m， n 是 member 個數，m 是返回結果數。需要注意的是，你應該避免命令會返回大量結果。

而使用 dict 的原因是實現 O(1) 時間復雜度查詢單個元素。比如 ZSCORE key member 指令。

總結來說，Sorted Sets 在插入或者更新的時候，會同時往 skiplist 和散列表中插入或者更新對應的數據。保證 skiplist 和散列表的數據一致。

?
MySQL：“這個方式很巧妙呀，skiplist 用來根據 score 進行范范圍查詢或者單個查詢，dict 散列表則用于實現 O(1) 時間復雜度查根據數據查詢對應 score，滿足高效范圍查詢和單元素查詢。“

sorted sets 實現源碼主要在以下兩個文件中。

結構定義在 server.h。
功能實現在 t_zset.c。

先看 skiplist（跳表） + dict（散列表）數據結構如何存儲數據。

skiplist + dict

MySQL：“說說什么是跳表吧”

實質就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現快速查找。

不僅能提高搜索性能，還可以提高插入和刪除操作的性能。它在性能上和紅黑樹、AVL 樹不相上下，但是跳表的原理和實現比紅黑樹簡單。

回顧鏈表，它的痛點就是查詢很慢，O(n) 時間復雜度，作為唯快不破的 Redis 是不能忍的。

如果在有序鏈表的每相鄰兩個節點增加一個“跳躍”指向下下個節點的指針，那么查找的時間復雜度就可以降低為原來的一半，如下圖所示。

這樣 level 0 和 level 1 分別形成兩個鏈表，level 1 層的鏈表節點個數只有 2 個（6、26）。

跳表節點查找

查找數據總是從最高層開始比較，如果節點保存的值比待查數據小，跳表就繼續訪問該層的下一個節點；

如果碰到比待查數據值大的節點時，那就跳到當前節點的下一層的鏈表繼續查找。

比如現在想查找 17，查找的路徑如下圖紅色指向的方向進行。

從 level 1 開始，17 與 6 比較，值大于節點，繼續與下一個節點比較。
與 26 比較，17 < 26，回到原節點，跳到當前節點的 level 0 層鏈表，與下一個節點比較，找到目標 17。

skiplist 正是受這種多層鏈表的想法啟發設計出來的。按照上面的生成鏈表方式，每次往上增加一層鏈表的節點個數是下面一層的一半，這樣的查找過程就類似于一個二分查找，時間復雜度為 O(log n)。

但是，這種方式在插入數據的時候有很大的問題，每次新增一個節點，就會打亂相鄰的兩層鏈表節點個數 2:1 的關系，如果要維持這個關系，就需要對鏈表調整，事件復雜度是 O(n)。

為了避免這個問題，它不要求上下相鄰的兩層鏈表節點個數有嚴格的比例關系，而是為每個節點隨機出一個層數，這樣插入節點只需要修改前后指針。

如下圖是一個有 4 層鏈表的 skiplist，假設我們要查找 26，下圖給出了查找經歷過的路徑。

對經典跳表有個直觀的映像后，來看看 Redis 中 skiplist 的實現細節，Sorted Sets 數據結構定義如下。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

zset 結構體中有兩個變量，分別是散列表 dict 和跳表 zskiplist。dict 在前文已經講過，重點看 zskiplist 。

typedef struct zskiplist {
    // 頭、尾指針便于雙向遍歷
    struct zskiplistNode *header, *tail;
    // 當前跳表包含元素個數
    unsigned long length;
    // 表內節點的最大層級數
    int level;
} zskiplist;

zskiplistNode *header, *tail，兩個頭、尾指針，用于實現雙向遍歷。
length，鏈表包含的節點總數。需要注意的是，新創建的 zskiplist 會生成一個空的頭指針，它不包含在 length 計數中。
level，表示 skiplist 中，所有節點層數的最大值。

接著繼續看 skiplist 中每個節點的定義 zskiplistNode 結構體。

typedef struct zskiplistNode {
    sds ele;
    double score;

    struct zskiplistNode *backward;

    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];

} zskiplistNode;

Sorted Set 既要保存元素，又要保存元素的權重。所以對應了 sds 類型的 ele 存儲實際內容， double 類型 score 用于保存權重。
*backward，后退指針，指向該節點的上一個節點，便于從尾節點實現倒序查找。注意，每個節點只有一個后向指針，只有 level 0 層鏈表是一個雙向鏈表。
level[]，是一個 zskiplistLevel 結構體類型的柔性數組。跳表是一個多層的有序鏈表，每一層的節點也是由指針鏈接起來的，所以數組中每個元素代表著 skiplist 的一層。

*forward，該層的前進指針。
span，跨度，用來記錄節點在該層的 *forward 指針到指針指向的下一個節點之間跨越了 level0 層的節點數。span 用于計算元素排名(rank)，例如查找 ele = 肖菜雞、score = 17 的排名，只需要把查找路徑經過的節點的 span 相加即可，如下圖的紅色路徑的 span 累加，rank = (2 + 2) - 1 = 3（減 1 是因為 rank 從 0 開始）。如果要計算從大到小的排名，只需要用 skiplist 長度減去查找路徑上的 span 累加值，即 4 - (2 + 2) = 0。

下圖展示了 Redis 中一個 skiplsit 的可能結構。

listpack

MySQL：“根據 zset 結構體定義可知，分別使用了 dict、zskiplist 兩種數據結構，listpack 影子都見不著呀。“

這個問題問得好，使用 listpack 存儲的細節在源碼文件t_zset.c 中的zaddGenericCommand函數中體現，部分代碼如下，內部會判斷是否使用 listpack 來存儲。·

void zaddGenericCommand(client *c, int flags) {
    // 省略部分代碼

    // key 不存在則創建 sorted set
    zobj = lookupKeyWrite(c->db,key);
    if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
    if (zobj == NULL) {
        if (xx) goto reply_to_client;
      // 當 zset_max_listpack_entries == 0 或者
        // 元素字節大小大于 zset_max_listpack_value 配置
        // 則使用 skiplist + dict 存儲，否則使用 listpack。
        if (server.zset_max_listpack_entries == 0 ||
            server.zset_max_listpack_value < sdslen(c->argv[scoreidx+1]->ptr))
        {
            zobj = createZsetObject();
        } else {
            zobj = createZsetListpackObject();
        }
        dbAdd(c->db,key,zobj);
    }
   // 省略部分代碼
}

我們知道，listpack 是一塊由多個數據項組成的連續內存。而 sorted set 每一項元素是由 member 和 score 兩部分組成。

采用 listpack 存儲插入一個（member、score）數據對的時候，每個 member/score 數據對緊湊排列存儲。

listpack 最大的優勢就是節省內存，查找元素的話只能按順序查找，時間復雜度是 O(n)。正是如此，在少量數據的情況下，才能做到既能節省內存，又不會影響性能。每一步查找前進兩個數據項，也就是跨越一個 member/score 數據對。

3、出招實戰：排行榜

很多地方都會用到排行榜功能，比如微博熱榜、知乎熱榜、電影排行榜、游戲戰力排行等。

以游戲排行榜為例，我教你使用 Sorted Set 實現一個實時游戲高分排行榜。

玩家的得分越高，排行越靠前，如果分數相同則先達到該分數的玩家排在前面，游戲排行榜的提供的功能如下。

按照分數從大到小排名，查詢前 N 位玩家信息。
新注冊玩家，需要把新玩家信息添加到排行榜中。
能查看某個玩家的排名和分數。

Sorted Set 每個元素有兩部分組成（member + score），可利用 score 進行排序，正好滿足我們的場景。用 score 保存玩家的游戲得分，member 保存玩家 ID。

王架構：“分數相同，先達到該分數的排在前面，也就是說，游戲分數相同的情況下，時間戳越小，排名越靠前，咋實現？”

這個問題問得好，既然時間也會影響排名，那就把時間戳考慮到 score 中。

王架構：“有問題，分數越大，排名越靠前；而時間戳越小，排名越靠前。兩個規則相反的，怎么結合在一起。”

好問題，這時候你可以指定一個非常大的時間作為基準時間，比如這個時間就是你當年信誓旦旦的對那個女孩說：“如果非要在我們的愛上加一個期限，我是希望……一萬年”，也就是 2023 + 10000 年。

執行時間排序值 =（基準時間 - 玩家達到分數時間）/ 基準時間公式計算，得到的結果值一定小于 0，正好可作為 score 小數部分。越早達到，這個值就越大，滿足排序。

最后score = 玩家游戲分 + ((基準時間 - 玩家獲得某分數時間) / 基準時間)，就實現了分數相同，先達到該分數的排在前面的功能。

代碼邏輯如下所示。

private double calcScore(int playerScore, long playerScoreTime) {
  return playerScore + (BASE_TIME - playerScoreTime) * 1.0 / BASE_TIME;
}

playerScore，玩家游戲分。
playerScoreTime，玩家獲得分數的時間秒數。
BASE_TIME，基準時間的時間秒數。

想要獲取真正玩家游戲分數的時候，取整數位即可。接下來我來演示一下如何使用 zset 的指令實現排行榜。

假設 BASE_TIME 為 12023 年 1 月 1 日 0 時 0 分 0 秒時間戳秒數 = 317242022400。

更新排行榜

使用指令 ZADD key score member [score member...] 用于新增或者更新玩家排行榜。如下指令表示新增了 4 個玩家信息到排行榜。leaderboard:339 作為 key，表示區服 339 戰力排行榜，玩家 2 和玩家 3 的戰力都是 500 分，玩家 3 比玩家 2 先到達 500 戰力。

redis> ZADD leaderboard:339 2500.994707057989 player:1
(integer) 1
redis> ZADD leaderboard:339 500.99470705798905 player:2
(integer) 1
redis> ZADD leaderboard:339 500.9947097814618 player:3
(integer) 1
redis> ZADD leaderboard:339 987770.994707058 player:4
(integer) 1

假設某天玩家 4 的女朋友不在家，他就天天玩游戲，戰力提升到 1987770。執行如下指令，player:4 的 score 機會更新為 1987770.994707055。

ZADD leaderboard:339 1987770.994707055 player:4

獲取 Top 3 玩家排行信息

ZRANGE 命令可以按照排名、score、字典排序進行范圍查詢。語法使用規則。

ZRANGE key start stop [BYSCORE | BYLEX] [REV] [LIMIT offset count] [WITHSCORES]

默認排序是按照 score 由低到高，分數相同則根據 member 字典排序。

REV，可選參數，按照 score 由高到低逆序排序。
LIMIT offset count 可選參數，類似于 MySQL 的使用，需要注意的是， count 為負數則返回所有符合數據。
WITHSCORES 可選參數，返回 score 和 member，返回的格式是 member 1,score 1,…memberN,scoreN。

你可以使用 REV 來實現逆序，WITHSCORES返回 member 和 score。如下指令的一是是從 key 為 leaderboard:339 的 Sorted Set 中按照 score 逆序排序獲取 3 個元素。

> ZRANGE leaderboard:339 0 2 REV WITHSCORES
player:4
1987770.9947070549
player:1
2500.9947070579892
player:3
500.99470978146178

獲取指定玩家排名

我提供了 ZREVRANK指令，用于返回指定 member 的排名，需要注意的是，排名從 0 開始。如下指令查找 player:4 的排名，0 表示第一。

> ZREVRANK leaderboard:339 player:4
0

責任編輯：姜華來源：碼哥字節

Redis Sets