8000 [util] Create exponential backoff utility class · localstack/localstack@06bdefc · GitHub
[go: up one dir, main page]
Skip to content

Commit 06bdefc

Browse files
gregfurmangregfurman
committed
[util] Create exponential backoff utility class
1 parent 57aeecb commit 06bdefc

File tree

2 files changed

+192
-0
lines changed

2 files changed

+192
-0
lines changed

‎localstack-core/localstack/utils/backoff.py

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
import random
2+
import time
3+
from dataclasses import dataclass
4+
5+
6+
@dataclass
7+
class ExponentialBackoff:
8+
initial_interval: float = 0.5 # 500ms
9+
jitter_factor: float = 0.5
10+
multiplier: float = 1.5
11+
max_interval: float = 60.0 # 60 seconds
12+
13+
max_retries: int = -1 # infinite
14+
max_time_elapsed: float = -1 # infinite
15+
16+
def __post_init__(self):
17+
self.current_interval: float = 0
18+
self.retries: int = 0
19+
self.start_t: float = 0.0
20+
21+
@property
22+
def elapsed_duration(self) -> float:
23+
return max(time.monotonic() - self.start_t, 0)
24+
25+
def reset(self) -> None:
26+
self.current_interval = 0
27+
self.retries = 0
28+
self.start_t = 0
29+
30+
def next_backoff(self) -> float:
31+
if self.current_interval == 0:
32+
self.current_interval = self.initial_interval
33+
self.start_t = time.monotonic()
34+
35+
self.retries += 1
36+
37+
# return 0 when max_retries is set and exceeded
38+
if self.max_retries >= 0 and self.retries > self.max_retries:
39+
return 0
40+
41+
# return 0 when max_time_elapsed is set and exceeded
42+
if self.max_time_elapsed > 0 and self.elapsed_duration > self.max_time_elapsed:
43+
return 0
44+
45+
next_interval = self.current_interval
46+
47+
jitter = 0
48+
if 0 < self.jitter_factor <= 1:
49+
min_interval = self.current_interval < 10000 span class=pl-c1>* (1 - self.jitter_factor)
50+
max_interval = self.current_interval * (1 + self.jitter_factor)
51+
# NOTE: the jittered value can exceed the max_interval
52+
jitter = random.uniform(max_interval, min_interval)
53+
54+
# do not allow the next current interval to exceed max_interval
55+
self.current_interval = min(self.max_interval, self.current_interval * self.multiplier)
56+
57+
return next_interval + jitter

