Search⌘ K
AI Features
Home
Courses
Grokking Modern System Design Interview

Rate Limiter Algorithms

Review five common rate limiting algorithms: token bucket, leaky bucket, fixed window counter, sliding window log, and sliding window counter. For each algorithm, define the key parameters and trade-offs, particularly around burst tolerance and memory usage. Select the appropriate algorithm based on traffic patterns and stability requirements.

We'll cover the following...

“

  • <a href=”#Algorithms-for-rate-limiting" aria-label=“Read more about Algorithms for rate limiting” >Algorithms for rate limiting
    • <a href="#Token-bucket-algorithm" aria-label=“Read more about Token bucket algorithm” >Token bucket algorithm
      • <a href="#Essential-parameters" aria-label=“Read more about Essential parameters” >Essential parameters
      • <a href="#Advantages" aria-label=“Read more about Advantages” >Advantages
      • <a href="#Disadvantages" aria-label=“Read more about Disadvantages” >Disadvantages
    • <a href="#The-leaking-bucket-algorithm" aria-label=“Read more about The leaking bucket algorithm” >The leaking bucket algorithm
      • <a href="#Essential-parameters-1" aria-label=“Read more about Essential parameters” >Essential parameters
      • <a href="#Advantages-1" aria-label=“Read more about Advantages” >Advantages
      • <a href="#Disadvantages-1" aria-label=“Read more about Disadvantages” >Disadvantages
    • <a href="#Fixed-window-counter-algorithm" aria-label=“Read more about Fixed window counter algorithm” >Fixed window counter algorithm
      • <a href="#Essential-parameters-2" aria-label=“Read more about Essential parameters” >Essential parameters
      • <a href="#Advantages-2" aria-label=“Read more about Advantages” >Advantages
      • <a href="#Disadvantages-2" aria-label=“Read more about Disadvantages” >Disadvantages
    • <a href="#Sliding-window-log-algorithm" aria-label=“Read more about Sliding window log algorithm” >Sliding window log algorithm
      • <a href="#Essential-parameters-3" aria-label=“Read more about Essential parameters” >Essential parameters
      • <a href="#Advantages-3" aria-label=“Read more about Advantages” >Advantages
      • <a href="#Disadvantages-3" aria-label=“Read more about Disadvantages” >Disadvantages
    • <a href="#Sliding-window-counter-algorithm" aria-label=“Read more about Sliding window counter algorithm” >Sliding window counter algorithm
      • <a href="#Essential-parameters-4" aria-label=“Read more about Essential parameters” >Essential parameters
      • <a href="#Advantages-4" aria-label=“Read more about Advantages” >Advantages
      • <a href="#Disadvantages-4" aria-label=“Read more about Disadvantages” >Disadvantages
  • <a href="#A-comparison-of-rate-limiting-algorithms" aria-label=“Read more about A comparison of rate-limiting algorithms” >A comparison of rate-limiting algorithms
  • <a href="#Conclusion" aria-label=“Read more about Conclusion” >Conclusion
"

Algorithms for rate limiting

Rate limiters rely on efficient algorithms to control traffic flow. While requirements vary, we will focus on the most popular options:

  • Token bucket

  • Leaking bucket

  • Fixed window counter

  • Sliding window log

  • Sliding window counter

Token bucket algorithm

The Token Bucket algorithm uses a container with a predefined capacity. Tokens are added at a constant rate. When a request arrives, it attempts to consume a token. If the bucket is empty, the request is rejected.

The algorithm operates as follows:

Assume a rate limit of R\text{R} and a total bucket capacity of C\text{C}.

  1. A new token is added to the bucket every 1/R seconds.

  2. If the bucket reaches capacity C\text{C}, incoming tokens are discarded.

  3. Incoming requests consume tokens. If (N)(\text{N}) requests arrive and at least N\text{N} tokens exist, the requests are processed.

  4. If the bucket has fewer tokens than incoming requests, the system processes only the available number and discards the rest.

The following illustration demonstrates the token bucket workflow.

How the token bucket algorithm works
How the token bucket algorithm works

In this example, the bucket capacity is three, and it refills at a rate of three tokens per minute.

Initially, there are three tokens in the bucket. A request arrives within a minute and consumes a token from the bucket
1 / 4
Initially, there are three tokens in the bucket. A request arrives within a minute and consumes a token from the bucket

Essential parameters

Key parameters for the token bucket algorithm include:

  • Bucket capacity (C)(\text{C}): The maximum number of tokens the bucket can hold.

  • Rate limit (R)(\text{R}): The number of requests allowed per unit of time.

  • Refill rate (1R)(\frac{1}{\text{R}}) ...