How to keep track of players' rankings?

Question

I have a Player class with a score attribute:

class Player(game_engine.Player):

    def __init__(self, id):
        super().__init__(id)
        self.score = 0

This score increases/decreases as the player succeeds/fails to do objectives. Now I need to tell the player his rank out of the total amount of players with something like

print('Your rank is {0} out of {1}')

First I thought of having a list of all the players, and whenever anything happens to a player:

1. I check if his score increased or decreased
2. find him in the list
3. move him until his score is in the correct place

But this would be extremely slow. There can be hundreds of thousands of players, and a player can reset his own score to 0 which would mean that I'd have to move everyone after him in the stack. Even finding the player would be O(n).

What I'm looking for is a high performance solution. RAM usage isn't quite as important, although common sense should be used. How could I improve the system to be a lot faster?

Updated info: I'm storing a player's data into a MySQL database with SQLAlchemy everytime he leaves the gameserver, and I load it everytime he joins the server. These are handled through 'player_join' and 'player_leave' events:

@Event('player_join')
def load_player(id):
    """Load player into the global players dict."""
    session = Session()
    query = session.query(Player).filter_by(id=id)
    players[id] = query.one_or_none() or Player(id=id)

@Event('player_leave')
def save_player(id):
    """Save player into the database."""
    session = Session()
    session.add(players[id])
    session.commit()

Also, the player's score is updated upon 'player_kill' event:

@Event('player_kill')
def update_score(id, target_id):
    """Update players' scores upon a kill."""
    players[id].score += 2
    players[target_id].score -= 2

Answer 1

Redis sorted sets help with this exact situation (the documentation uses leader boards as the example usage) http://redis.io/topics/data-types-intro#redis-sorted-sets

• The key commands you care about are ZADD (update player rank) and ZRANK (get rank for specific player). Both operations are O(log(N)) complexity.

Redis can be used as a cache of player ranking. When your application starts, populate redis from the SQL data. When updating player scores in mysql also update redis.

If you have multiple server processes/threads and they could trigger player score updates concurrently then you should also account for the mysql/redis update race condition, eg:

• only update redis from a DB trigger; or
• serialise player score updates; or
• let data get temporarily out of sync and do another cache update after a delay; or
• let data get temporarily out of sync and do a full cache rebuild at fixed intervals

Answer 2

The problem you have is that you want real-time updates against a database, which requires a db query each time. If you instead maintain a list of scores in memory, and update it at a more reasonable frequency (say once an hour, or even once a minute, if your players are really concerned with their rank), then the players will still experience real-time progress vs a score rank, and they can't really tell if there is a short lag in the updates.

With a sorted list of scores in memory, you can instantly get the player's rank (where by instantly, I mean O(lg n) lookup in memory) at the cost of the memory to cache, and of course the time to update the cache when you want to. Compared to a db query of 100k records every time someone wants to glance at their rank, this is a much better option.

Elaborating on the sorted list, you must query the db to get it, but you can keep using it for a while. Maybe you store the last_update, and re-query the db only if this list is "too old". So you update quickly by not trying to update all the time, but rather just enough to feel like real-time.

In order to find someone's rank nearly instantaneously, you use the bisect module, which supports binary search in a sorted list. The scores are sorted when you get them.

from bisect import bisect_left

# suppose scores are 1 through 10
scores = range(1, 11)

# get the insertion index for score 7
# subtract it from len(scores) because bisect expects ascending sort
# but you want a descending rank
print len(scores) - bisect_left(scores, 7)

This says that a 7 score is rank 4, which is correct.