参加者の皆さん、 ISUCON4 予選、お疲れ様でした。
ISUCON4 運営チームの @rosylilly です。
すでに予選問題の解説記事もあがっていますが、この記事では、ベンチマーカー実装者が予選参加者となるべく同じ状況で、出来る限り高得点を出すことを重点に置いたピーキーな解答例について解説します。
※ 別解となる、この記事ほどピーキーではない @sorah による解答記事はこちらです。

また、実装されたソースコードは GitHub にて公開しています。

前提

1. 実装時間は皆さんとおなじ8時間程度を想定しています
2. この実装はすべて僕一人で行います
   • 架空の想定として、運営チーム(@mirakui, @sorah, @rosylilly)で予選に参加している状況としています
   • @mirakui と @sorah がまったく別の実装を行っている設定です(去年の予選と同じ状況)
3. 僕は出題者であり、ベンチマーカー実装者
   • 問題を把握する時間などはほぼスキップできる
   • すでにどういう解法にするかある程度検討がついている

手始めに(2分)

僕の手元で EC2 インスタンスを立ち上げて真っ先にやることは

1. sudo service nginx stop
2. sudo service mysqld stop
3. sudo chkconfig nginx off
4. sudo chkconfig mysqld off

で Nginx と MySQL を停止させます。

Nginx 及び MySQL を停止させるのは、この2つに一切依存しない実装をする、と最初から決めているためです。この2つはおそらく並行作業中の @mirakui と @sorah が触っているはずなので、僕の時間内にうまくいくかどうかわからないギャンブル実装に合わせていれた変更による手戻りや、設定のコンフリクトなど、想定されうる諸問題を最初から発生させないように、僕の実装からは完全に除外するためにサービスの停止を行います。

実装方針

まずは、実装方針を固めます。実装方針はおおまかに3点。以下のように定めました。

1. 他のミドルウェアに依存しない
   • Redis であれ、 Memcached であれ、2人が使っていそうなので依存しません
   • これはベンチマーク対象をスイッチした時に事故を起こさないための措置です
     • 最終的な AMI 作成時に事故を起こすと失格になってしまいかねません
2. Go 言語で実装するが、参考実装のフォークは行わず、フルスクラッチで書く
   • Martini が入っていて便利そうなのはいいのですが、最終的にどこがボトルネックになるのかわからない以上、型による制約が多く、人の手の入った状況から書き換え難い Go ではベース実装が足かせになると踏んでの判断です
3. 後半になって完成してなかろうととにかく脇目も振らずに実装し続ける
   • 実装がパスしないことで不安になってやっぱり MySQL のチューニングで……と言いたくなっても、そこは2人のチームメンバーが必ず順当に良いスコアを出しているはずだと確信した上で気にしない
   • まずもって予選時間内に実装が間に合うかすらわからないので、とにかく作り上げることだけを考える

以上の方針ですすめていきます。

ベース実装

• User と IP のモデルを作って、インメモリ DB として Go のアプリケーション上に展開(20分)
  • 起動時に sql/dummy_users.tsv と sql/dummy_users_used.tsv を読んで初期状態を再現しておく
    • ベンチマーカーの実装を知っているため、即座に行える判断です。本来ならここだけで1〜2時間つかっておかしくないと思われます。
• 外部のパッケージは一切使わず、net/http を使った生実装を行う(2時間)
  • HandleFunc などの組み込みルーターは使わない
    • エンドポイントのリストを並べるとわかるのですが、全部一致させる必要はなく、リクエストパスの先頭1文字を比較すればどのエンドポイントへのリクエストか識別可能です
      • i もしくは s なら静的ファイルへのリクエストなので、メモリ上に読み込んでおいた静的ファイルを返す
      • l なら login の処理
      • m なら mypage の処理
      • r なら report の処理
      • 1文字以下のパスなら top の処理
      • どれにもマッチしなければ 404
• トップページの表示パターンは5種類しかないので、事前にテンプレートを実行して文字列化しておく(20分)
  • ついでに HTML テンプレート内の無駄な改行、空白を削っておく(5分)
• ロック周りに注意しつつログイン処理を実装(1時間)
  • /reportでこけるとスコアが送信されず、すべてが水泡に帰すので、それだけは避けなくてはいけない
• 再起動に耐えうる実装を追加(30分)
  • SIGINT, SIGTERM, SIGKILL を受け取ったら、現在の User, IP を json で吐き出してから終了する処理を追加
  • ベンチマーカーからの初期化処理も必要なので、 SIGHUP を受け取ったらメモリ上のデータを破棄して、上記 tsv から再度データを作る処理を追加
