こんにちは、ISUCON12の本選問題作問チームの goodoo です。
この記事では、本選問題の「ISU CONQUEST」について、問題の解説と講評を行います。

ISU CONQUESTとは

今年も、問題に関する動画を作成いただきました。
まずは、動画を見てみましょう。


ゲームです!
育成型放置ゲームが題材です。
放置した時間で生産した椅子を売って、コインをゲットし、そのコインでガチャを回し、装備を強化し、椅子をさらに効率よく生産する、というゲームストーリーになっています。
ひたすら椅子を生産するゲームのため、椅子で世界を埋め尽くす、という謳い文句になっています。

当日の競技内容とアプリケーションの仕様については ISUCON本選当日マニュアルISU CONQUESTアプリケーションマニュアル を参照してください。今回の解説文もアプリケーションマニュアルに出てくる用語を用いて解説しています。
本選問題のレポジトリはこちら https://github.com/isucon/isucon12-final

出題の意図

作問チームのメンバーがゲーム開発しているため、ゲーム開発を体験してもらうのは面白かもしれない、と思い、題材として選びました。

問題を解いてもらうとわかるのですが、ログインがボトルネックになるように設計されています。
これは、現実のゲームの運用でもよく起きる話で、ゲーム開発経験者の方は、わかっていただけるのではないか?と勝手に思っています。

ゲームをプレイするユーザ体験をどうするか、によるのですが、通信回数が少ないほうがユーザ体験も良いよね、という考え元に自由に設計すると、今回のように、ログインだったり、特定のAPIがめっちゃ仕事する、というAPI設計になってしまいます。

また、問題を解く面白さ、という観点では、あまり派手な仕込みは自分たちで意図的に仕込むのは難しいと判断したため、地道なチューニングをする問題になっていたのではないかと思います。これも実際のゲーム開発・運用現場と似ていて、今回皆さんがチューニングしていただいたように、コツコツと積み上げる形で、改善することが多いです。

ただし、1つだけ今回の問題で、是非やっていただきたいポイントとしては、DBの水平分割でした。

ゲーム開発でMySQLを使う場合、水平分割なしでは負荷が捌けず、運用できません。
今回のテーブルも、水平分割がしやすい様なテーブル設計にしていました。
水平分割するとスケールする感覚を体感してもらえたらな、と思います。
あと、密かな思いとして、自分たちが思い付かないようなチューニングを、本選参加者にはしていただいて、その手法を、今後のゲーム開発に活かせたらな、なんてことも思っていました。

また、今回、ゲームらしさを全面に出すため、WebフロントがUnityで作成したWebGLでした。チューニングとは直接関係ない部分なのですが、ゲームらしさを感じていただけたのではないでしょうか?
このクリエイティブは、サイバーエージェントのゲーム事業のクリエイターに協力をいただき、実現することができました。

1
図1. ゲームスタート画面

2
図2. ホーム画面(初期)

3_re
図3. ホーム画面(報酬受け取り後。椅子が増えている)

解説

今回の問題で、過去のISUCONと違う部分がありましたので、先にそこだけ説明します。
今までのISUCONの問題としては、ワンソースでおおよその内容が把握できる作りになっていました。
しかし、今回、ゲームの仕様を競技に落とし込んだ時に、仕様を削るだけ削ったものの、トータルとして結構な物量になってしまいました。

結果として、user系のAPIとadmin系のAPIの2ファイルに分割し、負荷をかけるのは、user系のAPIだけとしました。
ゲームをチューニングしてもらうお題なので、admin系のAPIのチューニングは本題とは外れると判断したためです。

ただし、整合性チェック時にデータのチェックをする上で、admin系があったほうが、APIの設計として自然にデータチェックができるため、admin系のAPIも作成しています
これも実際のゲーム開発・運用現場と似ている部分で、今回はチューニングの対象としては外していますが、admin系APIも処理が重くなることが多く、実際の開発現場ではチューニングすることがあります。

シナリオ

