ISUCON9で予選通過したのでbcryptについて書く
はじめに
ISUCON9の本戦出場が決まりました. 今年から学生枠が無くなったためかなり厳しい状況になるな〜と思っていましたが、チームメンバーのおかげで通過できました.
ISUCON本戦出場決定しました!! (チーム百万円ドリブン)https://t.co/Di7z2EKNX1 pic.twitter.com/5PahwX0SX9
— むらため (> <) (@paradigm_9) September 8, 2019
私のチーム(百万円ドブリン)の状況は@nakario のブログ に詳しく書いてあるのでそちらをご参照ください. 私がしたことはbcryptをいじっていただけだったのでチームメンバーの力が如何に素晴らしいかがわかります。
bcrypt 改善について
実は去年の本戦でもbcryptが出題されていました。 GoアプリのCPUフレームグラフを見るとbcryptの処理が支配的になるのですが、 その時はGoアプリのCPUはネックになっていないため、そこをどんなに改善してもスコアが上がらない、という構成でした。 昨年はここを改善しようとして沼にハマって大敗しました。 詳しくは isucon8本戦は低レイヤーがネックにならない良問だった - (/^^)/⌒●~*$ a(){ a|a& };a を読んでいただければ。
うって変わって今年の bcrypt はかなり強めの主張をしてきました。 アプリをチューニングしていくと頻繁に login 処理が入るようになり、bcryptの処理が支配的かつCPUを大量に消費するようになります。
これの直し方は以下の2つがあります。
- こちらが持っているハッシュ化済みのパスワードからもとのパスワードは推測できないので、ベンチマーカーからのログインを盗聴してハッシュアルゴリズムを変更し、徐々にコスト10のbcryptを取り除いていく。
- 本質的に改善不可能な処理なので、ログイン専用サーバーを構築し、処理を分散させる。
私は最初は1の方法を取ったのですが、実はログインはそんなに成功しないことが分かりました。 そのため試算の結果では数十回ベンチを回す必要がありそうでした*1。 加えてこの盗聴作業は楽しくなかったため、我々のチームはログイン専用サーバーを構築することにしました。 Nginxでどうやるんだったけ...とぼーっとしていたら aokabi がシュッと実装してくれました。
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万円を取るぞ!