ジョーカー~ギャングロード~(以下ジョーカー)でサーバーエンジニアをやっている嶋です。
ジョーカーは、最大25 vs 25の計50人で戦う抗争というGvGがメインのカードゲームです。
参加人数、行動回数が多いチーム同士の対戦(以下、アクティブな対戦)では、レイテンシがかなり高くプレイ体感が悪いことが発覚し、調査及びレイテンシ改善を行いました。
その結果、最大約60%のレイテンシ削減に至ったので、その時のことを書かせて頂きます。

まずはジョーカーのインフラ構成、GvGにおける排他制御の方法を説明します。

ジョーカーのインフラ構成

ジョーカーではAWSを使っており、GvGにおける構成は下記のようになっています。

• APIサーバー50台(EC2)
• user用DB guild用DB(各4台)
• gvg用DB(元々各4台、集約後Amazon Aurora1台)
• Redis 4台

GvG関連のデータの更新はgvg用DBに対して行い、参照用にRedisを使用しています。

GvGにおける排他制御の仕組み

Gvgでは多人数が同時に行動するため、同じレコードに対する更新が同時に頻繁に起こります。
同時に行動が行われた場合でも、全ての行動の結果が正しくゲームに反映されることが必須です。
そのためのジョーカーの排他制御の方法を説明します。

前述の通り、ジョーカーのGvGのデータはMySQLで管理しています。
テーブルのイメージは下記の通りです。

データ更新系のAPIが叩かれた場合、大元のgvgテーブル(以降gvg_mainとします)を行ロック(select for update)を行い、ロックが取得できてから計算を開始する流れになっています。
gvg_mainは1試合につき1レコードできるので、最大25 vs 25の計50人で戦うジョーカーのGvGでは、最大50人がgvg_mainへの行ロックを同時に行うことになります。

–処理順–
①試合IDに紐づくgvg_mainテーブルのレコードを行ロック
②パラメータなど関連データを取得、効果値を計算
③MySQLにcommit、Redisに処理後の値を登録

計算途中に他の人の行動によってgvgデータが書き換えられることがないため、データの整合性が保たれます。

例えばA,B,Cのユーザーがほぼ同時にA,B,Cの順番に行動をした場合、

1.Aが①の行ロックを行う
2.Bは①の行ロックを試みるが、Aが行ロックをしているため待ち
3.Cは①の行ロックを試みるが、Aが行ロックをしているため待ち
4.Aが②-③の処理を行い、ロックを解放する
5.Bが行ロックを取得する
6.CはBが行ロックをしているため待ち
7.Bが②-③の処理を行い、ロックを解放する
8.Cが行ロックを取得する
9.Cが②-③の処理を行い、ロックを解放する

という流れになります。

レイテンシ悪化の原因調査・改善

以下、レイテンシ改善のために取り組んだことを書いていきます。

New Relicでボトルネックの調査

本番のAPIサーバーに仕込んでいるNew Relicをもとに、レイテンシが高い時の各処理の所要時間を計測しました。
レイテンシが高い時の所要時間99%は、①のロック待ちでした。
多人数が同時に行動した場合、上記説明の通り他の人の処理が終了するのを待ってから自分の行動分の処理が開始されます。
この待ち時間が肥大化したことによって、行動数の多い抗争ではレスポンス速度が悪化していたことが推測されました。

待ち時間行列モデル(M/M/1)による検証

上記ロック待ちの仕組みの置いて、ロック中の処理時間と平均レイテンシの関係は待ち時間行列のM/M/1モデルで説明することができます。
待ち時間行列のM/M/1モデルとは、1つしかない窓口にお客がランダムに到着した場合の、
・お客の到着する頻度
・窓口での処理時間
を元に、平均の待ち時間を算出するモデルです。

単位時間当たりにお客の到着する数:λ
単位時間当たりに窓口がこなす人数:μ
とすると、お客が到着してから窓口を終えるまでの時間(W)は
W = 1/ (μ – λ)
で表されます。

M/M/1モデルはジョーカーのロック待ちの仕組みに適用することが出来ます。
前述のように最大50人がgvg_mainへの行ロックを試みるため、窓口1つに対して最大50人が到着するモデルです。
ロック待ちが窓口の列での待っている時間に相当し、ロック中に行っている処理が窓口での処理時間に相当します。

単位時間当たりに到着するgvgのリクエスト数:λ
単位時間当たりにサーバーが処理するリクエスト数:μ
として、平均のレイテンシ(W)は
W = 1/ (μ – λ)
で計算できます。
グラフにすると

図１レイテンシを固定した場合の、リクエスト数と平均レイテンシの関係

図２リクエスト数を固定した時の、平均レイテンシと実処理時間の関係
※平均レイテンシ:ロック待ちを加味した平均のレスポンス速度
※実処理時間:ロック待ちがなかった場合のレスポンス速度

のようになりました。
この図から

❶ロック対象のリクエスト数が増えるとレイテンシが上がる(図1)
❷ロック内の処理時間が増えるとレイテンシが上がる(図2)
ことが分かります。

アクティブな対戦ではリクエスト数が上図のNであり、参加人数が多くユーザーの行動回数が多い対戦では待ち時間が発散していることが分かりました。

リクエスト数がKの時のシステムの処理時間(ロック待ちを加味した平均レスポンス速度)とレイテンシの関係が上図です。
これより、ロック中の処理時間を20%改善すればレイテンシは最大70%改善することがわかりました。

