Rate Limiting Explained: Fixed Windows, Sliding Windows & Token Buckets

code : https://github.com/AKACHI-4/LLD/tree/master/src/main/java/com/lld/rate_limiter

A rate limiter lets you control the rate of traffic that your service processes by blocking requests that exceed a set limit during a period of time.

useful beyond just throttling spam in a chat. For instance, rate limiting a login form can determine brute force attacks while still allowing a small burst of incorrect guesses.

3 most common algorithms :

1. Fixed windows

2. Sliding windows

3. Token buckets

Fixed windows

A set number of requests can be made within a predefined time window. Requests increment a counter that’s reset to zero at the start of each window.

• Cons

  • Allows bursts up to 2x the limit when requests begin near the end of a window

• A brief tangent on 24-hour fixed windows

  There is a subtle issue with the 24-hour limiter above. Its windows reset every day at midnight—but midnight according to which time zone? A standard fixed window might reset its counter according to your server’s midnight or a standard timezone offset such as UTC. A user in a different timezone who just ran out of requests might retry just after midnight and be surprised if the limit hasn’t been lifted—since, to them, it is a new calendar day.

  For these applications, you need to offset your window starts according to the user’s time zone, which has some potential for abuse as users can manually adjust their timezone once they’ve run out of requests to gain up to 1 full window of additional requests. Worse yet, users traveling west to east might incorrectly have more requests limited, while those traveling east to west might incorrectly have more requests allowed. If a rate limit resets based on local midnight and a user moves to an earlier time zone, they encounter earlier local midnights. This can allow them to reset their request count sooner by being in a new “day” earlier than expected, potentially increasing their total allowable requests within a 24-hour period as measured by real time. Yikes. And we still haven’t dealt with DST.

  This use case is already a bit of a tangent, so for now I’ll leave it at this: handling time zones correctly, accounting for users relocating as well as daylight savings, is difficult to get right—so if you’re considering going down that painful path, I’ll just point you to these resources instead. If you can sidestep this problem by using any other approach at all, you should!

Fixed window with user-defined start

Instead of fixing the start times to a set interval, each window can be created at the time of the user’s first request within that window.

With this approach, it’s especially important to show users the time remaining until the next window once they’re limited since there’s no set time that aligns each window.

Sliding windows

Instead of refreshing the capacity all at once, sliding windows refill one request at a time.

• Pros

  • Smooths the distribution of request traffic

  • Well-suited for high loads

• Cons

  • Less predictable for users than fixed windows

  • Storing timestamps for each request is resource-intensive

Logs :

Because sliding windows tend to be most useful in high-traffic scenarios, the fact that the naive algorithm is resource-intensive is counterproductive. Shouldn’t a high-traffic rate limiter use an efficient algorithm?

For this reason, most real-world sliding window rate limiters, such as those provided by Upstash or Cloudflare, use an approximation, often called a floating window. Using this approximation, we have all the same pros but can remove the “resource-intensive” point from the cons.

Here’s how it works:

1. Count the number of allowed requests in the previous fixed window.

2. Count the number of allowed requests in the current fixed window.

3. Weight the previous window’s allowed requests proportional to that window’s overlap with a floating window ending at the current time.

4. Add the weighted requests from (3) to the unweighted requests from (2).

approximation = (prevWindowCount * prevWindowWeight) + currentWindowCount

Counter :

• Calculate Position within Current Window

active fixed window ID = ⌊ CurrentTimestamp / WindowSize ⌋

Progress = Time Elapsed in Current Window / WindowSize

• Fetch Window Counts

  • PrevCount : total allowed requests in the prior fixed window.

  • curCount : total allowed requests so far in the active fixed window.

• Compute Weighted Estimate

EstimatedRequests = ( PrevCount × ( 1 − Progress )) + CurrCount

• Evaluate Decision

  • If EstimatedReq < Limit :

    • Increment curCount by 1.

    • Set TTL on the key to 2 × WindowSize  ( so old window data automatically gets cleaned up ).

  • else-uf EstimatedReq ≥ Limit :

    • Do not increment CurCount.

Strategy	Memory Cost	Accuracy	Stored Data
Sliding Window Log (Exact)	O(N) per request	100% Precise	Every request's epoch timestamp
Sliding Window Counter (Approx)	O(1) constant	~99% Accurate	Only 2 integer counts (Current & Previous window)

basically counter thinks here :

If I know how many requests happened in the previous fixed hour, and I know where I am in the current hour, I can linearly interpolate how many requests fell into the trailing 60-minute frame.

Cloudflare’s configurable rate limiter uses an approximated sliding window.

Token buckets

Instead of thinking in terms of windows with durations, picture a bucket that fills up with tokens at a constant rate. Each request withdraws one token from this bucket, and when the bucket is empty the next request will be blocked.

• capacity of the bucket is the maximum number of requests that a burst can support (not counting tokens that are replenished mid-burst).

• refill interval represents the long-term average allowed request interval.

having distinct burst and average capacities without the need for multiple rate limiters is one of the main benefits to this algorithm.

• Pros

  • allows bursts of high traffic, but enforces a long-term average rate of requests

  • more flexible for users, allowing for traffic spikes within an acceptable range

• Cons

  • more difficult to convey limits and refill times to users than with fixed windows

Real-world examples

• Stripe uses a token bucket in which each user gets a bucket with limit = 500, refillInterval = 0.01s, allowing for sustained activity of 100 requests per second, but bursts of up to 500 requests. (Implementation details.)

• OpenAI’s free tier for GPT-3.5 is limited to 200 requests per day using a token bucket with limit = 200 and refillInterval = 86400s / 200, replenishing the bucket such that at the end of a day (86,400 seconds) an empty bucket will be 100% filled. They refill the bucket one token at a time.

Other considerations

• Create a persisted store for the rate limiter.

• Fail open.

• Optionally throttle bursts.

• Choose sensible keys.

• Surface useful rate limiting errors.