5 Rate limiting algorithm you should?know

In February 2018, GitHub faced one of the largest DDoS attacks, peaking at 1.35 terabits per second. This incident highlighted the crucial role of rate limiting in preventing such traffic surges from crippling systems. In this article , we’ll explore various rate-limiting algorithms that can help safeguard services from excessive traffic.

1. Fixed Window?Counter:

lets say you can send maximum 10 API request per minute in a particular server. so how actually those request will be process by fixed window counter algorithm? basically It divides time into fixed windows and it counts the number of requests in each window. lets try to understand the scenario.

steps:?

1. Set a 1-minute window: Time is split into fixed windows (e.g., 12:00:00–12:00:59, 12:01:00–12:01:59, etc.).
2. Start the counter: Each window starts with a counter that is set to 10.
3. Process requests: As requests come in during the window, the counter decreases by 1 for each request.
4. Reach the limit: When 10 requests are processed, any further requests within that minute are blocked (discarded).
5. Reset: At the start of the next minute (12:01:00), the counter resets to 10, and the process starts over.

• Pros: Simple to implement.
• Cons: Traffic spikes can happen at the boundary (e.g., 10 requests at 12:00:59 and 10 requests at 12:01:00) that means within 2sec server can experience 20 request.

Pseudocode:?

Initialize counter = 10
Start a timer for 1 minute

When request comes in:
  If counter > 0:
    Process the request
    Decrement counter by 1
  Else:
    Reject the request

After 1 minute:
  Reset counter to 10
  Restart the timer        

2. Sliding Window?Log

You can make 10 API requests per minute, but instead of fixed windows, it tracks requests over a rolling time frame.

Steps:

1. Log each request’s timestamp: Every request’s time (e.g., 12:00:10) is saved in a log.
2. Check the log: When a new request comes in, the system checks the log to see how many requests were made in the last 60 seconds.
3. Limit enforcement: If there are fewer than 10 requests in the past 60 seconds, the new request is processed. If there are already 10, the request is rejected.
4. Remove old requests: As time passes, older requests (older than 60 seconds) are removed from the log.

• Pros: More accurate than Fixed Window (no traffic spikes at the boundary).
• Cons: Requires more memory to store all request timestamps.

Pseudocode:

Initialize empty log for storing request timestamps

When request comes in:
  Remove any request from log older than 60 seconds
  If log has less than 10 requests in last 60 seconds:
    Process the request
    Add current timestamp to the log
  Else:
    Reject the request        

3. Sliding Window?Counter

Sliding window counter is almost similar with sliding window log but instead of logging each request, it uses counters. lets explain the same example here also.?

Steps:

1. Track requests per small interval: Divide the minute into smaller intervals (e.g., 6-second intervals).
2. Count requests: Track how many requests were made in each interval.
3. Check the sliding window: When a new request comes in, the system sums up the number of requests in the last 60 seconds by adding the counts from the last 10 intervals.
4. Process or reject: If fewer than 10 requests were made in the last minute, process the request. If 10 or more were made, reject the request.

• Pros: Uses less memory than Sliding Window Log.
• Cons: Slightly less accurate than Sliding Window Log because it averages requests over small intervals.

Pseudocode:

Initialize small intervals (for example, every 6 seconds) with request counters
Total request_count = 0

When request comes in:
  Remove any counts older than 60 seconds
  If request_count < 10:
    Process the request
    Add 1 to the current interval’s counter
    Update total request_count
  Else:
    Reject the request        

4. Token?Bucket

In this algorithm requests consume tokens. If the bucket does not contain any tokens, new requests are denied. You can make 10 API requests per minute, and tokens are used to allow requests. lets see the explaination for this.?

Steps:

1. Set up the bucket: The bucket holds 10 tokens (one token per request).
2. Process requests: Each time a request comes in, a token is taken out of the bucket and the request is processed.
3. Reject when empty: If the bucket runs out of tokens, further requests are rejected.
4. Refill the bucket: Tokens are added back to the bucket at a regular rate (e.g., 1 token every 6 seconds). This ensures requests are evenly spread out over time instead of all at once.

• Pros: Smoothens traffic over time, avoiding spikes.
• Cons: More complex to implement than Fixed Window.

Pseudocode:

Initialize bucket with 10 tokens
Start a refill timer (e.g., 1 token every 6 seconds)

When request comes in:
  If bucket has tokens:
    Process the request
    Remove 1 token from the bucket
  Else:
    Reject the request

At every 6-second interval:
  Add 1 token to the bucket (up to 10 tokens max)        

5. Leaky?Bucket

In this Algorithm Requests are added to a queue (bucket) and processed at a fixed rate to avoid traffic spikes. so in our example we can use 10 API requests per minute, but instead of tokens, requests are queued and processed at a constant rate.

Steps:

1. Queue the requests: All incoming requests are added to a queue.
2. Process at a constant rate: The system processes requests from the queue at a steady rate (e.g., 1 request every 6 seconds).
3. Discard excess requests: If the queue is full or requests come in too fast, some requests are discarded.
4. Smooth request handling: Requests are processed steadily over time, preventing any sudden traffic spikes.

• Pros: Ensures a constant rate of request processing.
• Cons: Can lead to slower response times if requests build up in the queue.

Pseudocode:

Initialize empty queue for requests

When request comes in:
  If queue is not full:
    Add request to queue
  Else:
    Reject the request

At every fixed interval (e.g., 1 request per 6 seconds):
  Process the first request from the queue (if any)        

I’d love to hear your thoughts on this article! If you have any suggestions or notice areas for improvement, feel free to share. Your feedback will help me improve the content for future readers.