(/^^)/⌒●~*$ a(){ a|a& };a

きょうと…のだいがく?にかよってるんですけど!

ISUCON9で予選通過したのでbcryptについて書く

はじめに

ISUCON9の本戦出場が決まりました. 今年から学生枠が無くなったためかなり厳しい状況になるな〜と思っていましたが、チームメンバーのおかげで通過できました.

リポジトリはこちら

私のチーム(百万円ドブリン)の状況は@nakario のブログ に詳しく書いてあるのでそちらをご参照ください. 私がしたことはbcryptをいじっていただけだったのでチームメンバーの力が如何に素晴らしいかがわかります。

bcrypt 改善について

実は去年の本戦でもbcryptが出題されていました。 GoアプリのCPUフレームグラフを見るとbcryptの処理が支配的になるのですが、 その時はGoアプリのCPUはネックになっていないため、そこをどんなに改善してもスコアが上がらない、という構成でした。 昨年はここを改善しようとして沼にハマって大敗しました。 詳しくは isucon8本戦は低レイヤーがネックにならない良問だった - (/^^)/⌒●~*$ a(){ a|a& };a を読んでいただければ。

うって変わって今年の bcrypt はかなり強めの主張をしてきました。 アプリをチューニングしていくと頻繁に login 処理が入るようになり、bcryptの処理が支配的かつCPUを大量に消費するようになります。

f:id:CHY72:20190911145737p:plain

これの直し方は以下の2つがあります。

  1. こちらが持っているハッシュ化済みのパスワードからもとのパスワードは推測できないので、ベンチマーカーからのログインを盗聴してハッシュアルゴリズムを変更し、徐々にコスト10のbcryptを取り除いていく。
  2. 本質的に改善不可能な処理なので、ログイン専用サーバーを構築し、処理を分散させる。

私は最初は1の方法を取ったのですが、実はログインはそんなに成功しないことが分かりました。 そのため試算の結果では数十回ベンチを回す必要がありそうでした*1。 加えてこの盗聴作業は楽しくなかったため、我々のチームはログイン専用サーバーを構築することにしました。 Nginxでどうやるんだったけ...とぼーっとしていたら aokabi がシュッと実装してくれました。

f:id:CHY72:20190911151158p:plain

17時前、複数台にした途端点数が跳ね上がりました。やったぜ。aokabi最高! 勝利! もちろんbcryptが支配的になるまでチューニングしてくれたnakarioも最高! 優勝!

Go の bcrypt は遅い?

本戦終了後、twitterを見ていると 「Goのbcryptは遅い」という主張がたまに目につくようになります。 これは例えばPythonのbcryptは(Pythonそのままでbcryptすると遅すぎるので)内部的にC言語で書かれており、 そのためGoのbcryptとくらべて速いのでは、という主張です。 一理あったのでGo/Python/Rubyの3バージョンで雑に計測してみます*2

コードはこちら

結果、Go実装は15秒,Python実装は14秒,Ruby実装は13秒でした。Go実装はちょっとだけ遅いものの、そこまで差は無いように見えます*3*4。 どの言語を選んでもbcryptと向き合う必要がありそうです。

最後に

感想戦をする時に盗聴をしなくてもbcryptを完全に排除できるように、 全ユーザーの生パスワードを抽出したjsonファイルを作りました!お使い下さい!

今回こそは100万円を取るぞ!

*1:bcryptをほぼ完全に取り除く場合,実際はもっと少なくても効果はでうる

*2:@手元のMac(core i5 / RAM8GB)でgo 1.11.5 / python3.7.4 / ruby 2.3.7

*3:PythonについてはCの最適化がなされていない可能性を考慮し、手動でCソースをO2/O3をつけてビルドしたPython非経由の実装も試してみましたが結果は同じでした

*4:もちろん、環境によっては特別な最適化がなされて速度が変わる可能性はあります