From 6466c35737eff21e9b48c3ce2353d42628f4bb77 Mon Sep 17 00:00:00 2001 From: Konstantin Varlamov Date: Tue, 10 Jul 2018 17:45:16 -0400 Subject: C++ migration: add a C++ implementation of `FSTExponentialBackoff` (#1465) This is a pretty close port of `FSTExponentialBackoff`. The changes are pretty minor: * delay is calculated using duration types, not plain numbers, which should be a little more type-safe; * split a piece of code into a ClampDelay function, because it's reasonably close to std::clamp; * rephrased the class-level comment to make it clearer that the first attempt always has delay = 0; * added simple tests (other platforms don't have tests for this). Also make sure that canceling a DelayedOperation is always valid. --- .../src/firebase/firestore/remote/CMakeLists.txt | 2 + .../firestore/remote/exponential_backoff.cc | 93 +++++++++++++++++ .../firestore/remote/exponential_backoff.h | 116 +++++++++++++++++++++ .../core/src/firebase/firestore/util/executor.h | 4 +- 4 files changed, 214 insertions(+), 1 deletion(-) create mode 100644 Firestore/core/src/firebase/firestore/remote/exponential_backoff.cc create mode 100644 Firestore/core/src/firebase/firestore/remote/exponential_backoff.h (limited to 'Firestore/core/src') diff --git a/Firestore/core/src/firebase/firestore/remote/CMakeLists.txt b/Firestore/core/src/firebase/firestore/remote/CMakeLists.txt index fc51b37..0ef0b7c 100644 --- a/Firestore/core/src/firebase/firestore/remote/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/remote/CMakeLists.txt @@ -17,6 +17,8 @@ cc_library( SOURCES datastore.h datastore.cc + exponential_backoff.h + exponential_backoff.cc serializer.h serializer.cc DEPENDS diff --git a/Firestore/core/src/firebase/firestore/remote/exponential_backoff.cc b/Firestore/core/src/firebase/firestore/remote/exponential_backoff.cc new file mode 100644 index 0000000..a880c45 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/remote/exponential_backoff.cc @@ -0,0 +1,93 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/remote/exponential_backoff.h" + +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/hard_assert.h" +#include "Firestore/core/src/firebase/firestore/util/log.h" + +namespace firebase { +namespace firestore { +namespace remote { + +using firebase::firestore::util::AsyncQueue; +using firebase::firestore::util::TimerId; +namespace chr = std::chrono; + +ExponentialBackoff::ExponentialBackoff(AsyncQueue* queue, + TimerId timer_id, + double backoff_factor, + Milliseconds initial_delay, + Milliseconds max_delay) + : queue_{queue}, + timer_id_{timer_id}, + backoff_factor_{backoff_factor}, + initial_delay_{initial_delay}, + max_delay_{max_delay} { + HARD_ASSERT(queue, "Queue can't be null"); + + HARD_ASSERT(backoff_factor >= 1.0, "Backoff factor must be at least 1"); + + HARD_ASSERT(initial_delay.count() >= 0, "Delays must be non-negative"); + HARD_ASSERT(max_delay.count() >= 0, "Delays must be non-negative"); + HARD_ASSERT(initial_delay <= max_delay, + "Initial delay can't be greater than max delay"); +} + +void ExponentialBackoff::BackoffAndRun(AsyncQueue::Operation&& operation) { + Cancel(); + + // First schedule the block using the current base (which may be 0 and should + // be honored as such). + Milliseconds delay_with_jitter = current_base_ + GetDelayWithJitter(); + if (delay_with_jitter.count() > 0) { + LOG_DEBUG("Backing off for %s milliseconds (base delay: %s milliseconds)", + delay_with_jitter.count(), current_base_.count()); + } + + delayed_operation_ = queue_->EnqueueAfterDelay(delay_with_jitter, timer_id_, + std::move(operation)); + + // Apply backoff factor to determine next delay, but ensure it is within + // bounds. + current_base_ = ClampDelay( + chr::duration_cast(current_base_ * backoff_factor_)); +} + +ExponentialBackoff::Milliseconds ExponentialBackoff::GetDelayWithJitter() { + std::uniform_real_distribution distribution; + double random_double = distribution(secure_random_); + return chr::duration_cast((random_double - 0.5) * + current_base_); +} + +ExponentialBackoff::Milliseconds ExponentialBackoff::ClampDelay( + Milliseconds delay) const { + if (delay < initial_delay_) { + return initial_delay_; + } + if (delay > max_delay_) { + return max_delay_; + } + return delay; +} + +} // namespace remote +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/src/firebase/firestore/remote/exponential_backoff.h b/Firestore/core/src/firebase/firestore/remote/exponential_backoff.h new file mode 100644 index 0000000..8836e7e --- /dev/null +++ b/Firestore/core/src/firebase/firestore/remote/exponential_backoff.h @@ -0,0 +1,116 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_REMOTE_EXPONENTIAL_BACKOFF_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_REMOTE_EXPONENTIAL_BACKOFF_H_ + +#include // NOLINT(build/c++11) + +#include "Firestore/core/src/firebase/firestore/util/async_queue.h" +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" + +namespace firebase { +namespace firestore { +namespace remote { + +/** + * + * A helper for running delayed operations following an exponential backoff + * curve between attempts. + * + * The first attempt will be done immediately. After that, each retry will + * have a delay that is made up of a "base" delay which follows the + * exponential backoff curve, and a +/- <=50% "jitter" that is calculated and + * added to the base delay. This prevents clients from accidentally + * synchronizing their delays causing spikes of load to the backend. + * + */ +class ExponentialBackoff { + public: + /** + * @param queue The queue to run operations on. + * @param timer_id The id to use when scheduling backoff operations on the + * queue. + * @param backoff_factor The multiplier to use to determine the extended base + * delay after each attempt. + * @param initial_delay The initial delay (used as the base delay on the first + * retry attempt, that is, the second attempt). Note that jitter will + * still be applied, so the actual delay could be as little as + * `0.5*initial_delay`. + * @param max_delay The maximum base delay after which no further backoff is + * performed. Note that jitter will still be applied, so the actual delay + * could be as much as `1.5*max_delay`. + */ + ExponentialBackoff(util::AsyncQueue* queue, + util::TimerId timer_id, + double backoff_factor, + util::AsyncQueue::Milliseconds initial_delay, + util::AsyncQueue::Milliseconds max_delay); + + /** + * Resets the backoff delay. + * + * The very next `backoffAndRun` will have no delay. If it is called again + * (i.e. due to an error), `initial_delay` (plus jitter) will be used, and + * subsequent ones will increase according to the `backoff_factor`. + */ + void Reset() { + current_base_ = Milliseconds{0}; + } + + /** + * Resets the backoff to the maximum delay (e.g. for use after + * a RESOURCE_EXHAUSTED error). + */ + void ResetToMax() { + current_base_ = max_delay_; + } + + /** + * Waits for `current_base` seconds (which may be zero), increases the delay + * and runs the specified operation. If there was a pending operation waiting + * to be run already, it will be canceled. + */ + void BackoffAndRun(util::AsyncQueue::Operation&& operation); + + /** Cancels any pending backoff operation scheduled via `BackoffAndRun`. */ + void Cancel() { + delayed_operation_.Cancel(); + } + + private: + using Milliseconds = util::AsyncQueue::Milliseconds; + + // Returns a random value in the range [-current_base_/2, current_base_/2]. + Milliseconds GetDelayWithJitter(); + Milliseconds ClampDelay(Milliseconds delay) const; + + util::AsyncQueue* const queue_; + const util::TimerId timer_id_; + util::DelayedOperation delayed_operation_; + + const double backoff_factor_; + Milliseconds current_base_{0}; + const Milliseconds initial_delay_; + const Milliseconds max_delay_; + util::SecureRandom secure_random_; +}; + +} // namespace remote +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_REMOTE_EXPONENTIAL_BACKOFF_H_ diff --git a/Firestore/core/src/firebase/firestore/util/executor.h b/Firestore/core/src/firebase/firestore/util/executor.h index df8b0b5..ea67b17 100644 --- a/Firestore/core/src/firebase/firestore/util/executor.h +++ b/Firestore/core/src/firebase/firestore/util/executor.h @@ -38,7 +38,9 @@ class DelayedOperation { // If the operation has not been run yet, cancels the operation. Otherwise, // this function is a no-op. void Cancel() { - cancel_func_(); + if (cancel_func_) { + cancel_func_(); + } } // Internal use only. -- cgit v1.2.3