基于TairZset实现分布式架构排行榜 - 云数据库 Tair（兼容 Redis®）

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作为排名起点。