math314のブログ

主に競技プログラミング,CTFの結果を載せます

ISUCON5 オンライン予選 通過しました

優勝賞金100万円!今年もやります ISUCON5 開催と日程のお知らせ #isucon : ISUCON公式Blog

「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。」(公式説明)であるISUCON5のオンライン予選に参加してきました。

...

ISUCONは Iikanjini Speed Up Contest の略で、Webアプリケーションがデプロイされたイメージを渡されて、その上で何をしてもいいからとにかくパフォーマンスを上げることが競技内容です。

ISUCON5オンライン予選に参加してきた « chibiegg日誌

ということで参加してきました。

チーム マウント竹田氏(メンバー: @misodengaku, @chibiegg, @__math) で出ていました. 16位で予選通過です。 いつもは @aki33524 も参加するんですが、上限が3人までということだったので、裏番組のTrend Micro CTFを頑張ってもらいました…、きひろくんごめん。

他のメンバーの参加記です

初参加でしたが決勝に進出出来てよかったです。

前日準備

メンバーが自分以外東京なので、バスで東京へ移動した。 更に、ノートPCが死亡しているためさくらのクラウドwindowsサーバを借りて、 misodengaku から借りたPCからRemoteDesktopして作業することに。

ISUCONが何をするか分からないのでISUCON4でお勉強。 ISUCON4はサーバのチューニングを頑張ると通過できたらしい。ISUCON5もそうなるのだろうか?

クラウドよくわからないって言ってたらchibieggとmisodengakuが全部準備してくれたので、 インフラは二人に任せて、自分はアプリケーションの重い処理を潰す係に。

ISUCON4の練習を終えて、戦略と役割分担を決定した。

戦略

  • ISUCON4の練習で溜まった設定ファイルをそのままISUCON5に持って行って、楽をする
  • 最初はpythonで動かして、重いSQLや遅い処理を高速化。余裕があれば、misodengakuにその変更をgoに移植してもらう。
    • 全員使える言語がpythonである
    • 予選突破はpythonでも可能だと思う
    • 余裕があれば、高速に動作するgoで動かしたい
  • 予選突破だけならRedis、Memchachedは不要、余裕が出来れば触る

役割

  • chibiegg : インフラ整備
  • misodengaku : goでのチューニング
  • __math : pythonでのチューニング

本番

ISUxiというアプリケーションの高速化。 機能は主に

  • ログイン
  • あしあと
  • 日記
  • コメント

の4つ。昨年と比べて重たく、プログラムに結構手をいれる必要がありそう

goの実装が不完全!?マジ!? となるものの、一応misodengakuにgoのコードを読んでもらう。 chibieggが設定を弄ってる間にpythonのソースを読む。SQLがやたら多い。

とりあえずベンチ投げたら3桁。 スコア計算式は [2xx] * 1 + [3xx] * 0.1 - <ペナルティ> とのこと。計測時間は多分60s。 ……リダイレクト300,000回したらそれだけで3万点超えない?と思ったものの、後で怒られたくないので最終的にはやめた。 実際それだけリダイレクトさせる事は可能なのだろうか?

アプリケーション側でやったことを順番に書いていく。得点を保存するのを忘れていたため、どの改善がどれだけ効いたのかわからなくなってしまった。

序盤

  • ログイン画面をキャッシュするため、ログイン画面で表示するメッセージ毎にurlを分ける
    • 今回はログイン試行回数が少なかったため効果薄
  • sessionにuser.idのみ保存して参照する度にSQL吐いていたので、sessionにuserを入れる
  • relationsのINSERTクエリは問題ないが、SELECTで無駄な条件がついていたため消す
    • one < another にすればINSERTするデータ数が半分になり軽いのでは?という話をしていたが、これはSELECTが遅いので却下した
  • ISUCON4ではjsでCSSの遅延ロードが有効だったので試したが、ISUCON5ではテストが通らなかった
    • ISUCON4予選の公式解法でもそうなっていたから今年も出来ると思った
    • misodengakuがgzipで固めて試していたがそれもだめだったみたい
  • userが5000件しかなく、SELECTしかされないので、オンメモリに保存する

中盤

  • htmlのtemplateにSQLが直書きされているとmisodengakuが教えてくれる
    • !?
    • templateを全部漁って、片っ端からSQLを消していく
  • mysqldumpslowで確認してると、'/'のページがやたら重たいクエリを連発していることが確認出来た
  • N+1問題が2箇所という地獄を発見した。SELECT * ...... LIMIT 1000 した後 n個クエリを吐いてる
    • どっちも、有効な物を10件しか表示していないので、LIMIT 10に出来るクエリを作成
  • entriesから引いてるのはすぐ LIMIT 10で引けるようになったが、commentsから引いてるクエリが応答を返さなくなる
  • entries.privateにindexを張れれば良さそうだったのでCREATE INDEXしたが終わる気配がない
  • しかたないので、privateになっているentryの割合を計算すべく SELECT COUNT(private) from entries するがこれも終わらない
  • entries.privateの問題は後回しにする
  • footprintが遅いので、 テーブル構造を変えて INSERT INTO ...... ON DUPLICATE KEY UPDATE が出来る形に変更する (chibiegg)

この時点でscoreが3000を超えておらずお通夜

終盤

  • template内のSQL全部消して、高速に出来るようにしてくれた (misodengaku, chibiegg)
  • SELECT * FROM comments ... LIMIT 1000 の1000は削れないけど、is_friendの判定はSQLに組み込める、ということで組み込んだ

    • score = 6939 に急激に上昇`
  • 後回しにしていたLIMIT 1000にとりかかり、 SELECT private from entries LIMIT 1000 くらいを目視で確認する

  • privateなentryは10%程度、ランダムに割り当てられている様子
    • 恣意的なケースが入ってたと仮定すると、用意されていたpythonのコードがベンチマークのテストを通るわけがない…
  • privateなentryが10%と仮定し、LIMIT 1000 をどこまで減らしてもよいか式を立てて計算した結果、30件もあれば十分ということがわかる

'/'へのリクエスト回数を request, LIMIT nとし、立式する。具体的には \[ 1 - (\sum_{k = 10}^{n} binomial(n,k) \frac{9}{10}^{k} \frac{1}{10}^{n-k})^{request} \] が、ベンチマークを失敗すると思われる確率

  • request = 104 ,n = 30の時、これは10^-10 以下となるので、これが失敗するとは考えにくい、ということで、LIMITの上限を下げた

    • n = 100 にしただけでベンチマークの結果がうなぎのぼり
    • n = 50 にした結果、score = 16000 まで出ていた
  • 色々やっていたが残り30分を切ったので、再起動テストに切り替える

  • MySQLが温まっておらずinitilizeでこけたり、タマキが出現してfailedして困惑
  • その後数回投げた結果、score = 14795まで回復したので、これでfinish

感想

中盤まで全くスコアが出ずにお通夜モードだったが、'/'のSQLを軽くした途端スコアが伸びてチーム内で沸いた。

ISUCON1 ~ 4 まで python で通過したチームがいなかったらしく、python初通過チームになれたのでは?と思います、うれしい。 本戦優勝はpythonでは難しいと考えているので、goに慣れたほうがよさそう。