Building a Distributed Rate Limiter with Redis and Lua for Real-Time Notification Systems
This article details the architectural evolution and implementation of a distributed rate limiting system designed for high-scale, real-time notification services. It highlights the challenges of naive in-memory counters in distributed environments and presents a robust solution using the Token Bucket algorithm, implemented atomically with Redis and Lua scripts to ensure accuracy and handle bursty traffic efficiently.
Read original on Dev.to #systemdesignThe Need for Distributed Rate Limiting
Real-time notification systems, similar to Slack, face significant challenges in managing message volume. A single "power-user" can inadvertently overload a service, causing outages and missed important messages. The core problem is not just message delivery, but controlling the rate of incoming requests to prevent system degradation. A naive, in-memory rate limiter fails dramatically in a distributed setup, as each instance maintains its own counter, leading to actual limits being N times the intended limit across N instances, alongside issues like window drift and lack of persistence.
Why In-Memory Counters Fail in Distributed Systems
- Scaling Issues: Each API gateway instance has its own counter, leading to an aggregated limit of `N * configured_limit` if `N` instances are running.
- Window Drift: `setInterval` for window resets can drift under load, leading to inaccurate limiting (either over-limiting or under-limiting).
- No Persistence: Service restarts or deployments wipe out all counters, creating a window for uncontrolled traffic bursts.
The Token Bucket Algorithm for Robust Rate Limiting
The Token Bucket algorithm is a superior choice for distributed rate limiting due to its inherent properties. Instead of simply counting requests, it models access permissions as "tokens" that refill over time. Each user or API key has a conceptual bucket of tokens; to send a notification, a token must be consumed. If the bucket is empty, the request is rejected or queued.
Advantages of Token Bucket
The Token Bucket algorithm is burst-friendly, allowing users to accumulate tokens during idle periods and spend them in a quick burst. It provides smooth decay as tokens refill continuously, avoiding the "thundering herd" problem associated with fixed-window resets. Crucially, its state can be managed in a distributable and atomic store.
Implementing with Redis and Lua for Atomicity
The breakthrough for a distributed Token Bucket lies in using Redis as a fast, atomic data store and Lua scripts for the core logic. Redis's single-threaded nature combined with Lua's atomic execution ensures that the check-and-consume operation on a token bucket is indivisible. This eliminates race conditions even when multiple API gateway instances concurrently access the same user's rate limit key.