ゲームのイベントランキングで同一スコアを取り扱うために

はじめまして、技術統括部エンジニアの伊藤 (@kanataxa) です。

このブログが開設されて大分日が経ってしまいましたが、二本目の記事を書かせていただきます。

今回は、ソーシャルゲームには欠かせないランキングについての記事になります。

はじめに

ランキングの実装をする方法はいくつかあると思いますが、弊社では Redis のSorted setsを採用しています。

Sorted sets を採用しているのはすでに枯れた技術であること、また非常に簡単にランキングを作成することができるためです。実際にはもう少し複雑なことをしていますが、基本的には以下のような単純な操作でランキングを作ることができます。

1. redisにランキング用のSorted setを作る
2. 各ユーザのスコアを追加する

つまりランキングを実装したい機能があった場合には、特定のSorted setsに対して ZADD などの用意されたコマンドを組み合わせて、アプリケーション側からスコアを redis に送るだけで実装が可能です。あとは redis がよしなにそのスコアをみて順位付け(ソート)を行ってくれます。

これによりランキングの作成が非常に簡略化されましたが、ランキングを実装していく上で避けては通れない問題が一つ発生しました。同一スコアの取り扱いです。

Sorted sets は以下のような仕様でソートします。

If A and B are two elements with a different score, then A > B if A.score is > B.score.
If A and B have exactly the same score, then A > B if the A string is lexicographically greater than the B string. A and B strings can't be equal since sorted sets only have unique elements.

つまり日本語で以下のように言い換えることができると思います。

任意のkeyとscoreを持つAとBに対して、

1. A.score > B.score ならば A > B となる。
2. A.score == B.score ならばkeyの辞書順判断し、 A.key > B.key ならば A > B となる。また、keyはユニークであるため、A.key != B.key は必ず保証される。

この仕様により、同一スコアのユーザに対して Sorted sets は完全に辞書順で優劣をつけてしまいます。

例えば、同一スコアの場合は先にそのスコアを出したユーザを上にしたいとしても、ただ単純にスコアを積むだけでは Sorted sets はゲーム側の仕様を加味することはしません。

本記事では、実際にイベントなどでランキングを運用していく上で、Sorted sets で同一スコアをうまく扱うためにどういう工夫をしているか詳しく説明していこうと思います。

ランキングを実装するにあたって(おまけ)

さて少し話はそれてしまいますが、なぜ Sorted sets を用いてランキングを実装することにしたのか、ついでに本項目で簡単に述べようと思います。

もし Sorted sets についてすでに知見のある方や同一スコアについてのみ知りたい方は、この項目を読まなくても問題ないように書いていますので飛ばしてください。

なぜ Sorted setsを使うのか

どの機能を実装する場合にも言えることですが、仕様を満たす機能の実装はだいたいにおいて複数の実装方法があります。

この複数の選択肢からコストや実装容易性などを加味して最も適したものを選んで実装していく必要があります。

ランキング機能に関しても同様で、この機能を実装する際には2つの実装が考えられました。

RDBを用いた実装

1つはRDBを用いての実装です。

スコア用のテーブルなどを用意して、このテーブルに各ユーザのスコアを INSERT/UPDATE していきます。

CREATE TABLE `user_scores` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `user_id` bigint(20) unsigned NOT NULL,
  `event_id` bigint(20) unsigned NOT NULL,
  `score` int(10) unsigned NOT NULL,
  `created_at` datetime NOT NULL,
  `updated_at` datetime NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

上のようなテーブル¹に積まれているデータをバッチ処理で集計したり、アプリケーション側から取ってきてソートすればランキングの情報になります。

この実装のメリットは、強いて言うのであればRDBとアプリケーションのみで基本的な処理が完結することでしょうか。

しかしながらそもそもRDBがランキングに適したデータストアではないため、アプリケーション側で都度ソートする処理を書く必要があります。また、負荷など考慮しなければならないことは非常に多いです。

アプリケーションに複雑さを取り込む必要が出てきます。

redis Sorted sets を用いた実装

RDBを用いての実装は複雑でコストがかかりそうで、あまり良い選択肢ではないように見えました。²

そこで、今回の本題にも出てくる redis の Sorted sets を用いての実装です。

redis はインメモリデータストアで、list や set などのいくつかのデータ構造をサポートしている KVS の一種です。大きな特徴としてシングルスレッドで動作することが挙げられ、データベースやキャッシュ、メッセージブローカーとしても使うことができます。

Sorted sets は redis がサポートしているデータ構造の一つで、セットとハッシュの混合に似たデータ型です。

この辺りは導入の際にも述べましたが、このSorted setを扱うと適切なタイミングでスコアをredis に積んでいくだけで済みます。積むタイミングで redis がよしなにソートし直すためアプリケーション側でソートする必要もありません。

このため非常にシンプルにランキングを実装することができます。

負荷に関してはRDBと同様に考慮しなければなりませんが、RDBを用いて実装するよりはるかに軽いコストで実装することが可能だと思います。このため Sorted set を採用しています。

同一スコアをうまく扱うために

先ほど述べたように、同じスコアを取ったユーザでもスコアを獲得した順で優劣をつけなくてはいけません。これは Sorted sets の仕様で取り扱えず、アプリケーション実装者が考えなくてはいけない事項です。

これを実現するために、すでにソートされているはずのデータを Sorted sets から取ってきて同一スコアの取り扱いのためだけに再びソートしていては Sorted sets を使う意味がありません。

なんとかして Sorted sets で順位づけを完結させつつ、時間を加味できるようにすることを考えていきます。

Sorted setsで扱うことのできるデータの型について見る

