ISUCON13に参加しました

こんいす〜。ISUCON13に参加したので、参考になるかはわかりませんが当日考えたことややったことについて書いていきたいと思います。

今回の問題

今回の問題はライブ配信サービス「ISUPipe」の高速化でした。
スコア計算が「投げ銭機能により送金・寄付された金額の合計」と非常にシンプルでわかりやすかったのが面白かったです。
www.youtube.com

当日の戦略

マニュアルを見て今回の問題はアイコン画像の配信とDNSサーバーが最初の大きな課題になると思いました。DNSサーバーについては残念ながら詳しくなかったので、早速色々と調べてみたところ、今回の問題の出題企業であるさくらインターネット株式会社様の発表記事を見つけることができました。
knowledge.sakura.ad.jp
この発表は今年の1月に行われた比較的新しいものであることや、今回の問題で使用されているPowerDNSに対するDNS水責め攻撃への対策について述べられていることから、これが問題の元ネタなんじゃないかと考えました。この記事から「dnsdistというDNS用のプロキシサーバーがあるらしい」ということ、そして「PowerDNSのバックエンドとしてMySQLのようなRDBMSを使用するのは水責め攻撃時のパフォーマンス影響が大きいため、KVSやBIND形式を採用する方が良いらしい」ということがわかりました。今回の問題の初期実装ではPowerDNSのバックエンドがMySQLだったので、これを移行することが重要課題であると認識できました。
ここまでのことを踏まえて、当日はまずアイコン画像配信担当 / DNS担当 / アプリケーションのN+1を潰す担当で別れて作業を進めることにしました。自分はN+1を潰す人だったので、どんなことをやったのか次で書いていこうと思います。

やったこと

以降の内容はGo言語での実装について話しています。

ライブ配信の検索を改善する1

ライブ配信の検索処理を行うsearchLivestreamsHandlerではタグによる検索を行った場合、まずそのタグが付けられたライブ配信のID一覧をDBから取得し、各IDに対して1つずつライブ配信の情報をDBから取得するという典型的なN+1が発生しています。これを解決するにはSQLのIN句を用いて、全てのIDに対するライブ配信の情報を一度に取得すれば良さそうです。
しかし、今回のケースでは1つだけ落とし穴があります。というのもここでは、ライブ配信のIDの降順に結果を返すことを期待されているということです。IN句による単純な取得では、IN句に指定したIDの順番を考慮してくれません。そのため、このままではレスポンスが不正であると怒られてしまいます。
これを解決する方法はいくつかあってSQLで解決する方法もあるらしいのですが、今回は素直にアプリケーション側でソートをすることにしました。Go言語であればsort.Sliceを使うことでIDの降順ソートを実現できます。
またアプリケーション側でソートすることによって、livestream_tagsテーブルからライブ配信IDの一覧を取ってくる際にソートをする必要がなくなるので、ORDER BY livestream_id DESCを消すことができるというメリットもあります。これにより、テーブルにINDEXを張る時に複合インデックスにしなくても良くなったりします。

ライブ配信の検索を改善する2

searchLivestreamsHandlerにはもう1つN+1が仕込まれており、それはDBから取得したライブ配信データ（LivestreamModel型）を実際に返すレスポンスデータ（Livestream型）として整形する部分で発生します。このLivestreamModel型からLivestream型への変換はfillLivestreamResponseという関数を用いて行われていますが、この関数が単一のLivestreamModel型のデータを変換することにしか対応していないため、複数のLivestreamModel型のデータを変換したい場合には必然的にN+1が発生してしまいます。
実はこのような問題はアプリケーションの至るところで発生しており、XxxModel型をXxx型に変換するfillXxxResponse関数を、同時に複数のデータを変換できるように対応させた関数に置き換えることができるかというのが最初の大きな課題のようでした。
ひとまずfillLivestreamResponseの実装を見てみると、レスポンスに詰め込む情報を取得するために様々なクエリが発行されており、ループの中で呼び出すのはまずそうだということがわかりました。しかもこのfillLivestreamResponseの中の処理でも、ライブ配信に付けられたタグのデータをレスポンスデータにする部分でN+1が仕込まれていました。とりあえずこの部分はすぐに直すことにしましたが、fillLivestreamResponse自体の複数対応は面倒そうだったので、一旦見送ることにしました。

ライブコメントの取得を改善する

計測の結果、次にライブコメントの取得が重そうだったので実装を見てみたのですが、なんとパッと見で重そうな処理がfillLivecommentResponseの複数回呼び出しによるN+1しかなかったので、覚悟を決めて向き合うことにしました。
fillLivecommentResponseを複数データ変換に対応させるためには、まずfillUserResponseとfillLivestreamResponseを複数データ変換に対応させる必要があります。fillUserResponseの複数データ変換対応が一番簡単で、この実装ができれば後のやつらは基本的にこれを真似て複数データ変換対応させていけば良かったです。
基本的にはSQLのIN句を用いたデータの一括取得を行えばいいのですが、例えばユーザーを例にするとアイコン画像を一括取得しただけの状態では、あるユーザーに紐づいたアイコン画像の情報が取得した配列のどこに存在するかわからないので、すぐに取り出すことができません。そこでユーザーのIDをKeyとし、アイコン画像のデータをValueとするような連想配列を用意する前処理を行うことで、後でデータを取り出しやすくなります。
fillLivestreamResponseの方は、この連想配列を用意する前処理を行う部分が若干面倒くさかったので、TODOコメントだけ置いて後でまとめてfillLivestreamResponseをループ内で呼び出している箇所を置き換えることにしました。

