Issue while creating leaky bucket. Exceeded capacity

[sandeepanumula8690]

@mennanov I have been trying to implement ratelimiter using leaky bucket in my project. At the time of creation of bucket I have specified the bucket capacity as 5 and the leak rate as 5 per hour. But it's allowing 7requests within the first minute itself. I have attached the code for reference.

func (r RateLimitsRepo) CreateLeakyBucket(ctx context.Context, identifier string, rate time.Duration, capacity uint32) (limiters.LeakyBucket, error) { // Check if a LeakyBucket instance already exists for the identifier if bucket, found := bucketCache[identifier]; found { return bucket, nil } logger := limiters.NewStdLogger() clock := limiters.NewSystemClock()

// Create a new redsync pool using the Redis client
pool = goredis.NewPool(r.redisClient)

// Create a mutex with a specific name
mutexName := identifier

// Wrap the mutex in a LockRedis struct
lockRedis := limiters.NewLockRedis(pool, mutexName)
bucket := limiters.NewLeakyBucket(
    int64(capacity), // Capacity of the bucket
    rate,            // Leak rate
    lockRedis,       // Distributed lock for synchronization
    limiters.NewLeakyBucketRedis(
        r.redisClient,
        identifier,
        rate,   // TTL for Redis keys
        false), // Set to false to avoid logging missing keys
    clock,
    logger,
)
defer lockRedis.Unlock(ctx)
// Cache the new LeakyBucket instance
bucketCache[identifier] = bucket
return bucket, nil

}

func (h RateLimitHandler) RateLimitCheck(ctx context.Context, rq pb.RateLimitCheckRq) (pb.RateLimitCheckRs, error) { var bucket limiters.LeakyBucket key := rq.GetKey() apiCall := rq.GetApiCall()

identifier := fmt.Sprintf("%s:%s", key, apiCall)

durationRate := time.Hour / 5

bucket, err := h.rateLimitsRepo.CreateLeakyBucket(ctx, identifier, durationRate, 5)
if err != nil {
    return nil, err
}
waitTime, err := bucket.Limit(ctx)
if err == limiters.ErrLimitExhausted {
    return &pb.RateLimitCheckRs{
        Allowed:    false,
        RetryAfter: timestamppb.New(time.Now().Add(waitTime)),
    }, nil
} else if err != nil {
    return nil, err
}
return &pb.RateLimitCheckRs{
    Allowed: true,
}, nil

}

[leeym]

Code to reproduce this issue. To make it extreme, the capacity is zero and the rate is one hour.

diff --git a/leakybucket.go b/leakybucket.go
index 14c45ef..488339b 100644
--- a/leakybucket.go
+++ b/leakybucket.go
@@ -100,6 +100,7 @@ func (t *LeakyBucket) Limit(ctx context.Context) (time.Duration, error) {
    }

    wait := state.Last - now
+   t.logger.Log("wait:", time.Duration(wait))
    if wait/t.rate > t.capacity {
        return time.Duration(wait), ErrLimitExhausted
    }
diff --git a/leakybucket_test.go b/leakybucket_test.go
index 24762d4..b1422d3 100644
--- a/leakybucket_test.go
+++ b/leakybucket_test.go
@@ -2,6 +2,7 @@ package limiters_test

 import (
    "context"
+   "fmt"
    "sync"
    "testing"
    "time"
@@ -81,6 +82,25 @@ func (s *LimitersTestSuite) TestLeakyBucketRealClock() {
    }
 }

+func (s *LimitersTestSuite) TestLeakyBucketIssue70() {
+   capacity := int64(0)
+   rate := time.Hour
+   for name, clock := range map[string]l.Clock{
+       "fakeClock": newFakeClock(),
+       "realClock": l.NewSystemClock(),
+   } {
+       s.Run(name, func() {
+           for _, bucket := range s.leakyBuckets(capacity, rate, clock) {
+               for i := int64(1); true; i++ {
+                   _, err := bucket.Limit(context.TODO())
+                   s.Require().NoError(err, fmt.Sprintf("For a leaky bucket of capacity %d, it accepts request 1..%d and rejects request %d", capacity, i-1, i))
+               }
+               break
+           }
+       })
+   }
+}
+
 func (s *LimitersTestSuite) TestLeakyBucketFakeClock() {
    capacity := int64(10)
    rate := time.Millisecond * 100

And the result

?       github.com/mennanov/limiters/examples/helloworld    [no test files]
=== RUN   TestLimitersTestSuite
2024/07/05 11:07:31 Connected to 127.0.0.1:2181
2024/07/05 11:07:31 authenticated: id=72292542106763301, timeout=4000
2024/07/05 11:07:31 re-submitting `0` credentials after reconnect
=== RUN   TestLimitersTestSuite/TestLeakyBucketIssue70
=== RUN   TestLimitersTestSuite/TestLeakyBucketIssue70/realClock
2024/07/05 11:07:31 wait: 0s
2024/07/05 11:07:31 wait: 59m59.9827s
2024/07/05 11:07:31 wait: 1h59m59.969393s
    leakybucket_test.go:96: 
            Error Trace:    /Users/leeym/git/limiters/leakybucket_test.go:96
                                        /Users/leeym/go/pkg/mod/github.com/stretchr/testify@v1.8.4/suite/suite.go:112
            Error:          Received unexpected error:
                            requests limit exhausted
            Test:           TestLimitersTestSuite/TestLeakyBucketIssue70/realClock
            Messages:       For a leaky bucket of capacity 0, it accepts request 1..2 and rejects request 3
=== RUN   TestLimitersTestSuite/TestLeakyBucketIssue70/fakeClock
2024/07/05 11:07:31 wait: 0s
2024/07/05 11:07:31 wait: 1h0m0s
    leakybucket_test.go:96: 
            Error Trace:    /Users/leeym/git/limiters/leakybucket_test.go:96
                                        /Users/leeym/go/pkg/mod/github.com/stretchr/testify@v1.8.4/suite/suite.go:112
            Error:          Received unexpected error:
                            requests limit exhausted
            Test:           TestLimitersTestSuite/TestLeakyBucketIssue70/fakeClock
            Messages:       For a leaky bucket of capacity 0, it accepts request 1..1 and rejects request 2
--- FAIL: TestLimitersTestSuite (0.09s)
    --- FAIL: TestLimitersTestSuite/TestLeakyBucketIssue70 (0.04s)
        --- FAIL: TestLimitersTestSuite/TestLeakyBucketIssue70/realClock (0.04s)
        --- FAIL: TestLimitersTestSuite/TestLeakyBucketIssue70/fakeClock (0.01s)
FAIL
FAIL    github.com/mennanov/limiters    0.588s
testing: warning: no tests to run
PASS
ok      github.com/mennanov/limiters/examples   (cached) [no tests to run]
FAIL

The first request is allowed as it will go through directly and not staying in the bucket.

• When using a fake clock, it rejects the second request.
• When using a real clock, it allows the second request as it is within one hour from the first one, and rejects the third one.

[mennanov]

Thanks for reporting! I will take a close look within the next 5-7 days. Consider creating a PR if you need it sooner

[mennanov]

@sandeepanumula8690 could you please verify the fix in #v1.7.0 I believe the issue should be resolved now