Rate Limiting

A simple, memory-efficient algorithm that counts requests within non-overlapping time windows.

• Time is divided into fixed intervals (e.g., a 60-second window starting at every minute).
• A counter is incremented for each request in the current window.
• If the counter exceeds the limit, all further requests in that window are denied. The counter resets at the start of the next window.
• Drawback: Allows double the limit at window boundaries (e.g., 100 requests at the end of one window and 100 at the start of the next).
• Key Use Case: Suitable for simple, high-volume logging or metrics collection where perfect precision is less critical than low overhead.

A highly precise algorithm that maintains a timestamped log of each request.

• When a new request arrives, timestamps older than the current time minus the window (e.g., 60 seconds) are discarded from the log.
• The algorithm counts the remaining timestamps. If the count is below the limit, the new request's timestamp is added and allowed.
• Advantage: Provides smooth, accurate limiting without the boundary spikes of a fixed window.
• Drawback: Can consume significant memory if request volume is very high, as it stores a record for each request in the window.
• Key Use Case: Critical for billing APIs or security-sensitive endpoints where exceeding the limit by even one request is unacceptable.

A memory-efficient hybrid that approximates the sliding window log's precision.

• It tracks request counts for the previous window and the current window, weighted by time.
• The estimated count is calculated as: count_previous * (overlap %) + count_current.
• This avoids storing individual timestamps while providing a much smoother limit than a fixed window.
• Trade-off: It is an approximation but is typically within 1-2% of the true sliding window log count.
• Key Use Case: The preferred choice for most production API gateways and load balancers (like Nginx, Envoy) as it balances precision with minimal resource usage.

A dynamic algorithm that adjusts limits in real-time based on system health and client behavior.

• It monitors backend metrics like latency, error rates, and CPU/memory utilization.
• When signs of stress are detected, the algorithm proactively reduces rate limits for all or specific clients.
• As the system recovers, limits are gradually increased.
• Often incorporates client reputation scoring, imposing stricter limits on aggressive or misbehaving clients.
• Key Use Case: Essential for protecting shared, autoscaling backend services from cascading failure, often used in conjunction with the circuit breaker pattern.

The HTTP 429 Too Many Requests status code is the standard response a server sends to explicitly communicate that a client has been rate limited. This is a client-error response (4xx) that indicates the limit has been exceeded for a given time window. A well-behaved API should include a Retry-After header in the 429 response to inform the client how long to wait before making a new request.

• Semantic Signal: Distinguishes a rate limit error from other client errors (e.g., 400 Bad Request) or server errors (e.g., 503 Service Unavailable).
• Best Practice: Clients should parse this status code and implement exponential backoff based on the Retry-After hint.

The token bucket algorithm is a common, flexible method for implementing rate limiting. The system maintains a conceptual bucket that holds a maximum number of tokens. The bucket refills with new tokens at a steady, predefined rate. Each incoming request consumes one token. If tokens are available, the request proceeds; if the bucket is empty, the request is denied or queued.

• Burst Allowance: A full bucket allows a burst of requests up to the bucket's capacity, smoothing traffic spikes.
• Contrast with Leaky Bucket: The token bucket allows bursts; the leaky bucket enforces a strict, uniform output rate.

Backpressure is a flow control mechanism where a system component that is struggling to keep up with incoming data or requests signals upstream producers to slow down. In the context of APIs and rate limiting, backpressure propagates rate limit signals (like 429 errors) back through a chain of services to the ultimate client. This prevents failures from cascading and buffers from overflowing.

• Systemic Protection: Moves beyond point-in-time rejection to manage load across an entire data pipeline.
• Implementation: Can be explicit (e.g., TCP flow control) or implicit (e.g., a service slowing its consumption from a message queue).

Load shedding is a proactive survival strategy where a system under extreme stress automatically identifies and rejects or drops non-critical requests to preserve resources for critical operations. It is a more aggressive form of protection than standard rate limiting. While rate limiting applies consistent rules, load shedding is triggered by real-time health metrics (e.g., CPU, memory, latency) and often involves priority-based or random drop policies.

• Use Case: During a traffic surge, an e-commerce site might shed product image requests to keep the checkout API available.
• Goal: Prevents cascading failure and total system collapse.

The circuit breaker pattern is a resilience design pattern that prevents an application from repeatedly calling a failing or unresponsive service (including one returning rate limit errors). It operates in three states:

• Closed: Requests flow normally.

• Open: Requests fail immediately without attempting the call, after a failure threshold is met.

• Half-Open: A limited number of test requests are allowed to probe if the service has recovered.

• Synergy with Rate Limiting: A circuit breaker can trip when it detects a high frequency of 429 errors, giving the downstream service time to recover and the client's rate limit quota to reset.