Design sliding-window rate limiter with multi-keys
Overview
This question evaluates understanding of precise sliding-window rate limiting, multi-dimensional counters, time-series state management, and distributed systems concerns such as sharding, clock skew, idempotency, and scalable state eviction.
Design a Precise Sliding-Window Rate Limiter
Context
You are designing a rate limiter for an API that must enforce a true sliding-window limit (i.e., at any instant, only the last T seconds of traffic count toward the quota). You will first design a global limiter, then extend it to multi-dimensional limits.
Part A — Global Limit
Design and implement a precise sliding-window rate limiter that enforces a cap of R requests within any rolling T-second window (true sliding window; not fixed window or token bucket). Specify:
- Public interface (inputs, return values, error semantics)
- Data structures and state storage (single-host and distributed options)
- Time source and resolution
- Time and space complexity per request
Part B — Per-Dimension Limits
Each request includes two attributes: userId and userExperience.
Enforce all of the following limits concurrently:
- Global limit: R requests per T seconds
- Per-user limit: U requests per T seconds per userId
- Per-experience limit: X requests per T seconds per userExperience
Explain key design choices:
- How to structure keys/counters to support multiple dimensions without double-counting
- How to evict stale state efficiently
- How to deploy and scale in a distributed environment (sharding, coordination, clock skew, idempotency)
- How to test correctness and edge cases (bursts, boundary timestamps, window rollover)
Solution
Login required