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 | |
23 | namespace folly { |
24 | namespace 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 | */ |
62 | template <class Policy, class FF> |
63 | invoke_result_t<FF, size_t> retrying(Policy&& p, FF&& ff); |
64 | |
65 | namespace detail { |
66 | |
67 | struct retrying_policy_raw_tag {}; |
68 | struct retrying_policy_fut_tag {}; |
69 | |
70 | template <class Policy> |
71 | struct 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 | |
82 | template <class Policy, class FF, class Prom> |
83 | void 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 | |
113 | template <class Policy, class FF> |
114 | invoke_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 | |
124 | template <class Policy, class FF> |
125 | invoke_result_t<FF, size_t> |
126 | retrying(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 | |
133 | template <class Policy, class FF> |
134 | invoke_result_t<FF, size_t> |
135 | retrying(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] |
140 | template <class URNG> |
141 | Duration 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 | |
157 | template <class Policy, class URNG> |
158 | std::function<Future<bool>(size_t, const exception_wrapper&)> |
159 | retryingPolicyCappedJitteredExponentialBackoff( |
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 | |
189 | template <class Policy, class URNG> |
190 | std::function<Future<bool>(size_t, const exception_wrapper&)> |
191 | retryingPolicyCappedJitteredExponentialBackoff( |
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 | |
212 | template <class Policy, class URNG> |
213 | std::function<Future<bool>(size_t, const exception_wrapper&)> |
214 | retryingPolicyCappedJitteredExponentialBackoff( |
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 | |
233 | template <class Policy, class FF> |
234 | invoke_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 | |
239 | inline std::function<bool(size_t, const exception_wrapper&)> |
240 | retryingPolicyBasic(size_t max_tries) { |
241 | return [=](size_t n, const exception_wrapper&) { return n < max_tries; }; |
242 | } |
243 | |
244 | template <class Policy, class URNG> |
245 | std::function<Future<bool>(size_t, const exception_wrapper&)> |
246 | retryingPolicyCappedJitteredExponentialBackoff( |
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 | |
264 | inline std::function<Future<bool>(size_t, const exception_wrapper&)> |
265 | retryingPolicyCappedJitteredExponentialBackoff( |
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 | |