ISUCON8予選をオンメモリ戦略で通過した
ISUCON8の予選に参加しました。運営の皆様お疲れ様でした、今年はオーソドックスな問題だった気がします。 isucon.net
結果 44,295点で全体8位、予選通過のようです。今年もよろしくお願いします。
メンバー
- chibiegg: インフラとコード
- misodengaku: インフラとコード
- __math: コード
- aki33524: 3人しか出れないので不参加 最近は太刀魚を釣っているらしい
死後硬直で曲がっとるがタチウオ pic.twitter.com/wzfiEsVdFk
— きひろちゃん@わたモテ百合はいいぞ (@aki33524) 2018年9月17日
以下箇条書き
- Goは速いだろうということでGoを選択。pythonの方が慣れているがCPU勝負になったときに不利…
- MacbookにGolandを入れていたが、Debuggerが起動せずに苦しんだ。なんか色々インストールする必要があるらしいが時間がないのでDebuggerなしでやることに
- Goのアプリのプロファイリング用にpprofというものがあるらしい、でも結局使わず
- misodengakuはリモートで参加。こちらの通話のみ聞こえており、misodengaku側がslackでのみ反応
競技開始
- パスワードでログインは面倒なので各サーバーにpublic keyを置いてもらう
- gitリポジトリを用意してもらう。GoのコードとDB初期化のコードはここで管理
- トイレに行って閉め出される、一回休み
- リバースプロキシはh2o、nginxじゃないの
- misodengaku, chibiegg がよしなにしてくれた
- アプリはGo + MySQLのシンプルなもの。フロントはjsで触るところはなかった。APIと何個かのhtmlを返すエンドポイントをいい感じにする
- 取りあえずベンチマークを走らせる。
09/16 10:18:47 レスポンスが遅いため負荷レベルを上げられませんでした。/ 09/16 10:18:48 レスポンスが遅いため負荷レベルを上げられませんでした。/ 09/16 10:18:49 レスポンスが遅いため負荷レベルを上げられませんでした。/ 09/16 10:18:50 レスポンスが遅いため負荷レベルを上げられませんでした。/ 09/16 10:18:51 レスポンスが遅いため負荷レベルを上げられませんでした。/ 09/16 10:18:52 レスポンスが遅いため負荷レベルを上げられませんでした。/ 09/16 10:18:53 レスポンスが遅いため負荷レベルを上げられませんでした。/ ...
- "/" が遅いらしい サーバの負荷は
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 7525 mysql 20 0 1633596 260344 9480 S 77.7 25.6 1:56.13 mysqld 7784 isucon 20 0 268432 145580 4720 R 31.3 14.3 0:38.41 torb
- とりあえずmysqlがネックらしい?コードを読む
- エンドポイントを洗い出す
- "/admin/" 以下になんかある?"/"以下と同じくらいの実装量のページ?
- table多い
- "/"がすごい量のSQLを吐き出している。localのGo + 本番サーバー上のMySQLで動かすとなんとレスポンスに40s+かかる。明らかにクエリを減らす必要がある
- ssh -L でトンネルを作って接続していた。全てのdev環境が本番DBを参照する素敵仕様
- ついでにサーバのスペック確認してもらう
CPU: 2 メモリ : 1GB
- メモリ少ないっぽい
- MySQLとGoがCPU/Memoryを食べあうことになりそうなので早めに分離。
アプリケーションサーバを3、DBを1にしました
misodengaku [11:12 AM] slowlog的にはここで全件取ってそうでやばそうぐらいしか見えない
e.GET("/admin/api/reports/sales", func(c echo.Context) error { rows, err := db.Query("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")
chibiegg [11:14 AM] リクエスト的には GET / GET /api/events/10 GET /admin/ POST /api/events/11/actions/reserve が重い (合計時間的な意味で)
- MySQLに格納されているデータを見る。
- INSERT/UPDATEのないテーブルは起動時にメモリに載せればいいよね
sheets
はもうちょっとなんとかなるでしょ- …ていうか全部合わせても100MBいかなくない?
- 基本全部Go側でデータ持てば良くない?MySQLはデータの永続化にのみ使用して、起動時にデータ全読み込みでいいよね?
- 2018/09/17 追記 アプリケーションを1つしか起動しなくてもパフォーマンス十分出るよね?
- ISUCONだからね
- INSERT/UPDATEのないテーブルは改造するのに難しい点はない。半分がメモリ上のデータ、残り半分がSQL発行してデータ取得しててもベンチマークは通るし通らないとバグっていることがわかる
- 一方INSERT/UPDATEがある場合は結構複雑、色々考えたけど競技時間が8時間しかないということで以下の方針で行くことにした
reservation
テーブルと例に上げると、
1. 起動時にDBから全reservationデータを取り出す
var ( reservationStore = make([]*Reservation, 0) reservationMutex = new(sync.Mutex) ) // main内と /initializeで呼ばれる func initReservation() error { rows, err := db.Query("SELECT * FROM reservations") if err != nil { return err } defer rows.Close() reservationStore = make([]*Reservation, 0) for rows.Next() { var reservation Reservation rows.Scan( &reservation.ID, &reservation.EventID, &reservation.SheetID, &reservation.UserID, &reservation.ReservedAt, &reservation.CanceledAt) reservationStore = append(reservationStore, &reservation) } return nil }
- SELECT/INSERT/UPDATEは全て
reservationStore
のデータを参照/追加/更新する - INSERT/UPDATEは、アプリ/マシンの再起動に備えてMySQLにもデータを流す。ただしアプリは起動時以外一切データを見ないので非同期でSQLを発行
// mutexで保護しつつ reservationStoreのデータを追加 go func() { res, err := db.Exec("INSERT INTO reservations (id, event_id, sheet_id, user_id, reserved_at) VALUES (?, ?, ?, ?, ?)", reservation.ID, reservation.EventID, reservation.SheetID, reservation.UserID, reservation.ReservedAt.Format("2006-01-02 15:04:05.000000")) if err != nil { log.Println("error happened on Exec") return } // 追加のエラーハンドリング }()
- メリット
- デメリット
event := eventStore[id] // eventの更新 go func() { // NG 実行されるgoroutineの順番によっては最新でないeventを元にしたUPDATEが発行される恐れがある if _, err := db.Exec("UPDATE events SET public_fg = ?, closed_fg = ? WHERE id = ?", event.PublicFg, event.ClosedFg, event.ID); err != nil { log.Println(err) } }()
- SAFE
// eventStoreの更新 go func() { // OK 実行されるgoroutineの順番によらず、最新の状態を元にUPDATEが発行される // どのeventStoreの更新よりの後に実行されるgoroutineは必ず一つ以上あるので、実行中にKillされない限りMySQL内のデータもいずれは最新の状態になる event, _ := getEvent(eventID, -1) if _, err := db.Exec("UPDATE events SET public_fg = ?, closed_fg = ? WHERE id = ?", event.PublicFg, event.ClosedFg, event.ID); err != nil { log.Println(err) } }()
ISUCON以外でやろうとすると怒られる。indexを貼ってもMySQLでパフォーマンスが満足できないなら次はRedisを試すのだろうか?
sheet
はボトルネックではないけど、他の箇所の編集と競合しづらいだろうと考えchibieggに頼む- INSERTがあるけど、
reservation
が減れば嬉しいだろうと考えてなんとかしようとする event
もでかいけど後回し- 11:30 くらいからみんなで着手し始めた
- このあたりでsheet関係のSQLが無くなったのでベンチマークを走らせたら"座席がランダムではありません"と怒られる。ランダムじゃないとだめなのか…
- Fisher-Yatesのシャッフルを実装したら通った。スコアは変わらず
- 13:30くらいになって
reservation
周りの半分くらいSQLを消す。この時点で半分がメモリ上の情報のみを参照して残りがDBの情報を参照する - 残りの
reservation
は私がして、chibieggとmisodengakuにuser
周りをなんとかしてもらうことに - 多分14時くらい
getEvents
が爆速になった(local 40s -> 1s未満)のでlocalでのデバッグが捗る - 15:00 全部
reservation
周りのSQLが全部消えたのでテストするけどfailする。多分UPDATEが悪さしてる - なんか
user
もバグってるらしい。reservation
の方が動かないとスコアは上がらないのでchibieggにdebugを頼む - INSERT時にMutexで保護する範囲を広げたり色々直す
- 15:34 30000点を超えて1位になったので喜ぶ
- Goがだいぶ分かってきたのでこの調子で
event
も剥がすことに。次のボトルネックを探してた気がするけど何だったか忘れてしまった - gzipで圧縮してみたら?ってことでやったらスコアが下がる
- 16:47
event
を剥がし終わったのでもっかいベンチを走らせるも25000点。topで見るとCPUを使い切っている - どうせ帯域は余裕があるしgzipを切る
- 40000点を超える
- CPUがボトルネックだしh2oも別サーバに移動で良くない?
- そんなに変わらない
- そろそろ残り1時間ちょっとだし、予選は突破できそうなのでベンチガチャを開始することに
- 17:14 最高得点(44295)が出る。何も変えてないのに2万点弱ブレてびっくりする
- 目標は予選突破であって1位ではないのでこれで撤収。ホワイトなISUCONだった
感想
- MySQLからデータを剥がしてスコアが上がるのは面白い、結局今回はindexを使わなかった気がする
- ちゃんとindexを貼ってもスコアは上がったらしい?こっちの戦略でも良かったかな…
- プロファイリングが必要な段階まで行けなかったのは心残り
- データ全部剥がした後適切なデータ構造で管理すればスコアは軽く倍になりそう。20万の
reservation
を愚直に回しまくっていたのが問題
- データ全部剥がした後適切なデータ構造で管理すればスコアは軽く倍になりそう。20万の
From(reservationStore).Where(func(c interface{}) bool { r := c.(*Reservation) if r.EventID != event.ID { return false } if r.CanceledAt != nil { return false } return true }).ToSlice(&reservations)
- Goでlinq辛すぎ問題。interface{}何回出てくるんだ…
SELECT event_id FROM reservations WHERE user_id = ? GROUP BY event_id ORDER BY MAX(IFNULL(canceled_at, reserved_at)) DESC LIMIT 5
- After
From(relatedReservations).GroupBy(func(c interface{}) interface{}{ r := c.(*Reservation) return r.EventID }, func(c interface{}) interface{} { return c }).OrderByDescending(func(c interface{}) interface{} { values := c.(Group).Group maxTime := From(values).Select(func(c2 interface{}) interface{} { r := c2.(*Reservation) if r.CanceledAt != nil { return r.CanceledAt.UnixNano() } else { return r.ReservedAt.UnixNano() } }).Max().(int64) return maxTime }).Take(5).Select(func(c interface{}) interface{} { eventId := c.(Group).Key return eventId }).ToSlice(&eventIds)
- 普段使わないlaptopで苦戦した。IDEのインストールとかは事前にするとよさそう
- branch名を間違えてreserveのつもりがreverseになっていた。英語…
- 面白かったです