Welcome back! In our previous lesson, we explored how to implement a concurrent inventory system using ConcurrentHashMap
. Today, we will take your skills further by designing a real-time, thread-safe game leaderboard using ConcurrentSkipListMap
. This lesson will help you understand how to manage sorted data in a concurrent environment—an essential feature for real-time applications such as online games or financial systems.
By the end of this lesson, you will:
- Understand how
ConcurrentSkipListMap
maintains sorted data in a thread-safe manner. - Learn how to update entries safely while handling concurrent modifications.
- Retrieve top-scoring entries efficiently, which is crucial for leaderboard management.
These skills will ensure you are well-equipped to handle concurrent data access challenges in applications that require real-time data sorting and updates.
Let’s dive in and start building our concurrent game leaderboard!
Before we start implementing the leaderboard, let's quickly recap ConcurrentSkipListMap
and why it's well-suited for our use case.
ConcurrentSkipListMap
is part of Java's java.util.concurrent
package and is a thread-safe variant of TreeMap
. It maintains keys in a sorted order and allows efficient retrieval of data in real time. One of the primary reasons to use ConcurrentSkipListMap
is that it provides thread-safe access to the elements while ensuring that the entries are always sorted by key.
This makes it ideal for use cases like leaderboards, where you want to maintain a ranking of players by score and allow concurrent updates.
- Thread Safety: Unlike traditional collections,
ConcurrentSkipListMap
allows multiple threads to update the map without the need for explicit synchronization or locking. - Sorted Order: The map automatically sorts entries based on keys (in our case, player scores), making it easy to retrieve the highest-scoring players.
However, by default, ConcurrentSkipListMap
sorts the keys in ascending order. Since we want the leaderboard to rank players with the highest scores first, we need to modify the natural ordering.
To ensure that the highest scores come first, we use Collections.reverseOrder()
when initializing ConcurrentSkipListMap
. This reverses the natural ordering of the keys.
Java1private final ConcurrentSkipListMap<Double, Set<String>> scoreMap = 2 new ConcurrentSkipListMap<>(Collections.reverseOrder());
- Why Use reverseOrder(): By passing
Collections.reverseOrder()
to the constructor, we tell the map to sort the keys in descending order. This way, when we iterate over the map, we start with the highest scores.
We'll begin by constructing the Leaderboard
class, which maintains player scores and ensures they are always sorted with the highest scores first.
Java1import java.util.*; 2import java.util.concurrent.*; 3 4public class Leaderboard { 5 // Map scores to players, with scores in reverse order (highest first) 6 private final ConcurrentSkipListMap<Double, Set<String>> scoreMap = 7 new ConcurrentSkipListMap<>(Collections.reverseOrder()); 8 // Map players to their current scores 9 private final ConcurrentHashMap<String, Double> playerScores = new ConcurrentHashMap<>(); 10}
This class uses two concurrent maps:
ConcurrentSkipListMap
(scoreMap
): Stores scores mapped to sets of player names, ensuring the scores are always in descending order.ConcurrentHashMap
(playerScores
): Quickly retrieves a player’s current score, ensuring we can efficiently update a player's score.
Let’s implement the addScore()
method, which will add or update a player’s score in the leaderboard:
Java1public void addScore(String player, double score) { 2 Double oldScore = playerScores.put(player, score); 3 if (oldScore != null) { 4 // Remove player from old score set 5 scoreMap.computeIfPresent(oldScore, (k, v) -> { 6 v.remove(player); 7 return v.isEmpty() ? null : v; 8 }); 9 } 10 // Add player to new score set 11 scoreMap.compute(score, (k, v) -> { 12 if (v == null) v = ConcurrentHashMap.newKeySet(); 13 v.add(player); 14 return v; 15 }); 16}
-
playerScores.put()
: Stores the player's current score inplayerScores
. If the player already had a score (oldScore
is notnull
), we remove the old score fromscoreMap
. -
Removing Old Score:
computeIfPresent()
: Checks if the old score exists inscoreMap
. If it does, it removes the player from the set of players with that old score.- Cleanup: If no players are left for that score, the score is removed from the map to prevent memory leaks.
-
Adding New Score:
compute()
: Adds the player to the new score inscoreMap
. If the score isn’t already present, a new set is created, and the player is added.- Thread Safety: Using
compute()
ensures atomic updates to the map, preventing race conditions.
This method ensures that each player has only one score entry, and the leaderboard remains sorted by score at all times.
Next, let's implement the getTopNPlayers()
method, which retrieves the top n
players from the leaderboard. This method is crucial because it allows us to efficiently extract the highest-scoring players based on their scores, leveraging the built-in sorting mechanism of ConcurrentSkipListMap
.
Java1public List<String> getTopNPlayers(int n) { 2 List<String> topPlayers = new ArrayList<>(); 3 for (Map.Entry<Double, Set<String>> entry : scoreMap.entrySet()) { 4 for (String player : entry.getValue()) { 5 topPlayers.add(player); 6 if (topPlayers.size() == n) return topPlayers; 7 } 8 } 9 return topPlayers; 10}
Here’s how it works:
-
Iterating Over the
scoreMap
: TheConcurrentSkipListMap
is already sorted in descending order due toreverseOrder()
. This allows us to start from the highest score and work our way down. We use theentrySet()
to iterate over the scores and the corresponding players. -
Fetching Players for Each Score: Since the
scoreMap
stores scores as keys and sets of players as values, we loop through the set of players for each score. Each player is then added to ourtopPlayers
list. -
Limiting to
n
Players: To ensure we only retrieve the topn
players, we check the size of thetopPlayers
list in each iteration. As soon as the list reaches the sizen
, we stop the process and return the result.
This method efficiently fetches the top players in real time by leveraging the sorted order of the ConcurrentSkipListMap
. As scores are updated, this method can quickly return the current highest-ranked players without additional sorting operations.
The design ensures thread safety as well. The ConcurrentSkipListMap
allows concurrent reads and updates without external synchronization, making this method suitable for highly concurrent environments where multiple threads update player scores.
This approach is scalable, allowing you to retrieve top players even in large leaderboards without performance concerns, as the ConcurrentSkipListMap
keeps scores sorted at all times.
Finally, we implement the displayLeaderboard()
method to print the entire leaderboard in order of scores:
Java1public void displayLeaderboard() { 2 scoreMap.forEach((score, players) -> 3 players.forEach(player -> 4 System.out.println(player + ": " + score))); 5}
This method uses the forEach
method to print each player and their score, maintaining the leaderboard’s sorted order.
- Order Maintained: Due to the
reverseOrder()
inscoreMap
, players are displayed from the highest score to the lowest.
Here’s the full implementation of the Leaderboard
class, incorporating all the methods and ensuring the highest scores are ranked first:
Java1import java.util.*; 2import java.util.concurrent.*; 3 4public class Leaderboard { 5 // Map scores to players, with scores in reverse order (highest first) 6 private final ConcurrentSkipListMap<Double, Set<String>> scoreMap = 7 new ConcurrentSkipListMap<>(Collections.reverseOrder()); 8 // Map players to their current scores 9 private final ConcurrentHashMap<String, Double> playerScores = new ConcurrentHashMap<>(); 10 11 // Add or update a player's score 12 public void addScore(String player, double score) { 13 Double oldScore = playerScores.put(player, score); 14 if (oldScore != null) { 15 // Remove player from old score set 16 scoreMap.computeIfPresent(oldScore, (k, v) -> { 17 v.remove(player); 18 return v.isEmpty() ? null : v; 19 }); 20 } 21 // Add player to new score set 22 scoreMap.compute(score, (k, v) -> { 23 if (v == null) v = ConcurrentHashMap.newKeySet(); 24 v.add(player); 25 return v; 26 }); 27 } 28 29 // Get the top n players 30 public List<String> getTopNPlayers(int n) { 31 List<String> topPlayers = new ArrayList<>(); 32 for (Map.Entry<Double, Set<String>> entry : scoreMap.entrySet()) { 33 for (String player : entry.getValue()) { 34 topPlayers.add(player); 35 if (topPlayers.size() == n) return topPlayers; 36 } 37 } 38 return topPlayers; 39 } 40 41 // Display the entire leaderboard 42 public void displayLeaderboard() { 43 scoreMap.forEach((score, players) -> 44 players.forEach(player -> 45 System.out.println(player + ": " + score))); 46 } 47}
Now, let’s simulate multiple threads updating the leaderboard concurrently.
Java1public class Main { 2 public static void main(String[] args) throws InterruptedException { 3 Leaderboard leaderboard = new Leaderboard(); 4 5 // Thread 1 - Adding scores for group 1 of players 6 Thread t1 = new Thread(() -> { 7 leaderboard.addScore("Alice", 1500); 8 leaderboard.addScore("Bob", 1200); 9 }); 10 11 // Thread 2 - Adding scores for group 2 of players 12 Thread t2 = new Thread(() -> { 13 leaderboard.addScore("Charlie", 1800); 14 leaderboard.addScore("Diana", 1600); 15 }); 16 17 // Thread 3 - Updating existing scores 18 Thread t3 = new Thread(() -> { 19 leaderboard.addScore("Alice", 1900); 20 leaderboard.addScore("Eve", 1700); 21 }); 22 23 // Start the threads 24 t1.start(); 25 t2.start(); 26 t3.start(); 27 28 // Wait for all threads to finish 29 t1.join(); 30 t2.join(); 31 t3.join(); 32 33 // Display the final leaderboard 34 System.out.println("=== Final Leaderboard ==="); 35 leaderboard.displayLeaderboard(); 36 37 // Display the top 3 players 38 System.out.println("\n=== Top 3 Players ==="); 39 leaderboard.getTopNPlayers(3).forEach(player -> System.out.println(player)); 40 } 41}
This Main
class simulates multiple threads updating the leaderboard simultaneously. Each thread represents a different group of players adding or updating their scores.
- Thread Coordination: We use
join()
to ensure all threads complete their updates before the final leaderboard is displayed. - Concurrency: Thanks to
ConcurrentSkipListMap
andConcurrentHashMap
, updates are handled in a thread-safe way without explicit locking.
Implementing a real-time, thread-safe leaderboard is essential for many applications, such as games or any competitive environment where rankings are critical. Here's why this matters:
-
Real-Time Data Handling: The
ConcurrentSkipListMap
ensures that all updates and reads happen in a thread-safe and efficient manner. -
Data Consistency: By maintaining a sorted structure, we can easily retrieve the top-performing players in real time.
-
Concurrency: Using concurrent collections like
ConcurrentSkipListMap
allows multiple threads to update the leaderboard without blocking each other, providing smooth and scalable performance.
Incorporating these techniques into your applications will give you the skills to manage real-time data and concurrent updates efficiently.
Now, let’s move on to the practice section and apply these concepts to more advanced challenges!