Quick study on using Redis as a scoring engine

1.setup.md

Redis Groups

Small prototype to look at group and ranking across a lot of users.

Setup

• 10^6 players (can easily bump)
• 20,000 groups
• users are randomly put into 0..5 groups using a good distribution random # generator
• all users are playing a single game
• assuming the setup is a point in time somewhere during the game
• each user will get a score set randomly between 0..99

Demonstrate

• the rank of a particular player across all players
• the ranking of a player across all associated groups
• aggregate ranking across all associated groups that a player is associated with.

Keys

• group:#{group}:members - [set] holds all the ids of the players in the group. #{group} in [0..20,000]
• user:#{user}:groups - [set] holds all the users associated groups. #{user} in [0..10^6]
• group:#{group}:game:1:rankings - [sorted set] holds all the player members current score for the game.
• game:1:rankings - [sorted set] holds all the 10^6 players scores
• user:#{user}:groups:rankings - [sorted set] built on the fly. union of all groups the user is associated with. scores are aggregated.

2.load.coffee

gen   = require 'mersenne'
redis = require('redis').createClient()

[current, max] = [0, Math.pow 10, 6]

load = ->
  if current++ is max
    redis.end() 
  else
    seed current, gen.rand(100), -> load()

seed = (player, score, cb) ->
  console.log "user #{player}" if player % 100 is 0
  multi  = redis.multi()
  groups = gen.rand(5)
  for i in [0..groups]
    group = gen.rand(20000)
    multi.sadd "group:#{group}:members", player
    multi.sadd "user:#{player}:groups", group
    multi.zadd "group:#{group}:game:1:rankings", score, player
    multi.zadd "game:1:rankings", score, player
  multi.exec -> cb()

redis.flushdb -> load()

3.ranking.coffee

redis = require('redis').createClient()

player = process.argv[2] || 1
start  = new Date();

#
# Get the overall score and rank.
#
overall = ->
  key   = "game:1:rankings"
  multi = redis.multi()
  multi.zscore key, player   #O(1)
  multi.zcard  key           #O(1)
  multi.exec (err, data) ->
    score = data[0]
    console.log "Current Score: #{score}"
    rank key, score, data[1]
    groups()
#
# Get the groups associated with the player in context.
#
groups = -> 
  redis.smembers "user:#{player}:groups", (err, data) -> #O(N)
    console.log "Groups: #{data}"
    groups_rank data
   
#
# Rank the player for each associated groups.
#
groups_rank = (groups) ->
  multi = redis.multi()
  keys  = ("group:#{group}:game:1:rankings" for group in groups)
  multi.zscore key, player for key in keys 
  multi.zcard  key         for key in keys 
  multi.exec (err, data) ->
    [scores, players]  = [data[0...groups.length], data[groups.length..]]
    for i in [0...groups.length]
      rank keys[i], scores[i], players[i] 
    across_groups_rank groups, scores, players
#
# union all the groups aggregating the scores
#
across_groups_rank = (groups, scores, players) ->
  keys = ("group:#{group}:game:1:rankings" for group in groups)
  redis.zunionstore ["user:#{player}:groups:rankings", keys.length].concat(keys), ->
    aggregate_rank()
    
#
# the user in context will almost always be the winner since 
# the player is present in all groups
#
aggregate_rank = ->
  key   = "user:#{player}:groups:rankings"
  multi = redis.multi()
  multi.zscore key, player
  multi.zcard  key
  multi.exec (err, data) ->
    score = data[0]
    console.log "Aggregate score is #{score}"
    rank key, score, data[1], true 

#
# redis hack since score doesn't mean rank, ie items with the same score do
# not have the same rank.  this is not what we are looking for
# simply count all the players that are have a score greater than
# this current players
#
rank = (key, score, players, end = false) ->
  redis.zcount key, parseInt(score) + 1, '+inf', (err, data) ->
    console.log "Rank: #{parseInt(data) + 1} of #{players}"
    redis.end() if end
    
overall()

process.on 'exit', ->
  console.log "took #{new Date().getMilliseconds() - start.getMilliseconds()}ms"

4.samples.txt

-- a couple of random picks
coffee rankings.coffee 1
Current Score: 85
Rank: 139859 of 1000000
Groups: 13074
Rank: 26 of 163
Aggregate score is 85
Rank: 26 of 163
took 23ms

$ coffee rankings.coffee 49999
Current Score: 44
Rank: 549821 of 1000000
Groups: 3443,7209
Rank: 89 of 153
Rank: 72 of 141
Aggregate score is 88
Rank: 35 of 293
took 81ms


-- top dogs tied for 1st
$ coffee rankings.coffee 99817
Current Score: 99
Rank: 1 of 1000000
Groups: 12654
Rank: 1 of 141
Aggregate score is 99
Rank: 1 of 141
took 3ms

