Build a Sliding Window Rate Limiter

Difficulty: Medium · Category: Rate Limiter · Languages: Java 17, Python 3.11, Go 1.22, Node.js 20, TypeScript 5.x

Sliding Window Rate Limiter

Background

Rate limiting is a critical component of any production system. It protects services from being overwhelmed by too many requests — whether from a single abusive client, a traffic spike, or a denial-of-service attack.

A sliding window rate limiter is more accurate than a fixed-window counter because it avoids the "boundary burst" problem where a client can send 2× the limit by timing requests around a window boundary.

Recommended infrastructure: Redis — its atomic operations and > built-in key expiry make it ideal for high-throughput rate limiting.

How It Works

The platform injects your chosen infrastructure SDK(s) via constructor. For example, if you select Redis:

public class MyRateLimiter implements RateLimiterContract {
    private final RedisClient redis;

    public MyRateLimiter(RedisClient redis) {
        this.redis = redis;
    }
}

See the SDK Docs tab for the full API reference of your chosen system.

Your Task

Implement the RateLimiterContract interface. Your implementation must:

1. Store all rate-limit state externally (no in-process counters).
2. Use a sliding window algorithm — not a simple fixed-window counter.
3. Be thread-safe: concurrent calls for the same user must never allow more requests than the configured limit.
4. Automatically expire old request data so memory does not grow unbounded.

Interface

public interface RateLimiterContract {
    boolean allowRequest(String userId);
    void configure(int maxRequests, int windowSizeSeconds);
    int getRemainingRequests(String userId);
    void reset(String userId);
}

Method Details

Constraints

• maxRequests ≥ 1
• windowSizeSeconds ≥ 1
• userId is a non-null string (may be empty)
• Your solution will be tested with up to 10 000 distinct users
• Performance target: ≥ 10 000 ops/sec with p99 latency ≤ 5 ms

Examples

configure(5, 60)          // 5 requests per 60-second window

allowRequest("alice")     → true   (1/5)
allowRequest("alice")     → true   (2/5)
allowRequest("alice")     → true   (3/5)
allowRequest("alice")     → true   (4/5)
allowRequest("alice")     → true   (5/5)
allowRequest("alice")     → false  (rate limited)

getRemainingRequests("alice") → 0
getRemainingRequests("bob")   → 5   (bob hasn't made any requests)

reset("alice")
allowRequest("alice")     → true   (1/5 — counter reset)

Hints

• A sorted set is a natural fit: use the request timestamp as both the score and member. Remove entries outside the window by score range, and count entries inside it.
• Wrap the check-and-add in an atomic script or transaction to ensure the allow/deny decision and the record-insert happen as one unit.
• Set a TTL on each user's key so that idle users' data is automatically cleaned up.
• For getRemainingRequests, compute max(0, maxRequests - currentCount).

Infrastructure your code runs against

• Redis 7.x

How your solution is graded

Your score combines functional correctness (40%), performance (40%) and code quality (20%).

• Target throughput: 10,000 operations/second
• Target p99 latency: 5 ms
• Load test concurrency: 8 concurrent clients
• Load test duration: 10 seconds
• Maximum error rate: 0.1%

Practice this problem

• Solve Build a Sliding Window Rate Limiter in the browser
• Read the walkthrough

Related LLD problems

• Build a Circuit Breaker
• Build a Parking Lot System
• Build a Priority Task Queue
• Build an LRU Cache