作問のテーマ

今回の作問のテーマは「いろいろな解き方ができる問題」でした。
ISUCONの問題には、解消するべきボトルネックとなる要素が複数(意図的に作り込まれて)存在しています。基本的にはその時点で最大のボトルネックになっている要素を解消することでスコアが上がっていき、多くのボトルネックを解消するほどスコアが向上します。

つまりこれは初見のシステムに対して、ボトルネックをモニタリングやコードリーディングによって発見し、解消していくというゲームです。個人的には、これは運営が仕込んだ課題をどれだけ高速に発見できるかという謎解きになってしまうことがあるな、と感じる場面がありました。

限られた時間とコンピューティングリソースの制約がある状態で、競技として成立させるためにはある程度仕方ない面があるのですが、もう少しアーキテクチャの創意工夫ができる問題はできないか、と思ったのです。

筆者が過去の問題で一番好きなのは「ISUCON7 予選」です。お題は画像投稿ができるチャットアプリケーションで、画像配信の速度が最終的にスコアに効いてくる問題でした。その課題を解決するために、上位陣の取った戦略がバリエーションに富んでいたのが好きな理由です。

詳しくは ISUCON7予選の上位陣の戦略まとめ にまとまっていますが、アップロードされた画像をどのように複数台のホストで効率的に保存して配信するか、各チームがそれぞれの方法を考案していました。

• 画像ストレージをRedisにして3台に分散、アプリケーションで配信
• 画像を1台のWebDAVサーバーに集約して保存、配信
• 3台にロードバランスしてホスト名のprefixを付けてファイルに保存、他のホストからはprefixをみてnginx reverse proxyで配信
• 2台にロードバランスしてファイルに保存、nginxのtry_filesで自ホストに存在しない画像は他ホストを参照

ISUCONはプログラミング技術を競うだけのコンテストではなく、もっといろいろな解き方ができてほしい、という思いをこめて今回の問題を作問しました。

予選問題の概要 ISUPORTS とは

社内ISUCONが普及した現代では、より多くのISUCONの結果をまとめられる利便性の高いリーダーボードアプリケーションが求められています。そのようなニーズに対して、ISUPORTSでは、会社ごとに隔離された高品質なISUCONリーダーボードを提供しています。

ISUPORTSアプリケーションマニュアル より引用。

今回の問題は、以下の特徴を持つ「マルチテナントSaaSアプリケーション」がお題でした。

• 各テナントには、独立したホスト名(サブドメイン)が与えられ、ユーザーはそのホスト名でアクセスを行うことでテナントが識別される
  • 各テナントの参加者は、リーダーボードを閲覧できる
• 各テナントごとに管理者が存在する
  • 大会(社内ISUCON、という体裁)を開催/終了できる
  • 参加者の登録/失格処理が行える
  • CSVをアップロードすることで、リーダーボード(ランキング表)を更新できる
• SaaS管理者が存在する
  • テナントの追加、課金情報の閲覧ができる

また、技術的には、次の特徴がありました。

• 各テナントごとに1個、SQLiteのデータベースファイルが存在する
• それとは別に、テナントを管理するためのMySQLデータベースが存在する
• 認証はアプリケーション外部で実行されてJWTが発行され、クライアントはそのJWTをCookieヘッダで送信してユーザーを識別する

1つのシステムに複数個のデータベースが存在するという、これまでのISUCONに出題されたことがない形式になっています。 初期状態では100個のテナントがあるため、SQLiteのデータベースファイルも100ファイル存在していました。また、ベンチマークが実行されると新規のテナントが追加されるため、そのたびにデータベースファイルが作成されます。

問題に含まれる要素

すべてを解説していくと大長編になってしまうため、最初に今回の問題に含まれる主な要素を列挙しておきます。

• SQLiteのまま進める?　MySQLに移行する?
  • ISUCONの過去の経緯から、SQLiteよりはMySQLを扱い慣れている人が多い
  • SQLiteは1つのデータベースをネットワーク越しに他のホストから参照できないため、複数台(今回は3台)を簡単に使えるのはMySQL
  • しかしSQLiteのままでも、各テナントを複数台に分散配置できれば性能は上げられるはず
