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 |
94 | |