Algorithm: Understanding Rate Limiting and Common Algorithms

Rate limiting is a technique used in software systems to control how many requests a client can make within a given period of time. It is commonly used in APIs, web services, authentication systems, and distributed applications to prevent abuse, ensure fairness, and protect system resources.

Whenever you see an error message like “Too many requests, try again later,” that is rate limiting in action.

Rate limiters are used in many real-world systems. Public APIs use them to enforce usage plans and prevent misuse. Login systems use them to protect against brute-force attacks. Cloud platforms use them to maintain system stability. Even internal microservices use rate limiting to prevent cascading failures.

There are multiple algorithms used to implement rate limiting. Each one has trade-offs in terms of accuracy, memory usage, and complexity.

Some of the most common algorithms include:

• Fixed Window
• Sliding Window Log
• Sliding Window Counter
• Token Bucket
• Leaky Bucket

Fixed Window

Definition: Fixed Window divides time into fixed intervals, such as one minute or five seconds. A counter tracks how many requests occur during each window.

Parameters: Window size (for example, 60 seconds) Maximum allowed requests per window

Calculation: When a request arrives, the system checks whether the current time is still within the same window. If yes, it increments the counter. If the counter exceeds the limit, the request is rejected. When the window expires, the counter resets to zero.

Use Case: Fixed Window is simple and easy to implement. It is suitable for basic rate limiting where strict accuracy is not critical. However, it can allow sudden bursts at window boundaries.

import time

class Fixed_window:
    def __init__(self, window_size, max_requests):
        self.window_size = window_size
        self.max_requests = max_requests
        self.requests = 0
        self.window_start = time.monotonic()

    def allow_request(self):
        current_time = time.monotonic()
        elapsed_time = current_time - self.window_start

        # If still in same window
        if elapsed_time < self.window_size:
            if self.requests < self.max_requests:
                self.requests += 1
                return True
            else:
                return False
        else:
            # Reset window
            self.requests = 1   # count current request
            self.window_start = current_time
            return True

Sliding Window Log

Definition: Sliding Window Log keeps a record of timestamps for each request within the current time window.

Parameters: Window size Maximum allowed requests A log structure (usually a queue) to store timestamps

Calculation: When a new request arrives, the system removes timestamps older than the window size. It then checks the number of remaining timestamps. If the count is below the limit, the request is allowed and its timestamp is added. Otherwise, it is rejected.

Use Case: Sliding Window Log provides accurate rate limiting because it always considers the exact last time interval. However, it consumes more memory since every request timestamp must be stored.

import time
from collections import deque

class SlidingWindowLog:
    def __init__(self, window_size, max_requests):
        self.window_size = window_size
        self.max_requests = max_requests
        self.log = deque()

    def allow_request(self):
        current_time = time.monotonic()

        # Remove expired timestamps
        while self.log and current_time - self.log[0] >= self.window_size:
            self.log.popleft()

        if len(self.log) < self.max_requests:
            self.log.append(current_time)
            return True
        return False

Sliding Window Counter

Definition: Sliding Window Counter improves memory efficiency by approximating the sliding window using two counters instead of storing all timestamps.

Parameters: Window size Maximum allowed requests Previous window count Current window count

Calculation: The system tracks request counts for the current time window and the previous one. When a request arrives, it calculates a weighted value based on how much of the previous window overlaps with the current time. The effective request count is the current window count plus a weighted portion of the previous window count. If this value exceeds the limit, the request is rejected.

Use Case: Sliding Window Counter provides a good balance between accuracy and memory efficiency. It is commonly used in high-traffic systems where storing every timestamp is too expensive.

import time
class SlidingWindowCounter:
    def __init__(self, max_requests, window_size):
        self.max_requests = max_requests
        self.window_size = window_size
        self.window_start = time.monotonic()
        self.prev_count = 0
        self.curr_count = 0

    def allow_request(self):
        current_time = time.monotonic()
        elapsed = current_time - self.window_start

        # If window has passed, shift windows
        if elapsed >= self.window_size:
            # Move current to previous
            self.prev_count = self.curr_count
            self.curr_count = 0

            # Advance window start
            self.window_start += self.window_size
            elapsed = current_time - self.window_start

        # Calculate weight of previous window
        weight = elapsed / self.window_size

        # Compute approximate total requests
        effective_requests = (
            self.curr_count +
            self.prev_count * (1 - weight)
        )

        if effective_requests < self.max_requests:
            self.curr_count += 1
            return True
        else:
            return False

Token Bucket

Definition Token Bucket controls request rate by using tokens that are added to a bucket at a fixed rate. Each request consumes one token.

Parameters Bucket capacity Token refill rate

Calculation: Tokens are added to the bucket continuously at a fixed rate until it reaches capacity. When a request arrives, it checks whether at least one token is available. If yes, one token is removed and the request is allowed. If no tokens are available, the request is rejected.

Use Case: Token Bucket allows short bursts of traffic while enforcing a long-term average rate. It is widely used in networking systems, APIs, and cloud services because it provides flexibility and good performance.

import time
class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last_refill_time = time.time()

    def allow_request(self):
        current_time = time.time()
        elapsed_time = current_time - self.last_refill_time

        # Add new tokens based on elapsed time
        self.tokens += elapsed_time * self.rate

        # Ensure bucket does not exceed capacity
        self.tokens = min(self.capacity, self.tokens)

        # Update last refill time
        self.last_refill_time = current_time

        # Check if request can be allowed
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        else:
            return False

Leaky Bucket

Definition: Leaky Bucket models traffic as water flowing into a bucket that leaks at a constant rate.

Parameters: Bucket capacity Leak rate

Calculation: Incoming requests are added to a queue. The bucket leaks or processes requests at a fixed rate over time. If the bucket is full when a new request arrives, the request is rejected.

Use Case: Leaky Bucket ensures a steady and smooth output rate. It is useful when a system needs consistent processing speed, such as network traffic shaping or smoothing bursts before passing requests to downstream services.

import time
class LeakyBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.queue_size = 0
        self.last_update = time.monotonic()

    def allow_request(self, data_size=1):
        current_time = time.monotonic()
        elapsed_time = current_time - self.last_update
        self.last_update = current_time

        # Leak from bucket
        leaked = elapsed_time * self.rate
        self.queue_size -= leaked

        # Prevent negative queue
        self.queue_size = max(0, self.queue_size)

        # Check if new request fits
        if self.queue_size + data_size > self.capacity:
            return False

        # Add request
        self.queue_size += data_size
        return True

Beyond these five common algorithms, there are several other advanced or specialized approaches worth exploring:

Generic Cell Rate Algorithm (GCRA), which is mathematically related to token bucket and used in telecom and high-performance API gateways.

Distributed Token Bucket implementations that use shared storage like Redis to coordinate rate limits across multiple servers.

Concurrency-based rate limiting, which limits the number of simultaneous in-flight requests rather than requests per time window.

Cost-based rate limiting, where different requests consume different amounts of quota based on their complexity.

Probabilistic approaches such as Count-Min Sketch for large-scale systems where memory efficiency is critical.

Conclusion

Rate limiting is a core concept in backend engineering and distributed systems. It protects services from overload, ensures fair usage, and improves overall reliability. Different algorithms offer different trade-offs between simplicity, accuracy, memory usage, and burst handling.

Understanding these algorithms and when to use each one is an important step toward building scalable and resilient systems.