ISUCON6予選をwebサービス初心者が通過しました #isucon

ISUCON6の予選を通過しました。

私はwebサービス初心者だったのですが、初心者の視点から、チームで何を考え行ったかをメモしておきます。

ISUCONとは

いい感じスピードアップコンテスト。 webサービスが与えられるので頑張って高速化します。 詳しくは公式サイトを読んでください。

isucon.net

今回のお題は、はてなスターはてなキーワード的機能が付いたWikiサイト。

チーム

チームメイトのブログはこちら。

utgwkk.hateblo.jp

www.wass80.xyz

参加動機

本選参加者の名札がかっこよく、欲しかったので。

やったこと

  • プロファイル計測
  • nginxで静的ファイルをキャッシュ
  • SQLで呼び出すcolumnを必要最小限に
  • 不要なHTTP通信の除去
  • 正規表現による置換の回数を減らす
  • 正規表現に渡す引数を減らす

ソースコードはこちら。

github.com

結果

最終スコア: 19610

学生枠8位!

isucon.net

反省

  • slackで情報伝達したのはよかった
  • GitHubのプライベートリポジトリでソースを見られるようにしたのもよかった
    • commit方針は気が向いたときにスナップショットというゆるふわ運用だった
  • ホワイトボードやプロジェクタのある環境は便利
  • スキル向上、環境構築をして個々が同時並行で別の作業ができるようにしたい
  • キャッシュを使えるようにしたい
  • 便利スクリプトとか用意しておくとよさそう
  • その場で使い方を調べる事態が多発したので事前に練習しておきたい

感想

  • 前日までの練習はazureにvmを立てるくらいしかしていなかった。 でもやっておいてよかった。 ボタンを押してsshキーを登録するだけでデプロイできるのは面白かった。
  • 最初はよくわからなかったけれど ソースとチームメイトを眺めているうちに世界観が分かってきた。
  • 途中から競技プログラミングを解いている気持ちになった。
  • 0点だった間はつらい気持ちだったが、正の点数が取れると楽しくなってきた。
  • チームメイトの2人には感謝しかない。
  • 本選では正の点数をとれるように頑張りたい。
  • はてなキーワード aho corasick 検索
  • 松屋お持ち帰りはコスパがよい。

当日の様子

  • azureにvmをデプロイ。sshkeyの準備に手間取る。 何故か私のアカウントからリソースグループが確認できないが、どうせsshするので気にしないことにした。

  • メンバーが慣れていることから言語はrubyを選択。とりあえず初期実装でベンチマークを走らせるもPASS 0点。 動いてはいるが GET / などがタイムアウトになり減点されまくっているようだ。 なんとなくperlで動かしてみたら3000点くらい取れていた。最悪これを提出しよう

  • rack-lineprof でプロファイルをとることにした。 クリティカルに重い箇所を改善しようというISUCONの基本を再確認した。

  • このあたりでなぜかベンチマークがFAILで落ちる現象が発生。 結構悩む。 どうやらプロファイルを取りながらベンチマークを走らせると処理が追い付かずに例外を吐くらしいことが分かった。 プロファイル取得のon/offを切り替えられるようにした。

  • htmlifyのkeywords周りが重そうということが分かった。 不要な情報まで読み込んでいたSQLを改良した。

    - keywords = db.xquery(%| select * from entry order by character_length(keyword) desc |)
    + keywords = db.xquery(%| select keyword from entry order by character_length(keyword) desc |)
    
  • GET / の代わりに POST /star でタイムアウトするようになったので重い箇所を探す。 keywordが存在するかチェックするところでHTTP通信をしているのを発見。 HTTP通信は重そうだったので直接SQLをチェックするクエリを投げるように変えた。 点数が正(1500位)になってチームの士気が上がりだす。

  • こんどはまた GET / がタイムアウトするようになった。 keywordの正規表現生成を each do の中で回していることが分かった。 htmlify関数の外に出し、1度だけ呼び出すようにした。 ここで3000点位。perl初期実装に追いついた。

  • このあたりで静的ファイルをnginxでキャッシュするように設定した。 スコアへの寄与はあまり実感できなかったが、おそらく効いていると信じる。

  • 点数は上がったものの、未だに GET / がタイムアウトする。 正規表現での置換が重い問題に全てのリソースを割くことにする。

  • keywordをひたすら|で並べる正規表現が重いということが分かっていたので、 keywordを1つずつ正規表現で置換するアルゴリズムを試した。 8000点を取るも、ベンチマークが「ページ hoge の中に fuga へのリンクがありません」みたいなメッセージを出す。 不幸な偶然だろうとベンチマークを取り直すも、点数は安定せずついにはFAILした。

  • アルゴリズムの再検討を始めた。 トライ木の実装や、rubyでの高速な文字列処理ライブラリ導入を試みるも失敗する。 キャッシュに乗せておくことも検討したが、不慣れなためredisの導入で手間取りそうだったので保留。

  • 初期実装をベースに考え直すことに。 オーダー単位での改善方法が思いつかなかったので、定数倍の改善を図る。 これまでの実験により、正規表現に渡すkeywordが多いと重くなることが分かっていたので、 全てのkeywordを正規表現に渡すのをやめ、 content内に出てくるkeywordのみを抽出して正規表現に渡すことにした。 12000点位になった。

  • この時点で残り1時間を切っていたため、これ以上のチューニングをやめて再起動チェックを行った。 プロファイル計測を止め、不要なサービスを落としたうえでベンチマークを走らせた。 19610点をマークし、予選通過に十分な点数と判断したため、下手にいじってミスしたくなかったので、作業を終えた。

  • あとは終了時間までひたすら祈っていた。

まとめ

ひたすら文字列処理とSQLをチューニング(という名前の観察)していました。

名札に入れるアイコンどうしようかな。

本選でお会いする皆様、どうぞよろしくお願いします。