天天看點
傳回

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

作者：Java架構日記

1. 是什麼

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

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

這是規則，得記下來。

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

常見的使用場景：

  • 排行榜，比如維護大型線上遊戲中根據分數排名的 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 是不能忍的。

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

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

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

這樣 level 0 和 level 1 分别形成兩個連結清單，level 1 層的連結清單節點個數隻有 2 個（6、26）。

跳表節點查找

查找資料總是從最高層開始比較，如果節點儲存的值比待查資料小，跳表就繼續通路該層的下一個節點；

如果碰到比待查資料值大的節點時，那就跳到目前節點的下一層的連結清單繼續查找。

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

Redis Sorted Set 底層實作原理深度解讀與排行榜實戰
  • 從 level 1 開始，17 與 6 比較，值大于節點，繼續與下一個節點比較。
  • 與 26 比較，17 < 26，回到原節點，跳到目前節點的 level 0 層連結清單，與下一個節點比較，找到目标 17。

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

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

為了避免這個問題，它不要求上下相鄰的兩層連結清單節點個數有嚴格的比例關系，而是為每個節點随機出一個層數，這樣插入節點隻需要修改前後指針。

如下圖是一個有 4 層連結清單的 skiplist，假設我們要查找 26，下圖給出了查找經曆過的路徑。

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

對經典跳表有個直覺的映像後，來看看 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 的可能結構。

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

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 資料對。

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

3. 出招實戰：排行榜

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

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

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

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

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

❝

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

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

❝

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

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

執行時間排序值 =（基準時間 - 玩家達到分數時間）/ 基準時間公式計算，得到的結果值一定小于 1，正好可作為 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

原文出自公衆号：碼哥位元組

原文連結：https://mp.weixin.qq.com/s/gXcm7LSicql06ZA5W7J39w

底層實作 實作原理 Redis
上一篇: ·随着超高清視訊、雲辦公、vr、直播、智能家居等業務的快速發展，人們對于高品質、高速率、網絡的需求不斷增加，為滿足使用者家
下一篇: 時間序列的季節性：3種模式及8種模組化方法

繼續閱讀