dca9ca20-d04b-4556-9d5e-54a876ecdd65

Committed 18 Feb 2025 04:38PM UTC coverage: 86.857% (-0.03%) from 86.888%

Build # dca9ca20-d04b-4556-9d5e-54a876ecdd65

Build Type

push

circleci

Committed by

web-flow

Commit Message

[Utils] Create exponential backoff utility class (#12264)

Coverage Stats

36 of 39 new or added lines in 1 file covered. (92.31%)

23 existing lines in 14 files now uncovered.

61541 of 70853 relevant lines covered (86.86%)

0.87 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.31

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

import random
import time

from pydantic import Field
from pydantic.dataclasses import dataclass


@dataclass
class ExponentialBackoff:
    """
    ExponentialBackoff implements exponential backoff with randomization.
    The backoff period increases exponentially for each retry attempt, with
    optional randomization within a defined range.

    next_backoff() is calculated using the following formula:
        ```
        randomized_interval = random_between(retry_interval * (1 - randomization_factor), retry_interval * (1 + randomization_factor))
        ```

    For example, given:
        `initial_interval` = 2
        `randomization_factor` = 0.5
        `multiplier` = 2

    The next backoff will be between 1 and 3 seconds (2 * [0.5, 1.5]).
    The following backoff will be between 2 and 6 seconds (4 * [0.5, 1.5]).

    Note:
        - `max_interval` caps the base interval, not the randomized value
        - Returns 0 when `max_retries` or `max_time_elapsed` is exceeded
        - The implementation is not thread-safe

    Example sequence with defaults (initial_interval=0.5, randomization_factor=0.5, multiplier=1.5):

    | Request # | Retry Interval (seconds) | Randomized Interval (seconds) |
    |-----------|----------------------|----------------------------|
    | 1         | 0.5                  | [0.25, 0.75]              |
    | 2         | 0.75                 | [0.375, 1.125]            |
    | 3         | 1.125                | [0.562, 1.687]            |
    | 4         | 1.687                | [0.8435, 2.53]            |
    | 5         | 2.53                 | [1.265, 3.795]            |
    | 6         | 3.795                | [1.897, 5.692]            |
    | 7         | 5.692                | [2.846, 8.538]            |
    | 8         | 8.538                | [4.269, 12.807]           |
    | 9         | 12.807               | [6.403, 19.210]           |
    | 10        | 19.210               | 0                         |

    Note: The sequence stops at request #10 when `max_retries` or `max_time_elapsed` is exceeded
    """

    initial_interval: float = Field(0.5, title="Initial backoff interval in seconds", gt=0)
    randomization_factor: float = Field(0.5, title="Factor to randomize backoff", ge=0, le=1)
    multiplier: float = Field(1.5, title="Multiply interval by this factor each retry", gt=1)
    max_interval: float = Field(60.0, title="Maximum backoff interval in seconds", gt=0)
    max_retries: int = Field(-1, title="Max retry attempts (-1 for unlimited)", ge=-1)
    max_time_elapsed: float = Field(-1, title="Max total time in seconds (-1 for unlimited)", ge=-1)

    def __post_init__(self):
        self.retry_interval: float = 0
        self.retries: int = 0
        self.start_time: float = 0.0

    @property
    def elapsed_duration(self) -> float:
        return max(time.monotonic() - self.start_time, 0)

    def reset(self) -> None:
        self.retry_interval = 0
        self.retries = 0
        self.start_time = 0

    def next_backoff(self) -> float:
        if self.retry_interval == 0:
            self.retry_interval = self.initial_interval
            self.start_time = time.monotonic()

        self.retries += 1

        # return 0 when max_retries is set and exceeded
        if self.max_retries >= 0 and self.retries > self.max_retries:
            return 0

        # return 0 when max_time_elapsed is set and exceeded
        if self.max_time_elapsed > 0 and self.elapsed_duration > self.max_time_elapsed:
            return 0

        next_interval = self.retry_interval
        if 0 < self.randomization_factor <= 1:
            min_interval = self.retry_interval * (1 - self.randomization_factor)
            max_interval = self.retry_interval * (1 + self.randomization_factor)
            # NOTE: the jittered value can exceed the max_interval
            next_interval = random.uniform(min_interval, max_interval)

        # do not allow the next retry interval to exceed max_interval
        self.retry_interval = min(self.max_interval, self.retry_interval * self.multiplier)

        return next_interval

1	import random	1✔
2	import time	1✔
3
4	from pydantic import Field	1✔
5	from pydantic.dataclasses import dataclass	1✔
6
7
8	@dataclass	1✔
9	class ExponentialBackoff:	1✔
10	"""
11	ExponentialBackoff implements exponential backoff with randomization.
12	The backoff period increases exponentially for each retry attempt, with
13	optional randomization within a defined range.
14
15	next_backoff() is calculated using the following formula:
16	```
17	randomized_interval = random_between(retry_interval * (1 - randomization_factor), retry_interval * (1 + randomization_factor))
18	```
19
20	For example, given:
21	`initial_interval` = 2
22	`randomization_factor` = 0.5
23	`multiplier` = 2
24
25	The next backoff will be between 1 and 3 seconds (2 * [0.5, 1.5]).
26	The following backoff will be between 2 and 6 seconds (4 * [0.5, 1.5]).
27
28	Note:
29	- `max_interval` caps the base interval, not the randomized value
30	- Returns 0 when `max_retries` or `max_time_elapsed` is exceeded
31	- The implementation is not thread-safe
32
33	Example sequence with defaults (initial_interval=0.5, randomization_factor=0.5, multiplier=1.5):
34
35	\| Request # \| Retry Interval (seconds) \| Randomized Interval (seconds) \|
36	\|-----------\|----------------------\|----------------------------\|
37	\| 1 \| 0.5 \| [0.25, 0.75] \|
38	\| 2 \| 0.75 \| [0.375, 1.125] \|
39	\| 3 \| 1.125 \| [0.562, 1.687] \|
40	\| 4 \| 1.687 \| [0.8435, 2.53] \|
41	\| 5 \| 2.53 \| [1.265, 3.795] \|
42	\| 6 \| 3.795 \| [1.897, 5.692] \|
43	\| 7 \| 5.692 \| [2.846, 8.538] \|
44	\| 8 \| 8.538 \| [4.269, 12.807] \|
45	\| 9 \| 12.807 \| [6.403, 19.210] \|
46	\| 10 \| 19.210 \| 0 \|
47
48	Note: The sequence stops at request #10 when `max_retries` or `max_time_elapsed` is exceeded
49	"""
50
51	initial_interval: float = Field(0.5, title="Initial backoff interval in seconds", gt=0)	1✔
52	randomization_factor: float = Field(0.5, title="Factor to randomize backoff", ge=0, le=1)	1✔
53	multiplier: float = Field(1.5, title="Multiply interval by this factor each retry", gt=1)	1✔
54	max_interval: float = Field(60.0, title="Maximum backoff interval in seconds", gt=0)	1✔
55	max_retries: int = Field(-1, title="Max retry attempts (-1 for unlimited)", ge=-1)	1✔
56	max_time_elapsed: float = Field(-1, title="Max total time in seconds (-1 for unlimited)", ge=-1)	1✔
57
58	def __post_init__(self):	1✔
59	self.retry_interval: float = 0	1✔
60	self.retries: int = 0	1✔
61	self.start_time: float = 0.0	1✔
62
63	@property	1✔
64	def elapsed_duration(self) -> float:	1✔
65	return max(time.monotonic() - self.start_time, 0)	1✔
66
67	def reset(self) -> None:	1✔
68	self.retry_interval = 0	1✔
69	self.retries = 0	1✔
70	self.start_time = 0	1✔
71
72	def next_backoff(self) -> float:	1✔
73	if self.retry_interval == 0:	1✔
74	self.retry_interval = self.initial_interval	1✔
75	self.start_time = time.monotonic()	1✔
76
77	self.retries += 1	1✔
78
79	# return 0 when max_retries is set and exceeded
80	if self.max_retries >= 0 and self.retries > self.max_retries:	1✔
81	return 0	1✔
82
83	# return 0 when max_time_elapsed is set and exceeded
84	if self.max_time_elapsed > 0 and self.elapsed_duration > self.max_time_elapsed:	1✔
85	return 0	1✔
86
87	next_interval = self.retry_interval	1✔
88	if 0 < self.randomization_factor <= 1:	1✔
NEW 89	min_interval = self.retry_interval * (1 - self.randomization_factor)	×
NEW 90	max_interval = self.retry_interval * (1 + self.randomization_factor)	×
91	# NOTE: the jittered value can exceed the max_interval
NEW 92	next_interval = random.uniform(min_interval, max_interval)	×
93
94	# do not allow the next retry interval to exceed max_interval
95	self.retry_interval = min(self.max_interval, self.retry_interval * self.multiplier)	1✔
96
97	return next_interval	1✔

localstack / localstack / dca9ca20-d04b-4556-9d5e-54a876ecdd65

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous