リアルタイム・ランキングの実装例をRailsで書いてみた

参考文献

http://labs.gree.jp/blog/2010/07/456/ リアルタイム・ランキングを考える
http://www.cyberagent.co.jp/technology/pdf/2011_10.pdf

元ネタについては、GREEさんや、サイバーエージェントさんが同じような方式でした。

これを真似てRailsで実装してみました

動作環境

• Ubuntu 12.04
• Ruby 1.9.3
• Rails 3.2.12
• MySQL 5.5

データ構造

こんな感じの構造です(minとmaxはコードに埋め込んだら実は無くても良い)

schema.rb

  create_table "high_score_partitions", :force => true do |t|
    t.integer  "min"
    t.integer  "max"
    t.integer  "user_count", :default => 0
    t.datetime "created_at",                :null => false
    t.datetime "updated_at",                :null => false
  end
  add_index "high_score_partitions", ["user_count"], :name => "index_high_score_partitions_on_user_count"

  create_table "user_high_scores", :force => true do |t|
    t.integer  "user_id"
    t.integer  "high_score_partition_id"
    t.integer  "score"
    t.datetime "created_at",              :null => false
    t.datetime "updated_at",              :null => false
  end
  add_index "user_high_scores", ["high_score_partition_id"], :name => "index_user_high_scores_on_high_score_partition_id"
  add_index "user_high_scores", ["score"], :name => "index_user_high_scores_on_score"
  add_index "user_high_scores", ["user_id"], :name => "index_user_high_scores_on_user_id"

ダミーデータ類

12万~28万スコアくらいに集中すると想像してパーティションのコードを書いてみました。minとmaxはDBに持たなければ普通にコードを吐き出す感じで問題ないはず。

seeds.rb

pt_max = 128
pt_more = [120000,280000]
pt_last = 0
pt_last_size = 0
pt_max.times.each do |pt_id|
  pt = HighScorePartition.where(id: (pt_id + 1)).first_or_initialize
  if pt_more[0] <= pt_last and pt_last <= pt_more[1]
    size = 3000
  else
    size = 8000
  end
  pt.min = pt_last + pt_last_size
  pt.max = pt_last + pt_last_size + size - 1
  pt_last = pt.min
  pt.user_count = 0
  pt.save!
 pt_last_size = size
 p "#{pt.min} => {id: #{pt.id}, max: #{pt.max}},"
end

実装コード

high_score_partition.rb

class HighScorePartition < ActiveRecord::Base
  attr_accessible :id, :max, :min, :user_count

  has_many :user_high_scores

  def self.target score
    partition_map = HighScorePartitionMap::PARTITIONS.select {|k,v| k <= score and v[:max] >= score}.values.map {|v| v[:id]}
    self.where(id: partition_map)
  end

  def self.upper score
    partition_map = HighScorePartitionMap::PARTITIONS.select {|k,v| k <= score }.values.map {|v| v[:id]}
    self.where(id: partition_map)
  end

end

high_score_permission_rank.rb

class HighScorePartitionMap

  PARTITIONS = {
       0 => {id: 1, max: 7999},
       8000 => {id: 2, max: 15999},
       16000 => {id: 3, max: 23999},
       24000 => {id: 4, max: 31999},
       32000 => {id: 5, max: 39999},
       40000 => {id: 6, max: 47999},
       48000 => {id: 7, max: 55999},
       56000 => {id: 8, max: 63999},
~~中略~~
      740000 => {id: 126, max: 747999},
       748000 => {id: 127, max: 755999},
       756000 => {id: 128, max: 763999}
    }

end

user_high_score.rb

class UserHighScore < ActiveRecord::Base
  belongs_to :user
  belongs_to :high_score_partition
  attr_accessible :score

  before_save do |r|
    partition_map = HighScorePartitionMap::PARTITIONS.select {|k,v| k <= r.score and v[:max] >= r.score}.values.first
    # Not modify
    return true if r.high_score_partition_id == partition_map[:id]
    if r.high_score_partition_id
     where = [r.high_score_partition_id, partition_map[:id]]
    else
     where = partition_map[:id]
    end
    partition = HighScorePartition.where(id: where).lock(true).all.select{|v| v.id == partition_map[:id]}.first

    # Not found partition if cheat?
    raise "Score not found range partition" unless partition
    # Remove user for old pertition
    HighScorePartition.decrement_counter(:user_count, r.high_score_partition_id) if r.high_score_partition_id
    # Add user for new partition
    HighScorePartition.increment_counter(:user_count, partition)
    # New partition
    self.high_score_partition = partition
  end

  def current_rank
    total = HighScorePartition.upper(self.score).sum(:user_count)
    range = self.class.upper_byrange(self.score).count(:score)
    total + range + 1
  end

  def rank_range
    user_count = 0

    users = self.class.upper_byrange(self.score).limit(10).all
    return users if users.length >= 10

    user_count = users.count if users.count
    if self.current_rank >= 10
        partitions = HighScorePartition.order('min DESC').all
    else
        partitions = HighScorePartition.upper(self.score).order('min DESC').all
    end
    partitions.each do |partition|
      users << partition.user_high_scores.limit(10).all
      user_count += partition.user_count
      return users if user_count >= 10
    end
  end

  def self.upper_byrange score
    target = HighScorePartition.target(score).first
    self.where(score: (score + 1)..target.max)
  end

end

