Add DynamoDB limiter backends

[lamebear]

This adds support to use DynamoDB as a Limiter backend for:

• FixedWindow
• SlidingWindow
• LeakyBucket
• TokenBucket

[lamebear]

@mennanov I could use some help figuring out why the tests are failing in the CI when they pass locally.

[mennanov]

The tests are failing for me even locally:

=== RUN   TestBucketTestSuite/TestTokenBucketRealClock
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 3 and 1 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:5 refillRate:100000000 requestCount:10 requestRate:25000000 missExpected:3 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 3 and 1 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:5 refillRate:100000000 requestCount:10 requestRate:25000000 missExpected:3 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 3 and 1 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:5 refillRate:100000000 requestCount:10 requestRate:25000000 missExpected:3 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:15 requestRate:33000000 missExpected:2 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:15 requestRate:33000000 missExpected:2 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:15 requestRate:33000000 missExpected:2 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:16 requestRate:33000000 missExpected:2 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:16 requestRate:33000000 missExpected:2 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:16 requestRate:33000000 missExpected:2 delta:1}
    tokenbucket_test.go:119: 
            Error Trace:    /Users/renat/projects/limiters/tokenbucket_test.go:119
            Error:          Max difference between 2 and 0 allowed is 1, but difference was 2
            Test:           TestBucketTestSuite/TestTokenBucketRealClock
            Messages:       {capacity:10 refillRate:100000000 requestCount:16 requestRate:33000000 missExpected:2 delta:1}

I'd suggest checking the implementation of TokenBucketDynamoDB

[mennanov]

You may try to run just 1 test case at a time in TestTokenBucketRealClock and see how the state of the token bucket is persisted in DynamoDB: examine the state before the test and after and see if it is correct.

[lamebear]

I was able to replicate the failures on an AMD64 system but not on my Mac M2

[lamebear]

The issue is that requests for the DynamoDB Backend are taking much longer on AMD64. Instead of 33ms between requests the time is ~50ms between requests, allowing the bucket to accrue more tokens than the tests allow.