juju / ratelimit

Efficient token-bucket-based rate limiter package.
Other
2.79k stars 312 forks source link

If not enough tokens are available, no tokens should be removed from the bucket. #37

Closed jongrun closed 2 years ago

jongrun commented 2 years ago
func (tb *Bucket) take(now time.Time, count int64, maxWait time.Duration) (time.Duration, bool) {
    ...
    avail := tb.availableTokens - count
    if avail >= 0 {
        tb.availableTokens = avail
        return 0, true
    }
    ...
    tb.availableTokens = avail
    return waitTime, true
}

If not enough tokens are available, no tokens should be removed from the bucket. (see https://en.wikipedia.org/wiki/Token_bucket#Algorithm) Otherwise, the availableTokens would be less than zero and would never be enough if many threads are trying to take token from the bucket circularly.

rogpeppe commented 2 years ago

That function returns the number of taken tokens and the amount of time the caller must wait until they're available. If you don't sleep for that length of time, you're not following the contract. The reason its designed that way is so you can wait for other things to happen at the same time (for example by using that duration in a call to timer.Reset)

This is working as designed and as intended. Unless you can show an example of it not working correctly, this issue should be closed.

jongrun commented 2 years ago

Yes, it is. The reason I created this issue is that I used the method Take in a wrong way:

for wait := bucket.Take(1); wait != 0; wait = bucket.Take(1) {
    time.Sleep(wait)
}

When multiple go routines call in this way, they may be blocked forever. The correct call way should be:

bucket.Wait(1)

The Wait method takes required tokens from the bucket and waits until they are available. After the call, the required tokens have been taken, so no more calls should be tried again. Thank you for your reply. I will close this issue.