ここでいうシナリオとは、ベンチマーカーの挙動のことを指します。
今回の問題は、特定の仕組みを突破すると負荷のかかり方が変わる、というような仕掛けはありません。
単純に、リクエストを捌くと段階的に並列数が上がる、という設計になっています。

具体的なシナリオをみていきます。
内部的にベンチマーカーは、次の3つのシナリオを並列で実行していました。
  1. 既存ユーザのログインシナリオ
  2. 新規ユーザの登録シナリオ
  3. BANユーザ(※)のアクセスシナリオ
  4. ※BANユーザとは、ゲーム運営側からユーザアカウントを停止されたユーザのことを指します。

    また、4つ目に特殊なシナリオとして、ベンチマークが走り始めて、20秒後に1回だけ実行される
  5. マスター更新シナリオ
も存在していました。


それぞれのシナリオを見ていきます。

(1)ゲームの既存ユーザのログインシナリオ
  1. ログイン
  2. ホーム画面表示
  3. 報酬受け取り
  4. プレゼント一覧表示
  5. プレゼント受け取り
  6. ガチャ一覧表示
  7. 10連ガチャを引く
上記のリクエストを順に投げていきます。
ログイン時には、ログインボーナス処理だったり、全体報酬のプレゼントの受け取り処理(プレゼントに積まれる)が実行されます。
1-7まで実行が終わると、次のユーザがまた1-7のリクエストを投げてくる、という繰り返しになります。

(2)新規ユーザの登録シナリオ
  1. ユーザ登録
  2. ホーム画面表示
  3. プレゼント一覧表示
  4. プレゼント受け取り
  5. ガチャ一覧表示
  6. 10連ガチャを引く
  7. プレゼント一覧表示
  8. プレゼント受け取り
  9. アイテム一覧表示
  10. カード強化
  11. デッキ変更
上記のリクエストを順に投げていきます。
1-11まで実行が終わると、新規ユーザがまた、1のユーザ登録のリクエストから投げてくる、という繰り返しになります。

(3)BANユーザのアクセスシナリオ
  1. ログイン(失敗)
上記のリクエストを0.5秒毎に投げていきます。ただしBANユーザのアクセスシナリオ、と書いてある通り、BANユーザのため、ログインは成功せず、ログイン失敗になります。
ゲーム運用あるある感を出すシナリオです。

(4)マスター更新シナリオ
  1. adminユーザログイン
  2. マスター更新
  3. adminユーザログアウト
上記のリクエスト、1-3を一回だけ実行します。
マスター更新時、マスターバージョンが更新されると、ユーザはログイン画面に飛ばされる、というよくあるゲームの仕様を今回の問題でも取り入れています。
ログインが一番重い処理のため、マスタ更新が走ると、一時的に負荷が高くなる、というゲームあるあるを再現するべく、このシナリオを入れています。

改善ポイント

サーバ構成

今回のサーバーは5台構成でした。
アプリケーションの動作としては、Write heavyな仕組みです。
それを踏まえると、サーバー構成は、App 1台、DB 4台が良いバランスだと思います。
4台でDBを水平分割すると、その効果が顕著に出ることを想定していました。

プレゼントテーブル

プレゼントテーブルが件数も多く、処理が重いのです。
実は、変更が加わらないデータがプレゼントテーブルにはあります。受け取り済みのプレゼントはdeleted_atに日付が入り、以降、変更が加わりません。
つまり、プレゼントテーブルは、履歴も兼ねたデータを持っているテーブル構造になっていました。

改善ポイントとしては、受け取り前のプレゼントテーブルと、受け取り済みのプレゼント履歴テーブルにわけ、テーブルのデータ件数を減らした上で、水平分割することを想定していました。

マスターテーブル

マスターテーブルも扱いに慎重になった部分かと思います。
改善ポイントとしては、マスターテーブルのデータは、全てキャッシュに入れる想定でした。

しかし、マスター更新処理が実際には発生するので、パージ処理をきちんと作る必要があります。
いくつか方法がありますが、キャッシューのキーにマスターバージョンのプレフィックスをつけてキャッシュする手法が、パージ漏れを無くす意味でも、有効な手法だと考えています。

IDの採番

