Implement a Token Bucket Rate Limiter in Go

Rate limiting is a crucial technique for controlling the rate at which a service can be accessed, preventing abuse, ensuring fair usage, and maintaining stability. This challenge asks you to implement a common rate limiting algorithm, the token bucket, in Go.

Problem Description

Your task is to create a TokenBucket struct in Go that manages a rate-limited resource. The TokenBucket should allow a certain number of requests to pass through at a specified rate.

Here are the key requirements:

• Token Bucket Algorithm: Implement the token bucket algorithm. This algorithm works by having a bucket that holds a certain capacity of "tokens". Tokens are added to the bucket at a fixed rate. When a request arrives, it tries to consume a token. If a token is available, the request is allowed. If no token is available, the request is rejected or queued (for this challenge, rejection is sufficient).
• Capacity: The bucket should have a defined maximum capacity. This is the maximum number of tokens it can hold at any given time.
• Refill Rate: Tokens should be added to the bucket at a constant rate per second.
• Allow() method: The TokenBucket should have an Allow() method that returns true if a request is permitted and false otherwise.
• Concurrency Safety: The TokenBucket must be safe for concurrent use by multiple goroutines.

Expected Behavior:

When Allow() is called:

1. If there are tokens available in the bucket, consume one token and return true.
2. If there are no tokens available, return false.
3. Tokens are replenished over time at the specified refill rate, up to the maximum capacity.

Edge Cases to Consider:

• Initial state: The bucket starts empty or full (you can decide the initial state, but it should be clearly defined).
• Rapid bursts: Handling scenarios where many requests arrive in a short period.
• Long idle periods: Ensuring tokens refill correctly after a period of inactivity.

Examples

Example 1:

Capacity: 5 tokens
Refill Rate: 2 tokens/second

Time 0: Bucket = 0 tokens
Call Allow() -> false (Bucket = 0)
Call Allow() -> false (Bucket = 0)
... (wait a bit)
Time 1 second: Bucket refills 2 tokens. Bucket = 2 tokens.
Call Allow() -> true (Bucket = 1)
Call Allow() -> true (Bucket = 0)
Call Allow() -> false (Bucket = 0)
Time 2 seconds: Bucket refills another 2 tokens. Bucket = 2 tokens.
Call Allow() -> true (Bucket = 1)
Call Allow() -> true (Bucket = 0)
Call Allow() -> false (Bucket = 0)
Time 2.5 seconds: Bucket refills 1 more token (0.5s * 2 tokens/s). Bucket = 1 token.
Call Allow() -> true (Bucket = 0)

Explanation: Initially, the bucket is empty. Tokens are refilled at 2 per second. Requests are allowed only when tokens are present. The bucket never exceeds its capacity.

Example 2:

Capacity: 10 tokens
Refill Rate: 5 tokens/second

Imagine a scenario where we call Allow() 100 times rapidly at time 0.
Bucket state after 100 rapid calls at time 0:
Since the bucket starts empty (or with fewer than 100 tokens), the first 10 calls might succeed if the bucket is initially full or has tokens. Subsequent calls will fail immediately until tokens refill.
Let's assume the bucket starts empty.
Call Allow() 10 times in quick succession: all return false.
Wait 2 seconds.
Bucket refills: 2 seconds * 5 tokens/second = 10 tokens. Bucket = 10 tokens.
Call Allow() 10 times in quick succession: all return true. Bucket becomes 0 tokens.
Call Allow() again: returns false.

Explanation: This highlights how the capacity limits the burstiness, and the refill rate determines how quickly the bucket can recover from a high demand.

Example 3: Concurrent Access

Capacity: 3 tokens
Refill Rate: 1 token/second

Multiple goroutines concurrently call Allow().

Goroutine A calls Allow()
Goroutine B calls Allow()
Goroutine C calls Allow()
Goroutine D calls Allow()

At time 0, let's say bucket has 3 tokens.
Allow() by A, B, C succeed. Bucket = 0 tokens.
Allow() by D fails.
Wait 1 second. Bucket refills 1 token. Bucket = 1 token.
Allow() by D succeeds. Bucket = 0 tokens.

Explanation: This demonstrates that even with concurrent requests, the token bucket logic correctly enforces the rate limit, and concurrency safety ensures correct state management.

Constraints

• Capacity: 1 <= capacity <= 1000
• Refill Rate: 1 <= refill_rate <= 100 (tokens per second)
• The Allow() method should ideally respond within milliseconds to typical load.
• Your TokenBucket implementation should be a single Go struct.

Notes

• You will need to manage time and token counts within your TokenBucket struct.
• Consider using Go's concurrency primitives like sync.Mutex to ensure thread safety.
• The time package in Go will be essential for handling the refill rate.
• Think about how you will track the last refill time and the current number of tokens.
• You do not need to implement a web server or handle network requests. The challenge is focused purely on the TokenBucket logic.