Sliding Window Log

The limiter keeps the timestamp of every request it lets through. When a request arrives, timestamps older than the window are dropped, and the request passes only if fewer than the limit are left. The window moves with time instead of resetting, so it is exact, but it stores one timestamp per request. Below, an attacker joins two ordinary users: watch who is refused when they share one log and when each has their own.

User A289 req/sUser B289 req/sAttacker1,736 req/sAPI serverprotectedLog of the last 5sABAtt.5s agonow

Each dot stands for 579 real requests. Time is not scaled. In the log, green dots are requests that were let through and red ones are refused requests kept in the log. The busiest stretch counts what got through in any 5 seconds in a row.

Sizing the shared log
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 timestamps age out.

  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
    The same L as a fixed window, but it holds for every 5 seconds in a row, not just windows that start on a boundary.

  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 log

    at most L timestamps = 5,788 x 8 bytes = 45.2 KB
    For one key, before any data-structure overhead. A log per user multiplies this by the number of active users.
  7. Requests arrive faster than r, so the log fills in L / live = 5,788 / 2,315 = 2.5 s. After that, a request gets in only as an old timestamp ages out, so about 50% are refused (1 - r / live), spread through time rather than bunched at the end of a window. With a shared log, that includes the innocent users. In no 5-second stretch can more than L = 5,788 get through.
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 log behaves identically and only the number each dot stands for changes. The memory, though, does double: the log stores every request, however many there are.

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 log: drop outdated timestamps, add the new one, and allow the request if the log is no bigger than the limit. Its worked example keeps a refused request's timestamp in the log, which is what the Refused requests stay in the log switch shows. Steps 3 to 6 join the two, written here.

Limits of the sliding window log

Exact, with no boundary to game

Every request is checked against exactly the last W seconds, so no stretch of W seconds ever lets more than L through. Choose Two bursts: against a fixed window the same attack got twice the limit through.

Memory grows with traffic

A counter is one number per key; a log is one timestamp per request. A busy key with a long window holds a lot of them, and a log per user multiplies that by every active user. This is the main reason people choose something else.

Keeping refused requests in the log

If refused requests are logged too, a client that keeps sending too fast never gets anything through until it slows down. That is a strong penalty for an attacker, but in a shared log it locks out everyone. Turn on Refused requests stay in the log in both modes to compare.

Use both limits together

Per-user logs keep one client from filling the others' windows; a global limit protects total capacity. Turn on Attacker rotates accounts: every request starts a new, empty log, and only a global limit would notice.

How ClassDojo and Figma weighed the sliding log

Both come from one engineering post by Figma, which describes the technique and then explains why Figma did not use it.

A log in a Redis sorted set

Figma's post credits Peter Hayes at ClassDojo with keeping each user's requests in a single Redis sorted set, with the request's timestamp as its score. On each request, timestamps older than the window are removed (ZREMRANGEBYSCORE), the new one is added (ZADD), and the size of the set (ZCARD) is the number of requests in the sliding window. Counting carries on after the limit is reached, which the post notes "would just extend a ban on a malicious user": the same effect as the switch above. One detail from the Redis documentation: members of a sorted set are unique, so two requests with the same timestamp need different member values.

Why Figma chose something else

The post says the sliding log "leaves a considerably large memory footprint because it stores a value for every request." Its own example: 10,000 daily users making 500 requests a day could mean 5,000,000 stored values, about 20 MB at 4 bytes each. Figma built a sliding window counter instead, which in the same example needs at most about 2.4 MB. That is the next algorithm in this series.
Sources and credibility

Figma's post is a first-hand account by the engineer who built their limiter (Nikrad Mahdi, Figma engineering blog, April 2017). The Redis pages are the official command reference. Quoted phrases are short attributed quotations; everything else is described in our words.