2 * Copyright 2014-present Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
19 #include <folly/Random.h>
20 #include <folly/futures/Future.h>
28 * Given a policy and a future-factory, creates futures according to the
31 * The policy must be moveable - retrying will move it a lot - and callable of
32 * either of the two forms:
33 * - Future<bool>(size_t, exception_wrapper)
34 * - bool(size_t, exception_wrapper)
35 * Internally, the latter is transformed into the former in the obvious way.
36 * The first parameter is the attempt number of the next prospective attempt;
37 * the second parameter is the most recent exception. The policy returns a
38 * Future<bool> which, when completed with true, indicates that a retry is
41 * We provide a few generic policies:
43 * - CappedJitteredexponentialBackoff
45 * Custom policies may use the most recent try number and exception to decide
46 * whether to retry and optionally to do something interesting like delay
47 * before the retry. Users may pass inline lambda expressions as policies, or
48 * may define their own data types meeting the above requirements. Users are
49 * responsible for managing the lifetimes of anything pointed to or referred to
50 * from inside the policy.
52 * For example, one custom policy may try up to k times, but only if the most
53 * recent exception is one of a few types or has one of a few error codes
54 * indicating that the failure was transitory.
56 * Cancellation is not supported.
58 * If both FF and Policy inline executes, then it is possible to hit a stack
59 * overflow due to the recursive nature of the retry implementation
61 template <class Policy, class FF>
62 typename std::result_of<FF(size_t)>::type retrying(Policy&& p, FF&& ff);
66 struct retrying_policy_raw_tag {};
67 struct retrying_policy_fut_tag {};
69 template <class Policy>
70 struct retrying_policy_traits {
71 using result = std::result_of_t<Policy(size_t, const exception_wrapper&)>;
72 using is_raw = std::is_same<result, bool>;
73 using is_fut = std::is_same<result, Future<bool>>;
74 using tag = typename std::conditional<
76 retrying_policy_raw_tag,
77 typename std::conditional<is_fut::value, retrying_policy_fut_tag, void>::
81 template <class Policy, class FF, class Prom>
82 void retryingImpl(size_t k, Policy&& p, FF&& ff, Prom prom) {
83 using F = typename std::result_of<FF(size_t)>::type;
84 using T = typename F::value_type;
85 auto f = makeFutureWith([&] { return ff(k++); });
87 prom = std::move(prom),
88 pm = std::forward<Policy>(p),
89 ffm = std::forward<FF>(ff)](Try<T>&& t) mutable {
91 prom.setValue(std::move(t).value());
94 auto& x = t.exception();
97 prom = std::move(prom),
100 ffm = std::move(ffm)](bool shouldRetry) mutable {
102 retryingImpl(k, std::move(pm), std::move(ffm), std::move(prom));
104 prom.setException(std::move(xm));
110 template <class Policy, class FF>
111 typename std::result_of<FF(size_t)>::type
112 retrying(size_t k, Policy&& p, FF&& ff) {
113 using F = typename std::result_of<FF(size_t)>::type;
114 using T = typename F::value_type;
115 auto prom = Promise<T>();
116 auto f = prom.getFuture();
118 k, std::forward<Policy>(p), std::forward<FF>(ff), std::move(prom));
122 template <class Policy, class FF>
123 typename std::result_of<FF(size_t)>::type
124 retrying(Policy&& p, FF&& ff, retrying_policy_raw_tag) {
125 auto q = [pm = std::forward<Policy>(p)](size_t k, exception_wrapper x) {
126 return makeFuture<bool>(pm(k, x));
128 return retrying(0, std::move(q), std::forward<FF>(ff));
131 template <class Policy, class FF>
132 typename std::result_of<FF(size_t)>::type
133 retrying(Policy&& p, FF&& ff, retrying_policy_fut_tag) {
134 return retrying(0, std::forward<Policy>(p), std::forward<FF>(ff));
137 // jittered exponential backoff, clamped to [backoff_min, backoff_max]
138 template <class URNG>
139 Duration retryingJitteredExponentialBackoffDur(
141 Duration backoff_min,
142 Duration backoff_max,
146 auto dist = std::normal_distribution<double>(0.0, jitter_param);
147 auto jitter = std::exp(dist(rng));
148 auto backoff = d(d::rep(jitter * backoff_min.count() * std::pow(2, n - 1)));
149 return std::max(backoff_min, std::min(backoff_max, backoff));
152 template <class Policy, class URNG>
153 std::function<Future<bool>(size_t, const exception_wrapper&)>
154 retryingPolicyCappedJitteredExponentialBackoff(
156 Duration backoff_min,
157 Duration backoff_max,
161 return [pm = std::forward<Policy>(p),
166 rngp = std::forward<URNG>(rng)](
167 size_t n, const exception_wrapper& ex) mutable {
168 if (n == max_tries) {
169 return makeFuture(false);
171 return pm(n, ex).then(
172 [n, backoff_min, backoff_max, jitter_param, rngp = std::move(rngp)](
175 return makeFuture(false);
177 auto backoff = detail::retryingJitteredExponentialBackoffDur(
178 n, backoff_min, backoff_max, jitter_param, rngp);
179 return futures::sleep(backoff).then([] { return true; });
184 template <class Policy, class URNG>
185 std::function<Future<bool>(size_t, const exception_wrapper&)>
186 retryingPolicyCappedJitteredExponentialBackoff(
188 Duration backoff_min,
189 Duration backoff_max,
193 retrying_policy_raw_tag) {
194 auto q = [pm = std::forward<Policy>(p)](
195 size_t n, const exception_wrapper& e) {
196 return makeFuture(pm(n, e));
198 return retryingPolicyCappedJitteredExponentialBackoff(
203 std::forward<URNG>(rng),
207 template <class Policy, class URNG>
208 std::function<Future<bool>(size_t, const exception_wrapper&)>
209 retryingPolicyCappedJitteredExponentialBackoff(
211 Duration backoff_min,
212 Duration backoff_max,
216 retrying_policy_fut_tag) {
217 return retryingPolicyCappedJitteredExponentialBackoff(
222 std::forward<URNG>(rng),
223 std::forward<Policy>(p));
226 } // namespace detail
228 template <class Policy, class FF>
229 typename std::result_of<FF(size_t)>::type retrying(Policy&& p, FF&& ff) {
230 using tag = typename detail::retrying_policy_traits<Policy>::tag;
231 return detail::retrying(std::forward<Policy>(p), std::forward<FF>(ff), tag());
234 inline std::function<bool(size_t, const exception_wrapper&)>
235 retryingPolicyBasic(size_t max_tries) {
236 return [=](size_t n, const exception_wrapper&) { return n < max_tries; };
239 template <class Policy, class URNG>
240 std::function<Future<bool>(size_t, const exception_wrapper&)>
241 retryingPolicyCappedJitteredExponentialBackoff(
243 Duration backoff_min,
244 Duration backoff_max,
248 using tag = typename detail::retrying_policy_traits<Policy>::tag;
249 return detail::retryingPolicyCappedJitteredExponentialBackoff(
254 std::forward<URNG>(rng),
255 std::forward<Policy>(p),
259 inline std::function<Future<bool>(size_t, const exception_wrapper&)>
260 retryingPolicyCappedJitteredExponentialBackoff(
262 Duration backoff_min,
263 Duration backoff_max,
264 double jitter_param) {
265 auto p = [](size_t, const exception_wrapper&) { return true; };
266 return retryingPolicyCappedJitteredExponentialBackoff(
275 } // namespace futures