予選の概要

今回の予選問題の内容についてはfujiwaraに解説を譲りますが、ざっくり言うとこんな感じでした。

• マルチテナントSaaS
• テナント管理用のDBはMySQLだが、テナントごとのデータは(なぜか)SQLiteのDBになっている
• 最初はSaaS管理画面の請求レポート画面がめちゃめちゃ重い
• ボトルネックを解消すると、どんどんテナントと参加者が増えてきてサービスが大繁盛する

この辺の話を踏まえて、さてどうやって解いていったらよかったのか、という話を書いてきます。

問題の中には、

• SQLiteのDBはテナントごとに別れているのになぜか全て tenant_id カラムがついている
• webapp/sql/ ディレクトリに sqlite-to-sql というスクリプトがそっと置かれている

といった状況があり、多くの人は「これはMySQLへの載せ替えを推奨しているのだな!」と思ったかもしれませんが、これはあくまでも「いろいろな解き方ができるようにしたいので、選択肢の一つとしてSQLite全廃して別のRDBMSに載せ替えるための手助けになるものを入れておいた」といった感じになっております。その辺はfujiwaraがたぶんなんか書いてくれるはずです。

ということで、今回の解説はSQLiteからMySQLへの載せ替えをやらずに3台構成にして10万点を出す方法、ということで解説してきます。縛りというわけでもないですが、Redisやプロセスオンメモリキャッシュを使わず、言語はNode.jsでやりました。多くの人が選択したGoでももちろん出来ますが、私Node.jsの移植者だったのでNode.jsでやりました。

いつもの感じの初動

さて、事前解答でやった順に解説していきますが、ベンチマーカーのシナリオデバッグとスコアリングの調整をするための事前解答だったのでスコアについては参考にならないため、「ちょっと伸びた」「大きく伸びた」くらいの表現に留まることを先にお断りしておきます。

adminDB visit_history にINDEXを張る

初期状態だとmysqlが大半のCPU時間を占めていて、調べてみるとvisit_historyにINDEXがないことが一因なのでここにINDEXを張ります。

ALTER TABLE visit_history ADD INDEX idx_all_cover
  (tenant_id, competition_id, player_id, created_at);

最後にcreated_atまで入れておくと、Covering Indexになるのでセカンダリインデックス単体でクエリを返すことができて高速ですが、created_atを張るのを忘れるとcreated_atを読むためにクラスタインデックスを読みに行くのでそこまで伸びない(もちろん張らないよりはマシ)といった感じです。私は最初created_atまで入れてなくて「アルェー」と言ってました。

Ranking APIが重いのでひとまずループクエリをなくす

mysqlがちょっと落ち着いたら、alpでリクエストごとの総レスポンスタイム(SUM)を見てみると、rankingが重いことが分かります。flockしているのも気になりますが、ロック区間内でループクエリが発生しているのがマズいので、まずはplayer_scoreを取るところにplayerをJOINして、retrievePlayerせずともdisplay_nameを取れるようにします。

SELECT player_score.*, player.display_name FROM player_score
  JOIN player ON player.id = player_score.player_id
  WHERE player_score.tenant_id = ? AND competition_id = ? ORDER BY row_num DESC;

スコアは…あがりませんでした。flockしてるので他の所も足を引っ張っていて全体が律速していそうです。

Score APIの追加のループクエリをなくす

rankingの次にレスポンスタイム合計が大きいのはscoreなので、ここにも手をつけます。scoreもflockがあり、ロック区間内で存在しない参加者かかどうかを確認するためのretrievePlayerのループ、scoreのDELETE、そしてscoreのINSERTループ、という感じでクエリがたくさん走っています。

この実装だと1件ずつ存在しない参加者チェックをしているかぎりループクエリをBulk INSERTにできない感じがしますが、基本的にこのアプリは4xxエラーでほとんどメッセージを返さないようになっているので「どのプレイヤーが見つからなかったか」を返す必要がありません(ログには書いていましたが)。

ということで、「CSVを全行チェックしてPlayerIdの重複ないリストを作る」→「それをSELECT COUNT(*) as count FROM player WHERE id IN (...) に渡してCOUNTに差分があるか確認する」という処理を追加すると参加者数チェックの部分は1クエリでできるようになります。INSERTするときはBulk INSERTで入れれば3クエリになります。