• init.sh で MySQL へクエリを流している部分を消去してアプリケーションへ SIGHUP を送るように変更(5分)
  • kill は即座に返ってきてしまって、初期化が終わった保証がないので、ついでに sleep 20 も入れておく
• Cookie 周りの処理を実装(30分)
  • 参考実装だと長い Cookie 名なので、_ と u に統一
  • ユーザーセッションがユーザー名を記録するようになっていて無駄なのでユーザー ID を Cookie に記録するように変更
• GOMAXPROCS はコード中で指定しない(0分)
  • 何が最適値かわからないので環境変数で指定できるように、あえてコード内での指定を行わない

ここまで実装すると、大体動くようになっているので、ベンチマーカーを走らせながらブラウザチェックも同時に行います。

並列度を上げると ulimit やローカルポート枯渇などが発生するので、その辺を何とかして欲しいと @mirakui に頼んでおく。これはきっとまっとうな実装の方でも必要な処理なので問題ない……はずです。

肌感覚で、ここまで実装するのに5時間ほど費やしました。予選はあと3時間しか残っていないので、この辺でなるべく高いスコアを出すための計測を行います。

ということで計測したのが以下のスコアです。

$ ./benchmarker b --workload 16
12:52:22 type:info  message:launch benchmarker
12:52:22 type:warning   message:Result not sent to server because API key is not set
12:52:22 type:info  message:init environment
12:52:32 type:info  message:run benchmark workload: 16
12:53:32 type:info  message:finish benchmark workload: 16
12:53:37 type:info  message:check banned ips and locked users report
12:53:37 type:report    count:banned ips    value:1035
12:53:37 type:report    count:locked users  value:5088
12:53:38 type:info  message:Result not sent to server because API key is not set
12:53:38 type:score success:259220  fail:0  score:55999

5万点……予選通過はこの時点で問題なさそうです。

(スコアの計測は後述するピーキーモード実装後にピーキーモードをオフにして行いました)

次にどこを触るか

上記のスコアでも問題なさそうですが、できうる限り高い得点を出すために、まだまだチューニングを続行します。

今回は pprof などを利用した計測は一旦行わず、単純にエンドポイント毎のレスポンスタイムを見て、重そうな所に当たりをつけて対策を検討しました。そうすると、以下の3つが浮かび上がってきます。

(pprof を使わない理由としては、単に僕が慣れておらず、ここで新しいツールを採用すると時間をロスすると判断したためです。)

1. /mypage : 平均で 200µs ほどかかっていて重たい。他の / や /login が大したことない(/ は 20µs で /login は 50µs)ことを考えると html/template のレンダリングが重そう？あとで pprof かけてもいいかも
2. /images, /stylesheets : 平均すると大したことない気がする(60µs から 80µs 程度)けど、如何せんリクエスト数が多いし、送ってるバイト数も HTML に比べ大きいので、ベンチマーカーとの通信で時間を食っている可能性が高い
3. /report : 30ms ほどかかっていて他エンドポイント達の 100 倍以上遅いけど、レギュレーションの1分以内を鑑みるに問題はまったくないので放置でよい

残り3時間でこのうちどれか一個を触るとして、一番怖くないのが 2 のエンドポイントをなんとかすることです。/mypage をいじるのも効きそうですが、テンプレートを壊すことなく、安全に終えられるかどうかが不明ですし、なによりテンプレートがボトルネックかはっきりしない以上、確実な対策とは呼べませんので、チャレンジしないことにしました。

ピーキーモードを作る(2時間)

前提として2つの方策があります。

1. レスポンスの送信がボトルネックなのであれば、 CSS を全部連結して minify をかけ、不要な CSS セレクタを削除することで対応する
2. まずもってベンチマーカーに CSS や画像へのリクエストを行わせない

CSS と画像を読み込まなくする処理はテンプレートの変更だけですみますが、もし失敗して切り戻すとなった時に、すぐに切り替えられるようにしなくてはいけません。

なので今回はシステム上で誰も使ってなさそうな AYATAKA という環境変数に 1 が入っていたら、 CSS と画像についてのチューンの入ったテンプレートで稼働させることにします。

まず、既存のテンプレートを別フォルダにコピー、有効時はそちらのフォルダを見るようにします。CSS や画像類も同じく別フォルダに丸ごとコピーして、変更を入れても影響のないように備えます。

最初に行ったのは方策1の minify でしたが、いすこん銀行が採用している bootstrap や bootflat などの CSS フレームワークでは vendor prefix が多く使われており、また、 HTML の静的解析もエラーメッセージの表示の有無などである要素ない要素があったりと、うまく行うことができず、断念しました。これだけで1時間半のロスです。

なので方針を切り替えて、方策2のまずもって読み込みを行わない、という手段を取ります。

