1/*
2 * Copyright 2014-present Facebook, Inc.
3 *
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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17#pragma once
18
19#include <folly/Random.h>
20#include <folly/functional/Invoke.h>
21#include <folly/futures/Future.h>
22
23namespace folly {
24namespace futures {
25
26/**
27 * retrying
28 *
29 * Given a policy and a future-factory, creates futures according to the
30 * policy.
31 *
32 * The policy must be moveable - retrying will move it a lot - and callable of
33 * either of the two forms:
34 * - Future<bool>(size_t, exception_wrapper)
35 * - bool(size_t, exception_wrapper)
36 * Internally, the latter is transformed into the former in the obvious way.
37 * The first parameter is the attempt number of the next prospective attempt;
38 * the second parameter is the most recent exception. The policy returns a
39 * Future<bool> which, when completed with true, indicates that a retry is
40 * desired.
41 *
42 * We provide a few generic policies:
43 * - Basic
44 * - CappedJitteredexponentialBackoff
45 *
46 * Custom policies may use the most recent try number and exception to decide
47 * whether to retry and optionally to do something interesting like delay
48 * before the retry. Users may pass inline lambda expressions as policies, or
49 * may define their own data types meeting the above requirements. Users are
50 * responsible for managing the lifetimes of anything pointed to or referred to
51 * from inside the policy.
52 *
53 * For example, one custom policy may try up to k times, but only if the most
54 * recent exception is one of a few types or has one of a few error codes
55 * indicating that the failure was transitory.
56 *
57 * Cancellation is not supported.
58 *
59 * If both FF and Policy inline executes, then it is possible to hit a stack
60 * overflow due to the recursive nature of the retry implementation
61 */
62template <class Policy, class FF>
63invoke_result_t<FF, size_t> retrying(Policy&& p, FF&& ff);
64
65namespace detail {
66
67struct retrying_policy_raw_tag {};
68struct retrying_policy_fut_tag {};
69
70template <class Policy>
71struct retrying_policy_traits {
72 using result = invoke_result_t<Policy, size_t, const exception_wrapper&>;
73 using is_raw = std::is_same<result, bool>;
74 using is_fut = std::is_same<result, Future<bool>>;
75 using tag = typename std::conditional<
76 is_raw::value,
77 retrying_policy_raw_tag,
78 typename std::conditional<is_fut::value, retrying_policy_fut_tag, void>::
79 type>::type;
80};
81
82template <class Policy, class FF, class Prom>
83void retryingImpl(size_t k, Policy&& p, FF&& ff, Prom prom) {
84 using F = invoke_result_t<FF, size_t>;
85 using T = typename F::value_type;
86 auto f = makeFutureWith([&] { return ff(k++); });
87 std::move(f).thenTry([k,
88 prom = std::move(prom),
89 pm = std::forward<Policy>(p),
90 ffm = std::forward<FF>(ff)](Try<T>&& t) mutable {
91 if (t.hasValue()) {
92 prom.setValue(std::move(t).value());
93 return;
94 }
95 auto& x = t.exception();
96 auto q = makeFutureWith([&] { return pm(k, x); });
97 std::move(q).thenTry([k,
98 prom = std::move(prom),
99 xm = std::move(x),
100 pm = std::move(pm),
101 ffm = std::move(ffm)](Try<bool> shouldRetry) mutable {
102 if (shouldRetry.hasValue() && shouldRetry.value()) {
103 retryingImpl(k, std::move(pm), std::move(ffm), std::move(prom));
104 } else if (shouldRetry.hasValue()) {
105 prom.setException(std::move(xm));
106 } else {
107 prom.setException(std::move(shouldRetry.exception()));
108 }
109 });
110 });
111}
112
113template <class Policy, class FF>
114invoke_result_t<FF, size_t> retrying(size_t k, Policy&& p, FF&& ff) {
115 using F = invoke_result_t<FF, size_t>;
116 using T = typename F::value_type;
117 auto prom = Promise<T>();
118 auto f = prom.getFuture();
119 retryingImpl(
120 k, std::forward<Policy>(p), std::forward<FF>(ff), std::move(prom));
121 return f;
122}
123
124template <class Policy, class FF>
125invoke_result_t<FF, size_t>
126retrying(Policy&& p, FF&& ff, retrying_policy_raw_tag) {
127 auto q = [pm = std::forward<Policy>(p)](size_t k, exception_wrapper x) {
128 return makeFuture<bool>(pm(k, x));
129 };
130 return retrying(0, std::move(q), std::forward<FF>(ff));
131}
132
133template <class Policy, class FF>
134invoke_result_t<FF, size_t>
135retrying(Policy&& p, FF&& ff, retrying_policy_fut_tag) {
136 return retrying(0, std::forward<Policy>(p), std::forward<FF>(ff));
137}
138
139// jittered exponential backoff, clamped to [backoff_min, backoff_max]
140template <class URNG>
141Duration retryingJitteredExponentialBackoffDur(
142 size_t n,
143 Duration backoff_min,
144 Duration backoff_max,
145 double jitter_param,
146 URNG& rng) {
147 auto dist = std::normal_distribution<double>(0.0, jitter_param);
148 auto jitter = std::exp(dist(rng));
149 auto backoff_rep = jitter * backoff_min.count() * std::pow(2, n - 1);
150 if (UNLIKELY(backoff_rep >= std::numeric_limits<Duration::rep>::max())) {
151 return backoff_max;
152 }
153 auto backoff = Duration(Duration::rep(backoff_rep));
154 return std::max(backoff_min, std::min(backoff_max, backoff));
155}
156
157template <class Policy, class URNG>
158std::function<Future<bool>(size_t, const exception_wrapper&)>
159retryingPolicyCappedJitteredExponentialBackoff(
160 size_t max_tries,
161 Duration backoff_min,
162 Duration backoff_max,
163 double jitter_param,
164 URNG&& rng,
165 Policy&& p) {
166 return [pm = std::forward<Policy>(p),
167 max_tries,
168 backoff_min,
169 backoff_max,
170 jitter_param,
171 rngp = std::forward<URNG>(rng)](
172 size_t n, const exception_wrapper& ex) mutable {
173 if (n == max_tries) {
174 return makeFuture(false);
175 }
176 return pm(n, ex).thenValue(
177 [n, backoff_min, backoff_max, jitter_param, rngp = std::move(rngp)](
178 bool v) mutable {
179 if (!v) {
180 return makeFuture(false);
181 }
182 auto backoff = detail::retryingJitteredExponentialBackoffDur(
183 n, backoff_min, backoff_max, jitter_param, rngp);
184 return futures::sleep(backoff).thenValue([](auto&&) { return true; });
185 });
186 };
187}
188
189template <class Policy, class URNG>
190std::function<Future<bool>(size_t, const exception_wrapper&)>
191retryingPolicyCappedJitteredExponentialBackoff(
192 size_t max_tries,
193 Duration backoff_min,
194 Duration backoff_max,
195 double jitter_param,
196 URNG&& rng,
197 Policy&& p,
198 retrying_policy_raw_tag) {
199 auto q = [pm = std::forward<Policy>(p)](
200 size_t n, const exception_wrapper& e) {
201 return makeFuture(pm(n, e));
202 };
203 return retryingPolicyCappedJitteredExponentialBackoff(
204 max_tries,
205 backoff_min,
206 backoff_max,
207 jitter_param,
208 std::forward<URNG>(rng),
209 std::move(q));
210}
211
212template <class Policy, class URNG>
213std::function<Future<bool>(size_t, const exception_wrapper&)>
214retryingPolicyCappedJitteredExponentialBackoff(
215 size_t max_tries,
216 Duration backoff_min,
217 Duration backoff_max,
218 double jitter_param,
219 URNG&& rng,
220 Policy&& p,
221 retrying_policy_fut_tag) {
222 return retryingPolicyCappedJitteredExponentialBackoff(
223 max_tries,
224 backoff_min,
225 backoff_max,
226 jitter_param,
227 std::forward<URNG>(rng),
228 std::forward<Policy>(p));
229}
230
231} // namespace detail
232
233template <class Policy, class FF>
234invoke_result_t<FF, size_t> retrying(Policy&& p, FF&& ff) {
235 using tag = typename detail::retrying_policy_traits<Policy>::tag;
236 return detail::retrying(std::forward<Policy>(p), std::forward<FF>(ff), tag());
237}
238
239inline std::function<bool(size_t, const exception_wrapper&)>
240retryingPolicyBasic(size_t max_tries) {
241 return [=](size_t n, const exception_wrapper&) { return n < max_tries; };
242}
243
244template <class Policy, class URNG>
245std::function<Future<bool>(size_t, const exception_wrapper&)>
246retryingPolicyCappedJitteredExponentialBackoff(
247 size_t max_tries,
248 Duration backoff_min,
249 Duration backoff_max,
250 double jitter_param,
251 URNG&& rng,
252 Policy&& p) {
253 using tag = typename detail::retrying_policy_traits<Policy>::tag;
254 return detail::retryingPolicyCappedJitteredExponentialBackoff(
255 max_tries,
256 backoff_min,
257 backoff_max,
258 jitter_param,
259 std::forward<URNG>(rng),
260 std::forward<Policy>(p),
261 tag());
262}
263
264inline std::function<Future<bool>(size_t, const exception_wrapper&)>
265retryingPolicyCappedJitteredExponentialBackoff(
266 size_t max_tries,
267 Duration backoff_min,
268 Duration backoff_max,
269 double jitter_param) {
270 auto p = [](size_t, const exception_wrapper&) { return true; };
271 return retryingPolicyCappedJitteredExponentialBackoff(
272 max_tries,
273 backoff_min,
274 backoff_max,
275 jitter_param,
276 ThreadLocalPRNG(),
277 std::move(p));
278}
279
280} // namespace futures
281} // namespace folly
282