Skip to content

Instantly share code, notes, and snippets.

@flisboac
Last active August 12, 2022 13:47
Show Gist options
  • Save flisboac/a40eefc02772ad9f5aa3bd3b46b157ef to your computer and use it in GitHub Desktop.
Save flisboac/a40eefc02772ad9f5aa3bd3b46b157ef to your computer and use it in GitHub Desktop.
backoff.dart
import 'dart:async';
import 'dart:collection';
import 'dart:math';
import 'package:collection/collection.dart';
class BackoffDelay {
static const zero = BackoffDelay(
baseDuration: Duration.zero,
jitterDuration: Duration.zero,
duration: Duration.zero,
);
/// O tempo de espera atual.
final Duration baseDuration;
/// O tempo de espera atual.
final Duration jitterDuration;
/// O tempo de espera atual.
final Duration duration;
/// Contagem de quantas chamadas foram realizadas até o momento.
///
/// Se não foi realizada nenhuma **chamada** até o momento, `retryCount == 0`.
/// (ie. não houve nenhuma tentativa, esta será a primeira chamada).
///
/// Se não foi realizada nenhuma **espera** até o momento, `retryCount == 1`.
/// (ie. houve ao menos uma tentativa, e esta será a primeira espera/retentativa).
final int retryCount;
const BackoffDelay({
required this.baseDuration,
required this.jitterDuration,
required this.duration,
this.retryCount = 0,
});
const BackoffDelay.ofBaseDuration(this.baseDuration, {this.retryCount = 0})
: duration = baseDuration,
jitterDuration = Duration.zero;
BackoffDelay next({
required Duration duration,
required Duration baseDuration,
required Duration jitterDuration,
}) {
return BackoffDelay(
baseDuration: baseDuration,
jitterDuration: jitterDuration,
duration: duration,
retryCount: retryCount + 1,
);
}
}
abstract class Backoff {
/// Reinicia a contagem e valor dos delays.
///
/// Após a execução de `resetDelays()`, a próxima chamada à
/// `getNextDelay()` terá resultado similar à primeira execução deste.
/// (ie. como se fosse a primeira chamada à `getNextDelay()`).
void reset();
/// Calcula o próximo tempo de espera.
BackoffDelay nextDelay();
}
typedef OnCalculateBackoffDelay = Duration Function(
BackoffDelay previousDelay, CustomizableBackoff backoff);
typedef OnCalculateBackoffJitter = Duration Function(
Duration currentBaseDuration, CustomizableBackoff backoff);
typedef OnGenerateValue<T> = FutureOr<T> Function();
typedef OnStopIf<T> = FutureOr<bool> Function(
T result,
BackoffDelay current,
);
typedef OnRetryIf<T> = FutureOr<bool> Function(
dynamic error,
BackoffDelay current,
);
typedef OnRegenerateIf<T> = FutureOr<bool> Function(
T result,
BackoffDelay current,
);
class CustomizableBackoff extends Backoff {
/// Tempo de espera base, ou inicial.
final Duration initialDuration;
/// Tempo de espera mínimo, se houver.
final Duration? minDuration;
/// Tempo de espera máximo, se houver.
final Duration? maxDuration;
/// Tempo de espera adicionado a cada cálculo.
final OnCalculateBackoffJitter onCalculateJitter;
/// Tempo de espera adicionado a cada cálculo.
final OnCalculateBackoffDelay onCalculateDelay;
/// Indica se a primeira execução deve ser imediata.
final bool immediate;
/// Número máximo de execuções armazenadas.
final int maxHistorySize;
QueueList<BackoffDelay> get history => _history;
int get retryCount => _current != null ? _current!.retryCount : 0;
final QueueList<BackoffDelay> _history = QueueList<BackoffDelay>();
BackoffDelay? _current;
CustomizableBackoff({
Duration? initialDuration,
this.minDuration,
this.maxDuration = defaultMaxDelayDuration,
this.maxHistorySize = defaultMaxHistorySize,
OnCalculateBackoffDelay? onCalculateDelay,
this.onCalculateJitter = defaultJitter,
this.immediate = _defaultImmediate,
}) : initialDuration = initialDuration ?? defaultInitialDelayDuration,
this.onCalculateDelay = onCalculateDelay ?? defaultDelay();
@override
void reset() {
_current = null;
_history.clear();
}
@override
BackoffDelay nextDelay() {
if (_current != null) {
_addToHistory(_current!);
if (immediate && _current!.retryCount == 0) {
_current = BackoffDelay.ofBaseDuration(
initialDuration,
retryCount: 1,
);
} else {
_current = _calculateNextDelay(_current!);
}
} else if (immediate) {
_current = BackoffDelay.zero;
} else {
_current = BackoffDelay.ofBaseDuration(initialDuration);
}
return _current!;
}
Duration clampDuration(Duration duration) {
return _clampDuration(
duration,
minDuration ?? duration,
maxDuration ?? duration,
);
}
BackoffDelay _calculateNextDelay(BackoffDelay previousDelay) {
assert(_current != null);
Duration baseDuration = _doCalculateDuration(previousDelay);
Duration jitterDuration = _doCalculateJitter(baseDuration);
Duration duration = baseDuration + jitterDuration;
duration = clampDuration(duration);
return _current!.next(
baseDuration: baseDuration,
jitterDuration: jitterDuration,
duration: duration,
);
}
Duration _doCalculateDuration(BackoffDelay previousDelay) {
return onCalculateDelay(previousDelay, this);
}
Duration _doCalculateJitter(Duration currentDuration) {
return onCalculateJitter(currentDuration, this);
}
void _addToHistory(BackoffDelay delay) async {
_history.add(delay);
int endIndex = _history.length - maxHistorySize;
if (endIndex > 0) {
_history.removeRange(0, endIndex);
}
}
}
const Duration defaultInitialDelayDuration = Duration(milliseconds: 100);
const Duration defaultMaxDelayDuration =
Duration(microseconds: 9007199254740991);
const double defaultJitterFactor = 0.20;
const int unlimitedRetries = -1;
const bool _defaultImmediate = true;
const int defaultMaxHistorySize = 5;
const defaultJitter = defaultRandomJitter;
Duration _minDurationOf(Duration lhs, Duration rhs) {
return lhs == rhs
? lhs
: lhs.compareTo(rhs) <= 0
? lhs
: rhs;
}
Duration _maxDurationOf(Duration lhs, Duration rhs) {
return lhs == rhs
? lhs
: lhs.compareTo(rhs) >= 0
? lhs
: rhs;
}
Duration _clampDuration(Duration duration, Duration min, Duration max) {
return _minDurationOf(_maxDurationOf(duration, min), max);
}
Duration _generateRandomDuration(Duration min, Duration max) {
assert(max >= min);
if (max == min) {
return max;
}
int usMin = min.inMicroseconds;
int usMax = max.inMicroseconds;
int usDiff = (usMax - usMin).abs();
int usValue = usMin + Random().nextInt(usDiff);
Duration value = Duration(microseconds: usValue);
return value;
}
OnCalculateBackoffDelay defaultDelay() {
return fibonacciDelay();
}
Duration noDelay(
BackoffDelay previousDelay,
CustomizableBackoff backoff,
) {
return Duration.zero;
}
Duration sameDelay(
BackoffDelay previousDelay,
CustomizableBackoff backoff,
) {
return previousDelay.baseDuration;
}
OnCalculateBackoffDelay fibonacciDelay() {
return (BackoffDelay previousDelay, CustomizableBackoff backoff) {
BackoffDelay first = backoff.history.length > 1
? backoff.history[backoff.history.length - 2]
: BackoffDelay.zero;
BackoffDelay second = backoff.history.isNotEmpty
? backoff.history.last
: BackoffDelay.ofBaseDuration(backoff.initialDuration);
return first.baseDuration + second.baseDuration;
};
}
OnCalculateBackoffDelay incrementalDelay({
Duration add = Duration.zero,
bool exponential = false,
}) {
return (BackoffDelay previousDelay, CustomizableBackoff backoff) {
num factorInc = boolToInt(!backoff.immediate) + boolToInt(!exponential);
num factor = min(backoff.retryCount + factorInc, pow(2, 31));
num mult = factor;
if (exponential) {
mult = pow(2, min(factor, 31));
}
Duration delay = backoff.initialDuration * mult;
delay += add;
return delay;
};
}
OnCalculateBackoffDelay cumulativeDelay({
Duration add = Duration.zero,
bool exponential = false,
}) {
return (BackoffDelay previousDelay, CustomizableBackoff backoff) {
num factorInc = boolToInt(!!backoff.immediate) + boolToInt(!exponential);
num factor = min(backoff.retryCount + factorInc, pow(2, 31));
num mult = factor;
if (exponential) {
mult = pow(2, min(factor, 31));
}
Duration previousDuration = previousDelay.baseDuration;
previousDuration += backoff.initialDuration * mult;
previousDuration += add;
return previousDuration;
};
}
Duration noJitter(
Duration delay,
CustomizableBackoff backoff,
) {
return Duration.zero;
}
OnCalculateBackoffJitter randomJitter({
List<Duration Function(Duration)>? limits,
List<double>? factors,
double? factor,
List<Duration>? absoluteLimits,
}) {
assert(factor == null || (factor <= 1 && factor >= 0));
return (Duration duration, CustomizableBackoff backoff) {
Duration minJitter = duration - duration * defaultJitterFactor;
Duration maxJitter = duration + duration * defaultJitterFactor;
if (limits != null) {
minJitter = limits[0](duration);
maxJitter = limits[1](duration);
} else if (factors != null) {
minJitter = duration * factors[0];
maxJitter = duration * factors[1];
} else if (factor != null) {
minJitter = duration - duration * factor;
maxJitter = duration + duration * factor;
}
if (absoluteLimits != null) {
minJitter = _maxDurationOf(minJitter, absoluteLimits[0]);
maxJitter = _minDurationOf(maxJitter, absoluteLimits[1]);
}
Duration jitter = _generateRandomDuration(minJitter, maxJitter);
return jitter;
};
}
Duration defaultRandomJitter(
Duration currentDuration,
CustomizableBackoff backoff,
) {
Duration jitter = _generateRandomDuration(
currentDuration - currentDuration * defaultJitterFactor,
currentDuration + currentDuration * defaultJitterFactor,
);
return jitter;
}
Backoff backoff({
Duration? initialDuration,
Duration? minDuration,
Duration? maxDuration,
OnCalculateBackoffDelay? delay,
OnCalculateBackoffJitter jitter = defaultJitter,
bool immediate = _defaultImmediate,
int maxHistorySize = defaultMaxHistorySize,
}) {
return CustomizableBackoff(
onCalculateDelay: delay ?? defaultDelay(),
onCalculateJitter: jitter,
initialDuration: initialDuration,
minDuration: minDuration,
maxDuration: maxDuration,
immediate: immediate,
maxHistorySize: maxHistorySize,
);
}
int boolToInt(bool value) {
return value ? 1 : 0;
}
FutureOr<bool> _selectFirst<T>(
T result,
BackoffDelay current,
) {
return true;
}
FutureOr<bool> _rethrowIfError<T>(
dynamic error,
BackoffDelay current,
) {
return error != null;
}
FutureOr<bool> _regenerateIfNoError<T>(
T? result,
dynamic error,
BackoffDelay current,
) {
return error != null;
}
FutureOr<bool> _noRegenerate<T>(
T result,
BackoffDelay current,
) {
return false;
}
const _defaultBackoff = backoff;
Backoff noBackoff({
OnCalculateBackoffJitter jitter = noJitter,
}) {
return backoff(
delay: noDelay,
jitter: jitter,
immediate: true,
initialDuration: Duration.zero,
maxHistorySize: 0,
);
}
Future<T> tryGet<T>(
OnGenerateValue<T> generator, {
Backoff? backoff,
OnStopIf<T>? stopIf,
OnRetryIf<T>? retryIf,
OnRegenerateIf<T>? regenerateIf,
int maxRetries = unlimitedRetries,
}) async {
backoff ??= _defaultBackoff();
stopIf ??= _selectFirst;
retryIf ??= _rethrowIfError;
regenerateIf ??= _noRegenerate;
while (true) {
BackoffDelay current = backoff.nextDelay();
await Future.delayed(current.duration);
bool maxRetriesExceeded =
(maxRetries >= 0 && current.retryCount >= maxRetries);
dynamic error;
bool generated = false;
try {
T currentResult = await generator();
generated = true;
bool stopping = await stopIf(
currentResult,
current,
);
if (stopping) {
return currentResult;
}
bool regenerating = await regenerateIf(
currentResult,
current,
);
if (!regenerating) {
throw Exception("Could not fetch a suitable value.");
}
} catch (e) {
if (!generated) {
rethrow;
}
bool retrying = await error(
error,
current,
);
if (!retrying) {
rethrow;
}
error = e;
}
if (maxRetriesExceeded) {
throw Exception("Maximum number of tries reached or exceeded.");
}
}
}
Future<void> waitForCondition(
OnGenerateValue<bool> condition, {
Backoff? backoff,
OnRetryIf<bool>? retryIf,
OnRegenerateIf<bool>? regenerateIf,
int maxRetries = unlimitedRetries,
}) async {
await tryGet(
condition,
backoff: backoff,
stopIf: (bool result, _) => result,
retryIf: retryIf,
regenerateIf: regenerateIf,
maxRetries: maxRetries,
);
}
void main() {
Backoff b = backoff(
initialDuration: Duration(seconds: 1),
delay: incrementalDelay(exponential: true),
jitter: noJitter,
immediate: true,
);
for (int i = 0; i < 8; ++i) {
BackoffDelay delay = b.nextDelay();
print([ delay.retryCount, delay.duration ]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment