Rate Limiter using java and redis without locking

Question

I was trying to understanding how rate-limiter works.

Problem Statement is: ten requests per second per IP address

Soln: i Can see in blogs is:

public void makeApiCall(String ip){
    Long currentTime=Timestamp timestamp = System.currentTimeMillis();

    String key=ip+":"+currentTime;

    Integer count=redisClient.get(key);

    if(count!=null && count > 10){
         throw LimitExceededException();
    }
    else{
         redisClient.incr(key,1);
         callApi();
    }
}

As of now I am ignoring to removed old keys. I am unable to understand how this soln is going to work? As per me above code will end up making more than 10 api call in multi-threaded environment with in a second. It can only be solved by Syncronizing the redisClient.get(key) to callApi() code.

I have taking this code from

https://redis.io/commands/incr.

Can anyone help me in understanding(by modifying the above code) what is the correct way to use redis in these scenario?

Suppose in current second 9 requests have been served.now concurrently 5 new requests come,all these new threads call redisClient.get(key) before any of these 5 threads execute "else" block.So for each thread count will be 9 and else block will be executed and incr will be called 5 times more and for each thread api will be called.

Answer 1

As is, the code is indeed vulnerable to race conditions (and memory bloat as you've left out expiration). There are basically two ways to resolve this: a MULTI/EXEC transaction with a WATCH, or EVALing a Lua script.

Assuming that you're using Jedis as your Java client, something like the following should do the trick with transactions:

public void makeApiCall(String ip){
    Long currentTime=Timestamp timestamp = System.currentTimeMillis();

    String key=ip+":"+currentTime;

    redisClient.watch(key);
    Integer count=redisClient.get(key);

    if(count!=null && count > 10){
         throw LimitExceededException();
    }
    else{
         Transaction t = redisClient.multi();
         t.incr(key,1);
         List<Object> resp = t.exec();
         if(resp != null){
             callApi();
         }
    }
}

Lua is another matter, but basically assuming you provide the following script the entire key name (ip + ts), it pretty much will do the same thing as long as your code follows up with callApi on getting an OK:

local count = redis.call('GET', KEYS[1])
if count and tonumber(count) > 10 then
    return redis.error('count exceeded')
else
    redis.call('INCR', KEYS[1])
    redis.call('EXPIRE', KEYS[1], 10)
    return 'OK'
end

Note that with Lua you don't need to watch for changes, as the entire script is atomic.

Lastly, it seems that the counter pattern you've referred to in the documentation was missing the WATCH thing - I've submitted a PR to rectify that (https://github.com/antirez/redis-doc/pull/888).