レイドボスバトルの負荷を捌くには？ [ゲーム開発]
概要
ソーシャルゲームによくあるレイドボスバトルのデータの保存方法について考えてみます。
仕様は単純でも負荷が高くなりやすく意外と設計が難しいです。
要件定義
仕様
ひとくちにレイドと言っても様々な仕様があります。
ここでは単純化するために以下の仕様とします。
- 全員で 1 体のボスと戦う
- パラメーターは HP のみ
- HP は回復しない
- HP が 0 になったら終了、次のボスが湧く
- オーバーキル分のダメージは引き継がない
- HP は INT に収まる
- 与えるダメージは MEDIUMINT に収まる
DB は MySQL (Aurora MySQL) の InnoDB を想定しています。
従って SQL は MySQL 形式で書きますがそんなに難しいことはやっていないので他の DB でも似たようなことはできるのではないかと思います。
DB にはダメージを保存します。
レイドボスの残り HP は HP - ダメージ で計算します。
（HP を保存するよりはシンプルになるはず）
想定アクセス
- バトル（攻撃してダメージを与える）は 1 人 1,000 回
- （アクティブな）プレイヤーは 100 万人
- 同時接続は 10 万人
その他
基本的には HTTP でデータを送って返すことをベースに考えています（いわゆる昔ながらのソシャゲでも実現可能）が、よりリアルタイムに画面に反映したければ WebSocket 等で通信することになるでしょう。
WebSocket 等でサーバーからのプッシュができると DB の更新をトリガーにして後からプッシュするなどやれることの幅は広がりそうですがデータの保存方法はさほど変わらないと思うのでここでは割愛します。
プレイヤー ID の型はプロジェクトによる思いますがここでは INT にします。
仕様にはありませんが貢献度（ボス毎のランキング）についても少し考えてみます。
A. バトル毎にダメージを保存
バトル毎にデータを保存しておけばどんな情報でも取れるので完璧ですね。
CREATE TABLE `raid` (
`id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
`player_id` INT UNSIGNED NOT NULL,
`raid_id` INT UNSIGNED NOT NULL,
`damage` MEDIUMINT UNSIGNED NOT NULL,
PRIMARY KEY (`id`),
KEY (`raid_id`, `damage`) -- covering index
);
-- ダメージを与える
INSERT INTO `raid` (`player_id`, `raid_id`, `damage`) VALUES (?, ?, ?);
-- 総ダメージ
SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = ?;
-- 貢献度
SELECT `player_id`, SUM(`damage`) AS `damage`
FROM `raid`
WHERE `raid_id` = ?
GROUP BY `player_id`
ORDER BY `damage` DESC;
ほんとに？
バトル回数が増えてくると SELECT に時間がかかるようになります。
SELECT の頻度によっては負荷も上がってきます。
レスポンスが悪いのはゲームとして致命的です。
いわゆる非機能要件と呼ばれるものですね。
1 人 1,000 回バトルをするとしたらプレイヤーが 100 万人いると 10 億レコードになります。
シャーディング（水平分割）をしてデータ量を減らすこともできますがシャードが分かれると総ダメージの SUM ができなくなります。
アプリ側で総ダメージを計算することもできますが色々と扱いが難しいです。
ローカルでダミーデータの生成
雑にデータ生成をして雰囲気だけ見てみます。
参考として掲載しますが結局は仕様次第なので鵜呑みにせずに負荷試験をしてください。
ローカルで 100 万レコード
総ダメージはカバリングインデックスになっているので負荷さえ耐えられればいけそうです。
貢献度は 1 秒以上かかってしまっていますね。
mysql> SELECT COUNT(*) FROM `raid`;
+----------+
| COUNT(*) |
+----------+
| 1000000 |
+----------+
1 row in set (0.04 sec)
mysql> SELECT COUNT(DISTINCT `player_id`) FROM `raid`;
+-----------------------------+
| COUNT(DISTINCT `player_id`) |
+-----------------------------+
| 100 |
+-----------------------------+
1 row in set (16.99 sec)
mysql> SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1;
+----------+
| damage |
+----------+
| 50239975 |
+----------+
1 row in set (0.03 sec)
mysql> EXPLAIN SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: raid
partitions: NULL
type: ref
possible_keys: raid_id
key: raid_id
key_len: 4
ref: const
rows: 239046
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.00 sec)
mysql> SELECT `player_id`, SUM(`damage`) AS `damage`
-> FROM `raid`
-> WHERE `raid_id` = 1
-> GROUP BY `player_id`
-> ORDER BY `damage` DESC;
+-----------+--------+
| player_id | damage |
+-----------+--------+
| 16 | 765573 |
| 83 | 765062 |
（中略）
| 33 | 256291 |
| 34 | 253094 |
+-----------+--------+
100 rows in set (2.56 sec)
mysql> EXPLAIN SELECT `player_id`, SUM(`damage`) AS `damage`
-> FROM `raid`
-> WHERE `raid_id` = 1
-> GROUP BY `player_id`
-> ORDER BY `damage` DESC\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: raid
partitions: NULL
type: ref
possible_keys: raid_id
key: raid_id
key_len: 4
ref: const
rows: 239046
filtered: 100.00
Extra: Using temporary; Using filesort
1 row in set, 1 warning (0.01 sec)
ローカルで 1,000 万レコード
0.2 秒は厳しそうです。これ以上は無理そうですね。
ただ、ボスの HP が低ければ rows が減るのでいけるかもしれません。
mysql> SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1;
+-----------+
| damage |
+-----------+
| 500959986 |
+-----------+
1 row in set (0.26 sec)
mysql> EXPLAIN SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: raid
partitions: NULL
type: ref
possible_keys: raid_id
key: raid_id
key_len: 4
ref: const
rows: 2286102
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.00 sec)
mysql> SELECT `player_id`, SUM(`damage`) AS `damage`
-> FROM `raid`
-> WHERE `raid_id` = 1
-> GROUP BY `player_id`
-> ORDER BY `damage` DESC;
+-----------+---------+
| player_id | damage |
+-----------+---------+
| 50 | 7435490 |
| 84 | 7367949 |
（中略）
| 34 | 2577306 |
| 67 | 2541916 |
+-----------+---------+
100 rows in set (12.44 sec)
mysql> EXPLAIN SELECT `player_id`, SUM(`damage`) AS `damage`
-> FROM `raid`
-> WHERE `raid_id` = 1
-> GROUP BY `player_id`
-> ORDER BY `damage` DESC\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: raid
partitions: NULL
type: ref
possible_keys: raid_id
key: raid_id
key_len: 4
ref: const
rows: 2286102
filtered: 100.00
Extra: Using temporary; Using filesort
1 row in set, 1 warning (0.00 sec)
ローカルで 1 億レコード
mysql> INSERT INTO `raid` (`player_id`, `raid_id`, `damage`)
-> SELECT CEIL(RAND() * 100), CEIL(RAND() * 10), CEIL(RAND() * 1000)
-> FROM `dummy` `d1`, `dummy` `d2`, `dummy` `d3`, `dummy` `d4`;
Query OK, 100000000 rows affected (1 hour 27 min 21.76 sec)
Records: 100000000 Duplicates: 0 Warnings: 0
mysql> SELECT COUNT(*) FROM `raid`;
+-----------+
| COUNT(*) |
+-----------+
| 100000000 |
+-----------+
1 row in set (15.59 sec)
mysql> SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1;
+------------+
| damage |
+------------+
| 5005321242 |
+------------+
1 row in set (9.15 sec)
mysql> SELECT `player_id`, SUM(`damage`) AS `damage`
-> FROM `raid`
-> WHERE `raid_id` = 1
-> GROUP BY `player_id`
-> ORDER BY `damage` DESC;
+-----------+----------+
| player_id | damage |
+-----------+----------+
| 17 | 74132797 |
| 84 | 74009414 |
（中略）
| 34 | 25630627 |
| 67 | 25594818 |
+-----------+----------+
100 rows in set (25 min 21.11 sec)
B. プレイヤー毎にダメージを保存
バトル毎に保存するのは厳しそうなのでプレイヤー毎に与えたダメージを管理するようにします。
CS 対応に必要なバトル履歴は別途ログに保存しましょう。
CREATE TABLE `raid` (
`player_id` INT UNSIGNED NOT NULL,
`raid_id` INT UNSIGNED NOT NULL,
`damage` INT UNSIGNED NOT NULL,
PRIMARY KEY (`player_id`, `raid_id`),
KEY (`raid_id`, `damage`) -- covering index
);
-- ダメージを与える
INSERT INTO `raid` (`player_id`, `raid_id`, `damage`) VALUES (?, ?, ?)
ON DUPLICATE KEY UPDATE `damage` = `damage` + VALUES(`damage`);
-- 総ダメージ
SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = ?;
-- 貢献度
SELECT `player_id`, `damage` FROM `raid` WHERE `raid_id` = ? ORDER BY `damage` DESC;
どう？
1 人 1 レコードになったので 100 万レコードまで減りました。
総ダメージは SUM の対象が多いのでまだちょっと厳しそうです。
ボスの HP が低ければ SUM の対象も減るのでいけるかもしれません。
貢献度は SUM が不要になったので上位に絞れば一瞬で返ってくるようになりました。
ローカルで 600 万レコード
ダミーデータの生成の都合で約 600 万レコード。
プレイヤー数は約 60 万人で総ダメージに 2 秒なので厳しいですね。
mysql> INSERT INTO `raid` (`player_id`, `raid_id`, `damage`)
-> SELECT CEIL(RAND() * 1000000), CEIL(RAND() * 10), CEIL(RAND() * 1000)
-> FROM `dummy` `d1`, `dummy` `d2`, `dummy` `d3`, (SELECT * FROM `dummy` LIMIT 10) AS `d4`
-> ON DUPLICATE KEY UPDATE `damage` = `damage` + VALUES(`damage`);
Query OK, 13978259 rows affected, 1 warning (38 min 4.93 sec)
Records: 10000000 Duplicates: 3978259 Warnings: 1
mysql> SELECT COUNT(*) FROM `raid`;
+----------+
| COUNT(*) |
+----------+
| 6021741 |
+----------+
1 row in set (2.09 sec)
mysql> SELECT COUNT(`player_id`) FROM `raid` WHERE `raid_id` = 1;
+--------------------+
| COUNT(`player_id`) |
+--------------------+
| 601541 |
+--------------------+
1 row in set (0.73 sec)
mysql> SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1;
+-----------+
| damage |
+-----------+
| 500125450 |
+-----------+
1 row in set (0.81 sec)
mysql> EXPLAIN SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: raid
partitions: NULL
type: ref
possible_keys: raid_id
key: raid_id
key_len: 4
ref: const
rows: 1450118
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.02 sec)
mysql> SELECT `player_id`, `damage` FROM `raid` WHERE `raid_id` = 1 ORDER BY `damage` DESC;
+-----------+--------+
| player_id | damage |
+-----------+--------+
| 67178 | 7115 |
| 469334 | 6929 |
（中略）
| 851 | 1 |
| 465 | 1 |
+-----------+--------+
601541 rows in set (1.04 sec)
mysql> SELECT `player_id`, `damage` FROM `raid` WHERE `raid_id` = 1 ORDER BY `damage` DESC LIMIT 10;
+-----------+--------+
| player_id | damage |
+-----------+--------+
| 67178 | 7115 |
| 469334 | 6929 |
| 787827 | 6663 |
| 154634 | 6648 |
| 790388 | 6478 |
| 477076 | 6433 |
| 135842 | 6398 |
| 760917 | 6355 |
| 102256 | 6353 |
| 178205 | 6293 |
+-----------+--------+
10 rows in set (0.00 sec)
C. 総ダメージを保存
プレイヤー毎のデータを保存するのは諦めてボスへ与えた総ダメージだけを管理します。
貢献度は取れなくなりますが今回の要件では問題ないはずです。
欲しい場合は別テーブルで管理してバッチで集計しましょう。
CREATE TABLE `raid` (
`raid_id` INT UNSIGNED NOT NULL,
`damage` INT UNSIGNED NOT NULL,
PRIMARY KEY (`raid_id`)
);
-- ダメージを与える
INSERT INTO `raid` (`raid_id`, `damage`) VALUES (?, ?)
ON DUPLICATE KEY UPDATE `damage` = `damage` + VALUES(`damage`);
-- 総ダメージ
SELECT `damage` FROM `raid` WHERE `raid_id` = ?;
今度は UPDATE が
SELECT は問題なくなりましたが 1 つのレコードに対する UPDATE 頻度が高いので同時にバトルしている人が多いと DB が負荷で死にます。
D. 総ダメージを Redis に保存
DB では限界のようなので Redis に保存してみます。
仕様がシンプルなので KVS (NoSQL) でも実装が可能です。
Expire は付けずに無期限にしておきましょう。
# ダメージを与える、返り値は総ダメージ
INCRBY raid-<raid_id> <damage>
やっていることは変わりませんが Redis だと何とかなります。
流石 KVS ですね。パフォーマンスが違います。
実際に本番で稼働した実績もありますし、おそらく一般的な実装なのではないかと思います。
貢献度
貢献度を取りたい場合はソート済みセットに入れましょう。
# ダメージを与える、返り値はプレイヤー毎のダメージ
ZINCRBY raid-<raid_id> <damage> <player_id>
# 総ダメージ
# 前述の別キーで管理
# または ZRANGE 等で全リストを取得してアプリ側で足すか Lua スクリプトを書く
# 貢献度
ZREVRANGE raid-<raid_id> 0 -1 WITHSCORES
ZREVRANGEBYSCORE raid-<raid_id> +inf 0 WITHSCORES
総ダメージを別キーで管理
トランザクション張っておいた方がいいかも。
日本語（古め）
総ダメージをソート済みセットから計算
local sum=0
local z=redis.call('ZRANGE', KEYS[1], 0, -1, 'WITHSCORES')
for i=2, #z, 2 do
sum=sum+z[i]
end
return sum
Redis サーバーが落ちると…？
Redis はメモリにデータを保存することで高速な処理を実現しています。
データを永続化するために一定時間や一定回数ごとにファイルへ保存する仕組みもありますが間隔を短くすればするほど I/O が増えるのでパフォーマンスは悪化するのではないかと思います。
日本語（古め）
間隔をどんなに短くしてもサーバーが落ちるタイミングによっては漏れが出てきます。
これらを仕様的に許容したり別途何かしらの復旧手段（復旧時にログから再計算するなど）を用意できれば十分実用的です。
E. バトルサーバーのメモリに保存
Redis と似たような考え方で Node.js などプロセスが常に動いている言語であればインメモリでダメージを管理できるのではないかと思いました。
ただ全員を 1 つのサーバーに接続させるのは無理なので 1 体あたりの接続を限定できる場合に限られそうです。
私はやったことはありませんが方法の 1 つとして記載しておきます。
Redis と同様に永続化は課題になりそうですね。
F. 総ダメージを NoSQL DB に保存
やはり安全のためには永続化される DB へ保存するのが一番です。
ここまで DB ＝ Relational DB (RDB) として扱ってきましたが NoSQL DB もあります。
AWS だと MemoryDB for Redis や DynamoDB などが該当します。
MemoryDB は Redis に保存する感覚で使えそうですね。
DynamoDB も似たような感じで使えそうですが I/O があると思うので厳しいかもしれません。
私は試したことがないので負荷に耐えられるかは不明です。
G. 総ダメージを Relational DB に保存（再）
レイド以外のデータは基本的に RDB に保存されています。
NoSQL (KVS) に保存すると他のデータと保存先が異なるのでどうしても管理コストが増えてしまいます。
特にイベントで実施する場合、期間中だけ立ち上げるような運用が必要になるでしょう。
なんとか RDB で実現できないものでしょうか？
CREATE TABLE `raid` (
`raid_id` INT UNSIGNED NOT NULL,
`division` SMALLINT UNSIGNED NOT NULL, -- player_id % N
`damage` INT UNSIGNED NOT NULL,
PRIMARY KEY (`raid_id`, `division`)
);
-- ダメージを与える
INSERT INTO `raid` (`raid_id`, `division`, `damage`) VALUES (?, ?, ?)
ON DUPLICATE KEY UPDATE `damage` = `damage` + VALUES(`damage`);
-- 総ダメージ
SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = ?;
総ダメージを複数のレコードに分けて保存します。
シャーディングと似たような考え方です。
ちょうど B. と C. の中間ですね。B. は N = プレイヤー数、C. は N = 1 です。
分割数 N = 128 ～ 1,024 くらいであれば SUM するレコード数もそこまで多くないのですぐ返ってきますし UPDATE でロックされるレコードも分散されるので十分耐えることができます。
レコードの統合や更なる分割をするのに都合がいいので分割数は 2 の累乗がおすすめです。
1,024 分割として同時接続は 10 万人想定なので SUM は 1,024 レコード、UPDATE は約 100 接続/レコードになります。
これくらいなら耐えれそうですよね。
分割数やアクセス数などは異なりますが実際に本番で稼働した実績もあります。
ローカルで 1,024 レコード
mysql> INSERT IGNORE INTO `raid` (`raid_id`, `division`, `damage`)
-> SELECT CEIL(RAND() * 10),CEIL(RAND() * 1024), CEIL(RAND() * 1000)
-> FROM `dummy` `d1`, `dummy` `d2`, `dummy` `d3`;
Query OK, 10240 rows affected, 65535 warnings (5.09 sec)
Records: 1000000 Duplicates: 989760 Warnings: 989760
mysql> SELECT COUNT(*) FROM `raid` WHERE `raid_id` = 1;
+----------+
| COUNT(*) |
+----------+
| 1024 |
+----------+
1 row in set (0.00 sec)
mysql> SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1;
+--------+
| damage |
+--------+
| 515191 |
+--------+
1 row in set (0.00 sec)
mysql> EXPLAIN SELECT SUM(`damage`) AS `damage` FROM `raid` WHERE `raid_id` = 1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: raid
partitions: NULL
type: ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: const
rows: 1024
filtered: 100.00
Extra: NULL
1 row in set, 1 warning (0.00 sec)
どのくらいまで耐えられるの？
個人環境で負荷試験を実施するのは手間や費用面から難しいのと、結局は実装する環境のスペックに依存してしまうのでここには掲載しません。
ご自身の環境で試してみてください。
レコード数、同時接続数の上限は探っておきましょう。
負荷対策というのはなかなか奥が深くて通常の MySQL だと耐えられなくても Aurora MySQL や Fusion-io にするだけで耐えられるようになることもあります。
HP の判定について
しれっとスルーしていましたが補足です。
追加仕様も少し考えてみます。
倒したかどうか
raid_id はクライアントで分かっているものとします。
UPSERT (INSERT できなかったら UPDATE) をする前に残り HP を取得して判定するか、とりあえず UPSERT をした後に残り HP を取得して判定します。
仕様にもよりますが既に倒された状態であればエラーを返すことになるでしょう。
前者の場合トランザクション内でロックをかけないと判定したタイミングでは生きていても UPDATE するタイミングで倒されていることがあるので注意してください。
該当レコードがないタイミングでロックするとロックの範囲が広くなることにも注意してください。
UPSERT 前に判定する場合は攻撃後に HP が 0 を割っていたら倒したことになります。
UPSERT 後に判定する場合は攻撃後の HP から与えたダメージを引くと攻撃前の HP が分かります。攻撃前の HP が 0 を割っていた場合はエラーです。
もしくは UPSERT の SQL 文でうまいこと条件を付けてやる方法もあるかもしれませんがやったことはないです。（複雑になりそう）
オーバーキルのダメージを引き継ぎたい
前述の判定でエラーになった際に次のレコードを UPSERT してもいいですし raid_id を分けずにそのままダメージを加算していく手もあります。
現在のダメージは HP で割った余り (damage % hp) 、倒した数は商になります。
こうしておけば前述の判定はそもそも不要になります。
レイドが複数種類いる
raid_id だった部分を raid_type + raid_id で管理するとよさそうです。
DB 上で HP から引き算したい
1 レコードで管理する方式であれば最初に HP を INSERT することで実現可能だと思います。
それ以外では UNSIGNED INT ではなく SIGNED INT にして SUM することもできそうです。
HP を + で INSERT してダメージを - で UPSERT。
ボスの発見
今回は常にボスがいる状態でしたが、「ボスを発見する」仕様だった場合はそのタイミングで INSERT をしてバトルでは UPDATE するだけで良いのでかえって実装はシンプルかもしれないですね。
関連記事
他の人はどうやって実装しているのかなーと調べてみましたが具体的なテーブル定義が載っている記事は見つけられませんでした。
ここにない記事や他にもやり方があるよという方はコメントで教えてください。
Discussion