folly/executors/Codel.cpp

   1 /*
   2  * Copyright 2017 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 #include <folly/executors/Codel.h>
  18
  19 #include <folly/portability/GFlags.h>
  20 #include <algorithm>
  21
  22 DEFINE_int32(codel_interval, 100, "Codel default interval time in ms");
  23 DEFINE_int32(codel_target_delay, 5, "Target codel queueing delay in ms");
  24
  25 using std::chrono::nanoseconds;
  26 using std::chrono::milliseconds;
  27
  28 namespace folly {
  29
  30 Codel::Codel()
  31     : codelMinDelay_(0),
  32       codelIntervalTime_(std::chrono::steady_clock::now()),
  33       codelResetDelay_(true),
  34       overloaded_(false) {}
  35
  36 bool Codel::overloaded(std::chrono::nanoseconds delay) {
  37   bool ret = false;
  38   auto now = std::chrono::steady_clock::now();
  39
  40   // Avoid another thread updating the value at the same time we are using it
  41   // to calculate the overloaded state
  42   auto minDelay = codelMinDelay_;
  43
  44   if (now > codelIntervalTime_ &&
  45       // testing before exchanging is more cacheline-friendly
  46       (!codelResetDelay_.load(std::memory_order_acquire) &&
  47        !codelResetDelay_.exchange(true))) {
  48     codelIntervalTime_ = now + getInterval();
  49
  50     if (minDelay > getTargetDelay()) {
  51       overloaded_ = true;
  52     } else {
  53       overloaded_ = false;
  54     }
  55   }
  56   // Care must be taken that only a single thread resets codelMinDelay_,
  57   // and that it happens after the interval reset above
  58   if (codelResetDelay_.load(std::memory_order_acquire) &&
  59       codelResetDelay_.exchange(false)) {
  60     codelMinDelay_ = delay;
  61     // More than one request must come in during an interval before codel
  62     // starts dropping requests
  63     return false;
  64   } else if (delay < codelMinDelay_) {
  65     codelMinDelay_ = delay;
  66   }
  67
  68   // Here is where we apply different logic than codel proper. Instead of
  69   // adapting the interval until the next drop, we slough off requests with
  70   // queueing delay > 2*target_delay while in the overloaded regime. This
  71   // empirically works better for our services than the codel approach of
  72   // increasingly often dropping packets.
  73   if (overloaded_ && delay > getSloughTimeout()) {
  74     ret = true;
  75   }
  76
  77   return ret;
  78 }
  79
  80 int Codel::getLoad() {
  81   // it might be better to use the average delay instead of minDelay, but we'd
  82   // have to track it. aspiring bootcamper?
  83   return std::min<int>(100, 100 * getMinDelay() / getSloughTimeout());
  84 }
  85
  86 nanoseconds Codel::getMinDelay() {
  87   return codelMinDelay_;
  88 }
  89
  90 milliseconds Codel::getInterval() {
  91   return milliseconds(FLAGS_codel_interval);
  92 }
  93
  94 milliseconds Codel::getTargetDelay() {
  95   return milliseconds(FLAGS_codel_target_delay);
  96 }
  97
  98 milliseconds Codel::getSloughTimeout() {
  99   return getTargetDelay() * 2;
 100 }
 101
 102 } // namespace folly