Leaderboards in games serve as a dynamic platform where players can showcase their skills, compete with others, and strive for supremacy. They are a driving force in adding an extra layer of excitement while bringing user engagement.

Behind the scenes, the process of gathering and creating a leaderboard involves sifting through extensive data tables, collecting various metrics and numbers, and ultimately delivering accurate and up-to-date information. The pressure intensifies as players continually improve their scores and invite friends to join the competition, demanding swift and precise data retrieval and all of these in realtime.

Leaderboard queries

In our gaming system, each transaction involving in-game currency is logged in the transactions table, with entries categorized as either credits or debits. This ensures an accurate account of users' financial activities within the game.

There are 2 types of leaderboard queries.

  • Player requests a list of top N player.
  • Player requests own rank.

Resolve queries

For both the queries, we have to aggregate all credit transactions, group them by playerID and rank them in descending order of credit sum. Then we either return the top N players or search for user’s rank. This is still OK when we have few hundred users.

As our user base expands, reaching millions, scalability issues arise due to several factors:

  • The straightforward query for leaderboard retrieval can take tens of seconds when dealing with millions of users in a large table.
  • Calculating the rank for a specific user necessitates computing the leaderboard positions for all users.
  • Traditional relational database face challenges in handling continuous user additions, removals, score updates, and ranking computations efficiently.
  • Excessive read queries, especially in a real-time gaming environment, can strain database, potentially resulting in stale data and a suboptimal user experience.

The following narrative will detail our journey in overcoming these challenges and transitioning our leaderboard into a seamless real-time experience using Redis sorted-sets.

Redis Sorted Set

From Redis source code

ZSETs are ordered sets using two data structures to hold the same elements
in order to get O(log(N)) INSERT and REMOVE operations into a sorted
data structure.

A combination of hash-table and skip-list that gives reading, addition and deletion in O(log(N)) and space complexity of O(N).

Sorted Set commands:

  • ZADD: adds score to a member in a key.

    ZADD key score member

  • ZINCRBY: increases score of a member by provided increment value

    ZINCRBY key increment member

  • ZREVRANK: Returns the rank of member in the sorted set stored at key, with the scores ordered from high to low. The rank (or index) is 0-based, which means that the member with the highest score has rank 0. The optional WITHSCORE argument supplements the command’s reply with the score of the element returned.

    ZREVRANK myzset “three” WITHSCORE

  • ZSCORE: Returns the score of member in the sorted set at key.

    ZSCORE key member

  • ZREMRANGEBYRANK: Removes all elements in the sorted set stored at key with rank between start and stop.

    ZREMRANGEBYRANK key start stop

We figured out that sorted-set was the answer to all of our problems.

Now the next set of tasks were

  • Migrate the existing data to redis and create a sorted-set.
  • Implement three leaderboards for daily, weekly and all-time scores.
  • Solve score ties. (player to reach a joint score last should be ranked last; but sorted set sorts it lexicographically).

Ecto migrations

We use Phoenix for game servers and Ecto for db queries. The migration script for parsing transactions table and writing them to redis looks like this

defmodule Deadpool.Repo.Migrations.MigrateDataToLeaderboardRedis do
  use Ecto.Migration

  import Ecto.Query
  alias Deadpool.Repo
  alias Deadpool.Schema.Transaction

  def up do
    # Start a genserver that inits a connection to redis
    _ = Deadpool.RedisLeaderboard.start_link([])

    # Empty the leaderboard as it will be populated anyway
    Deadpool.RedisLeaderboard.remove_alltime_leaderboard()
    Deadpool.RedisLeaderboard.remove_daily_leaderboard()
    Deadpool.RedisLeaderboard.remove_weekly_leaderboard()

    Repo.transaction(fn ->
      Transaction
      # Take all trophies
      |> where([entry], entry.currency == "trophy" and entry.nature == "credit")
      |> select([entry], entry)
      |> Repo.stream()
      |> Stream.each(fn entry -> run_for_each(entry) end)
      |> Stream.run()
    end)
  end

  def down, do: :ok

  def run_for_each(
        %Deadpool.Schema.Transaction{
          player_id: player_id,
          amount: score,
          inserted_at: inserted_at,
          nature: nature
        } = _entry
      ) do

    # upsert and increase score all-time leaderboard
    Deadpool.RedisLeaderboard.increase_score(player_id, score, "alltime")

    # get this week ranges from a helper function
    {start_date, end_date} = get_week_range()

    # if data is of this week then upsert and increase score weekly leaderboard
    case {Date.compare(inserted_at, start_date), Date.compare(inserted_at, end_date)} do
    {:gt, :lt} -> Deadpool.RedisLeaderboard.increase_score(player_id, score, "weekly")
    _ -> :ok
    end

    # if today's data then upsert and increase score daily leaderboard
    if Date.compare(inserted_at, Date.utc_today()) == :eq do
        Deadpool.RedisLeaderboard.increase_score(player_id, score, "daily")
    end
  end
