Implement a Distributed Rate Limiter
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a simple rate limiter library that can run across multiple application servers.
The rate limiter should support a sliding time window policy:
- Each client is identified by a `clientId` string.
- A client may make at most `limit` requests within any `windowMs` millisecond window.
- `allowRequest(clientId, timestampMs)` returns `true` if the request is allowed and records it; otherwise it returns `false`.
- `reset(clientId)` clears the recorded request history for that client.
Your implementation should consider:
1. Multiple application servers checking the same client's limit concurrently.
2. Persistence of rate-limit state so that state is not lost immediately after a process restart.
3. Clock skew between servers.
4. A degraded mode where the shared remote store is unavailable and the system must temporarily fall back to local storage.
5. Recovery after the remote store becomes available again, including how locally recorded state is reconciled.