Katkat
Back

Design a thread-safe high-QPS rate limiter

Palo Alto NetworksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

A Palo Alto Networks system-design screen: design and implement a thread-safe, high-QPS rate limiter that enforces per-identity request quotas. The answer covers algorithm choice (token bucket vs. fixed/sliding window), atomic per-key state with locks or CAS, hot-path performance, bounded-memory eviction, distributed scaling (Redis+Lua, token leasing, consistent-hash partitioning), and rejection semantics.

Question

You are building a backend service that must enforce API rate limits. Design and (at a high level) implement a rate limiter, then work through the following:

  1. Per-identity limit. Enforce a limit per identity (e.g., per user ID, per IP, or per API key), such as N requests per second.
  2. Thread safety. The limiter must be safe when accessed concurrently by many threads in a multi-threaded server, with no corruption of per-key state and no allowing more requests than intended.
  3. Very high QPS. Handle very large request volume (e.g., millions of checks/sec) with low latency. Discuss the performance bottlenecks and the scaling strategies you would use.
  4. Algorithm choice. State which rate-limiting algorithm you would choose (e.g., token bucket, leaky bucket, fixed window, sliding window), what guarantees it provides (burstiness, fairness, accuracy), and the trade-offs.
  5. State and data structures. Describe the per-key state and the data structures you would store.
  6. Rejection behavior. Explain what happens when a request is rejected (e.g., HTTP 429, Retry-After, queue/delay).
  7. Distributed scaling. Explain how you would scale the solution when the service is distributed across many instances and traffic for a given key can land on any of them.

Be explicit about what you would clarify with the interviewer: limiting scope (per-user / per-IP / per-route / global), whether bursts are allowed or the rate is strict, single-node vs. distributed, exact vs. approximate consistency, and the preferred failure mode.