Searching for a player’s arbitrary rank in the leaderboard, so that scale is a common complex database problem.
There are several factors that can help you solve a problem, for example:
- Total number of players
- Rate individual players adding points
- Rate new points added (concurrent players * higher)
- Evaluation Range: Limited or Unlimited
- Distribution of points (uniform or their "hot points")
Simplified approach
A typical simplified approach is to count all players with a higher score, for example SELECT count(id) FROM players WHERE score > {playerScore} .
This method works on a small scale, but as your player base grows, it quickly becomes slow and resource intensive (both in MongoDB and Cloud Firestore).
Cloud Firestore does not support count , as it is a non-scalable operation. You will need to implement it on the client side, simply by counting the returned documents. In addition, you can use the Cloud features for Firebase to perform server-side aggregation to avoid the additional bandwidth of returned documents.
Periodic Update
Instead of giving them live ranking, change it to update only as often as every hour. For example, if you look at the overflow stack rating, they are updated only daily.
For this approach, you can schedule a function or schedule app Engine if it takes more than 540 seconds to run. The function will write out a list of players, as in the ladder collection, with a new rank field filled in with the rank of players. When a player scans the ladder now, you can easily get the top X + your own player rating in O (X).
Even better, you could further optimize and explicitly write out the top X as a separate document, so to extract the ladder you only need to read 2 documents, the top X and the player, saving money and speeding them up.
This approach will really work for any number of players and any recording speed, as this is done out of range. You may need to adjust the frequency, but as you grow, depending on your willingness to pay. 30 thousand Players every hour will be $ 0.072 per hour ($ 1.73 per day) if you have not done the optimization (for example, ignore all 0 points, since you know that they are connected last).
Inverted index
In this method, we will create a slightly inverted index. This method works if there is a limited range of points, which is significantly less than the number of players (for example, 0-999 points versus 30 thousand players). It can also work in an unlimited range of points, where the number of unique points is still significantly less than the number of players.
Using a separate fee called “points”, you have a document for each individual account (nonexistent if it is not), with the player_count field.
When a player receives a new total score, you will make 1-2 entries in the scores collection. One entry - from +1 to player_count for their new score, and if this is not the first time, -1 to their old score. This approach works both for “your last score is your current score” and for your “best scores”.
Finding the exact rank of a player is as simple as something like SELECT sum(player_count)+1 FROM scores WHERE score > {playerScore} .
Since Cloud Firestore does not support sum() , you do higher, but summarize on the client side. +1 is because the amount is the number of players above you, so adding 1 gives you a player rating.
Using this approach, you will need to read a maximum of 999 documents, an average of 500ish, to get a player rating, although in practice this will be less if you delete ratings that have zero players.
The speed of recording new points is important for understanding, since you can only update an individual score every 2 seconds * on average, which for a well-distributed range of points from 0 to 999 means 500 new points / second **. You can increase this by using distributed counters for each point.
* Only 1 new score in 2 seconds, as each point generates 2 entries
** Assuming an average game time of 2 minutes, 500 new points per second can support 60,000 simultaneous players without distributed counters. If you use the "Highest Score - Your Current Score", it will be much higher in practice.
N-wood shard
This is by far the most difficult approach, but it can allow you to have both faster and fixed positions in real time for all players. It can be considered as a read-optimized version of the Inverted Index approach above, while the above inverted index approach is a write-optimized version.
You can follow this related article for “Fast and Reliable Ranking in the Data Warehouse” for the overall approach. For this approach, you will want to have a limited score (this is possible with unlimited, but will require changes from below).
I would not recommend this approach, since you will need to do distributed counters for top-level nodes for any ladder with half-frequency updates, which will probably negatively affect the benefits of reading.
Final thoughts
Depending on how often you show the leaderboard for players, you can combine approaches to optimize this a lot more.
Combining the Inverted Index with Periodic Update over a shorter time interval can give you access to O (1) for all players.
As long as the leaderboard is viewed over all players> 4 times during the Periodic Update period, you will save money and get a faster leaderboard.
Essentially every period, say, 5-15 minutes, you read all the documents from scores in descending order. Using this, keep the total number of players_count . Rewrite each point in a new collection called scores_ranking with a new players_above field. This new field contains the current total, excluding current player_count .
To get a player’s rank, all you have to do now is read the player’s score with score_ranking → Their rank is players_above + 1.