mennanov / limiters Goto Github PK

README.md states that:

Fixed window counter
Simple and resources efficient algorithm that does not need a lock.

But the implementation uses a lock link

I'm confused.

After the fix from #22 I found a bug:
With a small amount of Takes from the bucket, where Backend is a Redis with raceCheck=true then sometimes the expected version is higher than the actual one.

To replicate the issue I created a simple test:

func (s *LimitersTestSuite) TestTokenBucketRealClockRaceCheckRedisProblem() {
	ttl := time.Second
	limit := int64(2)
	refillEvery := time.Duration(int64(ttl) / limit)
	locker := l.NewLockNoop()
	backend := l.NewTokenBucketRedis(s.redisClient, uuid.New().String(), ttl, true)

	clk := l.NewSystemClock()
	ctx := context.Background()

	bucket := l.NewTokenBucket(
		limit,
		refillEvery,
		locker,
		backend,
		clk,
		nil,
	)

	for i := 0; i < 4; i++ {
		wait, err := bucket.Limit(ctx)
		if err != nil {
			assert.ErrorIs(s.T(), err, l.ErrLimitExhausted)
		}
		if wait.Seconds() > 0 {
			clk.Sleep(time.Second) // after a second all keys expired and the initial state was returned, but lastVersion is not cleared
		}
	}
}

checkResponseFromRedis returns error:

got [1 1 OK OK] from redis, expected [3 1 OK OK]

Hello. Is there any particular reason why locker's Lock is context aware but Unlock is not?

I am implementing redis locker which needs to be context aware during Lock and Unlock.

Given the following:

1. TokenBucket created with refill rate of 100ms
2. Request 1 occurs at t = 0ms
3. Request 2 occurs at t = 90ms
4. Request 3 occurs at t = 140ms
5. Request 4 occurs at t = 210ms

The TokenBucket limiter should have added 2 tokens to the bucket, but only one token is added.

Relevent Code

now := t.clock.Now().UnixNano()
// Refill the bucket.
tokensToAdd := (now - state.Last) / int64(t.refillRate)
if tokensToAdd > 0 {
	state.Last = now
	if tokensToAdd+state.Available <= t.capacity {
		state.Available += tokensToAdd
	} else {
		state.Available = t.capacity
	}
}

The way this currently works is:

1. state.Last is set to 0ms on the first request, consuming a token.
2. state.Last is left at 0ms for request 2, consuming a token.
3. state.Last is set to 140ms for request 3, adding and consuming a token.
4. since the time between request 3 and 4 is < 100 ms, no token is added to the bucket

A simple fix would be to modify the logic to truncate state.Last to t.refillRate:

now := t.clock.Now().UnixNano()
// Refill the bucket.
tokensToAdd := (now - state.Last) / int64(t.refillRate)
modTime := (now - state.Last) % int64(t.refillRate)
if tokensToAdd > 0 {
	if tokensToAdd+state.Available < t.capacity {
		state.Available += tokensToAdd
		state.Last = now - modTime
	} else {
		state.Available = t.capacity
		state.Last = now
	}
}

With that change, a token is correctly added to the bucket for request 3:

1. state.Last is set to 0ms on Request 1
2. state.Last is left at 0ms on Request 2
3. state.Last is set to 100ms on Request 3, adding a token to the bucket: 140ms - (140ms % 100ms) = 100ms
4. state.Last is set to 200ms on Request 4, adding a token to the bucket: 210ms - (210ms % 100ms) = 200ms

Alternatively, the Available member of the TokenBucketState struct can be changed from an int64 to a float64 to account for partial tokens, but that would be a more involved change.

Set 60s/10 requests, but if there are many concurrent requests at the same time, all requests will pass, so limiting the rate will become meaningless

Hello,

It does not appear that this package allows for the reset of a limit, is that correct? I have come across a use case where rate limits need to be reset. A user forgets their password, gets rate limited logging into their account. They successfully reset their password, the previous limit should be cleared so they are allowed to attempt to login again.

Would you consider a PR for this feature?

I advise to use multi module to solve this issue

Hi,
Could you please explain what should be ideal value of epsilon in slidingWindow.
Here is my current configuration

slidingLimiter := registry.GetOrCreate(ip, func() interface{} {
		return limiters.NewSlidingWindow(100, window, limiters.NewSlidingWindowRedis(redisClient, ip), clock, 60)
	}, 0*time.Second, clock.Now())

	t, err := slidingLimiter.(*limiters.SlidingWindow).Limit(req.Context())
	fmt.Println("timeDuration: ", t)
	if err == limiters.ErrLimitExhausted {
		wrt.WriteHeader(http.StatusTooManyRequests)
		return
	} else if err != nil {
		// The limiter failed. This error should be logged and examined.
		wrt.WriteHeader(http.StatusInternalServerError)
		return
	}

	serveWebSocket(wrt, req)

When i run a load test,
Sometimes i get this panic

And other times, server breaks, but gives no error, only go routine ids

Please help

This is a corner case for the issue addressed here: #29.
This occurs when the version fetched by State() is deleted before SetState() is executed. That will cause an error: got [1 1 OK OK] from redis, expected [<version_before_remove>+1 1 OK OK] raised by checkResponseFromRedis.

Potential solution is to always expect version to be in initial state: #42