SELECT COUNT(*) as count FROM player WHERE id IN (...);
DELETE FROM player_score WHERE tenant_id = ? AND competition_id = ?;
INSERT INTO player_score (id, tenant_id, player_id, competition_id,
  score, row_num, created_at, updated_at) VALUES (...),(...)...;

flockしているところで一番大量にクエリが流れるのはこのscoreアップロードなので、ここのループクエリを減らすとスコアがちょっとあがります。ちなみに、flockで保護する必要があるのはDELETEとINSERTだけなので、SELECT COUNT(*) のところはflockの外に出しておくとさらにちょっとスループットがあがります。

アトミック書き込みのためのflockをトランザクションに変更する

flockは何のためにあったかというと、Score APIのCSV入稿でDELETEしてINSERTするという処理をアトミックにするためになぜかトランザクションをしらない人が作った、という設定でした。トランザクション張らずにflockを外すと、ベンチマーカーの整合性チェックフェーズで「同じscoreを2回入稿して2回目の入稿と同時にRanking APIを叩きまくっていて、DELETEとINSERTのスキマで99行くるはずのところがそれ未満しかこなくて「アトミックになってないぞ!」とエラーにするチェックが走っていて引っかかります。

ともあれ、Scoreの追加をBulk INSERTでやるようになってクエリ数も減ったことですし、DELETE-INSERTの部分をトランザクションにしてflockを外しましょう。残りの箇所はすべて読み取りのみなので、単純に外してOKです。

dispenseIDでMySQLを使うのをやめる

SQLite側のループクエリやflockをなんとかしても実はそこまでスコアはあがらなくて、もう一度全体の状況を計測してみると、mysqlのCPUがまだ高くて、slowlogで確認するとMySQLを使った発番の部分がめちゃめちゃボトルネックになっています。

発番についてはもともとdispenseIDで生成するのが整数値ではなく文字列値なので、比較的どんな形式でも受け入れるようにベンチマーク/フロントエンドは実装されていました。定番なのはUUIDとかULIDとかになるかと思いますが、普通に ${tenantId}-${unixepochnano} みたいな感じのいくつかのIDの文字列連結でも行けるようになっています。テナントIDを入れとくとベンチ落ちたときに調べやすいみたいなのはあるかもしれませんね。

とにかくMySQLが発番をする3箇所を全部ユニークかつMySQLに依存しない方法で発番するように変えてやれば、スコアが倍近くになるはずです。

adminDB visit_historyの初期データをコンパクトにする

MySQLに入っているvisit_historyデータは100テナントで322万行の巨大データですが、「アクセスをしたかどうか」だけがわかれば大丈夫というアプリケーションの作りになっているため、全件を保持しておく必要はありません。初期データ加工としてテナントID、大会ID、プレイヤーIDでGROUP BYして min(created_at) / min(updated_at)の値を1行とってきて入れ直すようにしてやれば20万行程度に減ります。私の場合は visit_historyと同じスキーマでvisit_history_tmpテーブルを作って一旦全データをそちらに移し、visit_historyテーブルに入れ直しました。これはアプリの中ではなくインフラ作業として行います。

insert into visit_history_tmp select * from visit_history;
truncate visit_history;
insert into visit_history select player_id, tenant_id, competition_id,
  min(created_at) as created_at, min(updated_at) as updated_at
  from visit_history_tmp group by player_id, tenant_id, competition_id;

dispenseID外しと、visit_historyのINDEX付与と、visit_history data compactionのこの3つをやると基本的にmysqlの負荷は大体1/10くらいになっているはずなので、ボトルネックはほぼすべてwebapp側になっているはずです。

Finish APIでBillingReportを生成する

3台構成の準備その1です。

この先、SQLiteのまま3台構成にしようとすると、テナントごとに1～3台目のどのサーバを使うかを固定してSQLiteのファイルが存在するサーバでそのテナントの処理が行われるようにする必要があります。その上で課題となるのは以下の様な感じです。

