こんにちは、ISUCON10 の本選出題を担当した白金動物園の mirakui です。最近はパン作りにハマっています。この記事では、本選問題であるアプリケーションの「XSUCON」について、問題の概要と想定していた解き方について解説していきたいと思います。

XSUCON とは

近年の ISUCON にはとても多くの方が参加してくださり、スコアランキングを表示したりベンチマーカー実行を指示したりするいわゆる「ポータルサイト」の負荷対策には毎年の出題担当たちが苦労してきました。記念すべき 10 回目の開催である ISUCON10 ではぜひこの ISUCON ポータルサイト自体を問題にしたい、と私たち白金動物園が1年前から温めてきた構想を形にしました。

というわけで ISUCON10 の本選問題は「XSUCON」という、 ISUCON を模した仮想的な競技のポータルサイトでした。XSUCON の世界観を表現するために動画まで作ってしまいました。せっかくなので見てください。



詳しい仕様は下記のマニュアルやソースコードを参照いただければと思います。
ISUCON10 本選当日マニュアル
XSUCON アプリケーションマニュアル
ソースコード (GitHub: isucon/isucon10-final)

簡単に概要を説明すると、
  1. 最初に仮想選手登録・仮想チーム登録リクエストが押し寄せる（初期状態では10チームで締め切り）
  2. 仮想選手たちが仮想負荷走行をエンキューしたり、仮想運営に質問を投げたりする
  3. 仮想運営は、質問が来たら返答を返す
  4. 仮想選手達は仮想負荷走行が終わったかどうかや、質問の回答が来たかどうかを知るために、通知のエンドポイントをひたすらポーリングしまくる
  5. その間も仮想選手や仮想オーディエンスがスコアのダッシュボードを常にポーリングしまくる
といったシナリオでした。

なお本稿および、上記マニュアル等では ISUCON10 本選の用語と XSUCON の用語の混同を避けるため、ISUCON の用語には「実」を、XSUCON の用語には「仮想」をつけて書き分けています。たとえば「実選手」「仮想選手」といった具合です。とってもややこしくておもしろいですね（開発時のコミュニケーションでも常に混乱を招いて大変でした）。

余談ですが、フロントエンドのコードや API 設計等の多くを本選の実ポータルから流用しています。そのため、ブラウザで見たときの見た目はそっくりです（競技中に見間違えないよう背景色は変えておきました）。

01
図1: 仮想ポータルの画面（オーディエンス向けダッシュボード）

アプリケーションの構成

本選問題となるアプリケーションは仮想ポータルと仮想ベンチマークサーバという2つのサーバから成り立っていました。仮想ポータルは HTTPS を、仮想ベンチマークサーバは gRPC を採用していました。

仮想ポータルのフロントエンドは React.js で実装（これはチューニング対象外）したのですが、フロントエンドとサーバとの通信には JSON ではなく Protocol Buffers （以下 protobuf）を利用しました。ですので、仮想ポータルのサーバはあらゆる API レスポンスを protobuf にエンコードして HTTPS で返しています。protobuf を採用したのは gRPC サーバを開発する都合上、全体的に protobuf に揃えたかったというのと、あと本選問題に先行して実ポータルの開発を進めていた sorah の趣味とのことです。protobuf であらゆる API やデータ構造を定義し、仮想ポータル・実ポータル・実ベンチマーカーでバックエンド・フロントエンド通して .proto を共有して開発したところ、開発者間の情報共有やバグの防止においてとても体験がよかったです。

アプリケーションの前段には Envoy があり、これが仮想ポータルと仮想ベンチマークサーバへのリクエストを振り分けていました。Envoy を採用したのは、gRPC と HTTPS の両方を受けて振り分けたいという今回のユースケースと合っていたからというのと、近年 reverse proxy としての事例も増えてきているので最近のネタとしていいだろうという判断でした。

問題設計と出題意図

ここからは、参考実装および実負荷走行シナリオがどのようなチューニングを意図して作られていたかについて解説します。

スコア設計

参考:当日マニュアルのスコア計算式

本選問題のスコアは、「仮想選手・仮想オーディエンス・仮想運営それぞれの視点からの XSUCON の満足度の高さ」がスコアになるように設計しました。これは、ISUCON 3 から参加し続けているチーム白金動物園として、「満足度の高い ISUCON とはどういうものだろう？」ということを議論をして方針を組み立てていきました。その結果として、

