6
\$\begingroup\$

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;
    }
};
\$\endgroup\$
13
  • 6
    \$\begingroup\$ This is not really c++. Basically C with a class to tie the functions together. In C++ you would/should use a std::array (if size known at compile time) or a std::vector with reserve. Maybe a FIFO queue is in fact what you need? ie std::queue Your code is probably faster, because it's basically "raw C". But it would be "safer and easier" with C++'s abstractions. \$\endgroup\$ Dec 23 '20 at 20:14
  • 2
    \$\begingroup\$ @OliverSchönrock There is no explicit requirement to not use the C equivalents when the C++ alternative provides no tangible advantage \$\endgroup\$ Dec 23 '20 at 20:23
  • 7
    \$\begingroup\$ @OliverSchönrock Everything that compiles by a C++ compiler and does not compile with a C compiler is "real C++" IMO. We should not be dogmatic and force a specific style. \$\endgroup\$
    – Ilkhd
    Dec 23 '20 at 20:25
  • 5
    \$\begingroup\$ I didn't mean to be dogmatic. And yes of course it's valid. I was simply making the point that if I had used C++ to write that I might have started by using a std::queue and seeing if it's "fast enough". If it is, leave it. If I had used C, I might have written something very similar to the above. My comment was merely meant to thought provoking, not critical. \$\endgroup\$ Dec 23 '20 at 20:27
  • 3
    \$\begingroup\$ The reason to use C++ concepts is that they are less error prone and should not introduce any significant (or any) overhead. Using std::vector or std::array above introduces no overhead but automatically fixes several bugs that your code already has (such not obeying the rule of five). \$\endgroup\$ Dec 24 '20 at 2:32
7
\$\begingroup\$

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;
  ;
};

\$\endgroup\$
12
  • 4
    \$\begingroup\$ I don't recommend those names beginning with _, as they are reserved for the implementation in many contexts. \$\endgroup\$ Dec 24 '20 at 9:53
  • 1
    \$\begingroup\$ @TobySpeight I changed it to postfix underscore. Is that better? \$\endgroup\$ Dec 24 '20 at 10:15
  • 1
    \$\begingroup\$ In personal projects, I don't do Hungarian-style markers (it's a good incentive to keep things simple). At work, I inherited a project that uses m_ prefix, so my new code there is consistent with the existing. The real danger of course is _ followed by uppercase, or __ anywhere in the identifier - implementations can use those for any purpose, including macros. \$\endgroup\$ Dec 24 '20 at 10:24
  • 1
    \$\begingroup\$ Thank you very much for your detailed analysis and excellent suggestions; I have already incorporated most of them. 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. Even nginx uses a queue for rate limiting (it maintains a separate queue per remote IP) \$\endgroup\$ Dec 24 '20 at 14:35
  • 1
    \$\begingroup\$ Curious, in the constructor, is there a reason to write q(std::vector<time_point_t>(n_, time_point_t())) instead of q(n_, time_point_t()) ? \$\endgroup\$ Dec 24 '20 at 14:37
8
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for your valuable suggestions. I have switched to vector. I am curious, though, you mentioned "unchecked allocation"; does C++ throw an exception if vector allocation fails? \$\endgroup\$ Dec 24 '20 at 14:40
  • \$\begingroup\$ You should expect the same std::bad_alloc as from new if vector allocation fails, so no need to change the exception handling in the calling code. I'm not sure what this review is referring to by "unchecked allocation", either. \$\endgroup\$ Dec 26 '20 at 11:37
  • \$\begingroup\$ @TobySpeight Poor wording; I've dropped that phrase. \$\endgroup\$
    – Reinderien
    Dec 26 '20 at 14:25
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ This is more a comment on another answer. However, I notice that your reputation doesn't allow you to comment and it's a helpful comment, so you are forgiven in this case :) Welcome to this site! \$\endgroup\$
    – Sjoerd
    Dec 25 '20 at 11:24
  • \$\begingroup\$ That was kind of my thought process too @Sjoerd 😊 \$\endgroup\$
    – IceGlasses
    Dec 25 '20 at 14:02
  • \$\begingroup\$ What you're alluding to is the use of a "monotonic" clock, called different things depending on what OS you're calling into. \$\endgroup\$
    – Reinderien
    Dec 26 '20 at 15:08
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ The problem with this is that you may have to clear N records in one go, if some time has passed since the last request. (Unless I misunderstood?) \$\endgroup\$ Dec 24 '20 at 14:26
3
\$\begingroup\$

"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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your comment, you are correct, the original code doesn't handle copying correctly. \$\endgroup\$ Jan 4 '21 at 8:13
2
\$\begingroup\$

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()
\$\endgroup\$
2
  • \$\begingroup\$ <ctime> is allowed to dump the same identifiers in the global namespace as well, and most implementations do.So your advice doesn't help. Actually, a better advice is to use a C++ container and the C++ <chrono> header, as other answers say. \$\endgroup\$
    – Sjoerd
    Dec 25 '20 at 11:22
  • \$\begingroup\$ It is indeed allowed to to so. But it's foolish (needlessly non-portable) to assume all targets will do that. Yes, using <chrono> is obviously better for the time stuff (and perhaps std::fill() rather than std::memset()), but this advice applies to all of the C standard library. \$\endgroup\$ Dec 26 '20 at 11:31
1
\$\begingroup\$

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;
};
\$\endgroup\$
1
  • \$\begingroup\$ Good catch, yes you are right. \$\endgroup\$ Jan 10 '21 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.