2023.12.1 12:04 If-None-Matchについて追記
----
こんいすー こんいすー

ISUCON13 の作問チーム、さくらインターネット kazeburo です。
この記事ではISUCON13の問題となった「ISUPipe」について問題の解説と講評をします。
今年のISUCONではさくらインターネットが作問を行い、アドバイザーとしてfujiwaraさん、catatsuyさんにも参加いただきました。ありがとうございました。

「ISUPipe」とは

今年も素晴らしい動画を作成いただきました。動画再生が止まり、サービスに悪い影響がでてくる部分、動画とわかっていても心拍数があがってしまいます。



動画の内容にもあるとおり、ライブ動画配信サイトが今回のテーマです。

ただし、動画やサムネイル配信は作問チームのサーバから行い、競技の対象となるのはライブ動画配信サイトのAPIが主となっています。

ライブ動画配信サイト「ISUPipe」には配信者ごとにサブドメインが割り当てられ、テーマ設定ができ、各種の統計情報、ライブ配信に対するコメントや「チップ」投稿機能があります。

問題のレポジトリはこちらで公開しています。
https://github.com/isucon/isucon13

ISUCON13当日のマニュアルやアプリケーションの説明もレポジトリに含まれていますので、参照してください。

出題について

ISUCON13は、ISUCON2以来となる本選のみの開催となりました。ISUCON2では参加チーム数が25組と限られていましたが、今回は600チーム以上が参加しています。

こういった条件のもと、作問チームでは、優勝経験があるチームから初めてISUCONに参加するチームまで、さまざまな参加者にとって挑戦のしがいがあり、しかも順位をつけるための差がつきやすい問題であることが求められると考え作問にあたりました。

また、ChatGPTが登場して以降初めてのISUCONであることも今回の大きな特徴の一つです。AIの利用はソフトウェア開発においてすでに切り離せないものとなっており、ISUCONにおいても当たり前に使用できたほうがいいと考えました。そこで明確にレギュレーションに「開発において、AIを活用したコードの分析、生成等を利用しても構わない。」と記しています。

.dat チームのブログでは、AIがどう使われていたかについて説明があり、ここまでアプリケーションの全体が把握できるということは、作問担当としても驚きの内容でした。
ISUCON13にLLM活用担当で参戦しました - LayerX エンジニアブログ

問題解説

今回の問題には、主に以下の要素が含まれています
  • 配信の予約
  • 配信の一覧、タグを利用した絞り込み
  • 配信の再生開始、停止
  • ライブコメントおよびTipsの投稿
  • リアクションの送信
  • スパム投稿のモデレーション
  • 配信ごとの統計
  • 配信主ごとの統計
  • アイコンの配信

    • これらの機能のパフォーマンスのボトルネックの対応を行うことで、負荷が次々に移動していったのではないかと思います。

    ISUCON13のスコアは、リクエストを処理した回数ではなく、Tipsの投稿の合計です。ベンチマーカーはいくつものシナリオを同時に走らせていますが、そのうちTipsの投稿に辿り着くシナリオは限られており、HTTPリクエストの最適化がスコアに結びつきにくい場面もありました。

    インデックスの作成

    参照実装の初期状態では、データベース上のインデックスがこれでもかっ！というほど存在しておりません。

    データベースのプロファイリングを行い、インデックスを付与するのがどのチームにとっても最初のステップだったのではないかと思います。以下は追加検討するインデックスの一例です。負荷のかかり方により、全てのインデックスが必要となるわけではありません。
    mysql> alter table livestream_tags add index idx_livestream_id (livestream_id);
    
mysql> alter table livestream_tags add index idx_tag_id_livestream_id (tag_id, livestream_id);
    
mysql> alter table livestreams add index idx_user_id (user_id);
    
mysql> alter table icons add index idx_user_id (user_id);
    
mysql> alter table livecomments add index idx_livestream_id (livestream_id);
    
mysql> alter table themes add index idx_user_id (user_id);
    
mysql> alter table reactions add index idx_livestream_id(livestream_id,created_at);
    
mysql> alter table livestream_viewers_history add index idx_user_id_livestream_id  (user_id, livestream_id);
    
mysql> alter table ng_words add index idx_livestream_id_user_id (livestream_id,user_id);
    
mysql> alter table reservation_slots add index idx_end_at (end_at);
    
