チューリング不完全

What are you afraid of? All you have to do is try.

ISUCON6予選 TOPで敗退するまでの道のり


supermomonga(@supermomonga), aomoriringo(@aomoriringo), purintai(@specepro_be)の3人でISUCON6に出場しました。
チーム名はSMAP(SuperMomongaAomoriringoPurntai)です。

ISUCON4には出場したことがあり、2年ぶりの出場となりました。

チーム構成

aomoriringoは3人の中では一番SQLを書いたことがあるっぽかったので、MySQLまわりを主に担当することにしました。
Rubyはほとんど書いたことがないのですが、コードを読んでここはN+1問題が発生してる、というのは普通にわかります。appコードを読みつつのSQL改善や、MySQLの解析ツール、パラメータチューニングなどをもろもろやりました。あとは強いて言えばRubyに閉じた中でのアルゴリズムの改善とか。

purintai は主にRuby app部分を担当。参照頻度の高いデータのRedisへの載せ替えや、Sikekiqによる非同期処理などをサクサクやってくれた。

supermomonga もメインはRuby app部分の担当ですが、3人の中で一番幅広い分野を触ってくれました。Redisの構築と設定、Ruby周りの解析ツール設定、書き捨ての便利スクリプトの作成、unicornの設定・・・などほんとにいろいろ。

チーム登録から本番まで

8/31 (3週間前)

supermomonga, purintai 両氏に「isuconどうですか」と誘ってもらい参加することに。
その日のうちに以下のことをやりました。

slackには本番までに必要そうなことや、参考になりそうな記事を各位投稿してやりとりをしていました。
前日から、とかではなく、3週間というある程度の時間の中で「ここはこういう風がいいのではないか」「環境はこうしたい」など各位の意見が見えることによって、ゆっくりと全員の意識共有が醸成できたのは大きかったなと思います。

9/1～9/8

  • 各自の得意分野について共有
  • 使用する言語の決定
    • supermomonga, purintai のメイン言語がRubyだったのでRubyにした
  • ISUCONの参加記事をslackに投稿し、とるべき方針や参考になりそうな部分についてやりとり
  • crowiの作成
    • 以降、調べたことをmarkdown形式でwikiとして保存できるようになった

9/8

  • aomoriringo がISUCONもくもく会@Wantedlyに参加
    • appの編集環境やデプロイツール周りなどの環境について考慮しておいた方がよい、ということを聞く
    • 使用されるIaaSについて
      • 今回はISUCONとしては初のAzure。インスタンスの作成や再起動試験などの概要について共有
    • 「最初の1時間で何をするか決めておく」という概念を学ぶ

9/9～9/10

  • supermomonga 邸に aomoriringo が訪問して練習会
    • matsuu氏によるISUCON5予選問題Azure版を構築
    • slackに#benchmark部屋を作成し、ベンチマーカーの実行結果を slackcat を使って実行完了時に結果が投稿されるようにした
    • 速くするためのappの変更よりも、実際の環境を触りながら使えそうな構築ツールのインストールや使用方法、便利そうなshellコマンドなどをwikiにまとめることを重点的に行う
    • redisの試用、各種解析ツールの試用

この時点ではMySQLのキャッシュについて深く把握しておらず、「再起動するとスコアが半分ぐらいになる・・・実行するごとにスコア上がる・・・なんで・・・？」とか言ってました。(クエリキャッシュの影響)

9/11～9/15

  • gitのrepository構成の決定
    • app repositoryとconf repositoryの2つを作成することにする
      • app repository (対象となるwebappディレクトリ以下を管理)
      • conf repository (/etc以下のmysql, nginx, redis等設定ファイルを管理)
  • 練習会の経験を得て、当日の進め方について話し合い
    • いきなりMySQLに初期状態のappで呼んでいるSQLを最適化するようなindexを貼ってしまうと、N+1解消するような変更をしたときにスコアとして改善が見えにくい。まずはappで見て明らかに無駄なところを直す

slackで書いてたことの例
f:id:aomori-ringo2:20160919003816p:plain

  • mysqlについて調べる
    • パラメータチューニング
    • B-Treeアルゴリズムについて
    • EXPLAINの読み方
    • 既存テーブルへのカラム追加手順

9/16-9/17

金曜日に有給を取得して supermomonga 邸に3人集合。(結果的に金曜日から月曜日にかけて3泊しました)

金曜日は既にたててあるISUCON5予選問題, 土曜日はpixiv社内ISUCON問題に取り組みました。

9/9,10に練習会をしたときと同じく、ツールの使用方法やテンプレになる処理をwikiにまとめながらの作業となるので、あまり厳密に時間の測定は行いませんでした。

過去問に取り組むときの方針

ISUCON4に出場したときは予選本番の前の週にチーム3人で集まり、本番と同じように時間を測ってISUCON3の問題に取り組んだのですが、これは失敗だったなあという思いがずっとありました。この時はメンバー全員がISUCON初参加だったし、事前に十分な予習やツール検討をできていたわけではありません。
本番と同様に10時～18時で行うとそのあとに何が良くなかったかを検討することもあまりできず、結局惨敗してしまいました。

その経験を踏まえて、今回は過去のISUCON予選通過組のブログを読み、有効な手段を試し、それぞれについて都度メンバーと共有をする、ということをたくさんやることにしました。
幸い今回は練習時間を多く確保することができたので、後半はwikiに書き留める作業が収束し、より対象のアプリや環境に集中して、高速化を検討することができるようになりました。

