指数バックオフとジッターとは?リトライ設計の教科書【シミュレーションで検証】

1. リトライはなぜ危険か

「一時的なエラーが出たら、とりあえずリトライしておけばいい」という発想は直感的には正しい。ネットワークは瞬断するし、サーバーは一時的に過負荷になるし、デプロイの瞬間にはリクエストが数件失敗する。こうした一過性の障害に対して、クライアントが自動的にリトライしてくれるのは望ましい振る舞いに見える。

問題は、1つのクライアントにとって合理的な振る舞いが、大量のクライアントが同時に同じ振る舞いをした瞬間に破滅的になることである。典型的なシナリオはこうだ。

あるサービスが一時的に過負荷になり、大量のリクエストがエラーを返す。
エラーを受け取ったクライアント群(数十〜数千)が、一斉にリトライする。
リトライの奔流がサービスへの負荷をさらに押し上げ、サービスはますます処理できなくなる。
処理できなかったリクエストがまたリトライされ、負荷が雪だるま式に増える。

この現象は一般に リトライストーム(retry storm) と呼ばれ、多数のクライアントが同じタイミングで同じ作業を要求してしまう サンダリングハード(thundering herd)問題 の一種である¹。本来はサービスを助けようとしているクライアントの善意のリトライが、結果として自分たちの手でサービスを叩き落とす「善意のDDoS」になってしまう点が厄介である。ネットワークの世界では古くから知られる輻輳崩壊(congestive collapse)――負荷が増えるほどスループットがかえって落ち込み、システムが自力で回復できなくなる現象――と本質的に同じ構造を持つ。

AWSのプリンシパルエンジニアであるMarc Brookerは、Amazon社内で信頼性の高いリモート呼び出しを実現するための3本柱として「タイムアウト・リトライ・バックオフ」を挙げている²。逆に言えば、タイムアウトとバックオフを伴わない素朴なリトライは、それ単体では危険な道具だということでもある。本記事では、この「バックオフ」、特に 指数バックオフとジッター に焦点を当て、なぜジッターが必要なのかを、AWSの一次資料の定義に基づいて整理したうえで、自作の離散事象シミュレーションで実際に検証する。

2. 固定間隔リトライの問題: 同期した再試行の波

最も素朴なリトライ方式は「失敗したら一定時間後にもう一度試す」という固定間隔リトライである。実装は簡単だが、次のような状況で深刻な問題を引き起こす。

ある瞬間(例: 短時間の障害やデプロイの瞬断)に、多数のクライアントの呼び出しが同時に失敗する。
全クライアントが同じ固定間隔 \(d\) でリトライする設定になっていると、\(d\) 秒後にほぼ全員が再び同時にリクエストを送る。
サーバー側の処理容量が有限であれば、この一斉リトライの一部だけが成功し、残りはまた失敗する。
失敗した残りのクライアントは、やはり同じ \(d\) 秒後にまた一斉にリトライする。

つまり、最初に発生した「同期」は固定間隔リトライでは自然には解消しない。クライアント群は容量の壁に何度もぶつかりながら、次第に数を減らしていく1つの塊(コホート)として振る舞い続ける。この様子を概念図として示す。

固定間隔リトライで起きる同期した波の概念図。サーバー容量k件/tickの上限を、tick=0,2,4,6,8で50→40→30→20→12件と徐々に減衰しながら繰り返し超過し、tick=10でようやく容量以下の6件に収まる

この図はあくまで概念を単純化したものだが、後述のシミュレーションで、この「波」が実際のモデルでどう振る舞うかを定量的に確認する。

3. 指数バックオフ: それでも残る「同期」の問題

固定間隔リトライの欠点への対策として広く使われるのが 指数バックオフ(exponential backoff) である。\(n\) 回目のリトライ時の待機時間 \(t_n\) を、基準値 base を初期値として2倍ずつ増やし、上限 cap で頭打ちにする。

\[ t_n = \min(\text{cap},\ \text{base} \cdot 2^{n}) \]

固定間隔ではなくリトライのたびに待機時間を伸ばすことで、「失敗が続くほどクライアントが遠慮する」という直感的に望ましい性質を持つ。AWSのアーキテクチャブログでも、これが素朴な固定間隔リトライに対する第一の改善として紹介されている³。

