Rate Limiting

The Token Bucket is a classic, flexible algorithm for controlling average request rates while allowing for bursts. A virtual bucket holds tokens, which are added at a steady refill rate. Each request consumes a token; requests are processed if tokens are available, or queued/dropped if the bucket is empty.

• Key Parameters: Bucket capacity (burst size) and token refill rate per second.
• Use Case: Ideal for APIs where occasional bursts of traffic are acceptable, such as user-initiated actions in a web application.
• Example: A bucket with a capacity of 10 tokens and a refill rate of 2 tokens/second allows a burst of 10 immediate requests, then sustains 2 requests per second.

The Leaky Bucket algorithm enforces a strict, smooth output rate, regardless of input burstiness. Incoming requests are placed in a queue (the bucket), which leaks (processes) them at a constant rate. If the queue is full, new requests are dropped.

• Key Parameters: Queue (bucket) size and constant leak (processing) rate.
• Use Case: Essential for smoothing traffic to a downstream service with fixed capacity, like a payment processor or database, to prevent overload.
• Contrast with Token Bucket: The Leaky Bucket shapes traffic to a constant rate; the Token Bucket permits controlled bursts.

The Fixed Window Counter is a simple algorithm that tracks requests in discrete, non-overlapping time intervals (e.g., per minute). A counter for the current window is incremented with each request and reset at the window's end. Requests are rejected if the counter exceeds a limit.

• Key Parameters: Request limit per window and window duration (e.g., 1000 requests/minute).
• Drawback: Allows double the limit at window boundaries. A surge of requests at the end of one window and the start of the next can overwhelm the system.
• Use Case: Suitable for simple, non-critical limits where absolute precision is less important, like limiting login attempts.

The Sliding Window Log algorithm provides precise rate limiting by storing a timestamp for each request. To check a new request, it counts timestamps within the preceding time window. This eliminates the boundary spike problem of fixed windows.

• Key Parameters: Request limit and the sliding window duration.
• Advantage: Highly accurate, ensuring the limit is never exceeded for any rolling window.
• Drawback: Can consume significant memory, as it may store a timestamp for every request within the window period. It is computationally more expensive than counter-based methods.

The Sliding Window Counter is a hybrid algorithm that approximates the sliding window's accuracy with the fixed window's efficiency. It calculates a weighted count based on the current and previous fixed windows.

• Mechanism: Estimated Count = Count in Previous Window * Overlap + Count in Current Window. This estimates how many requests fell in the rolling window.
• Advantage: More memory-efficient than the Sliding Window Log and more accurate than the Fixed Window Counter.
• Use Case: A practical default choice for production APIs requiring good accuracy without storing per-request data, balancing performance and precision.

Adaptive Rate Limiting dynamically adjusts rate limits based on real-time system health metrics rather than using static thresholds. Limits may tighten under high load or loosen during periods of low utilization.

• Key Metrics: Uses signals like server CPU load, memory usage, database connection pools, and backend service latency.
• Algorithms: Often implements a control loop, such as a PID controller, to adjust the limit.
• Use Case: Critical for protecting shared, auto-scaling infrastructure where resource availability fluctuates. It maximizes throughput during normal operation while aggressively protecting stability during stress.
• Related Pattern: This is a form of applying backpressure from the server to the clients.

Rate limiting enforces usage quotas and prevents a single tenant or process from monopolizing shared resources like databases, message queues, or third-party APIs with metered pricing. This is critical in multi-tenant SaaS platforms and for controlling internal service-to-service communication.

• Example: A billing service might limit calls to a payment processor's API to stay within a contracted transaction-per-second limit and avoid overage fees.
• Related Concept: Backpressure is a complementary flow-control mechanism for systems overwhelmed by data, while rate limiting proactively restricts the initiation of work.

In systems serving multiple users or agents, rate limiting ensures equitable access and prevents noisy neighbor problems. It guarantees a baseline Quality of Service (QoS) for all clients by preventing any single entity from degrading performance for others.

