Repository navigation
Misleading reset value #43
Description
Since a new member is added to the sorted set every time the rate limiter is accessed, the sorted set will keep growing even if the limit is reached.
It leads to situation where, clients that are waiting for the limit to be reached before retrying when specified can end up in a loop of requests that will be limited.
Simplified example:
limit = 2
duration = 3
| time | sorted set | result |
|---|---|---|
| t0.0 | [0.0] |
{remaining: 2, reset: 3.0} |
| t0.1 | [0.0, 0.1] |
{remaining: 1, reset: 3.0} |
| t0.2 | [0.0, 0.1, 0.2] |
{remaining: 0, reset: 3.0} |
| t3.0 | [0.1, 0.2, 3.0] |
{remaining: 0, reset: 3.1} |
| t3.1 | [0.2, 3.0, 3.1] |
{remaining: 0, reset: 3.2} |
Shouldn't the rate limiter remove the newly added member if remaining is <= 0?
With my simplified example we would have something like:
| time | sorted set | result |
|---|---|---|
| t0.0 | [0.0] |
{remaining: 2, reset: 3.0} |
| t0.1 | [0.0, 0.1] |
{remaining: 1, reset: 3.0} |
| t0.2 | [0.0, 0.1] |
{remaining: 0, reset: 3.0} |
| t3.0 | [0.1, 3.0] |
{remaining: 1, reset: 3.1} |
| t3.1 | [3.0, 3.1] |
{remaining: 0, reset: 6.0} |
Activity
noamshemesh commentedon Jul 4, 2018
It's a different approach, there are few algorithms, we picked the one with relatively low database footprint, as the "added value" of allowing an unwanted user accessing the API faster usually doesn't worth the cost.
A great blog post about different algorithms: https://blog.figma.com/an-alternative-approach-to-rate-limiting-f8a06cf7c94c
xdmnl commentedon Jul 5, 2018
@noamshemesh I agree with the algorithm used. It is just that the reset time will always be the same for every call that reached the limit, even though, doing the call will save it in the sorted set and will delay the real reset.
#44 is my proposed solution where the reset time is based on the oldest call in the range of the max elements.