ただし、ここで見落とされがちな点がある。指数バックオフは「間隔を伸ばす」だけであり、「同期を崩す」わけではない。 最初に \(N\) 個のクライアントが完全に同時刻に失敗した場合、全員が全く同じ式 \(t_n\) に従って待機時間を計算するので、\(n\) 回目のリトライも依然として全員が同時刻に発生する。変わるのは「波と波の間隔が指数的に開いていく」ことだけで、「1回の波の大きさ(同時に押し寄せるリクエスト数)」はジッターなしの指数バックオフでは実質的に変化しない。この直感が正しいかどうかは、第5節のシミュレーションで実測する。

4. ジッター3方式: Full / Equal / Decorrelated Jitter

同期を崩すために必要なのが ジッター(jitter)――待機時間に乱数によるランダム性を加えることである。この考え方と3つの具体的な方式を整理したのが、2015年に公開されたMarc Brookerによる AWS Architecture Blog の記事 “Exponential Backoff and Jitter” である³。同記事で定義されている3方式の疑似コードは次の通り(sleep が実際の待機時間、attempt がリトライ回数)。

Full Jitter

\[ \text{sleep} = \text{random}\bigl(0,\ \min(\text{cap}, \text{base}\cdot 2^{\text{attempt}})\bigr) \]

指数バックオフで決まる上限値 \(\min(\text{cap}, \text{base}\cdot2^{\text{attempt}})\) を「最大待機時間」とみなし、0からその値までの一様乱数をそのまま採用する、最も単純で最もランダム性の強い方式。

Equal Jitter

\[ d = \min(\text{cap}, \text{base}\cdot 2^{\text{attempt}}), \qquad \text{sleep} = \frac{d}{2} + \text{random}\Bigl(0,\ \frac{d}{2}\Bigr) \]

待機時間の下限を常に \(d/2\) 以上に保証しつつ、残り半分にランダム性を持たせる方式。Full Jitterと違い「運が良ければ即座にリトライできてしまう」ことがない代わりに、ランダム性の幅はFull Jitterの半分にとどまる。

Decorrelated Jitter

\[ \text{sleep} = \min\bigl(\text{cap},\ \text{random}(\text{base},\ \text{sleep}_{\text{prev}} \cdot 3)\bigr) \]

前回の待機時間 \(\text{sleep}_{\text{prev}}\) を引き継ぎ、その3倍までの範囲でランダムに次の待機時間を決める方式(初回は sleep_prev = base)。\(2^{\text{attempt}}\) を明示的に計算しない点が他の2方式と異なり、待機時間の系列がクライアントごとに異なる乱数的な軌道を描く。

AWS Architecture Blogの元記事は、100クライアントが競合する状況をシミュレーションし、「ジッターなしの指数バックオフは総所要時間が長すぎてグラフに収まらないほど悪い」「Full JitterとDecorrelated Jitterがほぼ同等に優れ、両者ともEqual Jitterより明確に少ない総呼び出し回数で完了する」という結論を報告している³。本記事ではこの結論を鵜呑みにせず、自分たちで同種のシミュレーションを組んで再現・検証する。

5. シミュレーションで比較する

5.1 モデル設定

次のようなモデルで、5方式(固定間隔・指数バックオフ(ジッターなし)・Full Jitter・Equal Jitter・Decorrelated Jitter)を比較する離散事象シミュレーションを自作した。

クライアント数 \(N\) : \(N\) 個のクライアントが、時刻(tick) 0 で同時に最初のリクエストを送り、全員が失敗する(短時間の障害を想定した初期条件)。
サーバー容量 \(k\) : サーバーは1 tickあたり最大 \(k\) 件までしかリクエストを受理できない。あるtickへの到着数が \(k\) 件以下ならば全件成功、\(k\) 件を超える場合はランダムに \(k\) 件だけ成功し、残りは失敗して各方式に従って次のリトライ時刻を決める。
パラメータ: base=1, cap=32, 固定間隔は fixed_delay=2、サーバー容量 k=10。
測定指標: 全クライアントが成功し終えるまでの総時間(tick数)と、その間にサーバーへ送られた総呼び出し回数(成功・失敗を問わず全試行の合計)。
試行回数: \(N \in \{50, 100, 200\}\) の各設定・各方式について、乱数シードを変えて30回試行し、平均と標準偏差を報告する。

