Exponential backoff のパラメーターを調整するための目安を知りたくて、ざっと計算してみました。
TL;DR
表題の答えは、ほぼ比例関係です。 Tn を n 回目のリトライ実施時の経過時間1とすれば、その次のリトライまでの間隔（sleepする時間）は以下の式で表せます。
\begin{align}
T_{n+1} - T_{n} &:= a r^n \\
&\;= a + (r-1) T_{n} \\
\end{align}
（ a は初回のsleep時間、 r はその時間を伸ばしていく倍率）
通常 r > 1 なので、十分に時間が経過すると a を無視できて (Tn+1 - Tn) / Tn ≃ (r-1) となります。逆に言えば、希望する「経過時間とリトライ間隔の比率」があれば、そこから r を決められます。
はじめに
「処理が成功するまでリトライして待つ」ということが時々あります。単に非同期処理の完了を待つことだったり、確率的に失敗することへの対策だったり、依存システム（やネットワーク）の障害発生時に復旧するまで耐えることだったり。
このリトライは頻繁すぎると無駄に負荷がかかり2、少なすぎると必要以上に待ち続けてしまいます。処理成功までの時間が見当つかない場合に適切な頻度を決めるのは困難です。このバランスをうまくとる方法として、リトライ間隔（sleepの時間）を指数関数的に伸ばしていく exponential backoff があります。指数関数的と言うと難しそうですが、単純に 1秒 → 2秒 → 4秒 → 8秒 → … などと前回の間隔を定数倍することになります3。（実用的にはもう少し工夫を入れます）
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時間」と「伸ばす倍率」であり、状況に合わせて調整したいです4。 n 回目のリトライにおけるsleep時間は指数関数ですぐ求まりますが、一方で（ n でなく）経過時間をもとにsleep時間を知る・調整することは可能でしょうか？
例えば、処理開始からちょうど 1000 秒後にリトライがあるという前提で、
- このリトライの前後のsleep時間は何秒でしょうか？
- このリトライの前後のsleep時間を約 100 秒にするには、パラメーターをどう設定すればいいでしょうか？
- 必要以上に待ってしまう時間を、経過時間の 1/10 くらいに抑えたいという意図です。
問題設定
以降では、「初回のsleep時間」を a 、「伸ばす倍率」を r と置きます。リトライ回数 n における直前のsleep時間を tn 、処理開始からの総経過時間1を Tn とすれば、以下の表のようになります。
| リトライ回数 | 直前のsleep時間 | 処理開始からの総経過時間 |
|---|---|---|
| 0 | - | 0 |
| 1 | a | a |
| 2 | a r | a + a r |
| 3 | a r2 | a + a r + a r2 |
| … | … | … |
| n | tn = a rn-1 | $T_{n} = \sum_{k=1}^{n} a r^{k-1}$ |
| n+1 | tn+1 = a rn | Tn+1 |
| … | … | … |
- パラメーターおよび Tn （ n は未知）が与えられたときに、 tn または tn+1 を求められるでしょうか？
- Tn において希望する tn または tn+1 （直前か直後のsleep時間）があるとき、パラメーターをどう決めればいいでしょうか？
具体例
例えばよくある a = 1, r = 2 だと以下のようになります。（時間の単位はひとまず秒とします）
| リトライ回数 | 直前のsleep時間 | 総経過時間 |
|---|---|---|
| 0 | - | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 4 | 7 |
| … | … | … |
| 10 | t10 = 512 | T10 = 1023 |
| 11 | t11 = 1024 | T11 = 2047 |
| … | … | … |
- パラメーターおよび Tn = 1023 （ n は未知）が与えられたときに、 tn = 512 または tn+1 = 1024 を求められるでしょうか？
- また、この例では 1030 秒後に処理成功するとしても 2047 秒後まで待ってしまいます。もう少し頻繁に、 1100 秒あたりでリトライを入れられないでしょうか？
計算
Tn は高校数学で習う 等比数列の和 そのものです。公式をそのまま使うなり、自力で導出するなり、すぐ総和記号の無い形が求まります。
T_{n} = a \cdot \frac{r^n - 1}{r - 1}
この結果に含まれている rn をsleep時間のほうに使えば、経過時間 Tn から tn+1 がすぐ求まります。（それを r で割れば tn です）
\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, Tn = 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$
合っていそうです。
式から見える性質
経過時間 Tn とその直後のsleep時間 tn+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 から rnew に変更するとして大雑把に評価すると、 Tn ∼ a rn なので、回数の比率は次のようになります。
\frac{n_\rm{new}}{n} \simeq \frac{\log{r}}{\log{r_\rm{new}}}
例えば r を 2 から 1.1 に変えた場合、同じ経過時間でのリトライ回数は 7 倍程度に増える恐れがあります。システムにかかる負荷が増えていいか考えながらパラメーターを調整する必要があります。
※ 他の項の影響があるため、実際に計るとこの値ほどの比率にならずに済みます。具体例の表を見比べると T = 1000 付近で 5 倍程度です。