最終的にはISUCON5予選問題は5万点, pixiv社内isucon問題は19万点ぐらいになりました。

「最初の1時間にやることリスト」の作成

crowiはknowledge baseとしてはとてもよかったのですが、チーム全員が同時に編集するには使いづらい。
そこで、複数人で同時に1テキストを編集することができるhackmdを使ってやることリストを用意しました。

f:id:aomori-ringo2:20160919212426p:plain

やることリストテンプレ
現時点で何が完了しているのか、何がまだできていないのかをすぐに確認することができ、各自がここを見ながら「じゃあ次はこれやります」「よろしく」みたいなやりとりをしてました。

9/18

予選当日です。
8時ごろに起床し、食べ物・飲み物を買い揃え、机の配置などの準備をしました。


メモ用紙と筆記具もあると良いです。

本番の取り組み

やったことを全部記録しているわけではないので、効果があった取り組みをいくつか書いてみます。

Isutar部分の消去

今回はIsuda, Isutar, Isupamという3つのサービスが連携している、いわゆるMicroservice的な作りでした。
Isupam部分はバイナリであり、かつボトルネックとしては最後まで問題にならなかったので正直忘れ去ってました。
IsudaとIsutarはMySQL側にそれぞれデータベースを持っていたのですが、Isudaは2テーブル, Isutarは1テーブルしかない小さなデータベースです。また、レコード件数もそんなに多くない。
そこで、Isutar部分の処理はIsuda側に移し、データはRedisに全部載せるようにしました。
この辺はMySQLの状態を確認できるように準備していたmyphpadminが地味に貢献していて、各テーブルの構成やデータ量把握を各自がすぐ行えるのがよかったかなと思います。

Etagの活用

今回の問題は「はてなキーワード」的なサービス内容でした。
キーワードとその説明を1記事(entry)として投稿することができ、閲覧すると説明文の中に、サービスに保存されているキーワードと同じ文字列があれば自動でリンクタグを挟むというものでした。
参考実装では、記事の閲覧(GET)が呼ばれるたびに説明文の文字列に対してリンクタグを入れていくという処理があります。お約束の対策としては事前にリンクタグが挿入済みのHTMLをあらかじめ生成しておき、キャッシュしてGETが呼ばれたときに即座に返すというものですが、問題はキーワードのPOSTが全記事に影響を及ぼす可能性があるということです。
あるキーワードがPOSTされると、そのキーワードを説明文に含む全ての記事は影響を受けます。キーワードの中でも特に短いもの、例えば「9年」などはテストデータ中の4割近くに含まれており、POST時に全てのHTMLを再生成するというのは現実的ではありません。
そこで、記事(entry)テーブルに「modified_at」カラムを追加し、キーワードの追加/削除時に以下のようなSQLを発行するようにしました。

UPDATE entry
SET modified_at = '#{now}'
WHERE description LIKE '%#{keyword}%';

HTTPにはEtagというレスポンスヘッダがあります。サーバがレスポンスを送信する時にEtagフィールドをセットすると、クライアントは次回同じURLにリクエストする際に先ほど送信されたEtagをIf-None-Matchヘッダに入れてHTTPリクエストを送信します。
このEtagに先ほどの「modified_at」の結果を入れ、GET時にもしDBに保存されている「modified_at」と同じであれば内容が変わっていないとし、「304 Not Modified」レスポンスを返すようにしました。

非同期処理(Sidekiq)による直近投稿部分のキャッシュ生成

トップページ`/`が表示されると、最新の投稿20件が表示され、画面最下部の「もっと見る」をクリックするとさらに次の20件が表示されるという仕様がありました。
解析ツールを見るとこのトップページに対するアクセスがとても多いため、直近数十件のエントリに対して非同期でエントリの生成を回し続けるという処理をSidekiqを使って実装しました。

その他

説明文文字列のHTML化(htmlify)部分には結局、大きく手をいれることができませんでした。
今思えばキーワードすべてを「|」で並べた正規表現が遅いことや、差し替えをするときの方針などもっといろいろ考えられたはずなので、大変悔やまれる部分です・・・

結果

今回の最終結果を見ると、予選通過のボーダーラインは90214点です。
我々のチームは一時的に11万点を超えるスコアを出すことができたのですが、ベンチマーカーやキャッシュの問題か計測によってかなり揺れがあり、最後のスコアが89923点となってしまいました。
予選落ち組の中ではほぼトップのスコアかと思います。とても悔しい・・・

反省

「Rubyは読めるけど書けない」、個人的な一番の課題はここです。
特にアルゴリズム部分を考える際、「Pythonなら書けるけどRubyだと・・・？」みたいなことをいちいちググったり人に聞いたりしていては話になりません。来年までにProject Eulerなどで訓練したいと思いました。
それから今回の問題ではデータベースのテーブル構成がとてもシンプルで、事前に調べていたSQLの知識がほとんど使えませんでした。JOINが1つもなかった気がします。
理解が完全であったかどうかはかなり怪しいところがありますし、次回の設問では揺り返しとしてテーブル構成が複雑な問題となるのではないかという感じがするので、SQL部分の知識も蓄えたいところです。

逆にチームとしては3週間前からのslackのやりとりと数日の泊まり込み合宿の成果がいかんなく発揮され、かなりスムーズに動けていたと思います。ここはぜひ次回にも活かしたいです。




おわりに

かなり真面目に取り組んだので、1000点差で本選に出られないのは忸怩たる思いがあります。
楽しかったけど、悔しかった。
悔しかったけど、楽しかった。
ISUCON7で会いましょう。