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.

Answer 2

The canonical way to do rate limiting is via the Leaky bucket algorithm. The downside of using a counter, is that a user can perform a bunch of request right after the counter is reset, i.e. 5 actions in the first second of the next minute for your case. The Leaky bucket algorithm solves this problem. Briefly, you can used ordered sets to store your "leaky bucket", using action time stamps as keys to fill it.

Check out this article for the exact implementation: Better Rate Limiting With Redis Sorted Sets

UPDATE:

There is also another algorithm, which has some advantages compared to leaky bucket. It's called Generic Cell Rate Algorithm . Here's how it works at the higher level, as described in Rate Limiting, Cells, and GCRA:

GCRA works by tracking remaining limit through a time called the “theoretical arrival time” (TAT), which is seeded on the first request by adding a duration representing its cost to the current time. The cost is calculated as a multiplier of our “emission interval” (T), which is derived from the rate at which we want the bucket to refill. When any subsequent request comes in, we take the existing TAT, subtract a fixed buffer representing the limit’s total burst capacity from it (τ + T), and compare the result to the current time. This result represents the next time to allow a request. If it’s in the past, we allow the incoming request, and if it’s in the future, we don’t. After a successful request, a new TAT is calculated by adding T.

There is a redis module that implements this algorithm available on GitHub: https://github.com/brandur/redis-cell

Answer 3

This is an old question that was already answered, but here's an implementation I did taking some inspiration from here. I'm using ioredis for Node.js

Here is the rolling-window time limiter in all its asynchronous yet race-condition-free (I hope) glory:

var Ioredis = require('ioredis');
var redis = new Ioredis();

// Rolling window rate limiter
//
// key is a unique identifier for the process or function call being limited
// exp is the expiry in milliseconds
// maxnum is the number of function calls allowed before expiry
var redis_limiter_rolling = function(key, maxnum, exp, next) {
  redis.multi([
    ['incr', 'limiter:num:' + key],
    ['time']
  ]).exec(function(err, results) {
    if (err) {
      next(err);
    } else {
      // unique incremented list number for this key
      var listnum = results[0][1];
      // current time
      var tcur = (parseInt(results[1][1][0], 10) * 1000) + Math.floor(parseInt(results[1][1][1], 10) / 1000);
      // absolute time of expiry
      var texpiry = tcur - exp;
      // get number of transacation in the last expiry time
      var listkey = 'limiter:list:' + key;
      redis.multi([
        ['zadd', listkey, tcur.toString(), listnum],
        ['zremrangebyscore', listkey, '-inf', texpiry.toString()],
        ['zcard', listkey]
      ]).exec(function(err, results) {
        if (err) {
          next(err);
        } else {
          // num is the number of calls in the last expiry time window
          var num = parseInt(results[2][1], 10);
          if (num <= maxnum) {
            // does not reach limit
            next(null, false, num, exp);
          } else {
            // limit surpassed
            next(null, true, num, exp);
          }
        }
      });
    }
  });
};

and here is a kind of lockout-style rate limiter:

// Lockout window rate limiter
//
// key is a unique identifier for the process or function call being limited
// exp is the expiry in milliseconds
// maxnum is the number of function calls allowed within expiry time
var util_limiter_lockout = function(key, maxnum, exp, next) {
  // lockout rate limiter
  var idkey = 'limiter:lock:' + key;
  redis.incr(idkey, function(err, result) {
    if (err) {
      next(err);
    } else {
      if (result <= maxnum) {
        // still within number of allowable calls
        // - reset expiry and allow next function call
        redis.expire(idkey, exp, function(err) {
          if (err) {
            next(err);
          } else {
            next(null, false, result);
          }
        });
      } else {
        // too many calls, user must wait for expiry of idkey
        next(null, true, result);
      }
    }
  });
};

Here's a gist of the functions. Let me know if you see any issues.

Answer 4

Note: The following code is a sample implementation in Java.

private final String COUNT = "count";

@Autowired
private StringRedisTemplate stringRedisTemplate;
private HashOperations hashOperations;

@PostConstruct
private void init() {
    hashOperations = stringRedisTemplate.opsForHash();
}

@Override
public boolean isRequestAllowed(String key, long limit, long timeout, TimeUnit timeUnit) {
    Boolean hasKey = stringRedisTemplate.hasKey(key);
    if (hasKey) {
        Long value = hashOperations.increment(key, COUNT, -1l);
        return value > 0;
    } else {
        hashOperations.put(key, COUNT, String.valueOf(limit));
        stringRedisTemplate.expire(key, timeout, timeUnit);
    }
    return true;
}

Answer 5

Here's my leaky bucket implementation of rate limiting, using Redis Lists.

Note: The following code is a sample implementation in php, you can implement it in your own language.

