INTRODUCTION

Leaderboards in video games are an interesting beast. They are used to rank players against one another using some quantifiable criteria such as # of kills, XP, total time played, points in a level, etc. Leaderboards have been an intimate part of my life for almost 3 years now at Agora Games. As such, I’m always looking for ways to improve our leaderboard technology and answer questions like: How do you efficiently insert and rank players in real time? How do you efficiently update and re-rank players in real time? How do you retrieve information about a specific member of a leaderboard? How do you retrieve information about a player and players around them in a leaderboard?

It was the morning of January 1, 2011, I had literally ridden the short bus back from my New Year’s dinner some hours earlier, and I woke up with a desire to make the world more awesome. It’s 2011 and we still don’t have flying cars … so ,,|, future. Where to start? Leaderboards.

LEADERBOARDS USING REDIS

At the studio I had discussed with colleagues the possibility of using Redis, an advanced key-value storage engine, for leaderboards. In less than an hour, I had the set of Redis commands using their sorted set data type (a set of data that is sorted based on an associated “score”) to perform operations on leaderboards such as:

  • Retrieving general information about a leaderboard such as total members or total pages
  • Adding or removing members from a leaderboard
  • Retrieving information about a member in the leaderboard such as their rank or score
  • Updating score information for a member in the leaderboard
  • Retrieving an arbitrary page of leaders from the leaderboard
  • Retrieving the leaders around a given member in a leaderboard, also known as an “Around Me” leaderboard
  • Retrieving information for an arbitrary set of members in a leaderboard, e.g. How do my friends compare against me?

The result of all this is now encapsulated in the Redis libraries in a number of programming languages such as C, C# C++, Lua, etc. The leaderboard gem is merely a semantic wrapper around the underlying Redis commands. It is left as an exercise to the reader to port the leaderboard code to your favorite programming language.

RUBBER MEETS ROAD

Here’s how you’d actually use the library to generate and interact with a ‘highscores’ leaderboard as outlined above.

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  9
 
  10
 
  11
 
  12
 
  13
 
  14
 
  15
 
  16
 
  17
 
  18
 
  19
 
  20
 
  21
 
  22
 
  23
 
  24
 
  25
 
  26
 
  27
 
  28
 
  29
 
  30
 
  31
 
  32
 
  33
 
  34
 
  35
 
  36
 
  37
 
  38
 
  39
 
  40
 
  41
 
  42
 
  43
 
  44
 
  45
 
  46
 
  47
 
  48
 
  49
 
  50
 
  51
 
  52
 
  53
 
  54
 
  55
 
  56
 
  57
 
  58
 
  59
 
  60
 
  61
 
  62
 
  63
 
  
Create a new leaderboard or attach to an existing leaderboard named 'highscores':

   ruby-1.8.7-p302 > highscore_lb = Leaderboard.new('highscores')
   => #<Leaderboard:0x1018e4250 @page_size=25, @port=6379, @host="localhost", @redis_connection=#<Redis client v2.1.1 connected to redis://localhost:6379/0 (Redis v2.1.10)>, @leaderboard_name="highscores"> 
   
If you need to pass in options for Redis, you can do this with the redis_options parameter:

  redis_options = {:host => 'localhost', :port => 6379, :password => 'password', :db => 'some_redis_db'}
  highscore_lb = Leaderboard.new('highscores', redis_options[:host], redis_options[:port], Leaderboard::DEFAULT_PAGE_SIZE, redis_options))

You can set the page size to something other than the default page size (25):

  ruby-1.8.7-p302 > highscore_lb.page_size = 5
   => 5 
  ruby-1.8.7-p302 > highscore_lb
   => #<Leaderboard:0x1018e2130 @leaderboard_name="highscores", @page_size=5, @port=6379, @redis_connection=#<Redis client v2.1.1 connected to redis://localhost:6379/0 (Redis v2.1.10)>, @host="localhost", @redis_options={:host=>"localhost", :port=>6379}>   
  
Add members to your leaderboard:

  ruby-1.8.7-p302 > 1.upto(10) do |index|
  ruby-1.8.7-p302 >     highscore_lb.add_member("member_#{index}", index)
  ruby-1.8.7-p302 ?>  end
   => 1 
  
Get some information about your leaderboard:

  ruby-1.8.7-p302 > highscore_lb.total_members
   => 10 
  ruby-1.8.7-p302 > highscore_lb.total_pages
   => 1 
  
