Rate Limiting

A Token Bucket algorithm models a bucket with a fixed capacity that refills at a steady rate. Each request consumes a token. This allows for burst handling up to the bucket's capacity while maintaining a long-term average rate.

• Mechanism: A bucket holds N tokens. Tokens are added at a rate of R tokens per second. An incoming request is processed if a token is available; otherwise, it is rate-limited.
• Use Case: Ideal for APIs where short bursts of traffic are acceptable, such as user-initiated actions in a web application.
• Example: A bucket with a capacity of 10 tokens, refilling at 2 tokens/second, can handle 10 immediate requests, then settles to 2 requests/second.

The Leaky Bucket algorithm models a bucket with a finite capacity and a hole at the bottom from which requests leak out at a constant rate. Incoming requests fill the bucket; if it overflows, requests are discarded or queued.

• Mechanism: Requests arrive at a variable rate but are processed at a fixed, constant rate. This smooths out traffic bursts, enforcing a strict output rate.
• Use Case: Suitable for protecting downstream systems that require a steady, predictable workload, like payment processors or database writes.
• Key Difference vs. Token Bucket: The Leaky Bucket enforces a strict output rate; the Token Bucket allows controlled bursts. The Leaky Bucket is often implemented as a FIFO queue.

A Fixed Window Counter algorithm divides time into discrete, non-overlapping windows (e.g., 1-minute intervals). A counter is maintained for each window; it increments with each request and resets at the window's end.

• Mechanism: Simple to implement using a key-value store. For a limit of R requests per minute, the counter for the current minute is checked.
• Limitation: Suffers from boundary issues. A burst of 2R requests can occur at the edge of two windows (e.g., last second of window 1 and first second of window 2), violating the intended rate limit.
• Use Case: Acceptable for less strict limits where double-the-limit bursts are tolerable, or for high-volume, low-precision logging.

The Sliding Window Log algorithm maintains a timestamped log of each request within the current time window. The request count is the number of timestamps within the sliding window.

• Mechanism: For a limit of R requests per minute, the system stores the timestamp of each request. To check a new request, it counts timestamps from now - 1 minute to now.
• Advantage: Provides high precision and avoids the boundary problems of fixed windows. It accurately enforces the limit for any rolling window.
• Drawback: Can consume significant memory as it stores individual timestamps for all requests, which is problematic under high load. Requires efficient pruning of old timestamps.

A Sliding Window Counter is a hybrid algorithm that approximates the sliding window's precision with the fixed window's memory efficiency. It calculates the current rate by weighting the counts of the previous and current fixed windows.

• Mechanism: It tracks counters for fixed windows (e.g., 1-minute chunks). The estimated count for a rolling 1-minute window is: previous_window_count * overlap_percentage + current_window_count.
• Example: For a limit of 100/min, at 1:30 (30 seconds into the current minute), the rate is: (count from 1:00-1:01) * 0.5 + (count from 1:01-1:01:30).
• Use Case: The preferred practical implementation for distributed systems, offering a good balance of fairness, precision, and low memory overhead. Used by systems like Redis.

Adaptive Rate Limiting dynamically adjusts rate limits based on real-time system health, client behavior, or downstream service capacity, moving beyond static thresholds.

• Mechanism: Uses feedback from metrics like server CPU load, latency percentiles, or error rates to tighten or loosen limits.
• Common Patterns:
  • Client Prioritization: Applying stricter limits to abusive clients while allowing higher quotas for trusted partners.
  • Load Shedding: Automatically reducing global limits when backend databases or LLM inference endpoints are under high stress.
  • AI-Driven Throttling: Using reinforcement learning to optimize limits for complex, variable-cost operations like LLM prompts.
• Use Case: Critical for protecting stateful, variable-cost backend services like LLM APIs, where request cost is not uniform.

The Token Bucket Algorithm is the most common rate limiting mechanism. It conceptualizes a bucket that holds a maximum number of tokens, where each token represents permission to make one request. Tokens are refilled at a steady rate (e.g., 100 tokens per minute). When a request arrives, the system checks if a token is available. If so, the request is processed and the token is consumed. If the bucket is empty, the request is denied or queued. This approach allows for burst handling (using saved tokens) while enforcing a long-term average rate.

Rate limiters differ in how they define the time window for counting requests.

