From 260f12aeeeb1395fe9cbbf188a8fdbd717250988 Mon Sep 17 00:00:00 2001 From: James Sedgwick Date: Tue, 23 Sep 2014 05:46:37 -0700 Subject: [PATCH] move Codel to wangle Summary: under folly::wangle:: Test Plan: ran unit for experimental/wangle, thrift/lib/cpp/concurrency, and a user of FbThreadManager Reviewed By: hans@fb.com Subscribers: trunkagent, fbcode-common-diffs@, fugalh, alandau, bmatheny, everstore-dev@, njormrod FB internal diff: D1566128 --- .../experimental/wangle/concurrent/Codel.cpp | 86 +++++++++++++++++++ folly/experimental/wangle/concurrent/Codel.h | 64 ++++++++++++++ .../wangle/concurrent/test/CodelTest.cpp | 38 ++++++++ 3 files changed, 188 insertions(+) create mode 100644 folly/experimental/wangle/concurrent/Codel.cpp create mode 100644 folly/experimental/wangle/concurrent/Codel.h create mode 100644 folly/experimental/wangle/concurrent/test/CodelTest.cpp diff --git a/folly/experimental/wangle/concurrent/Codel.cpp b/folly/experimental/wangle/concurrent/Codel.cpp new file mode 100644 index 00000000..d6558d4c --- /dev/null +++ b/folly/experimental/wangle/concurrent/Codel.cpp @@ -0,0 +1,86 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include + +#ifndef NO_LIB_GFLAGS + #include + DEFINE_int32(codel_interval, 100, + "Codel default interval time in ms"); + DEFINE_int32(codel_target_delay, 5, + "Target codel queueing delay in ms"); +#endif + +namespace folly { namespace wangle { + +#ifdef NO_LIB_GFLAGS + int32_t FLAGS_codel_interval = 100; + int32_t FLAGS_codel_target_delay = 5; +#endif + +Codel::Codel() + : codelMinDelay_(0), + codelIntervalTime_(std::chrono::steady_clock::now()), + codelResetDelay_(true), + overloaded_(false) {} + +bool Codel::overloaded(std::chrono::microseconds delay) { + bool ret = false; + auto now = std::chrono::steady_clock::now(); + + // Avoid another thread updating the value at the same time we are using it + // to calculate the overloaded state + auto minDelay = codelMinDelay_; + + if (now > codelIntervalTime_ && + (!codelResetDelay_.load(std::memory_order_acquire) + && !codelResetDelay_.exchange(true))) { + codelIntervalTime_ = now + std::chrono::milliseconds(FLAGS_codel_interval); + + if (minDelay > std::chrono::milliseconds(FLAGS_codel_target_delay)) { + 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)) { + codelMinDelay_ = delay; + // More than one request must come in during an interval before codel + // starts dropping requests + return false; + } else if(delay < codelMinDelay_) { + codelMinDelay_ = delay; + } + + if (overloaded_ && + delay > std::chrono::milliseconds(FLAGS_codel_target_delay * 2)) { + ret = true; + } + + return ret; + +} + +int Codel::getLoad() { + return std::min(100, (int)codelMinDelay_.count() / FLAGS_codel_interval); +} + +}} //namespace diff --git a/folly/experimental/wangle/concurrent/Codel.h b/folly/experimental/wangle/concurrent/Codel.h new file mode 100644 index 00000000..f969fc36 --- /dev/null +++ b/folly/experimental/wangle/concurrent/Codel.h @@ -0,0 +1,64 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include +#include + +namespace folly { namespace wangle { + +/* Codel algorithm implementation: + * http://en.wikipedia.org/wiki/CoDel + * + * Algorithm modified slightly: Instead of changing the interval time + * based on the average min delay, instead we use an alternate timeout + * for each task if the min delay during the interval period is too + * high. + * + * This was found to have better latency metrics than changing the + * window size, since we can communicate with the sender via thrift + * instead of only via the tcp window size congestion control, as in TCP. + */ +class Codel { + + public: + Codel(); + + // Given a delay, returns wether the codel algorithm would + // reject a queued request with this delay. + // + // Internally, it also keeps track of the interval + bool overloaded(std::chrono::microseconds delay); + + // Get the queue load, as seen by the codel algorithm + // Gives a rough guess at how bad the queue delay is. + // + // Return: 0 = no delay, 100 = At the queueing limit + int getLoad(); + + private: + std::chrono::microseconds codelMinDelay_; + std::chrono::time_point codelIntervalTime_; + + // flag to make overloaded() thread-safe, since we only want + // to reset the delay once per time period + std::atomic codelResetDelay_; + + bool overloaded_; +}; + +}} // Namespace diff --git a/folly/experimental/wangle/concurrent/test/CodelTest.cpp b/folly/experimental/wangle/concurrent/test/CodelTest.cpp new file mode 100644 index 00000000..f13dc02b --- /dev/null +++ b/folly/experimental/wangle/concurrent/test/CodelTest.cpp @@ -0,0 +1,38 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include +#include + +TEST(CodelTest, Basic) { + using std::chrono::milliseconds; + folly::wangle::Codel c; + std::this_thread::sleep_for(milliseconds(110)); + // This interval is overloaded + EXPECT_FALSE(c.overloaded(milliseconds(100))); + std::this_thread::sleep_for(milliseconds(90)); + // At least two requests must happen in an interval before they will fail + EXPECT_FALSE(c.overloaded(milliseconds(50))); + EXPECT_TRUE(c.overloaded(milliseconds(50))); + std::this_thread::sleep_for(milliseconds(110)); + // Previous interval is overloaded, but 2ms isn't enough to fail + EXPECT_FALSE(c.overloaded(milliseconds(2))); + std::this_thread::sleep_for(milliseconds(90)); + // 20 ms > target interval * 2 + EXPECT_TRUE(c.overloaded(milliseconds(20))); +} -- 2.34.1