Get some information about a specific member(s) in the leaderboard:

  ruby-1.8.7-p302 > highscore_lb.score_for('member_4')
   => 4.0 
  ruby-1.8.7-p302 > highscore_lb.rank_for('member_4')
   => 7 
  ruby-1.8.7-p302 > highscore_lb.rank_for('member_10')
   => 1 
  
Get page 1 in the leaderboard:

  ruby-1.8.7-p302 > highscore_lb.leaders(1)
	 => [{:member=>"member_10", :rank=>1, :score=>"10"}, {:member=>"member_9", :rank=>2, :score=>"9"}, {:member=>"member_8", :rank=>3, :score=>"8"}, {:member=>"member_7", :rank=>4, :score=>"7"}, {:member=>"member_6", :rank=>5, :score=>"6"}, {:member=>"member_5", :rank=>6, :score=>"5"}, {:member=>"member_4", :rank=>7, :score=>"4"}, {:member=>"member_3", :rank=>8, :score=>"3"}, {:member=>"member_2", :rank=>9, :score=>"2"}, {:member=>"member_1", :rank=>10, :score=>"1"}]

Add more members to your leaderboard:

  ruby-1.8.7-p302 > 50.upto(95) do |index|
  ruby-1.8.7-p302 >     highscore_lb.add_member("member_#{index}", index)
  ruby-1.8.7-p302 ?>  end
   => 50 
  ruby-1.8.7-p302 > highscore_lb.total_pages
   => 3 
  
Get an "Around Me" leaderboard for a member:

  ruby-1.8.7-p302 > highscore_lb.around_me('member_53')
	 => [{:member=>"member_65", :rank=>31, :score=>"65"}, {:member=>"member_64", :rank=>32, :score=>"64"}, {:member=>"member_63", :rank=>33, :score=>"63"}, {:member=>"member_62", :rank=>34, :score=>"62"}, {:member=>"member_61", :rank=>35, :score=>"61"}, {:member=>"member_60", :rank=>36, :score=>"60"}, {:member=>"member_59", :rank=>37, :score=>"59"}, {:member=>"member_58", :rank=>38, :score=>"58"}, {:member=>"member_57", :rank=>39, :score=>"57"}, {:member=>"member_56", :rank=>40, :score=>"56"}, {:member=>"member_55", :rank=>41, :score=>"55"}, {:member=>"member_54", :rank=>42, :score=>"54"}, {:member=>"member_53", :rank=>43, :score=>"53"}, {:member=>"member_52", :rank=>44, :score=>"52"}, {:member=>"member_51", :rank=>45, :score=>"51"}, {:member=>"member_50", :rank=>46, :score=>"50"}, {:member=>"member_10", :rank=>47, :score=>"10"}, {:member=>"member_9", :rank=>48, :score=>"9"}, {:member=>"member_8", :rank=>49, :score=>"8"}, {:member=>"member_7", :rank=>50, :score=>"7"}, {:member=>"member_6", :rank=>51, :score=>"6"}, {:member=>"member_5", :rank=>52, :score=>"5"}, {:member=>"member_4", :rank=>53, :score=>"4"}, {:member=>"member_3", :rank=>54, :score=>"3"}, {:member=>"member_2", :rank=>55, :score=>"2"}]	

Get rank and score for an arbitrary list of members (e.g. friends):

  ruby-1.8.7-p302 > highscore_lb.ranked_in_list(['member_1', 'member_62', 'member_67'], true)
   => [{:rank=>55, :member=>"member_1", :score=>1.0}, {:rank=>33, :member=>"member_62", :score=>62.0}, {:rank=>28, :member=>"member_67", :score=>67.0}]

Let’s cover a few more scenarios in-depth as to what calls you might make.

I’ve based Scenario 1 and 2 from LittleBigPlanet. NOTE: I have absolutely no idea if this is what actually happens in that game.

Scenario 1: Player finishes a level in game, upload player’s score (add_member), display to the player the scores around them (set page_size and use around_me call for player).

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  9
 
  10
 
  11
 
  12
 
  13
 
  14
 
  15
 
  16
 
  17
 
  18
 
  19
 
  
fossil:leaderboard dczarnecki$ irb
ruby-1.8.7-p302 > require 'rubygems'
 => true 
ruby-1.8.7-p302 > require 'leaderboard'
 => true 
ruby-1.8.7-p302 > highscore_lb = Leaderboard.new('highscores')
 => #<Leaderboard:0x1011b23b0 @leaderboard_name="highscores", @page_size=25, @port=6379, @redis_connection=#<Redis client v2.1.1 connected to redis://localhost:6379/0 (Redis v2.0.4)>, @host="localhost", @redis_options={:host=>"localhost", :port=>6379}> 