• Fixed Window: Counts requests in non-overlapping time blocks (e.g., 0:00-0:01). Simple but allows double the limit at window boundaries (e.g., 100 requests at 0:00:59 and another 100 at 0:01:00).
• Sliding Window: Tracks requests in a rolling time window (e.g., the last 60 seconds). More precise and smooths out boundary spikes. Often implemented with a sliding log (tracking timestamps) or a sliding counter approximation for efficiency. Essential for enforcing strict, consistent limits on costly LLM inference calls.

Rate limiting is applied at different architectural levels for defense-in-depth:

• User/API Key Tier: Limits per end-user or API key to enforce subscription plans (e.g., 1000 requests/day for free tier).
• Application/Service Tier: Global limits per application to control aggregate load from all users.
• Model/Endpoint Tier: Limits specific to a model (e.g., GPT-4) or API endpoint to protect expensive resources. This is often managed by the LLM provider (e.g., OpenAI's RPM/TPM limits).
• IP/Network Tier: A coarse-grained limit based on client IP address to mitigate denial-of-service attacks.

When a limit is exceeded, the server must communicate this clearly. Standard HTTP status code 429 Too Many Requests is used. Response headers inform the client of their status:

• X-RateLimit-Limit: The maximum number of requests allowed in the window.
• X-RateLimit-Remaining: The number of requests left in the current window.
• X-RateLimit-Reset: The time (in seconds or UTC timestamp) when the limit will reset.
• Retry-After: Recommended time for the client to wait before making a new request. Implementing proper headers allows clients to build intelligent exponential backoff logic.

In a microservices or multi-instance deployment, a simple in-memory counter fails. Requests can hit any server, requiring a shared state. Solutions include:

• Centralized Data Store: Using a fast, shared cache like Redis or Memcached to store counters. This introduces network latency and a single point of failure.
• Distributed Consensus: Algorithms that synchronize counts across nodes, complex but more resilient.
• Client-Side Throttling: The client estimates its quota and self-throttles, reducing server load but requiring trust. For LLM APIs, providers typically enforce limits at their load balancer or gateway layer using a centralized store.

Rate limiting is rarely implemented directly in the application logic. It is typically enforced at the API Gateway (e.g., Kong, Apigee, AWS API Gateway) or within a Service Mesh (e.g., Istio, Linkerd). These infrastructure components:

• Provide declarative configuration for limits per route, service, or consumer.
• Handle the distributed counting logic transparently.
• Integrate with authentication systems to identify users.
• Offer real-time dashboards for monitoring limit usage and violations. This separation of concerns allows developers to focus on business logic while SREs manage traffic policies.

The practice of controlling the volume and rate of network traffic sent to a service. While rate limiting is a reactive enforcement of a hard cap, traffic shaping is a proactive, often more granular, policy for managing bandwidth allocation and traffic flow.

• Purpose: To smooth bursts, prioritize certain traffic types (e.g., API calls vs. data syncs), and prevent network congestion.
• Mechanism: Uses techniques like token buckets or leaky buckets to regulate average and peak rates.
• Example: Allowing a client 100 requests per minute (rate limit) but using shaping to ensure those requests are spaced evenly, not in a single burst.

A networking device or software component that distributes incoming client requests across multiple backend servers. Load balancers work in tandem with rate limiting to ensure fair distribution and prevent any single server from being overwhelmed.

• Function: Performs health checks, uses algorithms (round-robin, least connections), and can implement global rate limiting.
• Layer 7 vs. Layer 4: Application-layer (L7) balancers can make routing decisions based on HTTP content, while network-layer (L4) balancers work on IP and port.
• Integration: An API Gateway often incorporates both load balancing and rate limiting functionalities.

A software design pattern that detects failures and prevents an application from repeatedly trying to execute an operation that is likely to fail. It protects a system from cascading failures when a dependent service is unhealthy.

• States: Closed (normal operation), Open (requests fail fast), Half-Open (allows a test request to see if the service has recovered).
• Difference from Rate Limiting: A circuit breaker reacts to failure rates, not request volume. It's a client-side pattern for fault tolerance, whereas rate limiting is typically a server-side pattern for resource protection.

A client-side strategy for handling transient failures by progressively increasing the wait time between retry attempts. It is a critical complement to server-side rate limiting to avoid exacerbating a throttling situation.

• Algorithm: Wait time = base * (2 ^ attempt). For example: 1s, 2s, 4s, 8s...
• Purpose: Reduces load on a struggling server, spreads out retry storms, and increases the chance of successful recovery.
• Best Practice: Always implement jitter (randomized delay) to prevent synchronized retries from many clients.