• Fleet Orchestration Context: In a heterogeneous fleet, a priority-based routing system might use differential rate limits. High-priority agents (e.g., those carrying critical inventory) could have higher request rates to the central orchestration middleware than low-priority agents, ensuring mission-critical tasks are not starved of planning cycles.

Rate limiting is used to smooth traffic spikes and create predictable load patterns, making systems easier to scale and monitor. This is a proactive stability measure, preventing cascading failures that might otherwise trigger circuit breakers.

• Example: A real-time replanning engine for a robot fleet might accept plan update requests at a maximum of 100/sec. If a warehouse section fails, causing 500 agents to simultaneously request new paths, the limiter queues or rejects excess requests, allowing the engine to work through the backlog sustainably rather than crashing.
• Synergy: Used alongside exponential backoff in client retry policies to prevent retry storms.

When integrating with external APIs (e.g., cloud services, maps, weather data), rate limiting must be implemented client-side to adhere strictly to the provider's published rate limits, quota limits, and throttling policies. Violating these limits results in HTTP 429 (Too Many Requests) errors and blocked access.

• Implementation Pattern: Client libraries often include built-in rate limiters with queuing or call scheduling to transparently manage compliance.
• Related Concept: A retry policy for these calls must respect the retry-after headers often provided with 429 responses.

During load testing or chaos engineering experiments, rate limiters act as a safety valve to prevent test traffic from overwhelming production or staging environments. They allow engineers to understand system behavior under load up to a defined threshold without causing an outage.

• Connection to SLOs: Testing up to the rate limit helps validate that the system can meet its Service Level Objectives (SLOs) under expected peak load.
• Observability: Rate limiters provide crucial telemetry (e.g., count of throttled requests) that feeds into fleet health monitoring and error budget calculations.

A retry algorithm where the waiting time between consecutive retry attempts increases exponentially. It is a critical companion to rate limiting for client-side error handling. When a request fails (often due to a rate limit or service error), the client waits for a short interval before retrying. If it fails again, the wait time doubles (e.g., 1s, 2s, 4s, 8s). This decorrelates client retry storms and prevents a thundering herd problem, giving the server time to recover from overload or process its request queue.

A resilience pattern that isolates elements of an application into pools, so a failure in one pool does not drain resources and cause a cascading failure. In the context of rate limiting and traffic management:

• Resource Isolation: Critical user-facing APIs can be placed in a separate 'pool' with dedicated connection/thread limits.
• Failure Containment: A surge of traffic (or a denial-of-service attack) on one endpoint consumes only the resources of its bulkhead, leaving other system functions unaffected. This pattern enforces internal rate limits on subsystems.

A flow control mechanism where a system that is overwhelmed signals upstream components to slow down or stop sending data. While rate limiting is often imposed proactively by a server, backpressure is a reactive signal from a congested component.

• Mechanisms: Can be implemented via TCP window sizing, explicit status codes (HTTP 429, 503), or message queue acknowledgments.
• Prevents Resource Exhaustion: Stops memory and thread pool exhaustion by aligning the data production rate with the processing rate, forming a dynamic, system-wide complement to static rate limits.

A persistent queue used to store messages or tasks that cannot be processed successfully after multiple retries. It relates to rate limiting in failure scenarios:

• Handling Rate-Limited Requests: If a service call fails repeatedly due to upstream rate limits (and retries with backoff also fail), the task can be moved to a DLQ.
• Analysis and Manual Intervention: The DLQ allows operators to inspect failed messages (e.g., malformed payloads, destination errors) without blocking the main processing queue, enabling post-mortem analysis of why rate limits were persistently hit.

A dedicated API endpoint (e.g., /health or /ready) that exposes the operational status of a service. It is a foundational tool for systems interacting with rate-limited or fragile dependencies.

• Liveness Probes: Indicate if the service process is running.
• Readiness Probes: Indicate if the service is ready to accept traffic (e.g., databases connected, below rate-limit thresholds).
• Load Balancer Integration: Unhealthy instances failing health checks can be taken out of rotation, preventing traffic from being sent to a rate-limited or failing node and allowing it to recover.