The TairJedis client lets you implement distributed leaderboards using the exZset data structure. You only need to work with a single key. Tair automatically distributes the data and computation tasks across multiple sub-keys. By default, 10 sub-keys are used, and you do not need to manage their details. This solution helps you easily create leaderboards with more than 100,000 members and avoid large keys and hot keys.
Background information
Two solutions are available to implement distributed leaderboards: the precise ranking method and the imprecise ranking method (linear interpolation).
Table 1. Solutions for implementing distributed leaderboards
Solution | Description |
Precise ranking (recommended) | Distribute data to different keys for computation. When you query, find the rank of the target data in each key and then sum the ranks. For example, assume you use three underlying keys. If you create a leaderboard and insert 3,000 members, Tair distributes these members across the three sub-leaderboards. To find the rank of member x, the FindRank(x) operation queries the three sub-leaderboards. If the ranks returned are 124, 183, and 156, the actual rank of member x is 463 (124 + 183 + 156).
|
Linear interpolation (not yet implemented in exZset) | This method divides data into segments. It records the number of members and the highest rank for each segment. For scores that fall between the lowest and highest values in a segment, linear interpolation is used to estimate the rank.
|
This solution implements a distributed leaderboard using the precise ranking method. For more information about the exZset commands used in this solution, see exZset.
Code example
This solution requires the TairJedis client, which is developed by Tair.
Add the pom.xml configuration.
<dependency> <groupId>com.aliyun.tair</groupId> <artifactId>alibabacloud-tairjedis-sdk</artifactId> <version>5.3.1</version> </dependency>Sample code.
import io.valkey.JedisPool; import io.valkey.JedisPoolConfig; import com.aliyun.tair.tairzset.*; public class DistributedLeaderBoardExample { // Configure the instance endpoint, port, password, and other information. 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(); // Configure the distributed leaderboard. private static final int shardKeySize = 10; // The number of underlying sub-leaderboards. private static final int pageSize = 10; // The number of members on each page of the leaderboard. private static final boolean reverse = true; // In this example, members are sorted 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(config, HOST, PORT, DEFAULT_CONNECTION_TIMEOUT, DEFAULT_SO_TIMEOUT, PASSWORD, 0, null); // Create a distributed leaderboard. In this example, the key is named distributed_leaderboard. DistributedLeaderBoard dlb = new DistributedLeaderBoard("distributed_leaderboard", jedisPool, shardKeySize, pageSize, reverse, useZeroIndexForRank); // If the number of gold medals is the same, sort by the number of silver medals. If the number of silver medals is also the same, sort by the number of bronze medals. // Gold Silver Bronze 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); // Get the rank of A. dlb.rankFor("A"); // 1 System.out.println(dlb.rankFor("A")); // Get the top 3. 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}] } }Parameters:
Parameter
Type
Description
shardKeySize
int
The number of underlying sub-leaderboards. The default value is 10. This number cannot be dynamically scaled out. Plan for this number in the initial phase of your service.
pageSize
int
The number of members on each page of the leaderboard. The default value is 10.
reverse
boolean
Valid values:
false (default): Sorts in ascending order.
true: Sorts in descending order.
useZeroIndexForRank
boolean
Valid values:
true (default): Ranks start from 0.
false: Ranks start from 1.
For more operations, see the com.aliyun.tair.tairzset.DistributedLeaderBoard class in alibabacloud-tairjedis-sdk.
Appendix: Comparison between conventional and distributed leaderboards
The following table compares the implementation of basic features for conventional and distributed leaderboards.
Basic feature | Conventional leaderboard | Distributed leaderboard | ||
Implementation | Time complexity | Implementation | Time complexity | |
Insert a member | Use EXZADD to insert an element. | O(log(N)) | Calculate the target key using | O(log(N)) |
Update a member's score | Use EXZINCRBY to update the score. | O(log(N)) | Calculate the target key using | O(log(N)) |
Remove a member | Use EXZREM to remove a member. | O(M*log(N)) | Calculate the target key using | O(log(N)) |
Query the number of members | Use EXZCARD to query the number of members. | O(1) | Use EXZCARD to query the number of members in each sub-key, and then sum the results. | O(m) Note In this column, m indicates the number of shards. |
Query the total number of pages | Use EXZCARD to query the number of members, and then divide the result by PAGE_SIZE (the number of records per page). | O(1) | Use EXZCARD to query the number of members in each sub-key, sum the results, and then divide the total by PAGE_SIZE (the number of records per page). | O(m) |
Total number of members within a score range | Use EXZCOUNT to query. | O(log(N)) | Run EXZCOUNT on each sub-key, and then merge the results. | m × O(log(N)) |
Remove members within a score range | Use EXZREMRANGEBYSCORE to remove members. | O(log(N)+M) | Run EXZREMRANGEBYSCORE on each sub-key. | m × O(log(N)) |
Get a member's score | Use EXZSCORE to query. | O(1) | Calculate the target key using | O(1) |
Get a member's rank | Use EXZRANK to query. | O(log(N)) | Call EXZRANKBYSCORE on each sub-key, and then sum the results. | m × O(log(N)) |
Get a member's score and rank at the same time | Use EXZSCORE and EXZRANK to query. | O(log(N)) |
| m × O(log(N)) |
Query the top i-th member | Use EXZRANGE to query. | O(log(N)+M) | Use EXZRANGE to query the top i members from each sub-key, and then merge the results to find the final top i members. | m × O(log(N)) |
Get page i of the leaderboard | Use EXZRANGE to query. | O(log(N)) | Retrieve all members before the target page from each sub-key, and then sort them to get the final page. | m × O(log(N)) |
Set an expiration time | Use EXPIRE to set the time. | O(1) | Set an expiration time for each sub-key. | O(m) |
Delete a leaderboard | Use DEL to delete. | O(N) | Delete each of the sub-keys. | m × O(N) |