Open20

ISUCON12予選に参加しました(記録メモ)

ISUCON12予選の参加記録です。

https://isucon.net/archives/56571716.html

ISUCON5予選参加以来
ソロチーム

結果:
予選敗退
最終スコア 7627

以下大会時にやったことを時系列で書いてます。

環境構築

マニュアル通り用意されたAWS CloudFormationテンプレートからスタックを作成

sshしてenvchecker実行しておく。おk

$ sudo /usr/local/bin/isucon-env-checker
環境をチェックしています...
全てのチェックをパスしました

とりあえずベンチ回して

初期スコア 2500

開発環境

  • git
  • iTerm2 + tmux統合
  • IntelliJ
  • Makefile
    • 頻繁に叩くデプロイコマンドを随時足してく

計測ツール

  • pt-query-digest
  • alp
  • pprof
  • htop
  • dstat

mysqlのCPU使用率が高い

pt-query-digest見るにこのクエリが支配的

REPLACE INTO id_generator (stub) VALUES ('a')\G

コードでいうとここ

// システム全体で一意なIDを生成する
func dispenseID(ctx context.Context) (string, error) {
	var id int64
	var lastErr error
	for i := 0; i < 100; i++ {
		var ret sql.Result
		ret, err := adminDB.ExecContext(ctx, "REPLACE INTO id_generator (stub) VALUES (?);", "a")
		if err != nil {
			if merr, ok := err.(*mysql.MySQLError); ok && merr.Number == 1213 { // deadlock
				lastErr = fmt.Errorf("error REPLACE INTO id_generator: %w", err)
				continue
			}
			return "", fmt.Errorf("error REPLACE INTO id_generator: %w", err)
		}
		id, err = ret.LastInsertId()
		if err != nil {
			return "", fmt.Errorf("error ret.LastInsertId: %w", err)
		}
		break
	}
	if id != 0 {
		return fmt.Sprintf("%x", id), nil
	}
	return "", lastErr
}