end

Clean redis daily and weekly

We need the daily leaderboard to reset everyday at midnight and weekly leaderboard every sunday midnight. We use cron scheduler that cleans out the sorted-sets for daily leaderboard and weekly leaderboards.

config :deadpool, Deadpool.Scheduler,
  jobs: [
    # Runs every midnight:
    {"@daily", {Deadpool.RedisLeaderboard, :remove_daily_leaderboard, []}},
    # Runs every sunday midnight:
    {"0 0 * * SUN", {Deadpool.RedisLeaderboard, :remove_weekly_leaderboard, []}}
  ]

Joint Ranks

Their are 2 types of ranking we can opt for

Ordinal ranking

Sorted-set sorts the score and in case of ties, sort them lexicographically member-wise. For this we have to ensure, there is minimum clashes of score. But this is not possible if we store only the score value, as people are bound to have same scores.

Since we want the player that reached a certain score first to be ranked higher, we should take time taken into consideration as well. But as we can only have one value in score, we can merge the two.

Redis sorted sets use a double 64-bit floating point number to represent the score and thus is able to represent precisely integer numbers between -(2^53) and +(2^53) included. In more practical terms, all the integers between -9007199254740992 and 9007199254740992 are perfectly representable. Larger integers, or fractions, are internally represented in exponential form, so it is possible that you get only an approximation of the decimal number, or of the very big integer, that you set as score.

@spec leaderboard_score(list(%{score: number, type: :atom})) :: number()
def leaderboard_score(score_priority_list) do
  score_priority_list
  |> Enum.map(&adjusted_score/1)
  |> Enum.join()
  |> String.to_integer()
end

def adjusted_score(%{score: score, type: type}) do
  with %{relation: relation, max_value: max_value} <- score_info(type),
        pad_count <- get_pad_count(max_value),
        new_score <- get_score(score, max_value, relation),
        zero_padded_string_scores <- zero_padded_string_scores(new_score, pad_count) do
    zero_padded_string_scores
  end
end

def score_info(:trophy),  do:
  %{ relation: :direct, max_value: 500 }

def score_info(:retries), do:
  %{ relation: :inverse, max_value: 20 }

def score_info(:time), do:
  %{ relation: :inverse, max_value: 50 }

def get_score(score, _max_score_value, :direct), do: 
  score

def get_score(score, max_score_value, :inverse), do: 
  max_score_value - score

Eventhough redis can save values bigger that +(2^53), it is recommended to not go that far and choose our scores and priorities wisely.

Retrieval works the same way, we have to split the score with the max_value length from least priority value(ie from right).

Dense ranking

In dense ranking, items that compare equally receive the same ranking number, and the next items receive the immediately following ranking number. Equivalently, each item’s ranking number is 1 plus the number of items ranked above it that are distinct with respect to the ranking order.

Thus if A ranks ahead of B and C (which compare equal) which are both ranked ahead of D, then A gets ranking number 1 (“first”), B gets ranking number 2 (“joint second”), C also gets ranking number 2 (“joint second”) and D gets ranking number 3 (“Third”).

This does help when we have a slow paced game and its okay for players to share ranks.

But then sorted set does not provide any APIs for implementing this type of ranking. So we have to

  • create a leaderboard comprising of all the members
  • chunk equal scoring rows together
  • readjust the ranks
  • take top N or find player’s rank.

According to redis docs,ZREVRANGE has a time complexity of O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned (in our case N=M). We will then have to readjust the ranks which again has a time complexity of O(N).

