Implement distributed leaderboards by using TairZset - Tair (Redis® OSS-Compatible)

TairZset is a data structure developed by Alibaba Cloud. It allows you to sort score data of the DOUBLE type with respect to 256 dimensions. You can use the Tair clients developed in-house by Alibaba Cloud to implement distributed leaderboards where computing tasks can be distributed to multiple keys (also called sub-leaderboards). For example, if you specify 10 keys, data is distributed to the 10 keys for computing.

Background information

The precise ranking and imprecise ranking (also called linear interpolation) methods can be used to implement distributed leaderboards.

Table 1. Methods to implement distributed leaderboards

Method

Description

Precise ranking (recommended)

In this method, you can distribute data to multiple keys for computing, and query the ranks of the same member in multiple keys to obtain a total rank of the member.

For example, if you specify three keys and create a leaderboard that has 3,000 members, Tair distributes these members to the three keys (or sub-leaderboards). During a data query, the FindRank(x) command is used to retrieve three ranks of the x member from the three keys. Assume that the retrieved ranks are 124, 183, and 156. In this case, the actual rank of the x member is 463, which is the sum of 124, 183, and 156.

Advantages: This method yields precise ranks.
Disadvantages: The time complexity of this method is m*O(log(N)).

Linear interpolation (unavailable for now)

In this method, you can classify members into different ranges by member score, record the number of members and the highest rank in each range, and then use linear interpolation to estimate the ranks of members whose scores fall between the largest and the smallest values in each range.

Advantages: This method is fast in rank retrieval and has a time complexity of O(m).
Disadvantages: This method retrieves estimated ranks that may differ from the actual ranks.

This topic describes how to use precise ranking to implement distributed leaderboards.

Note

For information about the TairZset commands that are used in this topic, see exZset.

Prerequisites

A Tair client developed by Alibaba Cloud is used. For more information, see alibabacloud-tairjedis-sdk.

Implement distributed leaderboards

The following table compares the methods to implement basic features for common leaderboards and distributed leaderboards.

Basic feature	Common leaderboard		Distributed leaderboard
Basic feature	Implementation method	Time complexity	Implementation method	Time complexity
Insertion of a member	Run the EXZADD command.	O(log(N))	Use the crc(key) & m syntax to specify the key into which you want to insert a member, and then run the EXZADD command to insert the member into the key.	O(log(N))
Update of the score of a member	Run the EXZINCRBY command.	O(log(N))	Use the `crc(key) & m` syntax to specify the key whose member score you want to update, and then run the EXZINCRBY command to update the score of a member in the key.	O(log(N))
Removal of a member	Run the EXZREM command.	O(M*log(N))	Use the `crc(key) & m` syntax to specify the key whose member you want to remove, and then run the EXZREM command to remove a member from the key.	O(log(N))
Query of the number of members in a key	Run the EXZCARD command.	O(1)	Run the EXZCARD command several times to individually query the number of members in multiple keys and add the numbers to obtain a total number.	O(m) Note In this column, m indicates the number of shards.
Query of the total number of pages	Run the EXZCARD command to query the number of members in a key, and then divide the number by the number of entries that can be displayed on each page.	O(1)	Run the EXZCARD command several times to individually query the number of members in multiple keys and add the numbers to obtain the total number. Then, divide the total number by the number of entries that can be displayed on each page.	O(m)
Query of the total number of members whose scores are within a specific range	Run the EXZCOUNT command.	O(log(N))	Run the EXZCOUNT command several times to individually query the number of members whose scores are within a specific range in multiple keys, and then add the numbers to obtain the total number.	m*O(log(N))
Removal of the members whose scores are within a specific range	Run the EXZREMRANGEBYSCORE command.	O(log(N)+M)	Run the EXZREMRANGEBYSCORE command several times to individually remove the members whose scores are within a specific range from multiple keys.	m*O(log(N))
Retrieval of the score of a member	Run the EXZSCORE command.	O(1)	Use the `crc(key) & m` syntax to specify the key whose member score you want to retrieve, and then run the EXZSCOR command to retrieve the score of a member in the key.	O(1)
Retrieval of the rank of a member	Run the EXZRANK command.	O(log(N))	Run the EXZRANKBYSCORE command to individually retrieve the rank of the same member in multiple keys, and then add the ranks to obtain the total rank of the member.	m*O(log(N))
Retrieval of the score and rank of a member	Run the EXZSCORE and EXZRANK commands.	O(log(N))	Use the `crc(key) & m` syntax to specify the key whose member score you want to retrieve, and then run the EXZSCORE command to retrieve the score of a member in the key. Run the EXZRANKBYSCORE command to individually retrieve the rank of the same member in multiple keys, and then add the ranks to obtain the total rank of the member.	m*O(log(N))
Query of the top i members	Run the EXZRANGE command.	O(log(N)+M)	Run the EXZRANGE command several times to individually query the top i members in multiple keys, and then obtain the top i members among all retrieved members.	m*O(log(N))
Query of the top i pages of a leaderboard	Run the EXZRANGE command.	O(log(N))	Retrieve the members displayed before the ith page in each sub-leaderboard, rank the retrieved members of all sub-leaderboards, and then obtain the total top i pages of all retrieved members.	m*O(log(N))
Configuration of an expiration time	Run the EXPIRE command.	O(1)	Specify an expiration time for each member.	O(m)
Deletion of a leaderboard	Run the DEL command.	O(N)	Delete all members from a key.	m * O(N)

Sample code:

public class DistributedLeaderBoradExample {
    private static final int shardKeySize = 10;  // Number of sub-leaderboards.
    private static final int pageSize = 10;      // Number of entries that can be displayed on each page in a leaderboard.
    private static final boolean reverse = true; // In this example, members are ranked in descending order.
    private static final boolean useZeroIndexForRank = false; // In this example, ranks start from 1.

    public static void main(String[] args) {
        JedisPool jedisPool = new JedisPool();
        // Create a distributed leaderboard.
        DistributedLeaderBoard dlb = new DistributedLeaderBoard("distributed_leaderboard", jedisPool,
            shardKeySize, pageSize, reverse, useZeroIndexForRank);

        // Rank the participants by the number of their gold medals. If the number of gold medals is the same, rank the participants by the number of their silver medals. If the number of silver medals is also the same, rank the participants by the number of their bronze medals.
        //                    Gold medal Silver medal Bronze medal
        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);

        // Retrieve the rank of Participant A.
        dlb.rankFor("A"); // 1
        System.out.println(dlb.rankFor("A"));

        // Retrieve the top 3 participants.
        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}]
    }

The following table describes the parameters.

Parameter	Type	Description
shardKeySize	int	The number of sub-leaderboards. The default value is 10. The number of sub-leaderboards cannot be dynamically scaled. You must determine the precise number of sub-leaderboards that you need before you use them.
pageSize	int	The number of entries that can be displayed on each page in a leaderboard. The default value is 10.
reverse	boolean	Valid values: false (default): Members are ranked in ascending order. true: Members are ranked in descending order.
useZeroIndexForRank	boolean	Valid values: true (default): Ranks start from 0. false: Ranks start from 1.