ISUCON5 予選 part4 #Go

研究室有志によるISUCON勉強会 ISUCON部の資料です。

今回は、
http://isucon.net/archives/45627361.html
を参考にアプリケーション側のボトルネックを解消していく。
解説と講評にあるとおり、 / ページだけでも多くの問題があるので、 / に着目してボトルネックを解消していくことにする。

score遷移

（score は測るたびにばらつきがでるので、何回か測るようにした）

施策	score
修正前	900.4
relationsのN+1問題を修正	1975.4, 2061.8, 2140.8
usersのN+1問題を修正	2621.5, 2234.4, 2498.7
足あと	7850.9, 7008.6, 8681.9
友だちの日記エントリ	10870.9, 10105.3
友だちのコメント	13568.6, 9819.7, 10980.0
日記エントリの本文	12296.8, 8321.2, 10127.3, 12154.6, 11667.6

デプロイスクリプト作成

ログのローテート（旧ログのファイル名にtimestampをくっつける）
app.go のビルド
systemctl restart xxx 系

などを行ってくれるスクリプトを作成した。

コードはこちら

アプリを理解する

mixiを模した作りになっている。
ログインした後、一通り遊んで見る。
記事の投稿、友達関係、足あとなどの概念と mysql の table を頭の中で結びつけておくと、後々楽になる。

relations の N+1 問題

mysqldumpslow 等でクエリを解析してみると（part2 参照）、relations への select の実行時間の割合が一番大きいことがわかる。
また、 app.go の GetIndex 関数の中を読んでいくと、forループの中で isFriend 関数を読んでいる部分があり、更に isFriend の中で上記のクエリを叩いていることがわかる。ここで N+1 問題が発生してしまっている。

修正方針として以下の2つが考えられる。

JOIN 句を使って mysql へのリクエスト回数を減らす
table をキャッシュに載せてそもそも mysql へアクセスしなくする

今回は、IOバウンドかつメモリに余裕がある状態なので、 2 が有効で手っ取り早いと判断。
キャッシュとして今回は go の map を使ってデータを全部載せた。
（redis等を使うてもあるが、今回は map を使うほうが手っ取り早い気がした。）

map を更新する際に mutex で lock をかけるのを忘れないようにする。

diff はこちら

users の N+1 問題

方針は relations と同様。

diff はこちら

足あと

mysqldumpslow の解析結果によると、次に重そうなクエリは footprints 系のクエリのよう。

Count: 4001  Time=0.29s (1145s)  Lock=0.00s (0s)  Rows=10.0 (40010), root[root]@localhost
  SELECT user_id, owner_id, DATE(created_at) AS date, MAX(created_at) AS updated
  FROM footprints
  WHERE user_id = N
  GROUP BY user_id, owner_id, DATE(created_at)
  ORDER BY updated DESC
  LIMIT N

Count: 1188  Time=0.28s (332s)  Lock=0.00s (0s)  Rows=50.0 (59400), root[root]@localhost
  SELECT user_id, owner_id, DATE(created_at) AS date, MAX(created_at) as updated
  FROM footprints
  WHERE user_id = N
  GROUP BY user_id, owner_id, DATE(created_at)
  ORDER BY updated DESC
  LIMIT N

今回のアプリケーションでは同じ日に同じユーザーが付けた足あとは最新のものだけ表示すればいい。なので、dbにもすべての足あとは保存せず、同じ日に同じユーザーが付けた最新の足あとだけを記録するように変更する。こうすることで、 GROUP BY や MAX といった句を使わずに済むようになる。

REPLACE 文を使うと、 (1)試しに INSERT してみて、 (2)UNIQUE制約等により衝突が発生したら該当する行を UPDATE する、ということをしてくれる。 REPLACE 文を使うために、 footprints テーブルに date という列を追加し、 (user_id,owner_id,date) の複合uniqueインデックスを張っておく。

sqlのクエリとdiffはこちら

友だちの日記エントリ

既存のコードは、とりあえず entries を1000件取ってきて、友達の投稿が10件見つかるまでループを回して調べる、というあまりよろしくない実装になっている。

友達のidの配列を WHERE IN 句に与えることで、友達の投稿だけを取得することができる。

SELECT * FROM entries
WHERE user_id IN (:friend_ids)
ORDER BY id DESC LIMIT 10

rails などでは WHERE IN 句の引数として直接配列を与えるような書き方ができますが、go ではそうはいかないらしい。代わりに、 len(friendIds) 個ぶんのプレースホルダ ? を埋め込んだクエリ文字列を生成する。

created_at の index は不要になったので、落としておく。

diffはこちら

友だちのコメント

既存のコードは、友だちの日記エントリ同様で、よろしくない実装になっている。

友達のコメントについては、 isFriend の判断に加え、記事がprivateかどうかの判断もしなければならない。条件をまとめると以下のようになる。

private=0 の場合は、全ユーザから閲覧可能
private=1 の場合は、友達からのみ閲覧可能

この条件は JOIN を使って以下のように sql で表現できる。

SELECT * FROM comments c
JOIN entries e ON c.entry_id = e.id
WHERE c.user_id IN (:friend_ids)
AND (
  e.private = 0
  OR
  e.private = 1 AND (e.user_id = :my_user_id OR e.user_id IN (:friend_ids))
)
ORDER BY c.id DESC LIMIT 10

友だちの日記エントリの部分でも説明したとおり、 WHERE IN の部分に配列を引数として与えるには、 ? を配列の要素数ぶん埋め込んだ文字列を生成するという力技が必要。

この際、 comments.user_id に index が必要となり、 comments.created_at のindexは不要になるので、それぞれ ALTER TABLE で対応しておく。

diffはこちら

日記エントリの本文

entries テーブルには日記のタイトルと本文が \n で連結された1つの文字列として body というカラムに格納されている。また、タイトルだけを取得すればいい場合でも本文も含めて取得しており無駄が多くなっている。

そこで今回は、 title という新しいカラムを作り、タイトルを title に、本文を body に分割して保存するようにした。また、本文を必要としない場合は SELECT 文に body カラムを含めないようにした。

diffはこちら

ちなみに、 mysql の文字列の長さを取得する関数は2種類ある。

LENGTH ... 文字列のバイト長を取得する
CHAR_LENGTH ... 文字列の文字数を取得する

MySQL String Length | Explain LENGTH and CHAR_LENGTH Functions

まとめ

練習用vagrant VMと予選のVMはスペックが必ずしも一致していなので一概には言えないが、
一応はここまでの対策で予選突破ラインの13898点に迫る得点を出せるようになった。ただ、 dstat 等でログを見る限りCPUが100%使い切れていないため、チューニングの余地はまだあると思われる。