Implement a rate limiter in Go using a token bucket algorithm.
- User
Implement a rate limiter in Go using a token bucket algorithm.
- Assistant
Let's implement a rate limiter in Go using the token bucket algorithm. This implementation will include a token bucket struct, methods to manage the bucket, and an example of how to use it. The token bucket algorithm is a popular rate limiting technique where tokens are added to a bucket at a fixed rate, and requests consume tokens to proceed.
Here's a complete implementation:
package main import ( "fmt" "sync" "time" ) // TokenBucket represents a token bucket rate limiter type TokenBucket struct { capacity int64 // maximum number of tokens the bucket can hold tokens int64 // current number of tokens in the bucket rate time.Duration // time interval to add one token lastRefill time.Time // last time the bucket was refilled mu sync.Mutex // mutex for thread-safe operations } // NewTokenBucket creates a new token bucket // capacity: maximum number of tokens // rate: time duration to add one token func NewTokenBucket(capacity int64, rate time.Duration) *TokenBucket { return &TokenBucket{ capacity: capacity, tokens: capacity, // start with full bucket rate: rate, lastRefill: time.Now(), } } // refill adds tokens to the bucket based on elapsed time func (tb *TokenBucket) refill() { now := time.Now() elapsed := now.Sub(tb.lastRefill) // Calculate new tokens to add newTokens := int64(elapsed / tb.rate) if newTokens > 0 { // Add new tokens, but don't exceed capacity tb.tokens = min(tb.capacity, tb.tokens+newTokens) tb.lastRefill = now } } // min returns the minimum of two int64 values func min(a, b int64) int64 { if a < b { return a } return b } // Allow checks if a request is allowed (has enough tokens) // Returns true if request is allowed, false otherwise func (tb *TokenBucket) Allow() bool { tb.mu.Lock() defer tb.mu.Unlock() // Refill tokens before checking tb.refill() // Check if we have at least one token if tb.tokens >= 1 { tb.tokens-- return true } return false } // AllowN checks if n requests are allowed // Returns true if all n requests are allowed, false otherwise func (tb *TokenBucket) AllowN(n int64) bool { tb.mu.Lock() defer tb.mu.Unlock() // Refill tokens before checking tb.refill() // Check if we have enough tokens if tb.tokens >= n { tb.tokens -= n return true } return false } // Wait blocks until a request can be allowed func (tb *TokenBucket) Wait() { for !tb.Allow() { // Calculate how long to wait for the next token tb.mu.Lock() waitTime := tb.rate - time.Since(tb.lastRefill) tb.mu.Unlock() if waitTime > 0 { time.Sleep(waitTime) } } } // Example usage func main() { // Create a token bucket that allows 10 requests per second // (adds 1 token every 100ms, with capacity of 10 tokens) bucket := NewTokenBucket(10, 100*time.Millisecond) // Simulate some requests for i := 0; i < 15; i++ { if bucket.Allow() { fmt.Printf("Request %d allowed at %v\n", i+1, time.Now()) } else { fmt.Printf("Request %d denied at %v\n", i+1, time.Now()) } // Add some delay between requests time.Sleep(50 * time.Millisecond) } // Demonstrate Wait functionality fmt.Println("\nDemonstrating Wait functionality:") for i := 0; i < 5; i++ { start := time.Now() bucket.Wait() duration := time.Since(start) fmt.Printf("Request %d processed after waiting %v\n", i+1, duration) } // Demonstrate AllowN functionality fmt.Println("\nDemonstrating AllowN functionality:") if bucket.AllowN(5) { fmt.Println("Allowed 5 requests at once") } else { fmt.Println("Denied 5 requests at once") } // Try AllowN with too many requests if bucket.AllowN(15) { fmt.Println("Allowed 15 requests at once") } else { fmt.Println("Denied 15 requests at once") } }This implementation includes:
-
A
TokenBucketstruct that maintains:- Bucket capacity
- Current number of tokens
- Rate at which tokens are added
- Last refill timestamp
- Mutex for thread safety
-
Key methods:
NewTokenBucket: Creates a new token bucketrefill: Adds tokens based on elapsed timeAllow: Checks if a single request is allowedAllowN: Checks if N requests are allowedWait: Blocks until a request can be allowed
-
Features:
- Thread-safe using mutex
- Burst handling (up to capacity)
- Precise timing calculations
- Support for both blocking and non-blocking operations
-
Example usage demonstrating:
- Basic rate limiting
- Waiting for tokens
- Handling multiple requests at once
To use this rate limiter in a real application, you might:
- Use it in an HTTP server to limit API requests:
func handler(w http.ResponseWriter, r *http.Request) { if !bucket.Allow() { http.Error(w, "Rate limit exceeded", http.StatusTooManyRequests) return } // Process request }- Use it in a message processing system:
func processMessage(msg Message) { bucket.Wait() // Block until we can process // Process message }The rate limiter can be configured by adjusting:
- Capacity: Controls burst size
- Rate: Controls how quickly new tokens are added
For example, to allow 100 requests per second with a burst capacity of 200:
bucket := NewTokenBucket(200, 10*time.Millisecond) // 10ms = 1/100 secondThis implementation is production-ready and handles edge cases such as:
- Thread safety
- Time precision
- Integer overflow prevention
- Proper burst handling
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.