Create a rate limiter that monitors API usage and enforces request caps. The system should handle many clients (each distinguished by a unique key, like a user ID or API token) and decide whether a given request is permitted based on a sliding time window.
Your implementation must expose two primary operations:
hit(key, timestamp) – Log an access attempt for the specified key at the given timestamp.allowed(key, timestamp) – Return whether the key is currently within its allowed rate at the provided timestamp.The rate limit is expressed as a maximum number of requests permitted inside a sliding window. For instance, a limit of 100 requests per 60-second window means a key should be allowed only if it has made fewer than 100 requests in the last 60 seconds.
# Rate limit: 3 requests per 10-second window
limiter = RateLimiter(max_requests=3, window_seconds=10)
limiter.hit("user_1", 1)
limiter.hit("user_1", 2)
limiter.allowed("user_1", 3) # Returns True (2 hits in window, under limit)
limiter.hit("user_1", 3) # Records 3rd hit
limiter.allowed("user_1", 4) # Returns False (3 hits = limit reached)
limiter.allowed("user_1", 12) # Returns True (hits at t=1,2 expired, only 1 hit remains)
limiter.allowed("user_2", 5) # Returns True (different key, no previous hits)
Build a RateLimiter class that records hits per key using a sliding window.
class RateLimiter:
def __init__(self, max_requests: int, window_seconds: int):
"""
Initialize the rate limiter.
Args:
max_requests: Maximum number of requests allowed within the window
window_seconds: Size of the sliding window in seconds
"""
pass
def hit(self, key: str, timestamp: int) -> None:
"""
Record an access event for the given key at the specified timestamp.
"""
pass
def allowed(self, key: str, timestamp: int) -> bool:
"""
Check if the key is within its rate limit at the given timestamp.
Returns:
True if the number of hits in the current window is < max_requests,
False otherwise.
"""
pass
hit() automatically reject requests that exceed the limit, or always record them?allowed() count a pending request, or only past recorded hits?In a production setting, keys may experience long idle periods followed by new traffic. Your implementation should efficiently purge expired timestamps to avoid unbounded memory growth.
hit() and allowed() operations?Extend your implementation to cope with various edge cases that arise in production systems.
limiter = RateLimiter(max_requests=3, window_seconds=10)
# Burst traffic: multiple hits at same timestamp
limiter.hit("user_1", 5)
limiter.hit("user_1", 5)
limiter.allowed("user_1", 5) # Returns True (2 hits, under limit)
limiter.hit("user_1", 5)
limiter.allowed("user_1", 5) # Returns False (3 hits = limit reached)
# Out-of-order timestamps
limiter.hit("user_2", 10)
limiter.hit("user_2", 8) # Earlier timestamp arrives later
limiter.allowed("user_2", 10) # Should count both hits
# Large time gap
limiter.hit("user_3", 1)
limiter.hit("user_3", 2)
limiter.allowed("user_3", 1000) # Returns True (all previous hits expired)
In a production environment, multiple threads or processes may simultaneously call hit() and allowed() for the same key. Your implementation must be thread-safe and handle concurrent access without race conditions or data corruption.
hit() and allowed() for the same key must produce correct results.# Without proper synchronization, this sequence can fail:
# Initial state: count = 2 (one more request allowed before hitting limit of 3)
# Thread A: allowed("user_1", 100) -> reads count = 2, returns True
# Thread B: allowed("user_1", 100) -> reads count = 2, returns True
# Thread A: hit("user_1", 100) -> count becomes 3
# Thread B: hit("user_1", 100) -> count becomes 4 (exceeds limit!)
# Both threads were allowed, but only one should have been