• SQLiteへ発行しているクエリのロギングと分析
  • アプリケーションでは環境変数を設定することにより、JSON形式(Rust実装を除く)でクエリログをファイルに出力できるようになっていた
  • このJSONにはクエリ、プレースホルダの引数、実行時間などが含まれる
  • dsq のような、JSONファイルに対してSQLできるツールを使うことで解析できる想定 (dsqは、内部でSQLiteが使われています)

    $ dsq trace.ndjson "select sum(query_time), avg(query_time), statement from {} group by statement order by sum(query_time) DESC limit 3" | jq -c .[] --sort-keys
    {"avg(query_time)":0.06336696733617025,"statement":"SELECT player_score.*, player.display_name FROM player_score JOIN player ON(player_score.player_id=player.id) WHERE player_score.tenant_id = ? AND competition_id = ? ORDER BY row_num DESC","sum(query_time)":476.51959436800036}
    {"avg(query_time)":0.006513457029783814,"statement":"SELECT * FROM player WHERE id = ?","sum(query_time)":164.23681900599885}
    {"avg(query_time)":0.0408031005297249,"statement":"SELECT * FROM competition WHERE tenant_id=?","sum(query_time)":45.98509429699996}
    

• 排他処理のためのファイルロック (flock) を解消できるか
  • なぜか初期実装はトランザクションという概念を知らない人が書いた(という想定)ので、アプリケーションの整合性を保つために排他ロックをしている
  • トランザクションを適切に使うことで、この排他ロックはなくせる
• 課金情報の計算が重いのを高速化できるか
  • SaaS管理者、テナント管理者がアクセスする課金情報は、MySQLとSQLiteの両方にアクセスして計算する
  • 正しい課金情報を返す必要があるのは大会が完了(finish)した後だけなので、その時点で確定値を計算して保存できる。アクセスのたびに都度計算する必要はない
• 一意IDの発行が重いのを高速化できるか
  • システム内で一意のIDを発行するために、MySQLのauto_incrementが設定されたテーブルに更新を掛けてIDを採番している
  • IDは文字列型なので、UUIDやULID、他にも一意になるような文字列であれば代用できる
• 各種N+1クエリ
  • SELECTだけでなく、大量の行を書き込むINSERTも1行ごとに発行されている
• 初期データに無駄が多い上に、書き込みが多発する
  • 課金計算のためのvisit_history (MySQL)
  • リーダーボードのためのplayer_score (SQLite)
  • これらのデータは、適切な処理で初期状態からcompaction可能
  • visit_historyの書き込みは削減可能
• 安全にキャッシュ可能なアプリケーションの制約を生かせるか
  • リーダーボードの情報はCSVのアップロードを契機に全行が更新され、それ以外では更新されない
  • 参加者情報はスコアのCSVのアップロードと、参加者の失格処理が行われた場合以外には更新されない
  • これらのエンドポイントは参加者が大量にリクエストするため、高速に返すことでスコアが伸びやすい
  • レギュレーション上、更新が行われるイベントが発生してから実際の情報が更新されるまでに3秒の猶予がある
• レスポンスにHTTP 429 (Too Many Requests) を返せるエンドポイントがある
  • テナントの追加と、大会の開催APIについては、429とRetry-Afterヘッダを返すことで、リクエストをその秒数だけ待ってからリトライさせることできる
  • 負荷が高すぎる場合の調整弁として使用可能
• ベンチマーカーの送信するリクエストの並列度が、初期状態で比較的高い
  • Go, Node, Rustなどデフォルト状態で並列処理が行いやすい言語と、Ruby, Perl, Python, PHPのようにPrefork型のアーキテクチャを採用している言語では、初期状態のスコアに差がある(前者が約2500、後者が約1500程度)
  • Prefork型のアーキテクチャを採用している言語では、メモリの許す範囲で30〜50程度までプロセス数を多くすることで、初期スコアが前者のグループに近くなる
• 初期実装は、アプリケーションのみDocker Composeで動作していた
  • MySQLやnginxはホストで通常のプロセスとして動作していた
  • 運営が、多数の言語に対して環境を用意する手間を省力化できる目的も

その他、nginxやMySQLの設定ファイルはUbuntu 22.04のデフォルト状態がほぼそのままであるとか、データベースに適切なインデックスが存在しない、などの定番要素もありました。

講評

まずアプリケーションを見て、SQLite???となった方が多かったようです。

テナントデータベース(SQLite)にはテナントごとの情報(大会、参加者、登録されたスコア)を保存する3テーブルがあります。それぞれのテーブルにはすべて tenant_id というカラムがあり、各テーブルのプライマリーキーには、システム全体で一意なIDが保存されています。
つまり、このテナントデータベースの行は、内容を変換せずにMySQLへ取り込むことができるようになっていました。

そこで、「あまり馴染みがないSQLiteではなく、MySQLに取り込んでからチューニングを行おう」と考えたチームも多かったようです。アンケートの結果では、半分ほどのチームが移行を検討したようです。

