こんにちは、ISUCON4 運営チームの @mirakui です。 @rosylilly @sora_h とともに ISUCON4 の問題作成と運営を担当しています。
さて、予選に参加していただけたみなさんは楽しんでいただけたでしょうか。今回は、予選問題の振り返りをしたいと思います。
銀行とはいっても、実は銀行としての機能は一切ないハリボテで、今回用意したのは ログイン機能 のみです。ログインって機能なの? と思うかもしれませんが、実際のウェブサービスを作る上で、ログイン部分の設計は単純では済みません。
それは、近年増加している「パスワードリスト攻撃」のような、不正ログインの対策を行わなければならないからです。
「いすこん銀行」には、ログイン画面と、ログインに成功した時に表示されるマイページの2画面しかありません。
ログイン画面でユーザ名とパスワードを入力し、ログインに成功するとマイページに遷移することができますが、失敗した場合、エラーメッセージを表示してログイン画面に戻ります。
このとき「いすこん銀行」は次のような条件で不正なログインとみなし、それ以降はログイン禁止にします。
一つのユーザIDに対して試みたログインで、連続3回以上パスワードを間違えた場合、それ以降そのユーザIDはログイン不可能になる 同一IPアドレスから試みたログインで、連続で合計10回以上パスワードを間違えた場合、それ以降そのIPアドレスからはログイン不可能になる
今回の予選問題は、とにかくシンプルな問題にすることを意識して設計されました。最初は、銀行アプリケーションなので暗証番号表を用意しようとか、他アカウントへの振込み機能を作ろうとか言っていたのですが、工数の都合シンプルさを重視して、最終的にログイン機能のみを残しました。
ログインを題材にしたのは、「パスワードリスト攻撃」を念頭に置いた、時事問題といったところです。
そして、ログインが試みられたときに、そのユーザもしくはIPアドレスがアクセス禁止になっているかどうかを、このログから計算して判定しています。
「いすこん銀行」では、/report にアクセスすると、ログイン禁止になったIPアドレスやユーザIDのリストを JSON で出力する機能があります。これは管理者用の機能を想定しています。
そして、この /report は、この問題において最も重要なものです。
ログイン失敗数は、インメモリであったり、Redis や Memcached などでカウンタキャッシュを持てば用意すれば高速に処理する事ができると思います。
/report の内容を作るのにもログインログは使わずに、カウンタキャッシュだけあれば問題なかったりしますが、これを揮発性のデータストアに入れていると、サーバ再起動後に /report の内容が異なってしまい、レギュレーション違反となってしまうため、ここに関しては工夫が必要でした。
ところで、 benchmarker の /report のチェックに関しては、以下のようなルールがありました。
> 負荷走行の最後に、 benchmarker は5秒の待ち時間をおいた後、 /report にリクエストを行う。この /report は1分以内にレスポンスを返さなければならない。
「5秒の待ち時間をおいた後」というのは、負荷走行の後にログインログをメモリから MySQL に書き出せばよいというのを意識して設定しました。
また「/report は1分以内にレスポンスを返さなければならない」というルールで、タイムアウトが「1分」と比較的長めに設定してあるのは、集計をそれほど高速化しなくてもよいというメッセージでもありました。
逆算すると、本選出場のためには1分間の負荷走行において平均約1.6ms、630 request/sec でレスポンスを返さなければならないということになります。
これほどの低レイテンシを初期状態の LL + MySQL 構成のまま実現するのは簡単ではないでしょう。結果として、
今回、ログインページ(トップページ)は4パターンしかないため、キャッシュする ログインログへの書き込みをインメモリ、もしくは高速なミドルウェアに置き換える Golang, C++ (!?) などの高速なコンパイル言語ですべて処理できるようにする
というのが基本的な戦略になったようです。
このように、コンパイル言語と比べて LL が不利になりがちな、低レイテンシ・高rpsの勝負となった予選ですが、予選を勝ち抜いたチームの多くが LL を利用しており、これも ISUCON の面白いところだと思います。
本戦出場チームの利用言語割合:
> Ruby 9組 31.0%
> Go 7組 24.1%
> PHP 6組 20.6%
> Perl 6組 20.6%
> C++ 1組 3.4%
これが言語の有利不利を表現しているわけではありませんが、初期スコアには差があったことが分かります。
なお、実装の都合上、 PHP だけは最初から CSS などの静的ファイルを Nginx で返す設定にしてあったことも補足しておきます。
賛否両論あると思いますが、機械的なチェックには限界があったり、厳密なチェックをしようとすると benchmarker の負荷が高くなったり、実装が大変だったりしてしまうので、benchmarker によるレギュレーションのチェックはそこそこにして、運営によるチェックをしっかりやるというのが今回の予選でした。
ISUCON4 本選出場の一部基準変更についての詳細 : ISUCON公式Blog
この問題に関して、ご迷惑をおかけして申し訳ありませんでした。
レギュレーション: ISUCON4(2014) オンライン予選レギュレーション : ISUCON公式Blog 当日マニュアル: ISUCON4 予選当日マニュアル 予選問題のソースコード:isucon4/qualifier at master · isucon/isucon4 予選で使われたAMI: ami-e3577fe2
それでは、ISUCON4 本選をお楽しみに!
さて、予選に参加していただけたみなさんは楽しんでいただけたでしょうか。今回は、予選問題の振り返りをしたいと思います。
予選問題「いすこん銀行」
今回の予選問題は、「いすこん銀行」という架空の銀行の Web サービスがテーマでした。銀行とはいっても、実は銀行としての機能は一切ないハリボテで、今回用意したのは ログイン機能 のみです。ログインって機能なの? と思うかもしれませんが、実際のウェブサービスを作る上で、ログイン部分の設計は単純では済みません。
それは、近年増加している「パスワードリスト攻撃」のような、不正ログインの対策を行わなければならないからです。
「いすこん銀行」には、ログイン画面と、ログインに成功した時に表示されるマイページの2画面しかありません。
ログイン画面でユーザ名とパスワードを入力し、ログインに成功するとマイページに遷移することができますが、失敗した場合、エラーメッセージを表示してログイン画面に戻ります。
このとき「いすこん銀行」は次のような条件で不正なログインとみなし、それ以降はログイン禁止にします。
今回の予選問題は、とにかくシンプルな問題にすることを意識して設計されました。最初は、銀行アプリケーションなので暗証番号表を用意しようとか、他アカウントへの振込み機能を作ろうとか言っていたのですが、
ログインを題材にしたのは、「パスワードリスト攻撃」を念頭に置いた、時事問題といったところです。
ログインの記録と判定の実装
「いすこん銀行」の参考実装では、全てのログイン試行において、リモートIPアドレス、ユーザID、ログイン成功可否をログとして MySQL に保存しています。そして、ログインが試みられたときに、そのユーザもしくはIPアドレスがアクセス禁止になっているかどうかを、このログから計算して判定しています。
レポート機能
不正なログインが来ているのかどうかはサイト管理者にとって心配の種です。ましてや銀行ならなおさらですよね。「いすこん銀行」では、/report にアクセスすると、ログイン禁止になったIPアドレスやユーザIDのリストを JSON で出力する機能があります。これは管理者用の機能を想定しています。
そして、この /report は、この問題において最も重要なものです。
レポートをどう作るか
今回のアプリケーションには「ログイン試行のたびにログイン失敗数の判定をログインログから計算している」という無駄があります。ログイン失敗数は、インメモリであったり、Redis や Memcached などでカウンタキャッシュを持てば用意すれば高速に処理する事ができると思います。
/report の内容を作るのにもログインログは使わずに、カウンタキャッシュだけあれば問題なかったりしますが、これを揮発性のデータストアに入れていると、サーバ再起動後に /report の内容が異なってしまい、レギュレーション違反となってしまうため、ここに関しては工夫が必要でした。
ところで、 benchmarker の /report のチェックに関しては、以下のようなルールがありました。
> 負荷走行の最後に、 benchmarker は5秒の待ち時間をおいた後、 /report にリクエストを行う。この /report は1分以内にレスポンスを返さなければならない。
「5秒の待ち時間をおいた後」というのは、負荷走行の後にログインログをメモリから MySQL に書き出せばよいというのを意識して設定しました。
また「/report は1分以内にレスポンスを返さなければならない」というルールで、タイムアウトが「1分」と比較的長めに設定してあるのは、集計をそれほど高速化しなくてもよいというメッセージでもありました。
高rpsの戦い
今回の本選出場のボーダーラインとなったスコアは「Team Ku's」チームの 37,808 でした。逆算すると、本選出場のためには1分間の負荷走行において平均約1.6ms、630 request/sec でレスポンスを返さなければならないということになります。
これほどの低レイテンシを初期状態の LL + MySQL 構成のまま実現するのは簡単ではないでしょう。結果として、
というのが基本的な戦略になったようです。
このように、コンパイル言語と比べて LL が不利になりがちな、低レイテンシ・高rpsの勝負となった予選ですが、予選を勝ち抜いたチームの多くが LL を利用しており、これも ISUCON の面白いところだと思います。
本戦出場チームの利用言語割合:
> Ruby 9組 31.0%
> Go 7組 24.1%
> PHP 6組 20.6%
> Perl 6組 20.6%
> C++ 1組 3.4%
参考実装の初期スコア
ちなみにですが、各言語の初期スコアは以下のとおりでした。これは参考実装を何も変更せずに、 workload=1 で benchmarker を実行した結果です。これが言語の有利不利を表現しているわけではありませんが、初期スコアには差があったことが分かります。
なお、実装の都合上、 PHP だけは最初から CSS などの静的ファイルを Nginx で返す設定にしてあったことも補足しておきます。
AMIの審査
今回は /report のチェックが失敗したときのみ Fail するようにしていて、それ以外のレスポンスが間違っていても、スコアが伸びないだけです。その代わりに AMI 審査のチェックを運営がしっかり行い、レギュレーションに基いて表示崩れなどを失格にしています。賛否両論あると思いますが、機械的なチェックには限界があったり、厳密なチェックをしようとすると benchmarker の負荷が高くなったり、実装が大変だったりしてしまうので、benchmarker によるレギュレーションのチェックはそこそこにして、運営によるチェックをしっかりやるというのが今回の予選でした。
レギュレーションの変更
今回は以前公開したとおり、予選1日目に使った benchmarker に高スコアを出せてしまうバグがあり、2日目ではそのバグを修正しています。ISUCON4 本選出場の一部基準変更についての詳細 : ISUCON公式Blog
この問題に関して、ご迷惑をおかけして申し訳ありませんでした。
予選問題とAMIの公開
以下のとおり予選問題を公開しますので、復習などにご利用ください。それでは、ISUCON4 本選をお楽しみに!