Building a rate limiter with Redis is easy because of two commands INCR and EXPIRE. The basic concept is that you want to limit requests to a particular service in a given time period. Let’s say we have a service that has users identified by an API key. This service states that it is limited to 20 requests in any given minute.
To achieve this we want to create a Redis key for every minute per API key. To make sure we don’t fill up our entire database with junk, expire that key after one minute as well. Visualize it like this:
User API Key = zA21X31, Green represents unlimited and red represents limited.
Redis Key | zA21X31:0 | zA21X31:1 | zA21X31:2 | zA21X31:3 | zA21X31:4 |
Value | 3 | 8 | 20 | >2 | 20 |
Expires at | Latest 12:02 | Latest 12:03 | Latest 12:04 | Latest 12:05 | Latest 12:06 |
Time | 12:00 | 12:01 | 12:02 | 12:03 | 12:04 |
The key is derived from the User API key concatenated with the minute number by a colon. Since we’re always expiring the keys, we only need to keep track of the minute—when the hour rolls around from 59 to 00 we can be certain that another 59 don’t exist (it would have expired 58 minutes prior).
With pseudocode, let’s see how this would work.
1 |
> [user-api-key]:[current minute number] |
2 | If the result from line 1 is less than 20 (or unset) go to 4 otherwise line 3 |
3 | Show error message and end connection. Exit. |
4 |
> OK > INCR [user-api-key]:[current minute number] QUEUED > EXPIRE [user-api-key]:[current minute number] 59 QUEUED > OK |
5 | Do service stuff |
Two key points to understand from this routine:
The worse-case failure situation is if, for some very strange and unlikely reason, the Redis server dies between the INCR and the EXPIRE. When restoring either from an AOF or in-memory replication, the INCR will not be restored since the transaction was not complete.
With this pattern, it’s possible that anyone one user will have two limiting keys, one that is being currently used and the one that will expire during the same minute window, but it is otherwise very efficient.