redis

Redis static window rate limiting


I don't get why we don't just do

MULTI
INCR limit:key1:min12
EXPIRE limit:key1:min12 60 NX
EXEC

In all the examples I see on the internet, people GET first before INCR. What's the risk if we just INCR immediately?


Solution

  • Usually the problem is that you want to stop when you've checked the value and found it to be too high, without touching the value. You might respond "that's fine, I'll just read the incremented value, and if it is too high we reject the request, the extra increment at the server doesn't matter" - but it does matter - it means that a slow trickle of requests can keep the server in an infinite rejection state without ever resetting and getting a new batch of successes - via the EXPIRE slowly extending the life of that ever-increasing value out to forever.

    Note also that this might be more effectively done via a Lua script and EVAL/EVALSHA instead of MULTI/EXEC, which is very hard to do correctly. This is in part because MULTI is really subtle - note that the GET needs to be done inside a WATCH, not a MULTI - you can't see the value from a GET inside a MULTI until the EXEC, making it pointless; for example you can issue a pipeline/batch (zero latency between commands) all of:

    WATCH imit:key1:min12
    GET imit:key1:min12
    MULTI
    INCR limit:key1:min12
    EXPIRE limit:key1:min12 60 NX
    

    (important: the above is left in an incomplete state)

    and then right at the end decide whether to issue EXEC or DISCARD based on the value from the GET, as soon as it comes back. But by using WATCH, there's a non-zero chance of getting a conflict against a different connection, if we assume that this is a system under non-zero load, which now means you need to redo everything from the start (the MULTI block gets thrown away by the server). In a system under serious load/congestion, this could mean that most of your time gets used up redoing-from-start due to competing load - not a good use of your connection time. In reality, you'd need to do something like "try 10 times, then give up and reject", which could incorrectly reject many requests after taking 10x latency. Note: if you don't need the rate limit to be exact (i.e. you're fine having a few extra requests sneak through, as long as it is roughly right), then you could lose the WATCH and just accept that sometimes you might be a little over - often this is a sensible and pragmatic compromise to avoid the whole redo-from-start problem.

    Again: doing this via Lua would be so much easier. It avoids the complex nature of MULTI/EXEC, and because EVAL/EVALSHA run start-to-end without interruption from other connections, there is never a conflict situation, meaning: you never need to redo-from-start - you always run the script exactly once per request.