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
24DECLARE_int32(codel_interval);
25DECLARE_int32(codel_target_delay);
26
27namespace 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
57class 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
94