※2021.09.18 18:44 MariaDBのDESC指定に関する記述を修正しました
---
こんにちは、ISUCON11 予選問題担当の Mahito です。
この記事では ISUCON11 予選問題であるアプリケーション「ISUCONDITION」について、問題の概要と想定した解法について解説を行います。なお、ISUCON11 予選問題の作問はNTTコミュニケーションズ株式会社 - kanataMahito東京工業大学デジタル創作同好会traP - eiyaoriberyohaヤフー株式会社 - okimototabuchi の7名で担当させていただきました。

ISUCONDITION とは

ISUCON11 予選問題は、ISU (問題ではイスをこう表現していたのでここでもそう表現します) が人々にとって大事なパートナーとして扱われる世界で、ISU から送られるデータを記録し、いつでも確認できるようにする ISUCONDITION という IoT サービスでした。
例年、本選では問題に関する動画が流れるのですが、今年は予選でも動画を作ってもらいましたのでぜひ御覧ください。


問題はこちらで公開しています isucon11-qualify

ISUCONの過去問にチャレンジするためのシンプルな環境構築にもすでにISUCON11の予選問題がありますのでご参照ください。

出題の意図

予選問題担当チームでは「教科書的な問題でありつつも、解きごたえのある問題」を目指して作問を行いました。
ISUCON は年々参加者が増えており、近年では歴戦の猛者だけでなく、数多くの初心者の方も参加されるようになっています。
そのため初心者でも手が動かせるよう、index が作成されていない、LIMIT が設定されていないなど、過去の ISUCON でも頻出の典型的なパターンで構成されていました。ただし、計測の大切さを伝えたいという思いもあり、典型的なボトルネックだからと むやみに改善を行ってもスコアが伸びない問題設計にしていました。
例年と違う要素として、予選では珍しい大量の書き込み処理と、書き込まれた分だけ重くなる表示処理をいかにパフォーマンスチューニングするかという要素も問題に取り入れました。処理のバランスを上手く調整する必要があり、技術が要求されるポイントとなっていたと思います。

ベンチマーカーの動き(配点、負荷のかけ方)

ベンチマーカーは、ISUCONDITIONのサービスコンセプト「ISUとつくる新しい明日」をもとに、ユーザと ISU がよい関係をつくるための動きを評価していました。具体的には、「ISU の状態が良いこと」、「ISU が送ってくるコンディションを多く処理できていること」が確認されると、高いスコアを出すようにしていました。この評価を実現するために、ベンチマーカーは以下の 3 つのロールを模してリクエストしていました。
  1. ISU としてコンディションを送信し続ける
  2. ユーザとして ISU を登録し、 3 種類の行動を ISU ごとに繰り返し続ける
    • まだ見ていない ISU のコンディションを確認する
    • コンディションレベルが悪い ISU について詳細を確認し、問題を改善する
    • グラフを見て ISU の状態を確認する
  3. 閲覧者としてトレンドを確認し続け、トレンドの変化に応じてユーザを増やす

直接の加点は 2 のユーザの行動で行っており、いずれかが詰まると次の行動に移るまでに時間がかかるため、スコアが伸び悩む仕組みになっていました。

アプリケーションの認証機能について

選手が問題として扱うアプリケーションは ISUCONDITION 1 つでしたが、これとは別に認証用に主催者側が管理するサーバーが存在していました。ISUCONDITION では認証用のサーバーで発行された JSON Web Token (JWT) を検証することをログイン処理としました。
問題検討段階ではアプリケーションに認証管理の機能をもたせる案もありました。しかし、不適切な認証管理の方法をパフォーマンスのために選択して欲しくなかったため、今回は認証管理の仕組みを外に出すことにしました。

問題の解説

予選問題は ISU から送られてくるコンディションの書き込み/読み込みをいかに捌くかが重要な問題でした。
isu_condition テーブルが大きなデータであり、かつ様々な箇所からアクセスされるため、ここを改善することがスコアに繋がります。

計測

ベンチマーカーを実行し計測を行うと、CPU が主なボトルネックということがわかります。
どのプロセスが CPU を使っているかを調べるには top コマンド等でリソース使用量の傾向を見つつ、言語別のプロファイリングツール (例. Go 言語の場合 pprof) を用いて行単位の CPU 時間を確認すると良いです。