XSUCON の仮想選手の視点では、
  • たくさん仮想負荷走行を実行できること
  • 仮想運営への質問がすぐに返ってくること
  • ダッシュボードが正確かつ素早く表示されること
仮想オーディエンスの視点では、
  • ダッシュボードが素早く表示されること
  • 大会が盛り上がっている（＝たくさん仮想負荷走行が実行されている）こと
    • 仮想負荷走行が実行されるたびに仮想オーディエンスが 1 人増えるようになっていました
仮想運営の視点では、
  • 多くのチームが参加すること
    • 初期値は10チームですが、100チームまで増やすと仮想選手スコアが最大2倍になるようになっていました（大会規模ボーナス）
という考え方を基本にスコア計算式ができています。仮想選手の満足度はこの中でも特にスコア比重が高いので、問題を解く上ではいかに仮想負荷走行や質問の回答頻度を上げるかが重要になってきます。

3台のサーバのリソース

本選問題では予選と同様に、スポンサーである株式会社サイバーエージェント様のご協力により、競技サーバーとして1実チームあたり3台が提供されました。実選手に対して、特にスペックはアナウンスしませんでしたが、実はこの3台はそれぞれ異なるスペックを有していました。もしこのスペック差に気付いてないと、3台への振り分けをする際に苦しむことになったかもしれません。
  • 競技サーバー1: 1 GB RAM, 2 vCPUs
  • 競技サーバー2: 2 GB RAM, 2 vCPUs
  • 競技サーバー3: 1 GB RAM, 4 vCPUs

今回はサイバーエージェント様のプライベートクラウドを利用させていただいたので、このように柔軟なリソース割り当てができ、とてもありがたかったです。いわゆるオンメモリ戦術が有利になりすぎないようメモリを少なめにしていましたが、実際のところ 1 GB はきつすぎたようで、ちょっと無理をするとサーバから応答がなくなってしまうような状況にありました。また今回は高い並列性が求められる問題だったこともあってメモリの少なさが言語の差がつく原因の一つになっていたようで、ここに関しては申し訳なく思います。

静的ファイル配信

ISUCON10 本選の実ベンチマーカーは Web ブラウザを模した挙動をするように作られていました。 ISUCON10 のために rosylilly が開発した isucandar というベンチマーカーフレームワークを利用しています。

isucandar は取得した HTML の link 要素、script 要素を解釈し、含まれている外部リソース（css, js）へのリクエストを行います。また、 favicon.ico へのリクエストもいちいちしてくれるのでリアルです。実ベンチマーカーからのアクセスログをじっくり読まれた方は、そのリクエスト群の「それっぽさ」を味わっていただけたかと思います。
初期状態では上記のような静的ファイル（css, js, favicon.ico, HTML）へのリクエストもアプリケーションで捌いてる状態になっているので、これを前段に nginx 等を置くなどすることでアプリケーションの負荷を下げることができます。

実ベンチマーカーはリクエストの際に Accept-Encoding: gzip, br, deflate のリクエストヘッダを送っていました。静的ファイルのリクエストはネットワーク帯域を考えるとそれなりに無視できない量があったはずで、nginx 等を用いて static gzip の設定をするか、実は対応していた brotli にしてあげるとかなり転送量を抑えられたかと思います。オススメは（せっかく対応したので） brotli でした……が気付いたチームはいたんでしょうか。また、マニュアルにわざとらしく書いてあるとおり実ベンチマーカーは Cache-Control に対応しているので、 max-age を設定すれば静的ファイルへのリクエスト自体を減らすことができます。仮想オーディエンスは増えるたびに新しいブラウザセッションで訪れてきてそのたびに静的ファイル配信はどんどん増えていくため、これらのような対策をしていないと次第に大きなトラフィックになっていったはずです。

SQL

提供された競技サーバーでは MySQL 8.0 が動いており、アプリケーションから利用されていました。初期状態ではこれといったスロークエリは無く、スロークエリログを有効にして張っていてもほとんど出力されなかったと思います。今回の問題では、初期状態ではすべてのテーブルは空の状態から実負荷走行が始まります。そのなかでテーブルに書き込みが走っていくので、初期状態ではアプリケーションのスループットが低くテーブルのデータがあまり増えないため、データ量起因のスロークエリが起こり始めるのはチューニングが進んだ実競技後半になるとおもいます。

