isucon8本戦は低レイヤーがネックにならない良問だった

TLDR;

  • ISUCON8に参加した
  • 感想戦は41万点出た
  • ISUCON8本戦は低レイヤーがネックにならない良問だった

はじめに

ISUCON8に参加してきました. 私のチーム(百万円ドブリン)の状況は @nakario のブログに詳しく書いてあるのでそちらをご参照ください.

うちのチームでは @nakario が Goをゴリゴリゴリゴリと書きWebアプリケーション自体を高速化し, @aokabi が MySQL と Nginx を触ったり複数台構成の準備をしていました. 二人のプロがいるので僕は踊っているだけでよくて最高でした.

やったこと

予選

匿名関数を剥がしたり,高速化後のデッドロック要因の select ... for update の for update をなんとなく消す役割をしていた様子. 怪しいところを消すガチャ要員です.

本戦

Dockerを剥がしたりbcrypt をなんとかしようとしていました. pprof だけを見ると bcrypt しかCPUを食っていなかったからですね. CPUはネックではなかったので直す意味はなく,これは完全に罠だったので反省.

bcrypt について

結論としては signup の時のハッシュ化するときの cost を デフォルトの 10 から 4 (最低値)にする程度で十分です. ハッシュ化は 2^{cost} 回行われるため,この変更だけでハッシュ化は64倍早くなり,signup処理はほぼ一瞬になります.

bcryptが大変そうに見えるsigninは,実は成功するユーザー数はとても少なく, 例えば成功したユーザーのハッシュ化のコストを4にするなどの小手先の技では効果はありません. signinを完全に潰すには, DBに保存されているハッシュ値から元のパスワードを当てて全てコスト4にして保存するしか方法はありません. なお,もしもそれが出来たら bcrypt の脆弱性を見つけたのと同値ですのでISUCONより先にセキュリティ系の学会あたりに報告したほうがいいと思います.

ちなみに問題設計としては,signin はBan処理の実装だけで十分なようになっていました. ユーザーが多くなってくると, info や runTrade 関係の処理がネックを占めてくるようになり, signinのbcryptの比重は自然に減っていくため手を付ける機会は永遠に訪れないのです.

感想戦

本戦当日では5000点程度で終わってしまいましたが, それはそれとして日曜日に集まって感想戦をやっていました. これは賞金をもらえないので意味は無いように思えますが, どこまでチューニングできるものなのかを知れて大変楽しいものです.

twitter.com

最終的に41万点くらいでたので満足です.

41万点への道のり

https://github.com/aokabi/isucon8f (現在非公開repoですがそのうち公開してくれると思います)

感想戦では,aokabitが複数台構成を行い, nakario がISUCON8 本選問題の解説と講評 : ISUCON公式Blog に書かれている高速化作業を全部やってくれました.すごい.

goroutineの数でshare機能の有無を決めたり, singleflightを取り入れたり,Ban機能を実装したり,ロウソク足を改善したり,LIMIT 1 を入れたり, send_bulk をやったりを全部nakarioがやってくれました. すごすぎる. それを aokabi が4台に分散させたところで 6万点くらいまでいっていました.

更に最後に nakario が info の N+1を消したり クッキーを活用したり といった処理を入れたところで20万点くらいまで行きました. 最終的にはコネクション数がネックになっていたように見えたので info の N+1 を消したりクッキーで不要なSQL通信を減らすと得点が爆上がりしたのを見ると面白いなあという感じです.

20万点からあと上げる作業では,要はコネクションを安定させながらユーザーを増やせばいいので, アプリに db.SetMaxIdleConns(1024) を加えてコネクションプールをしたり, nginxの設定でgoのアプリとの間のkeepaliveを設定したりしてコネクションを安定させました.

(編集注: nakario,aokabi担当分に関して,僕が間違った解釈をしている可能性があるので鵜呑みにはしないでくださいね).

ISUCON8本戦は低レイヤーな部分がネックにならない良問

ISUCON本戦まで,毎週日曜日にISUCONの過去問や公開社内ISUCONを解くという集まりをやっていました. その中でISUCON8本戦がすごいなあと思ったのは低レイヤーな部分がネックにならない作りになっていたところです.

低レイヤーについて,ここでは 標準ライブラリの実装では遅いので高速化する箇所 と定義します. 標準ライブラリでは様々な入力ケースに対応する必要があるので得てしてオーバーヘッドがかかります. これを高速化する作業は著しく保守性を損なうため通常のWebアプリケーションでは絶対にいじりたくない場所ですが, なんでもありのISUCONならこれをやる必要が出てきてしまうものです.

以下,過去問でそのレイヤーを見てみます.

ISUCON7本戦の低レイヤー

https://github.com/nakario/isucon7f2 ここでの低レイヤーは BigInt と json化 です.

BigIntの高速化については ISUCON7本戦でBigintを殺したかった話 - (/^^)/⌒●~*$ a(){ a|a& };a にて考察しています. json化の高速化作業は,リフレクション的な作業がgoで行われるのが遅い原因なので, json化するGoのコードを生成する fastJson を導入すれば消すことが出来ます.

ISHOCON2 の低レイヤー

GitHub - nakario/ishocon2 ここでの低レイヤーは PostのFormの読み込み と Goのテンプレートエンジンのレンダリング です.

Go の PostForm では,Formが1つしかなくても複数あった場合を想定して, フォームが1つの場合の解析と,複数の場合の解析と二度解析してしまいます. ですので標準ライブラリを読みながら複数の方の解析をしないPostFormを作ることで2倍位早くできます.

Goの標準ライブラリには html/template があり,大体のレンダリングエンジンにおいてこれを内部で使用しています. ただ,これは構文解析やeval的な操作をしてしまうので余計なオーバーヘッドがかかってしまいます. 解決方法は fastJsonと同じで,要はGoのコードにしてしまうことです. これを解決するために,.tmpl ファイルを静的解析して .go のファイルを生成するNimのコードを書いたので,よければ使ってください.

yisucon の低レイヤー

GitHub - nakario/yisucon ここでの低レイヤーは Goのテンプレートエンジンのレンダリング です.同じなので割愛.

ISOCON1 での低レイヤー

GitHub - Muratam/ishoisho1111: 158160点 ここでの低レイヤーは Goのテンプレートエンジンのレンダリング と 時刻のパースです.

時刻のパースはどうしてもformatの解析ののちscanという二度手間を挟んでしまうので, 直書きしてしまうことで解決します.

低レイヤーについて

以上見たように htmlやjsonを生成してユーザーに返すリクエストが多い問題では, どうしてもこういった低レイヤー部分がネックの一つになってしまうという問題があります. 今回の問題を41万点までチューニングしたわけですが, 一つもこういう低レイヤーの部分が表面化せず,良問だったなあと思いました.

例えばもし今回問題設計のバランスが悪ければ bcrypt のハッシュ化がネックになり得たわけで, 頑張れば定数倍高速化出来たのかなーとかちょっと思ったりしていました.

どうも過去問では僕はこういった部分ばかり率先して担当していたようで(低レイヤーは楽しいので), 今回の問題でずっと踊るしか出来なかったのはISUCON8本戦が低レイヤーが問題にならない良問だったからかなあと思いました.

最後に,ISUCONやそれに類する問題を作成・運営してくれた方々すべてに最上級の感謝を込めて結びとします.