Why this matters
A rate limiter is a piece of code that decides whether a request should be allowed or rejected, based on how many requests the same user sent recently. Web services use rate limiters every day. A login page might allow five attempts per minute, so a script cannot try a million passwords. A paid API might allow 100 calls per second for each customer, so one busy customer cannot slow everyone else down.
This lesson builds one rate limiter from the start. The main data structure is a per-user queue of request times. The earlier lessons in this module covered unordered_map and map, and this lesson uses an unordered_map to find each user's queue. The queue itself is a std::deque, which you will meet in the first section. The idea is called a sliding window because the window of time you look at moves forward as time moves forward.
The rule in plain words
The rule has two numbers:
limitis the most requests a user may make inside one window.windowis the length of the window, in the same time units as the request times.
A request is allowed when the user has made fewer than limit requests in the last window time units. Otherwise the request is rejected.
Take limit 3 and window 10, with the time measured in seconds. A user sends requests at seconds 0, 1, 2 and 3. The first three are allowed. The request at second 3 is rejected, because three requests already happened in the last 10 seconds. At second 10, the request from second 0 is exactly 10 seconds old, so it no longer counts. One slot opens, and a request at second 10 is allowed.
The word "sliding" matters. A simpler design uses a fixed window, which resets its counter at fixed times, such as every minute on the minute. A fixed window has a weak spot. A user can send 3 requests at second 59 and 3 more at second 60, which is 6 requests in two seconds, and the limit still says 3 per minute. A sliding window looks back from the current moment, so the same burst is rejected.
Step 1: a queue of times
Each user needs a list of the times of their recent allowed requests. The list has two properties that decide the data structure:
- New times are added at the back, because time only moves forward.
- Old times are removed from the front, because the oldest request is the first one to leave the window.
A list that adds at one end and removes at the other end is a queue. C++ has a standard queue type that is built on a double-ended queue, called std::deque. A deque is a list where you can add and remove at both ends in constant time. You use push_back to add a time, front to read the oldest time, and pop_front to remove it.
You could use std::vector, but removing from the front of a vector shifts every other element, which takes time proportional to the length of the vector. A deque removes from the front in constant time, so it fits this job better.
How much memory each user takes
The queue for one user never holds more than limit times, because allow refuses a request when the queue is full and does not store it. So the memory for one user is bounded by the limit, not by how many requests the user sends. A user who sends a million requests a day still has at most limit times stored at any moment.
The only part that grows with the number of users is the map itself, with one entry for each user seen. That growth is why the cleanup function appears in worked example 3.
A single count per user would use less memory, but it cannot tell which requests have left the window. A count says how many requests happened, and a queue keeps the time of each one, so the limiter can remove exactly the requests that are too old.
The code below uses plain integers for the times. The caller passes the time in with each request. Real services read the time from a clock, such as std::chrono::steady_clock, which only moves forward. Passing the time in is useful for learning, because the same input always gives the same output. You can run every example and check the answers by hand.
Worked example 1: one user, a small window
Here is the first version of the limiter. The allow function is the whole rule.
#include <cstddef>
#include <deque>
#include <iostream>
#include <string>
#include <unordered_map>
class RateLimiter {
public:
RateLimiter(int limit, long long window) : limit_(limit), window_(window) {}
bool allow(const std::string& user, long long now) {
std::deque<long long>& times = history_[user];
drop_old(times, now);
if (static_cast<int>(times.size()) < limit_) {
times.push_back(now);
return true;
}
return false;
}
// Removes users who have no request left in the window.
void forget_idle(long long now) {
for (auto it = history_.begin(); it != history_.end();) {
drop_old(it->second, now);
if (it->second.empty()) {
it = history_.erase(it);
} else {
++it;
}
}
}
std::size_t tracked_users() const { return history_.size(); }
private:
void drop_old(std::deque<long long>& times, long long now) const {
while (!times.empty() && now - times.front() >= window_) {
times.pop_front();
}
}
int limit_;
long long window_;
std::unordered_map<std::string, std::deque<long long>> history_;
};The class has three parts. The history_ map gives each user a deque of times. The drop_old helper removes times that have left the window. The allow function drops the old times, checks the count, and either stores the new time or refuses it.
The line history_[user] uses operator[]. For a user who has never been seen, it creates an empty deque. That is what we want here, because the next step would create it anyway. Lesson 18 in this module shows what goes wrong when operator[] is used for a lookup that should not create anything.
The removal test is now - times.front() >= window_. A time is too old when its age is at least the window length. With a window of 10, the time at second 0 is too old at second 10, but the time at second 1 is still counted at second 10. So at second 10 the window covers the times 1 through 10, which is 10 time units.
Now run the limiter on the events from the rule above, with a small list of users:
int main() {
RateLimiter limiter(3, 10);
struct Event { std::string user; long long time; };
std::vector<Event> events = {
{"ann", 0}, {"ann", 1}, {"ann", 2}, {"ann", 3},
{"bob", 3},
{"ann", 9}, {"ann", 10}, {"ann", 11},
};
for (const Event& e : events) {
std::cout << e.user << " at " << e.time << ": "
<< (limiter.allow(e.user, e.time) ? "allowed" : "rejected") << '\n';
}
}This main uses std::vector, so add #include <vector> at the top. The compiler command is g++ -std=c++20 -Wall -Wextra -o limiter limiter.cpp. Running it prints:
ann at 0: allowed
ann at 1: allowed
ann at 2: allowed
ann at 3: rejected
bob at 3: allowed
ann at 9: rejected
ann at 10: allowed
ann at 11: allowedFollow Ann's queue by hand. At time 0, the queue is empty, so the request is allowed and the queue becomes 0. At time 1 it becomes 0 1, and at time 2 it becomes 0 1 2. At time 3, nothing is old enough to drop, because 3 - 0 is 3 and 3 is less than 10. The queue already has 3 items, which equals the limit, so the request is rejected. The rejected request is not added to the queue.
Bob has his own queue, so his request at time 3 is allowed even though Ann was rejected at the same moment.
At time 9, Ann's queue is still 0 1 2. The request is rejected again. At time 10, the time 0 is now 10 units old, so it is removed. The queue becomes 1 2, which is below the limit, so the request is allowed and the queue becomes 1 2 10. At time 11, the time 1 is 10 units old, so it is removed. The queue becomes 2 10, and the request is allowed again.
Worked example 2: a client that keeps retrying
Rejected requests are easy to get wrong. Suppose a program stores every request in the queue, including the rejected ones. It looks like a small change, and it breaks the limiter. The next example puts the correct class and a wrong class side by side and sends the same stream of requests to both. The wrong class is called BadRateLimiter. The line that is different from the correct version is marked in the comment.
class BadRateLimiter {
public:
BadRateLimiter(int limit, long long window) : limit_(limit), window_(window) {}
bool allow(const std::string& user, long long now) {
std::deque<long long>& times = history_[user];
while (!times.empty() && now - times.front() >= window_) {
times.pop_front();
}
bool ok = static_cast<int>(times.size()) < limit_;
times.push_back(now); // bug: pushed even when rejected
return ok;
}
private:
int limit_;
long long window_;
std::unordered_map<std::string, std::deque<long long>> history_;
};
int main() {
RateLimiter good(2, 5);
BadRateLimiter bad(2, 5);
for (long long t = 0; t <= 12; ++t) {
bool g = good.allow("zoe", t);
bool b = bad.allow("zoe", t);
std::cout << "t=" << t << " good=" << (g ? "yes" : "no")
<< " bad=" << (b ? "yes" : "no") << '\n';
}
}The client in this example asks once every time unit, from time 0 to time 12. The output is:
t=0 good=yes bad=yes
t=1 good=yes bad=yes
t=2 good=no bad=no
t=3 good=no bad=no
t=4 good=no bad=no
t=5 good=yes bad=no
t=6 good=yes bad=no
t=7 good=no bad=no
t=8 good=no bad=no
t=9 good=no bad=no
t=10 good=yes bad=no
t=11 good=yes bad=no
t=12 good=no bad=noThe correct limiter lets the client through again at time 5, after the first request has left the window. The wrong limiter never lets the client through again. At time 2, it stores a rejected request, and that rejected request stays in the queue. At time 5, the time 0 leaves the window, but the time 1 and the rejected times 2, 3 and 4 are still there. The queue holds more than the limit. Each new rejected request adds another time, so the queue never drops below the limit. A client that keeps retrying is locked out forever. This is a common outcome of a small bookkeeping error.
The fix is the one line that the correct version has: only add the time when the request is allowed.
Worked example 3: cleaning up idle users
The map in the class has one entry for every user the limiter has ever seen. If a million users each send one request, the map keeps a million entries, even when no user is still inside a window. The forget_idle function in the class removes the entries that have no request left in the window.
The function walks through the map with an iterator. An iterator is an object that points to one element of a container and moves to the next element. The erase line has a detail that matters:
it = history_.erase(it);erase removes the element at it and returns an iterator to the element after it. If you wrote history_.erase(it); and then ++it;, the iterator would point at a removed element, and the program would have undefined behaviour. The loop only moves the iterator forward when nothing was erased, so each element is visited exactly once.
Here is the main function from the program that runs the cleanup:
int main() {
RateLimiter good(2, 5);
good.allow("max", 0);
std::cout << "tracked before cleanup: " << good.tracked_users() << '\n';
good.forget_idle(20);
std::cout << "tracked after cleanup: " << good.tracked_users() << '\n';
}It prints:
tracked before cleanup: 1
tracked after cleanup: 0The window is 5, and the last request was at time 0. At time 20, that request is 20 units old, so it has left the window, and the user has nothing left to remember. The cleanup removes the entry.
In a real service, forget_idle would run on a timer, for example once a minute. The limiter also needs a plan for thread safety, because web servers handle requests in parallel. That topic is outside this lesson, so the code here runs in one thread only.
Choosing the right numbers
The limit and window numbers are chosen by the people who run the service, not by the code. A few points help with the choice:
- A window of 60 with a limit of 5 means at most 5 requests in any 60 seconds. A burst of 5 at second 0 blocks the user until second 60.
- A larger limit lets short bursts through. A smaller limit protects the server more but blocks honest users sooner.
- Time units must match. If requests are timed in milliseconds, the window must also be in milliseconds. A window of 60 in a millisecond system means 60 milliseconds, not one minute.
The constructor should refuse numbers that do not make sense. A limit of zero blocks every request, and a window of zero or less makes the age test meaningless. The next section shows how to reject these values.
Checking the queue without changing it
Sometimes a caller wants to know how many requests a user has made in the window, without making a new request. The function below counts the times that are still inside the window. It is a const member function, so it cannot change the map. The std::count_if algorithm counts the elements that match a condition. Here it is part of a stricter class that also checks its constructor arguments:
#include <algorithm>
#include <stdexcept>
class StrictLimiter {
public:
StrictLimiter(int limit, long long window) : limit_(limit), window_(window) {
if (limit <= 0 || window <= 0) {
throw std::invalid_argument("limit and window must be positive");
}
}
bool allow(const std::string& user, long long now) {
std::deque<long long>& times = history_[user];
while (!times.empty() && now - times.front() > window_) {
times.pop_front();
}
if (static_cast<int>(times.size()) < limit_) {
times.push_back(now);
return true;
}
return false;
}
int pending(const std::string& user, long long now) const {
auto it = history_.find(user);
if (it == history_.end()) {
return 0;
}
return static_cast<int>(std::count_if(it->second.begin(), it->second.end(),
[&](long long t) { return now - t < window_; }));
}
private:
int limit_;
long long window_;
std::unordered_map<std::string, std::deque<long long>> history_;
};Two details differ from the earlier class. The allow function here uses > where the earlier class used >=. This changes which requests count as old, and the next practice exercise asks you to work out the difference. The pending function uses find and not operator[]. A call to operator[] would add an empty entry for a user who has never made a request, which is a side effect a query should not have.
The main function for this test has limit 2 and window 4. It sends requests at times 0, 1, 2, 4 and 5, then checks the pending count, then checks the constructor:
int main() {
StrictLimiter s(2, 4);
for (long long t : {0LL, 1LL, 2LL, 4LL, 5LL}) {
std::cout << "t=" << t << " " << (s.allow("ann", t) ? "yes" : "no") << '\n';
}
std::cout << "pending at 5: " << s.pending("ann", 5) << '\n';
std::cout << "pending for unknown user: " << s.pending("nobody", 5) << '\n';
try {
StrictLimiter bad(0, 4);
} catch (const std::invalid_argument& e) {
std::cout << "error: " << e.what() << '\n';
}
}It prints:
t=0 yes
t=1 yes
t=2 no
t=4 no
t=5 yes
pending at 5: 1
pending for unknown user: 0
error: limit and window must be positiveThe last line comes from the constructor, which was given a limit of 0. The try block catches the exception and prints its message. The message text is set by the string you pass to std::invalid_argument.
Common mistakes
Adding a rejected request to the queue. This is the mistake in worked example 2. The symptom is a user who stays blocked long after the window has passed. Store a time only on the path that returns true.
Off-by-one in the age test. Using > where the rule needs >= keeps a request one unit longer than intended. The result is that a user gets one fewer request than the limit allows at the window boundary. Pick one form, write down what it means in words, and test the boundary time, which is the time exactly one window after the first request.
Using a vector and erasing from the front. The code still compiles and gives the right answers, but each removal shifts the rest of the list. With many requests per user, the program slows down. Use std::deque for a queue that removes from the front.
Reading the clock inside the limiter. A limiter that calls std::chrono::steady_clock::now() inside allow is hard to test, because two runs never see the same times. Pass the time into the function, as this lesson does, and read the clock in the code that calls the limiter.
Forgetting that the map grows. A limiter with no cleanup keeps one map entry per user ever seen. The memory grows with every new user, even after they stop sending requests. Run forget_idle on a schedule, or remove the entry when its queue becomes empty.
A compile error from a missing header. If you use std::count_if and do not include <algorithm>, g++ 15 reports an error such as:
ce1.cpp: In function ‘int main()’:
ce1.cpp:5:23: error: ‘count_if’ is not a member of ‘std’The fix is to add #include <algorithm> at the top of the file.
Practice
Exercise 1: trace a limiter by hand
Use the class from worked example 1, with limit 2 and window 4. The requests for one user arrive at times 0, 1, 2, 4 and 5. For each request, write yes or no, and say what was in the queue before the request.
Show the answer
The answers are yes, yes, no, yes, yes. At time 0 the queue is empty, so the request is allowed and the queue becomes 0. At time 1 it becomes 0 1. At time 2 the queue has 2 items, so the request is rejected and the queue stays 0 1. At time 4, the time 0 is 4 units old, which is at least the window of 4, so it is removed. The queue becomes 1, the request is allowed, and the queue becomes 1 4. At time 5, the time 1 is 4 units old and is removed. The queue becomes 4, the request is allowed, and the queue becomes 4 5.
Exercise 2: change the boundary
Use the StrictLimiter class with limit 2 and window 4. The requests arrive at times 0, 1, 2, 4 and 5. Predict the answers before you run the code, then check them.
Show the answer
The answers are yes, yes, no, no, yes. The strict test removes a time only when its age is more than 4, so at time 4 the time 0 is still counted. The queue has 2 items, so the request at time 4 is rejected. At time 5 the time 0 is 5 units old, so it is removed. The time 1 is 4 units old, which is not more than 4, so it stays. The queue has 1 item, so the request is allowed.
Exercise 3: reject a bad window
Add a check to the RateLimiter constructor so that it throws std::invalid_argument when limit is 0 or less. Write the constructor, then a test that calls it with 0 and prints the message.
Show the answer
RateLimiter(int limit, long long window) : limit_(limit), window_(window) {
if (limit <= 0 || window <= 0) {
throw std::invalid_argument("limit and window must be positive");
}
}The test is:
try {
RateLimiter bad(0, 4);
} catch (const std::invalid_argument& e) {
std::cout << "error: " << e.what() << '\n';
}The output is error: limit and window must be positive. The check goes in the constructor, so an invalid limiter never exists.
Exercise 4: count the requests still in the window
Write a const member function int pending(const std::string& user, long long now) const for the RateLimiter class. It returns how many stored times for that user are still inside the window. It must not add an entry for a new user.
Show the answer
int pending(const std::string& user, long long now) const {
auto it = history_.find(user);
if (it == history_.end()) {
return 0;
}
return static_cast<int>(std::count_if(it->second.begin(), it->second.end(),
[&](long long t) { return now - t < window_; }));
}The function uses find, so a query for an unknown user returns 0 and does not change the map. The lambda counts the times whose age is less than the window. The now - t < window_ test is the opposite of the removal test, so a time is counted exactly when it would not be removed.
Exercise 5: why a deque and not a vector
Explain in two or three sentences why std::deque is a better choice than std::vector for the per-user queue. Use the words front, shift and constant time in your answer.
Show the answer
A limiter removes times from the front of the queue, which is the oldest request. In a vector, removing the first element moves every other element one place forward, so the cost grows with the length of the queue. In a deque, pop_front takes constant time, which does not depend on how many times are stored.
Summary
- A sliding window rate limiter allows at most
limitrequests for one user in the lastwindowtime units. - Store each user's allowed request times in a
std::deque, oldest at the front, and remove old times from the front. - Add a time only when the request is allowed. A stored rejected request keeps a user blocked.
- A time is too old when its age is at least the window length, so the window covers exactly
windowtime units. - Pass the time into the limiter, so runs can be repeated and checked by hand.
- Remove users who have nothing left in the window, using
erasewith the iterator it returns.