チームooooookayamaでISUCON12予選に参加した

hackMD版

hackmd.io

チーム ooooookayama

ninja
nagatech
masutech

で参加して13861点の予選敗退でした。
ログやインフラ部分は他二人に任せて、主にアプリ部分のコード/SQLを書くところを担当しました。

最終提出の構成

isuports-1
- MySQLサーバー
isuports-2
- 使ってない
isuports-3
- Nginx
- アプリ
  - sqlite

大まかな改善箇所

billing系

billingの計算で終了していないcompetitionの計算をしない
billingのcompetitionの料金をキャッシュする
- 終了した後に料金は変更しないため

GET /api/player/player/:player_id

/api/player/player/:player_idではtenantDBに対して3種類のクエリが発行されていました。

大会を取得
大会ごとに最終スコアを取得
スコアごとに大会名を取得

少なくとも3は不要です。
プレイヤーの最終提出さえあれば問題ないため、あるプレイヤーの大会全てでの最終提出をサブクエリで取得して(mps)、提出と大会情報をJOINするようにしました。

SELECT c.title, ps.score FROM 
    (SELECT tenant_id, competition_id, player_id, MAX(row_num) row_num 
    FROM player_score
    WHERE tenant_id = ? AND player_id = ?
    GROUP BY tenant_id, competition_id, player_id) mps
JOIN player_score ps
    ON mps.player_id = ps.player_id AND
        mps.competition_id = ps.competition_id AND
        mps.tenant_id = ps.tenant_id AND
        mps.row_num = ps.row_num
JOIN competition c
    ON ps.competition_id = c.id

visit_historyのスキーマ変更

adminDBに存在するvisit_historyテーブルはランキングを見にきたplayerの履歴が保管されているテーブルです。
billingの計算で使用されますが、created_atの最小値のみ使われるため、(`player_id`, `tenant_id`, `competition_id`)の組み合わせに対して複数のデータは不要となっています。
上記のカラムの(`player_id`, `tenant_id`, `competition_id`)を主キーとするテーブルを新規に作成し、INSERT IGNOREを用いることで挿入される行数を減らしました。

CREATE TABLE `visit_history2` (
      `player_id` VARCHAR(255) NOT NULL,
      `tenant_id` BIGINT UNSIGNED NOT NULL,
      `competition_id` VARCHAR(255) NOT NULL,
      `created_at` BIGINT NOT NULL,
      INDEX `tenant_id_idx` (`tenant_id`),
      PRIMARY KEY (`player_id`, `tenant_id`, `competition_id`)
) ENGINE=InnoDB DEFAULT CHARACTER SET=utf8mb4;

visit_historyは初期データの時点で1,400,000行ほど存在するため、initializeで処理を行わず、直接DBにクエリを投げて移行しました。
3~4分ぐらいかかりました。

INSERT INTO visit_history2 (player_id, tenant_id, competition_id, created_at)
    (SELECT v.player_id, v.tenant_id, v.competition_id, MIN(v.created_at)
     FROM visit_history v
     GROUP BY (v.player_id, v.tenant_id, v.competition_id))
# ログが残ってなかったので記憶から再現しています
# おそらく動く

DBサーバーの分離

MySQLを別のサーバーに分離しました
(1のサーバーでスキーマ変更していたため、アプリ/Nginx側を別サーバーに分離しています)

bulk insert POST /api/organizer/competition/:competition_id/score

データごとにINSERT文が発行されていたので一括で行うようにしました。

