Rare failure mode

[hardbyte]

Looking at the core in fastapi_limiter/depends.py#L35-L42:

        p = redis.pipeline()
        p.incrby(key, 1)
        p.pttl(key)
        num, pexpire = await p.execute()
        if num == 1:
            await redis.pexpire(key, self.milliseconds)
        if num > self.times:
            return await callback(request, pexpire)

In the extremely rare case that the process fails between incrementing the value with p.execute() and setting the ttl with redis.pexpire the key won't actually have a time to live set. The next request will increment the count, but as num will already be greater than 1 the expiry won't get set... so after self.times requests all following requests will count as exceeding the rate limit.

[hardbyte]

A possible solution might be to first check if the key exists, and if it doesn't create it with the count of zero and set the TTL.

[long2ice]

Maybe we should use transaction said in https://aioredis.readthedocs.io/en/v1.3.0/mixins.html#transaction-commands instead of pipeline

[hardbyte]

It looks to me like that would work - assuming aioredis exposes the watch command from https://redis.io/topics/transactions#cas

[hardbyte]

Issue is still present right? Is this being closed as "won't fix"?

[long2ice]

Fixed in f7d5720

[hardbyte]

As far as I can tell that change doesn't address the issue.

It's the second redis call that sets the ttl on the key (iff num is 1). If that second transaction is missed due to computers being computers, the rate limiter is forever going to deny all future requests once the per period limit is reached.

[long2ice]

Could you give a PR and tests?

[hardbyte]

I can think of a few ways to improve the protocol such that the failure mode becomes "in rare circumstances could let one extra request into a period" rather than "in rare circumstances will enter a stater where all future requests are denied".

"Oh, you wanted to increment a counter?! Good luck with that!" -- the distributed systems literature
@lindsey

So the current behavior is this:

Proposal 1 adds an additional redis query of "does the key exist":

if not redis.exists(key):
    redis.psetex(key, period_in_milliseconds, 0)

tr = redis.multi_exec()
tr.incrby(key, 1)
tr.pttl(key)
num, expiry = await tr.execute()

Which gives something like this:

There may be a method without an extra roundtrip to redis, and there could very well still be issues with that proposal. Ideally there would be a published protocol we could use, or we could make a TLA+ model of the protocol.

[hardbyte]

@long2ice do you want to reopen this issue? Hopefully my diagrams help to explain how a service using fastapi-limiter can get into an irrecoverable state.

Do you have any thoughts on my proposed solution?

[long2ice]

Could get exists by num = 1 after run incr?

[hardbyte]

I'm not sure what you mean? In the current protocol or in my proposal?

[Alexander-N]

How about setting the TTL every time in the transaction? That should be safe and doesn't need the extra roundtrip. Maybe I'm missing something but doesn't it make sense to reset the TTL for every request?

Not familiar with aioredis but something like this:

tr = redis.multi_exec()
tr.incrby(key, 1)
tr.pexpire(key, self.milliseconds)
num, _ = await tr.execute()

[hardbyte]

That would prevent the failure condition... but it would stop being a rate limiter :-P

[Alexander-N]

Oh, thats right 😄. What's missing is that one has to use a separate key for each time interval as in https://redis.io/commands/incr/#pattern-rate-limiter-1

[hardbyte]

Nice work @long2ice 1fd34df looks like a solid fix.