ruby-1.8.7-p302 > 1.upto(10) do |index|
ruby-1.8.7-p302 >     highscore_lb.add_member("member_#{index}", index)
ruby-1.8.7-p302 ?>  end
 => 1 
ruby-1.8.7-p302 > highscore_lb.add_member('DavidCzarnecki', 6)
 => true 
ruby-1.8.7-p302 > highscore_lb.page_size = 5
 => 5 
ruby-1.8.7-p302 > highscore_lb.around_me('DavidCzarnecki')
 => [{:member=>"member_7", :score=>"7", :rank=>4}, {:member=>"member_6", :score=>"6", :rank=>5}, {:member=>"DavidCzarnecki", :score=>"6", :rank=>6}, {:member=>"member_5", :score=>"5", :rank=>7}, {:member=>"member_4", :score=>"4", :rank=>8}] 
ruby-1.8.7-p302 >

Scenario 2: Player finishes same level in game, update player’s score (add_member), display to the player the scores around them (set page_size and use around_me call for player). Note, you can call add_member again, because under the hood in Redis, it will just update the player’s score (if it exists) and re-rank.

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  
ruby-1.8.7-p302 > highscore_lb.add_member('DavidCzarnecki', 15)
 => false 
ruby-1.8.7-p302 > highscore_lb.page_size = 5
 => 5 
ruby-1.8.7-p302 > highscore_lb.around_me('DavidCzarnecki')
 => [{:member=>"DavidCzarnecki", :score=>"15", :rank=>1}, {:member=>"member_10", :score=>"10", :rank=>2}, {:member=>"member_9", :score=>"9", :rank=>3}, {:member=>"member_8", :score=>"8", :rank=>4}, {:member=>"member_7", :score=>"7", :rank=>5}] 
ruby-1.8.7-p302 >

I’ve based Scenario 3 and 4 from Call of Duty: Black Ops playing a wager match. NOTE: I have absolutely no idea if this is what actually happens in that game. Also, in Scenario 3 and 4, you could certainly use the add_member call with the player’s total earnings. I simply want to illustrate the delta call (change_score_for).

Scenario 3: Players finish a match and you want to update their winnings (change_score_for) for that match.

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  9
 
  10
 
  
ruby-1.8.7-p302 > total_money_lb = Leaderboard.new('total_money')
 => #<Leaderboard:0x101180680 @leaderboard_name="total_money", @page_size=25, @port=6379, @redis_connection=#<Redis client v2.1.1 connected to redis://localhost:6379/0 (Redis v2.0.4)>, @host="localhost", @redis_options={:host=>"localhost", :port=>6379}> 
ruby-1.8.7-p302 > total_money_lb.change_score_for('DavidCzarnecki', 15)
 => "15" 
ruby-1.8.7-p302 > total_money_lb.change_score_for('ChristianArca', 7)
 => "7" 
ruby-1.8.7-p302 > total_money_lb.leaders(1)
 => [{:member=>"DavidCzarnecki", :score=>"15", :rank=>1}, {:member=>"ChristianArca", :score=>"7", :rank=>2}] 
ruby-1.8.7-p302 >

Scenario 4: Players finish another wager match and you want to update their winnings (change_score_for) for that match. NOTE: If you use negative values, the score is decremented.

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  
ruby-1.8.7-p302 > total_money_lb.change_score_for('DavidCzarnecki', -8)
 => "7" 
ruby-1.8.7-p302 > total_money_lb.change_score_for('ChristianArca', 16)
 => "23" 
ruby-1.8.7-p302 > total_money_lb.leaders(1)
 => [{:member=>"ChristianArca", :score=>"23", :rank=>1}, {:member=>"DavidCzarnecki", :score=>"7", :rank=>2}] 
ruby-1.8.7-p302 >

BUT … REDIS?

It’s scaleable because you can setup master-slave replication to have multiple read-only slaves. I assume all of these are important to you as game developers.

All of this amounts to a Guarantee Fairy right? It makes a man feel good. You figure you put this blog post under your pillow at night, the Guarantee Fairy might come by and leave a quarter, am I right? What’s my point? The point is, how do you know the fairy isn’t a crazy glue sniffer? “Building model airplanes” says the little fairy; well, we’re not buying it. He sneaks into your house once, that’s all it takes. The next thing you know, there’s money missing off the dresser, and your daughter’s knocked up. I’ve seen it a hundred times.