実装は次の通り(Python, numpy を使用)。

import numpy as np

def simulate(N, k, policy, base=1.0, cap=32.0, fixed_delay=2.0, seed=0, max_ticks=4000):
    rng = np.random.default_rng(seed)
    n = np.zeros(N, dtype=int)                  # 各クライアントのリトライ回数
    prev_sleep = np.full(N, base, dtype=float)   # decorrelated jitter用の直前sleep
    scheduled_tick = np.zeros(N, dtype=int)      # 次にリクエストを送るtick(全員tick=0)
    succeeded = np.zeros(N, dtype=bool)

    total_calls = 0
    arrivals_per_tick = []
    last_active_tick = 0

    for tick in range(max_ticks):
        idx = np.where((~succeeded) & (scheduled_tick == tick))[0]
        m = len(idx)
        arrivals_per_tick.append(m)
        if m == 0:
            if succeeded.all():
                break
            continue

        total_calls += m
        last_active_tick = tick

        if m <= k:
            succeeded[idx] = True
        else:
            chosen = rng.choice(idx, size=k, replace=False)
            succeeded[chosen] = True
            failed = np.setdiff1d(idx, chosen)
            for i in failed:
                ni = n[i] + 1
                n[i] = ni
                if policy == "fixed":
                    delay = fixed_delay
                elif policy == "expo":
                    delay = min(cap, base * (2 ** ni))
                elif policy == "full_jitter":
                    delay = rng.uniform(0, min(cap, base * (2 ** ni)))
                elif policy == "equal_jitter":
                    d = min(cap, base * (2 ** ni))
                    delay = d / 2 + rng.uniform(0, d / 2)
                elif policy == "decorr_jitter":
                    delay = min(cap, rng.uniform(base, prev_sleep[i] * 3))
                    prev_sleep[i] = delay
                new_tick = tick + max(1, int(round(delay)))
                scheduled_tick[i] = new_tick

        if succeeded.all():
            break

    total_time = last_active_tick + 1
    return total_calls, total_time, arrivals_per_tick

サーバー容量を1 tick単位のバケツとして扱い、そのtickに到着した呼び出し数が容量を超えていれば超過分だけ失敗させ、各クライアントが自分のリトライ回数 n (Decorrelated Jitterのみ直前の待機時間も)を保持して次の待機時間を計算する、という素直な実装である。\((N, \text{方式})\) の組み合わせごとに異なる乱数シードで30回実行し、平均と標準偏差を集計した。

5.2 実測結果: 総呼び出し回数と総時間

30試行の平均値(±標準偏差)は次の通りである。

\(N\)	方式	総時間(tick)	総呼び出し回数	固定間隔比の削減率
50	固定間隔	9.00 ± 0.00	150.0 ± 0.0	—
50	指数バックオフ(ジッターなし)	31.00 ± 0.00	150.0 ± 0.0	0.0%
50	Full Jitter	8.63 ± 1.50	117.8 ± 2.1	21.5%
50	Equal Jitter	8.33 ± 2.35	110.4 ± 0.7	26.4%
50	Decorrelated Jitter	10.00 ± 1.44	103.2 ± 2.0	31.2%
100	固定間隔	19.00 ± 0.00	550.0 ± 0.0	—
100	指数バックオフ(ジッターなし)	191.00 ± 0.00	550.0 ± 0.0	0.0%
100	Full Jitter	20.63 ± 5.26	316.8 ± 3.9	42.4%
100	Equal Jitter	19.67 ± 5.71	294.7 ± 3.4	46.4%
100	Decorrelated Jitter	16.93 ± 2.55	272.3 ± 5.3	50.5%
200	固定間隔	39.00 ± 0.00	2100.0 ± 0.0	—
200	指数バックオフ(ジッターなし)	511.00 ± 0.00	2100.0 ± 0.0	0.0%
200	Full Jitter	40.67 ± 3.59	814.0 ± 6.3	61.2%
200	Equal Jitter	48.17 ± 9.73	763.2 ± 4.5	63.7%
200	Decorrelated Jitter	36.30 ± 4.14	751.7 ± 9.3	64.2%

方式別の総呼び出し回数(左)と完了までの総時間(右、対数スケール)。N=50/100/200のいずれでも、固定間隔と指数バックオフ(ジッターなし)の総呼び出し回数は完全に一致し、ジッターを加えた3方式だけが総呼び出し回数を大きく削減している。一方、完了までの総時間は指数バックオフ(ジッターなし)だけが他方式より一桁以上長い

さらに、\(N=100\) の1試行について、各tickにサーバーへ到着したリクエスト数の時系列をプロットしたのが次の図である。

N=100・容量k=10/tickにおける到着リクエスト数の時系列。固定間隔と指数バックオフ(ジッターなし)は、大きさこそ減衰しながらも鋭い単発スパイクが同期したまま繰り返し発生し続けるのに対し、Full/Equal/Decorrelated Jitterはtick=0の初期スパイク以降、到着数が急速に分散・減衰していく

5.3 考察

実測結果は、期待していた定性的な傾向と概ね一致しつつ、いくつか予想以上に明確な事実を示した。

(1) ジッターなしの指数バックオフは、固定間隔リトライと総呼び出し回数が完全に一致する。 \(N=50,100,200\) のいずれでも、「指数バックオフ(ジッターなし)」の総呼び出し回数は固定間隔と1件の誤差もなく同じ値(150.0 / 550.0 / 2100.0)になった。これは偶然ではない。全クライアントが時刻0で完全に同期して失敗すると、ジッターがない限り同じ乱数を引かないので、生き残ったクライアント群は常に「全員が同じリトライ回数 \(n\) を共有する1つの塊」であり続ける。塊のサイズが \(N \to N-k \to N-2k \to \cdots\) と減っていく様子は、待機時間の伸ばし方(固定か指数か)によらず同一である。つまり 指数バックオフだけでは、同期を全く崩せない――3節で述べた直感は、シミュレーションでも定量的に裏付けられた。

(2) それにもかかわらず、指数バックオフ(ジッターなし)の完了までの総時間は、固定間隔より桁違いに悪化する。 \(N=200\) では固定間隔が39 tickで完了するのに対し、指数バックオフ(ジッターなし)は511 tickかかっており、実に13倍以上遅い。総呼び出し回数は同じなのに完了時間だけが悪化するのは、指数バックオフが「衝突する塊の大きさ」を変えずに「衝突の間隔」だけを引き延ばすからである。これはジッターを伴わない指数バックオフは、下手に導入するとかえって回復を遅らせるだけで、サーバー保護の効果はほぼ得られないという、やや反直感的だが重要な結論を示している。

(3) ジッターを加えた3方式は、いずれも固定間隔・指数バックオフに対して総呼び出し回数を21〜64%削減した。 削減率は \(N\) が大きくなるほど大きくなる傾向が見られた(Full Jitterで21.5% → 42.4% → 61.2%)。これは、\(N/k\) の比(1回のtickで捌ける容量に対する初期の過負荷倍率)が大きいほど、つまり本来リトライストームのリスクが大きい状況ほど、ジッターによる分散効果の恩恵が大きくなることを意味しており、実務上望ましい性質である。

(4) 3方式の間の優劣は、AWSブログの結論ほど明確な一貫性を示さなかった。 AWSの元記事はFull JitterとDecorrelated Jitterがほぼ同等に優れると報告しているが、今回のシミュレーションでは、総呼び出し回数はDecorrelated Jitterが3設定中2つ(\(N=100,200\) )で最小、完了時間も3設定すべてでDecorrelated Jitterが最速か僅差の最速だった。Full Jitterはむしろ3方式の中では総呼び出し回数がやや多めという結果になった。ただし差はいずれも数十件・数tickのオーダーであり、標準偏差(例えば \(N=200\) のEqual Jitterの完了時間は \(48.17 \pm 9.73\) )を踏まえれば、「3方式は同じオーダーで同程度に良く、固定間隔・ジッターなし指数バックオフに対して圧倒的に優れる」という大枠の結論の方が、個々の順位よりも頑健である。AWSの記事自身も「Full JitterとDecorrelated Jitterはほぼ同等」と述べており、本シミュレーションの結果もこの範囲には収まっている。Equal Jitterは待機時間の下限が保証される分、稀に大きな待機時間を引いた場合の完了時間のばらつき(標準偏差)が3方式中最大になる傾向も観測された。