そのかわり、N+1 や、本来叩く必要の無いクエリが意図的に随所に仕込んであります。一つ一つは 1ms 前後で返されるようなものですが単純に量が多いため、これらのクエリが発生しないようにアプリケーションを変えていく必要があります。
たとえば、仮想コンテストの開催時間を管理する contest_config テーブルは、/initialize 以降は更新されることがないので、負荷走行の中ではずっと使い回すことができます。
また、contestants や teams テーブルは、仮想チーム登録フェーズが終わった後は更新されることがないので、使い回すことができます。これらを protobuf にエンコードする頻度は高いため、protobuf にした状態でキャッシュしておくのもいいと思います。

ダッシュボード（Leaderboard）

実負荷走行の中でダッシュボードページは高い頻度でアクセスされますが、重い集計処理が走るようになっているので、これはチューニングが重要になってきます。

02
図2: ダッシュボードの Leaderboard 部分

ダッシュボードの Leaderboard 部分の集計は69 行もある 1 つの SQL クエリで実装されており、多くの方は見た瞬間に嫌気が差したかと思います（mirakui の力作です！）。このクエリはデータ量（仮想負荷走行の実行回数）の少ない初期状態ではスロークエリではないですがチューニングが進むと重くなっていくので、手を打っておく必要があります。対策としては

  • 仮想負荷走行が完了したときにあらかじめ Leaderboard のデータを作っておく
    • このデータ更新を同期的に行うとボトルネックになるので、非同期である程度まとめて処理するのがおすすめ（report_benchmark_job の ack は更新完了まで返さない）
  • student flag や latest / best score をカラム化しておくとよい
などが有効だったかと思います。

ダッシュボードにアクセスするのは仮想選手と仮想オーディエンスなのですが、仮想オーディエンス向けダッシュボードのみ、最大 1 秒のキャッシュが許可されていました。この 1 秒の判定はシビアで、単に1秒キャッシュをしているだけだと、アプリケーションが詰まり始めたときに「仮想負荷走行の結果が 1 秒以内にダッシュボードのレスポンスに反映されている」が達成できなくなる場合があったかと思います。このときに出力される「期待より古い内容のリーダーボードが返却されています」というエラーに悩まされたチームも多かったのではないでしょうか。
仮想オーディエンス向けダッシュボードのキャッシュについては、アプリケーションに対して同時に複数のキャッシュ更新（Thundering Herd）が走らないようにしたり、非同期でキャッシュ更新を走らせるようにしたりするのが効果的だったかと思います。たとえば Go の singleflight や Varnish を使うことでこういった制御をする事が可能です。

通知の Web Push 化

03
図3: ダッシュボードの通知機能

今回の問題では、仮想選手たちが高頻度で通知のエンドポイントをポーリングし、新着通知（仮想負荷走行の終了通知、質問仮想運営からの回答通知）を取りに来ます。今回の実ベンチマーカーは Web Push サーバーを内蔵しており、アプリケーションからの通知を Web Push 通知に実装し直すことで、ポーリングの処理を軽減できるというギミックがありました。Web Push 方式への書き換え方については、各言語でのサンプルコードを用意し、あまり高い障壁にならないように配慮していました。実ベンチマーカーへの Web Push サービスの実装は（sorah が）頑張って実装したのでぜひ使って欲しかったですが、参加者の多くは実装しなかった、あるいは実装したけどスコアが下がったのでポーリング方式に切り戻した、というご意見が多かったような印象です。実は、単にすべての状態の変化を即時に仮想選手に Web Push 通知するだけだと、仮想選手達は同時かつ即時に次のリクエストを送ってきていわゆる Thundering Herd 問題が発生し、より瞬間的な負荷が高まってしまうという状況が予想されるからです。

この状況の対応として想定していた回答の一つは、全体通知（Clarifications への回答は全選手へ同時に通知する場合がありました）については Thundering Herd 問題を避けるためにポーリング方式で処理し、それ以外の個別通知は Web Push 方式で処理する、というものです。実ポータルでは実際にそういう実装にしてありました。本選競技中になかなかそこまではしないだろうなーと思いつつも、やりこみ要素の一つとしてご理解いただければと思います。

白金動物園による解答例

本選と同じスペックの競技サーバー 3 台をお借りして sorah が解いたところ、以下のようなスコアになりました。
  • 使用言語: Ruby
  • スコア: 36,768
