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)。
|
線性插值法(TairZset暫未實現) | 將數據進行分段,記錄每個區間的數量和最高排名(即此區間中的最高排名),對于區間中介于當前區間最低與最高之間的分數,可通過線性插值法進行估算排名。
|
本文將使用精確排名法實現分布式架構排行。
關于本文中使用的TairZset相關命令,請參見exZset。
前提條件
使用Tair自研客戶端,更多信息,請參見TairJedis。
實現分布式架構排行榜
在實現同一基本功能時,普通排行榜和分布式架構排行榜的實現方案如下:
基本功能 | 普通排行榜 | 分布式架構排行榜 | ||
實現方案 | 時間復雜度 | 實現方案 | 時間復雜度 | |
插入成員 | 通過EXZADD插入元素。 | O(log(N)) | 通過 | O(log(N)) |
更新成員分值 | 通過EXZINCRBY更新分數。 | O(log(N)) | 通過 | O(log(N)) |
移除成員 | 通過EXZREM移除成員。 | O(M*log(N)) | 通過 | 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) | 通過 | O(1) |
獲取成員排名 | 通過EXZRANK查詢。 | O(log(N)) | 在每一個Key(子排行榜)調用 EXZRANKBYSCORE,然后相加。 | m*O(log(N)) |
同時獲取成員分值和排名 | 通過EXZSCORE和EXZRANK查詢。 | O(log(N)) |
| 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 | 取值說明:
|
useZeroIndexForRank | boolean | 取值說明:
|