登録時に時刻情報をうまく扱える仕組みが redis に用意されていれば解決すると考え、まずは Sorted sets に対してアプリケーション側が登録することのできるデータを見てみます。

以下は特定の Sorted sets へスコアを登録し、その中身を見る操作です。

redis> ZADD myzset 1 "one"
(integer) 1
redis> ZADD myzset 1 "uno"
(integer) 1
redis> ZADD myzset 2 "two" 3 "three"
(integer) 2
redis> ZRANGE myzset 0 -1 WITHSCORES
1) "one"
2) "1"
3) "uno"
4) "1"
5) "two"
6) "2"
7) "three"
8) "3"
redis>

この ZADD を用いてランキング用の Sorted sets へ key(string) と score(double) のペアを登録することができます。この score は IEEE 754浮動小数点で、-2^53~2^53 の範囲内の数値を登録可能です。

つまり、アプリケーション側からこの Sorted sets へ登録可能なものは、特定のユーザを示すための key と、そのユーザが出したスコアを示す score のみであることがわかります。

key に時刻による情報を付け足すことで辞書順の優劣をつけるか、 score に時刻の情報を付け足して数値的に優位をつけるかでしか実現できなさそうなことがわかりました。

key に時刻による情報を付加し辞書順を操作する

まずは、 key に時刻の情報を足してうまくいくかを考えます。

各ユーザには一意な id が割り当てられているので、これを key として用いており、Sorted sets に登録する key は user_id/${id} のような表現で登録しています。

この key を user_id/${id}:${timestamp}のような形⁴にすることでうまく順位づけできれば良いと考えました。

しかしながら、この方法で実装をすると同一ユーザが複数の key で登録されてしまうことになり、単純に登録するだけでは問題のある実装になってしまいます。新しいスコアを登録する際には、前の key を削除する必要があるのです。

1. 以前の時刻情報を用いて `key`を作る
2. あるユーザの前の `key` を削除する
3. 保持している時刻情報の更新をする
4. あるユーザを新しい `key` で登録する

削除の操作はが加わることで複雑さが増えてしまい、また書き込み処理を登録以外にもする必要が出てしまいました。

これはあまり良くない兆候だと感じ、より単純な操作を目指してスコアの方でうまくできないかを考えてみます。

スコアに時刻情報を付加する

どうにかしてスコアに時刻情報を焼き込む方法を考え、そこでbit演算を使うことに思い至りました。

上位nビットをスコアにし、下位mビットへ時刻情報を割り当てることで解決できそうです。同一スコアの場合は上位nビットが同値で、時刻情報で比較するはずなのでうまくいきそうな雰囲気があります。

key で扱うときのような削除処理も不要です。 Sorted sets の単純に操作するだけで済みそうです。

時刻情報を下位ビットに割り当てるのは良いアイデアだと考えましたが、一つ制約が発生しました。設定できる時刻情報の値の大きさにある程度制限がかかることです。

UnixTimeの最大値を用いる

スコア達成が早いユーザほどスコアを高くする必要があるため、まずは以下の計算式の結果を下位ビットに割り当てようと考えていました。

timestamp := MaxUnixTime.Unix() - now.Unix()

しかし、この計算式を扱うと 3000000000 前後の値になってしまうため 32bitほど割り当てる必要が出てきてしまいます。このためスコアに割り当て可能なビット数が減ってしまい、予期されたスコアに対して必要な分のビット数を確保できなくなってしまいました。

これは仕様に耐えうる実装ではないので別の方法を考えなければいけません。

この問題は、現在時刻とUnixTimeの最大値の差が大きすぎたために発生しています。そこで、この差を小さくできないかを考えてみます。

イベントの終了時刻を用いる

一般的なゲーム内イベントには期間があると思います。そして、イベントで用いるランキングのスコアの更新が発生するのはそのイベント期間内です。つまりスコアの達成時刻で最も遅い時刻というのはイベント終了時刻と等しいと考えることができます。

先ほどの割り当てようとした計算式でUnixTimeの最大値の代わりにイベント終了時刻を用いると以下のようになります。

timestamp := endTime.Unix() - now.Unix()

イベント開催期間にもよりますが、20~22bit ほどの割り当てで済むようになりました。これによりスコアに割り当て可能なビット数は約30bitほどになるため、予測されたスコアに対して十分な値をとることが可能になりました。

timestamp := endTime.Unix() - now.Unix()
// 23ビット程度で済むので上位30ビットはscoreに割り当てられる
timestamp |= 0 << (23 - 1)
int64(score)<<23 | timestamp

Sorted sets への登録もしくは取得の際にビット演算をして加工をしなければなりませんが、この手法を採用することで、 Sorted sets の優位性を失わずに比較的シンプルに実装することが可能になりました。

おわりに

今回は弊社でランキングを実装する際に同一スコアをどのように扱っているかについてご紹介させていただきました。ビット演算を用いることで、なんとか同一スコア含めてSorted sets のみで順序づけを完結できないかということを、考えた際の段階的な思考も含めて書かせていただきました。

Sorted Sets によるランキング実装はすでに何年も使われ続けているいわゆる枯れた技術で、そのため色々な知見がWebに溢れてはいますが、一つでも新しい発見があったとしたらとても嬉しいです。

ここまでお読みいただきありがとうございました。

参考文献

｢redis｣, https://redis.io/ (2019-12-24)

antirez(2015) ｢Clarifications about Redis and Memcached｣, http://antirez.com/news/94 (2019-12-24)

1. Indexは適切に貼る必要がある↩

2. かなり泥臭いことが明らかに見えていた↩

3. 実際に運用しているゲームの仕様とは相違がある↩

4. 厳密には辞書順を考慮した値にしないといけない↩

< 前へ

一覧へ戻る

開発ブログ