Sliding Window Counter

The limiter keeps just two numbers per key: how many requests it let through in the current fixed window, and in the previous one. To estimate the last W seconds it adds the current count to the part of the previous count that the rolling window still covers, and lets a request through while that estimate is under the limit. Below, an attacker joins two ordinary users: watch who is refused, and see where the estimate is right and where it is not.

User A289 req/sUser B289 req/sAttacker1,736 req/sAPI serverprotectedPrevious and current windowdashed box: the last 5s, which the formula estimates

Each dot stands for 579 real requests. Time is not scaled. The busiest stretch counts what really got through in any 5 seconds in a row, so it shows when the estimate is wrong.

Sizing the shared counter
x average

Busiest hour vs the daily average. The book's estimate uses 2x.

seconds

Real limits often use a minute or an hour; the animation stays short so you can watch the window slide.

  1. 1. Average requests per second

    DAU x requests per user per day / 86,400
    = 1,000,000 x 50 / 86,400 = 579 req/s

  2. 2. Peak requests per second

    average x peak factor = 579 x 2 = 1,157 req/s

  3. 3. Allowed rate r

    r = peak = 1,157 req/s

  4. 4. Limit in any window L

    L = r x window length = 1,157 x 5 s = 5,788 requests
    Checked against the estimate: current + previous x (share of the previous window still in the last 5 s).

  5. 5. What is arriving right now

    average x (1 + attack / 2) = 579 x (1 + 6 / 2) = 2,315 req/s, which is 2.00x r

  6. 6. Memory for the counter

    2 numbers = 16 bytes per key, however busy it gets
    A sliding log of the same limit stores up to 5,788 timestamps for this one key.
  7. Requests arrive faster than r, so from a quiet start the estimate reaches L in about L / live = 2.5 s. After that a request gets in only as the previous window's weight fades, so about 50% are refused (1 - r / live), spread through time. With a shared counter, that includes the innocent users. On average r gets through, but the estimate is only exact when the previous window's traffic was spread evenly. Ordinary uneven traffic lets the busiest single stretch pass L by a fraction; a burst at the very end of a quiet window lets up to nearly 2L = 11,575 through in one stretch.
Why changing only DAU does not change the animation

Doubling DAU doubles the traffic, and because r and L are sized from that same traffic, it doubles them too. Every ratio stays the same, so the counter behaves identically and only the number each dot stands for changes. Unlike the sliding log, the memory does not change at all: it is two numbers either way.

Where these formulas come from

Steps 1 and 2 are the estimation method from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, including its 2x peak. Its rate limiter chapter describes the sliding window counter as the current window's count plus the previous window's count weighted by their overlap, and cites Cloudflare's measurements below. Steps 3 to 6 join the two, written here. The "nearly 2L" case follows from the formula: a full limit at the end of a quiet window is counted as if spread across it, so it is discounted while it is still inside the last W seconds.

Limits of the sliding window counter

Right on average, not in every stretch

Over time it lets through exactly r, and Cloudflare measured it close to the real rate on real traffic. But it estimates, so the busiest single stretch can pass L by a fraction: run the flood and watch the readout. Choose Two bursts: the attack that beat the fixed window mostly fails here, because just after a boundary the previous window still counts almost in full.

Fooled by a burst at the end of a window

The formula assumes the previous window's requests were spread evenly. Choose Late burst: a full limit at the very end of a quiet window is discounted while it is still recent, and the busiest stretch passes the limit. If that matters, use a sliding log.

Two numbers per key

The memory of a fixed window, however much traffic there is, compared with one timestamp per request for a log. It needs only reads and atomic increments, which most key-value stores have.

Use both limits together

Per-user counters keep one client from using up the others' limit; a global limit protects total capacity. Turn on Attacker rotates accounts: every request starts at zero, and only a global limit would notice.

How Cloudflare and Figma use sliding window counters

Two engineering posts from 2017: one measures how accurate the estimate is, the other builds a variant of it.

Cloudflare: two counters and a measured error

Cloudflare's post builds rate limiting for millions of domains on a memcache cluster where only GET, SET and INCR were available, keeping "only two numbers per counter". Its example: a limit of 50 per minute, 42 requests in the previous minute and 18 in the current one, 15 seconds in, gives 42 x 0.75 + 18 = 49.5. The post says the method "assumes a constant rate of requests during the previous sampling period", and reports that across 400 million requests from 270,000 sources, 0.003% were wrongly allowed or rate limited.

Figma: many small windows instead of two

Figma's post describes a variant: instead of two windows it keeps counters for windows 1/60th the size of the limit's window, in a Redis hash, and adds up the ones inside the last hour. More counters make the estimate closer to exact, still at a fraction of a log's memory: in the post's example about 2.4 MB, against about 20 MB for a sliding log.
Sources and credibility

Both are first-hand accounts from the companies' engineering blogs (primary sources). Cloudflare's post was published in June 2017; Figma's is by Nikrad Mahdi, April 2017. Quoted phrases are short attributed quotations; everything else is described in our words.