Rate limiting: token bucket, leaky bucket, sliding window

Any open API has this risk: one client sends far too many requests. It may be a bug that loops. It may be a person who guesses passwords. Other users then get a slow service. The interviewer asks: "How do you stop one user from using too much?"

A weak answer says "count the requests and block the user". A strong answer says what is counted, for how long, what the user sees when blocked, and how much memory each user costs. It also names a second method and says why it chose one.

At SDE-1 level you should explain one method and the status code. At SDE-2 level you should compare two methods with numbers. At SDE-3 level you should also say how large a burst each method lets through.

Think about a bank that lets you withdraw at most Rs 10,000 a day. The day starts at midnight. At 11:59 pm you withdraw Rs 10,000. At 12:01 am the new day starts, and you withdraw Rs 10,000 again. In two minutes you took Rs 20,000. The rule was kept, but the aim of the rule was not.

Rate limiting means setting a maximum number of requests that a client may send in a period of time. When the client goes over the maximum, the server refuses the extra requests. The rate limiter is the code that counts and decides. It sits at the front of your servers, before the slow work starts.

For this lesson we assume that one program keeps all the counters in its own memory.

What to limit and what the user sees

The limiter needs a key: the name of the client that it counts. Common keys are the user ID, an API key (a secret code that identifies an app), or the IP address. An IP address is weak for a key, because many people can share one address, for example a college network. A user ID needs a login, so it cannot protect a login page. There you count by the account name that is being tried, and by the IP address. You can also set a different limit for each call: a small one for the login call and a larger one for reading.

When a request is over the limit, the server answers with status 429 Too Many Requests. This code says that the client sent too many requests in a given time. The answer may also include a Retry-After header. It tells the client how long to wait: a number of seconds, or a date. Do not use 500 for this. A 500 says the server has a bug. A client that behaves well waits for the Retry-After time and then tries again with backoff (lesson 54).

Five ways to count

Take one rule: 120 requests per minute for each user, which is 2 requests per second.

1. Fixed window. Cut time into equal windows, for example each minute. Keep one counter per user per window. Add 1 for each request. If the counter reaches 120, refuse until the next window starts. It is simple and small. Its weak point is the edge, the moment when one window ends and the next starts. As in the bank, a user can send 120 requests just before the edge and 120 just after it.

2. Sliding window log. Keep the time of every allowed request from the last 60 seconds. For a new request, remove times older than 60 seconds. If 120 times are left, refuse. It is exact, but it stores up to 120 times for each user.

3. Sliding window counter. Keep two counters, for the current window and for the previous one. Estimate the last 60 seconds like this:

• estimate = previous count x weight + current count
• weight = the share of the previous window that is still inside the last 60 seconds

For example, 15 seconds into the minute, 45 of the 60 seconds of the previous window are still inside. So the weight is 45 / 60 = 0.75. This is a guess, because it assumes the previous window's requests were spread evenly. It is small, and it removes most of the edge problem.

4. Token bucket. Picture a bucket that holds up to B tokens. Tokens are added at a steady rate of r tokens per second, and the bucket never holds more than B. Each request takes one token. If the bucket is empty, the request is refused. You do not need a timer. Store the token count and the time of the last request. At each request, add (now - last time) x r tokens, but stop at B. A full bucket lets a client send a burst: many requests at once. After the burst, the client can send only r per second. In any period of T seconds, at most B + r x T requests pass.

5. Leaky bucket. Picture a bucket with a small hole. Requests enter a waiting line of size B. The line lets out one request every 1 / r seconds, at a fixed speed. If the line is full, the new request is refused. The output is smooth, with no bursts, but requests may wait. (A different form of the idea counts the water level and refuses when full. That form gives the same results as the token bucket.)

class TokenBucket:
    def __init__(self, capacity, refill_per_second):
        self.capacity = capacity
        self.refill = refill_per_second
        self.tokens = capacity
        self.last = None

    def allow(self, now):
        if self.last is not None:
            gained = (now - self.last) * self.refill
            self.tokens = min(self.capacity, self.tokens + gained)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

A shop app has an API. The rule is 120 requests per minute for each user, which is 2 per second.

Assumptions (made up to teach with, not real traffic):

