たごもりすメモ

コードとかその他の話とか。

#isucon ベンチでいかにチートするか: その1 - 敵はhttp_load

isucon

チート対策とhttp_loadに仕掛けた罠の話 #isucon - blog.nomadscafe.jp

このエントリに刺激されたので、自分でも事前に大丈夫かなーと思っていたものの最終的には対処しなかったチート穴の攻略を今朝明確に思い付いたので書いてみる。

その2以降を書く予定は今のところありません。

isuconベンチの構造

ベンチマークとチェックツールを含めた全体的な構造については前出のエントリの通りだが、更に加えると、isuconのスコアは http_load によるリクエストの処理数のみによって決まる、という特徴がある。Node.jsで書かれたチェッカなどからもそこそこ(少なくとも秒間3リクエスト)のGETが来るが、最終的なスコアから考えると誤差と言っていい数値。

ということで、チェッカへのレスポンスを確実に返すこととhttp_loadのリクエストに高速に応答することが重要だ。

http_load

で、http_loadというベンチマークツールについて。ツールの機能としては「事前に生成したリストのURLに対して一定時間 or 一定リクエスト数を送る」というのが基本的な構造になっている。今回の isucon でもベンチマーク実行前にURLリストを生成して、それを食わせている。

ここに穴がある。

既に公開されているコードの bench_engine.jsの該当部分 を読むと分かるが、http_loadがアクセスする先のURLは以下の4種類しか無い。このことは当日朝のレギュレーション詳細発表でも言ってある。

  • トップページ - 20%
    • 画像/JS/CSS - トップページと同じ回数
  • 最新の1記事 - 30%
  • その他の記事 - 50%

問題は「その他の記事」だ。通常のアクセスパターンなら記事数が3000あってリクエストが(仮に) 6000 req/min だとすると、その50%つまり 3000req が既存記事に来ることになり、既存の全記事へ1アクセスずつ来ると考えるのが自然だ。
が、そうではなく、実際にはURLリストにどういった形でURLが記載されているかによる。URLがリストにある記事は http_load によりアクセスされるが、そこに載らなかった記事にはほとんどアクセスがこないし、来てもチェッカによるものであって、どれだけ高速に捌こうとスコアにはならないのだ。

で、このURLリスト、いったいどのくらいのサイズまで許容するのか、実はよく知らない。いまソースコードを追ってみたが明確な上限というものは設定されていないようだ。単純にメモリが許容する限りは設定できるというものかも。URLリストへのアクセスが直線的*1だからメモリ空間に対するランダムアクセスも抑えられるし、速度の低下もないかもしれない。誰かに試してみてほしい。

今回のURLリストは100行で生成している。たった100行だ。1行をアクセス数の1%になぞらえているため「その他の記事」に50行使っている。ということは、つまり、なんと、実はベンチマーク時のスコアについては52のURLにしかアクセスが行っていないのだ！

またURLリストの生成において、今回のベンチマークは実は若干の問題を抱えている。本当はURLリスト生成時には順序をランダムにする必要があった気がする*2が、これでは20回のトップページについて、全部並べて出力している。トップページへのアクセスがキャッシュミスになるようなケースだと複数回同時にミスになる可能性が極めて高い。こうなると現実のケースに較べてキャッシュミス時のペナルティが大きすぎるだろう。

で、どうチートするか

答は簡単。コメントの投稿があったら、52のURLについてページ全体のキャッシュを作り直して memcached なりに突っ込んでやればいい。リバースプロキシはまず最初に memcached を参照に行き、無ければ(つまりhttp_load以外のアクセスの場合は)APサーバにリクエストを投げて処理させる。
52のURLのページキャッシュ再生成だが、このときサイドバーの内容は同じなので、あとはそれ以外の部分を52回レンダリングすればいい。またトップページと「最新の記事」を真っ先に処理してキャッシュセットするのが効率が良いだろう。リバースプロキシでキャッシュミスするURLについてはキャッシュ再生成もせず、すべてAPサーバに同期的に処理させればいい。どうせベンチ対象じゃないし。

問題は「52のURL(のうちランダムなもの50)」をどうやって取り出すの？ ということだが、これも答は簡単。ベンチマークが開始されたら10秒くらいはいっさいキャッシュせず、アプリケーション側でアクセス数をカウントするだけでいい。http_loadのアクセス対象とそれ以外の区別はアクセス数だけを見ていればすぐわかる。10秒くらいしたらモードを切り替えてある閾値を超えたアクセス回数のURLを「52のURL」としてリストアップし、コメントのPOST時にキャッシュ再生成する対象として処理を開始する。
これで http_load からのアクセスは常にキャッシュヒットする状態になり、純粋にリバースプロキシ + キャッシュの速度だけで勝負が可能となる。リバースプロキシにおけるSSIとかも不要。やったぜ余裕の10万越えだ！*3

で、どうチートを防ぐか

http_load を使う以上、URLリストの存在は絶対だ。なら以下のふたつのどちらかの戦略を取るしかない。

  1. URLリストを超巨大にする
    • 数秒や数十秒では「ランダムなURL」のリストが推測されない程度に巨大なURLリストを作成する
    • しかし 1000req/s を越える戦いにおいてURLリストが推測されないということは数万行もしくは数十万行以上のURLリストということになる
    • 動くのそれ？ 誰か試してｗ
      • (追記) kazeburoさんによると動くらしい！ 頑張ってリスト作ればいいっぽいぞ！
  2. URLリストを一定時間ごとに作り直す
    • たとえば10秒ごとにURLリストを再生成し、http_loadを立ち上げ直す
      • 結果は10秒ごとに出てきたものを呼び出し側でマージしてやる必要がある
    • アクセスパターンに10秒ごとの谷ができてしまうのでベンチマークとしてはあまり良くない

どちらも実現はなかなか難しく、理想的な解放がないものかと考えずにはいられない。

まとめ

http_loadを使用したベンチマークに対抗するためのチート方法について書いた。ツール機能の本質的な部分に根ざしているので回避がなかなか難しい。とはいえ簡単にこのレベルのパフォーマンス計測ができるツールを自分で実装するのも難易度が高い。

次にやる人は大変だなあ！ｗ
(追記) 巨大リスト作成頑張れ！

*1:http_loadはURLリストから順番にひとつずつ読み込みアクセス先として使用している

*2:今そのように思い付いた

*3:試してないけど多分。