MySQLに移行する方法

ところが、初期状態のデータをいきなりSQLiteからMySQLに移行することはなかなか困難です。

競技用インスタンスには sqlite3-to-sql というコマンド(シェルスクリプト)が置いてありました。これは sqlite3 コマンドの .dump を用いた簡易的なもので、MySQLとPostgreSQLに取り込める形式に整形されたSQL文が出力されます。ただし、INSERT文がいわゆるバルクインサートではなく、1行につき1つのINSERT文が記述された形式です。

登録されたスコアを保存する player_score テーブルには、初期状態で(全てのテナントを合計して)370万行ほどが存在するため、1行ごとにINSERTでの取り込みを行うと、非常に時間が掛かる状態でした。おそらく、これですんなり移行できたチームは少なかったのではないでしょうか。

高速に取り込むためには、次のような工夫が必要になるでしょう。

• SQLiteからCSVで出力(.mode csv)してファイルに書き出し(.output filename)、MySQLではそのCSVを LOAD DATA によって取り込む
• SQLiteを読んでMySQLにバルクインサートするコードを書く
• 1行ずつINSERTするSQLをバルクインサート形式にテキストで整形する

更にISUCON特有の事情として、ベンチマーク開始時に /initialize というエンドポイントにアクセスが行われ、そこで初期状態(アプリケーション外部から観測できる状態)にデータを復元する必要があります。また、このエンドポイントは30秒以内に処理を終える必要もあります。

外部から観測できる状態さえ同一になっていればよいので、SQLiteからMySQLへのデータ移行を毎回行う必要はありませんが、移行した場合はMySQL上のデータをある時点に巻き戻す必要があります。

この復元処理はSQLiteの初期状態では、単なるファイルコピーで実現されていました。MySQLに移行した場合、この復元処理をどうやって解決するかもポイントになります。mysqldumpで取得した論理バックアップからの復元では、データ量的に30秒では処理できないサイズになるためです。

ここを解決したチームは、MySQLのデータベースディレクトリ(/var/lib/mysql)を丸ごとコピーしてMySQLを再起動する、などの方法を取ったチームがあったようです。Percona XtraBackup for MySQL Databases のように物理バックアップを取得するツールもありますし、高速にレストアするためには有効な方法です。

データベースを移行する、その前に

ここまで見てきたように、初期状態のデータをまるごとMySQLに移行するのは、高速に復元する要件を含めるとなかなか技術力が要求される作業となっていました。一般的に、既存のデータストアを移行するのは一筋縄ではいかないことが多く、ISUCONにおいても大改造の部類になります。初手から成功率の低い博打を打つことは、リスクが伴います。

アプリケーションをよく読んで、実際の挙動を観察することは、ISUCONでも現実でも大事です。ここからは、初期状態のアプリケーションにベンチマークを実行した結果から、どのようにチューニングするかを考えてみましょう。

visit_history の不要行削減

初期状態でベンチマークを行うと、MySQLのCPU負荷が高く観測されます。定番の手法ですがスロークエリーログを出力し、その結果を pt-query-digest などで解析すると、visit_history というテーブルへの次のクエリの読み取りが時間を消費していることが分かります。

SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history
WHERE tenant_id = 45 AND competition_id = '15a88ec1e' GROUP BY player_id

visit_history テーブルは初期状態で320万行以上ありますが、インデックスは tenant_id の1カラムしか存在しないため、読み取る行数が多い状態です。もっと効率がよいインデックスを作成することで、パフォーマンスを改善できます。

(tenant_id, competition_id) もしくは (tenant_id, competition_id, player_id) のインデックスを作ったチームが多いようでしたが、ここではクエリに必要な全てのカラムが含まれるCOVERING INDEXを作成することで、より効率的に処理できます。

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

このインデックスを作成すると、MySQLのCPU負荷が一気に下がります。ボトルネックはアプリケーション側(SQLiteの処理を含む)に移動しているので、この時点でSQLiteからMySQLへの移行を考えたチームもあったかもしれません。

しかし、ここでこのクエリを発行している部分のアプリケーションの処理をよく見ると、実は visit_history テーブルの行は「各テナント/大会/参加者につき、最初のアクセス時に作成される1行のみが必要」ということが分かります。集約クエリで MIN(created_at) を取得して、その値しか使わないためです。

つまりこのテーブルには大量に不要な行が含まれているため、次のようなクエリで不要な行を消し去ることができます。

