Design a thread-safe high-QPS rate limiter
Company: Palo
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Technical Screen
You are building a backend service that must enforce API rate limits.
Design and (at a high level) implement a rate limiter that:
1) Enforces a per-identity limit (e.g., per user ID or API key), such as **N requests per second**.
2) Is **thread-safe** in a multi-threaded server.
3) Can handle **high QPS** (very large request volume) with low latency.
Discuss which rate-limiting algorithm you would choose (e.g., token bucket, leaky bucket, fixed/sliding window), the data structures/state you would store, how you would ensure correctness under concurrency, and how you would scale the solution if the service is distributed across many instances.
Quick Answer: This question evaluates understanding of concurrency-safe rate limiting, distributed system scalability, and performance-oriented data structures and algorithms for enforcing per-identity request quotas under high QPS and low-latency constraints.