Design a Client-Specific Rate Limiter

Problem: Design a rate limiter specific to a client. Given a maximum of R requests allowed from a client in a time window of T seconds, design a system to enforce this limit. How would you handle the failure scenario where more requests arrive than can be processed?

Constraints: Must track requests per-client (not globally), support high request throughput, and behave correctly under bursty traffic.

Approach:

• Maintain, per client, a queue/log of recent request timestamps (sliding window log algorithm), or use a sliding window counter / token bucket for a more memory-efficient approximation.
• On a new request, use binary search on the sorted timestamp log to find how many requests fall within the last T seconds; if that count is >= R, reject or queue the request.
• For handling overload (more requests than can be processed immediately), buffer requests in a queue and process asynchronously, applying backpressure or shedding load once the queue exceeds a threshold, and returning a 429-style rejection to the client.
• At scale, this state is typically kept in a fast shared store like Redis (using sorted sets keyed by client id) so multiple API gateway instances see a consistent view per client.