ISUCON8予選突破しました

予選突破

ISUCONというWebアプリケーションのパフォーマンス改善コンテストに参加し、予選突破しました。去年は不参加だったので2年振り2度目。(blog書くのもISUCON6振りで2年振りという... output無さすぎ)

いやー実に楽しかった。やっぱりISUCONでしか味わえないモノがある。いつも何か新しい学びがある。

予選は両日共に問題なく進んだようですし、予選問題もいい問題でした。ベンチマーカーが詰まることもなく快適な予選でした。運営のみなさんありがとうございます。

久しぶりの参加だったので事前にISUCON7予選を解いてみたりconoha vpsでサーバ立ててansibleやfabric(deployに使っている)の動作確認をしたりして挑みました。ISUCON7予選を動かし始めたらあーこの感じやっぱり楽しいなと思って気持ちを高めてISUCON8に臨めて良かった。何を事前準備しないとイケないのかの確認もできたので予習大事ですね。

チーム:死闘の果てに

@najeiraとまた出ようって話はしてたけど、もう一人のメンバーが見つからずダメ元でTwitterで募集する。

ss 2018-09-17 21 55 03 ss 2018-09-17 21 55 55 ss 2018-09-17 21 56 01

マジで@songmuさん来てくれんの!?ってことでめっちゃテンション上がりました。

予選の結果は528組中7位

予選は528組(一般 432、学生96 [1,392名])中 7位でした。

ss 2018-09-17 21 49 37

  • 学生3チームも上位3チームに入ってるの本当に凄い

http://isucon.net/archives/cat_1024995.html

最終スコア

最終スコア

スコアの推移が記録できていないので何を変更したら何点行ったのかイマイチわからず。途中はベンチマーク結果がランダムに成功したり失敗したりの繰り返しで安定せず、スコアが出れば2万みたいな状態が続きました。

najeiraがアプリを改善し常に成功するようになったところで、後に記載する予約済みテーブルの対応を入れたところ3.8万が出て再実行しても失敗しないか確認の為に2回追加で実行したらスコアが上がって4.5万で終わり。まだ時間はあったのでsongmuさんのRedis対応を入れたかったが予選通過の可能性があったので安全のためにもうベンチマーカーを実行するのをやめて終了。

Redis実装入ったら何点だったのか見たかったーー。毎回思うけど時間切れ後に最後にこの実装入れたら何点になっていたのかって知りたい。

予選問題

チケット販売システム。席を予約するので排他制御が必要でMySQLのロックが含まれる問題でした。

サーバはCentOS7 3台で最初は1台にAppとMariaDBが入っている構成でスタート。

予選でやったこと

ざっと変更点を箇条書き(私以外のところは私の把握してる範囲のみ)

  • songmu
    • validateRankのselect count from sheetsを無くす
    • reservetions#last_updated_atのカラムを追加してORDER BY IFNULL(r.canceled_at, r.reserved_at) DESC LIMIT 5ORDER BY last_updated_at DESC LIMIT 5で済むようにする
    • Redisで空き座席を管理するようにしてMySQLでFOR UPDATEしているactions/reserveを高速化(これは間に合わず断念)
  • najeira
    • getEvents/getEventでevent_id INにするなどしてSQL発行回数を減らす
    • h2oをnginxに変更
    • DBサーバ、Webサーバ、Redisサーバの3台構成にする
  • bluerabbit
    • 計測/分析
    • reservetionsにINDEX追加
    • 予約済みテーブルを追加しreservetionsをreadしてるSQLを高速化

予選でやらなかったこと

  • Webサーバー複数台
  • getEventなどの検索結果のキャッシュ
  • DBのチューニング
  • goライブラリの変更
  • Viewレイヤーの変更
  • MySQLのFOR UPDATEの処理変更

作業分担

私は普段goは書かないので前半は計測やINDEX作成などの裏方作業をしてgoは得意な二人に任せることにした。

後に記載する計測結果でgetEventと座席の排他制御がキモだと判断し、getEventのN+1 Queryを@najeira、Redisで空き座席を管理する一番難しいところを@songmuという担当になった。

事前の打ち合わせは数日前に1時間ほど話をした程度だったがスムーズに担当割できた。

以下は私がやったことと計測の仕方や対応した内容を書く

各テーブルのレコード数を確認する

まず最初に初期実装のベンチマークを実行した後のレコード件数を記録する

select count(*) from administrators -- 101
select count(*) from events -- 20
select count(*) from reservations -- 191847
select count(*) from sheets -- 1000
select count(*) from users -- 5012

ベンチマーク実行前の件数は取得し忘れたが、実行前後で見比べてレコード数に変化があるテーブルと変化の無いテーブルを確認する。変化の無いテーブルはキャッシュするなどの対象になるが今回はキャッシュはしなかった。