予選問題のベンチマーカーは、 HTML 中に出現した link, script, img の要素で src もしくは href 属性を持つもののリンクをすべて取得しようとします。これは、事前にチェック対象として定義されているファイルかどうかの判断なく、書かれていればすべてリクエストしてきます。

ですが、 JS エンジンは稼働していないので、最初の読み込み後の DOM で上記要素が定義されていなければ、静的リソースへのアクセスは発生しません。これは、予選問題解説でも少し触れられている通り、ベンチマーカーのペルソナがパスワードリスト攻撃を行っている bot として実装されているためです(ある程度ブラウザに似せたアクセスを行うが、ブラウザそのものではない)。

作業としては、まず HTML テンプレートで <link> が並んでいる箇所を丸ごと <script>document.write(" ... ");</script> でくくって、遅延読み込みに切り替えます。

<img> タグの src 属性も削除して、画像の読み込みが走らないように調整。見た目が崩れてしまうので、いすこん銀行の CSS に a 要素の背景画像としてロゴを表示し、前面の img 要素には display: none で消えてもらう、という内容を追記します。

ブラウザでの表示が問題なく行えることを確認しましょう。

ここまでの実装で30分。残り制限時間は1時間ですから、あとは GOMAXPROCS や workload の調整を行います。

$ ./benchmarker b --workload 16
12:04:45 type:info  message:launch benchmarker
12:04:45 type:warning   message:Result not sent to server because API key is not set
12:04:45 type:info  message:init environment
12:04:55 type:info  message:run benchmark workload: 16
12:05:55 type:info  message:finish benchmark workload: 16
12:06:00 type:info  message:check banned ips and locked users report
12:06:00 type:report    count:banned ips    value:4942
12:06:00 type:report    count:locked users  value:14859
12:06:09 type:info  message:Result not sent to server because API key is not set
12:06:09 type:score success:237710  fail:0  score:237710

23万点 。ここまでやれば安心ですが、何度か計測を繰り返して、タイミングで Fail するようなことがないかの確認、また、再起動に耐えうるかの検証もできれば行っておきたいところです。

まとめ

この解答は僕一人で実装しており、また Go の実装以外触る箇所もほとんどありませんから、複数人で一気に触る、というのは難しいです。チーム参加前提の ISUCON において、それはいいのかと思われる方もいらっしゃるかもしれませんが、理由があってあえてこのような実装を行っています。

前年の ISUCON3 の時に参加した僕ら白金動物園チームのメンバー構成は、ざっくりと書くと以下のようになっています(これは、今回の問題作成時も変わりありません)。

• @mirakui : インフラ・ミドルウェア担当
• @sorah : アプリケーション・ミドルウェア担当
• @rosylilly : 問題特化バイナリ制作担当

この解答例のようなピーキー実装に乗り出せるのは、自分が間に合わなかったとしても、必ず @mirakui と @sorah の2人が、まっとうにチューニングを行って予選を通過してくれる。自分は最後に安全圏に飛び込むためだけに実装していればいい、という安心感あってこそです。

Go 単体で他に依存しないのも、2人が行っている作業とコンフリクトしたり、僕の実装の方で @mirakui が別ミドルウェアのチューニングを行ったりしなくていいように、という判断からきています。

実際にベンチマーカーの仕様を知っていてなお、23万点が出せた時点では残り1時間でしたし、それ以前の5万点でも残り3時間なので、これに加えて問題を一切把握しておらず、レギュレーションの読み込みや、既存コードのリーディングをする時間を含めると、今回の実装は間に合っていない可能性が高いと思われます。

限られた8時間の中でうまく作業分担を決めるのは難しく、またコンフリクトの無いようにと進めていくのは高いコミュニケーションコストがかかります。

だからこそ、あくまで最後に結果がついてくるはずだと信じて、自分の不得意な分野は完全に他メンバーに任せ、自分の得意な事を徹底して行い、チームに貢献する。もし失敗しても、その時はきっとメンバーがうまくやってくれる。メンバーが失敗したら、自分がなんとか間に合わせれば良い。という思想のもと、完全に分割した領域での作業を行っています。

ISUCON において、スコアの高い解答を出すためには、各自のスキルや能力だけでなく、いいチームとして8時間を動き続けることが必須だと、僕は考えており、また、それを実現することこそが、 ISUCON おける最難関の問題と言っても過言ではありません。

このようなピーキーな解答を作成できる裏に、こんなチーム構成がありますよ、ということで、参考にしていただければ幸いです(本戦でのメンバー変更は認められておりません。来年の参考にしてください)。

では、本選出場者のみなさん、本戦でお会いしましょう。