Exponential backoff のパラメーターを調整するための目安を知りたくて、ざっと計算してみました。

TL;DR

表題の答えは、ほぼ比例関係です。 T_n を n 回目のリトライ実施時の経過時間¹とすれば、その次のリトライまでの間隔（sleepする時間）は以下の式で表せます。

\begin{align}
T_{n+1} - T_{n} &:= a r^n \\
&\;= a + (r-1) T_{n} \\
\end{align}

（ a は初回のsleep時間、 r はその時間を伸ばしていく倍率）

通常 r > 1 なので、十分に時間が経過すると a を無視できて (T_n+1 - T_n) / T_n ≃ (r-1) となります。逆に言えば、希望する「経過時間とリトライ間隔の比率」があれば、そこから r を決められます。

はじめに

「処理が成功するまでリトライして待つ」ということが時々あります。単に非同期処理の完了を待つことだったり、確率的に失敗することへの対策だったり、依存システム（やネットワーク）の障害発生時に復旧するまで耐えることだったり。

このリトライは頻繁すぎると無駄に負荷がかかり²、少なすぎると必要以上に待ち続けてしまいます。処理成功までの時間が見当つかない場合に適切な頻度を決めるのは困難です。このバランスをうまくとる方法として、リトライ間隔（sleepの時間）を指数関数的に伸ばしていく exponential backoff があります。指数関数的と言うと難しそうですが、単純に 1秒 → 2秒 → 4秒 → 8秒 → … などと前回の間隔を定数倍することになります³。（実用的にはもう少し工夫を入れます）

import time

def do_something_with_retries(init_interval = 1.0, scaling = 2.0):
    n = 0  # 何回目のリトライかを表すカウンター（初回はゼロと数えることにする）
    interval = init_interval

    while True:
        try:
            result = do_something()
            break
        except Exception as exc:
            if n >= 10:  # （無限リトライ防止）
                raise RuntimeError from exc
            n += 1
            time.sleep(interval)  # 負荷を減らすために少し待つ
            interval *= scaling
            # リトライの準備が整ったので、whileループの先頭に戻る

    return result

例えば Fluentd のドキュメントに、図入りの簡潔な動作説明があります。

疑問

Exponential backoff に最低限必要なパラメーターは「初回のsleep時間」と「伸ばす倍率」であり、状況に合わせて調整したいです⁴。 n 回目のリトライにおけるsleep時間は指数関数ですぐ求まりますが、一方で（ n でなく）経過時間をもとにsleep時間を知る・調整することは可能でしょうか？

例えば、処理開始からちょうど 1000 秒後にリトライがあるという前提で、

このリトライの前後のsleep時間は何秒でしょうか？
このリトライの前後のsleep時間を約 100 秒にするには、パラメーターをどう設定すればいいでしょうか？
- 必要以上に待ってしまう時間を、経過時間の 1/10 くらいに抑えたいという意図です。

問題設定

以降では、「初回のsleep時間」を a 、「伸ばす倍率」を r と置きます。リトライ回数 n における直前のsleep時間を t_n 、処理開始からの総経過時間¹を T_n とすれば、以下の表のようになります。

リトライ回数	直前のsleep時間	処理開始からの総経過時間
0	-	0
1	a	a
2	a r	a + a r
3	a r²	a + a r + a r²
…	…	…
n	t_n = a r^n-1	$T_{n} = \sum_{k=1}^{n} a r^{k-1}$
n+1	t_n+1 = a rⁿ	T_n+1
…	…	…

パラメーターおよび T_n （ n は未知）が与えられたときに、 t_n または t_n+1 を求められるでしょうか？
T_n において希望する t_n または t_n+1 （直前か直後のsleep時間）があるとき、パラメーターをどう決めればいいでしょうか？

具体例

例えばよくある a = 1, r = 2 だと以下のようになります。（時間の単位はひとまず秒とします）

リトライ回数	直前のsleep時間	総経過時間
0	-	0
1	1	1
2	2	3
3	4	7
…	…	…
10	t₁₀ = 512	T₁₀ = 1023
11	t₁₁ = 1024	T₁₁ = 2047
…	…	…

