folly/executors/Codel.h

   1 /*
   2  * Copyright 2017-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 <atomic>
  20 #include <chrono>
  21
  22 #include <folly/portability/GFlags.h>
  23
  24 DECLARE_int32(codel_interval);
  25 DECLARE_int32(codel_target_delay);
  26
  27 namespace folly {
  28
  29 /// CoDel (controlled delay) is an active queue management algorithm from
  30 /// networking for battling bufferbloat.
  31 ///
  32 /// Services also have queues (of requests, not packets) and suffer from
  33 /// queueing delay when overloaded. This class adapts the codel algorithm for
  34 /// services.
  35 ///
  36 /// Codel is discussed in depth on the web [1,2], but a basic sketch of the
  37 /// algorithm is this: if every request has experienced queueing delay greater
  38 /// than the target (5ms) during the past interval (100ms), then we shed load.
  39 ///
  40 /// We have adapted the codel algorithm. TCP sheds load by changing windows in
  41 /// reaction to dropped packets. Codel in a network setting drops packets at
  42 /// increasingly shorter intervals (100 / sqrt(n)) to achieve a linear change
  43 /// in throughput. In our experience a different scheme works better for
  44 /// services: when overloaded slough off requests that we dequeue which have
  45 /// exceeded an alternate timeout (2 * target_delay).
  46 ///
  47 /// So in summary, to use this class, calculate the time each request spent in
  48 /// the queue and feed that delay to overloaded(), which will tell you whether
  49 /// to expire this request.
  50 ///
  51 /// You can also ask for an instantaneous load estimate and the minimum delay
  52 /// observed during this interval.
  53 ///
  54 ///
  55 /// 1. http://queue.acm.org/detail.cfm?id=2209336
  56 /// 2. https://en.wikipedia.org/wiki/CoDel
  57 class Codel {
  58  public:
  59   Codel();
  60
  61   /// Returns true if this request should be expired to reduce overload.
  62   /// In detail, this returns true if min_delay > target_delay for the
  63   /// interval, and this delay > 2 * target_delay.
  64   ///
  65   /// As you may guess, we observe the clock so this is time sensitive. Call
  66   /// it promptly after calculating queueing delay.
  67   bool overloaded(std::chrono::nanoseconds delay);
  68
  69   /// Get the queue load, as seen by the codel algorithm
  70   /// Gives a rough guess at how bad the queue delay is.
  71   ///
  72   ///   min(100%, min_delay / (2 * target_delay))
  73   ///
  74   /// Return:  0 = no delay, 100 = At the queueing limit
  75   int getLoad();
  76
  77   std::chrono::nanoseconds getMinDelay();
  78   std::chrono::milliseconds getInterval();
  79   std::chrono::milliseconds getTargetDelay();
  80   std::chrono::milliseconds getSloughTimeout();
  81
  82  private:
  83   std::atomic<uint64_t> codelMinDelayNs_;
  84   std::atomic<uint64_t> codelIntervalTimeNs_;
  85
  86   // flag to make overloaded() thread-safe, since we only want
  87   // to reset the delay once per time period
  88   std::atomic<bool> codelResetDelay_;
  89
  90   std::atomic<bool> overloaded_;
  91 };
  92
  93 } // namespace folly