Wait … what?

SCIENCE. IT WORKS B*TCHES

One of the things I love about Redis is that it’s backed by science … mathematics and computer science. In particular, all of the commands give their respective time complexity in Big O notation. If you don’t know what that is, consider yourself fired. Not really. But … still. It’s important because you want to know how long operations are going to take given a particular data set size. This might be useful information from a game developer’s perspective to figure out average or worst-case scenario time estimates for interacting with a leaderboard based on total expected players.

At the request of one of my colleagues, Ola Mork, I did some basic benchmarking. Insert 10 million sequential scores into a leaderboard (in practice you will probably not be doing this all at once) and determine the average time to request an arbirtrary page from the leaderboard. Insert 10 million random scores into a leaderboard (again, in practice you will probably not be doing this all at once) and determine the average time to request an arbitary page from the leaderboard.

The long and short of it is that it’s fast. Negligible difference in terms of leaderboard page retrieval.

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  9
 
  10
 
  11
 
  12
 
  13
 
  14
 
  15
 
  16
 
  17
 
  18
 
  19
 
  20
 
  21
 
  22
 
  23
 
  24
 
  25
 
  26
 
  27
 
  28
 
  29
 
  30
 
  31
 
  32
 
  33
 
  34
 
  35
 
  36
 
  37
 
  38
 
  39
 
  40
 
  41
 
  42
 
  43
 
  44
 
  45
 
  46
 
  47
 
  48
 
  49
 
  50
 
  51
 
  52
 
  
10 million sequential scores insert:

  ruby-1.8.7-p302 > insert_time = Benchmark.measure do
  ruby-1.8.7-p302 >       1.upto(10000000) do |index|
  ruby-1.8.7-p302 >           highscore_lb.add_member("member_#{index}", index)
  ruby-1.8.7-p302 ?>      end
  ruby-1.8.7-p302 ?>  end
   => #<Benchmark::Tms:0x101605660 @label="", @stime=173.61, @total=577.52, @real=911.718175172806, @utime=403.91, @cstime=0.0, @cutime=0.0> 
  
Average time to request an arbitrary page from the leaderboard:

  ruby-1.8.7-p302 > requests_to_make = 50000
   => 50000 
  ruby-1.8.7-p302 > lb_request_time = 0
   => 0 
  ruby-1.8.7-p302 > 1.upto(requests_to_make) do
  ruby-1.8.7-p302 >       lb_request_time += Benchmark.measure do
  ruby-1.8.7-p302 >           highscore_lb.leaders(rand(highscore_lb.total_pages))
  ruby-1.8.7-p302 ?>      end.total
  ruby-1.8.7-p302 ?>  end
   => 1 
  ruby-1.8.7-p302 > 
  ruby-1.8.7-p302 >   p lb_request_time / requests_to_make
  0.001808
   => nil 
  
10 million random scores insert:

  ruby-1.8.7-p302 > insert_time = Benchmark.measure do
  ruby-1.8.7-p302 >       1.upto(10000000) do |index|
  ruby-1.8.7-p302 >           highscore_lb.add_member("member_#{index}", rand(50000000))
  ruby-1.8.7-p302 ?>      end
  ruby-1.8.7-p302 ?>  end
   => #<Benchmark::Tms:0x10164ebf8 @label="", @stime=172.94, @total=577.91, @real=1356.57155895233, @utime=404.97, @cstime=0.0, @cutime=0.0> 
  
Average time to request an arbitrary page from the leaderboard:

  ruby-1.8.7-p302 > requests_to_make = 50000
   => 50000 
  ruby-1.8.7-p302 > lb_request_time = 0
   => 0 
  ruby-1.8.7-p302 > 1.upto(requests_to_make) do
  ruby-1.8.7-p302 >       lb_request_time += Benchmark.measure do
  ruby-1.8.7-p302 >           highscore_lb.leaders(rand(highscore_lb.total_pages))
  ruby-1.8.7-p302 ?>      end.total
  ruby-1.8.7-p302 ?>  end
   => 1 
  ruby-1.8.7-p302 > 
  ruby-1.8.7-p302 >   p lb_request_time / requests_to_make
  0.00179680000000001
   => nil

FIN

Leaderboards may seem complicated, but they are not. Wrapping software like Redis with a set of semantic commands, we have a near complete set of use cases covered for how we might interact with a leaderboard. Finally, it’s fast.

Take a look at the leaderboard gem code and get involved. Comments or code. The choice is yours.

You can find more hilarity over on my Twitter account, CzarneckiD.