upper_byrangeで自分のスコアを入れてしまうと、自分も含め上位 という扱いになるようです。

ダミーテスト

dummy.rb

u1 = User.where(id: 1).first
hs1 = UserHighScore.where(user_id: u1).first_or_initialize
hs1.user = u
hs1.score = 2235
hs1.save!

u2 = User.where(id: 2).first
hs2 = UserHighScore.where(user_id: u2).first_or_initialize
hs2.user = u2
hs2.score = 2234
hs2.save!


u3 = User.where(id: 3).first
hs3 = UserHighScore.where(user_id: u3).first_or_initialize
hs3.user = u3
hs3.score = 4334
hs3.save!

hs1.current_rank
hs2.current_rank
hs3.current_rank

結果は下記の通り

irb

irb(main):020:0* hs1.current_rank
   (0.7ms)  SELECT SUM("high_score_partitions"."user_count") AS sum_id FROM "high_score_partitions" WHERE (min > 2235)
  HighScorePartition Load (0.2ms)  SELECT "high_score_partitions".* FROM "high_score_partitions" WHERE ((min <= 2235 AND 2235 <= max)) LIMIT 1
   (0.2ms)  SELECT COUNT("user_high_scores"."score") FROM "user_high_scores" WHERE ("user_high_scores"."score" BETWEEN 2236 AND 2999)
=> 2
irb(main):021:0> hs2.current_rank
   (0.4ms)  SELECT SUM("high_score_partitions"."user_count") AS sum_id FROM "high_score_partitions" WHERE (min > 2234)
  HighScorePartition Load (0.1ms)  SELECT "high_score_partitions".* FROM "high_score_partitions" WHERE ((min <= 2234 AND 2234 <= max)) LIMIT 1
   (0.1ms)  SELECT COUNT("user_high_scores"."score") FROM "user_high_scores" WHERE ("user_high_scores"."score" BETWEEN 2235 AND 2999)
=> 3
irb(main):022:0> hs3.current_rank
   (0.5ms)  SELECT SUM("high_score_partitions"."user_count") AS sum_id FROM "high_score_partitions" WHERE (min > 4334)
  HighScorePartition Load (0.1ms)  SELECT "high_score_partitions".* FROM "high_score_partitions" WHERE ((min <= 4334 AND 4334 <= max)) LIMIT 1
   (0.1ms)  SELECT COUNT("user_high_scores"."score") FROM "user_high_scores" WHERE ("user_high_scores"."score" BETWEEN 4335 AND 4999)
=> 1

ベンチマーク

スコア数20万件で実施(legacyが普通にスコアから上位10位取得、newが今回の方式)

          user     system      total        real

1time legacy: 0.000000 0.000000 0.000000 ( 0.001784)
1time new: 0.120000 0.030000 0.150000 ( 0.143830)
100time legacy: 0.630000 0.120000 0.750000 ( 2.116978)
100time new: 0.610000 0.250000 0.860000 ( 0.809772)
250time legacy: 1.470000 0.290000 1.760000 ( 4.827297)
250time new: 1.710000 0.520000 2.230000 ( 2.144867)
1000time legacy: 6.780000 1.200000 7.980000 ( 25.567251)
1000time new: 10.640000 2.230000 12.870000 ( 12.602131)

軽く感想

私が掛け持ちしている趣味方面のブラウザゲームで、リアルタイムランキング入れたいって話が上がっていたので、どうやったらいいかな〜？と思っていました。

先人の知恵が世の中には出まわっていたので、参考にしない手は無いと感じました。

ただし、2万件程度であればスロークエリには出るけど、ベンチ上は何も考えず普通にスコアから10位取得したほうが早くなりやすいことも分かってきました。

ツッコミとそのお返事

• パーティションのコード、ymlに書くなりしたら？

  • はい、ごもっともです(書いてた時は、力強くコードに書いていいかなーって思って書いてた

• パーティションは別テーブルに切り出してあげたら？

  • 別テーブルにすることで動的にパーティションを最適値に変動する機能があるならそのほうがいいと思います。ただ、手でやるならエンジニアが触ることになるだろうし、どうせメンテにいれないと更新作業怖すぎなので、コードに書いたら一番はやいし、実は最適解なのかなーと思ってコードにしました。

• Web†DB PRESSの73号あたりにRedisの例があったけど？

  • RDBでやりたかったのと、先に今回のきっかけとなる資料を目にしたのでそっちを試したかったというのが理由です

• ロックしないとダメなの？

  • ロックしないとやっぱ不整合出ました(パーティション上の対象データ件数の総和が何故か実際のデータ数より少ない数字になりました。ロックをちゃんとしたらそういうことは起こりません)

• Rails側であれこれロックとかしてるけど、ストアドとかダメなの？

  • 個人的にはあまり好まれてない気がするので使ってません。

• partition = HighScorePartition.where(id: where).lock(true).all.select{|v| v.id == partition_map[:id]}.first ここ、なんでデータとってきてからselectメソッド叩いてるの？

• ロックする時に、1〜2行ロックしているので、インクリ対象のほうをとってきてました。一度に対象の行をロックしないと、運悪くデッドロックになるパターンが密かに眠ってたりします。また再度クエリ投げるくらいなら2行とってきた後にプログラム的に抽出したほうが早いですし。

勉強会発表

Ruby勉強会札幌 24回にて、ミニセッションという形で発表させて頂きました。