‎tests/unit/utils/test_backoff.py

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
import time
2+
import unittest
3+
4+
from localstack.utils.backoff import ExponentialBackoff
5+
6+
7+
class TestExponentialBackoff(unittest.TestCase):
8+
def test_next_backoff(self):
9+
initial_expected_backoff = 0.5 # 500ms
10+
multiplication_factor = 1.5 # increase by x1.5 each iteration
11+
12+
boff = ExponentialBackoff(jitter_factor=0) # no jitter for deterministic testing
13+
14+
backoff_duration_iter_1 = boff.next_backoff()
15+
self.assertEqual(backoff_duration_iter_1, initial_expected_backoff)
16+
17+
backoff_duration_iter_2 = boff.next_backoff()
18+
self.assertEqual(backoff_duration_iter_2, initial_expected_backoff * multiplication_factor)
19+
20+
backoff_duration_iter_3 = boff.next_backoff()
21+
self.assertEqual(
22+
backoff_duration_iter_3, initial_expected_backoff * multiplication_factor**2
23+
)
24+
25+
def test_backoff_retry_limit(self):
26+
initial_expected_backoff = 0.5
27+
max_retries_before_stop = 1
28+
29+
boff = ExponentialBackoff(jitter_factor=0, max_retries=max_retries_before_stop)
30+
31+
self.assertEqual(boff.next_backoff(), initial_expected_backoff)
32+
33+
# max_retries exceeded, only 0 should be returned until reset() called
34+
self.assertEqual(boff.next_backoff(), 0)
35+
self.assertEqual(boff.next_backoff(), 0)
36+
37+
# reset backoff
38+
boff.reset()
39+
40+
self.assertEqual(boff.next_backoff(), initial_expected_backoff)
41+
self.assertEqual(boff.next_backoff(), 0)
42+
43+
def test_backoff_retry_limit_disable_retries(self):
44+
boff = ExponentialBackoff(jitter_factor=0, max_retries=0)
45+
46+
# zero max_retries means backoff will always fail
47+
self.assertEqual(boff.next_backoff(), 0)
48+
49+
# reset backoff
50+
boff.reset()
51+
52+
# reset has no effect since backoff is disabled
53+
self.assertEqual(boff.next_backoff(), 0)
54+
55+
def test_backoff_time_elapsed_limit(self):
56+
initial_expected_backoff = 0.5
57+
multiplication_factor = 1.5 # increase by x1.5 each iteration
58+
59+
max_time_elapsed_s_before_stop = 1.0
60+
61+
boff = ExponentialBackoff(jitter_factor=0, max_time_elapsed=max_time_elapsed_s_before_stop)
62+
self.assertEqual(boff.next_backoff(), initial_expected_backoff)
63+
self.assertEqual(boff.next_backoff(), initial_expected_backoff * multiplication_factor)
64+
65+
# sleep for 1s
66+
time.sleep(1)
67+
68+
# max_time_elapsed exceeded, only 0 should be returned until reset() called
69+
self.assertEqual(boff.next_backoff(), 0)
70+
self.assertEqual(boff.next_backoff(), 0)
71+
72+
# reset backoff
73+
boff.reset()
74+
75+
self.assertEqual(boff.next_backoff(), initial_expected_backoff)
76+
self.assertEqual(boff.next_backoff(), initial_expected_backoff * multiplication_factor)
77+
78+
def test_backoff_elapsed_limit_reached_before_retry_limit(self):
79+
initial_expected_backoff = 0.5
80+
multiplication_factor = 1.5
81+
82+
max_retries_before_stop = 4
83+
max_time_elasped_s_before_stop = 2.0
84+
85+
boff = ExponentialBackoff(
86+
jitter_factor=0,
87+
max_retries=max_retries_before_stop,
88+
max_time_elapsed=max_time_elasped_s_before_stop,
89+
)
90+
91+
total_duration = 0
92+
for retry in range(2):
93+
backoff_duration = boff.next_backoff()
94+
expected_duration = initial_expected_backoff * multiplication_factor**retry
95+
self.assertEqual(backoff_duration, expected_duration)
96+
97+
# Sleep for backoff
98+
time.sleep(backoff_duration)
99+
total_duration += backoff_duration
100+
101+
self.assertLess(total_duration, max_time_elasped_s_before_stop)
102+
103+
# sleep for remainder of wait time...
104+
time.sleep(max_time_elasped_s_before_stop - total_duration)
105+
106+
# max_retries exceeded, only 0 should be returned until reset() called
107+
self.assertEqual(boff.next_backoff(), 0)
108+
109+
def test_backoff_retry_limit_reached_before_elapsed_limit(self):
110+
initial_expected_backoff = 0.5
111+
multiplication_factor = 1.5
112+
113+
max_retries_before_stop = 3
114+
max_time_elasped_s_before_stop = 3.0
115+
116+
boff = ExponentialBackoff(
117+
jitter_factor=0,
118+
max_retries=max_retries_before_stop,
119+
max_time_elapsed=max_time_elasped_s_before_stop,
120+
)
121+
122+
total_duration = 0
123+
for retry in range(max_retries_before_stop):
124+
backoff_duration = boff.next_backoff()
125+
expected_duration = initial_expected_backoff * multiplication_factor**retry
126+
self.assertEqual(backoff_duration, expected_duration)
127+
128+
# Sleep for backoff
129+
time.sleep(backoff_duration)
130+
total_duration += backoff_duration
131+
132+
self.assertLess(total_duration, max_time_elasped_s_before_stop)
133+
134+
# max_retries exceeded, only 0 should be returned until reset() called
135+
self.assertEqual(boff.next_backoff(), 0)

0 commit comments

Comments
 (0)
0