実際の計測の結果から nginx、アプリケーション、DB のいずれもが CPU を使っているため、以下のことがわかります。
  • nginx の CPU 使用率が高いことから、非常に多くのリクエストが送られている
  • API 単位だと POST /api/condition/:jia_isu_uuid がボトルネックになっている
  • go 実装の場合、アプリケーションの CPU 負荷は DB 周りが支配的で、ロジック単体で重い部分は少ない

  • 以降では、これらの改善について解説します。

    isu_condition テーブルに index を貼る

    DB の改善です。初期状態では以下のようなクエリがボトルネックになっています。

  • SELECT * FROM `isu_condition` WHERE `jia_isu_uuid` = S ORDER BY `timestamp` DESC LIMIT N
  • SELECT * FROM `isu_condition` WHERE `jia_isu_uuid` = S ORDER BY timestamp DESC
  • SELECT * FROM `isu_condition` WHERE `jia_isu_uuid` = S AND `timestamp` < S ORDER BY `timestamp` DESC

  • isu_condition テーブルの検索がボトルネックになっているので、index を張りましょう。WHERE の jia_isu_uuid に対して index を張っても良いですが、ORDER BY まで含めて複合 index を張ると良いです。jia_isu_uuid は = でしか比較していないので、ASC, ASC で構いません。なお、MariaDBでは DESC の指定は意味がありません。ただし、不必要な index があると INSERT 時に index を計算する必要があり、POST /api/condition/:jia_isu_uuid が遅くなってしまうことに注意しましょう。
    また、アプリケーションマニュアルに記載がある通り、同一の ISU について、コンディションの timestamp が重複することはありません。そのため (
    jia_isu_uuid
    ,
    timestamp
    ) を複合 Primary Key に設定することで、より負荷を下げることができました。

    POST /api/condition/:jia_isu_uuid の改善

    今回の問題はこのエンドポイントをどうするかで決まるといっても過言ではありませんでした。
    このエンドポイントによる INSERT が DB の CPU 負荷の多くを占めます。

    まず目につくのは INSERT するレコード数と同じ数のクエリを発行している箇所です。
    ここのクエリは一度発行するだけで十分なので、bulk (batch) insert をするようにしましょう。

    また、INSERT するレコード数が非常に多いため Prepared Statement をアプリケーション側で処理することも有効です。さらなる改善として、アプリケーションマニュアルの記載から、コンディションの反映が遅れることをベンチマーカーは許容しているため、POST されたコンディションをキューに詰めるなどして、複数リクエストを跨いで纏めたコンディションを一定間隔で INSERT するとさらに速くなります。

    ボトルネックそのものはここですが、ここを改善しただけでは点数の直接的な要因である GET リクエストがまだ遅いため、あまりスコアは伸びません。

    クエリに limit をつける (GET /api/trend)

    index を張った後でも、GET /api/trend 内で呼ばれている以下のクエリが負荷の上位に来ています。
    SELECT * `isu_condition` WHERE `jia_isu_uuid` = S ORDER BY timestamp DESC
    この処理は最新の一件のみをレスポンスに用いるため、LIMIT 1 をつけて高速化することができます。

    クエリに limit をつける (GET /api/condition/:jia_isu_uuid)]

    同じように index を張った後でも、GET /api/condition/:jia_isu_uuid 内で呼ばれている以下のクエリが負荷の上位に来ます。
    SELECT * FROM `isu_condition` WHERE `jia_isu_uuid` = S AND `timestamp` < S ORDER BY `timestamp` DESC

    GET /api/condition/:jia_isu_uuid も LIMIT があるエンドポイントなので LIMIT をつけたいところですが、filter 条件(condition_level) があるため、単純に LIMIT を取ることはできません。
    POST /api/condition/:jia_isu_uuid で INSERT するタイミングで condition_level を計算し、WHERE で filter をかけられるようにすると、LIMIT をかけることができるようになります。

    condition_level が正規化されていない CSV 形式だったため、とりあえず改善しようとしたチームも多かったと思います。しかし速度の観点における問題点は正規化されていないこと自体ではなく、正規化されていないことにより上述のように LIMIT を取れないことでした。

    クエリに対する検索条件の追加 (GET /api/isu/:jia_isu_uuid/graph)

    これは他の改善を入れていくと目立つようになるボトルネックです。GET /api/isu/:jia_isu_uuid/graph は、クエリパラメータの datetime から 24 時間分のグラフデータを返すエンドポイントです。しかし、初期実装のクエリでは全区間のデータを取得しています。
    そのため、次のように WHERE に追加の条件を加えて範囲を制限することで改善ができます。
    SELECT * FROM `isu_condition` WHERE `jia_isu_uuid` = ? AND ? <= `timestamp` AND `timestamp` < ? ORDER BY `timestamp` ASC

    アプリケーション側のログ出力を止める

    上記の改善を入れて top を見ると、systemd-journal が CPU 使用率の上位に来るようになります。
    systemd-journal はログ周りを担当しているサービスです。
    これはアプリケーションがログを出力しすぎているということを表しているので、ログを出力しないようにしましょう。

    注意点として、POST /api/condition/:jia_isu_uuid において、リクエストを drop する際にもログを出力しています。
    この箇所での出力もかなりの件数があるので、ここも出力しないようにしましょう。

    複数台のサーバーを活用する

    以上まででいくつかの改善を入れてきましたが、1 台では限界があるため、複数台のサーバーを活用するようにします。
    一番変更が簡単な構成は、DB が 1 台でアプリケーションが 2 台の構成です。

    ISUの登録時に指定する
    target_base_url
    を変えることで、ISU のコンディション送信先を変えることができます。
    そのためアプリケーションサーバーの分割は、
    target_base_url
    を用いて、POST /api/condition/:jia_isu_uuid のみを受けるサーバーと、そのほか全てのリクエストを受けるサーバーに分割するのが簡単です。

    上記までの変更で、負荷が満遍なくかかるようになっているため、この変更で大きくスコアが伸びます。

    dropProbabilityを下げる

    初期状態では dropProbability を下げてもアプリケーションが負荷に耐えきれず、GET の処理をする余裕がないため得点が伸びませんでした。
    しかし、ここまでの改善で CPU に余裕が生まれ、dropProbability を下げても十分に GET の処理が行えるようになっています。

    dropProbability を下げることで、一日の中にあるコンディションの数が多くなり、グラフの確認による加点を大きくできます。

    go 実装の場合、ここまでで15 万点以上の点数が取れることを確認しています。

    GET /api/trendの改善

    GET /api/trend を改善することで新規ユーザの獲得を目指しましょう。
    アプリケーションマニュアルには
    ISUCONDITION に興味を持っている閲覧者は、トレンドの変化に注目しています。
    という記述があります。ベンチマーカーのシナリオとしては、トレンドの変化があると評判が良くなり、ユーザが増加するようになっています。

    このエンドポイントの特徴は、パラメーターも認証も一切無いことです。一度レスポンスを計算したら、そのデータをキャッシュしておき、全てのリクエストに対してそのデータを返すことができます。
    ただし、閲覧者は変化に注目しているので、常に同じものを返すことはユーザの増加に繋がりません。定期的に更新するような処理を入れると良いでしょう。

    この改善を入れた場合、ユーザと ISU が増えリクエスト数が急増します。そのため、大量のリクエストを捌くような修正を入れないとスコアは下がります。特に、ファイルディスクリプタ数の上限を増やすなど、nginx、アプリケーション、DB の各種 limit パラメーターを緩和しないとエラーが出て fail することがあります。

    timeout ではなくてもレスポンスタイムが遅い場合は、その分だけユーザが閲覧できるページ数が少なくなります。状況に応じて、trendの更新頻度を下げたり、dropProbabilityを上げたりすることで負荷を絞り、レスポンスタイムを速くすることも得点を稼ぐためには重要でした。

    クライアントキャッシュを利用する

    ユーザ数の増加により、静的ファイルや icon の取得コストが目立つようになってきます。
    これらのファイルに対しては 304 Not Modified を返すことで、負荷を下げることができます。
    さらに、作成後は内容が変更されないため、Cache-Control に max-age を設定しリクエスト自体を減らすこともできます。

    その他のチューニングポイントとなり得る箇所

  • nginxの
    worker_connections
    を増やしたり、unix domain socket を使うようにする
  • そもそもnginxを使わず、直接アプリケーションと通信させるようにする
  • DB テーブルを分割する

  • などといった戦略も取れました。

    go 実装の場合、ここまでで65 万点以上の点数が取れることを確認しています。

    点数が上がるまでチューニングポイントとなり得ない箇所(isu テーブル)

    isu テーブルは、ユーザ数が増加しない限りは 100 件ほどのデータしか存在しません。isu テーブルには image カラムがあり ISU の画像が入っていましたが、件数が少ないためあまり負荷になっていませんでした。

    競技時間中は、手間をかけずに行える変更に留めておくことが予選問題担当チームの想定でした。
    isu の SELECT は
    SELECT *
    というように画像データまで取得するクエリが多くありました。ここで image を取得しないように修正すると、あまり手間をかけずに DB との通信量を減らすことができます。
    これは INVISIBLE COLUMNS を使って、1行で実現することもできました。

    講評

    今回の予選問題に含まれるボトルネックは典型的なパターンが多く、どこを直せばいいか全く分からない、ということは少なかったのではないかと思います。一方で、目についた典型的なボトルネックをとりあえず直したもののスコアが改善しなかった、という経験をした方も多かったのではないでしょうか。「推測するな、計測せよ」といわれる通り、Webパフォーマンスチューニングでは、改善に先立って、計測に基づいてボトルネックを特定することが極めて重要です。改めて「推測するな、計測せよ」という金言について、その重要さを確認する機会になればと思います。

    また、write upを拝見していると、高得点を得たチームには「まずはボトルネックになっているコンディションに集中している」「複数台に負荷を分散している」といった特徴がありました。今回の問題である ISUCONDITION というサービスは、センサーデータ(ISU からのコンディションの送信)を捌くことに重点を置いていました。そのサービスの性質を理解していると、この発想に至りやすかったと思います。

    謝辞

    主催並びに会場を提供してくださった LINE 社の皆様、アドバイザリーとして様々な助言をくださった白金動物園の皆様、問題を解いてフィードバックをくださった皆様、参考実装を別のプログラミング言語に移植してくださった移植者の皆様、スポンサーとして ISUCON11 を盛り上げて頂いている皆様、そして予選に参加していただいた選手の皆様に感謝申し上げます。本当にありがとうございました。