Best Practices

open all | close all

Basic Rate Limiting

Building a rate limiter with Redis is an 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 doesn’t exist (it would have expired 58 minutes prior).

With pseudocode, let’s see how this would work.

 

1
> GET [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
> MULTI
OK
> INCR [user-api-key]:[current minute number]
QUEUED
> EXPIRE [user-api-key]:[current minute number] 59
QUEUED
> EXEC
OK
5 Do service stuff

Two key points to understand from this routine:

  1. INCR on a non-existent key will always be 1. So, the first call of the minute will be result the value of 1
  2. EXPIRE is inside a MULTI transaction along with the INCR, which means form a single atomic operation.

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.