Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/time/rate: CancelAt returns less than expected tokens #56924

Closed
YoungReese opened this issue Nov 24, 2022 · 3 comments
Closed

x/time/rate: CancelAt returns less than expected tokens #56924

YoungReese opened this issue Nov 24, 2022 · 3 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@YoungReese
Copy link

YoungReese commented Nov 24, 2022

What version of Go are you using (go version)?

$ go version
1.17.6

Does this issue reproduce with the latest release?

yes
https://github.com/golang/time/blob/master/rate/rate.go

What operating system and processor architecture are you using (go env)?

mac os, m1 chip

go env Output
$ go env

What did you do?

Using rate.go to build my token bucket algorithm, when I read the source code, I got one question that puzzled me.

The question is that we call function CancelAt, the variable restoreTokens calculated is not right.

Then, I googled to see if anyone had this problem. As follows:

https://learnku.com/go/t/71323

https://stackoverflow.com/questions/70993567/rate-limiting-cancellation-token-restore

https://lailin.xyz/post/go-training-week6-3-token-bucket-2.html#comments

Now, let us look a piece of code.

func Test_tr(t *testing.T) {
	tr()
}

func tr() {
	t0 := time.Now()
	t1 := time.Now().Add(100 * time.Millisecond) // + 1
	t2 := time.Now().Add(200 * time.Millisecond) // + 2
	t3 := time.Now().Add(300 * time.Millisecond) // + 3

	l := rate.NewLimiter(10, 20)
	l.ReserveN(t0, 15) // bucket left 5 token
	fmt.Printf("%+v\n", l)

	r := l.ReserveN(t1, 10) // bucket left 4 token
	fmt.Printf("%+v\n", l)

	l.ReserveN(t2, 2) // bucket left -5 token
	fmt.Printf("%+v\n", l)

	r.CancelAt(t3) // when we see source code in CancelAt, now logic is: -5 + 1 + (10 - 2) = 4
	// but we expected logic is: -5 + 1 + 10 = 6, this is a right answer
	fmt.Printf("%+v\n", l) // bucket left 4 token
}

What did you expect to see?

we expected logic is: -5 + 1 + 10 = 6, this is a right answer

What did you see instead?

// when we see source code in CancelAt, now logic is: -5 + 1 + (10 - 2) = 4

Why ?

Then I debug the code, I found the is we sub the tokensFromDuration twice.

// the code blow is source code in `rate.go`

func (r *Reservation) CancelAt(now time.Time) {
	if !r.ok {
		return
	}

	r.lim.mu.Lock()
	defer r.lim.mu.Unlock()

	if r.lim.limit == Inf || r.tokens == 0 || r.timeToAct.Before(now) {
		return
	}

	restoreTokens := float64(r.tokens) - r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct)) // look this, we sub tokensFromDuration, but is also should be restore instead of exclude
	if restoreTokens <= 0 {
		return
	}
	now, _, tokens := r.lim.advance(now) // the tokens is `lim.tokens + delta`, we has already sub once when we call `reserveN`
	tokens += restoreTokens
	if burst := float64(r.lim.burst); tokens > burst {
		tokens = burst
	}
	r.lim.last = now
	r.lim.tokens = tokens
	if r.timeToAct == r.lim.lastEvent {
		prevEvent := r.timeToAct.Add(r.limit.durationFromTokens(float64(-r.tokens)))
		if !prevEvent.Before(now) {
			r.lim.lastEvent = prevEvent
		}
	}
}

if we use restoreTokens = float64(r.tokens), then we got right answer.

@YoungReese YoungReese changed the title affected/package: [bug] affected/package: golang.org/x/time has a bug in function CancelAt, rate.go Nov 24, 2022
@YoungReese YoungReese changed the title [bug] affected/package: golang.org/x/time has a bug in function CancelAt, rate.go [bug] affected/package: golang.org/x/time has a bug in function CancelAt, rate.go Nov 24, 2022
@seankhliao seankhliao changed the title [bug] affected/package: golang.org/x/time has a bug in function CancelAt, rate.go x/time/rate: CancelAt returns less than expected tokens Nov 24, 2022
@gopherbot gopherbot added this to the Unreleased milestone Nov 24, 2022
@seankhliao
Copy link
Member

cc @Sajmani

@seankhliao seankhliao added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 24, 2022
@Sajmani
Copy link
Contributor

Sajmani commented Jan 6, 2023

The code in rate.go has a comment explaining the logic:

	// calculate tokens to restore
	// The duration between lim.lastEvent and r.timeToAct tells us how many tokens were reserved
	// after r was obtained. These tokens should not be restored.
	restoreTokens := float64(r.tokens) - r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct))

In your example code, 2 tokens are reserved by the call l.ReserveN(t2, 2).
These are the 2 tokens subtracted by r.CancelAt(t3): -5 + 1 + (10 - 2).
If we changed the code as you suggested, the limited would exceed the target rate by 2 tokens when the t2 reservation is used.

@Sajmani Sajmani closed this as completed Jan 6, 2023
@1996Paul-Wen
Copy link

YoungReese is right, and the logic of restoreTokens := float64(r.tokens) - r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct)) in golang.org/x/time/rate is wrong!

What's more, I would like to recommend a rate limiter that is more concise + more correct and effective than the official go implementation watchdog

watchdog has 2 advantages:


At the usage level, watchdog completely covers the functions of golang.org/x/time/rate and maintains a similar interface, so it does not require too much mental burden to use

For specific introduction and implementation, please refer to https://github.com/1996Paul-Wen/watchdog#readme

@golang golang locked and limited conversation to collaborators Mar 1, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

5 participants