1、是什么

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

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

這是規(guī)則，得記下來。

常見的使用場景：

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

2、修煉心法

Sorted Sets 底層有兩種方式來存儲數(shù)據(jù)。

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

MySQL：“也就是說 listpack 適用于元素個數(shù)不多且元素內(nèi)容不大的場景。

對，使用 listpack 存儲的目的就是節(jié)省內(nèi)存。

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

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

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

?

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

sorted sets 實現(xiàn)源碼主要在以下兩個文件中。

• 結構定義在 server.h。
• 功能實現(xiàn)在 t_zset.c。

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

skiplist + dict

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

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

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

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

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

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

跳表節(jié)點查找

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

如果碰到比待查數(shù)據(jù)值大的節(jié)點時，那就跳到當前節(jié)點的下一層的鏈表繼續(xù)查找。

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

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

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

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

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

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

對經(jīng)典跳表有個直觀的映像后，來看看 Redis 中 skiplist 的實現(xiàn)細節(jié)，Sorted Sets 數(shù)據(jù)結構定義如下。

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

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

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

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

接著繼續(xù)看 skiplist 中每個節(jié)點的定義 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 存儲實際內(nèi)容， double 類型 score 用于保存權重。
• *backward，后退指針，指向該節(jié)點的上一個節(jié)點，便于從尾節(jié)點實現(xiàn)倒序查找。注意，每個節(jié)點只有一個后向指針，只有 level 0 層鏈表是一個雙向鏈表。
• level[]，是一個 zskiplistLevel 結構體類型的柔性數(shù)組。跳表是一個多層的有序鏈表，每一層的節(jié)點也是由指針鏈接起來的，所以數(shù)組中每個元素代表著 skiplist 的一層。

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

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

listpack

MySQL：“根據(jù) zset 結構體定義可知，分別使用了 dict、zskiplist 兩種數(shù)據(jù)結構，listpack 影子都見不著呀?！?/p>

這個問題問得好，使用 listpack 存儲的細節(jié)在源碼文件t_zset.c 中的zaddGenericCommand函數(shù)中體現(xiàn)，部分代碼如下，內(nèi)部會判斷是否使用 listpack 來存儲?！?/p>

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

    // key 不存在則創(chuàng)建 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 或者
        // 元素字節(jié)大小大于 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 是一塊由多個數(shù)據(jù)項組成的連續(xù)內(nèi)存。而 sorted set 每一項元素是由 member 和 score 兩部分組成。

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

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

3、出招實戰(zhàn)：排行榜

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

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

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

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

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

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

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

王架構：“有問題，分數(shù)越大，排名越靠前；而時間戳越小，排名越靠前。兩個規(guī)則相反的，怎么結合在一起?！?/p>

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

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

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

代碼邏輯如下所示。

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

• playerScore，玩家游戲分。
• playerScoreTime，玩家獲得分數(shù)的時間秒數(shù)。
• BASE_TIME，基準時間的時間秒數(shù)。

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

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

更新排行榜

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

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 的女朋友不在家，他就天天玩游戲，戰(zhàn)力提升到 1987770。執(zhí)行如下指令，player:4 的 score 機會更新為 1987770.994707055。

ZADD leaderboard:339 1987770.994707055 player:4

獲取 Top 3 玩家排行信息

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

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

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

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

你可以使用 REV 來實現(xiàn)逆序，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