ISUCON公式Blog

WINNER'S PRIZE \1,000,000



   

ISUCON4 予選お疲れさまでした! 予選問題の Ruby 初期実装などを担当した @sora_h です。

予選はたのしんでいただけましたでしょうか? 本記事では、ざっくりとそこそこのスコアを出す解き方を紹介しようと思います。
※@rosylillyによる、高得点を出すことを重点に置いたピーキーな解答例はこちらです

前提

  • 一人でやる
  • 一応8時間経過時点でスコアをとる
    • ただし出題者であるので問題の把握などの時間は短縮されていることに注意。
  • Ruby の実装を利用する
  • ある程度、現実味のあるチューニングが主
    • ベンチマーカーの実装を利用したりしない

また、この記事で出来た実装は GitHub に掲載しています: https://github.com/sorah/isucon4-qualifier-sorah

初期スコア

とりあえず立ち上げて動かした時のスコアは success:6030 fail:0 score:1303 でした (workload=1)

チューニング

ここからチューニングしていきます。

失敗数のカウンタを Redis にのせかえる (2 時間経過)

問題を読むとログを残す必要は一切ない事がわかるので、とりあえず mysql でログを取るのをとめて、Redis をカウンターとして利用するように変更します。

ただし、MySQL でも適切な index を張ればスコアが出せます。この辺は好みだと思われます。

  • isu4:user:<id>, isu4:ip:<ip> をカウンタとして連続失敗数を記録 (INCR)
  • isu4:last:<id>, isu4:nextlast:<id> を最終ログイン記録に利用

スコアはこの時点で "success:29430 fail:0 score:6357" (workload=1)

これはあまりスコアに影響はなかったのですが、少し後で users テーブルも redis にのせることにより、
完全に mysql をとりのぞいています。

nginx で静的ファイルを配り、app process との接続を UNIX ドメインソケットに

見出しのまま。この時点でのスコアは workload=1 で "success:52550 fail:0 score:11351".
workload=16 にしたら 23994 点を記録しました。

erb が遅いのでレンダラーを erubis に入れ替える

erb を高速にレンダリングできる erubis を導入しました。

Sinatra を捨てる (4 時間経過)

ここで Sinatra の実装を見てみたら、意外に重そうだった事を思い出したので、捨てて、Rack アプリケーションとして実装しなおしました。

workload=16 で success:158590 fail:0 score:34265 を記録。

アプリケーションの細かいチューニング (6 時間経過)

引き続きボトルネックはアプリケーション側にあるので、気になったところをどうにかしていきます。
プロファイリングには stackprof.gem を利用しました。

この前後でスコアは 37228 点。

トップページのほぼ静的ページ化 (7 時間経過)

5 種類しかないので起動時にレンダリングしておいてクッキーの値を見て切り替えるようにしました。
実際予選上位ではこれ以外にも、URL のクエリストリングを利用しているチームもあったようです。

この時点でスコアは 39144 点でした。

ルーティングの改善 (およそ 8 時間経過)

自前で書いたルーティング処理が遅いので高速化しました。

この時点で、予選当日の競技での 8 時間が経過しました。8 時間経過時点でのスコアは workload=16, score=40324 点でした。

そして、ここからさらに粘ります。

アプリケーションの細かいチューニング (2)

この辺からはわりと試行錯誤しています。本当に効果あるかどうか微妙な変更もある気がする。

その他

パフォーマンスには影響ありませんが、Can't assign local address と Too many open files 対策で以下を追加しています。

# /etc/sysctl.conf
net.ipv4.tcp_tw_recycle = 1
net.ipv4.tcp_tw_reuse = 1

# /etc/security/limits.conf
* hard nofile 65535
* soft nofile 65535

(net.ipv4.tcp_fastopen = 2055 も追加していたんですが、スコアに大した影響はありませんでした)

最終スコア (8時間+)

