golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
124.14k stars 17.69k forks source link

x/time/rate: wrong number of tokens restored in Reservation.CancelAt #69419

Open footgod368 opened 2 months ago

footgod368 commented 2 months ago

Go version

go version go1.23.0 darwin/arm64

Output of go env in your module/workspace:

GO111MODULE='on'
GOARCH='arm64'
GOBIN='/Users/bytedance/go_repos/bin'
GOCACHE='/Users/bytedance/Library/Caches/go-build'
GOENV='/Users/bytedance/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/bytedance/go_repos/pkg/mod'
GONOPROXY='*.byted.org,*.everphoto.cn,git.smartisan.com'
GONOSUMDB='*.byted.org,*.everphoto.cn,git.smartisan.com'
GOOS='darwin'
GOPATH='/Users/bytedance/go_repos'
GOPRIVATE='*.byted.org,*.everphoto.cn,git.smartisan.com'
GOPROXY='https://goproxy.cn,direct'
GOROOT='/opt/homebrew/opt/go/libexec'
GOSUMDB='sum.golang.google.cn'
GOTMPDIR=''
GOTOOLCHAIN='local'
GOTOOLDIR='/opt/homebrew/opt/go/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.23.0'
GODEBUG=''
GOTELEMETRY='local'
GOTELEMETRYDIR='/Users/bytedance/Library/Application Support/go/telemetry'
GCCGO='gccgo'
GOARM64='v8.0'
AR='ar'
CC='cc'
CXX='c++'
CGO_ENABLED='1'
GOMOD='/Users/bytedance/Test/go_demo/time/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/k9/cdmv9r354_l13tvkrgn09f2m0000gn/T/go-build1012911903=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

I suspect the following line contains wrong 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))

I think there's no need to subtract tokens reserved after r was obtained, because these tokens are already subtracted at the time their reservation were made in reserveN.

This stackoverflow post resonates with my idea.

To verify this, I write a test case performing the following scenario:

Say we have an initially full limiter with tokens=burst=10 being refilled at rate=1.

At time=1s, we have only one task worth 1 token to act, and 8 tokens remaining. There's 1 token missing compared to burst=10.

My test code are attached here:

func printLim(lim *rate.Limiter, originTime time.Time) {
    fmt.Printf("tokens: %+v\n", lim.TokensAt(originTime))
}

func TestReserve() {
    lim := rate.NewLimiter(1, 10)
    originTime := time.Now()
    printLim(lim, originTime)
    r0 := lim.ReserveN(originTime, 10)
    printLim(lim, originTime)
    _ = lim.ReserveN(originTime, 1)
    printLim(lim, originTime)
    r0.CancelAt(originTime)
    printLim(lim, originTime)
}

What did you see happen?

The test result is:

tokens: 10
tokens: 0
tokens: -1
tokens: 8

What did you expect to see?

tokens: 10
tokens: 0
tokens: -1
tokens: 9

There should be 9 tokens remaining at the last line.

(Edited the test code to focus on tokens.)

gabyhelp commented 2 months ago

Related Issues and Documentation

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

timothy-king commented 2 months ago

CC @Sajmani, @tklauser as previous contributors.