リアルタイム・ランキングを考える
sp1rytusはじめに
こんにちは。プラットフォーム開発部のsp1rytusと申します。
先日、私もついに30歳のおっさんになってしまいました。加齢臭が出ないようにがんばります！
ランキングって？
ランキングは誰でもわかる、何らかの得点をソートして順位位置を決定する凄く簡単でシンプルなものです。しかし、ゲームを扱うコンテンツ・サービスにおいては、得点を通算/日別に順位付けされたものが直ぐに目に入るように、他人と自分を比較する非常に重要な役割を果たしています。そこで、この記事では次の３つ要件を満たすようなランキング・システムの難しさと、それを解決するための一例を簡単に説明させて頂きます。
- 順位付けはリアルタイムに行い、集計時間を必要としない。
- 100万件以上の得点データが扱える。
- すべてのデータが正しい順位付けで取得できる(線形補完などで順位を概算しない）。
リアルタイムによる正確な順位付けは、データ件数が小さい場合には容易に実装することができそうですが、データ件数が多くなるにつれてパフォーマンスよく動作させることが非常に困難になってきます。
データ件数が少ないときの手続き
ユーザIDと得点を、次のようにMySQLで管理する場合を例にします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
mysql> SELECT * FROM user_point; +---------+--------+ | user_id | point | +---------+--------+ | 109 | 294870 | | 108 | 94746 | | 107 | 61065 | | 106 | 41248 | | 105 | 32730 | | 104 | 8590 | | 103 | 7859 | | 102 | 5756 | | 101 | 4641 | | 100 | 1541 | |
ユーザID:105、得点:32730点の順位（得点の高い順にソート）を求める場合、次のようなクエリーを使うと簡単に求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
mysql> SELECT point FROM user_point WHERE user_id = 105; +-------+ | point | +-------+ | 32730 | +-------+ mysql> SELECT COUNT(*) + 1 AS rank FROM user_point WHERE 32730 < point; +------+ | rank | +------+ | 5 | +------+ |
データ件数が多くなるとなにが起こるのか
得点データが頻繁に更新(UPDATE)されるようなランキング・システムの場合、テーブルロックという特性を持つMyISAMだとデータの更新がボトルネックになるため、並列性が高い行レベルロックであるInnoDBを使います。しかし、InnoDBを採用したことにより得点データが10万件を超えた辺りから次のような現象が起こりはじめCOUNTクエリーに工夫が必要だと感じはじめます。
|
1 2 3 |
MySQL slow-query ログより # Query_time:21.1 Lock_time:0.026247 Rows_sent: 1 Rows_examined:112418 mysql> select COUNT(*) + 1 AS rank from user_point WHERE 32730 < point; |
負荷を軽減させる考え方
ある得点から、ある得点までの区間に現在何人が属しているかを次のようなデータ構成で表現します。
|
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 |
mysql> select * from user_point; +---------+--------+---------------+ | user_id | point | partition_id | +---------+--------+---------------+ | 100 | 1541 | 10 | | 101 | 4641 | 10 | | 102 | 5756 | 10 | | 103 | 7859 | 10 | | 104 | 8590 | 10 | | 105 | 32730 | 7 | | 106 | 41248 | 6 | | 107 | 61065 | 5 | | 108 | 94746 | 5 | | 109 | 294870 | 1 | mysql> select * from partition; +------+-----------+------------+------+ | id | min_point | max_point | num | +------+-----------+------------+------+ | 1 | 250000 | 300000 | 245 | | 2 | 200000 | 250000 | 132 | | 3 | 150000 | 200000 | 144 | | 4 | 100000 | 150000 | 1561 | | 5 | 50000 | 100000 | 1244 | | 6 | 40000 | 50000 | 1309 | | 7 | 30000 | 40000 | 1345 | | 8 | 20000 | 30000 | 1627 | | 9 | 10000 | 20000 | 2736 | | 10 | 0 | 10000 | 2736 | ← numの値はサンプルです +------+-----------+------------+------+ |
指定ユーザの得点順位を求める手続き
- user_idをから(得点, 所属する区間)データを取得する。
- (1)で取得したユーザの所属区間より上位(min_point, or max_pointが大きい)区間の人数合計を求める。
- (1)で取得したユーザの所属区間内で、大きい得点となる人数を求める。
- (2), (3)で求められた人数の和 + 1が順位になる。
(例) user_id:105で上の手順を実行すると
- (得点, 所属する区間)データ取得 point:32730 partition_id:7
- 上位区間人数の合計 245+132+144+1561+1244+1309= 4635(人)
- 同じ区間で得点が高い人数を求める SELECT COUNT(point) FROM user_point WHERE point BETWEEN 32730 AND 40000 (仮で上のクエリー発行で40人いたとします）
- 順位を求める 4635 + 40 + 1 = 4676 (位)
上のような処理を行った場合、MySQL的になにが改善されるかを見てみましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
単純なクエリーの場合 mysql> explain SELECT COUNT(point) FROM user_point WHERE 32730 < point ; +----+-------------+------------+-------+---------------+-------+---------+------+------+--------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+------------+-------+---------------+-------+---------+------+------+--------------------------+ | 1 | SIMPLE | user_point | range | point | point | 4 | NULL | 3846 | Using where; Using index | +----+-------------+------------+-------+---------------+-------+---------+------+------+--------------------------+ 1 row in set (0.00 sec) 得点区分を用いたランキングの場合 mysql> explain SELECT COUNT(point) FROM user_point WHERE point BETWEEN 32730 AND 40000; +----+-------------+------------+-------+---------------+-------+---------+------+------+--------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+------------+-------+---------------+-------+---------+------+------+--------------------------+ | 1 | SIMPLE | user_point | range | point | point | 4 | NULL | 130 | Using where; Using index | +----+-------------+------------+-------+---------------+-------+---------+------+------+--------------------------+ 1 row in set (0.00 sec) |
っといった具合に、条件を設けたことによりスキャンするrowsが減り負荷の軽減が見込めそうです。
実際に運用するにあたり
得点分布が予測できる場合は、先に説明したpartitionテーブルの得点区間の閾値を事前に準備することができますが、実際の運用では得点データはサービスのバランス調整次第で容易に推移するため、得点区間の閾値を運用中に動的に変化させる必要がでてくるかもしれません。そのほかにも、今回は理解のしやすさから該当区間に所属する人数を直接numに入れていますが、SUMの計算コストを減らすためにnumには上位区間からの総和を入れておいた方が効率的に扱えるでしょう。
グリーではランキングのリアルタイム性にこだわりを持ち、負荷問題解消を前提に構築されたランキング・システムで運用されています。そして、さらに多くの得点母集団を扱うため新たな手法によるもの(おそらく言語はCになる？)も構想中です。
さいごに
この記事を読まれて、釣りスタや、グリーゲームなどのランキングを少し意識してみてもらえれば開発者冥利に尽きます。