水平分割をするにあたり、IDの採番が工夫のしどころになります。
改善ポイントとしては、SnowflakeIDのような、App側での採番を想定していました。
ただし、SnowflakeIDをそのまま利用すると、除算した余りで水平分割したDBを決める、というロジックと相性が悪いです。
そのため、振り分けに使用する桁(下一桁)は、乱数で生成するなど工夫が必要になります。
App一台のため、ここは、衝突確認などした上で採番できる想定です。

IDの採番を工夫することで、DBで起こっていた、キャップロックが解消され、スムーズにデータの挿入が行われる様になっていったのではないでしょうか。

クエリー

基本にしたがって、N+1の解消など、クエリーを少しでも減らすようにチューニングをしていくと、少しずつスコアが伸びていく想定でした。今回は長大な重いクエリーはありませんでした。

講評

今回の問題は、割と地味な問題ではないか、と作問側としては思っていました。
しかし、競技開始後、すごい勢いで伸びていくスコアを見て、みなさんが気持ちよく問題に取り組んでいただけてるのではないか、と安堵したのを覚えています。

また、サーバ構成が久しぶりの5台構成だったのも、みなさんに驚きとやりがいを感じていただくポイントになったのではないかと思っています。

自分の想定では、優勝スコアのラインは25万から30万の間と踏んでいたのですが、それを大きく上回るスコアの34万点までいきました。ただただ驚きです。

優勝したNaruseJunチームには、本当に驚かされることばかりでした。
5万点を一つの基準に考えており、午後1時から2時の間くらいに達成できるスコア、と設定したつもりでしたが、午前中にNaruseJunチームに達成されてしまいました。
NaruseJunチームのスコアの伸びに、ベンチマークが原因でスコアが頭打ちになってしまうのではないか、とヒヤヒヤしたものです。(事前に、43万点まで運営で確認していましたが、ドキドキしました)

すごい勢いで改善していく様は見ていて気持ちよかったですし、そのスピードは本当に素晴らしいと感じました。

謝辞

今回、本選の10日前のミーティングで「この問題なら、サーバー4台か5台の方が良いのでは?」とfujiwaraさんからアドバイスいただき、時間がない中、株式会社ドワンゴのインフラチームに、急遽サーバー構成の3台から5台の変更に対応いただきました。
この決断と対応がなければ、今回の本選問題の体験が違ったものになってしまっていたかと思います。
非常に的確なアドバイスをいただいた、fujiwaraさん、無理を通していただいた株式会社ドワンゴのインフラチームの皆様に感謝です。

本選作問チームが慣れていない点もあり、各言語移植者の方々にかなり負担をかけてしまいました。それでも間に合わせていただいた言語移植者の方には、感謝しかありません。最後までありがとうございました。

本番のインスタンスの準備をギリギリまで対応いただいた、株式会社ドワンゴのインフラチームの皆様、ありがとうございました。無理をさせてしまい、申し訳なかったです。

事前回答に協力いただいた、fujiwara組、白金動物園、エビのあらまし、都営三田線東急目黒線直通急行日吉行、百万円ドリブン、mnsysのチームの皆様、ありがとうございました。
事前回答でいただいたフィードバックのおかげで、作問チームとして盲目的になっていた部分を修正することができました。わかりやすい問題に改善できたのではないかと思っています。

最初から最後まで面白法人カヤックの作問チームの皆様には、助けていただきました。いただいたアドバイスがなければ、間に合わなかったかもしれないと、本当に思っています。ありがとうございました。

本選作問チームが最後までドタバタしてしまいましたが、本選作問チームを暖かく、時には、ケツを叩いてくださった941さん、LINEの運営のみなさま、ありがとうございました。

イベントに協力いただいた、スポンサー企業のみなさま、ありがとうございました。エンジニアとして盛り上がるISUCONが続けていけているのは、スポンサー企業の方々の協力あってのISUCONだと改めて思いました。

最後に参加者のみなさま、ISUCONに参加いただきありがとうございました。
みなさまが少しでも楽しいと感じてくれたのであれば、よかったな、と本選作問チーム一同思っています。

ありがとうございました。