How to implement rate limiting using Redis

Question

I use INCR and EXPIRE to implement rate limiting, e.g., 5 requests per minute:

if EXISTS counter
    count = INCR counter
else
    EXPIRE counter 60
    count = INCR counter

if count > 5
    print "Exceeded the limit"    

However, 5 requests can be sent at the last second minute one and 5 more requests at the first second of minute two, i.e., 10 requests in two seconds.

How can this problem be avoided?

---

Update: I came up with this list implementation. Is this a good way to do it?

times = LLEN counter
if times < 5
    LPUSH counter now()
else
    time = LINDEX counter -1
    if now() - time < 60
        print "Exceeded the limit"
    else
        LPUSH counter now()
LTRIM counter 5

Answer 1

You could switch from "5 requests in the last minute" to "5 requests in minute x". By this it would be possible to do:

counter = current_time # for example 15:03
count = INCR counter
EXPIRE counter 60 # just to make sure redis doesn't store it forever

if count > 5
  print "Exceeded the limit"

If you want to keep using "5 requests in the last minute", then you could do

counter = Time.now.to_i # this is Ruby and it returns the number of milliseconds since 1/1/1970
key = "counter:" + counter
INCR key
EXPIRE key 60

number_of_requests = KEYS "counter"*"
if number_of_requests > 5
  print "Exceeded the limit"

If you have production constraints (especially performance), it is not advised to use the KEYS keyword. We could use sets instead:

counter = Time.now.to_i # this is Ruby and it returns the number of milliseconds since 1/1/1970
set = "my_set"
SADD set counter 1

members = SMEMBERS set

# remove all set members which are older than 1 minute
members {|member| SREM member if member[key] < (Time.now.to_i - 60000) }

if (SMEMBERS set).size > 5
  print "Exceeded the limit"

This is all pseudo Ruby code, but should give you the idea.