指数バックオフ

どのようなものか

指数バックオフは、再試行までどのくらい待つかを決める規則です。失敗の
たびに、待ち時間を、通常は二という固定の倍率で増やし、上限で止めま
す。一秒、二秒、四秒、八秒、といった具合です。規則はクライアントにあ
りますが、守るのは、呼び出す相手です。過負荷で失敗するサーバー、ネッ
トワーク経路、データベースは、すぐもう一度呼んでも、早く復旧しませ
ん。呼び出す側が控えたときに回復します。失敗ごとに待ち時間を延ばせ
ば、問題が長引くほど、さらに控えるようになります。

最も古く、最も広く使われる例はTCPです。2011年6月の標準化過程の文書、
RFC
6298は、TCPの再送タイムアウトの計算を定めます。最初の往復時間を測る
前は一秒にし、計算結果が一秒未満なら、一秒へ切り上げるべきとします。
タイマーが切れ、セグメントを再送するたびに、ホストはタイムアウトを倍
にしなければなりません。上限を設けてもよいものの、少なくとも60秒が必
要です。新しい往復時間を測ると、測定値から再計算します。何度も倍にし
た後でも、すぐ短くできることがあります。アルゴリズムは、Van
Jacobsonの1988年の論文、Congestion Avoidance and
Controlへさかのぼります。RFCのセキュリティ節は、何を守る必要があるか
を述べます。インターネットは、ネットワークの安定を保ち、輻輳崩壊を防
ぐため、正しい再送タイマーに依存します。

アプリのコードでは、同じ考え方に、いくつかの設定を加えます。初期の待
ち時間、倍率、増加を止める最大待ち時間、試行回数か再試行の総時間の上
限です。式にすれば、ゼロから数えてn回目の失敗後の待ち時間は、上限
と、基準値
×
倍率のn乗の、小さい方です。後述のAWSの分析は、上限付き指数バックオフ
と呼びます。上限は、見た目以上に重要です。一秒を十回倍にすると1,024
秒で、17分を超えます。大半の呼び出し側は、何を呼び出していても、そこ
までは待ちません。

最後の設定は、各待ち時間にランダム性を持たせる、ジッターです。gRPCの
接続バックオフプロトコルは、接続失敗後の再接続を説明します。一秒から
始め、1.6倍し、120秒で増加を止め、0.2のジッターを適用します。各待ち
時間が、ランダムに最大20%増減します。各接続試行には、完了まで少なく
とも20秒を与えます。サーバーが接続を受け入れたら、初期値へ戻します。
このプロトコルが、受け入れた時点と見なすのは、SETTINGSフレームが届い
たときです。できるだけスリープからの復帰回数を抑えたい携帯電話など、
別の実装も認めます。ただし、同時の再試行を分散させ、試行頻度を大幅に
高めないことを要求します。

なぜ重要なのか

再試行は、追加の負荷です。しかも、呼び出す相手が失敗している、最も悪
い瞬間に届きます。過負荷でサービスが遅くなり、すべての呼び出し側が直
ちに再試行すると、処理能力が下がる一方で負荷が増えます。そのため、
Google
Cloud
Storageの文書は、バックオフなしの再試行をアンチパターンに挙げます。
即座、または極端に短い間隔の再試行は、一つの失敗がほかを呼ぶ、連鎖障
害につながるためです。バックオフは、再試行を、増幅器からブレーキへ変
えます。問題が長引くほど、各クライアントが加える負荷は減ります。

バックオフだけでは足りません。同時に失敗するクライアントは、同時に待
つためです。AWSが2015年3月に公開したExponential
Backoff And Jitterで、Marc
Brookerは、リモートデータベースの同じ行を、楽観的な同時実行制御で更
新する、多数のクライアントをシミュレーションしました。各ラウンドで全
員が競うと、仕事の総量は、クライアント数の二乗で増えました。上限付き
指数バックオフの効果は、わずかでした。呼び出しがまとまって届き、その
間には呼び出しのない空白ができるため、競合はほぼ減りませんでした。ゼ
ロから上限付き指数値まで、各待ち時間をランダムに選ぶジッターを加える
と、空白がなくなり、呼び出しは、ほぼ一定の頻度になりました。100クラ
イアントが競う例では、呼び出し数を半分未満へ減らしました。比較した方
式の中で、ジッターなしのバックオフは、Brookerの言葉では「明らかな敗
者」でした。限界も明記しています。どの方法も、仕事が競合の二乗で増え
る事実は変えません。ジッターは無駄を減らしても、競合をなくしません。
2023年5月の追記では、大半のAWS
SDKが、標準と適応型の再試行モードに、指数バックオフとジッターを備え
ると述べます。