func competitionScoreHandler(c echo.Context) error {
//...
    
	params := make([]interface{}, 0, 500)
	query := "INSERT INTO player_score (id, tenant_id, player_id, competition_id, score, row_num, created_at, updated_at) VALUES "
	first := true
	// (?,?,?,?,?,?,?,?)

	for _, ps := range playerScoreRows {
		params = append(params, ps.ID, ps.TenantID, ps.PlayerID, ps.CompetitionID, ps.Score, ps.RowNum, ps.CreatedAt, ps.UpdatedAt)
		if first {
			first = false
			query += "(?,?,?,?,?,?,?,?)"
		} else {
			query += ",(?,?,?,?,?,?,?,?)"
		}
		if len(params) > 60000 {
			_, err := tenantDB.ExecContext(ctx, query, params...)
			if err != nil {
				return fmt.Errorf(
					"error Insert player_score: id=%s, tenant_id=%d, playerID=%s, competitionID=%s, score=%d, rowNum=%d, createdAt=%d, updatedAt=%d, %w",
					ps.ID, ps.TenantID, ps.PlayerID, ps.CompetitionID, ps.Score, ps.RowNum, ps.CreatedAt, ps.UpdatedAt, err,
				)
			}
			params = make([]interface{}, 0, len(playerScoreRows)*8)
			query = "INSERT INTO player_score (id, tenant_id, player_id, competition_id, score, row_num, created_at, updated_at) VALUES "
			first = true
		}
	}
	if len(params) > 0 {
		_, err := tenantDB.ExecContext(ctx, query, params...)
		if err != nil {
			return fmt.Errorf(
				"error Insert player_score: %w", err,
			)

		}
	}

スキーマ変更のときにプレースホルダの上限のエラーに遭遇したため、データ数が多くでも大丈夫なようにしていますが不要だと思います。

TooMany上限

ここまでの改善を入れた結果、大会の追加でエラーになりスコアが50%~100%で減点されるようなりました。
当日マニュアルで許容されている大会の追加 (POST /api/organizer/competitions/add) に上限を設けてTooManyを返すようにしました。
compLimitは/initializeで初期化します。

func competitionsAddHandler(c echo.Context) error {
//...
	compMux.Lock()
	if compLimit > 15 {
		compMux.Unlock()
		c.Response().Header().Add("Retry-After", "60")
		return echo.NewHTTPError(http.StatusTooManyRequests)
	}
	compLimit += 1
	compMux.Unlock()

sync/atomicのatomic.AddUint32()で良かったと思われる。

file lockをやめる

tenantDBに対する操作でfile lockが取られており、Read同士でも待ちが発生していました。
goのsync.RWMutexを用いてfile lockを取らないようにしました。

var tenantMuxs sync.Map

func flockByTenantID(tenantID int64) (*sync.RWMutex, error) {
	if mux, ok := tenantMuxs.Load(tenantID); ok {
		return mux.(*sync.RWMutex), nil
	}
	mx := sync.RWMutex{}
	tenantMuxs.Store(tenantID, &mx)
	return &mx, nil
}

(利用側でLock、RLockを使い分ける)

id_generatorをアプリ側で行う

nagatechにやってもらいました

func dispenseID(ctx context.Context) (string, error) {
	var id int64
	var lastErr error
	idGeneratorMux.Lock()
	{
		if idGeneratorID < idGeneratorFirstID {
			idGeneratorID = idGeneratorFirstID
		}
		break
		idGeneratorID += 1
		id = idGeneratorID
	}
	idGeneratorMux.Unlock()
	if id != 0 {
		return fmt.Sprintf("%x", id), nil
	}
    // ...

GET /api/player/competition/:competition_id/ranking

competitionの上位100件のスコアを1回で取るクエリを書きました。
サブクエリのmpsで最終提出を取得し、後からソートしてrankAfterのページングを効かせます。

SELECT ps.row_num, ps.player_id, p.display_name, ps.score
FROM (SELECT player_id pid, tenant_id tid, competition_id cid, MAX(row_num) mrn
      FROM player_score ps
      WHERE tenant_id = ?
        AND competition_id = ?
      GROUP BY player_id, tenant_id, competition_id) mps
         JOIN player_score ps ON mps.pid = ps.player_id AND
         mps.mrn = ps.row_num AND
         mps.cid = ps.competition_id AND
         mps.tid = ps.tenant_id
         JOIN player p on ps.player_id = p.id
ORDER BY ps.score DESC, ps.row_num ASC
LIMIT ?, 100

ログからrankAfterは未指定のものが大半であることが分かっていたため、0のときのみキャッシュするようにしました。
(CSV入稿でキャッシュを破棄する)

結果

file lock、id_generatorをアプリ側で行う付近で最高点の20000点を出していたものの、以降はスコアに対して有効な改善が入らず、10000点台を浮遊して13000点で終了しました。

今思いつく改善点としては以下がありそうです。

sqliteのplayer_scoreテーブルのインデックス
RWMutexではなくtransactionを使う
sqliteからMySQLへの移行
- 3台構成

終了2時間前時点で有効打が尽きていたのでMySQL移行のような攻めた戦略をとっていた方が良かったかもしれません。

今回良かったところ

visit_historyのスキーマ変更のような破壊的変更が序盤で通せていた
- 初期化処理がここ最近のISUCON予選と違っていたので気を使う必要があった
事前準備でブランチ単位のデプロイができるようにしておいた