15行で書くソーシャルゲームのリアルタイム・ランキング

これはgumi Engineer's Diaryに書いたものを修正・転載したものです。

はじめに
ソーシャルアプリでは、DBへの負荷を減らすためにKVSを使ったりすることが多いです。
そこで今回は実際にKVSを使用している例として、リアルタイム・ランキングを取り上げたいと思います。
一見難しそうに思えますが、リアルタイムでのランキング処理なんてメインのロジックは15行もあれば書けちゃうんですよ！

リアルタイム・ランキング
ゲームを扱うコンテンツ・サービスにおいてランキングは重要な要素となりますが、データの件数が多くなると単純な方法では負荷が高くなってしまうので難しいです。
その辺の難しさや解決策は GREE Engineer's Blog の「リアルタイム・ランキングを考える」にまとまっているので読んでみて頂けると理解がしやすいんじゃないかと思います。
ただ、GREEさんの記事は素晴らしいのですが、実際どうやっているのか等の細かいところまでは書かれていません。
なので、この記事では実際の実装も含めて出し惜しみをせずに紹介したいと思います。

gumi の取り組み
GREEさんのブログではMySQLを例として説明されていましたが、gumiでは頻繁に更新があるランキングのデータはKVSのTokyoTyrantに格納しています。
例えば勝ち数ランキングですと、キー：バリューが、勝ち数を：順位として入っています。
具体的にはこんな感じです。

'Ranking::Win::0' : 100
'Ranking::Win::1' : 50
'Ranking::Win::2' : 30
'Ranking::Win::3' : 10
'Ranking::Win::4' : 1

勝ち数が２の人の順位は 'Ranking::Win::2' で引いて返ってくる 30位となるわけです。
こうやってデータが格納されている状態なら、順位を求めるのは簡単ですし、負荷もかかりません。
素晴らしいですね！

でも、どうやってこのような状態を作っているのでしょうか？
先月リリースしたハッピーモデルではこんな15行程度のコードで行っています。

    def add_point(point, add=1):
        """ 
        値が増えた際の順位の更新
         point : 変化前の値
         add : 増加量
         """
        # 変化前の点数より上にプレイヤーが一人増えるため  
        # 変化前の点数に対応する順位を+1する。
        now_key = "Ranking::Win::%d" % point
        tokyotyrant.addint(now_key)

	# 1以上増えた場合は間の順位も+1する。
        for i in range(0, add):
            next_key = "Ranking::Win::%d" % (point+add-i)
            next = tokyotyrant.getint(next_key)
            # 今までになかった場合は1位を入れる。
            if not next:
                if i == 0:
                    tokyotyrant.putint(next_key, 1)
                else:
                    tokyotyrant.putint(next_key, 2)
            elif i != 0:
                tokyotyrant.addint(next_key)

コードだけ見てもよくわからないですね！
ごめんなさい。説明します。

ランキングの仕組み
初期状態はこんな感じです。

'Ranking::Win::0' : 1
人数：いっぱい

リリース時はまだ誰も勝っている人がいないので、全員１位です。

次に誰かが勝つとこうなります。

'Ranking::Win::0' : 1 → 2
人数：いっぱい
'Ranking::Win::1' : 1 # New Key
人数：１人

１勝した人だけが１位で残りが２位となります。

では、他の０勝の人が勝つとどうなるのでしょうか？

'Ranking::Win::0' : 2 → 3
人数：いっぱい
'Ranking::Win::1' : 1
人数：２人

同率１位の人が２人いるので、残りの人は３位です。

１勝している人が更に勝った場合は

'Ranking::Win::0' : 3
人数：いっぱい
'Ranking::Win::1' : 1 → 2
人数：１人
'Ranking::Win::2' : 1 # New Key
人数：１人

基本的にはコメントにもあるように
「変化前の勝ち数より上にプレイヤーが一人増えるため、変化前の勝ち数に対応する順位を+1する。」
これだけで順位テーブルが適切に更新されます。
簡単ですね！

まとめ
gumiでは、こんな感じでランキングを実装しています。

今の実装では下がることがある値（勝ち数ではなく勝率など）には対応していないのですが、それにも今後対応する予定です。

今回紹介した方法は (その間の全ての順位を更新する必要があるため) １勝の人が100勝になるなどの急激な値の変化には向いてないのですが、人数に関わらず負荷が一定でトランザクションの必要がないという素晴らしい方法です。

リアルタイム・ランキングの実装で悩んでいる方がいましたら、是非是非使ってください！