> [!abstract] 概要 > レイテンシばらつきを許容するソフトウェア技術は、応答性の高い大規模 Web サービスを構築するうえで不可欠である。 ## 論文情報 - タイトル: The Tail at Scale - 著者: Jeffrey Dean ([email protected]、Google Fellow, Systems Infrastructure Group)、Luiz André Barroso ([email protected]、Google Fellow、コアコンピューティングインフラのテクニカルリード)。所属はいずれも Google Inc., Mountain View, CA。 - 媒体: Communications of the ACM(CACM), Vol. 56, No. 2, pp. 74–80(2013年2月) - DOI: 10.1145/2408776.2408794 ## 概要 大規模分散システムでは、個々のコンポーネントのレイテンシばらつきがサービス全体のレイテンシに増幅されて現れる。本論文は、この現象を「フォールトトレラント」になぞらえて「tail-tolerant(テール耐性)」と呼び、原因の分類と、within-request(リクエスト内・即応)技術・cross-request(リクエスト横断・長期適応)技術の 2 種類の緩和技術を整理する。 ## 問題設定 大規模 Web サービスは、数千台のサーバに分散したマルチテラバイト規模のデータセットを参照しながら、100ms 以内の応答というユーザー体感上の「流動的」な応答性を実現する必要がある(Source: 本文 p.74)。個々のコンポーネントは平均的には高速でも、稀に大きなレイテンシを示すことがあり、リクエストがルートから多数のリーフサーバへファンアウトして結果をマージする構成では、この稀な高レイテンシが全体のレイテンシ分布を支配するようになる。 ## 提案手法 ### レイテンシばらつきが生じる要因 - **共有リソース**: 同一マシンを複数アプリケーションが共有し、CPU コア・プロセッサキャッシュ・メモリ帯域・ネットワーク帯域を奪い合う。同一アプリケーション内でも複数リクエストがリソースを奪い合う。 - **デーモン**: バックグラウンドデーモンは平均的には少量のリソースしか使わないが、スケジュールされたタイミングでミリ秒単位のヒッチを生む。 - **グローバルリソース共有**: 異なるマシン上のアプリケーションがネットワークスイッチや共有ファイルシステムなどのグローバルリソースを奪い合う。 - **メンテナンス活動**: 分散ファイルシステムのデータ再構築、BigTable のようなストレージシステムの定期的なログコンパクション、ガベージコレクション言語での定期 GC が周期的なレイテンシスパイクを起こす。 - **キューイング**: 中間サーバやネットワークスイッチの多層キューイングがこのばらつきを増幅する。 - ハードウェアトレンドによる増幅要因として、電力上限による一時的なサーマルスロットリング、SSD のガベージコレクション(書き込み負荷が中程度でも読み取りレイテンシが最大100倍に悪化しうる)、省電力モードから活性状態への遷移レイテンシを挙げる(Source: 本文 pp.75–76)。 ### コンポーネントレベルのばらつきがスケールで増幅される仕組み 大規模オンラインサービスの一般的なレイテンシ削減手法は、サブオペレーションを多数のマシンに並列化することである。各サーバが典型的には 10ms で応答するが 99 パーセンタイルレイテンシが 1 秒であるようなシステムを考えると、単一サーバで処理される 1 ユーザーリクエストのうち 100 件に 1 件が 1 秒かかる。100 台のこのようなサーバから並列に応答を集める場合、63% のユーザーリクエストが 1 秒を超える。1 台あたり 10,000 件に 1 件しか 1 秒超のレイテンシが起きない場合でも、2,000 台構成のサービスではおよそ 5 件に 1 件のユーザーリクエストが 1 秒を超える(Source: 本文 p.76, Figure「Probability of one-second service-level response time」)。 **Figure: システムのスケールとサーバレベル高レイテンシ外れ値の頻度に応じた、サービスレベルで1秒を超える応答時間の確率** ![[_attachments/TheTailAtScale/fig01-latency-vs-fanout.png]] (サーバレベルで 1 秒超のレイテンシが「1 in 100」の頻度で起きる場合、100 台構成でサービスレベルの 1 秒超確率は 0.63 に達する(グラフ中「×」)。「1 in 10,000」の頻度でも、2,000 台構成では確率が 0.18 に達する(グラフ中「○」)。横軸はサーバ台数、縦軸は P(service latency > 1s)。Source: 本文 p.76 の図(著者アダプト元は本論文自身)。) 実際の Google サービスの計測例(Table 1)では、ルートサーバが中間サーバを介して非常に多数のリーフサーバへリクエストを分配する構成で、単一のランダムなリーフリクエストが完了するまでの 99 パーセンタイルレイテンシはルートで測定して 10ms だが、全リーフリクエストが完了するまでの 99 パーセンタイルレイテンシは 140ms、95% のリーフリクエストが完了するまでの 99 パーセンタイルレイテンシは 70ms である。つまり、最も遅い 5% のリクエストを待つことが、全体の 99 パーセンタイルレイテンシの半分を占める(Source: 本文 p.76)。 **Table 1: 大規模ファンアウトサービスツリーにおける個別リーフリクエストの完了時刻(ルートノードから測定)** | | 50%ile latency | 95%ile latency | 99%ile latency | |---|---|---|---| | ランダムな1つのリーフが完了 | 1ms | 5ms | 10ms | | 全リーフリクエストの95%が完了 | 12ms | 32ms | 70ms | | 全リーフリクエストの100%が完了 | 40ms | 87ms | 140ms | (Table 1. 出典: 本文 p.77。) ### within-request(リクエスト内・即応)適応技術 数十ミリ秒の時間スケールで働く技術。読み取り専用・疎な一貫性のデータセットに対して有効。 - **ヘッジリクエスト(hedged requests)**: 同じリクエストを複数のレプリカへ送り、最初に応答が返ってきたレプリカの結果を使い、残りをキャンセルする。素朴な実装は許容できない追加負荷を生むが、最初のリクエスト送信後に一定時間待ってから 2 つ目を送る変種であれば、負荷増加を抑えつつレイテンシ削減効果の大半を得られる。1,000 台の BigTable から 1,000 キーの値を読み取る Google のベンチマークでは、10ms の遅延後にヘッジリクエストを送ると、追加負荷はわずか 2% で、99.9 パーセンタイルレイテンシが 1,800ms から 74ms に短縮された(Source: 本文 p.77)。 - **タイドリクエスト(tied requests)**: クライアントが同一リクエストを 2 台の異なるサーバへ「タグ付け」して同時送信し、実行が始まったサーバから相手サーバへキャンセルメッセージを送る。両サーバのキューが空の場合に両方が実行を開始してしまう「一次ウィンドウ」問題を避けるため、平均ネットワークメッセージ遅延の 2 倍(現代のデータセンターネットワークで 1ms 以下)だけ 2 つ目のリクエスト送信を遅らせる。Google のクラスタレベル分散ファイルシステムでの実装では、1ms 後にクロスサーバキャンセルするタイドリクエストが、アイドルに近いクラスタで中央値レイテンシを 16% 削減し、99.9 パーセンタイルレイテンシを約 40% 削減した(Table 2)。ディスク使用率へのオーバーヘッドはいずれのシナリオでも 1% 未満(Source: 本文 pp.77–78)。 **Table 2: BigTable サービスベンチマークで観測された読み取りレイテンシ** | | アイドルに近いクラスタ・ヘッジなし | アイドルに近いクラスタ・1ms後にタイドリクエスト | 並行terasort実行中・ヘッジなし | 並行terasort実行中・1ms後にタイドリクエスト | |---|---|---|---|---| | 50%ile | 19ms | 16ms (−16%) | 24ms | 19ms (−21%) | | 90%ile | 38ms | 29ms (−24%) | 56ms | 38ms (−32%) | | 99%ile | 67ms | 42ms (−37%) | 108ms | 67ms (−38%) | | 99.9%ile | 98ms | 61ms (−38%) | 159ms | 108ms (−32%) | (Table 2. 出典: 本文 p.78。) - **サービスクラスの差別化と上位レイヤキューイング**: 対話的リクエストを非対話的リクエストより優先してスケジュールする。低レベルキューを短く保ち、上位レベルのポリシーが速く効くようにする。Google のクラスタレベルファイルシステムのストレージサーバは、OS のディスクキューにわずかな未処理オペレーションしか残さず、独自の優先度付きキューでバッチ処理より対話的リクエストを優先させている。 - **head-of-line blocking の削減**: 長時間実行のリクエストを小さなリクエスト列に分割し、他の短時間リクエストの実行をインターリーブさせる。Google のウェブ検索はこの time-slicing により、少数の計算コストが高いクエリが多数の安価な並行クエリにレイテンシを付加するのを防いでいる。 - **バックグラウンド活動の管理と同期的な妨害**: ログ指向ストレージシステムのログコンパクションやガベージコレクション言語の GC 活動のように大きな CPU・ディスク・ネットワーク負荷を生むバックグラウンドタスクに対し、スロットリング・重い処理の細分化・負荷の低い時間帯での実行という組み合わせが有効。ファンアウトが大きいサービスでは、多数マシン間でバックグラウンド活動を同期させ、短時間の一斉負荷バーストに集約する方が、非同期に少数マシンが常にバックグラウンド活動をしている場合よりレイテンシテールへの影響が小さい。 - キャッシングはテールレイテンシに直接効かない。ワーキングセット全体がキャッシュに収まることが保証される構成を除き、キャッシングはこの議論の対象外である(Source: 本文 p.76)。 ### cross-request(リクエスト横断・長期適応)技術 数十秒〜数分の時間スケールで働き、粗粒度の現象(サービス時間のばらつき・負荷不均衡)によるレイテンシばらつきを緩和する。 - **マイクロパーティション**: マシン数より遥かに多いパーティション数を生成し、パーティションを動的にマシンへ割り当て・負荷分散する。BigTable は 1 マシンあたり 20〜1,000 個のタブレットを管理する。マシンあたり平均 20 パーティションであれば、約 5% 刻みで負荷をシェッドでき、故障復旧も高速化する(多数のマシンが 1 単位の作業を分担して引き受けるため)。 - **選択的レプリケーション**: 負荷不均衡を起こしそうなアイテムを検知・予測し、追加レプリカを作る。Google のメイン Web 検索システムは、人気・重要なドキュメントを複数のマイクロパーティションに追加コピーするほか、クエリ言語の混在に応じて言語別マイクロパーティションのレプリケーションを調整する。 - **レイテンシ起因の保護観察(latency-induced probation)**: 中間サーバがマシンごとのレイテンシ分布を観測し、特に遅いマシンをサービスから除外(保護観察)する一方、shadow リクエストを送り続けて統計を取り、問題が解消したら再度組み込む。負荷の高い期間にサービス容量を除去することで逆にレイテンシが改善するという、やや特異な状況。 ### 大規模情報検索(IR)システム向けの技術 - **good enough**: 十分な割合のリーフサーバが応答した時点で、わずかに不完全な結果をより良いエンドツーエンドレイテンシと引き換えにユーザーへ返す。個々のリーフサーバが最良の結果を持つ確率は 1,000 クエリに 1 回未満で、重要ドキュメントの複製によりさらに低い。広告やスペル修正のような非本質的サブシステムをタイムアウト時にスキップする用途にも使われる。 - **カナリアリクエスト**: 数千台のリーフサーバへ即座に送る前に、まず 1〜2 台のキャナリアサーバへ送り、成功応答が得られてから残りへ展開する。未テストのコードパスを踏んだリクエストが数千台で同時にクラッシュ・長時間ハングを引き起こす相関クラッシュシナリオや、悪意あるサービス拒否攻撃への頑健性を提供する。Table 1 の最初と最後の行を比較すると分かるように、単一サーバの応答を待つだけなので追加レイテンシはわずかである。 ### ミューテーション(状態変更)への適用 上記技術の多くは状態を変更しない操作に主眼を置くが、変更操作への適用は次の理由でむしろ容易: (1) レイテンシクリティカルな変更の規模は一般に小さい、(2) 更新はしばしばクリティカルパス外(ユーザーへの応答後)で実行できる、(3) 多くのサービスは非一貫な更新モデルを許容できる。一貫した更新が必要なサービスで最もよく使われる技術は quorum ベースのアルゴリズム(Lamport の Paxos など)で、これらは 3〜5 個のレプリカへのコミットで済むため本質的に tail-tolerant である(Source: 本文 p.79)。 ## 新規性 フォールトトレラントコンピューティングは「故障のない動作を保証する」ことがシステム複雑性の増大とともに非現実的になったために発展した。本論文は同様の論理を latency に適用し、「レイテンシばらつきの全原因を排除する」ことも大規模・共有環境では非現実的だと位置づけたうえで、根本原因を問わず遅延ヒッチを緩和する tail-tolerant 技術群を提示する。既存のフォールトトレランス目的で確保済みのリソース(レプリカ等)を tail-tolerant 技術が転用できる場合が多く、追加オーバーヘッドが低く抑えられる点を新規性として強調する(Source: 本文 p.80)。 ## 実験設定 論文自体は単一のベンチマークスイートというより、Google の複数の実運用システム(BigTable 上の読み取りベンチマーク、クラスタレベル分散ファイルシステム、大規模ファンアウトを持つ検索システムのログ計測)からの実測値を報告する形式を取る。データは Google の本番/準本番クラスタでの計測であり、比較対象は「ヘッジ/タイドリクエストなし」のベースライン、評価指標は 50/90/95/99/99.9 パーセンタイルレイテンシ。 ## 実験結果 - 1,000 台の BigTable から 1,000 キーを読む際、10ms 遅延ヘッジリクエストで 99.9 パーセンタイルレイテンシが 1,800ms → 74ms(追加負荷 2%)。 - タイドリクエスト(1ms 後にクロスサーバキャンセル): アイドルに近いクラスタで 99.9 パーセンタイルレイテンシが 98ms → 61ms(−38%)、並行 terasort 実行中でも 159ms → 108ms(−32%)とほぼ同等の改善率を維持(Table 2)。 - ファンアウト実験(Table 1): 単一リーフの 99 パーセンタイルレイテンシ 10ms に対し、全リーフ完了までの 99 パーセンタイルレイテンシは 140ms。95% のリーフが完了するまでの 99 パーセンタイルレイテンシは 70ms であり、最後の 5% を待つコストが全体の半分を占める。 - 理論上のスケーリング(Figure): サーバレベルの高レイテンシ頻度が「1 in 100」なら 100 台構成でサービスレベル 1 秒超確率が 0.63、「1 in 10,000」でも 2,000 台構成で 0.18 に達する。 ## 考察 タイドリクエストの効果が「アイドルに近いクラスタ」と「並行 terasort 実行中」でほぼ同じ改善率になった点について、著者らはレイテンシの原因が特定のリクエスト固有ではなく他の干渉によることが多いためだと説明する。これはタイドリクエスト・ヘッジリクエストのような「原因を問わない」緩和技術が、負荷が高く複雑な環境でも安定して効くことを示す実例である。また、事前にリモートキューの長さを確認してから最も空いているサーバへ送る「probe-then-request」方式は、probe と request の間の負荷変化・サービス時間推定の困難さ・全クライアントが同じ最空きサーバに殺到するホットスポット生成という 3 つの理由で、2 つのキューへ同時送信する方式より効果が薄いと論じる。 ## 強み / 弱点・課題 - **強み**: 単一の技術ではなく、原因の分類(共有リソース・デーモン・キューイング・ハードウェアトレンド)と対応技術群(within-request/cross-request)を体系的に整理し、既存のフォールトトレランス用リソースの転用によって低オーバーヘッドを実現できることを実測で裏付けている。BigTable・クラスタファイルシステム・検索システムという複数の実運用システムでの計測に基づく点も強み。 - **弱点・課題**: ヘッジリクエスト・タイドリクエストなどの技術は「レイテンシばらつきの原因が複数のリクエストレプリカへ同時に相関して影響しない」ことを前提としており、著者ら自身も本文でこの前提を明示している(Source: 本文 p.77「effective only when the phenomena that causes variability does not tend to simultaneously affect multiple request replicas」)。相関した障害・輻輳には効果が限定される可能性が高い。また、より積極的なヘッジリクエスト利用には高速なリクエストキャンセルが必要と述べるにとどまり、具体的な実現方式には踏み込んでいない。