12:19:44 type:info      message:launch benchmarker
12:19:44 type:warning   message:Result not sent to server because API key is not set
12:19:44 type:info      message:init environment
12:19:58 type:info      message:run benchmark workload: 10
12:20:58 type:fail      reason:Request cancelled because benchmark finished (1min)      method:GET      uri:/stylesheets/isucon-bank.css
12:20:58 type:fail      reason:Request cancelled because benchmark finished (1min)      method:GET      uri:/images/isucon-bank.png
12:20:58 type:fail      reason:Request cancelled because benchmark finished (1min)      method:GET      uri:/stylesheets/bootflat.min.css
12:20:58 type:info      message:finish benchmark workload: 10
12:21:03 type:info      message:check banned ips and locked users report
12:21:06 type:report    count:banned ips        value:654
12:21:06 type:report    count:locked users      value:4650
12:21:06 type:info      message:Result not sent to server because API key is not set
12:21:06 type:score     success:209927  fail:3  score:45350

workload=10 でこのようなスコアになりました。Ruby レベルではほぼ限界にチューニングしてあると思います。
(これでも上位チームはおろか Ruby を利用したチームのトップにすら勝てていなくて、皆さんすごいなあと思っています)

MySQL の場合

Redis を採用したのは筆者の趣味なので、同じ実装で MySQL に戻し少し手を加えたところ、 workload=10 で success:191040 fail:0 score:41270 を記録しました。

オリジナルの MySQL 関係から変更した点:

  • すべてにおいて users.id を利用しなくして、users.login を利用するようにした
  • index 追加と my.cnf に数行追加

MySQL 版はこちら: https://github.com/sorah/isucon4-qualifier-sorah/tree/mysql

まとめ

Ruby 実装を利用した解き方の一つを紹介しました。

運営チームは ISUCON4 本選も楽しんでいただけるような問題を準備中です。お楽しみに!

Read more...

こんにちは、ISUCON4 運営チームの @mirakui です。 @rosylilly @sora_h とともに ISUCON4 の問題作成と運営を担当しています。

さて、予選に参加していただけたみなさんは楽しんでいただけたでしょうか。今回は、予選問題の振り返りをしたいと思います。

予選問題「いすこん銀行」

今回の予選問題は、「いすこん銀行」という架空の銀行の Web サービスがテーマでした。
01

銀行とはいっても、実は銀行としての機能は一切ないハリボテで、今回用意したのは ログイン機能 のみです。ログインって機能なの? と思うかもしれませんが、実際のウェブサービスを作る上で、ログイン部分の設計は単純では済みません。

それは、近年増加している「パスワードリスト攻撃」のような、不正ログインの対策を行わなければならないからです。

「いすこん銀行」には、ログイン画面と、ログインに成功した時に表示されるマイページの2画面しかありません。
ログイン画面でユーザ名とパスワードを入力し、ログインに成功するとマイページに遷移することができますが、失敗した場合、エラーメッセージを表示してログイン画面に戻ります。