このときpt-query-digestの結果がやけに項目数少ないな〜と思ってた(このときはまだsqliteの存在を知らない

dispenseID funcは次のエンドポイントから呼ばれてる

  • GET /api/organizer/players/add
  • POST /api/organizer/competitions/add
  • POST /api/organizer/competition/:competition_id/score

forで100回試行してるけど一回目で即諦めてもいいのではとループ消して再度ベンチ
REPLACE INTO id_generatorの負荷が圧倒的に高いことには変わりなし

id生成をapp側でやるように変更

// システム全体で一意なIDを生成する
func dispenseID(ctx context.Context) (string, error) {
	return xid.New().String(), nil
}

結果 score 4760

まだmysqlの負荷が高い

mysql> explain SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = 36 AND competition_id = '14d7c5086' GROUP BY player_id\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: visit_history
   partitions: NULL
         type: ref
possible_keys: tenant_id_idx
          key: tenant_id_idx
      key_len: 8
          ref: const
         rows: 84748
     filtered: 10.00
        Extra: Using where; Using temporary
1 row in set, 1 warning (0.00 sec)

visit_historyテーブルのスキーマ

mysql> show create table visit_history\G
*************************** 1. row ***************************
       Table: visit_history
Create Table: CREATE TABLE `visit_history` (
  `player_id` varchar(255) NOT NULL,
  `tenant_id` bigint unsigned NOT NULL,
  `competition_id` varchar(255) NOT NULL,
  `created_at` bigint NOT NULL,
  `updated_at` bigint NOT NULL,
  KEY `tenant_id_idx` (`tenant_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.01 sec)

tenant_idとcompetition_idの複合インデックス足す。

どうやって追加migrationするか把握する。ベンチの最初に呼ばれる/initializeの動きを追う
admindbのスキーマはwebapp/sql/admin/10_schema.sqlにあるが、/initialize内で呼ばれるわけではない。

webapp/sql/adminのとなりにtenantディレクトリもあるけどこっちは今の所触る機会なく見てすらいない(まだsqliteの存在を知らない

マイグレーションスクリプトを手動で流す

-- webapp/sql/admin/101_add_index.sql
ALTER TABLE visit_history ADD INDEX tenant_competition_id_idx (tenant_id, competition_id);

インデックス追加ごのexplain

mysql> explain SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = 36 AND competition_id = '14d7c5086' GROUP BY player_id\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: visit_history
   partitions: NULL
         type: ref
possible_keys: tenant_id_idx,tenant_competition_id_idx
          key: tenant_competition_id_idx
      key_len: 1030
          ref: const,const
         rows: 1618
     filtered: 100.00
        Extra: Using temporary
1 row in set, 1 warning (0.00 sec)

ここまでやると、mysqlに偏っていた負荷がisuports.serviceに移った

score 5900

alp見ると次のボトルネックはGET /api/player/competition/.+/ranking

内部実装を追う

SQLiteの存在を知る

まさかのSQLiteに動揺。ここで休憩

頭悩ます

  • SQLiteと添い遂げる案
    • SQLite自体の性能限界どうなのか
    • チューニングできるか、slow query logをどう出すか
    • SQLiteのまま行くとしてどう複数サーバ構成を実現するか
      • テナントDB横断する必要があるクエリを調べたり
      • レプリケーション方法
      • nginxレイヤなりでテナントごとに投げ先を切り替えるか
  • MySQLに移行頑張るか
    • 慣れてないSQLiteだけど自分できるのか?!
    • 移行撤退リスクは全然ある。ソロだし、他の改善余地いくつもあるのに全部止まるぞ

30分くらい悩んだ結果SQLiteと添い遂げることに決めた

とりあえずMySQLは別サーバに移して複数台構成にしておく

SQLiteのslow query logの出し方がわからない。。。

調べつつ、限られた計測情報の中でチューニングを試みる

-- webapp/sql/tenant/10_schema.sql
CREATE INDEX competition_tenant_idx ON competition(tenant_id);
CREATE INDEX player_tenant_idx ON player(tenant_id);
CREATE INDEX player_score_tenant_comp_idx ON player_score(tenant_id, competition_id, player_id);
CREATE INDEX row_num_idx ON player_score(tenant_id, player_id, row_num desc);

追記:
あとからわかったが10_schema.sqlの変更だけだと新規作成されたtenantdbにしかインデックスが貼られない。不十分だった。。。
あと、tenantごとにdbが分かれているのでtenant_idカラムについてのインデックスは意味なかった😇

GET /api/player/player/:player_idGET /api/player/competition/.+/ranking が支配的

+-------+------+-----+-----+-----+--------+---------------------------------------+-------+--------+----------+-------+--------+
| COUNT | 2XX  | 3XX | 4XX | 5XX | METHOD |                  URI                  |  MIN  |  MAX   |   SUM    |  AVG  |  P99   |
+-------+------+-----+-----+-----+--------+---------------------------------------+-------+--------+----------+-------+--------+
| 2062  | 2027 | 0   | 32  | 3   | GET    | /api/player/player/.+                 | 0.008 | 30.000 | 1934.424 | 0.938 | 10.308 |
| 1571  | 1532 | 0   | 39  | 0   | GET    | /api/player/competition/.+/ranking    | 0.004 | 30.000 | 1752.624 | 1.116 | 10.484 |
| 260   | 245  | 0   | 15  | 0   | GET    | /api/player/competitions              | 0.000 | 2.840  | 150.192  | 0.578 | 2.744  |
| 96    | 89   | 0   | 7   | 0   | POST   | /api/organizer/competition/.+/score   | 0.088 | 10.348 | 145.820  | 1.519 | 10.348 |
| 39    | 38   | 0   | 1   | 0   | GET    | /api/admin/tenants/billing            | 0.420 | 30.860 | 75.856   | 1.945 | 30.860 |
| 44    | 44   | 0   | 0   | 0   | GET    | /api/organizer/billing                | 0.004 | 2.904  | 7.508    | 0.171 | 2.904  |
| 1     | 1    | 0   | 0   | 0   | POST   | /initialize                           | 2.161 | 2.161  | 2.161    | 2.161 | 2.161  |
| 75    | 74   | 0   | 1   | 0   | POST   | /api/organizer/competitions/add       | 0.004 | 0.344  | 1.244    | 0.017 | 0.344  |
| 68    | 67   | 0   | 1   | 0   | POST   | /api/organizer/competition/.+/finish  | 0.004 | 0.028  | 0.748    | 0.011 | 0.028  |
| 12    | 7    | 0   | 5   | 0   | POST   | /api/admin/tenants/add                | 0.004 | 0.120  | 0.568    | 0.047 | 0.120  |
| 57    | 57   | 0   | 0   | 0   | GET    | /api/organizer/players                | 0.004 | 0.116  | 0.548    | 0.010 | 0.116  |
| 18    | 17   | 0   | 1   | 0   | POST   | /api/organizer/player/.+/disqualified | 0.004 | 0.028  | 0.208    | 0.012 | 0.028  |
| 12    | 12   | 0   | 0   | 0   | POST   | /api/organizer/players/add            | 0.008 | 0.024  | 0.200    | 0.017 | 0.024  |
| 1     | 1    | 0   | 0   | 0   | GET    | /css                                  | 0.000 | 0.000  | 0.000    | 0.000 | 0.000  |
| 1     | 1    | 0   | 0   | 0   | GET    | /js                                   | 0.000 | 0.000  | 0.000    | 0.000 | 0.000  |
| 1     | 1    | 0   | 0   | 0   | GET    | /index.html                           | 0.000 | 0.000  | 0.000    | 0.000 | 0.000  |
| 1     | 1    | 0   | 0   | 0   | GET    | /api/organizer/competitions           | 0.000 | 0.000  | 0.000    | 0.000 | 0.000  |
+-------+------+-----+-----+-----+--------+---------------------------------------+-------+--------+----------+-------+--------+

// GET /api/player/player/:player_id

ここのN+問題解消

最初にcompetition一覧をとってきてからPlayerScoreRowを作るまでもなく、一発で取ってきたらいい

// func playerHandler(c echo.Context) error {

       	pss := make([]PlayerScoreRow, 0, 100)
        query := `SELECT id, tenant_id, player_id, competition_id, score, max(row_num) as row_num, created_at, updated_at FROM player_score WHERE tenant_id = ? AND player_id = ?` // GROUP BY id, tenant_id, player_id, competition_id, score // groupbyなしでmax取れたがほんとに?ベンチはパスした

	if err := tenantDB.SelectContext(
		ctx,
		&pss,
		query,
		v.tenantID,
		p.ID,
	); err != nil {
		return err
	}

その他やったこと

▶ tenantdbへのアクセスを減らすべくキャッシュ

https://github.com/patrickmn/go-cache
を利用
   	tenantCache      *cache.Cache
	playerCache      *cache.Cache
	competitionCache *cache.Cache // TODO:

控えめにリードスルー方式

▶ playersAddHandler bulk insertする

しゅっとやった

▶ リクエストごとにtenantdb connection確立が非効率。使い回せるように

やりきれなかった。

▶ competitionRankingHandler のN+1

player_scoreとplayerテーブルでjoin

▶ visit_historyのselect改善

visit_historyのレコード数が多いが、min created_atのみあればいいのでupsertにすることでがっつりレコード数減らせそう。40%の雑見積もりだったが結果約94%削除できてた

具体的にはplayer, tenant, competitionのprimary keyのテーブルを新規に作成してそこにupsertするように

既存のvisit_historyスキーマを変えるのは避けて別テーブルを作る方針で。オリジナルのテーブルをいじると、万が一この施策を捨てるとなった時にコードのリバートだけでは切り戻せないので

-- webapp/sql/101_visit_history2.sql 

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,
    `updated_at` BIGINT NOT NULL,
    PRIMARY KEY (player_id, `tenant_id`, `competition_id`),
    KEY (tenant_id, competition_id)
) ENGINE=InnoDB DEFAULT CHARACTER SET=utf8mb4;

INSERT INTO visit_history2
  SELECT player_id, tenant_id, competition_id, MIN(created_at) AS created_at, MAX(updated_at) AS updated_at FROM visit_history
  GROUP BY player_id,tenant_id, competition_id;

app側もupsertするよう修正

INSERT INTO visit_history2  (player_id, tenant_id, competition_id, created_at, updated_at) VALUES (?, ?, ?, ?, ?)
  ON DUPLICATE KEY UPDATE updated_at = ?;

レコード数を6%ほどに減らせた

-- before
mysql> select count(1) from visit_history;
+----------+
| count(1) |
+----------+
|  3224839 |
+----------+
1 row in set (0.28 sec)

-- after
mysql> select count(1) from visit_history2;
+----------+
| count(1) |
+----------+
|   218473 |
+----------+
1 row in set (0.06 sec)

17:40

最後、デバッグログ等々消して、追試、再起動試験等に備える
再度 sudo /usr/local/bin/isucon-env-checkerで確認しておく

終了

最終スコアは 7661でフィニッシュ

上位15%以内入れるかなぁといったところ。本戦出場にはほど遠い。。。

振り返り

  • クエリ発行時のファイルロックを解消できなかったのが敗因そう。そこにすべて律速していたと思われる
    • 全然CPU使い切れてなかった。
    • 後半のチューニングが限られたメトリクスのみを見て判断していた。計測大事
  • 最初に一回コードを全部見てから具体的な改善に取り掛かるほうがよかったかも。課題が発見しきれなかった、遅かった
  • サーバーを1台暇させてしまった。愚直でいいのでシャーディングしようと思いつつ手が回らなかった
  • SQLiteのチューニング、どうやるの?
  • docker剥がしすべきかどうか、判断しきれずそのままだった
  • MySQL移行しないという判断をして自チームとしては結果よかったと思う。他チームがどうだったか気になる
  • 大きな手戻りなくやれた。なるべくリバートしやすい形で改善を加える。初期データをいじらないで別テーブルを作る等

運営や他の参加者の皆様、お疲れ様でした!!

予選問題のベンチマーカーが公開されたら再チャレンジします!

作成者以外のコメントは許可されていません