CoDel (controlled delay) is an active queue management algorithm from networking for battling bufferbloat.
Synopsis
Declared in <folly/executors/Codel.h>
class Codel;Description
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
Types
Name |
Description |
Holds the tunable target delay and interval parameters for Codel. |
Member Functions
Name |
Description |
|
Constructors |
Returns the start time of the current interval. |
|
Get the queue load, as seen by the codel algorithm Gives a rough guess at how bad the queue delay is. |
|
Returns the minimum queueing delay observed during the current interval. |
|
Return a consistent snapshot of the two parameters used by Codel. Since parameters may be updated with the setOptions() method provided above, it is necessary to ensure that reads of the parameters return a consistent pair in which the invariant of targetDelay <= interval is guaranteed; the targetDelay value that is returned is the minimum of targetDelay and interval. |
|
Returns the timeout condition for overload given a target delay period. |
|
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. |
|
Same as overloaded() but with an explicitly supplied current time. |
|
Update the target delay and interval parameters by passing them in as an Options instance. Note that target delay must be strictly smaller than the interval. This is a no‐op if invalid arguments are provided. |
Created with MrDocs