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:
    1. Count allowed requests in previous fixed window
    2. Count allowed requests in current fixed window
    3. Weight previous window requests proportional to overlap with floating window
    4. 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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome