C++ Rate Controller

Question

This is from a high performance server that needs to block anyone who is doing more than limit requests per seconds seconds.

You call check and if it returns true you process the request, otherwise you block it.

It maintains a circular queue, initialized to 0, of the last times the event was triggered.

I use time() because it is faster, in my tests, (on ubuntu) than any other clock measuring function I know of (including all of the C++ timing mechanisms), and 1 second resolution is good enough.

It will be wrong for a few seconds after the 1970 epoch, but I'm not terribly worried about that.

class RateController {
    int n, seconds;
    time_t* q;
    int i;
    void push(time_t t) {
        q[i] = t;
        i = (i + 1) % n;
    }
public:
    RateController(int limit, int seconds): n(limit), seconds(seconds) {
        q = new time_t[n];
        memset(q, 0, sizeof(time_t) * n);
        i = 0;
    }
    ~RateController() {
        delete[] q;
    }   
    bool check() {
        time_t t = time(0);
        push(t);
        return (t - q[i]) >= seconds;
    }
};

Answer 1

As per my comments under your question, I would suggest that you use some C++ abstractions to do the "heavy" lifting for you. eg don't do your own memory allocation with new nor your own initialisation with memset.

Consider using a standard container. If in doubt use std:vector. You could also use std::make_unique to initialise an array, but why? Either way you now don't need a destructor. That's a bigger gain than it seems, because without the destructor, you can comply with the "Rule of zero". With the destructor (ie doing your own resource mgmt) you really need to comply with the "Rule of five", and your current code does not, causing potentially serious bugs as @henje nicely demonstrates below.

Use std::chrono: it's really powerful, makes for easy to read code and allows you to easily adjust the resolution of your RateController. The overhead is unlikely to be an issue unless you are talking millions of requests per seconds per RateController.

While testing I found that your code has a bug: in check() you need to test if the comparison is true before calling push(), or you constantly overwrite your circular buffer and block the system.

For style designate your member variables by postfixing them with _ or similar so they are easy to identify. I like to put the public interface first in a class, but it's getting heavily subjective now.

Suggested use of C++ abstractions:

#include <chrono>
#include <vector>

class RateController {
  using clk_t = std::chrono::system_clock;
  using time_point_t = std::chrono::time_point<clk_t>;

public:
  RateController(unsigned limit, unsigned long milliseconds)
      : n_(limit), milliseconds_(milliseconds),
        q(n_, time_point_t()) {}

  bool check() {
    time_point_t t = clk_t::now();
    bool allowed = t - q[i_] >= std::chrono::milliseconds(milliseconds_);
    if (allowed) push(t);
    return allowed;
  }

private:
  unsigned  n_;
  unsigned long milliseconds_;
  unsigned  i_ = 0;

  std::vector<time_point_t> q;

  void push(time_point_t t) {
    q[i_] = t;
    i_    = (i_ + 1) % n_;
  }
};

Algorithmically, your circular buffer idea could certainly work well, but it's quite a lot of storage, if you have many requests per interval. It depends on your use case.

If you have many throusands of clients and therefore many RateController instances then perhaps you don't want to store 1000 x 8byte unsigned longs (8k) for each one? In that case you could just divide time into predetermined slots (say every 10 minutes) and for each client just keep the time of last request and the number of requests in the current time slice. That would be ~500x less storage? This is similar to what @JerryCoffin was suggesting.

Below is a version which uses the time_slice idea. It basically revolves around an integer division. No more vector or other circular buffer. The behaviour is not identical, but I prefer this one.

If you are concerned that thousands of these RateController instances will all unblock at the same time when the new time slice starts and hence cause a load spike, you can address that too. Just generate a random offset in the range [0, time_slice_seconds) during construction and add it to the current time before doing the integer division. If you do this, I can no longer see the advantage of the circular buffer.

#include <chrono>

class RateController {
  using clk_t        = std::chrono::system_clock;

public:
  RateController(unsigned limit, long time_slice_seconds)
      : n_(limit), time_slice_(time_slice_seconds) {}

  bool check() {
    auto duration_since_epoch = clk_t::now().time_since_epoch();
    long curr_time_slice =
        std::chrono::duration_cast<std::chrono::seconds>(duration_since_epoch).count() /
        time_slice_; // integer division!

    if (curr_time_slice != last_time_slice_) {
      last_time_slice_ = curr_time_slice;
      count_           = 0;
    }
    ++count_;
    return (count_ <= n_);
  }

private:
  unsigned n_;
  long     time_slice_;
  long     last_time_slice_ = 0;
  unsigned count_           = 0;
  ;
};

Answer 2

Overall I'm going to side with Oliver's comment that

This is not really c++ [...] it would be "safer and easier" with C++'s abstractions.

At your scale, you haven't shown any data convincing me that performance will influence choosing "old-style C++" over new, idiomatic C++; and anyway that shouldn't be your first consideration: your first consideration should be for correctness, robustness and testability. All of those have suffered given the use of unmanaged pointers.

My advice - which falls short of recommending specific C++(17|20) constructs since I'm not strong in that area - is to make it right-first, not fast-first. Write this in a style that has safe memory management practices and has solid unit test coverage, then profile it. If the performance is good enough (and I would be surprised if it isn't, but I've been wrong before) then leave it. If the performance suffers and it's the fault of your use of idiomatic C++ and reverting to unsafe memory management solves the problem, then fine - revert the slow pieces.

Put another way, you're either going to pay the cost of using newer C++ abstractions to play with memory safely, or you're going to pay in engineering time poring over Valgrind dumps.

Answer 3

time() and std::chrono::system_clock use system time, which can change. This can cause small issues if, say, NTP changes your clock. But you'll also find that everything dies once a year in the fall when daylight saving time sends you an hour into the past. (At least if your system uses local time zones.)

std::chrono::steady_clock should avoid such issues and is likely a better choice for timing things instead of getting the actual "human" time.

Answer 4

First of all, I'd at least consider doing this a bit differently. Since multiple requests per second is entirely possible, I'd at least consider keeping a count of the number of requests in a given second:

struct count { 
    std::time_t t;
    std::size_t count;
};

With this, I'd probably also keep a running count of the number of requests in the last N seconds. Anytime you get a time_t different from the most recent on record, you add a new count record to your list, and check whether you have any old records to remove from the list. If so, subtract the count for each of them from your current count as you remove them.

But a bit here depends on how fast you really expect to receive requests. If you could have multiple incoming requests per second, this is likely to be a useful optimization. If you're expecting more on the order of multiple seconds between requests, it may be a waste of time.

Assuming we ignore that and stick to some variant of the current design, I'd start by observing that your class really has two rather separate responsibilities. One is keep track of time and timeouts and figuring out whether a request is allowed or not. The other is maintaining a circular buffer you use to implement that.

I'd try to decouple those, such as using a relatively generic circular buffer, and then a class to enforce the timeout that's implemented using the circular buffer.

Answer 5

"This RateController seems handy, I can use it in my function, great!"

bool use_controller(RateController rate_ctr) {
    return rate_ctr.check();
}

int main() {
    RateController rate_ctr{10, 1};
    bool check = use_controller(rate_ctr);
    return rate_ctr.check() || check;
}

"Let me just run it in my debug build, and ..., woah"

=================================================================
==1==ERROR: AddressSanitizer: heap-use-after-free on address 0x607000000028 at pc 0x0000004fa54f bp 0x7fffce7fed80 sp 0x7fffce7fed78
READ of size 8 at 0x607000000028 thread T0
...
0x607000000028 is located 8 bytes inside of 80-byte region [0x607000000020,0x607000000070)
freed by thread T0 here:
    #0 0x4f7710  (/app/output.s+0x4f7710)
    #1 0x4fa508  (/app/output.s+0x4fa508)

previously allocated by thread T0 here:
    #0 0x4f6d48  (/app/output.s+0x4f6d48)
    #1 0x4fa4e0  (/app/output.s+0x4fa4e0)

On a more serious note, you have a bug in your code. This scenario might seem a little contrived but, in general, libraries should be easy to use and hard to misuse. One can easily misuse the controller like in my example code.

The class you are implementing handles a resource and has to implement a copy-constructor and operator= to deal with copies gracefully. Alternatively, you could delete these functions to at least raise a compiler error, when the class is misused.

This could have been prevented by using a more idiomatic C++ solution, like other answers have provided. Implementing a resource-handling class is not trivial and in most cases not necessary because library classes exist to handle most cases.

One way to avoid this bug is to use std::unique_ptr which is not copyable and would make your class non-copyable as well. When you use a std::vector like in Oliver Schönrock's answer, the vector handles copying and allocates a new buffer for you. Then again you might want to be able to copy a controller but refer to the same queue. In this case you could use a std::shared_ptr.

You might want to look into the rule of zero/three/five as it helps with gotchas of custom types. In general, the best way is to use library types which remove the need for you to implement special functions at all.

You can try my test code here. I recommend to use tools like AddressSanitizer (UBSAN, TSAN, vagrant) for catching subtle bugs.

Answer 6

This looks more like C code than C++. I echo the other reviewers: use the abstractions that are available to you (and understand how they work, to have a grasp on the performance characteristics).

However, if you are using C functions in your C++ code, prefer to use the native C++ headers <ctime> and <cstring> rather than <time.h> and <string.h>. Then you get neatly namespaced versions of the identifiers you use:

• std::time_t
• std::time()
• std::memset()

Answer 7

I want to add to Oliver Schönrock's answer, and specifically address the comment you made:

I will say, however, that maintaining a queue is necessary to be able to correctly support short bursts which would otherwise overflow a strictly count-based algorithm.

You can support bursts without maintaining a queue, by implementing a leaky bucket:

#include <chrono>

class RateController {
  using clock_t      = std::chrono::steady_clock;
  using time_point_t = clock_t::time_point;
  using duration_t   = clock_t::duration;

public:
  RateController(unsigned limit, duration_t interval)
      : limit_(limit), interval_(interval) {}

  bool check() {
    // Try to drain the bucket
    if (count_) {
        auto now = clock_t::now();
        auto time_passed = now - last_update_;
        auto drained = time_passed / interval_;

        if (drained) {
            count_ -= drained < count_ ? drained : count_;
            last_update_ = now;
        }
    }

    if (count_ < limit_) {
        ++count_;
        return true;
    } else {
        return false;
    }
  }

private:
  const unsigned limit_;
  const duration_t interval_;
  time_point_t last_update_ = clock_t::now();
  unsigned count_           = 0;
};