TairZset是阿里云自研的数据结构,可实现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相关命令,请参见TairZset命令

前提条件

使用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))
  1. 通过crc(key) & m计算要操作的Key,然后执行EXZSCORE。
  2. 在每一个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作为排名起点。