「The Tail at Scale」2013 Jeffrey Dean著　を読んでみた

目的

自分なりの考えや理解を整理することを目的とする。

「The Tail at Scale」これなに？

Googleの技術フェローが書いたGoogleの大規模分散システム運用で得られた知見を一般化した解説的・提言的な論文。

きっかけ

仕事でパーセンタイル（p50、p90など）を調べる機会があり、基準となる考え方を提示している有名な企業や団体がないかとChatGPTに尋ねたところ、この論文（The Tail at Scale）を紹介された。

要約とコメント

はじめに

何千台ものサーバーを横断して処理を行うような大規模オンラインシステムでは、わずかな一部の遅延（テールレイテンシー）が全体の応答性能を著しく低下させることがある。
ハードウェアの世界で、壊れやすい部品を組み合わせて信頼性の高いシステムを構築する「フォールトトレラントコンピューティング」を目指すように、大規模オンラインサービスも、個々のリクエストが予測不能であっても、全体としては予測可能で安定した応答を実現することが求められる。

Tips

まれな遅延でも大規模な分散システムでは全体の要求のかなりの部分に影響する。
大規模システムにおいてレスポンスの遅延変動(latency variability)を完全に排除するのは現実的でない。

なぜ変動性が存在するのか

ソフトウェア観点

• 共通リソースの競合：１つのマシン内でリクエストがCPUコア、メモリ帯域、ネットワーク帯域を奪い合う
• デーモン：OS内部でバックグラウンドで定期的に起動するデーモンが、スケジュールされたタイミングでCPUやI/Oを一瞬使う(hiccup)
• グローバルリソースの競合：複数マシンでネットワークススイッチや共有DBをめぐって奪い合う
• メンテナンス活動：アプリ内部でのバックグラウンド処理(GC機能の定期的なGCや定期的なログ圧縮)
• キューイングの多層化：多段階にまたがるネットワークスイッチと中間サーバーのキューイング

ハードウェア観点

• 消費電力制限：CPUが熱くなりすぎないように、電力制限によって動作クロックを下げる
• ガベージコレクション：SSDやストレージのガベージコレクション(掃除)
• 省電力モードからの遷移：省電力モード(スリープ)から移行すると遅延が増加

スケールで増幅される変動性

• 多くのサーバーに分散して処理することでサービス全体の遅延テールが拡大する。
• 1台ではごくまれ（p99レベル）の遅延でも、複数台のサーバーを使うとよき起きる遅延になる
  • 1台のサーバーで「1%の確率で遅くなる」場合(p99が1秒以上)
    • 「速いサーバーである確率」は 99%（=0.99）
    • 100台のうち、全員が速い確率は0.99¹⁰⁰ ≒ 0.366
    • つまり63%(0.643)の確率で遅いサーバーに当たる
    • 63%のリクエストが全体として1秒以上になる
  • 1台が「1万分の1の確率」で遅くなる場合（p99.99）
    • 2000台に同時アクセスするシステムだと
    • 1 - (1 - 1/10000)²⁰⁰⁰ ≒ 0.181　で　18%（ほぼ5件に1件） は遅延
• 実際にGoogle のあるサービスで測定した例では、単体サーバー 1 回の単独応答では 99パーセンタイルが 10 msであっても、サービス全体で99パーセンタイルが 140 ms になる

変動性の抑制する工夫

• レスポンス待ちの処理(インタラクティブ)と待ってない(バッチ)を混ぜずに、インタラクティブを優先する
• 超重い処理は割って、小さな処理に混ぜて実行する
• ログ集計、圧縮、GC、再インデックスなど本質的に“誰も待ってない”作業を、別資源か閑散時間に逃がしてピークを平らに
• キャッシュはp50~90には効くが結局、テール(p99)を直接縮めることはない。

遅延変動を受け入れて生きる

リクエスト内部の短時間スケールでの適応

リクエストが実行される過程で遅延が長くなりそうなものを検出して対策を打つ

• ヘッジドリクエスト：最初に応答が返ってきたものを使い他はキャンセル
• タイドリクエスト：サーバー間でキャンセル信号を共有し無駄な重複処理を抑える
  これらはテールの遅延が発生し始めた時点で代替経路を使うという暫定対策

リクエストをまたぐ長時間スケールでの適応

• マイクロパーティション：マシン内でデータ領域はるかに細かい単位で分割してパーテイションを割り当てることで負荷の偏りを細かく再配置できる
• 選択的レプリケーション：アクセスが集中しそう、遅延の偏りが起こりそうなパーティションに追加のコピーをつくり負荷を分散させる
• 遅延観測に基づくプロベーション：遅いノードを一時的に除外する。収まったら復帰させる

大規模情報検索(IR)システムでの工夫

• サーバーの応答が一定数戻ってきた時点で残りを待たずに応答を返している
• まずはごく少数の “カナリアサーバー” に試験リクエストを送り、問題なければ本番サーバーに送る

読み書し更新するシステム

これまでの工夫はRead系処理には有効だが、Write系はそもそもそんなに遅延に敏感ではないことが多い。レスポンスだけ返してあとから更新すればいい。

ハードウェア動向とその影響

• 今後のハードのサブミクロン化において、製造過程でのばらつきは将来的に増大する可能性ある
• ただしネットワーク帯域やオーバーヘッドの技術向上はテールを小さくするだろう

結論

• 将来の大規模かつ反応性を重視するクラウド／Webサービスにおいては、遅延変動を完全になくすことは実用的ではない。
• その代わり、尾部遅延を許容しつつもシステム全体として「予測可能で応答性のある挙動を維持する」ための設計が不可欠であり、これが “tail-tolerant” アプローチの本質である。

疑問・コメント

疑問

• 2013年の記事だけど、今も影響あるの？
• 物理マシンを直接束ねて分散システムを構築していた時代のシステム前提だけど、サーバレスやマネージドサービスを利用する現代だと、1台あたり遅延が...という議論はどうなるんだ？
  • A. 現代でも「依存サービス/APIのP99(Tail)の連鎖がシステム全体のSLOを左右する」という構造は同じ。
• 「各サーバーの 99 パーセンタイルが 1 秒（つまり 1% のリクエストが 1 秒超）。100 サーバーに分散して 1 回のリクエストで全 100 台に問い合わせる場合、少なくとも 1 台が遅い確率 = 1 - 0.99¹⁰⁰ ≈ 63%。。」：これクラウドサービスでもいえるのか？
  • A. 同一 Lambda 関数を複数組み合わせるシステム（例：API Gateway → Lambda → DynamoDB） になると、「tail の伝播」で合成的に p99 が悪化する

コメント

• 読めば当たり前じゃんと思うけど、読まないと気が付けない。レイテンシーの原因・対策について言語化されてまとまられてるのかも。
• 2013年なので言ってることがちょっと古い