このとき「いすこん銀行」は次のような条件で不正なログインとみなし、それ以降はログイン禁止にします。

  • 一つのユーザIDに対して試みたログインで、連続3回以上パスワードを間違えた場合、それ以降そのユーザIDはログイン不可能になる
  • 同一IPアドレスから試みたログインで、連続で合計10回以上パスワードを間違えた場合、それ以降そのIPアドレスからはログイン不可能になる


  • 今回の予選問題は、とにかくシンプルな問題にすることを意識して設計されました。最初は、銀行アプリケーションなので暗証番号表を用意しようとか、他アカウントへの振込み機能を作ろうとか言っていたのですが、工数の都合シンプルさを重視して、最終的にログイン機能のみを残しました。

    ログインを題材にしたのは、「パスワードリスト攻撃」を念頭に置いた、時事問題といったところです。

    ログインの記録と判定の実装

    「いすこん銀行」の参考実装では、全てのログイン試行において、リモート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 構成のまま実現するのは簡単ではないでしょう。結果として、

  • 今回、ログインページ(トップページ)は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%


    参考実装の初期スコア

    ちなみにですが、各言語の初期スコアは以下のとおりでした。これは参考実装を何も変更せずに、 workload=1 で benchmarker を実行した結果です。

    02


    これが言語の有利不利を表現しているわけではありませんが、初期スコアには差があったことが分かります。

    なお、実装の都合上、 PHP だけは最初から CSS などの静的ファイルを Nginx で返す設定にしてあったことも補足しておきます。

    AMIの審査

    今回は /report のチェックが失敗したときのみ Fail するようにしていて、それ以外のレスポンスが間違っていても、スコアが伸びないだけです。その代わりに AMI 審査のチェックを運営がしっかり行い、レギュレーションに基いて表示崩れなどを失格にしています。

    賛否両論あると思いますが、機械的なチェックには限界があったり、厳密なチェックをしようとすると benchmarker の負荷が高くなったり、実装が大変だったりしてしまうので、benchmarker によるレギュレーションのチェックはそこそこにして、運営によるチェックをしっかりやるというのが今回の予選でした。

    レギュレーションの変更

    今回は以前公開したとおり、予選1日目に使った benchmarker に高スコアを出せてしまうバグがあり、2日目ではそのバグを修正しています。

    ISUCON4 本選出場の一部基準変更についての詳細 : ISUCON公式Blog

    この問題に関して、ご迷惑をおかけして申し訳ありませんでした。

    予選問題とAMIの公開

    以下のとおり予選問題を公開しますので、復習などにご利用ください。

  • レギュレーション: ISUCON4(2014) オンライン予選レギュレーション : ISUCON公式Blog
  • 当日マニュアル: ISUCON4 予選当日マニュアル
  • 予選問題のソースコード:isucon4/qualifier at master · isucon/isucon4
  • 予選で使われたAMI: ami-e3577fe2


  • それでは、ISUCON4 本選をお楽しみに!

    Read more...

    オンライン予選後レギュレーションに則り、参加者から提出された AMI を元に主催者が実行し競技時間中に計測された性能値に近い値が再現できるかを確認いたしました。その結果、本選出場者は以下となります。スコア、チーム名、利用言語、の順となっています。

    本戦出場者

    予選第1日トップ5枠
    1. 82386 チームフリー素材 [Go]
    2. 65398 鉄球 [Ruby]
    3. 62145 山形組 [Perl]
    4. 60344 lily white [Go]
    5. 45742 ご注文はPHPですか? [Go]

    予選第2日トップ5枠
    1. 67782 fujiwara組 [Perl]
    2. 51045 .dat [Go]
    3. 49199 SHINCHOKU.ZERO [C++]
    4. 46875 椅子子 [Ruby]
    5. 42809 EH-MTI [Ruby]

    総合トップ13枠
    第1日・第2日それぞれのトップ5をのぞいた一般参加チームの中から、上位13チームを選出しました。

    1 . 42638 ナイスカロリー [PHP]
    2 . 41748 Beer Qz's [Ruby]
    3 . 41705 (40618) GoMiami [Go]
    4 . 41640 (39599) 矢澤 [PHP]
    5 . 41266 (42134) マカレラーズ [Perl]
    6 . 40418 (42120) Printemps [PHP]
    7 . 40268 (43298) MEAN普及委員会 [Go]
    8 . 39377 Oops! [PHP]
    9 . 39363 (38855) Mr. Frank & Co: A New Hope [Ruby]
    10 . 38960 (40115) 部長と副部長 [Go]
    11 . 38921 (40079) 50ms or die. [Perl]
    12 . 38802 (30180) PHPに花束を [PHP]
    13 . 37808 Team Ku's [PHP]

    ※予選1日目の参加者のみ、スコアのレギュレーションが異なるため、参考値としてカッコ内に提出時のスコアを併記しています。詳しくは下記をご覧ください。
    ISUCON4 本選出場の一部基準変更についての詳細 : ISUCON公式Blog

    学生枠
    1. 17764 (ρ_-)/超銀杏バスターズ(・ω・ o) [Ruby]
    2. 16544 (86974) BIG丼 [Ruby]
    3. 13980 blacklab [Ruby]
    4. 8859 (8602) railsへの執着はもはや煩悩の域であり、開発者一同は瞑想したほうがいいと思います。 [Ruby]
    5. 6621 (6490) ☆(ゝω・)vキャピ[Perl]
    ※予選1日目の参加者のみ、スコアのレギュレーションが異なるため、参考値としてカッコ内に提出時のスコアを併記しています。

    予選第1日にご参加いただいた「twiskuld」チームは、提出時のスコアは 11209 でしたが、レギュレーション変更に従って第2日と同じ benchmarker (v2) で計測しなおしたところ、スコアが 5447 となったため、ランク外となってしまいました。申し訳ございません。

    運営枠
    ・LINE選抜「生ハム原木」(予選スコア 51192)[Perl]
    ・クックパッド選抜「†空中庭園†《ガーデンプレイス》」(予選不参加)
    ・DATAHOTEL選抜「チームレッド」(予選不参加)

    以上、 28 チームが本選出場となります。

    利用言語比率

    本戦出場チームの利用言語比率は以下の通りです。(予選不参加の2チームを除く)
    Ruby 9組 31.0%
    Go  7組 24.1%
    PHP  6組 20.6%
    Perl  6組 20.6%
    C++  1組  3.4%


    AMI 審査について

    提出いただいた AMI について、レギュレーションに基づき、以下のような手順で審査を行いました。

    1. AMI から EC2 インスタンスを起動
    2. CPU の確認
    - 「Intel(R) Xeon(R) CPU E5-2670 v2 @ 2.50GHz」でなければ 1 からやり直す
    3. benchmarker を指定されたオプションで実行
    - 負荷走行が完走しなかったり、 report チェックが失敗すれば失格
    - 提出されたスコアと近いスコアが再現できなければ失格
    4. benchmarker-v2 を配置し、同様のオプションで実行(第1日参加チームのみ)
    - ここでのスコアは「総合トップ13枠」「学生枠」の選出に利用
    5. この時点での /report の結果を保存
    6. EC2 インスタンスを再起動
    7. 起動後、再度 /report を実行
    - 5 と比較し、結果が異なっていたら失格(データの順番が変わっているのは可)
    8. ブラウザで目視確認
    - ブラウザから「isucon1」ユーザでログインし、 /mypage の結果が正しく出力されているかを確認。参考実装の挙動と異なっていたら失格

    失格チーム

    AMI 審査の結果、提出時の暫定スコアが上位に入っていたにも関わらず、レギュレーションを満たさず、失格となってしまったチームについて説明します。

    ・「SYM」チームは benchmarker 実行時に、「init script timed out」エラーになっていたため、負荷走行が実行できず、失格といたしました。

    ・「vg12」「もんご博士(RX有〼)」「KURA」「rapid」「team_karakani」「TKS」「チームhogehoge」の7チームは、サーバ再起動後に、再起動前と /report の出力内容が変わってしまっていたり、 /report 自体が動作しなかったりすることが確認され、失格といたしました。

    ・「5518」チームと「LSD」チームは、 AMI が指定された運営の AWS アカウントに共有されていなかったため、失格といたしました。

    ・「京都スイーツ」チームは、 /mypage にログインユーザ名が表示されていないため、表示崩れとみなし、失格といたしました。

    ・「RUSH!!」チームは、提出された AMI から EC2 インスタンスを起動しようとすると、 Kernel Panic が発生して起動できなかったため、失格といたしました。



    本選は11月8日(土)に LINE株式会社の渋谷ヒカリエオフィスにて行います。本選参加は当日渋谷ヒカリエにお越しいただける方のみとし、オンラインでの参加は不可とします。また、予選と本選でチームメンバーの交代は出来ませんのでご注意ください。

    本選出場チームの代表の方へは明日以降あらためてご連絡いたしますので、お待ちください。オンライン予選にご参加いただいた皆さん、まことにありがとうございました。まだ未定ではありますが、次回のご参加をお待ちしております。

    ご参加いただいた皆さんの感想などはこちらにまとめています。
    ISUCON4 オンライン予選 Tweet まとめ#isucon - Togetterまとめ
    ISUCON4 オンライン予選 関連エントリまとめ : ISUCON公式Blog
    Read more...

    ↑このページのトップヘ