全部产品
Search
文档中心

云原生内存数据库Tair:基于TairZset实现分布式架构排行榜

更新时间:Jul 29, 2024

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

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