logoalt Hacker News

simonwtoday at 2:53 PM1 replyview on HN

> 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

The code comments say it was heavily influenced by 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.


Replies

willempienaartoday at 3:12 PM

Also, 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.