mysql> alter table livecomment_reports add index idx_livestream_id(livestream_id);

    初期スコアは言語によりブレがあり、3,000点前後ですが、インデックスを付与していくことで10,000点程度まで上昇します。

    ICONのハッシュ値計算

    スコアをあげていくためには N+1 の解消が必須ですが、その前に改善の妨げとなる ICON のハッシュ値計算の対応と、条件付きGETリクエストへの対応を行なってあるとよいかもしれません。

    キャッシュやユーザテーブルへの計算結果の格納などいくつかの手段がありますが、ここではトリガーを利用する例を紹介します。
    # iconsテーブルへのカラムの追加
    
mysql> ALTER TABLE icons ADD icon_hash VARCHAR(255) AFTER user_id;
    

    
# INSERT, UPDATE時のトリガーを設置
    
mysql> DELIMITER $$
    
CREATE TRIGGER update_icons
    
BEFORE UPDATE ON icons
    
FOR EACH ROW
    
BEGIN
    
SET NEW.icon_hash = SHA2(NEW.image, 256);
    
END
    
$$
    

    
mysql> DELIMITER $$
    
CREATE TRIGGER insert_icons
    
BEFORE INSERT ON icons
    
FOR EACH ROW
    
BEGIN
    
SET NEW.icon_hash = SHA2(NEW.image, 256);
    
END
    
$$

    fillUserResponse関数(Go言語の場合)でデータベースから画像の生データを受け取り、都度SHA256の計算を行なっているところを、こちらのカラムに変更することで負荷の削減と、次の作業がしやすくなります。

    icon_hashについてキャッシュを利用する場合、「iconが更新されてから2秒以内にicon_hashを反映すること」という条件がありますので合わせて確認しておきましょう。

    ICON画像が設定されてないユーザの場合、レポジトリ内のNoImage.jpgが使用されますが、こちらのハッシュ値はあらかじめ求めておき (
    d9f8294e9d895f81ce62e73dc7d5dff862a4fa40bd4e0fecf53f7526a8edcac0
    です) プログラム中ではこちらの値を使用すると計算を省くことができます。

    また、ICON画像は条件付きGETに対応しています。こちらは当日のアプリケーションマニュアルにも書かれていました。画像のハッシュ値をAPIのレスポンスとして返すことで、そのハッシュ値を元に 
    If-None-Match
    がついたリクエストをベンチマーカーが送ってくる仕様になっています。
    query := `SELECT icon_hash FROM icons WHERE user_id = ?`
    
iconHash := "d9f8294e9d895f81ce62e73dc7d5dff862a4fa40bd4e0fecf53f7526a8edcac0"
    
err := dbConn.SelectContext(ctx, &iconHash, query, userID);
    

    
// err処理省略
    

    
match, ok := c.Request().Header["If-None-Match"]
    
