From eca25f374681ee19fb02bf1bb6f765009242fee4 Mon Sep 17 00:00:00 2001 From: David Garcia Quintas Date: Thu, 2 Nov 2017 14:52:54 -0700 Subject: Improvements to C Core's backoff code and API --- src/core/lib/backoff/backoff.cc | 73 ++++++++++++++++++++++------------------- src/core/lib/backoff/backoff.h | 55 ++++++++++++++++++++----------- 2 files changed, 76 insertions(+), 52 deletions(-) (limited to 'src/core/lib') diff --git a/src/core/lib/backoff/backoff.cc b/src/core/lib/backoff/backoff.cc index fe0a751817..5dd91da4f3 100644 --- a/src/core/lib/backoff/backoff.cc +++ b/src/core/lib/backoff/backoff.cc @@ -20,23 +20,27 @@ #include -void grpc_backoff_init(grpc_backoff *backoff, - grpc_millis initial_connect_timeout, double multiplier, - double jitter, grpc_millis min_timeout_millis, - grpc_millis max_timeout_millis) { - backoff->initial_connect_timeout = initial_connect_timeout; +void grpc_backoff_init(grpc_backoff *backoff, grpc_millis initial_backoff, + double multiplier, double jitter, + grpc_millis min_connect_timeout, + grpc_millis max_backoff) { + backoff->initial_backoff = initial_backoff; backoff->multiplier = multiplier; backoff->jitter = jitter; - backoff->min_timeout_millis = min_timeout_millis; - backoff->max_timeout_millis = max_timeout_millis; + backoff->min_connect_timeout = min_connect_timeout; + backoff->max_backoff = max_backoff; backoff->rng_state = (uint32_t)gpr_now(GPR_CLOCK_REALTIME).tv_nsec; } -grpc_millis grpc_backoff_begin(grpc_exec_ctx *exec_ctx, grpc_backoff *backoff) { - backoff->current_timeout_millis = backoff->initial_connect_timeout; - const grpc_millis first_timeout = - GPR_MAX(backoff->current_timeout_millis, backoff->min_timeout_millis); - return grpc_exec_ctx_now(exec_ctx) + first_timeout; +grpc_backoff_result grpc_backoff_begin(grpc_exec_ctx *exec_ctx, + grpc_backoff *backoff) { + backoff->current_backoff = backoff->initial_backoff; + const grpc_millis initial_timeout = + GPR_MAX(backoff->initial_backoff, backoff->min_connect_timeout); + const grpc_millis now = grpc_exec_ctx_now(exec_ctx); + const grpc_backoff_result result = {now + initial_timeout, + now + backoff->current_backoff}; + return result; } /* Generate a random number between 0 and 1. */ @@ -45,29 +49,32 @@ static double generate_uniform_random_number(uint32_t *rng_state) { return *rng_state / (double)((uint32_t)1 << 31); } -grpc_millis grpc_backoff_step(grpc_exec_ctx *exec_ctx, grpc_backoff *backoff) { - const double new_timeout_millis = - backoff->multiplier * (double)backoff->current_timeout_millis; - backoff->current_timeout_millis = - GPR_MIN((grpc_millis)new_timeout_millis, backoff->max_timeout_millis); - - const double jitter_range_width = backoff->jitter * new_timeout_millis; - const double jitter = - (2 * generate_uniform_random_number(&backoff->rng_state) - 1) * - jitter_range_width; - - backoff->current_timeout_millis = - (grpc_millis)((double)(backoff->current_timeout_millis) + jitter); - - const grpc_millis current_deadline = - grpc_exec_ctx_now(exec_ctx) + backoff->current_timeout_millis; - - const grpc_millis min_deadline = - grpc_exec_ctx_now(exec_ctx) + backoff->min_timeout_millis; +static double generate_uniform_random_number_between(uint32_t *rng_state, + double a, double b) { + if (a == b) return a; + if (a > b) GPR_SWAP(double, a, b); // make sure a < b + const double range = b - a; + return a + generate_uniform_random_number(rng_state) * range; +} - return GPR_MAX(current_deadline, min_deadline); +grpc_backoff_result grpc_backoff_step(grpc_exec_ctx *exec_ctx, + grpc_backoff *backoff) { + backoff->current_backoff = (grpc_millis)(GPR_MIN( + backoff->current_backoff * backoff->multiplier, backoff->max_backoff)); + const double jitter = generate_uniform_random_number_between( + &backoff->rng_state, -backoff->jitter * backoff->current_backoff, + backoff->jitter * backoff->current_backoff); + const grpc_millis current_timeout = + GPR_MAX((grpc_millis)(backoff->current_backoff + jitter), + backoff->min_connect_timeout); + const grpc_millis next_timeout = GPR_MIN( + (grpc_millis)(backoff->current_backoff + jitter), backoff->max_backoff); + const grpc_millis now = grpc_exec_ctx_now(exec_ctx); + const grpc_backoff_result result = {now + current_timeout, + now + next_timeout}; + return result; } void grpc_backoff_reset(grpc_backoff *backoff) { - backoff->current_timeout_millis = backoff->initial_connect_timeout; + backoff->current_backoff = backoff->initial_backoff; } diff --git a/src/core/lib/backoff/backoff.h b/src/core/lib/backoff/backoff.h index 80e49ea52a..8becf4aab8 100644 --- a/src/core/lib/backoff/backoff.h +++ b/src/core/lib/backoff/backoff.h @@ -27,36 +27,53 @@ extern "C" { typedef struct { /// const: how long to wait after the first failure before retrying - grpc_millis initial_connect_timeout; + grpc_millis initial_backoff; + /// const: factor with which to multiply backoff after a failed retry double multiplier; + /// const: amount to randomize backoffs double jitter; - /// const: minimum time between retries in milliseconds - grpc_millis min_timeout_millis; - /// const: maximum time between retries in milliseconds - grpc_millis max_timeout_millis; + + /// const: minimum time between retries + grpc_millis min_connect_timeout; + + /// const: maximum time between retries + grpc_millis max_backoff; + + /// current delay before retries + grpc_millis current_backoff; /// random number generator uint32_t rng_state; - - /// current retry timeout in milliseconds - grpc_millis current_timeout_millis; } grpc_backoff; +typedef struct { + /// Deadline to be used for the current attempt. + grpc_millis current_deadline; + + /// Deadline to be used for the next attempt, following the backoff strategy. + grpc_millis next_attempt_start_time; +} grpc_backoff_result; + /// Initialize backoff machinery - does not need to be destroyed -void grpc_backoff_init(grpc_backoff *backoff, - grpc_millis initial_connect_timeout, double multiplier, - double jitter, grpc_millis min_timeout_millis, - grpc_millis max_timeout_millis); - -/// Begin retry loop: returns a timespec for the NEXT retry -grpc_millis grpc_backoff_begin(grpc_exec_ctx *exec_ctx, grpc_backoff *backoff); -/// Step a retry loop: returns a timespec for the NEXT retry -grpc_millis grpc_backoff_step(grpc_exec_ctx *exec_ctx, grpc_backoff *backoff); +void grpc_backoff_init(grpc_backoff *backoff, grpc_millis initial_backoff, + double multiplier, double jitter, + grpc_millis min_connect_timeout, + grpc_millis max_backoff); + +/// Begin retry loop: returns the deadlines to be used for the current attempt +/// and the subsequent retry, if any. +grpc_backoff_result grpc_backoff_begin(grpc_exec_ctx *exec_ctx, + grpc_backoff *backoff); + +/// Step a retry loop: returns the deadlines to be used for the current attempt +/// and the subsequent retry, if any. +grpc_backoff_result grpc_backoff_step(grpc_exec_ctx *exec_ctx, + grpc_backoff *backoff); + /// Reset the backoff, so the next grpc_backoff_step will be a -/// grpc_backoff_begin -/// instead +/// grpc_backoff_begin. void grpc_backoff_reset(grpc_backoff *backoff); #ifdef __cplusplus -- cgit v1.2.3