以上から、「ジッターを入れるかどうか」が総呼び出し回数を左右する支配的な要因であり、「Full/Equal/Decorrelatedのどれを選ぶか」は二次的な選択であるという実務上の指針が、シミュレーションによって定量的に裏付けられたと言える。

6. 実務の設計指針

シミュレーションの結果を踏まえ、実際にリトライを実装する際の指針を整理する。

リトライ回数に上限を設ける: 無限リトライは、依存先が完全にダウンしている場合にクライアント側のリソース(接続・スレッド)を消費し続ける。cap による待機時間の頭打ちだけでなく、リトライ回数そのものにも上限(例: 3〜5回)を設け、それでも失敗する場合は呼び出し元にエラーを伝播させる。
タイムアウトを先に設計する: リトライは「1回の呼び出しがいつ失敗と判定されるか」が明確でないと機能しない。AWS Builders’ Libraryも、リモート呼び出しには必ずタイムアウトを設定することを、リトライより先に来る土台として位置づけている²。タイムアウトが長すぎると、リトライが積み重なる前に接続やスレッドが枯渇し、タイムアウトが短すぎると、正常に処理中のリクエストまで失敗としてリトライしてしまう。
冪等性が前提であることを忘れない: リトライは「同じリクエストを再送しても安全である」ことが前提になる。決済の作成のように副作用を伴うAPIをそのままリトライすると二重処理が起こりうる。冪等性キー(Idempotency-Key)を発行してサーバー側で重複を検出できるようにするか、そもそも冪等でない操作はリトライしない、という判断が必要である。
サーキットブレーカーと併用する: バックオフ+ジッターは「いつリトライするか」を制御する仕組みであり、「そもそもリトライすべきか」を判断する仕組みではない。依存先が明らかにダウンし続けている状況では、サーキットブレーカーで一定期間リトライそのものを止め、依存先の回復を妨げないようにする。AWS Builders’ Libraryが紹介する、ローカルにトークンバケットを持たせてリトライ数そのものを制限する仕組み²も、広い意味でのサーキットブレーカーの一種である。
クライアント階層でのリトライ増幅(retry amplification)に注意する: エッジ→サービスA→サービスB→DBのような多段の呼び出し階層で、各層が独立にリトライを行うと、最下層への実効呼び出し回数は各層のリトライ回数の積で増幅されうる(各層が3回ずつリトライすれば、3段構成で最大 \(3^3=27\) 倍)。リトライは呼び出し階層のうち1箇所(典型的には最も外側、あるいはクライアントSDKが提供する1点)に限定し、内部の層は失敗を即座に上位へ伝播させるべきである。

7. 各言語・ライブラリでの実装

自前でバックオフとジッターを実装する前に、多くの言語には実績のあるライブラリが存在する。車輪の再発明を避け、既存の実装を使うのが現実的である。

Python: tenacity

tenacity は @retry デコレータでリトライを宣言的に記述できるライブラリで、Full Jitter相当の待機戦略として wait_random_exponential が用意されている。

from tenacity import retry, stop_after_attempt, wait_random_exponential

@retry(
    wait=wait_random_exponential(multiplier=1, max=60),  # Full Jitter相当
    stop=stop_after_attempt(5),                          # リトライ上限
)
def call_flaky_service():
    ...

wait_random_exponential(multiplier, max) は、\(n\) 回目の待機時間の上限を multiplier * 2^n として max で頭打ちにし、0からその上限までの一様乱数を採用する――まさにFull Jitterの定義そのものである。stop_after_attempt と組み合わせて、指針1で述べたリトライ回数の上限も忘れずに設定する。