CREATE TABLE visit_history_2 AS
SELECT tenant_id, player_id, competition_id, MIN(created_at) AS created_at FROM visit_history GROUP BY tenant_id, player_id, competition_id;
ALTER TABLE visit_history RENAME TO visit_history_old;
ALTER TABLE visit_history_2 RENAME TO visit_history;
CREATE UNIQUE INDEX visit_history_idx ON visit_history(tenant_id, player_id, competition_id);

MIN(created_at) の行だけを使って新しいテーブルを作成し、既存のテーブルと入れ換え、更にUNIQUE INDEX を貼ることができます。この処理を行うと、初期の320万行が20万行まで削減できます。

この visit_history へのINSERTはリーダーボードへの閲覧アクセス時に発生します。非常にリクエストが多いエンドポイントになるため、毎回INSERTする必要がなくなるのは嬉しいですね。

flock と player_score の更新をなんとかする

このアプリケーションはなぜか実装者にトランザクションの知識がない(という設定の)ため、データの整合性を保つためにアプリケーション上で排他ロックを行っています。排他ロックの実装は、大昔のWebアプリケーションを知っている方には懐かしの flock です。(Javaのみ、実装上の理由で synchronized でした)

コードには排他ロックが必要な理由を含めてコメントが書いてあります。

// DELETEしたタイミングで参照が来ると空っぽのランキングになるのでロックする
// player_scoreを読んでいるときに更新が走ると不整合が起こるのでロックを取得する

リーダーボードへの参照のように頻繁に呼ばれる処理で排他ロックしてしまうと、アプリケーションの性能(レイテンシ)に影響します。これをなんとかしましょう。

リーダーボードへの更新時は次の処理が行われます。

1. CSVファイルがアップロードされる
2. player_score テーブルをDELETEする
3. player_score テーブルにCSVの内容を1行ずつINSERTする

この2と3の間に player_score テーブルへの参照(リーダーボードのや課金への参照)が発生すると中途半端なデータが返ります。アプリケーション的には不正な状態となるため、ベンチマーカーがfailします。

player_score テーブルはSQLiteに存在しますが、当然ながらSQLiteでもトランザクションは使用できます。DELETEとINSERTを1トランザクションで実行すれば、排他のための flock を丸ごとなくすことができます。

さて、ここで player_score の処理と初期状態のデータをよく観察すると、アップロードされてくるCSVには無駄な行(同一の参加者の複数のスコア)が大量に含まれていることが分かります。

アプリケーションの仕様上、各参加者ごとにCSV内で出現する最後の行がリーダーボードで有効になるため、その1行のみを保存すれば十分です。

アプリケーションは、CSVを読みながら各参加者の最後の1行だけを覚えておき、INSERTするように変更できます。

初期データでは、各参加者について row_num が一番最大の行のみを抽出して、player_score テーブルを作り直すことができます。

CREATE TABLE player_score_tmp AS SELECT player_id, competition_id, MAX(row_num) AS row_num FROM player_score GROUP BY player_id, competition_id;
CREATE TABLE player_score_new AS SELECT player_score.* FROM player_score JOIN player_score_tmp USING(player_id, competition_id, row_num);
DROP TABLE player_score;
DROP TABLE player_score_tmp;
ALTER TABLE player_score_new RENAME TO player_score;
VACUUM;

この処理を行うことで、player_score テーブルは初期状態の全テナント合計370万行から、18万行程度に削減されます。パフォーマンスはもちろんのこと、データサイズが劇的に小さくなるのが重要です。

この状態であれば、1行ずつINSERTする sqlite3-to-sql でも数分でMySQLに取り込めます。/initialize での処理も、mysqldump の論理バックアップ復元で余裕を持って完了できます。

感想を拝見したところでは、この player_score のデータ削減処理に気が付いたチームはMySQL移行に成功したところが多く、気が付かずに初期データを全てMySQLに移行しようとしたチームは、成功させることが難しかったようです。(もちろん、そこを豪腕で解決したチームもありました)

このデータ削減が行えたかどうか、がMySQL移行を成功させられたかどうかの分岐点となったようです。

visit_history と player_score をコンパクトにできると、他にも嬉しいことがあります。テナント/大会/参加者単位で1行のみになるため、課金情報の算出やリーダーボードの生成に含まれるN+1クエリを容易に解消できるようになります。

MySQL 移行 vs SQLite のまま

MySQLへの移行に成功すると、アプリケーションサーバー2台とMySQLサーバー1台など、複数台構成によって性能を伸ばすことが容易になります。

