Leaky Bucket Algorithm with no Queue

Question

Basic implementation of a leaky bucket, the idea is you call it by saying I will allow e.g. 5 login attempts per 60 seconds.

 //Leaky Bucket algorithm with chrono
 class RateController {
 int n;
 std::chrono::steady_clock::duration interval;
 int cnt;
 std::chrono::time_point<std::chrono::steady_clock> last;
 public:
 RateController(int limit, int seconds) : 
 n(limit), interval(std::chrono::seconds(seconds/limit)), cnt(0) {}
 bool ok() {
 auto t = std::chrono::steady_clock::now();
 if (cnt) {
 cnt -= (t - last) / interval;
 if (cnt < 0) cnt = 0;
 if (cnt >= n) return false;
 }
 ++cnt;
 last = t;
 return true;
 }
 };

Answer 1

Create a type alias for the clock you want to use

Things become more maintainable and easier to write if you create a type alias for the clock, like so:

using clock = std::chrono::steady_clock;

That way, you can write:

clock::duration interval;
clock::time_point last;
...
auto t = clock::now();

Use an unsigned type for the counters

I recommend using unsigned types for the counters, as they should never be negative. In order to leak without the counter going negative, write:

cnt -= std::min(cnt, (t - last) / interval);

Let the caller pass the interval as a std::chrono::duration

Instead of forcing the caller to pass the duration as an integer describing seconds, and then having to convert this to a std::chrono::duration type yourself, consider changing the parameter seconds of the constructor to be of type clock::duration. The caller can then pass in any std::chrono::duration it likes.

Be aware of integer division

The expression seconds / limit will evaluate to 0 if limit > seconds. This is problematic as it will cause a division by zero later in ok(). I would avoid the division entirely, and have interval mean the interval in which at most limit calls to ok() will return true. Then to leak you just write:

cnt -= std::min(cnt, (t - last) * n / interval);

Naming things

Some things are abbreviated unnecessarily. Instead of cnt, write count. Instead of n, write max_count or limit like you do in the constructor. Instead of t, write now or current_time. It's just a few more characters to type, but it will make the code much clearer to anyone reading it, including yourself in a few months when you've forgotten the details of your implementation.

• CaptainCodeman: Thanks, in particular the division by zero was a serious bug. I wonder, however, is there a chance for integer overflow when you multiply by n before dividing ?
• G. Sliepen: Yes, that's possible if both n and t - last are very large. However, at least there is no division by zero, so it should not cause a crash, and if there are frequent calls to ok() then it's very likely that t - last is going to be small, so this is a case where I would not worry about it. Also note that you could precompute clock::duration(interval) / n, and perhaps assert() that this is not zero to be very sure.
• CaptainCodeman: I feel this is a problem with using "magical" types such as duration, because we can't know if it stores the value in pico-seconds and whether it's safe to multiply..
• G. Sliepen: I agree it's not very explicit. However, the std::chrono::clock types need to have enough precision to store the system clock's timer value, this typically means they store nanoseconds. Also consider that their range must span centuries, so unless you think (t - last) * n would ever be more than a century, it should be fine. If you want to be defensive, think of a duration of only having a precision of 1 second and being stored in an int. Even then (t - last) * n / interval should work fine.