如何基於TairZset實現分布式架構熱門排行榜 - Tair

TairZset是阿里雲自研的資料結構，可實現256維度double類型的分值排序。藉助Tair自研用戶端可實現分布式架構熱門排行榜的能力，即可將計算任務分布至多個Key（子熱門排行榜）中完成，您可自訂該Key的數量（預設為10），Tair會將自動資料分散到10個Key中（子熱門排行榜）完成計算，實現分布式架構熱門排行榜。

背景資訊

實現分布式架構熱門排行榜有精確排名法和非精確排名法（線性插值法）兩種解決方案。

表 1. 實現分布式架構熱門排行榜的解決方案

解決方案

說明

精確排名法（推薦）

將資料分別分配到在不同的Key上進行計算，查詢時，查詢目標資料在各Key中的排名並進行匯總。

例如自訂底層為3個Key，建立一個熱門排行榜（Key）並插入3,000個值（成員），Tair會將3,000個值分別分配到3個Key（子熱門排行榜）中。查詢時，FindRank(x) 分別在3個Key（子熱門排行榜）中擷取到了3個排名：124、183和156，表示x分別在3個Key中排在第124、183和156位，那麼x的實際排名為463（即124+183+156）。

優勢：排名精確。
劣勢：擷取排名的時間複雜度為m*O(log(N))。

線性插值法（TairZset暫未實現）

將資料進行分段，記錄每個區間的數量和最高排名（即此區間中的最高排名），對於區間中介於當前區間最低與最高之間的分數，可通過線性插值法進行估算排名。

優勢：擷取排名速度相對較快，時間複雜度為 O(m)。
劣勢：排名為估算的值，可能存在誤差。

本文將使用精確排名法實現分布式架構排行。

說明

關於本文中使用的TairZset相關命令，請參見exZset。

前提條件

使用Tair自研用戶端，更多資訊，請參見TairJedis。

實現分布式架構熱門排行榜

在實現同一準系統時，普通熱門排行榜和分布式架構熱門排行榜的實現方案如下：

準系統	普通熱門排行榜		分布式架構熱門排行榜
準系統	實現方案	時間複雜度	實現方案	時間複雜度
插入成員	通過EXZADD插入元素。	O(log(N))	通過`crc(key) & m`計算要存放的目標Key，然後通過EXZADD插入元素。	O(log(N))
更新成員分值	通過EXZINCRBY更新分數。	O(log(N))	通過`crc(key) & m`計算要存放的目標Key，通過EXZINCRBY更新分數。	O(log(N))
移除成員	通過EXZREM移除成員。	O(M*log(N))	通過`crc(key) & m`計算要操作的Key，然後通過EXZREM移除成員。	O(log(N))
查詢成員數量	通過EXZCARD查詢成員數量。	O(1)	分別通過EXZCARD查詢成員數量，然後相加。	O(m) 說明本列中的m代表分區數
查詢總頁數	通過EXZCARD查詢成員數量，然後除以PAGE_SIZE（每頁可展示的記錄數）。	O(1)	分別通過EXZCARD查詢成員數量，然後相加，得出的結果再除以PAGE_SIZE（每頁可展示的記錄數）。	O(m)
某分數範圍內的總成員數	通過EXZCOUNT查詢。	O(log(N))	分別執行EXZCOUNT，然後合并結果。	m*O(log(N))
移除某分數範圍內的成員	通過EXZREMRANGEBYSCORE移除。	O(log(N)+M)	分別執行EXZREMRANGEBYSCORE。	m*O(log(N))
擷取成員分值	通過EXZSCORE查詢。	O(1)	通過`crc(key) & m`計算要操作的Key，然後執行EXZSCOR。	O(1)
擷取成員排名	通過EXZRANK查詢。	O(log(N))	在每一個Key（子熱門排行榜）調用 EXZRANKBYSCORE，然後相加。	m*O(log(N))
同時擷取成員分值和排名	通過EXZSCORE和EXZRANK查詢。	O(log(N))	通過`crc(key) & m`計算要操作的Key，然後執行EXZSCORE。在每一個Key（子熱門排行榜）調用 EXZRANKBYSCORE，然後相加。	m*O(log(N))
查詢第top i個成員	通過EXZRANGE查詢。	O(log(N)+M)	通過EXZRANGE查詢每個top i，然後合并並得出最終結果。	m*O(log(N))
擷取熱門排行榜第 i 頁	通過EXZRANGE查詢。	O(log(N))	將擷取頁數之前的元素都擷取到，然後排序以獲得最終的頁數。	m*O(log(N))
設定到期時間	通過EXPIRE設定。	O(1)	給每個元素設定到期。	O(m)
刪除熱門排行榜	通過DEL刪除。	O(N)	同時刪除Key中的每個元素。	m * O(N)

範例程式碼如下：

public class DistributedLeaderBoradExample {
    private static final int shardKeySize = 10;  // 底層子熱門排行榜的數量
    private static final int pageSize = 10;      // 熱門排行榜每頁包含的個數
    private static final boolean reverse = true; // 本樣本為從大到小排序
    private static final boolean useZeroIndexForRank = false; // 本樣本以1作為排名起點

    public static void main(String[] args) {
        JedisPool jedisPool = new JedisPool();
        // 建立分布式架構熱門排行榜
        DistributedLeaderBoard dlb = new DistributedLeaderBoard("distributed_leaderboard", jedisPool,
            shardKeySize, pageSize, reverse, useZeroIndexForRank);

        // 如果金牌數相同，按照銀牌數排序，否則繼續按照銅牌
        //                    金牌 銀牌 銅牌
        dlb.addMember("A",     32,  21, 16);
        dlb.addMember("D",     14,  4,  16);
        dlb.addMember("C",     20,  7,  12);
        dlb.addMember("B",     25,  29, 21);
        dlb.addMember("E",     13,  21, 18);
        dlb.addMember("F",     13,  17,  14);

        // 擷取 A 的排名
        dlb.rankFor("A"); // 1
        System.out.println(dlb.rankFor("A"));

        // 擷取top3
        dlb.top(3);
        System.out.println(dlb.top(3));
        // [{"member":"A","score":"32#21#16","rank":1},
        // {"member":"B","score":"25#29#21","rank":2},
        // {"member":"C","score":"20#7#12","rank":3}]
    }

參數說明：

參數	類型	說明
shardKeySize	int	底層子熱門排行榜的數量，預設為10，無法動態擴容，需要在業務初期做好規劃。
pageSize	int	熱門排行榜每頁包含的個數，預設為10。
reverse	boolean	取值說明： false（預設）：按從小到大排序。 true：按從大到小排序。
useZeroIndexForRank	boolean	取值說明： true（預設）：以0作為排名起點。 false：以1作為排名起點。