ISUCON7本戦、3位でした
運営の皆様お疲れ様でした。今年も本当に楽しませてもらいました。
最終スコアは27,816。2位と僅差(301点差)の3位でした。惜しかったとも言えるけど、1位は6万点超えなので惨敗です。
問題
WebSocketを使った複数人同時接続のクッキークリッカー的なゲームでした。ゲームとWebSocketは来そうな予感はしていました。ちなみに、チームメンバーは誰もクッキークリッカーやってなかった。
最初にレギューレーションを読みながら以下のような会話と作戦立てをした。
- ルームとサーバーを固定で対応させて分散すれば良さそう(シャーディング)
- データは各サーバーのローカルでみ保持できていれば良い
- コネクション多いルームとか出てくるかも(結局あまり無かった)
- 最終的にはDBいらなくなって4台配信になるだろう
- 各サーバーの足元にRedisかオンメモリか
- これはインクリメンタルな改善は厳しいかも
シャーディング
とりあえず、シャーディングしましょう、ということで手を動かし始める。言語はGoを選択。
僕は、サーバー割り当てのロジックを書くことにした。とりあえず状態持つのもメンドイので最初は雑にルーム名のハッシュ値で分散させることに。すぐ終わる予定だったが、ハッシュ値から数値を取り出すのに案外苦労した。
その間にmotemenは、 m_items (マスタデータ)を変数化したりしていた。それが素早く終わっていたので、僕がやる予定だった初期化の広報処理(どこかアクセスが来たら、全台の initialize 処理を叩きに行く)のをお願いした。それも一瞬で実装してて流石だった。
masayoshiにはサーバーの設定とか、deployの設定とか、サーバー全台にRedisを立てたりしてもらっていた。
12時くらいにお弁当が配られ始める頃にちょうどこのあたりの実装が終わった。一足飛びにRedis実装まで行くか、みたいな機運もあったんだけど、お弁当を食べながら一旦、全台にMySQL置いてベンチ回してみるか、という話になった。
その辺の設定をを終えて、飯を食いながらベンチを回す。この辺で、スコアは初期実装の5500程度から15000位まで伸び、暫定トップになったんだけど、このへんで暫定トップになるの過去を鑑みても死亡フラグな気がする。
プロファイル
これで各サーバーがシャードできたのでRedis化していくぞ！ってなりかけたんだけど、ここでmasayoshiが「でも、ベンチ中にGoのアプリが150%以上使ってて、MySQLは20%しか使ってませんよ」と指摘。言われてみれば確かにその通り。
先にやるべきはアプリの改善ということで、motemenがプロファイルを取ってくれた。pprof と go-torch を使って、flame graphを出力。
めっちゃ便利で、とにかく、どこがボトルネックか一目瞭然である。 calcStatus が全体の処理の67%を占めており圧倒的に支配的なのであった。Redis化とかオンメモリ以前にここをなんとかしないといけないぞ、となる。
この時点で開始3時間経過した13:20。暫定トップでボトルネックも見えていて、今から思うと、この時点では、かなり良い戦いをしていたように思う。
スコア26という大火傷
プロファイルを読み解いて、ボトルネックになってそうな big2exp の改善にmotemenが取り組んだ。しかし、修正を入れたら大幅にスコアが急落し、脅威のスコア26を叩き出す。暫定トップからの急落である。あとから聞いたら、これだけのスコアで逆にfailしなかったことは、運営部屋でも話題になっていたらしい。
初手でこのような手痛い火傷を負ってしまい、我々は「calcStatus怖い」となってしまった。なので、この関数自体の最適化に取り組むよりかは、キャッシュしたり呼び出しを減らす方向に方針転換した。
今から思うと、これは大きな誤りだった。ユニットテストが設けられていることから分かるように、明らかに calcStatus は最適化ポイントなのだから、もうちょっと真剣に読み解く時間を作るべきだったと競技後にチームで反省した。
細かいチューニング
てことで、以下のようなちまちました改善をおこなった。テストしやすさのためにサーバーは1台に固定しつつ開発。
- 同じ時間・同じルームで
getStatusが呼び出された時はキャッシュされた結果を返すように (Songmu) getStatusを一定時間間隔で呼び出すのではなくて、getStatusを生成するスレッドを作って、そっちから各コネクションにpushさせるように (motemen)
あまり目覚ましいスコア改善は見られず、この時点で、一台辺りのスコアは7000強。終了時間が近づいてきていて、終戦ムードに。
シャーディングの改善とGCチューニング
ハッシュでシャードするのがどうも安定しないので、素朴にラウンドロビンで分ける実装を作ることに。その間、motemenとmasayoshiは、GCのパラメーターや getStatus の間隔調整して悪あがきをしていた。そう、先のflame graphを見ると、GCが結構ボトルネックになってはいそうではあったので、ここを調整しにいくのは悪あがきとしては悪くなかったのかも知れない。
ラウンドロビンにしたらスコアは大分安定するようになった。ルーム名とサーバーの対応を記録するためにRedisを用いた。今回結局ここでしかRedisは使わなかった。
パラメーターチューニングは案外効果を発揮し、この時点で4台構成にして何度かベンチを回しても、failもせずスコアは2万は割らなくなって安定するようになった。
終戦
ここで残り30分くらいだったので、残念だけど、ここらあたりが潮時かなーというところで、各種ログなどを切るなどの小細工をして、再起動試験。再起動後、無事にアプリケーションも動いたので、後は何度かベンチを回して、27,816が出たところで打ち止めとした。
あとは、 calcStatus の実装読みながら「ここの1000回ループとかいかにも修正できそうだよなぁ」とかそういう話をしたりするなどしていた。
結果としては3位で、途中経過からすると良い順位を取れたなぁという感じではあるけど、これで満足してはいかんな、という気持ちです。
感想
運営の皆様、本当にお疲れ様でした。予選・本戦ともに過去最大級のボリュームだったと思うのですごいと思います。レギュレーションもしっかり書かれていて見事でした。本戦に関しては、結局単に一台あたりの処理能力を上げる戦いになってるなーとか思ったりはしましたが、それをうちのチーム含め、殆どの参加者はチューニングしきれなかったわけで、そういう問題だったんだなと思ってます。
来年の開催を願っています。はてなメンバーだけで優勝したい。
ちなみに、去年は予選・本戦で別の会社が作問しており、予選がはてなで決勝がpixivでした。僕は予選側の作問担当だったのですが、その形式はお互いの負担軽減以上の効果があったように感じています。お互いの問題を知らない状態で、相互にリハーサルができたことが一番良かったことで、それが難易度調整だったり、作問者が気付かない盲点の発見になりました。来年は可能であれば、その形式に戻した方が良いんじゃないかと思っています。