Exponential backoff and jitter/指数バックオフ

Exponential backoff and jitterとは

リトライ戦略の一つです。指数関数的にリトライ間隔を徐々に伸ばしつつランダムなばらつきを付与することでリトライ間隔を調整する手法です。それぞれの単語を和訳すると以下の通りです。

• exponential: 指数関数的な
• backoff: 速度・ペースを落とす
• jitter: ばらつき・揺らぎ・ズレ

詳細

• sleep: リトライ間隔
• base: リトライ間隔の基本単位。例：1000msなど
• cap: リトライ間隔の最大値。sleepがcapを超え内容にする。（capは帽子の意味？）
• attempt: リトライ回数

Exponential backoff無しの普通のリトライ

$$
sleep = base
$$
単純にbaseの秒数だけ待ちます。

メール送信処理を例にします。100人のユーザーが同時にメール送信リクエストを実行したとします。アプリサーバーはメール送信ロジックを1件ずつしか捌くことができないものとします。この場合、まず1人目のメールが送信され残り99人のメールリクエストはリトライに回されます。次に2人目のリクエストが処理され残り98人はリトライに回され…といった挙動を100人目まで繰り返します。

Exponential backoffを適用＆Jitterを付与(Full jitter)

$$
sleep = random(0 ,min(cap, base \times 2^{attempt}))
$$

$base \times 2^{attempt}$によってリトライ回数に応じた遅延（backoff）が適用されます。また、$random$によってばらつき（jitter）が生まれます。

Equal jitter

temp = min(cap, base \times 2^{attempt})

sleep = \frac{temp}{2} + random(0, \frac{temp}{2})

遅延（backoff）とばらつき（jitter）を最小限に留めようとする手法です。jitterがどんな値になろうとも$ \frac{temp}{2}$の分は必ず待つことになります。

Decorrelated jitter

$$
sleep = min(cap, random(base, sleep \times 3)
$$
前回計算した$sleep$の値を拡大することでsleepの最大化を図ります。
※Decorrelatedは無関心という意味です。

実装(Java)

以上を踏まえてJavaでサンプルコードを実装してみました。Equal jitterの例のみ記載します。

    private static int MAX_RETRY = 3;
    private static int CAP = 10 * 1000L; // 10,000ms
    private static int BASE = 1000L; // 1,000ms
    
    private void run() {
        for (int currentTry = 0; currentTry < MAX_RETRY; currentTry++) {
            try {
                doHeavyTask();
                return;
            } catch (final SomeException e) {
                try {
                    final var temp = Math.min(CAP, BASE * Math.pow(2, currentTry));
                    Thread.sleep(temp / 2 + RandomUtils.nextLong(0, temp / 2));
                } catch (final InterruptedException e1) {
                    // sleepでInterruptedExceptionが発生してもログだけ出力して握り潰す
                    log.warn(e1.getMessage());
                }
            }
        }
    }

参考