しかし、SQLiteはシングルスレッド性能でMySQLよりも劣っているわけではないこと、ネットワークのレイテンシに影響を受けないこともあり、MySQLに移行したからといってそれだけで性能が上がるわけではありません。むしろ、移行直後にはN+1クエリのレイテンシの影響などで、スコアが落ちたチームもあったようです。
SQLiteのままで複数台に分散するためには、リクエストをテナント単位でそのテナントのデータベースファイルが存在しているホストに適切に振り分ける必要があります。また、課金処理は初期状態ではテナントデータベースを参照するため、この扱いも問題になります。
運営での事前検討では、テナントのデータを保持しているホストの対応表をRedisに保持しておき、nginx lua (OpenResty) によってホスト名から振り分け先を決める、などの手法も考案されていました。
取り扱いに慣れた人でないと時間内に実現することは難しいかもしれませんが、SQLiteのままでも複数台に分散することで、複数台の性能を十分に発揮させることは十分可能です。

データの更新タイミングが限定されていることを生かす

player_score のコンパクト化に気が付かなかった場合は、MySQL移行の難易度が上がります。しかし、その状態でもSQLite 1台構成のままでスコアを伸ばせるポイントはあります。

リーダーボードAPI (GET /api/player/competition/:competition_id/ranking) のレスポンス内容はCSVアップロード時にしか書き換わらないため、このAPIの結果はレスポンスを丸ごとRedisなどにキャッシュ可能です。CSVがアップロードされたタイミングでキャッシュをパージすれば、不整合も起こりません。

参加者API (GET /api/player/player/:player_id) のレスポンス内容に付いても以下の制約があるため、キャッシュを有効に利用できるエンドポイントになっています。

• その参加者が含まれるCSVアップロード時と、参加者の失格処理が行われた場合しか書き換わらない
• 失格処理後、情報が反映されるまで3秒の猶予がある

実際にSQLiteのままキャッシュを有効に利用して本選進出したチームも多かったようです。

課金情報については、デフォルトでは閲覧のたびに visit_history と player_score にクエリを発行して算出しています。しかし、アプリケーションの仕様として次の要素を考慮すると、大幅に処理を効率化できます。

• 大会が終了するまでは常に課金は0
• 大会が終了した時点で課金情報が確定し、その後は変更されない

大会の終了フラグが立つまでは一切計算せずに0を返し、終了API (POST /api/organizer/competition/:competition_id/finish) が呼ばれたタイミングで1回だけ課金情報を計算してMySQLのテーブルに保存するようなチューニングが可能となっていました。

予選突破相当の参考チューニング

Ruby実装、SQLiteのまま1台構成 (MySQLも同居) で、次の変更をして予選突破相当のスコア(24,000点)が達成できることを確認しました。

• puma worker 32 thread 1
• visit_history, player_score の行削減
• ID採番をUUIDに
• player_score をトランザクションで更新
• flock 削除
• ranking APIでN+1 (player) 解消
• CSVアップロード時のN+1 (player) 解消
• billing_reportをfinish時に計算してMySQLへ保存

まとめ

今回のテーマである「いろいろな解き方ができる問題」は、予選結果を見る限りある程度実現できたのではないか、と思っています。

実際に予選を突破したチームを見た限りでも、次のようなバリエーションがありました。

• SQLiteのままアプリケーションサーバー1台でチューニングを進めた
• データが削減できることに気が付いてMySQL移行成功、複数台を活用できた
• 削減はできなかったが高速にMySQLを復元することで移行を成功させた
• キャッシュを活用した
• 排他ロックをなくせた / そのままだった
• ID採番を変更した / デフォルト状態のままだった

昨年は本選進出したチームの使用言語がGo, Rust, Node.jsの3言語でしたが、今年はGo, Ruby, Node.JS, Rust, Perlと5言語に増えたのも嬉しいところです。
参考：ISUCON12 オンライン予選の利用言語比率 : ISUCON公式Blog

「予選にしては複雑すぎる！」という感想も聞こえてきました。実際に出題した側としても、これは本選向きなお題だなあとは認識していました。例年なら参加者のごくごく一部の本選進出チームしか味わえない、本選テイストのお題を味わえたということでご容赦頂けたらと思います。

今回の予選問題作問は、面白法人カヤック のチームでお送りしました。楽しんで頂けましたでしょうか。

• ベンチマーカー実装 temama
• Node.js移植、事前回答 acidlemon
• Go初期実装、Perl事前回答 macopy
• 総合プロデュース、競技環境、ポータル構築運用 fujiwara

それでは引き続き、ISUCON 12をお楽しみください！