The primary problem solved by leaderboards is ranking – given my score, what is my ranked position against others? And which players are in ranks 17 through 32? Who else is ranked near me? At first this seems to be a simple concept, which would easily be solved using a sorted set in some kind of fast in-memory store. Recently, while researching for a customer solution, I learned that leaderboards can be more complex. In this article I’m going to share a few of my learnings as a precursor to a planned future article demonstrating how to actually build this and some of the things that Momento makes easier for leaderboard developers.
Changes in score result in bulk change across ranks
One challenge with ranking is that a single change of score can mean the rank for large subsets of players changes. In a fully-materialized database like DynamoDB, it means a lot of costly writes - and persisting all that change durably could take a while. So, it seems better to determine the rank of a given player’s score when it is requested.
Determining the rank of a score
The technique for finding rank of a player generally involves storing all the player scores sorted by numeric order (typically in descending order). Then scores are scanned and counted until the player is found. Alternatively, if the total number of score entries is known, a binary search can be used:
- Give me the middle entry in the range of sorted scores - is it my player’s score? Yes? You can now derive your rank - stop here. No? Go to 2.
- Adjust the range to be the upper half if my player’s score is higher than the middle, or the lower half if my player’s score is lower than the middle. Loop back to 1 with reduced range.
You can see that for large numbers of scores, this method converges to find rank much faster than the scan and count method. The larger the number of scores, the longer this operation will take - but it does not increase linearly - it increases logarithmically - so even large leaderboards can perform well - especially if the data structure is stored in memory.
If the leaderboard functionality described to this point works for your requirements, your problem is solved! Just use a Momento Cache sorted set collection to store your player scores, and SortedSetGetRank and SortedSetFetchByRank APIs to retrieve ranking information for your players. You can read more about using sorted sets for a variety of different scoring approaches in our earlier blog. But… there might be a sticking point lurking. Read on, intrepid leaderboarders.
Ordinal rank versus competition rank
The above technique for live determination of rank using a sorted set is dependent on the type of ranking. It only works if the ranking methodology is “ordinal” - which is the case for sorted sets today in Momento Cache. Below is an example of ordinal ranking.
Unfortunately, ordinal ranking is not the desired experience for many leaderboard scenarios - “competition” ranking is the common expectation for online games etc. In the example above, Chris and Daniela both scored 253, yet they are ranked differently - in fact, for any given score there is lexicographic sorting of ranks based on their names. Gamer Daniela might think about changing their name to AAA! In competition ranking, both Chris and Daniela would be ranked #4, and Kirk would be ranked #6.
How can we determine the competition rank of a particular player? It’s a multi-step process:
- SortedSetGetScore to retrieve the score for the player.
- SortedSetFetchByScore (with descending order and count 1) to find the first player who has the same score.
- SortedSetGetRank to retrieve the ordinal rank for the first player with that same score. This is also the competition rank for the player we are actually interested in. Done!
But… finding players who are nearby in the competition ranking or “top 10 by competition rank” type information is harder to solve for. We’ll need a separate sorted set, where the “scores” are actually our competition rankings as determined using the steps above.
Periodic materialization of the rankings
Because a single change in score can result in many changes to competition ranking, we’d need to rebuild our whole competition ranking sorted set every time there’s a score change. That doesn’t seem tenable. To solve for this requirement at scale, we’re going to need to accept a little staleness in the competition rankings. Periodically (perhaps once each 10 minutes? - and only if there are new scores), we’ll rebuild our competition ranking sorted set.
The basic pattern is to retrieve all the players and scores from the live scores sorted set, then iterate through each player determining their competition rank, and write this to our new sorted set with competition rank as the “score”. For the first player, we know their rank is 1, so we can just write that immediately to the rankings sorted set. For the next player (and each subsequent player) we compare their score to the player immediately preceding in the scores sorted set - if it is the same score, we reuse the same rank, but if it is different we use the player’s rank from the scores sorted set as their rank in the rankings sorted set. When we’re done, we update a configuration item in our Momento Cache to list the new sorted set as “current” - the application code checks this first to know which sorted set is the correct one to look at for the latest view of competition rankings. We might choose to keep a few different versions around to be safe, but old views can be deleted by TTL expiry after a while.
Conclusion
Leaderboards can be difficult to solve for if you want competition ranking, but it can be done if you’re willing to accept some eventual consistency for range queries over the competition ranked players. If you build competition ranking with Momento Cache sorted sets using the patterns shared in this article, I’d love to hear about your experiences. In the follow-up article, I’ll show you how I built this solution using Momento and all its newest features. In the meantime, check out what Momento is doing to help game developers. See you next time!
Tweet @pj_naylor, reach out on LinkedIn, or email me. You can also join us to chat about it on Discord.