各メソッドとendpointの実行回数を計測する

najeiraとISUCONに出る時はいつもコレで計測する

https://github.com/najeira/measure を使って各メソッドとendpointの実行回数と時間を計測する

func getEvent(eventID, loginUserID int64) (*Event, error) {
  defer measure.Start("getEvent").Stop()
  • 各メソッドで計測コードを入れる
e.POST("/api/events/:id/actions/reserve", func(c echo.Context) error {
  defer measure.Start("POST_/api/events/:id/actions/reserve").Stop()
  • 各endpointで計測コードを入れる
  e.GET("/stats", getStatsHandler)
  e.GET("/stats_reset", resetStatsHandler)
  • 計測結果を簡単に取れるendpointを用意しておく。ブラウザで開くとcsvが表示されるようにした。
    • 特定のパスにリクエストするとデバッグ結果が取れるみたいな仕組みは便利なのでオススメ

初期実装の計測

measureの埋め込みが終わったらベンチマークを実行した後に/statsの結果をGoogle SpreadSheetに貼り付けてチームメンバーに共有する。多く実行されていて遅いメソッドを上から順に対応していく

ss 2018-09-17 19 17 03

ざっと大雑把にでも読み解くと

  • getEventが一番問題がありそう
  • /api/users/:idは内部でgetEventを呼び出しているから遅い
  • getEventとgetEventsが問題ありそう
  • 次に問題になりそうなpathはactions/reserveだと推測できる

という形でコレだけで対応しないとイケなそうな場所がわかる。計測結果の上位に無い処理はどんなに気になっても手を入れないし、深く調べもしないと切り分けられるのが大事。ボトルネックにだけ集中する。 コレ以外ではdstatやpt-query-digestなどを気になった時に使う形。

アプリはgoが得意な二人に任せる

全てのSQLを書き出す

次はDBに必要なINDEXを付与する。機械的SQLをとりあえず書き出す。 思考内容も参考までに書いてみる

SELECT id, nickname FROM users WHERE id = ?
SELECT id, nickname FROM administrators WHERE id = ?
SELECT * FROM events ORDER BY id ASC
SELECT * FROM events WHERE id = ?
SELECT * FROM sheets ORDER BY `rank`, num
  • rank, numにindexはあるのかな?
SELECT * FROM reservations 
WHERE event_id = ? 
AND sheet_id = ? 
AND canceled_at IS NULL 
GROUP BY event_id, sheet_id 
HAVING reserved_at = MIN(reserved_at)
  • event_id, sheet_id, canceled_at に複合INDEXかなー
  • でもGROUP BYした結果セットが多いとHAVING reserved_atがめちゃ遅くなるなー
SELECT COUNT(*) FROM sheets WHERE `rank` = ?
  • rankにindexはあるのかな?
SELECT * FROM users WHERE login_name = ?
  • login_nameにindexはあるのかな?
INSERT INTO users (login_name, pass_hash, nickname) VALUES (?, SHA2(?, 256), ?)
  • SHA2関数かでもSQLの関数はあんまり遅くなった記憶は無いから一旦無視かな
SELECT id, nickname FROM users WHERE id = ?
SELECT r.*, s.rank AS sheet_rank, s.num AS sheet_num 
FROM reservations r 
  INNER JOIN sheets s ON s.id = r.sheet_id 
WHERE r.user_id = ? 
ORDER BY
  IFNULL(r.canceled_at, r.reserved_at) DESC LIMIT 5
  • user_id, sheet_idの複合INDEX使っても結果が多かったらORDER BYがだいぶ辛いし、LIMIT 5かー
  • IFNULL(r.canceled_at, r.reserved_at) はどうにかできないのかなー
SELECT IFNULL(SUM(e.price + s.price), 0) 
FROM 
  reservations r 
    INNER JOIN sheets s ON s.id = r.sheet_id 
    INNER JOIN events e ON e.id = r.event_id 
WHERE r.user_id = ?
AND r.canceled_at IS NULL
  • user_id, canceled_at, sheet_idの複合INDEXかな
SELECT event_id 
FROM reservations 
WHERE user_id = ? 
GROUP BY event_id 
ORDER BY MAX(IFNULL(canceled_at, reserved_at)) DESC LIMIT 5
  • またIFNULL(canceled_at, reserved_at)か
  • user_id, event_idの複合はINDEXは必要だなー
SELECT * FROM users WHERE login_name = ?"
SELECT SHA2(?, 256)
  • SQLでやらなくて良さそう計測結果が問題だったら対応かな
SELECT * 
FROM sheets 
WHERE id NOT IN (
  SELECT sheet_id 
  FROM reservations 
  WHERE event_id = ? 
  AND canceled_at IS NULL FOR UPDATE
) AND `rank` = ?
ORDER BY RAND() LIMIT 1
  • FOR UPDATE!!!
  • ORDER BY RAND()も怪しい
  • event_id, canceled_atの複合INDEXかな
INSERT INTO reservations (event_id, sheet_id, user_id, reserved_at) VALUES (?, ?, ?, ?)
SELECT * FROM sheets WHERE `rank` = ? AND num = ?
  • rank, numはINDEX必要なのかなー
SELECT * FROM reservations 
WHERE event_id = ? 
AND sheet_id = ? 
AND canceled_at IS NULL GROUP BY event_id 
HAVING reserved_at = MIN(reserved_at) FOR UPDATE
  • event_id, sheet_id, canceled_atの複合INDEXかな
UPDATE reservations SET canceled_at = ? WHERE id = ?
SELECT * FROM administrators WHERE login_name = ?
SELECT SHA2(?, 256)
INSERT INTO events (title, public_fg, closed_fg, price) VALUES (?, ?, 0, ?)
UPDATE events SET public_fg = ?, closed_fg = ? WHERE id = ?
SELECT r.*, s.rank AS sheet_rank, s.num AS sheet_num, s.price AS sheet_price, e.price AS event_price
FROM reservations r 
  INNER JOIN sheets s ON s.id = r.sheet_id 
  INNER JOIN events e ON e.id = r.event_id 
WHERE r.event_id = ? 
ORDER BY reserved_at ASC FOR UPDATE
  • MySQLでJOINしてFOR UPDATEはJOIN対象もロックかかるから範囲広いなー
  • event_id, sheet_id, reserved_atの複合INDEXかな
select r.*, s.rank as sheet_rank, s.num as sheet_num, s.price as sheet_price, e.id as event_id, e.price as event_price 
from reservations r 
  inner join sheets s on s.id = r.sheet_id 
  inner join events e on e.id = r.event_id 
order by reserved_at asc for update

などSQLをざっと眺めて必要そうなINDEXを追加

ss 2018-09-17 21 15 43

予約済みテーブルを作成する

次のようなキャンセルしていない(予約済み)レコードを検索するSQLが多かった。

FROM reservations 
WHERE event_id = ?  AND sheet_id = ? AND canceled_at IS NULL 

下記を実行すると全体の19万件中の1.5万件ほどしか存在しない事がわかる。

select count(*) from reservations where canceled_at IS NULL -- 15000

次のようなテーブルを作った(sheetsはseatsの間違いw)

CREATE TABLE IF NOT EXISTS reserved_sheets (
    id          INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT,
    reservation_id INTEGER UNSIGNED NOT NULL,
    event_id    INTEGER UNSIGNED NOT NULL,
    sheet_id    INTEGER UNSIGNED NOT NULL,
    user_id     INTEGER UNSIGNED NOT NULL,
    reserved_at DATETIME(6)      NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE INDEX reserved_sheets_reservation_id ON reserved_sheets (reservation_id)
CREATE INDEX reserved_sheets_event_id_sheet_id_reserved_at ON reserved_sheets (event_id, sheet_id, reserved_at)
CREATE INDEX reserved_sheets_user_id ON reserved_sheets (user_id)

初期化処理で既存データをSELECT INSERTで作る

INSERT INTO reserved_sheets (reservation_id, event_id, sheet_id, user_id, reserved_at) 
SELECT id, event_id, sheet_id, user_id, reserved_at FROM reservations 
WHERE canceled_at IS NULL ORDER BY event_id, sheet_id, reserved_at

予約済みテーブルを使って高速化/DB負荷を下げる

ss 2018-09-17 18 49 34

  • 上記のようにcanceled_at IS NULLは全部書き換えられる
  • 一番件数の多いreservationsと戦う必要がなくなる

次のようなSQL

SELECT * FROM reservations
WHERE event_id = ? AND sheet_id = ? AND canceled_at IS NULL
GROUP BY event_id, sheet_id
HAVING reserved_at = MIN(reserved_at)

reserved_sheetsを使うとINDEXが効いたSQLに変更できる

SELECT * FROM reserved_sheets
WHERE event_id = ? AND sheet_id = ?
GROUP BY event_id, sheet_id

実際にはnajeiraがN+1を対応済みだったので違うSQLで上記は例

中間スコア

13:25時点のスクショが1つだけ手元にあったので記録用にのせておく、振り返るとココからなかなか伸びなかったことがわかる。

中間スコア

最終スコア時の計測結果

ss 2018-09-17 23 40 58

  • 最後の計測結果は操作がバタバタだったので微妙に結果がスコアと一致してるのか怪しいですが参考までに
  • getEventが問題なくなって、予約とキャンセルのロック処理がボトルネックに変わっているのがわかる

決勝の本戦は10月

初優勝したい。