From: Adam Simpkins Date: Thu, 15 Jun 2017 18:03:50 +0000 (-0700) Subject: logging: add new RateLimiter helper class X-Git-Tag: v2017.06.19.00~19 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=commitdiff_plain;h=dc37f8eab5797e63c7cfe6f02de23518a40dcaa3 logging: add new RateLimiter helper class Summary: Add a new RateLimiter API to the logging library, to support rate limiting messages in the future. I have included a single IntervalRateLimiter implementation in this diff. In the future we can add more implementations if necessary, to mimic the functionality available with our older logging code, to make it easier for users to convert to the new framework. Note that RateLimiter is inside a `folly::logging` namespace, unlike most of the other code in the logging library that lives directly in the `folly` namespace. I intentionally chose this since RateLimiter is a fairly generic class name, and I wanted to distinguish it from other possible generic class names in folly. On the other hand, most of the other class names already start with `Log`, so there seems to be no need to put them in a `logging` namespace. Nothing is using this new API yet, but I will use it for some internal logging APIs in an upcoming diff. Later on I also plan to use it to implement per-LogCategory rate limiting, and possibly per-LogHandler rate limiting. Reviewed By: wez Differential Revision: D5162805 fbshipit-source-id: 9b81c2f4544006cd392152a768296bce0c5daaa1 --- diff --git a/CMakeLists.txt b/CMakeLists.txt index 17e04bd9..9aba1846 100755 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -327,6 +327,7 @@ if (BUILD_TESTS) LogMessageTest.cpp LogNameTest.cpp LogStreamTest.cpp + RateLimiterTest.cpp StandardLogHandlerTest.cpp XlogFile1.cpp XlogFile2.cpp diff --git a/folly/Makefile.am b/folly/Makefile.am index f5e365e0..b96b96d5 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -132,6 +132,7 @@ nobase_follyinclude_HEADERS = \ experimental/logging/LogStream.h \ experimental/logging/LogStreamProcessor.h \ experimental/logging/LogWriter.h \ + experimental/logging/RateLimiter.h \ experimental/logging/StandardLogHandler.h \ experimental/logging/xlog.h \ experimental/NestedCommandLineApp.h \ diff --git a/folly/experimental/logging/Makefile.am b/folly/experimental/logging/Makefile.am index 0700d0a1..5cb7ba47 100644 --- a/folly/experimental/logging/Makefile.am +++ b/folly/experimental/logging/Makefile.am @@ -11,6 +11,7 @@ libfollylogging_la_SOURCES = \ LogName.cpp \ LogStream.cpp \ LogStreamProcessor.cpp \ + RateLimiter.cpp \ StandardLogHandler.cpp \ xlog.cpp diff --git a/folly/experimental/logging/RateLimiter.cpp b/folly/experimental/logging/RateLimiter.cpp new file mode 100644 index 00000000..c163c80f --- /dev/null +++ b/folly/experimental/logging/RateLimiter.cpp @@ -0,0 +1,47 @@ +/* + * Copyright 2004-present 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 + +namespace folly { +namespace logging { +IntervalRateLimiter::IntervalRateLimiter( + uint64_t maxPerInterval, + std::chrono::steady_clock::duration interval) + : maxPerInterval_{maxPerInterval}, + interval_{interval}, + timestamp_{std::chrono::steady_clock::now().time_since_epoch().count()} {} + +bool IntervalRateLimiter::checkSlow() { + auto ts = timestamp_.load(); + auto now = std::chrono::steady_clock::now().time_since_epoch().count(); + if (now < (ts + interval_.count())) { + return false; + } + + if (!timestamp_.compare_exchange_strong(ts, now)) { + // We raced with another thread that reset the timestamp. + // We treat this as if we fell into the previous interval, and so we + // rate-limit ourself. + return false; + } + + // In the future, if we wanted to return the number of dropped events we + // could use (count_.exchange(0) - maxPerInterval_) here. + count_.store(1, std::memory_order_release); + return true; +} +} +} diff --git a/folly/experimental/logging/RateLimiter.h b/folly/experimental/logging/RateLimiter.h new file mode 100644 index 00000000..acd04a86 --- /dev/null +++ b/folly/experimental/logging/RateLimiter.h @@ -0,0 +1,68 @@ +/* + * Copyright 2004-present 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 +#include + +namespace folly { +namespace logging { + +/** + * An interface for rate limiting checkers. + */ +class RateLimiter { + public: + virtual ~RateLimiter() {} + virtual bool check() = 0; +}; + +/** + * A rate limiter that can rate limit events to N events per M milliseconds. + * + * It is intended to be fast to check when messages are not being rate limited. + * When messages are being rate limited it is slightly slower, as it has to + * check the clock each time check() is called in this case. + */ +class IntervalRateLimiter : public RateLimiter { + public: + IntervalRateLimiter( + uint64_t maxPerInterval, + std::chrono::steady_clock::duration interval); + + bool check() override final { + auto origCount = count_.fetch_add(1, std::memory_order_acq_rel); + if (origCount < maxPerInterval_) { + return true; + } + return checkSlow(); + } + + private: + bool checkSlow(); + + const uint64_t maxPerInterval_; + const std::chrono::steady_clock::time_point::duration interval_; + + std::atomic count_{0}; + // Ideally timestamp_ would be a + // std::atomic, but this does not work + // since time_point's constructor is not noexcept + std::atomic timestamp_; +}; +} +} diff --git a/folly/experimental/logging/test/RateLimiterTest.cpp b/folly/experimental/logging/test/RateLimiterTest.cpp new file mode 100644 index 00000000..53b3d4ac --- /dev/null +++ b/folly/experimental/logging/test/RateLimiterTest.cpp @@ -0,0 +1,62 @@ +/* + * Copyright 2004-present 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 + +using folly::logging::IntervalRateLimiter; +using std::chrono::duration_cast; +using namespace std::literals::chrono_literals; + +void intervalTest( + uint64_t eventsPerInterval, + std::chrono::steady_clock::duration interval) { + SCOPED_TRACE(folly::to( + eventsPerInterval, + " events every ", + duration_cast(interval).count(), + "ms")); + IntervalRateLimiter limiter{eventsPerInterval, interval}; + for (int iter = 0; iter < 4; ++iter) { + if (iter != 0) { + /* sleep override */ + std::this_thread::sleep_for(interval); + } + for (uint64_t n = 0; n < eventsPerInterval * 2; ++n) { + if (n < eventsPerInterval) { + EXPECT_TRUE(limiter.check()) + << "expected check success on loop " << iter << " event " << n; + } else { + EXPECT_FALSE(limiter.check()) + << "expected check failure on loop " << iter << " event " << n; + } + } + } +} + +TEST(RateLimiter, interval3per100ms) { + intervalTest(3, 100ms); +} + +TEST(RateLimiter, interval1per100ms) { + intervalTest(1, 100ms); +} + +TEST(RateLimiter, interval15per150ms) { + intervalTest(15, 150ms); +}