AI summary by TwinMind
Rate Limiting
Theo - t3․gg
19m 59s
Introduction & Context
- Rate limiting is complex topic with quick solutions but overall challenging
- Community member wrote comprehensive article about visualizing rate limiting algorithms
- Article inspired by Sam's load balancing visualizations, created with OnSClOM for canvas work
Why Rate Limiting Matters
- Spam Prevention: Twitch chat example - single spammer can dominate conversation without rate limiting
- Security: Login forms need protection against brute force password attacks
- API Protection: Prevent single user from monopolizing resources
- Twitch Implementation: Built-in slow mode allows messages every 30 seconds, 5 seconds, etc.
Fixed Window Rate Limiting
- Basic Concept: Set number of requests allowed within predefined time window
- Implementation: Counter increments with requests, resets to zero at window start
- Window Timing: Time window exists independently (via cron job), regardless of request timing
- GitHub Example: 5,000 requests per hour, resets at wall clock hour start
- Major Vulnerability: Allows bursts up to 2x the limit
- Can send 5,000 requests before midnight, 5,000 after midnight
- Enables 10,000 requests in 2-minute window at right timing
24-Hour Window Issues
- Timezone Problems: Window resets at server midnight or UTC, confusing users in different timezones
- User Exploitation: Users can change timezone after hitting limits to gain additional requests
User-Defined Start Windows
- Alternative Approach: Window starts with user's first request instead of fixed intervals
- New Problems: Strategic gaming possible - users can exhaust existing window before starting next
- User Experience: Must show time remaining since no set alignment time
Sliding Window Rate Limiting
- Core Concept: Refills one request at a time instead of bulk refresh
- Visualization: Vertical representation showing request "slots" with expiration timers
- Mechanism: Each request has individual timer; when 5+ requests overlap, blocking occurs
- Benefits: Smooths distribution, well-suited for high load
- Drawbacks: Harder to understand/predict, storing timestamps is resource-intensive
Floating Window Approximation
- Real-World Implementation: Used by Upstash, Cloudflare due to efficiency needs
- Algorithm Steps:
- Count allowed requests in previous fixed window
- Count allowed requests in current fixed window
- Weight previous window requests proportional to overlap with floating window
- Add weighted results
- Advantage: Same benefits as sliding window but far more efficient
- Trade-off: Blocks different requests but maintains same long-term average
Token Bucket Rate Limiting
- Concept: Bucket fills with tokens at constant rate, each request withdraws one token
- Key Properties:
- Bucket capacity = maximum burst requests (not counting mid-burst refills)
- Refill interval = long-term average request interval
- Flexibility: Distinct burst vs average capacities without multiple limiters
Real-World Examples
- Stripe: 500 token limit, refills every 0.01 seconds (100 requests/second sustained, 500 burst)
- OpenAI GPT-3.5 Free: 200 requests/day, new token every 432 seconds (7.5 minutes)
- Twitch Demo: 3 token bucket, 4-second refill (1 message per 4 seconds average)
Advantages & Disadvantages
- Pros: Excellent burst handling, flexible, prevents doubling problem
- Cons: Extremely difficult to explain to users, can't predict exact renewal times
Token Bucket Versatility
- Can mimic other algorithms by adjusting parameters
- Similar to React hooks being built on useReducer
Implementation Considerations
Persistent Storage
- Scaling Requirement: Need external storage for multi-server deployments
- Serverless Necessity: Can't use in-memory variables
- Popular Solution: Redis key-value store with built-in key expiration
- Optimization: Ephemeral in-memory cache for hot limiters
Failure Handling
- Fail Open: Allow all requests if persistent store connection fails
- Rationale: DOSing Redis much better than DOSing actual database
Key Selection Strategy
- Authenticated Users: User ID or API key
- Unauthenticated Users: IP address, device fingerprint, installation ID, or shared limiter
- Separation: Different keys for different rate limit types (login vs API)
Error Communication
- HTTP Status: Use 429 (Too Many Requests)
- Headers: Include X-rate-limit response headers
- Examples: GitHub (fixed window), OpenAI (token-based) provide good header implementations
- Developer Experience: Enable automatic retry logic with proper timing
Algorithm Selection Guide
- Fixed Window: Simple rate limiter or predictable window start times
- Approximated Sliding Window: Traffic smoothing for high request volumes
- Token Bucket: Support traffic bursts while enforcing lower long-term average
Additional Features
- Throttling: Can combine with rate limiting to reduce burst impact
- Playground: Interactive tool available for testing different traffic patterns against algorithms
