Rate Limit Violations | Theory

[pranjal-wego]

Problem Theory

I recently faced an issue related to the specified rate limit getting exceeded on certain occasions. Upon inspection of the code, I found a loophole which could theoretically make the rate limit reach up to twice the specified amount.

In my use case, I was trying to rate limit API calls in my client to a 3rd party API for which there was a rate limit imposed on server side. For the sake of simplicity within the context, let's assume a rate limit of 2 calls per second.
No matter how hard we try, we cannot record the exact time when the API call is made to the server in @ring array. The recorded time is always behind the actual time because time is recorded before forwarding the method call to super. The difference may become substantial because:

1. If i'm trying to rate limit API calls, I might have a method for facilitating the calls. There might be an extra layer of logic between the method call and the API call inside the method which would account for some extra time. Even if I'm not using a wrapper method I might be using a library to make calls, like Typhoeus or Net::HTTP, which would have a similar problem.
2. If I'm using multiple threads to make the API calls, the threads won't be truly parallel in Ruby due to shared GIL. Consequently, there might be a time gap between when the time gets recorded in @ring and when the method gets called (or when the API gets called) due to thread scheduling.

Based on above two reasonings, below is a tailor made example where the specified rate limit can get exceeded.
Rate limit of 2 calls per second.
Time recorded for first & second method call: 0.00 & 0.01 respectively. But the actual API calls happen at 0.98, 0.99.
After 1 second has elapsed, Time recorded for 3rd & 4th method call: 1.00 & 1.01. This time the actual API calls happen at 1.01, 1.02.
This results in 4 API calls happening in a duration of 0.04 seconds as opposed the expected rate limit of 2 calls per second. This could potentially make the API calls reach up to twice the specified amount in the specified duration.

[sbfaulkner]

Your reasoning seems sound - perhaps this library isn't what you need for your use-case.

If you have a suggestion to improve accuracy (and still remain "simple"), PRs will definitely be considered.