TairZset is a data structure developed by Alibaba Cloud that allows you to sort data of the DOUBLE type from different dimensions. You can use the Tair client developed by Alibaba Cloud to implement distributed leaderboards. You can distribute computing tasks to a specific number of keys (also called sub-leaderboards). Tair automatically allocates data to these keys for computing. The default number of keys is 10. You can also customize the number of keys.

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 you create a key (also called leaderboard) and insert 3,000 members into the key, Tair distributes these members to the three keys (also called sub-leaderboards). During a data query, the FindRank(x) command is used to retrieve three ranks of the x member from the three keys: 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.

  • Benefits: This method yields precise ranks.
  • Drawbacks: 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.
  • Benefits: This method is fast in rank retrieval, and the time complexity of this method is O(m).
  • Drawbacks: 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 TairZset commands.

Prerequisites

The Tair client developed by Alibaba Cloud is used. For more information, visit 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
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 from which you want to remove a member, 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))
  1. Use the crc(key) & m syntax to specify the key whose member score and rank you want to retrieve, and then run the EXZSCORE command to retrieve the score and rank of a member in the key.
  2. Run the EXZRANKBYSCORE command several times to individually query the score and rank of the same member in multiple keys, and then add the values to obtain the total score and rank.
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 of the queried 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 the retrieved members. m*O(log(N))
Configuration of an expiration time Run the EXPIRE command. O(1) Specifies 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);

        // If the number of gold medals that participants win is the same, participants are sorted by the number of silver medals that they win. If the number of silver medals is also the same, they are sorted by the number of bronze medals that they win.
        //                    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 used in the preceding sample code.

Parameter Type Description
shardKeySize int The number of sub-leaderboards. The default value is 10. The number of sub-leaderboards cannot be dynamically scaled. Therefore, you must determine how many sub-leaderboards you need before you use sub-leaderboards.
pageSize int The number of entries that can be displayed on each page in a leaderboard. The default value is 10.
reverse boolean Specifies whether to rank members in a leaderboard in descending order. Valid values:
  • false: Members are ranked in ascending order. This is the default value.
  • true: Members are ranked in descending order.
useZeroIndexForRank boolean Specifies whether to use zero-based indexing to rank members in a leaderboard. Valid values:
  • true: Ranks start from 0. This is the default value.
  • false: Ranks start from 1.