x/time/rate: unexpected behaviour with 0 limit

[leesio]

Go version

$ go version go version go1.22.1 darwin/arm64

Output of go env in your module/workspace:

GO111MODULE='auto'
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/jameslees/Library/Caches/go-build'
GOENV='/Users/jameslees/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/jameslees/pkg/mod'
GONOPROXY='github.com/monzo'
GONOSUMDB='github.com/monzo'
GOOS='darwin'
GOPATH='/Users/jameslees'
GOPRIVATE='github.com/monzo'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/opt/homebrew/Cellar/go/1.22.1/libexec'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/opt/homebrew/Cellar/go/1.22.1/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.22.1'
GCCGO='gccgo'
AR='ar'
CC='cc'
CXX='c++'
CGO_ENABLED='1'
GOMOD='/Users/jameslees/src/github.com/monzo/wearedev/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/9x/n8nfvk6s4554x9d75k55rl5m0000gn/T/go-build98659086=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

• Created a rate.Limiter with burst: 1 and limit: 0
• Called Allow on the limiter
• Set the limit to a non-zero value using SetLimit
• Called Wait on the limiter

func main() {
	limiter := rate.NewLimiter(0, 1)

	if !limiter.Allow() {
		// Should be true because the burst is 1
		fmt.Printf("Expected first request to be allowed but wasn't")
	}

	// Set a non-zero limit to start refilling the token bucket
	limiter.SetLimit(100)

	err := limiter.Wait(context.Background())
	if err != nil {
		fmt.Printf("Unexpected error waiting: %v\n", err)
	}
}

https://go.dev/play/p/25EIPtjqvDs

What did you see happen?

Wait returns a non-nil error: rate: Wait(n=1) exceeds limiter's burst 0.

This happens because the burst is decremented when reserveN is called on a Limiter with Limit of 0 which seems strange/incorrect to me.

The code appeared here but the conversation doesn't really reflect the code: the comment says:

The opposite in fact needs to happen: lim.tokens must be reduced by the n consumed tokens?

Which makes sense to me, but I'm not sure how we ended up decrementing the burst. To me the solution to the reported problem (limiters not actually being full) would be to set lim.tokens = burst on the constructor. I don't think burst should be changed by anything except SetBurst

What did you expect to see?

I expected Wait to return a nil error after an appropriate delay!

[gabyhelp]

Related Issues and Documentation

• x/time/rate: NewLimiter with burst of 1 and rate of 0 always allows #39984 (closed)
• x/time/rate: Limiter allows more configured with multiple goroutines #65508
• x/time/rate: function Limiter.AllowN generates much more tokens than expected #56263 (closed)
• x/time: "bursts" of the RateLimiter don't work as documented #52618 (closed)
• x/time/rate: When limit higher burst, Allow() will return true higher burst #39970 (closed)
• x/time/rate: token bucket is not initially full #23482
• x/time/rate: Limiter allows more than configured #45245 (closed)
• x/time/rate: Parallel reservations in Limiter.WaitN are served in parallel, violating rate limit #43858 (closed)
• x/time/rate: SetLimit does not update burst #23575 (closed)
• x/time/rate: function Limiter.AllowN does not work as expected #56145 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[ianlancetaylor]

CC @Sajmani

[leesio]

To me the solution to the reported problem (limiters not actually being full) would be to set lim.tokens = burst in the constructor

Having skimmed the code a bit more, I think this would actually make sense. The overflow described in the original issue is specifically guarded against.

If we remove this case entirely, a NewLimiter(0, 1) will never allow (instead of always allowing as before). I think changing the constructor to 👇 should resolve that:

func NewLimiter(r Limit, b int) *Limiter {
	return &Limiter{
		limit:  r,
		burst:  b,
		tokens: float64(b),
	}
}

I can submit a PR with this change

[Sajmani]

@leesio initializing tokens to the burst size makes sense to me based on the "initially full" phrase in the Limiter doc comment:
// It implements a "token bucket" of size b, initially full and refilled
// at rate r tokens per second.

I also agree that burst should only be set in the constructor and SetBurst.

Honestly I've lost any familiarity I've had with this code, so I'd feel better with a second set of eyes to review any changes and help us make sure we're not making a backwards-incompatible behavioral change.

[leesio]

Cool, glad we're on the same page.

There's no particular rush on my side to get this resolved—we've implemented a workaround. Here's my suggested patch. It's very possible I've done something very wrong, it's my first time using the tooling 😅