Leaderboard Ranking with Firebase

Leaderboard ranking with Firebase

Finding an arbitrary player's rank in leaderboard, in a manner that scales is a common hard problem with databases.

There are a few factors that will drive the solution you'll need to pick, such as:

• Total Number players
• Rate that individual players add scores
• Rate that new scores are added (concurrent players * above)
• Score range: Bounded or Unbounded
• Score distribution (uniform, or are their 'hot scores')

Simplistic approach

The typical simplistic approach is to count all players with a higher score, eg SELECT count(id) FROM players WHERE score > {playerScore}.

This method works at low scale, but as your player base grows, it quickly becomes both slow and resource expensive (both in MongoDB and Cloud Firestore).

Cloud Firestore doesn't natively support count as it's a non-scalable operation. You'll need to implement it on the client-side by simply counting the returned documents. Alternatively, you could use Cloud Functions for Firebase to do the aggregation on the server-side to avoid the extra bandwidth of returning documents.

Periodic Update

Rather than giving them a live ranking, change it to only updating every so often, such as every hour. For example, if you look at Stack Overflow's rankings, they are only updated daily.

For this approach, you could schedule a function, or schedule App Engine if it takes longer than 540 seconds to run. The function would write out the player list as in a ladder collection with a new rank field populated with the players rank. When a player views the ladder now, you can easily get the top X + the players own rank in O(X) time.

Better yet, you could further optimize and explicitly write out the top X as a single document as well, so to retrieve the ladder you only need to read 2 documents, top-X & player, saving on money and making it faster.

This approach would really work for any number of players and any write rate since it's done out of band. You might need to adjust the frequency though as you grow depending on your willingness to pay. 30K players each hour would be $0.072 per hour($1.73 per day) unless you did optimizations (e.g, ignore all 0 score players since you know they are tied last).

Inverted Index

In this method, we'll create somewhat of an inverted index. This method works if there is a bounded score range that is significantly smaller want the number of players (e.g, 0-999 scores vs 30K players). It could also work for an unbounded score range where the number of unique scores was still significantly smaller than the number of players.

Using a separate collection called 'scores', you have a document for each individual score (non-existent if no-one has that score) with a field called player_count.

When a player gets a new total score, you'll do 1-2 writes in the scores collection. One write is to +1 to player_count for their new score and if it isn't their first time -1 to their old score. This approach works for both "Your latest score is your current score" and "Your highest score is your current score" style ladders.

Finding out a player's exact rank is as easy as something like SELECT sum(player_count)+1 FROM scores WHERE score > {playerScore}.

Since Cloud Firestore doesn't support sum(), you'd do the above but sum on the client side. The +1 is because the sum is the number of players above you, so adding 1 gives you that player's rank.

Using this approach, you'll need to read a maximum of 999 documents, averaging 500ish to get a players rank, although in practice this will be less if you delete scores that have zero players.

Write rate of new scores is important to understand as you'll only be able to update an individual score once every 2 seconds* on average, which for a perfectly distributed score range from 0-999 would mean 500 new scores/second**. You can increase this by using distributed counters for each score.

* Only 1 new score per 2 seconds since each score generates 2 writes

** Assuming average game time of 2 minute, 500 new scores/second could support 60000 concurrent players without distributed counters. If you're using a "Highest score is your current score" this will be much higher in practice.

Sharded N-ary Tree

This is by far the hardest approach, but could allow you to have both faster and real-time ranking positions for all players. It can be thought of as a read-optimized version of of the Inverted Index approach above, whereas the Inverted Index approach above is a write optimized version of this.

You can follow this related article for 'Fast and Reliable Ranking in Datastore' on a general approach that is applicable. For this approach, you'll want to have a bounded score (it's possible with unbounded, but will require changes from the below).

I wouldn't recommend this approach as you'll need to do distributed counters for the top level nodes for any ladder with semi-frequent updates, which would likely negate the read-time benefits.

Final thoughts

Depending on how often you display the leaderboard for players, you could combine approaches to optimize this a lot more.

Combining 'Inverted Index' with 'Periodic Update' at a shorter time frame can give you O(1) ranking access for all players.

As long as over all players the leaderboard is viewed > 4 times over the duration of the 'Periodic Update' you'll save money and have a faster leaderboard.

Essentially each period, say 5-15 minutes you read all documents from scores in descending order. Using this, keep a running total of players_count. Re-write each score into a new collection called scores_ranking with a new field players_above. This new field contains the running total excluding the current scores player_count.

To get a player's rank, all you need to do now is read the document of the player's score from score_ranking -> Their rank is players_above + 1.

Calculate Leaderboard Ranking in Flutter

This might work: just count number of elements with higher score. I also added _denseRank function, if you want to show it that way (e.g. ranks would go 1,2,2,3,3 etc.). This one just counts number of unique elements with higher score - toSet() is used to remove duplicates - i.e. get unique values.

import 'package:flutter/material.dart';

final Color darkBlue = Color.fromARGB(255, 18, 32, 47);

void main() {
  runApp(MyApp());
}

class MyApp extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      theme: ThemeData.dark().copyWith(scaffoldBackgroundColor: darkBlue),
      debugShowCheckedModeBanner: false,
      home: Scaffold(
        body: Center(
          child: MyWidget(),
        ),
      ),
    );
  }
}

class MyWidget extends StatelessWidget {
  
  final a=<int>[10,9,9,8,8,4,4];
  
    
  int _rank(int index) => a.where( (element) => element>a[index]).length+1;
  
  int _denseRank(int index) => a.where( (element) => element>a[index]).toSet().length+1;
  
  
  
  @override
  Widget build(BuildContext context) {
    return Column(children: <Widget>[
      for (var index=0; index<a.length;index++) Row(children: <Widget>[Text('Index $index'), Text('Rank ${_rank(index)}'), Text('Dense Rank ${_denseRank(index)}')])
    ]);
  }
}

Creating a leaderboard scenario on Cloud Firestore

You can't find the position of a document within a query result except by actually running the query and reading all of them. This makes sorting by score unworkable for just determining rank.

You could reduce the number of writes for updating ranks by grouping ranks into blocks of 10 or 100 and then only updating the rank group when a player moves between them. Absolute rank could be determined by sorting by score within the group.

If you stored these rank groups as single documents this could result in significant savings.

Note that as you increase the number of writers to a document this increases contention so you'd need to balance group size against expected score submission rates to get the result you want.

The techniques in aggregation queries could be adapted to this problem but they essentially have the same cost trade-off you described in your question.

Generating a single Leaderboard document instead of fetching through all users in Firebase

One approach would be to create a separate leaderboard collection with a single document (or one per date, if you care about the data historically) with the leaderboard data (userId, name, current score), then use a Function with a Firestore Trigger that fires anytime a user document is updated and, if the user's score is updated, updates the leaderboard document.

Alternatively, anytime a user's score is updated you could write directly to both the user document and the leaderboard document and skip the function altogether.

Best way to get rank of a user rating with firestore?

If all the data you have is exactly as you have described, you don't have a way to query for just what you want. Firestore doesn't offer any SQL-like aggregation functions like sum() and avg(), so you will, in fact, need to query all of those documents and do math on the client to find the ranks.

If you don't want to read all of these documents every time, you will need to write code to maintain documents with aggregate data that get updated with every new and updated rating. So, if a user wants to add a new rating, you will have to write code that makes sure the rating document gets added, and also the aggregate document maintains whatever ranking you want to pre-compute.

---

Related Topics