リアクションの取得を改善する

リアクションの取得も重そうだったので実装を見ましたが、こちらもライブコメントの取得と同じくfillReactionResponseの複数回呼び出しによるN+1が原因のようでした。fillReactionResponseの実装もfillLivecommentResponseとほぼ同じなので、さっきやったことをやるだけです。

fillLivestreamResponseをなんとかする

ここまで来てようやくfillLivestreamResponseの複数データ変換対応をすることにしました。といっても、これまでやってきたことと同様のことをやるだけなので、特筆するべきことはないです。fillLivestreamResponseをループ内で呼び出している場所は結構あったので、この改修はかなり効果があったと思われます。
ここまでやると、スコアの方もそこそこ伸びてきました。

ライブコメント投稿時のスパム判定を改善する

ライブコメントが投稿されたとき、postLivecommentHandlerでは投稿されたライブコメントがNGワードを含んでいないか判定しているのですが、初期実装ではこの判定をSQLでなんとかしようとしているため効率が悪いです。NGワードを含んでいるかの判定はアプリケーション側で簡単に行うことができ、例えばGo言語ならstrings.Containsを使うことで容易に判定することが可能です。
NGワードを何回含んでいるかをカウントするhitSpam変数もログの出力に使われているくらいで、実際にはNGワードが1つ以上含まれているかどうかだけを知ることができればいいので、strings.Containsで十分というわけです。

ユーザーの統計情報を改善する

getUserStatisticsHandlerではユーザーがこれまでに行なった配信で獲得した累計のライブコメント数や売上金額などの統計情報を計算し、レスポンスとして返しています。しかしこれらの統計情報の計算を、ページにアクセスがあるたびに1から全て頑張って計算しているため、大量のDBアクセスが発生し非常に重たい処理となっていました。
このような場合の解決策としては、各種統計情報を格納するカラムをusersテーブルなどに用意し、統計情報が欲しいときはカラムの値を取り出すだけで済むようにしてしまうことです。例えばユーザーの累計のライブコメント数ならば、usersテーブルにtotal_commentsというカラムをデフォルト値0で用意します。このカラムの更新はそのユーザーの配信に対してコメントが増えたとき（livecommentsテーブルにINSERTが走ったとき）と、新たなNGワード登録などによってコメントが削除されたとき（livecommentsテーブルにDELETEが走ったとき）に発生します。
このような更新処理は、アプリケーション側でINSERTやDELETEのSQLが発行される場所で、このカラムの値をUPDATEする処理を記述する方法も考えられますが、初期データ投入時のデータ不整合を防ぐための対応も必要となるので面倒です。なので自分はトリガーの機能を用いてINSERTやDELETEを検知して更新を走らせるようにしましたが、結構雑にトリガーを書きまくったのでこれが正解なのかはあまり自信がないです。もっといいやり方があったら知りたい。
このように統計情報をカラムに載せるようにしていくと、ユーザーのランキング計算も2つのカラムの値の和を計算するだけで済むので非常に効率的になりました。

一方その頃

さて、ここまでアプリケーションのN+1撲滅活動について述べてきましたが、アイコン画像配信とDNSの方は非常に難航していました。
アイコン画像配信の方では実装がほぼ完了したものの、原因のわからないエラーに苦しめられていました。後で詳しく話を聞いてみると、アイコン画像の更新が入る前にアイコンの取得処理が走ると、返すべきハッシュがなく死ぬらしいということだったのですが、実際にはアイコン画像が設定されていないユーザーはデフォルトの画像としてNoImage.jpgが返されているので、これに対応するハッシュを返せば済む話でした。初期アイコンの存在についてはN+1の改善を行なっている中で自分は認識していたので、もっと早い段階で問題の内容について詳しく聞くことができていれば良かったと反省しています。
DNSの方はdnsdistを挟む作業を無事に終えた後、上述した記事を元にBIND形式への移行を目指して取り組み始めたのですが、静的なファイルで設定を行うBIND形式では今回のようにサブドメインが動的に増えていくようなサービスの要件には合わない、という事実に気付くまでにかなりの時間を要してしまいました。このことに気付いてからはKVS型のバックエンドへの移行を目指しましたが、これはすぐに移行を完了させることができたので、BIND形式で悩ませてしまった時間が非常にもったいなかったです。結果的に名前解決の成功件数を爆増させることに成功したものの、dnsdistを用いて水責め攻撃への根本的な対策をする時間がなく、大きなスコアの伸びに繋げられなかったので悔しいです。
競技終了直前まではサーバー3台構成への移行作業を進めていたのですがこれもうまくいかず、1台構成のまま最終提出を行おうとしたのですが、移行作業中にGitHubの管理下に置いていなかったenv.shを編集していたことを忘れていたためFAILし、最終結果は0点となりました。皆さんもGitHubの管理下にないファイルを触るのはやめましょう。

感想

全体としては非常に悔しい結果となってしまいました。初手での考察や分担などの動きは悪くなかったのではないかと思うのですが、その後の実装部分での連携不足によって本質的な問題の解決を終わらせられず、貴重な人的資源も大きく消費してしまったのがやはり大きいでしょう。ここを乗り越えていれば上位のスコアも狙えたと思うだけに、本当に悔しいです。次の機会があればリベンジしたいと思います。
まだまだやりたかったこともたくさんあるので、とりあえず感想戦ができるようになったらバリバリやっていきたいです。