folly/futures/Retrying.h

   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/futures/Future.h>
  21
  22 namespace folly {
  23 namespace futures {
  24
  25 /**
  26  *  retrying
  27  *
  28  *  Given a policy and a future-factory, creates futures according to the
  29  *  policy.
  30  *
  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
  39  *  desired.
  40  *
  41  *  We provide a few generic policies:
  42  *  - Basic
  43  *  - CappedJitteredexponentialBackoff
  44  *
  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.
  51  *
  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.
  55  *
  56  *  Cancellation is not supported.
  57  *
  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
  60  */
  61 template <class Policy, class FF>
  62 typename std::result_of<FF(size_t)>::type retrying(Policy&& p, FF&& ff);
  63
  64 namespace detail {
  65
  66 struct retrying_policy_raw_tag {};
  67 struct retrying_policy_fut_tag {};
  68
  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<
  75       is_raw::value,
  76       retrying_policy_raw_tag,
  77       typename std::conditional<is_fut::value, retrying_policy_fut_tag, void>::
  78           type>::type;
  79 };
  80
  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++); });
  86   f.then([k,
  87           prom = std::move(prom),
  88           pm = std::forward<Policy>(p),
  89           ffm = std::forward<FF>(ff)](Try<T>&& t) mutable {
  90     if (t.hasValue()) {
  91       prom.setValue(std::move(t).value());
  92       return;
  93     }
  94     auto& x = t.exception();
  95     auto q = pm(k, x);
  96     q.then([k,
  97             prom = std::move(prom),
  98             xm = std::move(x),
  99             pm = std::move(pm),
 100             ffm = std::move(ffm)](bool shouldRetry) mutable {
 101       if (shouldRetry) {
 102         retryingImpl(k, std::move(pm), std::move(ffm), std::move(prom));
 103       } else {
 104         prom.setException(std::move(xm));
 105       };
 106     });
 107   });
 108 }
 109
 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();
 117   retryingImpl(
 118       k, std::forward<Policy>(p), std::forward<FF>(ff), std::move(prom));
 119   return f;
 120 }
 121
 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));
 127   };
 128   return retrying(0, std::move(q), std::forward<FF>(ff));
 129 }
 130
 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));
 135 }
 136
 137 //  jittered exponential backoff, clamped to [backoff_min, backoff_max]
 138 template <class URNG>
 139 Duration retryingJitteredExponentialBackoffDur(
 140     size_t n,
 141     Duration backoff_min,
 142     Duration backoff_max,
 143     double jitter_param,
 144     URNG& rng) {
 145   using d = Duration;
 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));
 150 }
 151
 152 template <class Policy, class URNG>
 153 std::function<Future<bool>(size_t, const exception_wrapper&)>
 154 retryingPolicyCappedJitteredExponentialBackoff(
 155     size_t max_tries,
 156     Duration backoff_min,
 157     Duration backoff_max,
 158     double jitter_param,
 159     URNG&& rng,
 160     Policy&& p) {
 161   return [pm = std::forward<Policy>(p),
 162           max_tries,
 163           backoff_min,
 164           backoff_max,
 165           jitter_param,
 166           rngp = std::forward<URNG>(rng)](
 167              size_t n, const exception_wrapper& ex) mutable {
 168     if (n == max_tries) {
 169       return makeFuture(false);
 170     }
 171     return pm(n, ex).then(
 172         [n, backoff_min, backoff_max, jitter_param, rngp = std::move(rngp)](
 173             bool v) mutable {
 174           if (!v) {
 175             return makeFuture(false);
 176           }
 177           auto backoff = detail::retryingJitteredExponentialBackoffDur(
 178               n, backoff_min, backoff_max, jitter_param, rngp);
 179           return futures::sleep(backoff).then([] { return true; });
 180         });
 181   };
 182 }
 183
 184 template <class Policy, class URNG>
 185 std::function<Future<bool>(size_t, const exception_wrapper&)>
 186 retryingPolicyCappedJitteredExponentialBackoff(
 187     size_t max_tries,
 188     Duration backoff_min,
 189     Duration backoff_max,
 190     double jitter_param,
 191     URNG&& rng,
 192     Policy&& p,
 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));
 197   };
 198   return retryingPolicyCappedJitteredExponentialBackoff(
 199       max_tries,
 200       backoff_min,
 201       backoff_max,
 202       jitter_param,
 203       std::forward<URNG>(rng),
 204       std::move(q));
 205 }
 206
 207 template <class Policy, class URNG>
 208 std::function<Future<bool>(size_t, const exception_wrapper&)>
 209 retryingPolicyCappedJitteredExponentialBackoff(
 210     size_t max_tries,
 211     Duration backoff_min,
 212     Duration backoff_max,
 213     double jitter_param,
 214     URNG&& rng,
 215     Policy&& p,
 216     retrying_policy_fut_tag) {
 217   return retryingPolicyCappedJitteredExponentialBackoff(
 218       max_tries,
 219       backoff_min,
 220       backoff_max,
 221       jitter_param,
 222       std::forward<URNG>(rng),
 223       std::forward<Policy>(p));
 224 }
 225
 226 } // namespace detail
 227
 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());
 232 }
 233
 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; };
 237 }
 238
 239 template <class Policy, class URNG>
 240 std::function<Future<bool>(size_t, const exception_wrapper&)>
 241 retryingPolicyCappedJitteredExponentialBackoff(
 242     size_t max_tries,
 243     Duration backoff_min,
 244     Duration backoff_max,
 245     double jitter_param,
 246     URNG&& rng,
 247     Policy&& p) {
 248   using tag = typename detail::retrying_policy_traits<Policy>::tag;
 249   return detail::retryingPolicyCappedJitteredExponentialBackoff(
 250       max_tries,
 251       backoff_min,
 252       backoff_max,
 253       jitter_param,
 254       std::forward<URNG>(rng),
 255       std::forward<Policy>(p),
 256       tag());
 257 }
 258
 259 inline std::function<Future<bool>(size_t, const exception_wrapper&)>
 260 retryingPolicyCappedJitteredExponentialBackoff(
 261     size_t max_tries,
 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(
 267       max_tries,
 268       backoff_min,
 269       backoff_max,
 270       jitter_param,
 271       ThreadLocalPRNG(),
 272       std::move(p));
 273 }
 274
 275 } // namespace futures
 276 } // namespace folly