バックオフが決めるのは、いつ再試行するかで、安全かどうかではありませ
ん。Cloud
Storageの文書は、先に二つを問います。一つは、応答が一時的な問題を示
すかです。HTTP
408、429、5xxのステータスコード、ソケットのタイムアウト、TCP切断など
です。もう一つは、リクエストが冪等かです。一覧を取得する操作は、自由
に繰り返せます。Pub/Sub通知の作成は、できません。成功するたびに、新
しい通知を作るためです。中間には、条件付きで冪等な操作があります。オ
ブジェクトの世代番号が、まだクライアントの期待するものと一致する場合
だけ成功するアップロードなど、前提条件を付ければ、安全に再試行できま
す。

クライアントの式より、サーバーの方がよく知っていることもあります。
RFC
9110のRetry-Afterヘッダーフィールドは、次のリクエストまで待つべき時
間を、日時か秒数で伝えます。503 Service
Unavailableでは、サービスが予想する利用不能時間です。RFC 6585の429
Too Many
Requestsは、流量制限を示し、同じフィールドを含めることがあります。
バックオフのループを持つクライアントは、自分で計算した待ち時間の代わ
りに、その値を使えます。自分の負荷が見える側からの情報だからです。

実際の活用例

上限付き指数バックオフとFull Jitterを使う再試行ループは、Pythonの数
行に収まります。

```python
import random
import time

class TransientError(Exception):
    """タイムアウト、408・429・5xxの応答、または接続の切断。"""

def call_with_backoff(op, attempts=5, base=1.0, cap=30.0):
    for attempt in range(attempts):
        try:
            return op()
        except TransientError:
            if attempt == attempts - 1:
                raise
            ceiling = min(cap, base * 2**attempt)
            time.sleep(random.uniform(0, ceiling))
```

この値では、五回の試行の間に、上限が1、2、4、8秒の、四回の待機があり
ます。ゼロから各上限まで一様に選ぶため、諦めるまでに眠る時間の合計
は、最大15秒、平均約7.5秒です。再試行するのは`TransientError`だけで
す。認可の失敗や不正な形式のリクエストは、その場で例外になります。
ループは、`op`の行うすべてを繰り返します。そのため、`op`は安全に繰り
返せる必要があります。読み取りか、サーバーが重複と認識できる書き込み
です。

クライアントライブラリーにも、このループの実装があり、同じサービスで
も既定値は違います。Cloud
StorageのPythonクライアントは、一秒から始め、最大60秒まで倍にし、既
定の総期限120秒で諦めます。C++クライアントも、一秒から倍にしますが、
試行の間は最大五分待ち、最大15分間、再試行します。七倍を超える長さで
す。厳密な冪等性ポリシーを明示的に選ばなければ、決して冪等にならない
操作まで再試行します。gcloudのコマンドラインは、Googleが打ち切り付き
二進指数バックオフと呼ぶ方式を使い、既定で最大32回の再試行を行いま
す。同じAPIで同じ失敗に遭遇する二つのプログラムが、書いた言語によっ
て、二分で報告することも、十五分で報告することもあります。

待機で、スレッドを止める必要はありません。バックグラウンド処理なら、
失敗したジョブを、後の実行予定時刻でキューへ戻せます。バックオフは、
スリープ中のプロセスではなく、ジョブの属性になります。誰も答えを待た
ないときには、それが自然な置き場所です。

2025年からの職務で手がけたフェイルオーバーと配信ログを備えるメールで
は、バックオフを、非同期側に置きます。メールは、主系のSendGridと、後
続のSMTP2GO、Azure
Communication
Servicesの三事業者を使って送信し、切り替えは自動です。送信経路自体
は、30秒のタイムアウトを持つクライアントを通ります。非同期の配信経路
には、再試行とバックオフがあり、短い不調でメッセージを失わないように
します。事例は、結果をこうまとめます。一つの事業者の調子が悪いとき、
メールは停止するのではなく、機能を落とした経路を通ります。代償は、一
つではなく、三つの連携を動かし続けることです。

