googleapis · alevenberg · May 26, 2023 · May 18, 2023 · May 18, 2023 · May 18, 2023
@@ -20,8 +20,9 @@ GOOGLE_CLOUD_CPP_INLINE_NAMESPACE_BEGIN
 namespace internal {
 
 std::unique_ptr<BackoffPolicy> ExponentialBackoffPolicy::clone() const {
-  return std::make_unique<ExponentialBackoffPolicy>(initial_delay_,
-                                                    maximum_delay_, scaling_);
+  return std::make_unique<ExponentialBackoffPolicy>(
+      minimum_delay_, initial_delay_upper_bound_, maximum_delay_,
+      scaling_lower_bound_, scaling_upper_bound_);
 }
 
 std::chrono::milliseconds ExponentialBackoffPolicy::OnCompletion() {
@@ -39,19 +40,20 @@ std::chrono::milliseconds ExponentialBackoffPolicy::OnCompletion() {
     generator_ = google::cloud::internal::MakeDefaultPRNG();
   }
 
-  if (current_delay_end_ >= maximum_delay_) {
-    current_delay_start_ = std::max(maximum_delay_ / scaling_, initial_delay_);
-    current_delay_end_ = maximum_delay_;
+  if (current_delay_start_ >= (maximum_delay_ / scaling_upper_bound_)) {
+    current_delay_start_ =
+        (std::max)(minimum_delay_, maximum_delay_ / scaling_upper_bound_);
   }
+  current_delay_end_ = (std::min)(current_delay_end_, maximum_delay_);
 
   std::uniform_real_distribution<DoubleMicroseconds::rep> rng_distribution(
       current_delay_start_.count(), current_delay_end_.count());
   // Randomized sleep period because it is possible that after some time all
   // client have same sleep period if we use only exponential backoff policy.
   auto delay = DoubleMicroseconds(rng_distribution(*generator_));
 
-  current_delay_start_ = current_delay_end_;
-  current_delay_end_ *= scaling_;
+  current_delay_start_ *= scaling_lower_bound_;
+  current_delay_end_ *= scaling_upper_bound_;
 
   return std::chrono::duration_cast<std::chrono::milliseconds>(delay);
 }

@@ -73,15 +73,17 @@ class BackoffPolicy {
 };
 
 /**
- * Implements a truncated exponential backoff with randomization policy.
+ * Implements a truncated exponential backoff with randomization policy and a
+ * minimum delay.
  *
  * This policy implements the truncated exponential backoff policy for
  * retrying operations. After a request fails, and subject to a separate
- * retry policy, the client library will wait for an initial delay before
- * trying again. If the second attempt fails the delay time is increased,
- * using an scaling factor. The delay time growth stops at a maximum delay
- * wait time. The policy also randomizes the delay each time, to avoid
- * [thundering herd
+ * retry policy, the client library will wait for an initial delay after
+ * the specified minimum delay before trying again. If the second attempt fails
+ * the delay time is increased, using a scaling factor. The delay time begins at
+ * the minimum delay. The delay time growth stops at a
+ * maximum delay time. The policy also randomizes the delay each time, to
+ * avoid the [thundering herd
  * problem](https://en.wikipedia.org/wiki/Thundering_herd_problem).
  */
 class ExponentialBackoffPolicy : public BackoffPolicy {
@@ -100,21 +102,22 @@ class ExponentialBackoffPolicy : public BackoffPolicy {
    * auto r2 = ExponentialBackoffPolicy<S,T>(10min, 10min + 2s, 1.002);
    * @endcode
    *
-   * @param initial_delay how long to wait after the first (unsuccessful)
-   *     operation and the minimum value for the delay between operations.
+   * @param initial_delay the longest possible delay after the first
+   *     (unsuccessful) operation and the minimum value for the delay between
+   *     operations.
    * @param maximum_delay the maximum value for the delay between operations.
    * @param scaling how fast does the delay increase between iterations.
    *
-   * @tparam Rep1 a placeholder to match the Rep tparam for @p initial_delay's
-   *     type, the semantics of this template parameter are documented in
-   *     `std::chrono::duration<>` (in brief, the underlying arithmetic type
-   *     used to store the number of ticks), for our purposes it is simply a
-   *     formal parameter.
+   * @tparam Rep1 a placeholder to match the Rep tparam for
+   *     @p initial_delay's type. The semantics of this template parameter
+   *     are documented in `std::chrono::duration<>` (in brief, the underlying
+   *     arithmetic type used to store the number of ticks). For our purposes,
+   *     it is simply a formal parameter.
    * @tparam Period1 a placeholder to match the Period tparam for
-   *     @p initial_delay's type, the semantics of this template parameter are
-   *     documented in `std::chrono::duration<>` (in brief, the length of the
-   *     tick in seconds, expressed as a `std::ratio<>`), for our purposes it
-   *     is simply a formal parameter.
+   *     @p initial_delay's type. The semantics of this template parameter
+   *     are documented in `std::chrono::duration<>` (in brief, the underlying
+   *     arithmetic type used to store the number of ticks). For our purposes,
+   *     it is simply a formal parameter.
    * @tparam Rep2 similar formal parameter for the type of @p maximum_delay.
    * @tparam Period2 similar formal parameter for the type of @p maximum_delay.
    *
@@ -126,14 +129,81 @@ class ExponentialBackoffPolicy : public BackoffPolicy {
   ExponentialBackoffPolicy(std::chrono::duration<Rep1, Period1> initial_delay,
                            std::chrono::duration<Rep2, Period2> maximum_delay,
                            double scaling)
-      : initial_delay_(initial_delay),
+      : ExponentialBackoffPolicy(initial_delay, initial_delay * scaling,
+                                 maximum_delay, scaling, scaling) {}
+
+  /**
+   * Constructor for an exponential backoff policy that supports full jitter.
+   *
+   * Define a policy with a customizable delay intervals and scaling factors.
+   * While the constructor accepts `std::chrono::duration` objects at any
+   * resolution, the data is kept internally in microseconds. Sub-microsecond
+   * delays seem unnecessarily precise for this application.
+   *
+   * @code
+   * using namespace std::chrono_literals; // C++14
+   * auto r1 = ExponentialBackoffPolicy<S,T>(0ms, 10ms, 500ms, 1.0, 1.618);
+   * @endcode
+   *
+   * @param minimum_delay the minimum value for the delay between operations.
+   * @param initial_delay_upper_bound the longest possible delay to wait after
+   *     the first (unsuccessful) operation.
+   * @param maximum_delay the maximum value for the delay between operations.
+   * @param scaling_lower_bound how fast the delay's lower bound increases
+   *     between iterations.
+   * @param scaling_upper_bound how fast the delay's upper bound increases
+   *     between iterations.
+   *
+   * @tparam Rep1 a placeholder to match the Rep tparam for
+   *     @p minimum_delay's type. The semantics of this template
+   *     parameter are documented in `std::chrono::duration<>` (in brief, the
+   *     underlying arithmetic type used to store the number of ticks). For our
+   *     purposes, it is simply a formal parameter.
+   * @tparam Period1 a placeholder to match the Period tparam for
+   *     @p minimum_delay's type. The semantics of this template
+   *     parameter are documented in `std::chrono::duration<>` (in brief, the
+   *     underlying arithmetic type used to store the number of ticks). For our
+   *     purposes, it is simply a formal parameter.
+   * @tparam Rep2 similar formal parameter for the type of
+   *    @p initial_delay_upper_bound.
+   * @tparam Period2 similar formal parameter for the type of
+   *    @p initial_delay_upper_bound.
+   * @tparam Rep3 similar formal parameter for the type of @p maximum_delay.
+   * @tparam Period3 similar formal parameter for the type of @p maximum_delay.
+   *
+   * @see
+   * [std::chrono::duration<>](http://en.cppreference.com/w/cpp/chrono/duration)
+   *     for more details.
+   */
+  template <typename Rep1, typename Period1, typename Rep2, typename Period2,
+            typename Rep3, typename Period3>
+  ExponentialBackoffPolicy(
+      std::chrono::duration<Rep1, Period1> minimum_delay,
+      std::chrono::duration<Rep2, Period2> initial_delay_upper_bound,
+      std::chrono::duration<Rep3, Period3> maximum_delay,
+      double scaling_lower_bound, double scaling_upper_bound)
+      : minimum_delay_(minimum_delay),
+        initial_delay_upper_bound_(initial_delay_upper_bound),
         maximum_delay_(maximum_delay),
-        scaling_(scaling),
-        current_delay_start_(initial_delay_),
-        current_delay_end_(scaling_ * initial_delay_) {
-    if (scaling_ <= 1.0) {
+        scaling_lower_bound_(scaling_lower_bound),
+        scaling_upper_bound_(scaling_upper_bound),
+        current_delay_start_(minimum_delay_),
+        current_delay_end_(initial_delay_upper_bound_) {
+    if (initial_delay_upper_bound_ < minimum_delay_) {
+      google::cloud::internal::ThrowInvalidArgument(
+          "initial delay upper bound must be >= minimum delay");
+    }
+    if (scaling_lower_bound_ < 1.0) {
+      google::cloud::internal::ThrowInvalidArgument(
+          "scaling lower bound factor must be >= 1.0");
+    }
+    if (scaling_upper_bound_ <= 1.0) {
+      google::cloud::internal::ThrowInvalidArgument(
+          "scaling upper bound factor must be > 1.0");
+    }
+    if (scaling_lower_bound > scaling_upper_bound) {
       google::cloud::internal::ThrowInvalidArgument(
-          "scaling factor must be > 1.0");
+          "scaling lower bound must be <= scaling upper bound");
     }
   }
 
@@ -142,9 +212,11 @@ class ExponentialBackoffPolicy : public BackoffPolicy {
   //    know specifically which one is at fault)
   //  - We want uncorrelated data streams for each copy anyway.
   ExponentialBackoffPolicy(ExponentialBackoffPolicy const& rhs) noexcept
-      : initial_delay_(rhs.initial_delay_),
+      : minimum_delay_(rhs.minimum_delay_),
+        initial_delay_upper_bound_(rhs.initial_delay_upper_bound_),
         maximum_delay_(rhs.maximum_delay_),
-        scaling_(rhs.scaling_),
+        scaling_lower_bound_(rhs.scaling_lower_bound_),
+        scaling_upper_bound_(rhs.scaling_upper_bound_),
         current_delay_start_(rhs.current_delay_start_),
         current_delay_end_(rhs.current_delay_end_) {}
 
@@ -153,9 +225,11 @@ class ExponentialBackoffPolicy : public BackoffPolicy {
 
  private:
   using DoubleMicroseconds = std::chrono::duration<double, std::micro>;
-  DoubleMicroseconds initial_delay_;
+  DoubleMicroseconds minimum_delay_;
+  DoubleMicroseconds initial_delay_upper_bound_;
   DoubleMicroseconds maximum_delay_;
-  double scaling_;
+  double scaling_lower_bound_;
+  double scaling_upper_bound_;
   DoubleMicroseconds current_delay_start_;
   DoubleMicroseconds current_delay_end_;
   absl::optional<DefaultPRNG> generator_;

@@ -40,10 +40,78 @@ TEST(ExponentialBackoffPolicy, Simple) {
   delay = tested.OnCompletion();
   EXPECT_LE(ms(50), delay);
   EXPECT_GE(ms(100), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(50), delay);
+  EXPECT_GE(ms(100), delay);
+}
+
+/// @test Verify a full jitter policy, where the delay's lower bound is 0
+/// and does not grow.
+TEST(ExponentialBackoffPolicy, VerifyFullJitterPolicy) {
+  ExponentialBackoffPolicy tested(ms(0), ms(10), ms(50), 1.0, 2.0);
+
+  auto delay = tested.OnCompletion();
+  EXPECT_LE(ms(0), delay);
+  EXPECT_GE(ms(10), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(0), delay);
+  EXPECT_GE(ms(20), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(0), delay);
+  EXPECT_GE(ms(40), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(0), delay);
+  EXPECT_GE(ms(50), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(0), delay);
+  EXPECT_GE(ms(50), delay);
+}
+
+/// @test Verify a minimum jitter policy, where the delay's lower bound is
+/// nonzero and does not grow.
+TEST(ExponentialBackoffPolicy, VerifyMinJitterPolicy) {
+  ExponentialBackoffPolicy tested(ms(5), ms(10), ms(50), 1.0, 2.0);
+
+  auto delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(10), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(20), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(40), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(50), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(50), delay);
+}
+
+/// @test Verify the lower bound stops growing.
+TEST(ExponentialBackoffPolicy, VerifyLowerBoundStopsGrowing) {
+  ExponentialBackoffPolicy tested(ms(1), ms(10), ms(10), 2.0, 2.0);
+
+  auto delay = tested.OnCompletion();
+  EXPECT_LE(ms(1), delay);
+  EXPECT_GE(ms(10), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(2), delay);
+  EXPECT_GE(ms(10), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(4), delay);
+  EXPECT_GE(ms(10), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(10), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(5), delay);
+  EXPECT_GE(ms(10), delay);
 }
 
 /// @test Verify the initial and maximum delay are respected.
-TEST(ExponentialBackoffPolicy, RespectMinimumAndMaximumDelay) {
+TEST(ExponentialBackoffPolicy, RespectInitialAndMaximumDelay) {
   ExponentialBackoffPolicy tested(ms(10), ms(12), 2.0);
 
   auto delay = tested.OnCompletion();
@@ -54,6 +122,20 @@ TEST(ExponentialBackoffPolicy, RespectMinimumAndMaximumDelay) {
   EXPECT_GE(ms(12), delay);
 }
 
+/// @test Verify the minimum and maximum delay are respected when there are
+/// different scaling factors.
+TEST(ExponentialBackoffPolicy,
+     RespectMinimumAndMaximumDelayWithDifferentScalingFactors) {
+  ExponentialBackoffPolicy tested(ms(10), ms(10), ms(12), 1.1, 2.0);
+
+  auto delay = tested.OnCompletion();
+  EXPECT_LE(ms(10), delay);
+  EXPECT_GE(ms(12), delay);
+  delay = tested.OnCompletion();
+  EXPECT_LE(ms(10), delay);
+  EXPECT_GE(ms(12), delay);
+}
+
 /// @test Verify the delay range is determined by the scaling factor.
 TEST(ExponentialBackoffPolicy, DetermineRangeUsingScalingFactor) {
   ExponentialBackoffPolicy tested(ms(1000), ms(2000), 1.001);
@@ -63,8 +145,32 @@ TEST(ExponentialBackoffPolicy, DetermineRangeUsingScalingFactor) {
   EXPECT_GE(ms(1001), delay);
 }
 
-/// @test Verify that the scaling factor is validated.
-TEST(ExponentialBackoffPolicy, ValidateScaling) {
+/// @test Verify the initial delay upper bound is validated.
+TEST(ExponentialBackoffPolicy, ValidateInitialDelayUpperBound) {
+#if GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
+  EXPECT_THROW(ExponentialBackoffPolicy(ms(10), ms(9), ms(50), 2.0, 2.0),
+               std::invalid_argument);
+#else
+  EXPECT_DEATH_IF_SUPPORTED(
+      ExponentialBackoffPolicy(ms(10), ms(9), ms(50), 2.0, 2.0),
+      "exceptions are disabled");
+#endif  // GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
+}
+
+/// @test Verify that the scaling lower bound factor is validated.
+TEST(ExponentialBackoffPolicy, ValidateScalingLowerBound) {
+#if GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
+  EXPECT_THROW(ExponentialBackoffPolicy(ms(10), ms(10), ms(50), 0.99, 2.0),
+               std::invalid_argument);
+#else
+  EXPECT_DEATH_IF_SUPPORTED(
+      ExponentialBackoffPolicy(ms(10), ms(10), ms(50), 0.99, 2.0),
+      "exceptions are disabled");
+#endif  // GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
+}
+
+/// @test Verify that the scaling upper bound factor is validated.
+TEST(ExponentialBackoffPolicy, ValidateScalingUpperBound) {
 #if GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
   EXPECT_THROW(ExponentialBackoffPolicy(ms(10), ms(50), 0.0),
                std::invalid_argument);
@@ -78,6 +184,19 @@ TEST(ExponentialBackoffPolicy, ValidateScaling) {
 #endif  // GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
 }
 
+/// @test Verify that the scaling lower bound is less than the scaling upper
+/// bound factor.
+TEST(ExponentialBackoffPolicy, ValidateScalingFactors) {
+#if GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
+  EXPECT_THROW(ExponentialBackoffPolicy(ms(10), ms(10), ms(50), 1.01, 1.0),
+               std::invalid_argument);
+#else
+  EXPECT_DEATH_IF_SUPPORTED(
+      ExponentialBackoffPolicy(ms(10), ms(10), ms(50), 1.01, 1.0),
+      "exceptions are disabled");
+#endif  // GOOGLE_CLOUD_CPP_HAVE_EXCEPTIONS
+}
+
 /// @test Verify that less common arguments work.
 TEST(ExponentialBackoffPolicy, DifferentParameters) {
   ExponentialBackoffPolicy tested(ms(100), std::chrono::seconds(10), 1.5);

@@ -580,9 +580,9 @@ google::cloud::storage::Client StorageRetries(std::vector<std::string> const&) {
   // Retries only idempotent operations.
   options.set<gcs::IdempotencyPolicyOption>(
       gcs::StrictIdempotencyPolicy().clone());
-  // On error, it backs off for 1 second, then 3 seconds, then 9 seconds, etc.
-  // The backoff time never grows larger than 1 minute. The strategy introduces
-  // jitter around the backoff delay.
+  // On error, it backs off for a random delay between [1, 3] seconds, then [3,
+  // 9] seconds, then [9, 27] seconds, etc. The backoff time never grows larger
+  // than 1 minute.
   options.set<gcs::BackoffPolicyOption>(
       gcs::ExponentialBackoffPolicy(
           /*initial_delay=*/std::chrono::seconds(1),