Rate Limiting Fundamentals
Rate limiting is a strategy to control the rate at which a user, service, or system can access a resource or perform operations. Before diving into complex implementations, let’s establish a solid understanding of the core concepts and basic approaches.
Core Concepts and Terminology
Rate limiting involves several key concepts:
- Request Rate: The number of requests per unit time (e.g., 100 requests per second)
- Burst: A temporary spike in request rate
- Quota: The maximum number of requests allowed in a given time window
- Throttling: The act of delaying or rejecting requests that exceed defined limits
- Rate Limiter: The component that enforces rate limits
Simple Counter-Based Rate Limiter
Let’s start with a basic implementation—a fixed window counter rate limiter:
package main
import (
"fmt"
"sync"
"time"
)
// FixedWindowLimiter implements a simple fixed window rate limiter
type FixedWindowLimiter struct {
mu sync.Mutex
requestCount int
windowSize time.Duration
limit int
windowStart time.Time
}
// NewFixedWindowLimiter creates a new fixed window rate limiter
func NewFixedWindowLimiter(limit int, windowSize time.Duration) *FixedWindowLimiter {
return &FixedWindowLimiter{
limit: limit,
windowSize: windowSize,
windowStart: time.Now(),
}
}
// Allow checks if a request should be allowed based on the current rate
func (l *FixedWindowLimiter) Allow() bool {
l.mu.Lock()
defer l.mu.Unlock()
now := time.Now()
// If the window has expired, reset the counter
if now.Sub(l.windowStart) >= l.windowSize {
l.requestCount = 0
l.windowStart = now
}
// Check if we've reached the limit
if l.requestCount >= l.limit {
return false
}
// Increment the counter and allow the request
l.requestCount++
return true
}
func main() {
// Create a rate limiter: 5 requests per second
limiter := NewFixedWindowLimiter(5, time.Second)
// Simulate 10 requests in quick succession
for i := 1; i <= 10; i++ {
allowed := limiter.Allow()
fmt.Printf("Request %d: %v\n", i, allowed)
}
// Wait for the window to reset
fmt.Println("Waiting for window reset...")
time.Sleep(time.Second)
// Try again after the window resets
for i := 11; i <= 15; i++ {
allowed := limiter.Allow()
fmt.Printf("Request %d: %v\n", i, allowed)
}
}
This simple implementation demonstrates the basic concept but has significant limitations:
- Edge Effects: All requests in a window are treated equally, regardless of their distribution within the window. This can lead to “bursts” at window boundaries.
- Memory Efficiency: For high-volume services with many clients, maintaining counters for each client can consume significant memory.
- Precision: The fixed window approach lacks granularity and can allow twice the intended rate at window boundaries.