3 ms·
> Rate limiting is one of the most common Redis use cases. Traditionally, users implemented rate limiters using server-side Lua scripts combined with client log
by simonw 5mo ago
> Rate limiting is one of the most common Redis use cases. Traditionally, users implemented rate limiters using server-side Lua scripts combined with client logic. In Redis 8.8, we introduce a window counter rate limiter (by @raffertyyu, together with the Redis team).
I had a look for this and it turns out it's slightly mis-described there - it's not a window counter, it's a "GCRA (Generic Cell Rate Algorithm)" - a leaky bucket algorithm. Code here: https://github.com/redis/redis/blob/unstable/src/gcra.c https://github.com/redis/redis/blob/unstable/src/gcra.c
The code comments say it was heavily influenced by https://github.com/brandur/redis-cell https://github.com/brandur/redis-cell by Brandur Leach.
It's a neat algorithm (I just learned about it today) - it only needs to store a single integer for each rate-limited key, which is the "Theoretical Arrival Time" when the bucket would next be empty.
- willempienaar 5mo agoAlso, the “cell” in Generic Cell Rate Algorithm is an ATM cell. GCRA is 1990s telecom, the scheduling algorithm ATM switches used to check that 53-byte cells were arriving on the wire at the agreed rate.
- b33j0r 5mo agoAsynchronous Transfer Mode (I had to look it up too.) https://en.wikipedia.org/wiki/Asynchronous_Transfer_Mode https://en.wikipedia.org/wiki/Asynchronous_Transfer_Mode
- Xeoncross 5mo agoI've never liked token buckets (vs sliding window counters) due to the extra work CPU cycles required to "fill" them. It seems like doing an atomic incr on a key based on a `time % 1 minute` or something would be more efficient and then let that key TTL expire X duration later. This results in zero work for rate limiters not in use and only a single push change -> resulting count for ones in use. Nothing but setting the TTL extra is required. Thanks for the links, I'll checkout the Generic Cell Rate Algorithm!