[bug] GCRA race conditions

[judahrand]

Hi there,

I've been reading through your implementation of GCRA and it occurred to me that there is a large potential for race conditions emerging.

On line 28 on gcra.py you get the value of the key and then proceed to calculate whether or not to rate limit the request. It isn't until line 75 that you update the key. Clearly, the computation in between lines 25 and 75 doesn't take zero time and so there is potential for another RateLimiter to have already updated the key and accepted a new request in the time it took to work out what to do.

Another very good implementation of GCRA is the throttled project in Go (I had started porting it to Python before I found this project!). Their solution is to perform an atomic compare-and-swap operation when they update the key. If the key has already changed then they try again until either they succeed at updating the key, discover they now need to rate limit, or reach a maximum number of retries. They basically just loop over the rate_limit function until their CAS succeeds.

This seems like a good compromise to me as it does need a long 'lock' on any Store but also ensures that up to date information is always used. The only downside is that a compare_and_swap function would need to be added to the BaseStore and all implementations.

This is something I am happy to look at.