はじめに
Google Drive APIについて調べていたところ、使用制限の箇所で指数バックオフアルゴリズムに関する記述がありました。
自分が初めてエンジニアになった頃に、あるエンジニアがAngulerのRxJSを使用して指数バックオフを作成していたことがあり、その時はあまり理解できていなかったので、改めて調べてみることにしました。
Exponential Backoff（指数関数バックオフ）とは
指数バックオフとは、通信に失敗した際に、待ち時間を指数関数的に増やしてリクエストを定期的に再試行手法のことを指します。
実装例
実装方法は以下の通りです。
/**
* @param fn - 実行したい非同期関数（例: fetch）
* @param retries - 最大リトライ回数
* @param baseDelay - 初回の遅延ミリ秒（例: 100ms）
* @returns 最終的なPromiseの結果
*/
export const exponentialBackoff = async <T>(
fn: () => Promise<T>,
retries = 5,
baseDelay = 100
): Promise<T> => {
for (let attempt = 0; attempt <= retries; attempt++) {
try {
return await fn()
} catch (err) {
if (attempt === retries) throw err
const delay = Math.random() * baseDelay * 2 ** attempt
console.warn(`Retry ${attempt + 1} after ${Math.round(delay)}ms`)
await sleep(delay)
}
}
throw new Error('This should not be reached')
}
const sleep = (ms: number): Promise<void> => {
return new Promise((resolve) => setTimeout(resolve, ms))
}
const fetchWithRetry = async () => {
const result = await exponentialBackoff(async () => {
const res = await fetch('https://api.example.com/data')
if (!res.ok) throw new Error('API error')
return res.json()
})
}
baseDelay * 2 ** attemptで試行回数に応じて待機時間を倍に設定します。
指数関数的なリトライが必要なのか？
ここで疑問となるのが、Math.random() * baseDelay * attemptのような線形ではダメなのかということです。結論から述べると指数関数的な待機時間を設定することで短期間での過剰な再試行を避け、システムの安定性を守ることが目的となります。
線形（* attempt）でも動作はしますが、負荷抑制効果は小さく、混雑や障害時には効果が弱いため、WebサービスやAPIのスロットリング制限に引っかかる可能性があります。
| リトライ回数 | 線形（delay * attempt） | 指数（delay * 2^attempt） |
|---|---|---|
| 1回目 | 100ms | 100ms |
| 2回目 | 200ms | 200ms |
| 3回目 | 300ms | 400ms |
| 4回目 | 400ms | 800ms |
| 5回目 | 500ms | 1600ms |
表の通り指数的な方が急速にリトライ間隔が伸びる為、サーバやAPIの回復を待つ余裕を与えることにつながります。
ジッターとは何か？
ジッター（Jitter）とはリトライのタイミングに「ランダムなばらつき」を持たせて、同じタイミングで大量のリトライが発生しないようにする技術のことを指します。特に大規模システムの場合に、同時にリトライ → システムが再ダウンすることを防ぐ必要があります。
上記コードの場合、Math.random()を追加することでジッター（ばらつき）を加えで同時アクセスを緩和します。
指数バックオフ + ジッターの戦略パターン
Math.random()を使用した例はFull Jitterと呼ばれます。それ以外にもEqual Jitterや、Decorrelated Jitterが存在します。
Equal Jitter
安定性とばらつきの中間（リトライの遅延時間を「中央値（半分）+ ジッター」）で計算します。
Full Jitterより早くリトライする傾向にありますが、ある程度予測することができつつリトライにばらつきを持たせることができます。
const equalJitterDelay = (base: number, attempt: number) => {
const half = base * 2 ** (attempt - 1)
return half + Math.floor(Math.random() * half)
}
Decorrelated Jitter
前の遅延時間と次の遅延時間の相関関係はなく、毎回ランダムにリトライを行います。
let prevDelay = base
const decorrelatedJitterDelay = (base: number, cap: number) => {
const newDelay = Math.min(cap, Math.floor(Math.random() * (prevDelay * 3 - base) + base))
prevDelay = newDelay
return newDelay
}
Of the jittered approaches, “Equal Jitter” is the loser. It does slightly more work than “Full Jitter”, and takes much longer. The decision between “Decorrelated Jitter” and “Full Jitter” is less clear. The “Full Jitter” approach uses less work, but slightly more time. Both approaches, though, present a substantial decrease in client work and server load.
AWSの公式では、Decorrelated JitterやFull Jitterの採用を推奨しているようです。
さいごに
ここまで読んでいただきありがとうございました。機会があれば、状況に応じてDecorrelated JitterやFull Jitter等、リトライ戦略を適切に設定してきたいと思います。
Discussion