Building a Real-Time Notification System with a Distributed Token Bucket Rate Limiter
This article details the architectural evolution of a real-time notification system, specifically focusing on how to handle high-volume push notifications to third-party providers like FCM and APNs without exceeding rate limits. It highlights the transition from naive in-memory counters to a robust, distributed token bucket rate limiter backed by Redis, demonstrating a practical solution to a common distributed systems challenge.
Read original on Dev.to #architectureThe Challenge: Unthrottled Notification Bursts
The initial notification system operated on a "fire-and-forget" principle, where stateless workers immediately sent push notifications to third-party providers. This architecture failed under sudden surges in user activity, leading to 429 Too Many Requests errors from external APIs and resulting in delayed or lost notifications. The core problem was the lack of a global guardrail to smooth out traffic spikes before they overwhelmed downstream services.
Solution: Distributed Token Bucket Rate Limiting
The chosen solution was a distributed token bucket rate limiter, implemented using Redis for atomic operations across multiple service instances. This approach offers several advantages:
- Burst Tolerance: Allows for short, controlled bursts of traffic by holding a few extra tokens, while still enforcing a long-term average rate.
- Simplicity: Easy to understand; each request consumes a token, and if none are available, the request is either delayed or dropped.
- Global Consistency: When backed by an atomic store like Redis, the rate limiter operates consistently across all service instances, preventing the "each node has its own counter" problem.
Why Token Bucket?
The token bucket algorithm was preferred over fixed-window counters (which can cause burstiness at window starts or unnecessary throttling at edges) and leaky buckets (which can smooth traffic too aggressively, delaying immediately sendable requests). It provides a balance between burst handling and steady rate enforcement.
Implementation with Redis and Lua
The distributed rate limiter leverages a Redis-backed Lua script to atomically manage the token bucket state. The script calculates token refills based on time elapsed, caps tokens at the defined capacity, and attempts to consume one token per request. This atomic operation ensures consistency and prevents race conditions across multiple service instances attempting to acquire tokens simultaneously.
-- redis_token_bucket.lua
-- KEYS[1] = bucket key (e.g., "rate_limit:notifications")
-- ARGV[1] = rate (tokens per second)
-- ARGV[2] = capacity (max tokens)
-- ARGV[3] = now (current unix time in seconds)
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local last = redis.call("HGET", KEYS[1], "last") or now
local tokens = tonumber(redis.call("HGET", KEYS[1], "tokens") or capacity)
-- refill
local delta = math.max(0, now - last)
tokens = math.min(capacity, tokens + delta * rate)
local allowed = 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
end
redis.call("HMSET", KEYS[1], "tokens", tokens, "last", now)
redis.call("EXPIRE", KEYS[1], math.ceil(capacity/rate + 2)) -- auto-clean
return allowed