問題が起きるところ

全クライアントが、同じ時間だけ待ちます。
ジッターなしでは、同時に失敗したクライアントが、同時に再試行します。
サーバーには、一秒、二秒、四秒、八秒後に、同じ負荷の山が来ます。
Brookerのシミュレーションでも、そのため、単純な指数バックオフは、競
合をほとんど減らしませんでした。ジッターを加えます。比較では、Full
JitterもDecorrelated
Jitterも、クライアントの仕事量とサーバー負荷を大きく減らしました。ど
ちらも、妥当な既定の選択です。

待ち時間に上限がないか、再試行が終わりません。
上限なく倍にすると、十回の失敗後には17分を超えます。回数や時間を制限
しないループは、誰も返答を待たなくなってからも、リクエストを生かし続
けます。Googleは、再試行の制限を無視することを、アンチパターンに挙げ
ます。無期限の再試行で、アプリの資源を使い尽くしたり、介入なしには回
復しないサービスへ、送り続けたりするためです。呼び出す側に合う最大待
ち時間と総期限を決めます。レイテンシーが重要なら短く、バッチ処理なら
長くします。

恒久的なエラーを、再試行します。
認可の失敗や不正なリクエストは、毎回同じように失敗します。再試行は、
エラーを遅らせるだけです。Cloud
Storageの文書が警告するように、制限がなければ、クライアントが無限
ループへ入ることもあります。ループの前に、一時的なエラーと恒久的なエ
ラーを分け、408、429、5xx、切断など、一時的なものだけを再試行しま
す。残りは、原因と一緒にログへ記録します。

冪等でない操作を、無条件に再試行します。
サーバーがすでに処理した後でタイムアウトすると、再試行が同じ操作を繰
り返します。Googleのアンチパターンの一覧は、意図しない上書きやデータ
削除と説明します。冪等な操作だけを再試行し、APIが認めるなら書き込み
へ条件を付け、それ以外では、受け取る側が重複を検出できるようにしま
す。

複数の層で、再試行を重ねます。
アプリが三回試し、その一回ごとに、下のクライアントライブラリーも三回
試すと、一つの失敗が、九回の試行になります。Google自身の例で、さらに
自分で再試行する層が増えるたびに、回数を掛け合わせます。文書は、これ
ほどの再試行が、成功率を上げることなく、リクエストの流量制限やレイテ
ンシーの増加を招くこともあると付け加えます。再試行は、通常はライブラ
リーの、一層だけで行い、ほかの層では無効にするか減らします。

バックオフを戻さないか、誰もその状況を見ていません。
回復後も最後の長い待ち時間を保つクライアントは、次の小さい失敗でも、
最大時間を待ち切ります。gRPCは、接続を受け入れたら直ちに初期値へ戻
し、TCPは、新しい測定からタイマーを再計算します。成功したら、元に戻
します。再試行が問題を利用者から隠すと、チームからも隠れます。監視で
回数を数え、頻度が上がったらアラートを出します。一回の呼び出しに三回
の試行が必要な依存先は、すでに失敗しています。

参考資料

  * RFC 6298：TCPの再送タイマーの計算 —
タイマーが切れるたびの倍増を含む、TCP再送タイムアウトについての、標
準化過程の規則です。

  * gRPCの接続バックオフプロトコル — 再接続のアルゴリズム、五つのパ
ラメーターと値、バックオフを戻す時点です。

  * 指数バックオフとジッター — 競合するクライアントを扱うMarc
Brookerの2015年のシミュレーションです。ジッターなしと、Full、Equal、
Decorrelated
Jitterを比較します。

  * 再試行の方針 — Cloud
Storageが安全に再試行できるとする操作、各クライアントライブラリーの
既定値、五つの再試行のアンチパターンです。

  * RFC 9110：HTTPの意味論 —
サーバーが、次のリクエストまで待つ時間をクライアントへ伝える、Retry-
Afterフィールドです。

hこのページのウェブ版	URL:https://engineer.company/ja/glossary/exponential-backoff/	engineer.company	70
