ISUCON4 予選で workload=5 で 88000点出す方法 (lily white 参戦記)
ISUCON4 予選1日目に、 lily white というチームで参戦してきました。 試合中に 62000 点は出していたのですが、最終的に提出したスコアは 60344 点でした。
以降、予選終了までと、その後に気づいたさらにスコアを上げる方法について書いていきます。 実際の提出時のコードは methane/isucon4q-go リポジトリの "final" タグを見てください。
準備 (~前日)
予選方式が発表された時点で、 isucon3 予選と同じ方式だったので、有効な作戦もほぼ同じになる事が予測できました。 具体的には以下のとおりです。
PIOPS な EBS を使わないので、性能が不安定なディスクがネックになる問題は無いでしょう。 1インスタンスのみを使うということから、ネットワーク帯域がネックになる可能性も無いはずです。 ほぼ確実に CPU ネックな問題が出るはずです。
アプリをチューニングしていくとどうしても内容をチェックしてるベンチマーカーの方が負荷が増えます。 m3.xlarge は4コアですが、ベンチマーカーが3コア分を使い、さらに OS もCPUを使うとすると、アプリとWebサーバーあわせて 1コア分のCPUも使えない事になります。
そのため、 Python などの本来マルチコアで性能を出すためには複数プロセスを利用するのが一般的な言語でも、 1プロセス構成が強くなります。1プロセスにすることで変数上に状態を持つことができるので、DB には INSERT, UPDATE 文だけを投げ、ベンチマーク中には一切SELECT文を投げない作りができるからです。
CPU負荷を限界まで下げるために、テンプレートはレンダリング結果をキャッシュしたり、どうしてもリクエスト ごとに変わる部分はテンプレートではなく文字列連結で対処するのが強いです。
プロセス間通信のコストも限界まで下げたいので、 nginx や MySQL との通信には TCP は使わず unix domain socket を使った上で、さらにリクエストごとに接続するのではなく keep alive や connection pool を使って接続を使いまわします。
また、 Python の場合は nginx 側でなるべく多くのリクエストを処理できるようにし、それが難しいけど スコアへの影響が大きいリクエストは重厚な Flask フレームワークをバイパスして処理します。
Go の場合は、リクエストのたびにファイルを開く標準ライブラリの StaticFileHandler ではなく、 ファイルの内容をメモリ上に置いて Write するだけのハンドラを用意すれば、 nginx をリバースプロクシにするよりも Go 単体にした方が速くなります。
こういった工夫を、昨年の予選問題で、 Python と Go の両方で6万点~7万点以上だせるように練習しました。 そのコードがこちらになります。
ちなみに、 KLab はどのチームにも、実際に Web サーバーや MySQL、 Linux の設定を扱っているような インフラ運用者がいなかったので、比較的マシな僕が簡単なチートシートを用意して他のメンバーに解説 していました。 このチートシートは自分でも予選開始時に役に立ちました。
予選開始 (10:00-11:00)
本戦には外部ディスプレイを持っていく気力がないので、その予行も兼ねて、自分の準備は MacBook Air を広げて紙とペンを隣に置くだけです。
10:00 になって試合開始すると、ポータルを開いてAMIを起動して問題を把握して nginx と MySQL の設定を確認して、ベンチマーク書けてアクセスログ集計して、で1時間ほど使いました。
nginx と MySQL の設定は最低限未満だったので、これは ISUCON 夏期講習の AMI で練習した人には ツラいだろうなぁと思いながらチートシートに用意してあった設定を投入します。 my.cnf のコミットログサイズを変えたら MySQL が起動できなくなったり、 アプリの動作を目で確認しようと思って住宅ローンの申請ができなかったりはしましたが、ほぼ順調です。
この時点でアプリがすごくシンプルな上に、ログイン処理の部分は nginx + lua 以外だと nginx に閉じれなさそうなので、 Go を選択しました。
オンメモリ戦略 (11:00-13:20)
当初の計画通り、必要なデータをメモリ上に載せてベンチマーク中の SELECT 文の撲滅を目指します。
ユーザー一覧は初期投入後の追加削除が無いことを確認し、 tsv ファイルを読み込むようにしました。
ログイン履歴は DB から全件取得して初期化し、 IP ごとと ユーザー名ごとの配列にして、ログインごとに追記していきます。
この時点では sync.Mutex を使って、必ず配列への追記順と DB への INSERT 順が一致するようにしました。
あとは実際に、IPとユーザー名のブラックリストチェックを、SELECT文の代わりに配列の末尾からの列挙に置き換えるだけです。 ここでは「最終ログイン」が本当の最終の(現在ログインしている)IPではなく、その1つ手前のIPであることに引っかかりました。 サブクエリのあるSQLを見て怯んでコードリーディングが疎かになっていたようです。
書き換えが完了し、 13:20 に 33447 点を出し、暫定3位に浮上しました。
pprof (13:20-15:20)
ここからは、 go の pprof を使って地道に重い処理を削っていきます。
ですがその前に、 DB の書き込み待ちの部分が Mutex で排他されていて、 その待ち時間が pprof に現れないボトルネックになる可能性があるので、先にその部分を直します。
ロック中にする処理を配列への追加と buffered channel への書き込みだけにし、 別の goroutine で実際の INSERT を行えば、順序を保ったまま書き込みの非同期化が完了です。 pprof をすぐに使えるのと、非同期化が簡単なのが Go の強みです。
その後試しに INSERT 文を発行する goroutine を沢山動かしてみてもスコアやCPU使用率に変化がなかったので、 この時点でDB書き込みは全く問題にならないと確信することができました。 (これで配列上の順序とINSERT順が 一致しないケースが出てくるはずですが、エラーが無かったので、同一ユーザーや同一IPの同時アクセスまでは 厳密にチェックされていないようです)
pprof をみたところ、いきなり text/template.Parse が目につきました。
普通に考えるとテンプレートは1回パースしたら後は実行するだけなのに、プロファイルに出てくるのは何か変です。
Go 実装は martini というフレームワークを使って書かれていて、全く触ったことがなかったのですが、
検索するとすぐに判明しました。
MARTINI_ENV という環境変数に production を設定しないと開発モードになって、
最新のテンプレートをレンダリングするために毎回パースをしているようです。
この環境変数を設定して、 13:50 に 46419 点を提出し、暫定首位になりました。
カードがウチにそう告げるんや！ (#isucon 暫定トップ)
— INADA Naoki (@methane) September 27, 2014その後も pprof の結果に martini 関連が現れるので、地道に martini の機能を利用している部分を 直接標準ライブラリを使うように書き換えたりして、 14:10 には 51848 点を出しました。
ここで一旦集中力が途切れ、他のメンバーの様子を見たり他のチームの心配をしていたのですが、2チームに抜かれてしまいました。 簡単に削れるところを削って 15:10 に 55999 点までいったものの、1位争いの60000点台に追いつけそうにありません。 コーヒーとチョコを買いに行って気合を入れなおします。
はー。休憩して気合い入れてもうひと踏ん張りすっか。
— INADA Naoki (@methane) September 27, 2014martini 摘出と、敗北 (15:30-18:00)
コンビニから戻ってきて、
1位2位なんだよ… #isucon
— INADA Naoki (@methane) September 27, 2014と愚痴りつつ martini の完全除去を始めました。 16:10 に摘出作業が終わり 58000 点台になりましたが、ランクアップするどころか、 16:20 に 72000点台を取るチームが表れ4位に転落してしまいました。
1位おかしい #isucon
— INADA Naoki (@methane) September 27, 2014その後 GOMAXPROCS や workload の調整、 iptables を切るなどして 16:30 に 60000 点は達成したものの、 その後しばらくはスコアが上がらない時間が続きます。
今回のクライアントは keep-alive をしてくれて無いようで、 Go の標準ライブラリの http サーバーは 非 keep alive 時の性能を nginx ほどはチューニングしてないのでトップチームに勝てないんだと考え、 一旦 nginx を復活させていろいろ設定してみたものの、結局ハイスコアを更新できず nginx は諦めました。
最後に、知ってることはやって少しでもスコアを上げておこうと go の標準ライブラリの http サーバーから Date ヘッダを削って一時期 62000 点台まで行ったのですが、繰り返し計測していたら最終提出スコアは 60344 点になってしまいました。
すぐに結果速報が発表され、1日目予選勝ち抜けすらできないことが判明しました。 lily white はまだほぼ確実に決勝進出できるものの、他のチームは惨敗か、かなり厳しい状況でした。
その後
ここまで読んでくださった方、ありがとうございます。いよいよ 88000 点台を出す方法です。
試合終了後、ベンチマーカー側の動作に影響を与えるのを躊躇して試していなかった、 Go のランタイムに影響を与える環境変数を試してみることにしました。
Go の runtime パッケージのドキュメント を見たところ、チューニングできるとしたら GOGC だけです。 (GOMAXPROCS はベンチマーカーが自分で設定しているので環境変数で変更不可能でした。) 設定しない時のデフォルト値が 100 だったので、 0~100 までの範囲でチューニングするのかと思い 50 を設定してみたところ、大きくスコアが下がりました。
もう一度 GOGC の説明を読んでみたところ、 GC アルゴリズムを把握してないので完全には理解できないものの、
GCを頑張るかヒープ増やすかを判断する基準値で、大きい値を設定した方が早めにヒープを増やすようです。
実際、 200 や 500 にすると大きくスコアが伸びました。タイトルにある 88k は
GOGC=1000 ./benchmarker b --workload=5 の時のものです。
07:46:26 type:info message:finish benchmark workload: 5 ... 07:47:31 type:score success:409080 fail:0 score:88363
この設定がレギュレーション的にOKかどうか冷静になって考えてみたのですが、もともとこのクライアントは、 アプリの性能がある程度上がった所でポートを使い果たしたりファイルディスクリプタが足りなくなったり するので、ベンチマーカーに影響をあたえるような ulimit や sysctl の設定が必須でした。 環境変数の設定だけがNGのはずはありません。 workload の件と違いバグ利用でもありません。
今回の予選では "BIG丼" チームが最後に 86974 点を出し1日目トップを奪ったのですが、 この環境変数を使って 88363 点を提出していれば劇的な首位争いを演出しつつ予選トップになれたはずなので、 それができなかったのが残念です。
感想
workload の件は、運営が考えてもいない方法で攻めてくる参加者がこれだけたくさん居る以上仕方ない、 むしろこれだけで済んだし対応も納得がいくもので良かったと思います。
もともと土日連日の予選で月曜には結果発表という休みのないスケジュールだった上に、 bash の脆弱性や、 AWS 再起動祭りなど緊急の大規模なイベントの割り込みも入って来る中、運営の方々には本当に頭が下がります。
予選結果では、予想以上にいい成績を納めるチームが多くてびっくりしました。 きっとみんな去年の問題でみっちり練習していたのでしょう。 ISUCON が数百人のエンジニアにとても良い影響を与えている証拠です。
予選が始まった時は、予習がしにくい地力勝負の本戦に予習で予選を勝ち抜いたチームが出場することに対する不安がありました。 しかし、ここまで合格ラインが高いのであれば、去年の予選の合格ラインの2倍のスコア程度で満足していたチームはほとんどがふるい落とされ、 本戦にはすごい人たちが集まってくるはずです。
lily white は、チーム練習ができず、リモート参加のメンバーもいたので、各個で予選に挑戦していました。 本戦は1人で戦えるほど甘くないので、胸を張って優勝候補だと名乗れるチームに仕上げて挑戦しに行きます。
@methane