$list = $redis->lRange($key, 0, -1); // get whole list
$noOfRequests = count($list);
if ($noOfRequests > 5) {
    $expired = 0;
    foreach ($list as $timestamp) {
        if ((time() - $timestamp) > 60) { // Time difference more than 1 min == expired
            $expired++;
        }
    }
    if ($expired > 0) {
        $redis->lTrim($key, $expired, -1); // Remove expired requests
        if (($noOfRequests - $expired) > 5) { // If still no of requests greater than 5, means fresh limit exceeded.
            die("Request limit exceeded");
        }
    } else { // No expired == all fresh.
        die("Request limit exceeded");
    }
}
$redis->rPush($key, time()); // Add this request as a genuine one to the list, and proceed.

Answer 6

Your update is a very nice algorithm, although I a made couple of changes:

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()
        RPOP counter

Answer 7

Similar to other Java answer but will less round trip to Redis:

    @Autowired
    private StringRedisTemplate stringRedisTemplate;
    private HashOperations hashOperations;

    @PostConstruct
    private void init() {
        hashOperations = stringRedisTemplate.opsForHash();
    }

    @Override
    public boolean isRequestAllowed(String key, long limit, long timeout, TimeUnit timeUnit) {
        Long value = hashOperations.increment(key, COUNT, 1l);
        if (value == 1) {
            stringRedisTemplate.expire(key, timeout, timeUnit);
        }
        return value > limit;
    }

Answer 8

Here is an alternative approach. If the goal is to limit the number of requests to X requests per Y seconds with the timer starting when the first request is received, then you could create 2 keys for each user that you want to track: one for the time that the first request was received and another for the number of requests made.

key = "123"
key_count = "ct:#{key}"
key_timestamp = "ts:#{key}"

if (not redis[key_timestamp].nil?) && (not redis[key_count].nil?) && (redis[key_count].to_i > 3)
    puts "limit reached"
else
    if redis[key_timestamp].nil?
        redis.multi do
            redis.set(key_count, 1)
            redis.set(key_timestamp, 1)
            redis.expire(key_timestamp,30)
        end
    else
        redis.incr(key_count)
    end
    puts redis[key_count].to_s + " : " + redis[key_timestamp].to_s + " : " + redis.ttl(key_timestamp).to_s
end

Answer 9

This is small enough that you might get away with not hashing it.

local f,k,a,b f=redis.call k=KEYS[1] a=f('incrby',k,ARGV[1]) b=f('pttl',k) if b<0 then f('pexpire',k,ARGV[2]) end return a

The parameters are:

KEYS[1] = key name, could be the action to rate limit for example
ARGV[1] = amount to increment, usually 1, but you could batch up per 10 or 100 millisecond intervals on the client
ARGV[2] = window, in milliseconds, to rate limit in
Returns: The new incremented value, which can then be compared to a value in your code to see if it's over the rate limit.

The ttl will not be set back to the base value with this method, it will continue to slide down until the key expires, at which point it will start over with ARGV[2] ttl on the next call.

Answer 10

Requests in Last interval / Sliding window

interval == Amount of time that number of requests(throughput) accepted
throughput == number of requests per interval
RequestTimeList == Each request time added to this list

// Remove older request entries
while (!RequestTimeList.isEmpty() && (now() - RequestTimeList.get(0)) > interval) {

    RequestTimeList.remove(0)
}

if (RequestTimeList.length < throughput) {

    RequestTimeList.add(now())

} else {

    throw err;
}

Requests in Interval / Fixed window

I have tried with LIST, EXPIRE and PTTL

If tps is 5 per second, then
throughput = 5
rampup = 1000 (1000ms = 1sec)
interval = 200ms

local tpsKey = KEYS[1]
local throughput = tonumber(ARGV[1])
local rampUp = tonumber(ARGV[2])
-- Minimum interval to accept the next request.
local interval = rampUp / throughput
local currentTime = redis.call('PTTL', tpsKey)

--  -2 if the key does not exist, so set an year expiry
if currentTime == -2 then
    currentTime = 31536000000 - interval
    redis.call('SET', tpsKey, 31536000000, "PX", currentTime)
end

local previousTime = redis.call('GET', tpsKey)

if (previousTime - currentTime) >=  interval then
       redis.call('SET', tpsKey, currentTime, "PX", currentTime)
       return true
else
       redis.call('ECHO',"0. ERR - MAX PERMIT REACHED IN THIS INTERVAL")
       return false
end

another way with List

local counter = KEYS[1]
local throughput = tonumber(ARGV[1]) 
local rampUp = tonumber(ARGV[2])
local interval = rampUp / throughput
local times = redis.call('LLEN', counter)

if times == 0 then
    redis.call('LPUSH', counter, rampUp)
    redis.call('PEXPIRE', counter, rampUp)
    return true
elseif times < throughput then
    local lastElemTTL = tonumber(redis.call('LINDEX', counter, 0))
    local currentTTL = redis.call('PTTL', counter)
    if  (lastElemTTL-currentTTL) < interval then
        return false
    else
        redis.call('LPUSH', counter, currentTTL)
        return true
     end
else
    return false
end