Design sliding-window rate limiter with multi-keys
Quick Overview
Design sliding-window rate limiter with multi-keys evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Design sliding-window rate limiter with multi-keys
Company: Roblox
Role: Software Engineer
Category: System Design
Difficulty: hard
Interview Round: Technical Screen
Design and implement a precise sliding-window rate limiter for an API. Part A: Enforce a global cap of R requests within any rolling T-second window (true sliding window, not fixed window or token bucket). Specify the public interface, data structures, time resolution, and time/space complexity. Part B: Each request includes userId and userExperience fields. Enforce independent limits per userId and per userExperience concurrently (e.g., U requests per T seconds per userId and 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 this in a distributed environment (sharding, coordination, clock skew, idempotency); and how you would test correctness and edge cases (bursts, boundary timestamps, window rollover).
Quick Answer: Design sliding-window rate limiter with multi-keys evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Design sliding-window rate limiter with multi-keys
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)
Clarifying Questions to Ask Guidance
Clarify users, core use cases, read/write patterns, scale, latency, availability, and data retention.
State explicit assumptions before making sizing or architecture decisions.
Prioritize the functional path first, then address reliability, security, observability, and rollout.
What a Strong Answer Covers Guidance
A scoped requirements summary with concrete non-goals and success metrics.
API, data model, architecture, consistency, capacity, and operations.
Reasoned trade-offs among simple and scalable designs, including bottlenecks and failure modes.
A validation, monitoring, migration, and launch plan appropriate for the risk level.
Follow-up Questions Guidance
What breaks first at 10x traffic or data volume?
How would you degrade gracefully during dependency failures?
What metrics and alerts would prove the design is healthy after launch?