folly::Codel Class Reference

#include <Codel.h>

Public Member Functions
	Codel ()
bool	overloaded (std::chrono::nanoseconds delay)
int	getLoad ()
std::chrono::nanoseconds	getMinDelay ()
std::chrono::milliseconds	getInterval ()
std::chrono::milliseconds	getTargetDelay ()
std::chrono::milliseconds	getSloughTimeout ()

Private Attributes
std::atomic< uint64_t >	codelMinDelayNs_
std::atomic< uint64_t >	codelIntervalTimeNs_
std::atomic< bool >	codelResetDelay_
std::atomic< bool >	overloaded_

Detailed Description

CoDel (controlled delay) is an active queue management algorithm from networking for battling bufferbloat.

Services also have queues (of requests, not packets) and suffer from queueing delay when overloaded. This class adapts the codel algorithm for services.

Codel is discussed in depth on the web [1,2], but a basic sketch of the algorithm is this: if every request has experienced queueing delay greater than the target (5ms) during the past interval (100ms), then we shed load.

We have adapted the codel algorithm. TCP sheds load by changing windows in reaction to dropped packets. Codel in a network setting drops packets at increasingly shorter intervals (100 / sqrt(n)) to achieve a linear change in throughput. In our experience a different scheme works better for services: when overloaded slough off requests that we dequeue which have exceeded an alternate timeout (2 * target_delay).

So in summary, to use this class, calculate the time each request spent in the queue and feed that delay to overloaded(), which will tell you whether to expire this request.

You can also ask for an instantaneous load estimate and the minimum delay observed during this interval.

1. http://queue.acm.org/detail.cfm?id=2209336
2. https://en.wikipedia.org/wiki/CoDel

Definition at line 57 of file Codel.h.

Constructor & Destructor Documentation

folly::Codel::Codel

(

)

Definition at line 29 of file Codel.cpp.

    : codelMinDelayNs_(0),
      codelIntervalTimeNs_(
          duration_cast<nanoseconds>(steady_clock::now().time_since_epoch())
              .count()),
      codelResetDelay_(true),
      overloaded_(false) {}

Member Function Documentation

milliseconds folly::Codel::getInterval

(

)

Definition at line 93 of file Codel.cpp.

Referenced by overloaded().

                                {
  return milliseconds(FLAGS_codel_interval);
}

int folly::Codel::getLoad

(

)

Get the queue load, as seen by the codel algorithm Gives a rough guess at how bad the queue delay is.

min(100%, min_delay / (2 * target_delay))

Return: 0 = no delay, 100 = At the queueing limit

Definition at line 83 of file Codel.cpp.

References getMinDelay(), and getSloughTimeout().

Referenced by TEST().

                   {
  // it might be better to use the average delay instead of minDelay, but we'd
  // have to track it. aspiring bootcamper?
  return std::min<int>(100, 100 * getMinDelay() / getSloughTimeout());
}

nanoseconds folly::Codel::getMinDelay

(

)

Definition at line 89 of file Codel.cpp.

References codelMinDelayNs_.

Referenced by getLoad().

                               {
  return nanoseconds(codelMinDelayNs_);
}

milliseconds folly::Codel::getSloughTimeout

(

)

Definition at line 101 of file Codel.cpp.

References getTargetDelay().

Referenced by getLoad(), and overloaded().

                                     {
  return getTargetDelay() * 2;
}

milliseconds folly::Codel::getTargetDelay

(

)

Definition at line 97 of file Codel.cpp.

Referenced by getSloughTimeout(), and overloaded().

                                   {
  return milliseconds(FLAGS_codel_target_delay);
}

bool folly::Codel::overloaded

(

std::chrono::nanoseconds

delay

)

Returns true if this request should be expired to reduce overload. In detail, this returns true if min_delay > target_delay for the interval, and this delay > 2 * target_delay.

As you may guess, we observe the clock so this is time sensitive. Call it promptly after calculating queueing delay.

Definition at line 37 of file Codel.cpp.

References codelIntervalTimeNs_, codelMinDelayNs_, codelResetDelay_, count, getInterval(), getSloughTimeout(), getTargetDelay(), now(), and overloaded_.

Referenced by TEST().

                                        {
  bool ret = false;
  auto now = steady_clock::now();

  // Avoid another thread updating the value at the same time we are using it
  // to calculate the overloaded state
  auto minDelay = nanoseconds(codelMinDelayNs_);

  if (now > steady_clock::time_point(nanoseconds(codelIntervalTimeNs_)) &&
      // testing before exchanging is more cacheline-friendly
      (!codelResetDelay_.load(std::memory_order_acquire) &&
       !codelResetDelay_.exchange(true))) {
    codelIntervalTimeNs_ =
        duration_cast<nanoseconds>((now + getInterval()).time_since_epoch())
            .count();

    if (minDelay > getTargetDelay()) {
      overloaded_ = true;
    } else {
      overloaded_ = false;
    }
  }
  // Care must be taken that only a single thread resets codelMinDelay_,
  // and that it happens after the interval reset above
  if (codelResetDelay_.load(std::memory_order_acquire) &&
      codelResetDelay_.exchange(false)) {
    codelMinDelayNs_ = delay.count();
    // More than one request must come in during an interval before codel
    // starts dropping requests
    return false;
  } else if (delay < nanoseconds(codelMinDelayNs_)) {
    codelMinDelayNs_ = delay.count();
  }

  // Here is where we apply different logic than codel proper. Instead of
  // adapting the interval until the next drop, we slough off requests with
  // queueing delay > 2*target_delay while in the overloaded regime. This
  // empirically works better for our services than the codel approach of
  // increasingly often dropping packets.
  if (overloaded_ && delay > getSloughTimeout()) {
    ret = true;
  }

  return ret;
}

Member Data Documentation

std::atomic<uint64_t> folly::Codel::codelIntervalTimeNs_

private

Definition at line 84 of file Codel.h.

Referenced by overloaded().

std::atomic<uint64_t> folly::Codel::codelMinDelayNs_

private

Definition at line 83 of file Codel.h.

Referenced by getMinDelay(), and overloaded().

std::atomic<bool> folly::Codel::codelResetDelay_

private

Definition at line 88 of file Codel.h.

Referenced by overloaded().

std::atomic<bool> folly::Codel::overloaded_

private

Definition at line 90 of file Codel.h.

Referenced by overloaded().

---

The documentation for this class was generated from the following files:

• proxygen/folly/folly/executors/Codel.h
• proxygen/folly/folly/executors/Codel.cpp