Skip to content
Search

Rate limiting

lastmod 2024-05-20created 2024-05-203 edits

In computer networks, rate limiting is used to control the rate of requests sent or received by a network interface controller. It can be used to prevent DoS attacks and limit web scraping.

Why is rate limiting needed?

  • In a Twitch chat with many participants, if there is a single spammer and no rate limit, the spammer can dominate the conversation.
  • Rate limiting gives each user a fair chance to participate.
  • A rate limiter controls a service's traffic by blocking requests that exceed a set limit within a given period. This is useful beyond controlling spam in chat
  • For example, rate limiting on a login form can suppress brute-force attacks while still allowing a small number of wrong guesses
  • API endpoints are also often rate limited so that a single user cannot monopolize resources
    • If users may call an expensive API endpoint only 100 times per minute, a counter tracks 100 hits per minute and blocks subsequent requests
    • This is the Fixed Window Limiter, one of the simplest rate limiting algorithms
    • A common way to control service traffic

Leaky Bucket

Requests are put one by one into a FIFO bucket (queue), and requests are limited once it is full

Fixed windows algorithm

  • The number of requests is limited within a fixed time window
  • The request counter is reset to 0 at the start of each time window
  • Pros
    • Easy to implement and understand
    • Predictable for users
  • Cons
    • If requests start near the end of a time window, a burst of up to twice the limit may be allowed
  • Real-world example: the GitHub API uses a fixed window rate limiter allowing 5,000 requests per hour
  • Instead of setting window start times at fixed intervals, each time window can be created at the moment of the user's first request within that window
  • With this approach, it is especially important to tell users how much time remains until the next window

Sliding windows algorithm

  • Instead of refreshing all capacity at once, a sliding window refills capacity one request at a time
  • Pros
    • Smooths the distribution of request traffic
    • Well suited to high load
  • Cons
    • Less predictable for users than fixed windows
    • Storing a timestamp for each request is resource-intensive
  • Since sliding windows are most useful in high-traffic scenarios, the fact that the basic algorithm is resource-intensive is counterproductive
  • Therefore, most real-world sliding window rate limiters use an approximation
  • The approximation counts the requests allowed in the previous fixed window and in the current fixed window, and weights the previous window's allowed requests in proportion to its overlap with a floating window ending at the current time
  • This approximation limits requests at almost the same rate but is far more efficient
  • Real-world example: Cloudflare's configurable rate limiter uses an approximate sliding window

Token buckets algorithm

  • Instead of a window duration, imagine a bucket that is filled with "tokens" at a constant rate
  • Each request withdraws one token from this bucket, and if the bucket is empty, the next request is blocked
  • The bucket's capacity represents the maximum number of requests a burst can support
  • The refill interval represents the long-term average allowed interval between requests
  • One of the main advantages of this algorithm is that it can have separate burst and average capacities without multiple rate limiters
  • Pros
    • Allows bursts of high traffic while enforcing a long-term average request rate
    • More flexible for users, allowing traffic spikes within an acceptable range
  • Cons
    • Harder than fixed windows to communicate limits and refill times to users
  • Real-world examples
    • Stripe uses a token bucket with a per-user limit of 500 and a refill interval of 0.01 seconds, allowing a sustained 100 requests per second but bursts of up to 500 requests
    • OpenAI's GPT-3.5 free tier uses a token bucket with a limit of 200 and a refill interval of 86400 seconds/200, limiting it to 200 requests per day

Considerations when applying rate limits

  • You need to create persistent storage for the rate limiter
  • If the server's connection to persistent storage fails, it should allow all requests rather than block them
  • Optionally, burst traffic can be throttled
  • Choose an appropriate key (user ID, API key, etc.)
  • Show useful rate limit errors (wait time until the next request, 429 HTTP status code, x-ratelimit-* response headers, etc.)

See also

Favorite site

author Zer0 sitemap