• nginxからテナントを考慮したwebappへのproxy_passをどうやるか
• /api/admin/tenants/billing は複数テナントにまたがってSQLiteにアクセスするためどうやってこのAPIを実装し直すか
• テナント追加はテナントのAPIではなくてadminのAPIであるため、どうやって新規テナントのDBファイルを適切なサーバに配置するか

MySQL全載せ替えをせずに3台構成をするにはここをどうにかしないといけないので、1個ずつ対応していきます。

今回の当日マニュアルにあった、「Finish APIを呼び出したあとにAdmin/OrganizerのBilling APIに結果が反映されるまで3秒の猶予がある」の意味は、「初期実装だとBilling APIで請求額を計算しているけど、大会ごとにfinishするときに大会の請求額が確定するので、BillingReportをそこで生成してストレージにいれてね!」です。

3台分散するときにネックとなる /api/admin/tenants/billing ではテナントDBを必要とする情報はテナントの請求総額のみなので、finishで作る大会ごとの請求情報をMySQLにつくるようにします。大会ごとの請求額は /api/organizer/billing のAPIでも必要となるため、billingReportByCompetition関数の戻り値の構造をそのままテーブルスキーマにしておきましょう。

CREATE TABLE `billing_report` (
  `tenant_id` BIGINT UNSIGNED NOT NULL,
  `competition_id` VARCHAR(255) NOT NULL,
  `competition_title` VARCHAR(255) NOT NULL,
  `player_count` BIGINT NOT NULL,
  `visitor_count` BIGINT NOT NULL,
  `billing_player_yen` BIGINT NOT NULL,
  `billing_visitor_yen` BIGINT NOT NULL,
  `billing_yen` BIGINT NOT NULL,
  PRIMARY KEY(`tenant_id`, `competition_id`)
) ENGINE=InnoDB DEFAULT CHARACTER SET=utf8mb4;

あとは、finishのときに billingReportByCompetitionを呼び出して、その結果をINSERTしてやればOKです。このとき、3秒も猶予があるので、レスポンスは先に返して請求情報の保存は非同期に行う事が出来ます。Node.jsならawaitせずにasyncでなげておくとか、Goであればgoroutineで投げっぱなしにする、などです。

このテーブルがあれば、AdminのBilling APIでは SELECT sum(billing_yen) as billing_yen FROM billing_report WHERE tenant_id = ? で請求総額をだせます。OrganizerのBilling APIでは SELECT * FROM billing_report WHERE tenant_id = ? AND competition_id = ? で大会ごとのBillingReportを作れます。行がない場合はまだfinishしてないということなので、大会IDと大会名だけ入れて残り0にしたレスポンスを作ればOKです。

このBillingReportは /initialize のたびにTRUNCATEして、初期データを入れ直したあとに全ての終了済み大会について billingReportByCompetition を実行してINSERTしなおす、という処理が必要です。毎回実行してもいいですが、 curlで /initialize だけ叩けばbilling_reportの初期データができているので、それをmysqldumpして次以降はそれを流し込む、で十分です。

これがきっちり炸裂すると、スコアがいきなり激増します。わたしが事前解答でやったときは開発中のベンチマークスコアが5倍になりました。

tenantDB player_scoreにINDEXをはる

ところでここまで実はSQLiteのDBスキーマになにも手を入れておらずでして、player_scoreにもなにもINDEXが効いていない状態でした。基本的にはプレイヤーごとにデータ集計することがあるので、player_idまではっておきます。

create index idx_score on player_score (tenant_id, competition_id, player_id);

初期データについては initial_data ディレクトリで for db in *.db; do echo "CREATE INDEX..." | sqlite3 $db; done とやってINDEXを適用して、さらにテナント新規作成したときにも効くように、tenantの10_schema.sqlにもCREATE INDEX文を追記しておきます。

これをやるとスコアが1.5倍くらいになりました。

Ranking APIでランキング集計するのをやめる

alpでみていくと、ranking APIの呼び出される回数とscoreが入稿される回数は10～20倍くらい差があります。rankingはscoreを入稿したときしか変わらないので、score入稿時にrankingの情報を生成してDBかなんかに入れておくと、/rankingのときには重いクエリを実行しなくてすみます。

