基于exZset实现分布式架构排行榜

借助TairJedis客户端,您可以实现分布式架构排行榜(exZset数据结构)的功能。在操作过程中,您只需关注、操作一个Key,而Tair会自动将数据以及计算任务分布至多个子Key中。默认情况下,子Key的数量为10,您无需关注这些子Key的具体情况。通过本方案,您可以轻松实现超10万个元素的排行榜,从而有效避免产生超大Key和热Key。

背景信息

实现分布式架构排行榜有精确排名法和非精确排名法(线性插值法)两种解决方案。

表 1. 实现分布式架构排行榜的解决方案

解决方案

说明

精确排名法(推荐)

将数据分别分配到在不同的Key上进行计算,查询时,查询目标数据在各Key中的排名并进行汇总。

例如自定义底层为3Key,创建一个排行榜(Key)并插入3,000个值(成员),Tair会将3,000个值分别分配到3Key(子排行榜)中。查询时,FindRank(x) 分别在3Key(子排行榜)中获取到了3个排名:124、183156,表示x分别在3Key中排在第124、183156位,那么x的实际排名为463(即124+183+156)。

  • 优势:排名精确。

  • 劣势:获取排名的 时间复杂度m*O(log(N))。

线性插值法(exZset暂未实现)

将数据进行分段,记录每个区间的数量和最高排名(即此区间中的最高排名),对于区间中介于当前区间最低与最高之间的分数,可通过线性插值法进行估算排名。

  • 优势:获取排名速度相对较快,时间复杂度为 O(m)。

  • 劣势:排名为估算的值,可能存在误差。

本方案将使用精确排名法实现分布式架构排行。关于本方案中使用的exZset相关命令,请参见exZset

代码示例

本方案需使用TairJedis(Tair自研)客户端。

  1. 添加pom.xml配置。

            <dependency>
                <groupId>com.aliyun.tair</groupId>
                <artifactId>alibabacloud-tairjedis-sdk</artifactId>
                <version>5.3.1</version>
            </dependency>
  2. 示例代码。

    import io.valkey.JedisPool;
    import io.valkey.JedisPoolConfig;
    import com.aliyun.tair.tairzset.*;
    
    public class DistributedLeaderBoardExample {
        // 配置实例连接地址、端口号、账号密码等信息。
        private static final int DEFAULT_CONNECTION_TIMEOUT = 5000;
        private static final int DEFAULT_SO_TIMEOUT = 2000;
        private static final String HOST = "<r-bp1mx0ydsivrbp****.redis.rds.aliyuncs.com>";
        private static final int PORT = 6379;
        private static final String PASSWORD = "<Pass****word>";
        private static final JedisPoolConfig config = new JedisPoolConfig();
    
        // 配置分布式排行榜信息。
        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(config, HOST, PORT, DEFAULT_CONNECTION_TIMEOUT,
                    DEFAULT_SO_TIMEOUT, PASSWORD, 0, null);
                    
            // 创建分布式架构排行榜,此次以Key名称distributed_leaderboard为例。
            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作为排名起点。

    更多操作请参见alibabacloud-tairjedis-sdk中的com.aliyun.tair.tairzset.DistributedLeaderBoard介绍。

附录:常规排行榜和分布式架构排行榜对比

在实现同一基本功能时,常规排行榜和分布式架构排行榜的实现方案如下:

基本功能

常规排行榜

分布式架构排行榜

实现方案

时间复杂度

实现方案

时间复杂度

插入成员

通过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))

同时获取成员分值和排名

通过EXZSCOREEXZRANK查询。

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)