ヘッジドリクエストとテイル耐性

なぜ「速い系」でもp99が遅いのか

平均レイテンシが数ミリ秒のサービスでも、p99（99パーセンタイル）やp999が数十〜数百ミリ秒に跳ねることは珍しくありません。原因はGCの停止、キューの一時的な詰まり、ディスクの再試行、ホットスポットへの偶発的な集中など多岐にわたります。重要なのは、どれも「常に遅い」のではなく「ときどき特定のリクエストだけが遅い」 という点です。遅延の分布を見ると、本体は速くて裾（テイル）だけが長く伸びています（/devops/percentile-latency-statistics/）。

このテイルが厄介なのは、多段のファンアウトで増幅される からです。1つのユーザーリクエストが内部で100個のバックエンドを呼び、全部の応答を待つなら、各々のp99が10msでも「少なくとも1つが遅い裾に当たる」確率は急増します。個々の系を速くする努力には限界があり、遅い1台を待たない仕組み が必要になります。その代表が、Googleの論文「The Tail at Scale」で整理されたヘッジリクエストとタイドリクエストです。

ヘッジリクエスト：遅延してから二重発行

ヘッジリクエスト（hedged request）の発想は単純です。1台目に投げて、一定時間内に返ってこなければ、同じ要求を別レプリカにも投げ、先に返ってきた方を採用して残りはキャンセルする。

t=0     : レプリカAへ要求を送る
t=遅延d : まだAから応答なし → レプリカBへ同じ要求を送る
t=?     : A・Bのうち先に返った方を採用、もう一方はキャンセル

肝は遅延しきい値 d の置き方です。d をゼロにすると常に2倍のリクエストを発行することになり、システム全体の負荷が倍増します。逆に大きすぎれば、遅いリクエストを救えません。実務での定石は、d を1台目の応答時間分布のp95あたりに設定する ことです。こうすると二重発行が起きるのは全体の約5%だけ。余分な負荷は数%に抑えつつ、裾の5%を別レプリカで救える ため、p99・p999が劇的に縮みます。

遅延しきい値は固定値ではなく、実測の応答時間分布から動的に算出する のが理想です。HDRヒストグラムなどでp95を継続的に推定し、d を追従させます（/devops/percentile-latency-statistics/）。負荷状況やレプリカの健全性で分布は刻々と変わるためです。

タイドリクエスト：即時二重発行＋相互キャンセル

ヘッジは「待ってから」二重発行するので、最悪ケースでも d だけは余計に待ちます。これを嫌い、最初から2台へ同時に発行し、片方が実際に処理を開始した瞬間に相手をキャンセルする のがタイドリクエスト（tied request）です。「2つの要求が紐（tie）で結ばれている」イメージです。

t=0 : レプリカA・Bの両方へ要求を送る。
      各要求に「相手はB（またはA）」という情報を添える
t=?  : 先に自分のキューから取り出して処理を始めた側が、
       相手へ「自分が処理する」キャンセルメッセージを送る
t=?  : キャンセルを受けた側は、まだ未着手ならキューから破棄する

ここでの主役は レプリカ間の相互通知 です。各レプリカは要求をキューに積み、ワーカーが取り出して処理を始める直前に、ペアの相手へ「自分が始める」と通知します。通知を受けた相手は、まだキューで待機中（未着手）なら即座に破棄 します。これにより、一方のキューがたまたま空いていればそちらがすぐ処理を開始し、待ち時間ゼロで遅い方のキュー詰まりを回避 できます。

タイドリクエストの追加コストは、キャンセルメッセージの往復と、ごく短時間ながら2台に要求が乗ること です。ただしキャンセルが速やかに届けば、実際に両方が処理する「重複処理」はまれです。問題は同一データセンタ内などレプリカ間遅延が小さい環境 に向くこと。レプリカが地理的に離れていてキャンセルの伝播が遅いと、両方が処理を始めてしまい二度手間になります。

効く前提と、効かない条件

両技法とも、冪等性（idempotency）が大前提 です。同じ要求を2台に投げて両方が実行されても結果が壊れないこと。読み取りや、冪等に設計された処理なら安全ですが、非冪等な書き込み（在庫を1つ減らす等）にそのまま使うと二重実行で破綻 します。書き込みに適用するなら、リクエストIDで重複排除する仕組みと組み合わせる必要があります（/devops/idempotency-exactly-once/）。

もう一つの前提は、遅延が独立に近いこと です。レプリカ全体が同時に遅い（共通原因の障害、依存先の輻輳）場合、別レプリカに投げても同じく遅く、二重発行は無駄打ちになるどころか負荷を上乗せします。ヘッジが効くのは「個々のリクエストが独立に、たまたま遅い裾を引く」状況です。系全体のテイルが利用率起因で構造的に悪い場合は、まず利用率を下げる方が筋です（/devops/queueing-theory-tail-latency/）。

タイムアウト・リトライとの違い

ヘッジは一見リトライ（/devops/retry-backoff-jitter/）に似ますが、本質が違います。リトライは1台目が失敗・タイムアウトしてからやり直すので、その判定に長い時間（タイムアウト値）を要し、テイルをむしろ伸ばします。ヘッジは1台目をあきらめず生かしたまま並行で2台目を走らせ、先着を採る——失敗判定を待たない点が決定的に異なります。デッドライン伝播（/devops/timeout-deadline-propagation/）と組み合わせ、全体の締切内でヘッジが収まるよう設計します。

まとめ

• ヘッジリクエストは遅延しきい値 d 経過後に別レプリカへ二重発行し先着を採る。d をp95付近に置けば追加負荷は数%でp99・p999を大きく縮められる。
• タイドリクエストは即時に2台へ発行し、処理を始めた側が相手をキャンセルする。レプリカ間の相互通知で待ち時間ゼロにできるが、協調コストとレプリカ間の近接が要る。
• 両者とも冪等性が前提。非冪等な書き込みには重複排除を併用する。
• 割合上限でガード し、過負荷時の二重発行暴走と独立でないテイルへの無駄打ちを防ぐ。健全時の保険として裾だけを削るのが正しい使い方。