CREATE TABLE ranking (
  `tenant_id` BIGINT UNSIGNED NOT NULL,
  `competition_id` VARCHAR(255) NOT NULL,
  `rank` INT NOT NULL,
  `score` BIGINT NOT NULL,
  `player_id` VARCHAR(255) NOT NULL,
  `player_display_name` TEXT NOT NULL,
  PRIMARY KEY (`tenant_id`, `competition_id`, `rank`)
) ENGINE=InnoDB DEFAULT CHARACTER SET=utf8mb4;

※rankっていうカラム名は予約語なのでお勧めしません…

MySQLにつくってもSQLiteに作ってもいいのですが、scoreが入稿されるたびにこのrankingテーブルは一旦DELETEしてBulk INSERTしなおさないといけないので、トランザクションしないと普通はデッドロックになります。ベンチマークは同じ大会にscoreを何度か入稿してきますが、scoreの件数は減らない(追記式のスコアデータがCSVとして何度も入稿される)というベンチマーカーの仕様があってそれを知った上であれば ON DUPLICATE KEY UPDATE を使って1クエリでいけるのでMySQLを使いました。もちろんトランザクションはってDELETE+Bulk INSERTでも大丈夫です。

Bulk INSERTとON DUPLICATE KEY UPDATEって併用できるんか? と思った方、私も同じ事をおもったのですが、ちゃんと方法あるようです。

