From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladimir Davydov Subject: [PATCH 1/2] Introduce basic rate limiter Date: Tue, 11 Dec 2018 19:31:17 +0300 Message-Id: <3dd7090713f05b172286853cb204e7e02a3bee11.1544544474.git.vdavydov.dev@gmail.com> In-Reply-To: References: In-Reply-To: References: To: kostja@tarantool.org Cc: tarantool-patches@freelists.org List-ID: We will use it to limit the rate of log messages. Needed for #2218 --- src/ratelimit.h | 104 +++++++++++++++++++++++++++++++++++++++++++++ test/unit/CMakeLists.txt | 2 + test/unit/ratelimit.c | 78 ++++++++++++++++++++++++++++++++++ test/unit/ratelimit.result | 13 ++++++ 4 files changed, 197 insertions(+) create mode 100644 src/ratelimit.h create mode 100644 test/unit/ratelimit.c create mode 100644 test/unit/ratelimit.result diff --git a/src/ratelimit.h b/src/ratelimit.h new file mode 100644 index 00000000..2bf0bac7 --- /dev/null +++ b/src/ratelimit.h @@ -0,0 +1,104 @@ +#ifndef TARANTOOL_RATELIMIT_H_INCLUDED +#define TARANTOOL_RATELIMIT_H_INCLUDED +/* + * Copyright 2010-2018, Tarantool AUTHORS, please see AUTHORS file. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL + * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR + * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ +#include + +#if defined(__cplusplus) +extern "C" { +#endif + +/** + * Rate limit state. + */ +struct ratelimit { + /** Time interval used for rate limiting, in seconds. */ + double interval; + /** Max number of events per interval. */ + int burst; + /** Number of events emitted in the current interval. */ + int emitted; + /** Number of events suppressed in the current interval. */ + int suppressed; + /** Start time of the current interval. */ + double start; +}; + +/** + * Rate limit state initializer. + */ +#define RATELIMIT_INITIALIZER(interval_init, burst_init) \ + { (interval_init), (burst_init), 0, 0, 0 } + +/** + * Initialize a rate limit state. + */ +static inline void +ratelimit_create(struct ratelimit *rl, double interval, int burst) +{ + rl->interval = interval; + rl->burst = burst; + rl->emitted = 0; + rl->suppressed = 0; + rl->start = 0; +} + +/** + * Check if an event may be emitted. Returns true on success. + * @now is the current time. + * + * If the current interval is over, the total number of events + * suppressed in it is added to @suppressed. + */ +static inline bool +ratelimit_check(struct ratelimit *rl, double now, int *suppressed) +{ + if (now > rl->start + rl->interval) { + /* Current interval is over, reset counters. */ + *suppressed += rl->suppressed; + rl->emitted = 0; + rl->suppressed = 0; + rl->start = now; + } + if (rl->emitted < rl->burst) { + rl->emitted++; + return true; + } else { + rl->suppressed++; + return false; + } +} + +#if defined(__cplusplus) +} /* extern "C" */ +#endif + +#endif /* TARANTOOL_RATELIMIT_H_INCLUDED */ diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt index 7cba5cbb..0025d361 100644 --- a/test/unit/CMakeLists.txt +++ b/test/unit/CMakeLists.txt @@ -136,6 +136,8 @@ add_executable(rmean.test rmean.cc) target_link_libraries(rmean.test stat unit) add_executable(histogram.test histogram.c) target_link_libraries(histogram.test stat unit) +add_executable(ratelimit.test ratelimit.c) +target_link_libraries(ratelimit.test unit) add_executable(say.test say.c) target_link_libraries(say.test core unit) diff --git a/test/unit/ratelimit.c b/test/unit/ratelimit.c new file mode 100644 index 00000000..3dfbe485 --- /dev/null +++ b/test/unit/ratelimit.c @@ -0,0 +1,78 @@ +#include +#include + +#include "unit.h" +#include "ratelimit.h" + +#define check(expected_emitted, expected_suppressed) do { \ + is(emitted, expected_emitted, "emitted %d expected %d", \ + emitted, expected_emitted); \ + is(suppressed, expected_suppressed, "suppressed %d expected %d",\ + suppressed, expected_suppressed); \ +} while (0) + +int +main() +{ + header(); + plan(10); + + srand(time(NULL)); + double now = rand(); + + int burst = 10; + double interval = 5; + int count, emitted, suppressed; + struct ratelimit rl = RATELIMIT_INITIALIZER(interval, burst); + now += interval; + + count = burst; + emitted = suppressed = 0; + for (int i = 0; i < count; i++) { + if (ratelimit_check(&rl, now, &suppressed)) + emitted++; + now += interval / count / 2; + } + check(count, 0); + + emitted = suppressed = 0; + for (int i = 0; i < count; i++) { + if (ratelimit_check(&rl, now, &suppressed)) + emitted++; + now += interval / count / 2; + } + check(0, 0); + + now += 1; + emitted = suppressed = 0; + if (ratelimit_check(&rl, now, &suppressed)) + emitted++; + check(1, count); + + now += interval * 2; + emitted = suppressed = 0; + if (ratelimit_check(&rl, now, &suppressed)) + emitted++; + check(1, 0); + + interval = 5; + burst = 100; + ratelimit_create(&rl, interval, burst); + + int interval_count = 10; + count = burst * interval_count * 4; + emitted = suppressed = 0; + for (int i = 0; i < count; i++) { + if (ratelimit_check(&rl, now, &suppressed)) + emitted++; + now += interval_count * interval / count; + } + now += interval; + ratelimit_check(&rl, now, &suppressed); + check(interval_count * burst, count - interval_count * burst); + + check_plan(); + footer(); + + return 0; +} diff --git a/test/unit/ratelimit.result b/test/unit/ratelimit.result new file mode 100644 index 00000000..8a755c64 --- /dev/null +++ b/test/unit/ratelimit.result @@ -0,0 +1,13 @@ + *** main *** +1..10 +ok 1 - emitted 10 expected 10 +ok 2 - suppressed 0 expected 0 +ok 3 - emitted 0 expected 0 +ok 4 - suppressed 0 expected 0 +ok 5 - emitted 1 expected 1 +ok 6 - suppressed 10 expected 10 +ok 7 - emitted 1 expected 1 +ok 8 - suppressed 0 expected 0 +ok 9 - emitted 1000 expected 1000 +ok 10 - suppressed 3000 expected 3000 + *** main: done *** -- 2.11.0