Implement a Per-IP Sliding Window Rate Limiter

Question

The question asks the candidate to design and implement a per-IP sliding window rate limiter, which controls the number of requests a user can make to a service within a specified time frame.

Codemia · Accepted Answer

To implement a per-IP sliding window rate limiter, we need to track the number of requests made by each IP address over a specified time frame. The requirements include:
- Allow a maximum number of requests (e.g., 100 requests) per IP in a given time window (e.g., 1 minute).
- Reset the count after the time window expires.
- Ensure that the solution is efficient and can handle a large number of concurrent requests.

The sliding window algorithm can be implemented using a data structure that tracks timestamps of requests. We can use a dictionary to map IP addresses to a list of timestamps. When a request comes in, we:
1. Remove timestamps that are older than the time window from the list.
2. Check the size of the list to determine if the request can be allowed.
3. If allowed, add the current timestamp to the list.

Here is a Python implementation of the sliding window rate limiter:
```python
from collections import defaultdict
import time

class RateLimiter:
    def __init__(self, max_requests, window_size):
        self.max_requests = max_requests
        self.window_size = window_size
        self.requests = defaultdict(list)

def is_allowed(self, ip):
        current_time = time.time()
        # Remove timestamps that are outside the window
        self.requests[ip] = [t for t in self.requests[ip] if current_time - t < self.window_size]
        if len(self.requests[ip]) < self.max_requests:
            self.requests[ip].append(current_time)
            return True
        return False
```
This implementation uses a defaultdict to store a list of timestamps for each IP address.

While this implementation is straightforward, it has some trade-offs:
- **Memory Usage**: The memory grows with the number of requests and unique IPs. If many requests are made, this could become a problem.
- **Concurrency**: In a multi-threaded environment, additional locking mechanisms may be needed to ensure thread safety.
- **Time Complexity**: The time complexity for checking and adding requests is O(n) for each request due to the cleanup process, which can be optimized further.

In conclusion, the sliding window rate limiter is an effective way to manage request rates per IP. It balances flexibility and simplicity, making it suitable for many applications. Understanding the underlying principles and potential optimizations is key to implementing a robust solution.

Implement a Per-IP Sliding Window Rate Limiter

Ramp

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Ramp Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline