ISUCON5予選でスコア34000を出す方法

今回のISUCONについて

Gunosyの@y_matsuwitterです。
今回のISUCONは去年と同様チーム.datとして、

• @y_matsuwitter => プロセスキャッシュ中心の最終兵器作成
• @TakatoshiMaeda => 予選に向けたツールの用意と司令塔、分析
• @kanny => インフラ周り中心にボトルネック改善

と言う構成で、自分一人Go実装に突っ走るような布陣で望みました。

課題はMixiライクなSNSの実装で、割と色々なJOINが走らざるを得ない、短時間で高速化するには厄介な課題でした。

今回の結果としては日曜一位通過でき、一安心というところです。
また、予選中、両日含め最高スコアの34382を出せました。

事前準備

事前に色々と調査とすぐ使える形のサンプルコード書き溜めて置きました。

• Goでのunix domain socketの扱い
• signalの受け取り方
• syncおよびatomicパッケージの使い方
• 効率のいいrouter探し
• Redisライブラリ周り

当日

まず基本ですが、

• runtime.GOMAXPROCS(runtime.NumCPU())
• 各httpハンドラのレスポンスヘッダを正しく設定する

といった、Go関連の高速化処理を実装しています。

その後、開始後すぐにプロセスキャッシュ中心に持っていく方向で開発を開始しました。

その際立てた方針としては、

• goのオブジェクトのそのままプロセスキャッシュ
• プロセスキャッシュの内容のうち本文データなどサイズの大きいものを除いてgobに変換、ファイルに吐き出して食わせる

ちなみにgobというのはGoのオブジェクトをそのままserializeするためのフォーマットで、詳しくは下記を参照してください。

gob https://golang.org/pkg/encoding/gob/

今回の実装では上記方針にもとづいて、まずは各データをIDでコスト最小で引けるようにもつよう改造を入れていきました。概念的には下記のようなものです。

// データを保持するmap
var entries map[int]Entry

// エントリの取得、ただしこれは簡素
func getEntryObj(entryID int) Entry {
	return entries[entryID]
}

// 取得時
entry := getEntryObj(entryID)

上記は簡素すぎますが、sync.RWMutex等使いながら安全に実装していきます。

その後、各ページの表示形式に合わせて、全てのデータを非正規化、条件に合わせて順序を調整したidのsliceやmap、場合によっては専用の構造体を用意してsliceにもつなど、アプリケーションの挙動を分析してのインデックス的な構造を保持するようにしました。
結果として、各ページのデータ取得はslice等から必要数IDを取得、その後各IDでオブジェクトをgetするような実装に変更、DBアクセスを無くしています。
ちなみにEntryやCommentの文書データのみ、メモリの都合で効率のいいRedisに配置しています。（Goでも効率よく載せることはできますが時間の都合でやっていない）

また、初期データは上記の形式に合わせてオブジェクトを生成、gobに吐き出し、/initializeでプロセスキャッシュを洗い替えするような仕組みになっておりまして、大体12秒位で終わるような感じでした。
プロセス停止時はsignalを受け取った段階で各データをgobに吐き出し、初期データと別な場所にdumpしています。
このdumpデータは次回起動時に使うようになっており、データが復旧が完了します。

上記を淡々と実装した結果、スコアは17時頃に34000を超えました。

その他GOGCを弄ったりなどしましたが、こちらはメモリがそもそもカツカツなので実際には使っていません。
最終ベンチでは並列度と同期処理周りに不安が残り、大事を取ってruntime.GOMAXPROCSを1に設定し提出しました。そのためスコアがだいぶmoderateな感じになりましたが、ひとまずそれでも二日目1位通過ですので一安心。

苦労したこと

実は初期データのgobを吐いたファイル生成に一番時間を取られています。
非正規化の程度が激しいため、mysqlからのdumpしたtsvデータをgobに変換するのに一回あたり数分~もっと酷いものだと20分ほどかかったため、それが正しい結果を吐くまでに2時間ほど使ってしまいました。
Goで下記のようなsliceの先頭にひたすらオブジェクトを追加する処理を書く際は、不必要に長いsliceにならないよう注意しましょう。負荷が非常に高い処理になります。

hoge := []int{}
for _, comment := range comments {
	hoge = append([]int{comment.ID}, hoge...)
}

もっとやれたこと

後やれるとしたら、

• templateを文字列結合に持っていく
• 長文系のデータを圧縮してRedisからGoに持てるようにする
• gorilla/mux => httprouterなどパフォーマンス高いものに変更

など考えていましたが、template以外はそれほど意味ないかなとも思います。

最後に

運営の皆さん予選お疲れ様でした！個人的にはベンチマーカーのパフォーマンスの方に驚きました。
本戦でも宜しくお願い致します。