if ok && strings.Contains(match[0], iconHash) {
    
	return c.NoContent(http.StatusNotModified)
    
}

    If-None-Matchは前後に 
    "
    がついているので、削除するか文字列が含むかを調べることができる関数、メソッドを利用するとよさそうです。

    追記 2023.12.01 12:04
    If-None-Match はコンテンツをクライアントがすでに格納しているときに、その更新の確認を目的として、サーバがレスポンスを行った時の Etag の値をクライアントがリクエストに付与して、サーバ側でそれを比較することで 304 (Not Modified)などを返すこと等に使用されます。If-None-Matchには複数の値や弱いバリデータが含まれることもあり、上記実装はアドホックなものであり、一般的なサーバの実装としては必ずしも適切でない場合があります。
    ISUCON13のベンチマーカーはアプリケーションマニュアルにある動作を行なっています。

    N+1の対応

    SQLの実行結果に対してデータを付与していく 
    fill*Response
    (Go言語の場合)関数があり、何度も使われています。これらの中、さらにはそこから呼び出された関数の中でSQLが実行され、N+1 クエリとなっています。このようなパターンは過去のISUCONでも出題されていたかと思います
  • fillLivecommentResponse
  • fillLivecommentReportResponse
  • fillLivestreamResponse
  • fillReactionResponse
  • fillUserResponse

    • 各言語のProfilerやAPMなどを活用し、ボトルネックになっているであろう関数から改善していくことになります。N+1の解消方法は書籍「達人が教えるwebパフォーマンスチューニング: isuconから学ぶ高速化の実践」の中では
  • JOINクエリの利用
  • 別クエリーでのプリロード
  • キャッシュの利用
    • を紹介しています。

    その他の工夫

    その他負荷の要因になるポイントとしては「ユーザおよびライブ配信の統計情報」「NGワード登録時の過去のコメント消し込み」といったところがあります。

    こちらもN+1となっているクエリを1回のクエリ書き直したり、あらかじめ必要な計算を行なっておくテーブルを用意、あるいは無駄な処理を行わないようにするといった対応が必要となります。

    DNSの対応

    ISUCON13の参考実装では、Webアプリケーションの他にDNSという要素がありました。DNSはISUCONにおいて初めて登場になります。

    これまでのベンチマーカーは、ポータルで指定したIPアドレスに対して直接HTTPリクエストを送信していましたが、ISUCON13においては、IPアドレスで起動しているDNSサーバーで名前解決を行い、結果として得られたIPアドレスに接続します。

    DNSサーバーとしては MySQL をバックエンドとした PowerDNSがセットアップされています。こちらのMySQLでは一つスキーマをデフォルトから変更し、インデックスを削除した状態となっています。

    また、DNSには負荷走行中に「DNS水責め攻撃」がやってきます。DNS水責め攻撃ではランダムに生成したサブドメインにて大量の名前解決を行います。ランダムなサブドメインになるためDNSサーバーのキャッシュは有効に働かず、バックエンドのMySQLに負荷がかかっています。

    DNSサーバの対応としては、

  • 初期実装では各DNSレコードのTTLが 
    0
    で設定されているので、数値を大きくし名前解決結果をベンチマーク側でキャッシュさせる
  • PowerDNSのキャッシュ機能を有効にする
  • データベースに不足しているインデックスを付与する
  • アプリケーションのデータベースと分離する
    • のような対応が考えられます。

    水責めを緩和する方法として、次のようなことも考えられます。
  • DNSサーバを実装し、ユーザ名がDBになければゆっくりレスポンスをする、あるいはレスポンスをしない
  • dnsdist を導入し、NXDOMAIN(名前が見つからない場合)にゆっくりレスポンスをする、あるいはレスポンスをしないフィルタを導入する


    • ベンチマーカーの実装ではDNS水責めはratelimitがかけられ、一定以上の負荷がベンチマーカー、対象サーバーの双方にかからないようになっています。サーバの分離などで対応ができれば一旦は問題となりにくいのではなかったかと思われます。

    また、DNSではワイルドカード 
    *.u.isucon.dev
    を登録することもできます。ワイルドカードを使うことでユーザ登録時の 
    pdnsutil
    によるレコード追加をスキップすることができます。

    ただし、ワイルドカードがあると水責め攻撃の名前解決が成功し、スクレイピングを模したHTTPリクエストが増えるので、その対応も同時に必要になってしまいます。

    サーバ構成

    ISUCON13では参加者はすべてスペックが同じ3台のサーバが利用できました。

    おそらくDNSの負荷の大きい状態では、次のような使い方
    1. DNS と DNSのDB
    2. nginxとアプリケーション
    3. アプリケーションのDB
    DNSの対応ができれば
    1. nginx、DNS、DNSのDB
    2. アプリケーション
    3. アプリケーションのDB
    のような構成が考えられるかもしれません。

    講評と謝辞

    ISUCON13では優勝経験があるチームから初めてISUCONに参加するチームまで、さまざまな参加者にとって挑戦のしがいがあり、8時間やり込めることを目標に問題を作成してきました。

    参加者の方のブログを全て読ませて頂いていますが、それぞれのチームにとってよいチャレンジを行なって頂いたのではないかと思います。

    その中で上で紹介した .dat に加え、「INUCON 13(いい感じに猫を動かすコンテスト ワン!ミャ〜!)」のエントリーが大変興味深く読ませていただきました。

    ISUCON13にツールの力で勝ちたかった(mazrean) | 東京工業大学デジタル創作同好会traP

    アプリケーション開発においてはオブザーバビリティが重要となってきていますが、ISUCONにおいても参加者は高度なオブザーバビリティを駆使してやってきます。これからの作問はシナリオの分析までされる可能性があるということを念頭におきながら進めていくことになるのでしょう。

    最後に改めて、アドバイザーとして加わって頂いた fujiwaraさん、catatsuyさん、本当にありがとうございました。fujiwaraさんのコミット、catatuyさんのアドバイスがなければ、ISUCON13において参加者の皆様に楽しんでいただけるレベルまで達することはできませんでした。

    また、各言語の実装を担当して頂いた、kobakenさん、YutaUraさん、okashoiさん、eagletmtさん、pastakさん。短い期間での実装と、実装の問題点の指摘も含めてありがとうございました。

    LINEヤフーの941さん、Shoko Satoさんをはじめとする皆様。イベントに協力いただいた、スポンサー企業のみなさま、参加者の皆様、ありがとうございました。今後も参加者や様々な形でISUCONを盛り上げていきたいと考えてますのでよろしくおねがします。