[erlang-questions] How would you do it?

[Rudolph van Graan]

> I have to rank about 50 000 - 100 000 different players.
> On each score message I have to re-sort whole ranking table.
> It must be very cheap to get:
> top 100 players
> player's rating +/- 10 players about current player
> I expect about 20-50 score messages per seconds
> Size of score message is about 4KB (profile takes most of the space).
Trying to be pragmatic, I would do this:

1. Every player has a unique key (say ID) and this is the key to a Mnesia table that stores the player records.
2. I would have a second table with the rankings, keyed on score.
3. Each slot contains the ID and score of the player at that position: 
- {score,30,{player,200},undefined,20}
- {score,20,{player,5},30,19}
- {score,19,{player,18},20,undefined}
...
So the top player is the one with rank 30, i.e. player 200, the 2nd one is player 5 and the third is player 18. You can get to the first one by reading the first entry or last entry in the table. Each score record contains a "pointer" to the one before and the one after.

The record will look like this:

{score, Score, PlayerID, Next, Previous}

4. The player table is keyed on the player id and contains the player's current score. So in the example above Player 200 will be rank 1 (score 30) and Player 5 will be rank 2 (score 20) etc.

So you can easily get the top N, simply read the records starting at the end (using dirty last) and following the next pointer. That will give you two database reads per entry. If you want to cache this, make a simple gen_server that keeps this list in memory and refreshes every 10 seconds.

4. Process your score messages concurrently, i.e. each operation does the folling
 a) Read the player record according to ID and get the score from the player ID. 
 b) Read the score record using the current score and retrieve the values of "previous" and "next"
 c) Delete the score record and modify "previous" to point to "next" and "next" to point to previous
 d) Insert a new #score{score=NewScore,previous=undefined, next=undefined}
 e) Call mnesia:next(Tab,{score,NewScore}) to get the logical Next and mnesia:prev/2 to get the logical previous
 f) Update the three records with the appropriate next/prev values

(all of this protected by a transaction of course)

This approach is heavy compared to the other approaches suggested, but it gives you distribution for free and no single process bottlenecks. It should be very fast if you use only memory tables and fast enough if you add persistent tables.

Obviously I haven't worked out all the details above - I am sure you can figure that out.

Hope it helps.
Rudolph van Graan

Please have a look at my blogs:

- Random Views of London -- A photographer's interpretation of London
  http://randomlondonview.blogspot.co.uk/


On 2 Jul 2012, at 11:29, Max Bourinov wrote:

> Hi Erlangers,
> 
> I need to build a ranking system for online game.
> 
> I think I will have a ranking gen_server that will accept cast messages like this: {score, Player :: profile(), Score :: integer()}.
> 
> So, the question is what would be most appropriate data structure if:
> I have to rank about 50 000 - 100 000 different players.
> On each score message I have to re-sort whole ranking table.
> It must be very cheap to get:
> top 100 players
> player's rating +/- 10 players about current player
> I expect about 20-50 score messages per seconds
> Size of score message is about 4KB (profile takes most of the space).
> 
> Any ideas or suggestions are welcome!
> 
> Best regards,
> Max
> 
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120706/1fc43c9f/attachment.htm>