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-based clients developed in-house 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.
Method | Description |
---|
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.
|
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.
|
This topic describes how to use precise ranking to implement distributed leaderboards.
Prerequisites
The Tair-based 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 |
---|
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)
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 a member score | 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 a member rank | 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 a member score and rank | Run the EXZSCORE and EXZRANK commands. | O(log(N)) |
|
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 retrieve the top i members from 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 |
---|
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:
|
useZeroIndexForRank | boolean | Valid values:
|