Skip to content
TheChatArchiveThe Chat Archive
grok-3-preview-02-24· xAIHugging Face LMArena Human Preference 140K

Implement a rate limiter in Go using a token bucket algorithm.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4o-mini-2024-07-18’s answer.
  1. User

    Implement a rate limiter in Go using a token bucket algorithm.

  2. 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:

    1. A TokenBucket struct that maintains:

      • Bucket capacity
      • Current number of tokens
      • Rate at which tokens are added
      • Last refill timestamp
      • Mutex for thread safety
    2. Key methods:

      • NewTokenBucket: Creates a new token bucket
      • refill: Adds tokens based on elapsed time
      • Allow: Checks if a single request is allowed
      • AllowN: Checks if N requests are allowed
      • Wait: Blocks until a request can be allowed
    3. Features:

      • Thread-safe using mutex
      • Burst handling (up to capacity)
      • Precise timing calculations
      • Support for both blocking and non-blocking operations
    4. 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:

    1. 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
    }
    
    1. 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 second
    

    This implementation is production-ready and handles edge cases such as:

    • Thread safety
    • Time precision
    • Integer overflow prevention
    • Proper burst handling

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.