math314のブログ

主に競技プログラミング,CTFの結果を載せます

ISUCON8予選をオンメモリ戦略で通過した

ISUCON8の予選に参加しました。運営の皆様お疲れ様でした、今年はオーソドックスな問題だった気がします。 isucon.net

結果 44,295点で全体8位、予選通過のようです。今年もよろしくお願いします。

メンバー

  • chibiegg: インフラとコード
  • misodengaku: インフラとコード
  • __math: コード
  • aki33524: 3人しか出れないので不参加 最近は太刀魚を釣っているらしい

以下箇条書き

  • 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
}
  1. SELECT/INSERT/UPDATEは全てreservationStoreのデータを参照/追加/更新する
  2. 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
        }
                // 追加のエラーハンドリング
         }()
  • メリット
    • 実装途中でも負荷が少なければそれなりに動く。例えばSELECTはメモリ上のreservationStoreを参照、INSERT/UPDATEはSQLを同期的に発行しつつreservationStoreも更新という実装でも一応動く
      • でもtransactionとか消えてるから死ぬときは死ぬ。多分ベンチマークは通らない
      • GoだとSQL発行の同期/非同期の切り替えがとても簡単。非同期にしてバグったら最悪同期に戻すことでベンチマークを通すことが出来る
    • 完成してしまえばMySQL依存は無くなる。場合によってはN+1問題が発生していた箇所は放置しても爆速になっている可能性すらあるので他の改善に時間が使える
  • デメリット
    • 全部実装し終えないとベンチが通らない
    • MySQLにindexを貼ったりcolumnを整理した方が早くなる場合が大半なので慎重に考える
    • goroutine内(非同期)でSQLを発行することに気をつける。UPDATEは気をつけないとおそらく死ぬ
    • NG
   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位になったので喜ぶ f:id:math314:20180917191711p:plain
  • Goがだいぶ分かってきたのでこの調子でeventも剥がすことに。次のボトルネックを探してた気がするけど何だったか忘れてしまった
  • gzipで圧縮してみたら?ってことでやったらスコアが下がる
  • 16:47 eventを剥がし終わったのでもっかいベンチを走らせるも25000点。topで見るとCPUを使い切っている
  • どうせ帯域は余裕があるしgzipを切る
  • 40000点を超える
  • CPUがボトルネックだしh2oも別サーバに移動で良くない?
  • そんなに変わらない
  • そろそろ残り1時間ちょっとだし、予選は突破できそうなのでベンチガチャを開始することに
  • 17:14 最高得点(44295)が出る。何も変えてないのに2万点弱ブレてびっくりする f:id:math314:20180917192755p:plain
  • 目標は予選突破であって1位ではないのでこれで撤収。ホワイトなISUCONだった

感想

  • MySQLからデータを剥がしてスコアが上がるのは面白い、結局今回はindexを使わなかった気がする
    • ちゃんとindexを貼ってもスコアは上がったらしい?こっちの戦略でも良かったかな…
  • プロファイリングが必要な段階まで行けなかったのは心残り
           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)
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になっていた。英語…
  • 面白かったです