folly/wangle/concurrent/Codel.h

   1 /*
   2  * Copyright 2015 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 namespace folly { namespace wangle {
  23
  24 /* Codel algorithm implementation:
  25  * http://en.wikipedia.org/wiki/CoDel
  26  *
  27  * Algorithm modified slightly:  Instead of changing the interval time
  28  * based on the average min delay, instead we use an alternate timeout
  29  * for each task if the min delay during the interval period is too
  30  * high.
  31  *
  32  * This was found to have better latency metrics than changing the
  33  * window size, since we can communicate with the sender via thrift
  34  * instead of only via the tcp window size congestion control, as in TCP.
  35  */
  36 class Codel {
  37
  38  public:
  39   Codel();
  40
  41   // Given a delay, returns wether the codel algorithm would
  42   // reject a queued request with this delay.
  43   //
  44   // Internally, it also keeps track of the interval
  45   bool overloaded(std::chrono::microseconds delay);
  46
  47   // Get the queue load, as seen by the codel algorithm
  48   // Gives a rough guess at how bad the queue delay is.
  49   //
  50   // Return:  0 = no delay, 100 = At the queueing limit
  51   int getLoad();
  52
  53   int getMinDelay();
  54
  55  private:
  56   std::chrono::microseconds codelMinDelay_;
  57   std::chrono::time_point<std::chrono::steady_clock> codelIntervalTime_;
  58
  59   // flag to make overloaded() thread-safe, since we only want
  60   // to reset the delay once per time period
  61   std::atomic<bool> codelResetDelay_;
  62
  63   bool overloaded_;
  64 };
  65
  66 }} // Namespace