パラメーターおよび T_n = 1023 （ n は未知）が与えられたときに、 t_n = 512 または t_n+1 = 1024 を求められるでしょうか？
また、この例では 1030 秒後に処理成功するとしても 2047 秒後まで待ってしまいます。もう少し頻繁に、 1100 秒あたりでリトライを入れられないでしょうか？

計算

T_n は高校数学で習う 等比数列の和 そのものです。公式をそのまま使うなり、自力で導出するなり、すぐ総和記号の無い形が求まります。

T_{n} = a \cdot \frac{r^n - 1}{r - 1}

この結果に含まれている rⁿ をsleep時間のほうに使えば、経過時間 T_n から t_n+1 がすぐ求まります。（それを r で割れば t_n です）

\begin{align}
r^n &\;= 1 + \frac{r-1}{a} T_{n} \\
t_{n+1} &:= a r^n = a + (r-1) T_{n} \\
\end{align}

ちなみにリトライ回数 n は対数関数を使えば表せます。

n = \log_r{\frac{t_{n+1}}{a}} = \log_r{\left( 1 + \frac{r-1}{a} T_{n} \right)}

具体例で検算

a = 1, r = 2, T_n = 1023 で、前掲の表の通りの値が求まるか試してみます。

$t_{n+1} = a + (r-1) T_{n} = 1 + (2-1) \times 1023 = 1024$
$t_{n} = t_{n+1} / r = 1024 \div 2 = 512$
$n = \log_r{\left( t_{n+1} / a \right)} = \log_2{(1024 \div 1)} = 10$

合っていそうです。

式から見える性質

経過時間 T_n とその直後のsleep時間 t_n+1 に関する簡単な式が求まりました。 n は直接使わないので端折ってしまいます。

t(T) = a + (r-1) T

これは傾き (r-1) の一次関数です。 r > 1 のとき、 T が十分に大きくなれば a の寄与は無視できるようになり、 t(T) と T は比例関係とみなせます。

\frac{t(T)}{T} \simeq r-1

t(T) と T の比例関係を先に決めてから r を設定することもできます。もし T = 1000 のときに t(T) ≃ 100 （比率 0.1 ）としたいのなら、 r = 0.1 + 1 = 1.1 と設定すればいいことになります。

実際に確かめてみます（ a = 1 はそのままとします）。

リトライ回数	直前のsleep時間	総経過時間
0	-	0.000
1	1.000	1.000
2	1.100	2.100
3	1.210	3.310
…	…	…
48	88.197	960.172
49	97.017	1057.190
…	…	…

ちょうど T = 1000 にリトライがあるわけではないですが、 T = 960.172 の次のsleep時間が 97.017 と、ほぼ比率 0.1 となっています（式の通りちょうど a だけ差分があります）。

当然ながら注意点として、リトライ間隔を狭めればリトライ回数は増えます。 r から r_new に変更するとして大雑把に評価すると、 T_n ∼ a rⁿ なので、回数の比率は次のようになります。

\frac{n_\rm{new}}{n} \simeq \frac{\log{r}}{\log{r_\rm{new}}}

例えば r を 2 から 1.1 に変えた場合、同じ経過時間でのリトライ回数は 7 倍程度に増える恐れがあります。システムにかかる負荷が増えていいか考えながらパラメーターを調整する必要があります。
※ 他の項の影響があるため、実際に計るとこの値ほどの比率にならずに済みます。具体例の表を見比べると T = 1000 付近で 5 倍程度です。

簡単のため、リトライしたい処理そのものの時間は含めないとします。 ↩ ↩²
特に障害発生時に負荷をかけてしまうと、回復が遅れたり他へ飛び火したりする恐れがあります。 ↩
名前通り、指数関数（累乗） **, pow() を用いてリトライ回数から直接的に間隔を求めることもできます。 ↩
AWS SDK のように、サービス提供側で示しているリトライ処理があるのなら素直に従ったほうが良いかもしれません。 ↩