INSERT INTO ranking (tenant_id, competition_id, \`rank\`, score, player_id, player_display_name) VALUES
  (?,?,....),(?,?,....).... 
  ON DUPLICATE KEY UPDATE score = VALUES(score), player_id = VALUES(player_id),
  player_display_name = VALUES(player_display_name)

VALUES(column) という関数がありまして、唯一の使い道が ON DUPLICATE KEY UPDATE 句でステートメントからカラムの値を参照できるぜ! なのだそうです。yokuさんの記事も参考までにどうぞ。

rankingテーブルもinitializeで作っておく必要があるので、1回つくってmysqldumpしてinitializeで流し込みます。

AddTenant APIでSQLite DBを作るのをやめる

3台構成準備のその2です。

1台構成であればAdminのAddTenant APIでSQLiteのDBを追加する、でよいのですが、上の方にも書いた通り3台構成にするとAdminのAddTenantをするサーバとテナントの処理サーバが一致していないとこの処理がうまくいきません。テナントのサブドメインはベンチマーカーから指定されるランダム文字列なので先頭文字を使って既存テナントと新規テナントを振り分けるみたいなこともできないためnginxが /api/admin/tenants/add を受け取ったときに適切なサーバに振り分けるのはなかなか難しい…ということで新規DB作成処理のタイミングを変えます。

まず、AddTenant APIでcreateTenantDB関数を呼び出すのをやめます。そして、テナントAPIに出てくるconnectToTenantDB関数の中でテナントのDBファイルが存在するかチェックして、なければcreateTenantDBを呼ぶという処理に変えると、nginxでテナントの振り分けさえ出来ていれば全てのSQLiteの処理は振り分けたサーバで行われるようになるので、3台構成が可能になります。

nginxで複数台に振り分ける

ここまでで Adminの2つのAPIはどちらもSQLiteのDBを読み書きしなくなったので、nginxからホスト名で分散できるようになっています。

どうやって分散するかはお好みで…といった感じですが、私は初期データのサブドメイン文字数とベンチマーカーが生成するサブドメインの文字数が結構違う(初期データは1～100の連番、追加データはUnixEpochが入るので数値の桁数が多い)というところに着目して、文字数ベースで振り分けを変えました。

たまたまですが、adminは5文字、データ量が桁違いにでかいISUコングロマリットはisuconなので6文字、ということで、nginxとmysqlが載っている1台目にadminとisuconを含む短い文字列のサブドメインがくるようにして、残りは2台目3台目、という構成にしました。何文字目で切るかは結構ちょいちょい負荷をみながらチューニングしていて、最終的には1～9文字、10～18文字、19文字以降、としています。ここは3台の負荷と、1台ごとのレスポンスタイムを眺めながら負荷が分散するように文字数をうまくチューニングしてください。CPU的には全部100%使えていても、2台目はRanking APIを0.5秒で返せているが3台目はRanking APIを返すのに1.8秒かかっている、みたいなケースがあります。

  location /api {
    proxy_set_header Host $host;
    proxy_read_timeout 600;

    if ($host ~ "^[a-z0-9-]{1,9}.t.isucon.dev" ) {
      proxy_pass http://127.0.0.1:3000;
    }
    if ($host ~ "^[a-z0-9-]{10,18}.t.isucon.dev" ) {
      proxy_pass http://server2;
    }
    if ($host ~ "^[a-z0-9-]{19,}.t.isucon.dev") {
      proxy_pass http://server3;
    }
  }

Admin Billing APIは最初めちゃめちゃ重いAPIでしたが、この時点でalpをみると0.1秒以内に返るめちゃ早いAPIになっています。今回のベンチマークシナリオはAdmin Billing APIが一周するとテナントを追加するみたいな感じになっていたので、ここまで高速化するとテナントの追加ペースとプレイヤーの増加ペースが大変なことになります。この辺から429の活用を検討してもいいかもしれません。

あと、/initialize は1台目固定にして、1台目と同じsqliteの初期化処理を2台目と3台目にもinit.shから実行する、というのをやるようにします。

ssh -o "StrictHostKeyChecking=no" 192.168.0.12 rm -f webapp/tenant_db/*.db
ssh -o "StrictHostKeyChecking=no" 192.168.0.12 cp -r initial_data/*.db webapp/tenant_db/

nginxをupstream keepaliveする

ここまでくると場合によってはめちゃめちゃ並列数が上がっていて、nginxが色々悲鳴をあげることがあります。nginxが悲鳴をあげると、ベンチマーカー側でread: connection reset by peer とか EOF とかが出るようになります(私も夜中にこれをみて悲鳴をあげました)。

現在のベンチマークでは、Ranking APIのレスポンスに1秒以上かかると参加者が帰っちゃうのでそこまでコネクションが爆増することはありませんが、開発中はその仕様がなかったため本当に数千コネクションくらい来て「さすがにこれしんどいっす」という話をしました。

nginxが悲鳴あげた場合は、以下のあたりを確認します。

• worker_connections: 768からもう少し上げる(一旦2〜3倍くらいに)
• worker_rlimit_nofile: worker_connectionsの4倍くらいを目安に設定する
• upstream keepaliveする
  • proxy_set_header Connection "";
  • proxy_http_version 1.1;
  • upstreamのkeepalive設定も多めに設定する(数十〜数百くらい)

これ以外だと http2_max_requests とかも確認した方がいいかもしれません。

MySQLをちょっとチューニングする

• binlogをオフにする (disable-log-bin = 1)
• Disk書き込みタイミングの調整 (innodb_flush_log_at_trx_commit = 2)
• BufferPoolのサイズ調整… メモリ3.7GBのインスタンスなので勢いよくデカくしてswap死しないように慎重に

あと、接続側のパラメータでコネクションプールのコネクション数を大きくするのもやっておいたほうがよいです。30～60くらいあれば余裕あるんじゃないでしょうか。Node.jsであれば dbConfigに connectionLimit: 30 を設定するとか、Goであれば adminDB.SetMaxOpenConns(10) のところを変更するか、とかです。

mysqld側がmax connection 151なので、立てるプロセス数とプロセスごとのコネクション数を計算して150以上になってたらmysqld側も設定変更する必要があります。

Player APIもなんとかする

あと大量に呼ばれるのは GET /api/player/player/:playerId でして、これもどうにかして高速化したいところ。正攻法としては Score入稿のAPIで先に1プレイヤー1行にする、なのですがなぜか事前解答中にわたしはそれが思いつかなかったので、とりあえず大会ごとにplayer_scoreをたくさん回したあとにさらに大会のtitleをとるループクエリは非効率でしょ…ということでplayer_scoreを大会ごとにとるところにcompetitionをJOINしてtitleも一緒にとれるようにだけしました。

SELECT player_score.*, competition.title FROM player_score
  JOIN competition ON competition.id = player_score.competition_id
  WHERE player_score.tenant_id = ? AND competition_id = ? AND player_id = ?
  ORDER BY row_num DESC LIMIT 1

ちなみに、大会ごとにplayer_scoreを取るのはさすがに非効率だからこのループクエリも潰そう! と思って1クエリで採る方法を模索したところ「なんでそのクエリがシンタックスエラーにならんのか」というような激ヤバクエリが出来あがりました。これでベンチマークも無事とおったのですが、スコアは上がらなかったので採用しませんでした。

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

このGROUP BYしてるのにSELECTに集計関数が全然並んでない感じ、私はMySQL5.6の頃を思い出して懐かしくなったのですがみなさんいかがでしょうか。集計関数なしでGROUP BYすると最初の1行が取り出されて結果として返ってくるようなのですが、MAX(row_num) と書いておくとその条件を満たす行で返ってくるのでループクエリにせずとも1クエリで全大会分取れるようです。

このクエリはMySQLではなくSQLiteで実行されるため、Player APIのように高頻度で流れるクエリでこういう長めのクエリを投げてしまうと、EXCLUSIVEロックを取るためにPENDING状態で待ってるクエリを結構待たせてしまうため、なんでもかんでもN+1を解消すればいい、というわけではないようです。1点のAPIが10点のAPIのクエリを邪魔してはいけない、ということですね。

その他細かいネタ

• Ranking APIはほとんどrankAfterパラメータをつけずにアクセスがくるので、Rankingテーブルを作る以上にトップ100のJSONを文字列化したもの、でMySQLにキャッシュしておいてrankAfterがなかったらその文字列を返す、とかやるともうちょっと早くなる場合があります

まとめ

…ということで、SQLiteを維持しつつ3台構成にする方法、についての解説でした。

オンメモリキャッシュなどを駆使するともっとスコアは伸びる可能性がありますし、Node.jsじゃなくてGoでやっていれば伸びる部分もあるでしょう。また、ここまで速くなった状態からのMySQL移植をすればスケーラビリティがさらにあがるかもしれませんね～。

今回の予選問題のリポジトリは今週中を目処に公開作業予定です。もう少しだけおまちください。

---

よくある質問と答え

Node.jsなのにNode Clusterしてないんですか?

今回CPUが2コアしかないマシンなので、Node.jsがIOを別スレッドに逃がしてくれるため十分スループットでている感じでした。一応Cluster入れたやつも試したのですがそこまで上がる感じはしませんでした。数%かな。

MySQLにもっていった人だとやった人多かったと思いますが、retrievePlayerをプロセス上にオンメモリキャッシュするという高速化のネタもありまして、Node Clusterにすると1テナントを2プロセスで捌くことになるのでそういうのが出来なくなってしまいますね(disqualifiedを捌くのは1プロセスだけなので、もう1つのプロセスはオンメモリキャッシュを更新できない)。その場合はRedisが必要になります(PerlやRubyなどのprefork型のサーバも同様です)。

retrievePlayerのオンメモリ化については、SQLiteを使ってる場合そもそもSQLiteがメモリに載ってればオンメモリキャッシュとさほど変わらないレベルの速度でplayerをとれる感じだったので、なくても10万点は行く感じでした(あってもそこまでスコア伸びなかったともいう)。

tenantDBを開きっぱなしにしたほうがスループットあがりそう

予選後にそういえばこれ開いたり閉じたりする必要無くない? とおもって試してみたのですが、Node.jsの実装だと逆にスコアが落ちました。SQLiteに詳しいわけでもないしNode.jsでISUCON解くのも初めてなのでまったくわからん… みたいな顔をしていました。テナントDB開きっぱなし実装にする場合、 /initializeで全部まとめて閉じる(それをちゃんと2台目3台目にも伝えて閉じさせる)必要があり、そのあとinitial_dataのコピーをしないといけないみたいなのもありますので、安易に突っ込むとハマりどころあるやつだと思いました。

SQLite関連でいくと、ジャーナルモードをDELETEからWALにするとか、同期モードをNONEにするとか、その辺も試してみたのですがスコアは下がるばかり…。今回 POST系が10点、GET系が1点というのがあり、Ranking APIとPlayer APIを高速化するとどんどん並列数があがってしまってPOST系のAPIが回りづらくなる、といった要素がもしかするとあったのかもしれません。