• 1,000,000 users are counted at the same time.
• Every stored number takes 8 bytes. We ignore extra memory that real programs add.
• Opening one screen of the app sends 8 requests at once (lesson 14).

Step 1: fixed window. The windows are minute 0 (seconds 0 to 59) and minute 1 (seconds 60 to 119). The user sends 120 requests at second 59 and 120 at second 61 (second 1 of minute 1). Each window sees 120, so all 240 are allowed. This answers the predict box: 240 requests in 2 seconds, which is 2 times the limit.

Step 2: sliding window log. At second 61 the 120 requests from second 59 are still inside the last 60 seconds. So the second group of 120 is refused. The rule is kept. But the memory is 120 x 8 = 960 bytes for each user. For 1,000,000 users that is 960 x 1,000,000 = 960,000,000 bytes, or 960 MB.

Step 3: sliding window counter. Assumption: 96 requests in the previous minute, and 30 so far in this minute, at second 15.

• Estimate = 96 x 0.75 + 30 = 72 + 30 = 102. This is below 120, so the request is allowed.
• With 48 requests so far: 72 + 48 = 120. This is not below 120, so the request is refused.
• Memory: 2 numbers x 8 bytes = 16 bytes per user. For 1,000,000 users: 16 MB. The fixed window and the token bucket also store 2 numbers, so they also take 16 MB.

Step 4: token bucket. Capacity B = 20 and refill r = 2 tokens per second (2 x 60 = 120 per minute).

• The bucket is full. The app opens a screen: 8 requests. Tokens go from 20 to 12. All are allowed. A bucket of 1 or 2 would have refused most of them.
• A script sends 21 requests at the same instant. 20 pass and 1 is refused. After 0.5 seconds, 0.5 x 2 = 1 token is back, so one more passes.
• In any 2 seconds, at most 20 + 2 x 2 = 24 requests pass. The fixed window passed 240.
• In any 10 seconds, at most 20 + 2 x 10 = 40 pass. In one minute, at most 20 + 2 x 60 = 140. The burst size B adds to the limit.
• A user sends 3 requests per second without a pause. The bucket loses 3 - 2 = 1 token each second, so it is empty after about 20 seconds. By then about 3 x 20 = 60 requests were allowed. After that, 2 per second pass and 1 in 3 is refused.
• The refused client gets 429. The next token arrives in (1 - 0) / 2 = 0.5 seconds. Retry-After must be whole seconds, so the server sends Retry-After: 1.

Step 5: leaky bucket. The line holds 4. One request leaves every 500 ms (2 per second). A burst of 10 arrives at once. 4 enter the line and 6 get 429. The 4 leave at 0.5, 1.0, 1.5 and 2.0 seconds. The last one waits 4 x 0.5 = 2 seconds.

• The fixed window solves simplicity and small memory. It costs a burst of 2 times the limit at the edge. I would change it when the edge burst can hurt the service.
• The sliding log solves exactness. It costs memory in proportion to the limit. I would change to the counter when the limit is high or users are many.
• The token bucket solves short bursts, such as a screen that sends 8 requests. It costs that a burst passes at once. I would change to the leaky bucket when the service behind needs a steady flow.
• Limiting by IP address solves limiting before login. It costs fairness for people who share an address. I would limit by user ID once the user is known.

"A fixed window of 120 per minute means at most 120 in any 60 seconds." It means at most 120 in each window. Across the edge, 240 passed in 2 seconds.

"The token bucket and the leaky bucket are the same." The token bucket lets a burst pass at once. The leaky line releases requests at a steady speed, and some wait. In the example, 10 requests arrive together. The token bucket (capacity 20) passes all 10 at once. The leaky bucket releases 1 every 500 ms and refuses 6.

"Rate limiting by IP address is enough." People share addresses. Suppose 2,000 students share one college address, and the limit is 120 per minute for that address. Each student gets 120 / 2,000 = 0.06 requests per minute. And one attacker can use many addresses.

1. Name the five counting methods. Which one allows a burst by design, and which one gives the smoothest output?
2. A token bucket has capacity 10 and refills 5 tokens per second. It is full. A client sends requests as fast as it can for 4 seconds. At most how many requests pass? What is the long-run speed after that?
3. A teammate wants a fixed window of 100 requests per minute to stop password guessing on a login page, and says "the limit is exact". What is wrong with that, and what would you do?