Implement a Token Bucket Rate Limiter in Go

Rate limiting is a crucial mechanism for controlling the rate at which a service can be accessed, preventing abuse and ensuring fair usage. The token bucket algorithm is a popular and effective method for implementing rate limiting. This challenge asks you to build a token bucket rate limiter in Go.

Problem Description

Your task is to implement a TokenBucket struct in Go that simulates the token bucket algorithm for rate limiting. The TokenBucket should manage a supply of tokens, allowing operations to proceed only if a token is available.

Key Requirements:

1. Initialization: The TokenBucket must be initialized with a capacity (the maximum number of tokens the bucket can hold) and a rate (the number of tokens refilled per second).
2. Adding Tokens: Tokens should be added to the bucket at a constant rate. If the bucket is full, any additional tokens are discarded.
3. Consuming Tokens: When a request needs to be processed, it attempts to consume one token from the bucket.
   • If a token is available, the request is allowed, and one token is removed from the bucket.
   • If no token is available, the request is denied (or must wait, depending on the implementation strategy, but for this challenge, we'll focus on immediate availability).
4. Concurrency Safety: The TokenBucket must be safe for concurrent access from multiple goroutines.

Expected Behavior:

• A TokenBucket should be able to refill its tokens over time.
• Calls to consume tokens should succeed if tokens are present and fail otherwise.
• The bucket's token count should never exceed its capacity.

Edge Cases:

• Initializing with a capacity or rate of zero or less.
• Repeatedly trying to consume tokens when none are available.
• Simultaneous token consumption and refilling from multiple goroutines.

Examples

Example 1: Basic Consumption and Refill

// Assume a TokenBucket is initialized with capacity = 5, rate = 2 tokens/second.
// Initially, the bucket is full (5 tokens).

// Time 0:
// Consume 1 token: Success. Bucket has 4 tokens.
// Consume 1 token: Success. Bucket has 3 tokens.
// Consume 1 token: Success. Bucket has 2 tokens.

// Time 1 second passes:
// Bucket refills 2 tokens. Bucket has 2 + 2 = 4 tokens.

// Consume 1 token: Success. Bucket has 3 tokens.
// Consume 1 token: Success. Bucket has 2 tokens.
// Consume 1 token: Success. Bucket has 1 token.
// Consume 1 token: Success. Bucket has 0 tokens.

// Consume 1 token: Failure. Bucket has 0 tokens.

// Time 2 seconds passes:
// Bucket refills 2 tokens. Bucket has 0 + 2 = 2 tokens.

Example 2: Capacity Limit

// Assume a TokenBucket is initialized with capacity = 3, rate = 1 token/second.
// Initially, the bucket is full (3 tokens).

// Time 0:
// Consume 1 token: Success. Bucket has 2 tokens.
// Consume 1 token: Success. Bucket has 1 token.

// Time 1 second passes:
// Bucket refills 1 token. Bucket has 1 + 1 = 2 tokens.

// Consume 1 token: Success. Bucket has 1 token.
// Consume 1 token: Success. Bucket has 0 tokens.

// Time 1 second passes:
// Bucket refills 1 token. Bucket has 0 + 1 = 1 token.

// Time 1 second passes:
// Bucket refills 1 token. Bucket has 1 + 1 = 2 tokens.

// Time 1 second passes:
// Bucket refills 1 token. Bucket has 2 + 1 = 3 tokens.

// Time 1 second passes:
// Bucket refills 1 token. Bucket has 3 + 1 = 3 tokens (capacity reached).

// Consume 1 token: Success. Bucket has 2 tokens.

Example 3: Concurrent Access (Conceptual)

// Assume TokenBucket with capacity = 10, rate = 5 tokens/second.
// Multiple goroutines attempt to consume tokens concurrently.

// Goroutine A consumes 1 token.
// Goroutine B consumes 1 token.
// Goroutine C consumes 1 token.

// If tokens are available, these operations should proceed safely,
// decrementing the token count and returning true.
// If at any point the token count drops to 0, subsequent
// consumption attempts will fail until more tokens are refilled.

Constraints

• capacity will be an integer greater than or equal to 1.
• rate will be an integer greater than or equal to 1 (tokens per second).
• The refill mechanism should operate in a background goroutine to avoid blocking consumption calls.
• The solution should handle a high volume of concurrent Consume calls.

Notes

• You will likely need to use Go's sync package (e.g., sync.Mutex or sync.RWMutex) to ensure thread-safety.
• Consider using time.Ticker or time.Timer for managing the token refill rate.
• The Consume method should return a boolean indicating success or failure.
• Think about how to handle the case where the refill rate might cause the bucket to "overshoot" its capacity.
• A common approach is to have a separate goroutine that periodically adds tokens to the bucket based on the rate.
• The Consume method should atomically check and decrement the token count.