$ coffee rankings.coffee 984137
Current Score: 99
Rank: 1 of 1000000
Groups: 2747,4983,12231,13627
Rank: 1 of 166
Rank: 1 of 155
Rank: 1 of 150
Rank: 1 of 155
Aggregate score is 396
Rank: 1 of 623
took 5ms

-- redis 127.0.0.1:6379> zcount game:1:rankings  99 99
-- (integer) 10002
--
-- a score of 98 puts all players with 98 into 10003rd place since there are
-- 10002 players with 99
$ coffee rankings.coffee 72495
Current Score: 98
Rank: 10003 of 1000000
Groups: 8243
Rank: 4 of 163
Aggregate score is 98
Rank: 4 of 163
took 5ms

$ coffee rankings.coffee 113649
Current Score: 98
Rank: 10003 of 1000000
Groups: 825,2984,7541,8010
Rank: 3 of 124
Rank: 4 of 131
Rank: 3 of 145
Rank: 4 of 159
Aggregate score is 392
Rank: 1 of 556
took 7ms

-- losers here 
-- redis 127.0.0.1:6379> zcount game:1:rankings  1 +inf
-- (integer) 990054
-- 990054 players with a score of 1 or above
-- 
-- redis 127.0.0.1:6379> zcount game:1:rankings  0 0
-- (integer) 9946
-- 9946 players with a score of 0
$ coffee rankings.coffee 11571
Current Score: 0
Rank: 990055 of 1000000
Groups: 2167,2476,4523,15740,16783
Rank: 167 of 168
Rank: 137 of 138
Rank: 150 of 151
Rank: 143 of 147
Rank: 159 of 160
Aggregate score is 0
Rank: 752 of 760
took 138ms

$ coffee rankings.coffee 148574
Current Score: 0
Rank: 990055 of 1000000
Groups: 1796,1799,4317,12995
Rank: 140 of 141
Rank: 149 of 152
Rank: 134 of 137
Rank: 173 of 175
Aggregate score is 0
Rank: 593 of 602
took 138ms

5.redis.info.txt

redis 127.0.0.1:6379> info
redis_version:2.2.11
redis_git_sha1:00000000
redis_git_dirty:0
arch_bits:64
multiplexing_api:kqueue
process_id:4647
uptime_in_seconds:1477
uptime_in_days:0
lru_clock:1024562
used_cpu_sys:113.55
used_cpu_user:87.98
used_cpu_sys_childrens:0.00
used_cpu_user_childrens:0.00
connected_clients:1
connected_slaves:0
client_longest_output_list:0
client_biggest_input_buf:0
blocked_clients:0
used_memory:609476800
used_memory_human:581.24M
used_memory_rss:635310080
mem_fragmentation_ratio:1.04
use_tcmalloc:0
loading:0
aof_enabled:0
changes_since_last_save:10997902
bgsave_in_progress:0
last_save_time:1310478383
bgrewriteaof_in_progress:0
total_connections_received:14
total_commands_processed:13998123
expired_keys:0
evicted_keys:0
keyspace_hits:10958052
keyspace_misses:1040001
hash_max_zipmap_entries:512
hash_max_zipmap_value:64
pubsub_channels:0
pubsub_patterns:0
vm_enabled:0
role:master
allocation_stats:6=1,7=1,8=3020125,9=112,10=1624818,11=5409930,12=962554,13=14429876,14=4928784,15=8126144,16=46510448,17=34,18=210654,19=16,20=9962,21=17,22=4534,23=386,24=21054480,25=49654,26=496554,27=4958842,28=1519416,29=16,30=260,31=12,32=12052231,33=13522,34=135548,35=1359363,36=1525252,37=35,38=8,39=18,40=3019660,41=3,42=2,43=9,44=18727,45=29,46=1,47=1,48=1019507,49=2,50=1,51=1,52=19746,53=11,56=771298,57=3,58=3,59=5,60=19964,61=1,62=1,63=1,64=40028,65=3,66=1,67=1,68=20003,69=16,70=2,71=3,72=1207280,73=4,74=3,75=1,76=20003,77=3,78=7,79=11,80=20013,81=18,82=20,83=12,84=20025,85=18,86=15,87=12,88=86884,89=11,90=3,91=2,92=20000,93=23,95=3,96=1020006,99=5,100=20000,101=8,103=1,104=31967,105=2,107=4,108=20000,109=2,111=1,112=20000,116=20000,120=823374,124=20000,128=40029,131=3,132=20000,133=10,136=20727,140=20000,144=820390,148=20000,151=2,152=20177,156=20000,160=20000,161=2,164=20000,168=820446,172=20000,175=2,176=20000,180=20000,183=2,184=20015,185=1,187=7,188=20000,189=13,192=820390,193=2,195=5,196=20000,197=5,200=20003,201=1,203=2,204=20000,207=2,208=20000,212=20000,216=619602,220=20000,224=20000,228=20000,232=20000,236=20000,240=619602,244=20000,248=20000,252=20000,>=256=5476120
db0:keys=1040011,expires=0