AWS SDK: retryMode(standard / adaptive)

AWSの各言語向けSDK(boto3を含む)は、retryMode という設定でリトライ挙動を切り替えられる。legacy(デフォルト、限定的なリトライのみ)、standard(指数バックオフとサーキットブレーカー的な挙動を備えた標準モード)、adaptive(クライアント側で送信レートそのものを動的に調整する実験的モード)の3種類があり、特別な理由がなければ standard を明示的に指定することが推奨される。boto3での認証設定・リトライ設定の詳細はhttps://yuhi-sa.github.io/posts/20220220_aws_set/1/で解説している。

8. まとめ

「リトライすれば安全」という発想は、単一クライアントの視点では正しくても、多数のクライアントが同時に失敗した瞬間には成り立たない。今回のシミュレーションでは、次の点が定量的に確認できた。

固定間隔リトライも、ジッターなしの指数バックオフも、一度同期したクライアント群の同期を自力では解消できない(総呼び出し回数が完全に一致)。
ジッターなしの指数バックオフは、同期を崩さないまま待機時間だけを伸ばすため、完了までの総時間がかえって大幅に悪化する(実験では最大13倍以上)。
ジッター(Full/Equal/Decorrelated)を加えることで、総呼び出し回数を21〜64%削減でき、削減率は競合が激しい(\(N/k\) が大きい)ほど大きくなる。
3方式間の優劣は僅差であり、「ジッターを入れるかどうか」の方が「どのジッターを選ぶか」よりも支配的な要因である。

指数バックオフとジッターは、数式自体は数行で書けるほど単純だが、その効果は「なぜ効くのか」を分解して初めて理解できる。今回のように実際に手を動かしてシミュレーションすることで、AWSの一次資料が示す結論を鵜呑みにせず、自分の頭で確かめることができた。

FAQ

Q1. リトライは何回までにすべきか? A. 唯一の正解はないが、3〜5回程度を上限とし、それでも失敗する場合は呼び出し元にエラーを返すのが一般的な出発点である。回数そのものよりも、「リトライ全体にかけてよい総時間(デッドライン)」を先に決め、そこから逆算して回数と待機時間の上限を決める方が実務的に破綻しにくい。

Q2. ジッターはFull/Equal/Decorrelatedのどれを選ぶべきか? A. 本記事のシミュレーションでは3方式の差は僅差であり、どれを選んでも「ジッターなし」に対する優位性の方が圧倒的に大きい。実装の単純さと実績を考えると、まずは tenacity の wait_random_exponential のようなFull Jitter相当のライブラリ実装をそのまま使うのが無難である。

Q3. タイムアウトとリトライ、どちらを先に設計すべきか? A. タイムアウトを先に決めるべきである。タイムアウトが定義されていなければ、「いつリトライを開始してよいか」自体が定まらず、リトライの設計が成り立たない。

Q4. 冪等でないAPIはリトライしてよいか? A. 原則としてリトライすべきではない。決済作成など副作用を伴う操作は、そのままリトライすると二重処理を招く。サーバー側が冪等性キーによる重複排除に対応している場合に限り、そのキーを使って安全にリトライできる。

データベースのコネクションプールサイズを待ち行列理論(M/M/c)でモデル化する - 容量制限のあるサーバーへの負荷集中という点で、本記事のサーバー容量モデルと共通する題材を、待ち行列理論の観点から扱っています。
boto3の使い方入門【Python×AWS】 - AWS SDKのretryMode(standard/adaptive)の設定方法を解説しています。

他の分野の定番書はエンジニアにおすすめの技術書10選にまとめている。

参考文献

Thundering herd problem. Wikipedia. https://en.wikipedia.org/wiki/Thundering_herd_problem ↩︎
Brooker, M. (2019). Timeouts, retries, and backoff with jitter. Amazon Builders’ Library. https://aws.amazon.com/builders-library/timeouts-retries-and-backoff-with-jitter/ ↩︎ ↩︎ ↩︎
Brooker, M. (2015). Exponential Backoff And Jitter. AWS Architecture Blog. https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/ ↩︎ ↩︎ ↩︎