図1,図2より、レイテンシを下げるには
ロック中の処理時間を短縮する
ことが有効なことが分かります。

高速化を行うにあたって、守ると決めたこと

高速化を行うにあたって、データの整合性を維持することを絶対に守ることに決めました。
ロック待ちを厳密に行わないように変えてしまえば、レイテンシを下げることは簡単です。
しかし強い攻撃やパラメータアップなどがなかったことになる可能性が出てきてしまうため、ゲームとして許容できないと判断しました。

チームとして取り組むことに決める

ロック中の処理時間を20%改善すれば本番でのレイテンシは3倍改善するという定量的な情報を用意し、期間を決めてチームで取り組むことに決めました。
リファクタや改善系の取り組みはイメージが湧きにくく、プランナーに理解してもらうのが難しいことも多いですが、定量的な情報と見通しを元に話すと実感を持ってもらいやすかったです。

アプローチ

先述の待ち時間行列モデルの検証に基づき、下記のアプローチでレイテンシを改善することにしました。

gvg_mainのロックを行うAPIを減らす

gvg関連のレコードを更新するが、必ずしもロックが必要ない処理(排他制御をしなかったとしてもデータの整合性が崩れない)のみで構成されるAPIを洗い出しました。
ロックを行うAPIを減らせば、ロック待ち対象のリクエスト数がが減るはずというアプローチです。
その結果、1本のAPIがgvg_mainのロックが不要であることが分かり除外しました。

このAPIはgvg_mainのロックを行うAPIの25%を占めていたため、大幅な削減につながりました。
また該当のAPIもロック待ちがなくなったため、安定して速いレイテンシが出せるようになりました。

ロック待ちの間に、ロックが不要な計算を始める

ロックを取得した後に各種データを取得・計算をすると、どうしてもロック中の処理は長くなります。
しかしロックを取得した後に各種データを取得してから計算しないと、データの整合性は崩れてしまいます。
そこで、ロックを取得した前後で計算結果に差がない処理を抽出し、ロックした後に行う処理の量を極力減らすようにリファクタリングしました。

アベイラビリティゾーンの統一

もともとAPIサーバー、Redis、MySQL全てアベイラティビティゾーンを半分つずつに分けて2つのアベイラビリティゾーンに配置していました。
APIサーバーごとのレイテンシを確認すると、存在するアベイラビリティゾーンによってレイテンシにばらつきがありました。
それぞれのアベイラビリティゾーンに存在するAPIサーバーにNew Relicを入れて検証したところ、逆ゾーンに存在するRedis、MySQLへアクセスする際レイテンシが高いことが分かりました。
アベイラビリティゾーンが同一でないと、データセンターをまたいでの通信になるためです。
これを受けて、API、Redis、MySQLのアベイラティビティゾーンを全て片側に寄せました。
各MySQLのレプリカを全て逆のアベイラティビティゾーンにおくことで、データの信頼性は担保しました。
この対応でGvGのletencyが改善しただけではなく、ゲーム全体のレイテンシが平均10%程度改善したり、一部バッチの処理時間が1/3になったりなど、大幅な改善が見られました。

テーブルのindexの見直し、不要レコードの削除

不要に貼られたindexが多かったため、精査の上削除しました。
またGvG全体が更新が多い処理であるため、レコード数が多いとindexの更新にかかってしまいます。
そのため一定期間より前のレコードはすべて削除しました。
実は参照されているindexがあると困るため、リリース前に負荷試験を行って問題がないことを確認しました。

Amazon Auroraの導入、統合

過去の負荷対策によって、4台に水平分割していたGvGのDBを1台のAmazon Auroraに集約しました。
書き込み処理が多かったためAmazon Auroraと相性が良く、同じ費用で更に処理性能の高いものに変更できました。
同じクエリのレイテンシを比較しても、Amazon Aurora導入前より改善されていました。
マシンパワーに頼るのも、時として大事であることを実感しました。

遅い処理の探し出し、チューニング

上記のような抜本的な改修と合わせて地道なリファクタリングも行いました。
計測にはJava Flight Recorderを用いて、遅い処理をメソッド単位で洗い出しました。
計測→リファクタリング→計測を繰り返し、改善を行いました。
今回発見された遅い箇所は、リリース当初には顕在化しなかったものの、約5年の運用でマスタデータの件数が100倍以上になったことでデータの検索効率の悪さが露呈したものが多かったです。
線形検索していたマスタデータを、検索キーをキーとしたMapで処理するよう変更するなどして高速化を図りました。

最終結果

・GvG全体の平均レイテンシは約30%の削減
・アクティブな対戦では約60%の削減
となり、上位チーム同士の抗争では見違えるように速くなりました。

全体を通して

レイテンシ改善を行うにあたって、地道にやり続けることが一番大事だと感じました。
アベイラビリティゾーンの統一など、全体で見れば効果の大きかった対応はありますが、それ単体では目標の水準には到達し得ませんでした。
サービスの運用開発をしていると機能追加・改修に目が行き、レイテンシ改善やリファクタが後回しにされがちです。
レイテンシ改善やリファクタはその後の運用開発やユーザー体験に確実に良い効果をもたらすので、やると決めて集中して取り組み続けることが大事だと思っています。