Online games and trivia apps have grown tremendously in the last 10 years, especially in 2020, Mobile gaming has become a $77.2 billion global business. At the same time, the mobile gaming industry recorded 12% more players in 2020 than in 2019 with over 2.5 billion players. Even though the raging pandemic destroyed many businesses across several industries, the case was reversed for the gaming industry.

One of the most important elements of game-based environments is a leaderboard which sorts players against a particular criterion, usually the underlying score, thus relating the player’s performance to the performance of others.

Implementing a small leaderboard is simple, but when the number of users reaches many thousands, performance problems start to appear. And in our case, we had to show the player’s current ranking along with the leaderboard in real-time after each round, and the delay between the 2 rounds was 20 seconds. Our target was to update in two to three seconds for a leaderboard of at least 1 million active users.

We could use any of the below-mentioned approaches to implement the leaderboard, but even with the lower input size, there is a considerable difference between “in-memory” approaches and the HDD-based, that is, between the data structures running in the RAM and the database solution.

Classic Database Approach

Saving all the information in the database and using DB’s internal functions to calculate the rank(ORDER_BY and RANK()). It is very Inefficient, probably works faster for users under 50000 with time complexity of O(N2), falls down easily when N is high ex:- above 100,000 users.

Bucket Approach (In-memory + Database)

One approach was to divide the scores into buckets.  For example, in our case, we have 10 points for each correct answer, and the maximum a player can score is 400(40 rounds) for a complete contest. So we can have a bucket with attributes (range and counter) stored in Redis. Now, we can divide the scores into buckets (bucket 1 = 0-100), (bucket 2 = 100-200), (bucket 3 = 200-300), (bucket 4 = 300-400) and each time we add the score for a player we will find out the bucket based on the score. Then, we will increment the bucket’s counter and will save the reference of the selected bucket in the player’s record. And when we need to calculate the player’s rank, we’ll fetch the bucket referenced in a player record.  We’ll find out the number of players who have more scores than the current player in the current bucket along with the value of counters of the buckets that precedes the current bucket.  For example(for playerId: 9 the bucket stored in it is 2 and its current score is 130. Now, in order to calculate its rank we need to calculate the number of users who have scores >= 130 + the value of the counter of bucket 3 + the value of the counter of bucket 4  ). Again in this approach, we need to pre-create the buckets and decide their range. Also, the last query to calculate the number of players who have more scores than the current player in a bucket can be slow if our buckets are so big and we have a lot of users in each bucket.

Self Balanced Binary Search Tree (SBBST)

An SBBST is a particular kind of binary search tree, it means each node is linked at most to two subtrees, commonly denoted left and right. A node with no subtrees is called a leaf, and the unique top of the whole tree is called a root. Now, besides these features, a binary search tree must fulfill a condition: each node must be greater than all nodes in its left subtree, and not greater than any in the right subtree. It is called balanced because the height of the left and right subtree of any node differs by not more than one.

In our case, each of the nodes would store 6 attributes, playerId, score, a pointer to the left subtree, a pointer to the right subtree, a pointer to the parent, and size. The size of the current node refers to the number of nodes below and including it.

node.size = (node.left).size + (node.right).size + 1.

Also, note that we will create a node on the left subtree for the duplicate keys i.e for the same score of 2 different players.

Ranking

Before running the algorithm, we need to build and balance the binary tree with the players’ scores. The time complexity of building the tree would be in O(NlogN). Once we have SBBST ready, we can compute the ranking operation using an algorithm as presented below.

getRank(score, playerId) {
 
   const { root } = this._tree;
   if (!root) {
     logger.info("tree doesn't have any root");
     return -1;
   }
 
   const node = this._tree.search(score, playerId);
   if (!node) {
     logger.info("Node doesn't found for this Score", score);
     return -1;
   }
 
   let rank = node.right.size + 1;
   let anotherNode = node;
 
   while (anotherNode != node) {
     if (anotherNode == anotherNode.parent.left) {
       rank = rank + anotherNode.parent.right.size + 1;
     }
     anotherNode = anotherNode.parent;
   }
  return rank;
 }

So, it starts with finding the node based on the given score and playerId, if the node is found it sets the rank as the size of its right child + 1 (including itself) and then it goes up to the root one level at the time and adds the size(no of nodes preceding) to the rank accordingly.

Basically, this algorithm calculates the number of nodes preceding the current node (with given score and playerId) in a reverse in-order walk of the tree.

Now, notice that, in the previous algorithm, once the node x is found it goes up to the root one level at a time, which means that the running time is proportional to the tree height. Therefore, that is why the ranking operation also runs in O(logN).

The total time complexity of the entire ranking algorithm for N players is NlogN(building the tree) + NlogN = 2NlogN

Leaderboard

And if we just need to show the leaderboard, we can take the advantage of the binary search structure of the tree, and traverse the tree in a backward “in-order” direction which will give the sorted list of players in O(N)

Results

From the algorithmic point of view, this solution surpasses typical solutions as the ones based on databases, as well as other “in-memory,” bucket approaches mentioned above, and It achieves speedups when the N(number of players) is too high. So, we tried running some test cases for the above algorithm and the responses were amazingly fast, for example:- We ran this algorithm for 1.5 million users and as it can be seen below, it took just 1 ms to calculate the rank and 522 ms to calculate the Leaderboard.


References:-

https://techcrunch.com/2019/08/22/mobile-gaming-mints-money/ https://www.businessofapps.com/insights/mobile-gaming-industry-statistics-and-trends-for-2021/ https://www.hindawi.com/journals/ijcgt/2018/3234873/