おもにやったことは以下の通りです（順不同）。

  • ミドルウェアの導入: nginx, Varnish, Redis
  • 最終的な競技サーバー 3 台の役割: server 1 で実負荷走行を受け、 Envoy で3台に振り分け
    • server 1 (1GB, 2 vCPUs): Varnish, 静的ファイルの配信 (nginx), benchmark_server (gRPC)
    • server 2 (2GB, 2 vCPUs): web のうちスコアに寄与しないもの, MySQL, Redis
    • server 3 (1GB, 4 vCPUs): web のうちスコアに寄与するもの, benchmark_server (gRPC)
  • 静的ファイル配信
    • nginx + static brotli
    • Cache-Control (expires 1d;)
  • receive_benchmark_jobs (gRPC)
    • benchmark_jobs のキューを Redis 化し、sleep つきループの代わりに BRPOP でジョブのエンキューを待つようにした
  • ダッシュボード（仮想選手＆仮想オーディエンス）
    • 仮想負荷走行が成功したときにあらかじめ Leaderboard を構築し、都度 Redis に保存するようにした
    • 負荷軽減のため Leaderboard はアプリケーション側で計算するようにし、例の巨大な Leaderboard SQL は廃止
    • Leaderboard の更新負荷を下げるため、時間の近い (0.3s 以内の) 複数の report_benchmark_jobs (gRPC) を待ち合わせてLeaderboard 更新を 1 回にまとめるようにした
    • 仮想オーディエンス向けダッシュボード
      • Cache-Control: public, max-age=1
      • Leaderboard から生成した ETag を付与
      • varnish でキャッシュ (ttl=0.5s, grace=0.2s)
  • 各種 N + 1 の解消, MySQL index の改善
  • カウンタキャッシュ等の導入
    • teams.student, teams.last_answered_clarification_id
  • 通知の Web Push 化
    • (Ruby のため) Envoy で HTTP/2, TLS を終端し接続処理の負荷軽減も併せて実施
    • Web Push の購読がある場合、 GetNotifications では通知を返さないように
  • Puma 4 -> 5
      • 9/17 にリリースされていた
    • 4 ->5 でのパフォーマンス改善 (wait_for_less_busy_worker で負荷の低い worker にリクエストが行くようになる等) や nakayoshi_fork によるメモリ使用量削減効果を期待
  • 参加仮想チーム数の引き上げ
    • 最高スコア時は TEAM_CAPACITY=65
  • gRPC server (griffin) や Puma の workers, threads 調整
    • 併せて envoy の max_concurrent_streams を調整して gRPC server の最大同時リクエスト数を考慮してロードバランスするように


講評

今回の本選問題はあのシンプルな予選問題とは打って変わってとても参考実装のコード量が多く（移植チームの皆様本当にありがとうございます!!!）、またマニュアルもそれなりにボリュームがあったため、全体を把握するだけで多くの時間が取られてしまったチームは多かったのではないでしょうか。また、protobuf / gRPC や Web Push、Envoy など、これまでの ISUCON に登場しなかった技術要素も登場し、これらに馴染みのないチームは頭を抱えたかもしれません。

実競技の前半は、これまでの ISUCON でも活躍してきたベテランのチームがスコアを大きく伸ばし、上位を占めていた印象です。今回の問題は最初からアプリケーションネックの状態から始まるので、複数のサーバにうまく負荷を振り分けたり、静的ファイルの負荷がアプリケーションに行かないようにしたりなど、アプリケーションコードではなくインフラの技術によって大きくスコアを伸ばせる状態だったため、サーバのリソースと相談しながらこういったチューニングを素早くできるような、経験のあるチームが有利な展開だったかと想像します。

アプリケーションの解読が進んで各チームが具体的なアプリケーション改善に取り組み始めたであろう後半では、やはりパフォーマンスチューニングの基本である、今のボトルネックを正しく計測・理解し、改善していくサイクルを精度良く回せていったチームが上位に上がっていったのだと思います。参考実装のコード量が多く、視界に入ったものを推測で改善するのではなく、やることをうまく絞っていく必要があるからです。例の巨大な Leaderboard の SQL はそのためのちょっとした仕掛けのひとつでした。経験のあるエンジニアほどあのクエリを見たら真っ先になんとかしたくなると思いますが、先に改善するべきボトルネックは他にあります。

最終的に 1 位から 3 位まで学生チームが占め、しかも 1 位は 1 人チームだったという、これまでの ISUCON の常識を覆す結果となりました。記念すべき 10 回目となる ISUCON がこのように新しい時代を感じさせる象徴的な結果となり、それに立ち会うことができたのは問題作成者の一人として誇らしく思います。

最後に、ISUCON10 の予選や本選に参加していただいたチーム、スポンサーをしてくださった企業の皆様、ISUCON10 を応援し盛り上げてくださった全ての人に感謝申し上げます。