Redis is a good service to implement rate limiter, it's fast and east to support distributed system.
GET Get the value of key.
INCR Increments the number stored at key by one.
EXPIRE Set a timeout on key.
MULTI Marks the start of a transaction block.
EXEC Executes all previously queued commands in a transaction and restores the connection state to normal.
ZCOUNT Returns the number of elements in the sorted set at key with a score between min and max.
RPUSH Insert all the specified values at the tail of the list stored at key. If key does not exist, it is created as empty list before performing the push operation. When key holds a value that is not a list, an error is returned.
Redis key (APIKEY, IPs, UserId ...etc) |
191.168.2.10 | 192.168.2.15 |
---|---|---|
Value | 8 | 16 |
Expires at | 12:01 | 12:05 |
- GET: [Redis key]:[current number]
- if current number exceed RATE-LIMITER, return error (drop request)
- MULTI:
- INCR [Redis key]:[current number]
- EXPIRE [Redis key]:[current number] 59 (1 min)
- EXEC
2 key points
- INCR on non-exist key will always be 1.
- EXPIRE is inside a MULTI along with the INCR (means this is a atomic operation)
- easy to implement
- A burst of requests at the end of the window causes server handling more requests than the limit
- Overcome fixed window's cons
- It is not memory-efficient
- It is very expensive because we count the user’s last window requests in each request.
- Overcomes the cons of the fixed window by not imposing a fixed window limit and thus unaffected by a burst of requests at the end of the window.
- Overcomes the cons of sliding logs by not storing all the requests(only the requests limited to queue size) and thus memory efficient.
- Bursts of requests can fill up the queue with old requests and most recent requests are slowed from being processed and thus gives no guarantee that requests are processed in a fixed amount of time.
- This algorithm causes traffic shaping(handling requests at a constant rate, which prevents server overload, a plus point), which slows user’s requests and thus affecting your application.
- Overcomes the cons of the fixed window by not imposing a fixed window limit and thus unaffected by a burst of requests at the end of the window.
- Overcomes the cons of sliding logs by not storing all the requests and avoiding counting for every request and thus memory and performance efficient.
- Overcomes the cons of leaky bucket starvation problem by not slowing requests, not traffic shaping.
- Overcomes all the above algorithms cons, no fixed window limit, memory and performance efficient, no traffic shaping.
- No need for background code to check and delete expired keys.