リトライと指数バックオフ
Retry and Exponential Backoff ・ リトライとしすうバックオフ
失敗した処理を間隔を広げながら再試行する定石。無邪気なリトライは障害を増幅する。
✦ 30秒で試す — 航海ゆっくり待ってから再挑戦しても、サーバを沈めることがある再挑戦の要求は、サーバにどう届く？予想してみる概要
リトライは、失敗した処理をもう一度試すことです。ネットワークの一瞬の途切れ、依存先の瞬間的な過負荷、デプロイ直後の揺らぎ — 分散システムの失敗の多くは「もう一度やれば成功する」一過性のものなので、リトライは可用性を上げる最も手軽で効果的な手段です。
ただし、リトライには裏の顔があります。失敗の原因が「相手の過負荷」だった場合、リトライは弱っている相手にさらにリクエストを浴びせる行為になり、障害を長引かせ、増幅します。そこで「間隔をどんどん広げながら再試行する」のが指数バックオフ（exponential backoff）、その間隔に乱数のゆらぎを加えるのがジッター（jitter）です。「リトライ + 指数バックオフ + ジッター」の三点セットは、タイムアウトと並んで、外部呼び出しを堅牢にする定石として広く共有されています。
なぜ生まれたか
無邪気なリトライ — 失敗したら即座に、あるいは固定の短い間隔でやり直す実装 — が引き起こす典型的な事故が「リトライストーム」です。依存先のサーバが一瞬詰まると、大量のクライアントが一斉に失敗し、一斉にリトライします。相手が受ける負荷は元の2倍、3倍に膨れ上がり、回復しかけたサーバは再び押し潰されます。クライアントから見れば「まだ失敗する」のでさらにリトライが重なり、呼び出し階層が深いと各層のリトライが掛け算で効いて、末端には元の何十倍ものリクエストが殺到します。ちょっとした瞬断が、リトライによって本格的な障害へと育ってしまうのです。
指数バックオフは、この「善意の一斉攻撃」を抑えるために生まれました。ルーツは共有回線の衝突制御にあります。1970年代のハワイ大学の無線網 ALOHAnet は、衝突したら乱数の時間だけ待って送り直す方式を採り、それを受け継いだイーサネット（Metcalfe と Boggs の1976年の論文）は「衝突するたびに待ち時間の上限を倍にし、その範囲の乱数だけ待つ」二進指数バックオフを定めました。つまり、このアルゴリズムは最初から「倍にする」と「乱数でずらす」の二つがそろって生まれています。回線でもサーバでも本質は同じで、混んでいるなら引く、それでも駄目ならもっと引く、そして引くタイミングを参加者ごとにずらす — 競合する参加者たちが自律的に負荷を散らすための、時間方向の譲り合いです。
詳細
指数バックオフとジッターの仕組み
基本形は単純です。1回目の失敗後は例えば1秒待つ、2回目は2秒、3回目は4秒、4回目は8秒 — と待ち時間を指数的に（通常2倍ずつ）伸ばし、上限（例えば60秒）で頭打ちにします。失敗が続くほど「相手は本格的に調子が悪い」可能性が高いので、試行の頻度を急速に下げて相手の回復時間を確保する、という理屈です。
しかし指数バックオフだけでは足りません。同時に失敗した1000台のクライアントは、全員が同じ計算式で待つため、1秒後・2秒後・4秒後に「一斉に」再試行します。負荷の波は間引かれても、波が同期したままなのです。そこで待ち時間に乱数を混ぜるのがジッターです。代表的な「フルジッター」方式では、待ち時間を「0〜計算値の間の乱数」にしてしまいます。これで再試行の瞬間がばらけ、スパイクがなだらかな平均負荷へとならされます。AWS の Marc Brooker が2015年に公開した検証で「ジッターなしの指数バックオフより、大胆に乱数化したほうが総所要時間も総リクエスト数も少ない」ことが示されて以来、ジッターは省略してはいけない要素として定着しました。
図の縦の帯は「その瞬間にサーバへ同時に届く再試行」です。指数バックオフは帯の数を減らしますが、帯の太さ（同時に届く数）は変えません。サーバの容量を超えるのは帯の太さのほうなので、束をほどくジッターが効くのです。
下の部品で確かめてください。サーバを押すと1.5秒の瞬断が起き、32台のクライアントが同じ瞬間に失敗します。待ち方を切り替えて何度か瞬断を起こし、戻ってくる要求の束が容量線をどう越えるかを比べてみてください。
32台のクライアントが、ふだんはばらばらにサーバを呼んでいます（容量の半分ほど）。右のサーバを押して瞬断を起こし、失敗した全員がどう戻ってくるかを見てください。
リトライしてよい失敗、してはいけない失敗
すべての失敗をリトライしてよいわけではありません。判断の軸は「もう一度やれば結果が変わりうるか」です。HTTP で言えば、503（過負荷）や 429（レート制限超過）、408（リクエストタイムアウト）、そしてタイムアウトや接続の切断は一過性の可能性が高く、リトライの候補です。一方、429 と 408 を除く 4xx — 400（リクエスト不正）や 403（権限なし）など — は、こちらの送る内容が変わらない限り何度やっても同じ結果なので、リトライは無駄弾どころか有害です。429 や 503 で相手が Retry-After ヘッダによって「いつ来てよいか」を指示してくる場合は、自前のバックオフ計算よりその指示を優先します。
もうひとつの大前提が冪等性です。タイムアウトした呼び出しは「失敗した」のではなく「結果が分からない」だけで、実は相手側で処理が完了しているかもしれません。そこにリトライを重ねると、決済が二重に走る、注文が二件入る、といった事故になります。リトライを安全にするには、同じリクエストを何度受けても結果が一度分にしかならないよう、冪等キーなどで受け側を設計しておくことが欠かせません。
やりすぎを防ぐ — 回数上限とリトライバジェット
リトライには必ず打ち切りを設けます。試行回数の上限（3回程度が一般的）に加え、近年は「リトライバジェット」という考え方が広まっています。これは「リトライは通常トラフィックの10%まで」のように、リトライが全体に占める割合へ上限を課すものです。回数上限だけだと、全リクエストが失敗する大規模障害時には「全員が3回ずつ」で負荷が一気に4倍（初回＋3回）になりますが、バジェット方式なら障害が広がるほどリトライが自動的に絞られ、増幅が頭打ちになります。サービスメッシュの実装（Linkerd など）がこの方式を採用しています。
また、リトライは階層のどこか1か所に集約するのが原則です。各層が善意でリトライすると掛け算で増幅されるためです。3層の呼び出しで各層が「初回＋3回」試すと、末端の依存先には最大 4 × 4 × 4 = 64 倍の要求が届きます。「末端の呼び出し層でだけリトライし、上位層はしない」といった役割分担を決めておきます。ユーザーの応答を待たせられない処理なら、その場で粘るのではなくメッセージキューに積んで非同期に再試行し、規定回数失敗したものはデッドレターキューに退避して人が調べる、という形に逃がすのも定石です。
系譜の次へ — 諦める勇気
バックオフしながらのリトライは「そのうち直る」障害には有効ですが、長引く障害に対しては、失敗するとわかっている試行を延々と続けることになります。「この依存先は今は駄目だ」と判断して呼び出し自体を止め、回復の兆しが見えたら再開する — その判断を自動化したのがサーキットブレーカーです。タイムアウトで速く失敗し、バックオフ付きリトライで粘り、それでも駄目ならブレーカーで諦める。この3段構えが、外部呼び出しの信頼性設計の基本形になっています。
試問
左に32台のクライアント、右にサーバ（0.25秒に4件までしかさばけず、超えた分は失敗してまた待ちに戻る）があります。サーバを押すと1.5秒の瞬断が起き、32台が同じ瞬間に失敗して再試行を始めます。再試行の待ち方を「固定間隔（毎回1秒）」「指数バックオフ（0.5・1・2・4秒…と倍々）」「指数＋ジッター（0〜その倍々の値の乱数）」から選べ、下のグラフに到着数が出ます。
32台のクライアントが、ふだんはばらばらにサーバを呼んでいます（容量の半分ほど）。右のサーバを押して瞬断を起こし、失敗した全員がどう戻ってくるかを見てください。