Design an API rate limiter, then say how an iOS client should behave under one. Compare token bucket with a fixed window.

26.8.1 · L5 · Interview

Reported at: Uber

Predict first

What do the token bucket and the fixed window allow for these requests?

struct TokenBucket {
    let capacity: Double, refillPerSecond: Double
    private(set) var tokens: Double
    private var last: Double
    init(capacity: Double, refillPerSecond: Double, now: Double) {
        self.capacity = capacity; self.refillPerSecond = refillPerSecond; tokens = capacity; last = now
    }
    mutating func allow(at now: Double) -> Bool {
        tokens = min(capacity, tokens + (now - last) * refillPerSecond)   // refill for the time that passed
        last = now
        guard tokens >= 1 else { return false }
        tokens -= 1
        return true
    }
}
struct FixedWindow {
    let limit: Int, window: Double
    private var windowStart = 0.0, count = 0
    init(limit: Int, window: Double) { self.limit = limit; self.window = window }
    mutating func allow(at now: Double) -> Bool {
        if now - windowStart >= window { windowStart = (now / window).rounded(.down) * window; count = 0 }
        guard count < limit else { return false }
        count += 1
        return true
    }
}
var bucket = TokenBucket(capacity: 3, refillPerSecond: 1, now: 0)
let times: [Double] = [0, 0, 0, 0, 1, 1.2, 3]
print("bucket:", times.map { bucket.allow(at: $0) ? "ok" : "no" }.joined(separator: " "))

var fixed = FixedWindow(limit: 3, window: 10)
let burst: [Double] = [9.0, 9.1, 9.2, 10.0, 10.1, 10.2, 10.3]       // a burst across the window boundary
let results = burst.map { fixed.allow(at: $0) }
print("fixed window allowed in 1.3 seconds:", results.filter { $0 }.count, "of", burst.count)
var b2 = TokenBucket(capacity: 3, refillPerSecond: 0.3, now: 9.0)
print("bucket allowed in the same burst:", burst.filter { b2.allow(at: $0) }.count, "of", burst.count)

bucket: ok ok ok no ok no ok / fixed window allowed in 1.3 seconds: 6 of 7 / bucket allowed in the same burst: 3 of 7
bucket: ok ok ok ok ok ok ok / fixed window: 3 of 7 / bucket: 7 of 7
bucket: ok no no no ok no ok / fixed window: 6 of 7 / bucket: 6 of 7

Mental model. A fixed window is a turnstile that resets every ten minutes, so people queue at 9:59 and again at 10:00. A token bucket is a jar that refills at a steady drip: you can spend what is in it in a burst, then only as fast as it drips.

Reported at Uber (anonymous, unverified). A fixed window counts requests per time slot (3 per 10 seconds) and resets at the boundary: simple, but a burst straddling the boundary slips through double the limit. The check sends a burst at 9.0 to 10.3 seconds and the fixed window allows 6 of 7 in 1.3 seconds against a limit of 3 per 10 seconds. A token bucket holds up to capacity tokens, refilled at a steady rate; each request spends one, so it permits a controlled burst (the full bucket) and then the steady rate, and the same burst gets only 3 of 7. A sliding window log or counter is the more exact alternative at higher memory cost. On the server, key the limiter by user or API key, keep counters in a shared fast store, make the check atomic, and answer with HTTP 429 and a Retry-After header.

The client side is the iOS half of the question. Treat 429 as “slow down”, not as an error to show: wait for Retry-After if present, otherwise use exponential backoff with jitter so thousands of phones do not retry in lockstep (a retry storm), cap the retries, and only retry idempotent requests (or add an idempotency key). Reduce demand before the server has to push back: debounce search-as-you-type, batch analytics, cache, and coalesce identical in-flight requests. A client-side limiter (a token bucket in front of the network layer) protects against bugs that would loop. The token bucket here takes the clock as an argument, which is how you test it deterministically.

The bucket allows a burst then the refill rate, while the fixed window lets a burst across the boundary through at double the limit.

Common traps

Retrying immediately on a 429. It makes the overload worse; honour Retry-After and add jitter.
Reading the clock inside the limiter. Pass the time in so tests are deterministic.

They might follow up with

How do you rate limit across several servers? A shared store (a counter or token state with an atomic update), or accept a little inaccuracy with per-node limits.
What if a user hits the limit legitimately? Show a calm message and queue the work, not an error screen.

Design an API rate limiter, then say how an iOS client should behave under one. Compare token bucket with a fixed window.

Predict first

Common traps

They might follow up with

Related questions