Sliding window

Redis based rate limiter

Use a centralized data store such as Redis to store the counts for each window and consumer. Here is a high level architecture map.

Lock: Put a “lock” around the key in question, preventing any other processes from accessing or writing to the counter. This would quickly become a major performance bottleneck, and does not scale well, particularly when using remote servers like Redis as the backing datastore.
Lua script: Use a “set-then-get” approach, relying on Redis' atomic operators that implement locks in a very performant fashion, allowing you to quickly increment and check counter values without letting the atomic operations get in the way.

How to handle the additional latency introduce by performance

In order to make these rate limit determinations with minimal latency, it’s necessary to make checks locally in memory. This can be done by relaxing the rate check conditions and using an eventually consistent model. For example, each node can create a data sync cycle that will synchronize with the centralized data store.
Each node periodically pushes a counter increment for each consumer and window it saw to the datastore, which will atomically update the values. The node can then retrieve the updated values to update it’s in-memory version. This cycle of converge → diverge → reconverge among nodes in the cluster is eventually consistent.
- https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm/

How to avoid multiple round trips for different buckets

Use Redis Pipeline to combine the INCRE and EXPIRE commands
If using N multiple bucket sizes, still need N round trips to Redis.
- TODO: Could we also combine different bucket size together? How will the result for multiple results being passed back from Redis pipeline
Redis rate limiter implementation in python

Performance bottleneck and single point failure due to Redis

Last updated 2 years ago