TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design an API Rate Limiter

    SD Mock · Design an API Rate Limiter

    SD Mock · Design an API Rate Limiter

    Overview

    Design a distributed API rate limiter like Stripe's on a live architecture board — drag components, wire them up, and defend your design to an expert interviewer who watches every move.

    Your Instructions

    Design an API rate limiter

    A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.

    This question has a smaller surface than a crawler or a chat system. The signal concentrates in two places: algorithm tradeoffs, where every algorithm has a sharp, checkable failure mode, and distributed correctness, where the race condition and cross-instance synchronization separate memorized answers from real reasoning. Naming "token bucket in Redis" is not a design.

    Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):

    • Notepad. Shared notes. Requirements, capacity math, schema, and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    Build incrementally while you talk. Trace one request end to end through your diagram — including the third request in a second that gets bounced. Argue the tradeoff, not "industry standard."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    Where the limiter lives

    Client-side: no. Clients are forgeable, and you may not control them at all. Inside the API servers: valid — full algorithm control. Middleware in front of the API servers: the standard answer. In a microservice stack that usually means the API gateway, next to SSL termination and auth. The honest decision inputs: if a gateway already exists, add limiting there; a third-party gateway constrains your algorithm choices; limited engineering resources point to a commercial gateway. Under a 2 req/sec rule, a client's third request in one second never reaches an API server — the middleware answers HTTP 429 itself.

    Token bucket vs leaking bucket

    Token bucket (Amazon, Stripe): a bucket of fixed capacity refilled at a steady rate; each request spends a token; empty bucket → drop. Accumulated tokens mean short bursts are allowed by design. Two parameters — bucket size, refill rate — and both are genuinely hard to tune. Usually one bucket per rule per entity: "1 post/sec + 5 likes/sec" is two buckets; a global 10K RPS cap is one shared bucket.

    Leaking bucket (Shopify): a FIFO queue drained at a fixed outflow rate; full queue → drop. It flattens bursts into a smooth stream — good when downstream needs a constant rate — but a burst fills the queue with old requests and recent ones starve.

    The contrast is the point: token bucket permits bursts, leaking bucket erases them. Which one you want is a requirements question (flash sales want token bucket), not an algorithm preference.

    Fixed window and the boundary burst

    Cut time into fixed windows, one counter each, reset at the edge. Cheapest to run and easy to reason about — and broken at the boundary. Limit 5/min: send 5 requests at 2:00:59 and 5 more at 2:01:01, and the rolling minute from 2:00:30 to 2:01:30 saw 10 requests — double the quota. If your product genuinely resets quotas at fixed times, fine; otherwise this flaw is the reason sliding approaches exist. Knowing the boundary burst cold is table stakes for this question.

    Sliding log vs sliding window counter

    Sliding window log keeps every request's timestamp in a sorted set: evict entries older than the window, count, insert, decide. Perfectly accurate in any rolling window — and expensive: at 500 requests/hour it is ~12 KB per user, 12 GB for 1M users, and in Xu's variant even rejected requests still write a timestamp, so memory burns fastest under attack.

    Sliding window counter is the pragmatic hybrid. Weighted-average form: effective = current_count + previous_count × (1 − position_in_window). Worked example: limit 7/min, 5 last minute, 3 so far, request lands 30% in → 3 + 5 × 0.7 = 6.5, round down to 6, under 7 → allow. Or Grokking's bucket form: per-minute sub-counters summed over the last 60. Cost: ~1.6 KB per user, 1.6 GB for 1M users — about 86% less than the log. It is an approximation (it assumes the previous window was evenly distributed), and the honest defense is empirical: Cloudflare measured 0.003% of 400M requests wrongly allowed or limited. Saying "approximate, but the error is negligible in production" is judgment; pretending it is exact is not.

    The read-check-write race

    The naive flow is read counter → compare → write. Counter at 2, limit 3, two requests arrive simultaneously: both read 2, both conclude one more is fine, both write 3. The correct value was 5 — the limit leaked. A per-record lock fixes it but serializes a user's concurrent requests and adds latency. The stronger answers: a Redis Lua script so check-and-increment runs atomically server-side, or sorted-set operations (the ClassDojo rolling-limiter pattern) whose sequence is effectively atomic. Not seeing the race at all is the red flag; seeing it and naming Lua or sorted sets is the strong signal.

    Many limiter instances

    Several stateless limiter servers sit behind a load balancer; a client's requests land on different instances. Per-instance counters see only a slice — the cluster-wide limit silently becomes N× the intended one. Sticky sessions technically work; reject them anyway (neither scalable nor flexible) and say why. The canonical answer is a centralized store (Redis): every instance checks and increments the same counter, with INCR for atomic increments and EXPIRE so counters clean themselves up. Shard by entity key with consistent hashing when one Redis is not enough; a write-back cache (update in cache, flush periodically) is acceptable because a briefly stale counter costs far less than a synchronous write per request.

    When Redis dies, and who you key on

    Fail-open or fail-closed? If the counter store is down, most consumer APIs fail open — a limiter outage must not become a service outage. Security-critical endpoints (login, card attempts) may fail closed. Naming the tradeoff unprompted is bonus signal.

    IP or user ID? IP works pre-authentication (the login path itself needs protection) but NAT and carrier-grade NAT put thousands of users behind one IP, attackers rotate IPs, and IPv6 makes per-IP state explosive. User ID is precise but only exists after auth — and an attacker triggering wrong-password lockouts can DoS a victim's account. The practical answer is a hybrid: IP-based limits on unauthenticated endpoints, user or API-key limits after auth, sometimes both at once. There is no clean single answer; reasoning through it is the signal.

    Reference solution

    One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.

    Requirements (lock these or take the defaults)

    • Server-side API rate limiter; accurately throttle excess requests per entity per window
    • Flexible rules: by user, IP, API key, endpoint — different rule sets must coexist
    • Limits enforced across the cluster, not per server
    • Throttled users get a clear 429 plus information about their limits
    • Non-functional: high availability, low added latency, low memory, fault isolation (the limiter failing must not take the API down)
    • Vocabulary worth a line: hard throttling (never exceed), soft (exceed by a set percent), elastic (exceed when spare capacity exists)

    Capacity

    This question's estimation is memory per algorithm — it decides the algorithm.

    • 1M active users × 10 req/sec limit → up to 10M QPS through the limiter. QPS, not storage, is what forces a distributed limiter with a shared store.
    • Fixed window: 8 B user ID + 2 B count + 2 B minute timestamp + 20 B hash overhead = 32 B/user → 32 MB; +4 B per-record lock → 36 MB for 1M users
    • Sliding log at 500 req/hour: 8 B + (4 B timestamp + 20 B sorted-set overhead) × 500 + 20 B ≈ 12 KB/user → 12 GB for 1M users
    • Sliding window counter, 60 one-minute buckets per hour: 8 B + (4 B time + 2 B count + 20 B hash overhead) × 60 + 20 B ≈ 1.6 KB/user → 1.6 GB — ~86% less than the log

    Rough numbers are fine; the method is what gets graded — and the win is using the numbers: "the log is exact but 12 GB; counters are near-exact at 1.6 GB; I take the approximation."

    Components to put on the board

    How the graph works: clients hit a load balancer that spreads across a stateless rate-limiter tier (in production, usually middleware in the API gateway). Each limiter instance reads its rules from a local cache that a worker refreshes from config, then runs one atomic check-and-increment against shared Redis. Under the limit, the request forwards to the API fleet; over it, the limiter answers 429 with rate-limit headers — optionally parking the work on a queue instead of dropping it. The API servers never see excess traffic.

    Web Client, Mobile Client
        → Load Balancer
        → Rate Limiter (middleware tier, usually in the API Gateway; mark distributed)
            ↔ Cache (rules cache) ← Worker (pulls rule config periodically)
            ↔ Redis (counters: INCR + EXPIRE, Lua for atomicity; mark distributed)
            → Service (API server fleet; mark distributed)   [under limit]
            → 429 + X-Ratelimit headers back to the client   [over limit]
            → Queue (optional: park throttled work instead of dropping)
    

    Components:

    • Clients (Web, Mobile). The traffic sources — including the misbehaving ones. Client-side throttling is a courtesy (cache, respect limits, exponential backoff on 429), never the enforcement point.
    • Load Balancer. Spreads requests across the limiter tier. No sticky sessions: any instance must be able to serve any client, which is exactly why the counters cannot live per instance.
    • Rate Limiter. The middleware tier, stateless and marked distributed. Identifies the entity (user ID after auth, IP before), finds the matching rule, runs the counter check, and either forwards or answers 429 itself. Keeping it in front of the API servers means excess traffic dies here.
    • Cache (rules cache) + Worker. Rules like "5 logins per minute" live in config files (Lyft's open-source format: domain, descriptors, unit, requests_per_unit), not in code. A worker pulls them into a cache the limiter reads locally. Without this, every rule change is a deploy.
    • Redis. The shared counter store — the single source of truth that makes the limit cluster-wide. INCR gives atomic increments, EXPIRE self-cleans stale counters, Lua scripts or sorted sets close the read-check-write race. A database is too slow for a per-request check; disk latency would tax every API call.
    • Service (API servers). The protected fleet. They only ever see traffic that passed the limiter; their capacity planning can trust the caps.
    • Queue. The optional soft path: instead of dropping a throttled request (an order during an overload, say), park it for later processing. Business decision, not a default.

    Walk one request: a client's third request in one second, limit 2/sec

    1. The client sends the request; the Load Balancer routes it to any Rate Limiter instance — no stickiness.
    2. The limiter identifies the entity: user ID from the auth token (or IP on an unauthenticated endpoint), plus the endpoint, and looks up the matching rule in the rules Cache.
    3. The limiter runs one atomic check-and-increment against Redis — a Lua script reads the counter, compares to the limit, and increments in a single server-side step; EXPIRE keeps the counter from outliving its window.
    4. Requests one and two were under the limit: forwarded to a Service instance, response carrying X-Ratelimit-Limit and X-Ratelimit-Remaining.
    5. Request three finds the counter at the cap: the limiter answers 429 Too Many Requests with X-Ratelimit-Retry-After, and the API fleet never sees it. Optionally the work is parked on the Queue instead of dropped.
    6. It would not matter if request three hit a different limiter instance — the counter lives in shared Redis, so every instance gives the same verdict.

    Two requests race at the threshold: counter at 2, limit 3, both read 2, both write 3 — the correct value was 5. This is why step 3 is one atomic operation, not read-then-write. A lock also works but serializes the user's traffic.

    Redis goes down: decide the failure posture per endpoint. Consumer traffic fails open — the limiter must not become the outage. Login and payment attempts fail closed. Say which and why.

    The boundary burst: if the counter in step 3 is a fixed window, 5 requests at 2:00:59 plus 5 at 2:01:01 puts 10 in one rolling minute. The sliding window counter closes that hole for 1.6 KB per user.

    Schema

    Rules(domain, descriptor_key, descriptor_value, unit, requests_per_unit)   — config files, pulled into the rules cache
    Counters(entity_key, window_start, count)                                  — Redis string, INCR + EXPIRE (fixed / sliding-counter windows)
    Buckets(entity_key, minute_bucket → count)                                 — Redis hash, one field per sub-window (sliding-counter variant)
    RequestLog(entity_key → sorted set of timestamps)                          — Redis sorted set (sliding-log variant only)
    
    • entity_key = user ID or IP, plus the API/endpoint when limits are per-API (createURL and deleteURL get separate limits)
    • Shard Redis by entity_key with consistent hashing; replicate for fault tolerance
    • Write-back caching is acceptable: update counters in cache, flush periodically — brief staleness beats a synchronous write per request
    • Rules stay in config, never hardcoded; the worker's refresh interval bounds how fast a rule change lands

    Scaling and wrap-up

    • The limiter tier is stateless and scales horizontally behind the load balancer; Redis shards by entity key
    • Multi-region: run limiters at the edge near users; accept eventual consistency for cross-region counter sync
    • First metrics: 429 rate per rule (too strict? too loose?), limiter-added latency, Redis errors/timeouts — monitor whether the algorithm fits (flash-sale bursts breaking fixed windows → token bucket) and whether the rules fit
    • If time: hard vs soft vs elastic throttling, L3 (iptables per-IP) vs L7 limiting, client-side etiquette (caching, backoff), throttled-request queueing

    Equally defensible variants

    Token bucket as the primary algorithm (Amazon and Stripe run it) if you want bursts and can argue the tuning cost. Leaking bucket where downstream needs a constant rate (Shopify). Sliding log where exactness is worth 12 GB — low-volume, high-stakes limits. Limiting inside the API servers instead of a gateway when the stack is small. A commercial gateway when engineering time is the constraint. What matters is that you can argue the tradeoff.

    More in System Design Interview Prep: AI Coach Edition

    • SD Coach · News Feeds and Typeahead
    • SD Mock · Design Facebook News Feed
    • SD Mock · Design Twitter
    • SD Mock · Design Typeahead Suggestion
    • SD Mock · Design Twitter Search
    • SD Coach · Rate Limiting
    • SD Coach · Event-Driven Systems and Notifications
    • SD Mock · Design a Notification System
    • SD Coach · Async Jobs, Schedulers and Crawlers
    • SD Mock · Design a Web Crawler
    • SD Coach · Distributed Storage
    • SD Mock · Design a Key-Value Store
    View the full course (43 sessions) →