基于TairZset实现分布式架构排行榜
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 | 取值说明:
|