@doc """
  from ->
  [
    %{id: "c", rank: 1, score: "18"},
    %{id: "d", rank: 2, score: "15"},
    %{id: "b", rank: 3, score: "15"},
    %{id: "g", rank: 4, score: "7"},
    %{id: "f", rank: 5, score: "7"},
    %{id: "e", rank: 6, score: "7"},
    %{id: "a", rank: 7, score: "3"}
  ]

  to ->
  [
  %{id: "c", rank: 1, score: "18"},
  %{id: "b", rank: 2, score: "15"},
  %{id: "d", rank: 2, score: "15"},
  %{id: "e", rank: 3, score: "7"},
  %{id: "f", rank: 3, score: "7"},
  %{id: "g", rank: 3, score: "7"},
  %{id: "a", rank: 4, score: "3"}
]
"""
@spec dense_ranking(list(leaderboard_row()), number()) :: list(leaderboard_row())
def dense_ranking(sorted_set_leaderboard, count) do
  chunk_func = fn
    # first element
    element, {} ->
      {:cont, {1, [element]}}

    # when current row score matches the score of the head of current chunk, push it to the chunk stack
    %{score: score} = element, {n, [%{score: score} = _head | _rest] = acc_list} = _acc ->
      {:cont, {n, [element | acc_list]}}

    # when current row score does not match the score of the head of current chunk, create a new chunk stack
    element, {n, _acc_list} = acc ->
      {:cont, acc, {n + 1, [element]}}
  end

  after_func = fn
    [] -> {:cont, []}
    acc -> {:cont, acc, acc}
  end

  sorted_set_leaderboard
  |> Enum.chunk_while({}, chunk_func, after_func)
  |> Enum.map(fn {rank, row_list} ->
    row_list
    |> Enum.map(fn row -> Map.put(row, :rank, rank) end)
  end)
  |> List.flatten()
  |> Enum.take_while(fn %{rank: rank} -> rank < count + 1 end)
end

Standard competition ranking

In competition ranking, items that compare equal receive the same ranking number, and then a gap is left in the ranking numbers. The number of ranking numbers that are left out in this gap is one less than the number of items that compared equal. Equivalently, each item’s ranking number is 1 plus the number of items ranked above it.

@doc """
  from ->
  [
    %{id: "c", rank: 1, score: "18"},
    %{id: "d", rank: 2, score: "15"},
    %{id: "b", rank: 3, score: "15"},
    %{id: "g", rank: 4, score: "7"},
    %{id: "f", rank: 5, score: "7"},
    %{id: "e", rank: 6, score: "7"},
    %{id: "a", rank: 7, score: "3"}
  ]

  to ->
  [
  %{id: "c", rank: 1, score: "18"},
  %{id: "b", rank: 2, score: "15"},
  %{id: "d", rank: 2, score: "15"},
  %{id: "e", rank: 4, score: "7"},
  %{id: "f", rank: 4, score: "7"},
  %{id: "g", rank: 4, score: "7"},
  %{id: "a", rank: 7, score: "3"}
]
"""
@spec standard_ranking(list(leaderboard_row()), number()) :: list(leaderboard_row())
def standard_ranking(sorted_set_leaderboard, count) do
  chunk_func = fn
    # first element
    element, {} ->
      {:cont, {1, 1, [element]}}

    # when current row score matches the score of the head of current chunk, push it to the chunk stack
    %{score: score} = element, {a, n, [%{score: score} = _head | _rest] = acc_list} = _acc ->
      {:cont, {a + 1, n, [element | acc_list]}}

    # when current row score does not match the score of the head of current chunk, create a new chunk stack
    element, {a, _n, _acc_list} = acc ->
      {:cont, acc, {a + 1, a + 1, [element]}}
  end

  after_func = fn
    [] -> {:cont, []}
    acc -> {:cont, acc, acc}
  end

  sorted_set_leaderboard
  |> Enum.chunk_while({}, chunk_func, after_func)
  |> Enum.map(fn {_n, rank, row_list} ->
    row_list
    |> Enum.map(fn row -> Map.put(row, :rank, rank) end)
  end)
  |> List.flatten()
  |> Enum.take_while(fn %{rank: rank} -> rank < count + 1 end)
end

We went with the Dense competition ranking (1223) method, as neither prize money was distributed from a pool nor was there any design problem with players sharing ranks.

Conclusion

With the new pipeling in place the flow looks likes this

leaderboard

The leaderboard system write incoming scores to both redis and database. All leaderboard related operations like fetching player rank and top N players can be done through redis. User data informations like listing recent in-game transactions, can be done by querying table, which can be made faster with indexing and other DB optimizations.

Improvements

Since, leaderboard system is pretty self-contained, it can be moved out to be a stand-alone service with HTTP or Websocket for communication. This will bring into picture better customizations like implementing other leaderboard systems.

FIN.