Leaky Bucket Algorithm

The algorithm's core characteristic is its constant, predetermined output rate. Requests leave the bucket (are processed) at a steady, leak-like drip, regardless of how irregularly they arrive. This smooths traffic bursts into a predictable stream, protecting downstream services from being overwhelmed by sudden influxes. For example, an API gateway might be configured to leak requests to a payment service at exactly 100 requests per second, ensuring the service's capacity is never exceeded.

Incoming requests that cannot be processed immediately are held in a First-In, First-Out (FIFO) queue (the bucket). This queue has a finite capacity. The algorithm's behavior when this queue is full defines its two main variants:

• Non-Conformant Packets Discarded: In traffic policing implementations, excess packets are simply dropped.
• Requests Queued or Rejected: In API rate-limiting, new requests may be queued (if space allows) or immediately rejected with a 429 Too Many Requests status code.

This defines the algorithm's primary operational mode:

• Traffic Policing: Excess traffic that exceeds the bucket's capacity is discarded. This is a strict enforcement mechanism used to protect a system from overload, common in network routers.
• Traffic Shaping: Excess traffic is buffered in the queue and released later at the constant leak rate. This delays requests rather than denying them, creating a smoother output but introducing variable latency. Shaping is often used where data integrity is paramount, and delays are acceptable.

A key mathematical property is that the maximum delay for a queued request is predictable. If the bucket has a capacity C (in requests) and a leak rate R (requests/second), the worst-case delay for a request arriving when the queue is full is C / R seconds. This predictability is valuable for Service Level Objective (SLO) calculations and system design, unlike algorithms with randomized delays like jitter-added backoff.

It is essential to distinguish the Leaky Bucket from the Token Bucket algorithm, another common rate limiter.

• Leaky Bucket: Has a fixed output rate. It smooths bursts. A burst of incoming requests fills the queue but does not increase the output speed.
• Token Bucket: Has a fixed maximum burst capacity. It allows bursts. A bucket full of tokens can be spent quickly, allowing a short period of high-speed output up to the burst limit, before settling to the average refill rate.

Widely implemented in API management layers (e.g., Kong, NGINX, Envoy) to enforce rate limits per client, API key, or IP address. When configured, it:

1. Tracks an incoming request queue per limiting key.
2. Processes (leaks) requests from each queue at the defined rate.
3. Enforces the policy (queue or reject) when capacity is exceeded. This protects backend services from being overwhelmed by a single aggressive consumer, ensuring fair usage and system stability, which is a core concern for Reliability Engineers.

A complementary rate-limiting algorithm where incoming requests consume tokens from a bucket that refills at a steady rate. Unlike the strict, queue-based pacing of a leaky bucket, it allows for burst traffic up to the bucket's capacity while enforcing a long-term average rate. This makes it suitable for APIs where occasional bursts are acceptable, such as user-initiated actions.

• Key Difference: Token bucket permits bursts; leaky bucket enforces a smooth, constant output.
• Use Case: Often used for network traffic shaping and APIs where clients can save up capacity.

The overarching control mechanism for restricting the number of requests a client or service can make within a time window. The Leaky Bucket is one specific implementation strategy for rate limiting. The goal is to ensure fair usage, protect backend resources from overload, and maintain system availability.

• Enforcement Points: Can be applied at the API gateway, application layer, or infrastructure level.
• Common Response: Requests exceeding the limit typically receive an HTTP 429 Too Many Requests status code.

A flow control mechanism where a system component that is struggling to keep up (e.g., a downstream service or a full queue) signals upstream producers to slow down or stop sending data. While the leaky bucket controls the output rate, backpressure is a reactive signal that controls the input rate to prevent resource exhaustion and cascading failures.

• Reactive vs. Proactive: Backpressure reacts to congestion; leaky bucket proactively shapes traffic.
• Implementation: Can be explicit (e.g., TCP flow control) or implicit (e.g., dropping requests).

A resilience design pattern that prevents an application from repeatedly calling a failing service. After a threshold of failures is reached, the circuit "opens" and fails fast for a period, allowing the failing system time to recover. It works in tandem with rate limiters like leaky bucket: the rate limiter controls flow volume, while the circuit breaker halts flow entirely during downstream outages.

• Three States: Closed (normal operation), Open (failing fast), Half-Open (testing recovery).
• Prevents Retry Storms: Stops clients from hammering an already-unhealthy service.

The proactive strategy of dropping or rejecting low-priority requests when a system is under extreme load. This is a more aggressive cousin of rate limiting. While a leaky bucket queues or drops excess requests based on a fixed rate, load shedding makes dynamic decisions based on overall system health (e.g., CPU, memory) to preserve resources for critical operations.

• Goal: Prevent total system collapse by sacrificing non-essential functionality.
• Triage Logic: Requires classifying requests by priority (e.g., user login vs. background analytics).

The process of deliberately slowing down the processing of requests or data, often used interchangeably with rate limiting. However, throttling can imply a more dynamic, adaptive control that responds to current system conditions, whereas the classic leaky bucket operates at a pre-configured, constant rate. It's a key technique for implementing graceful degradation.

• Dynamic Adjustment: May reduce throughput from 1000 to 100 requests/sec based on database load.
• User Experience: Can manifest as slower response times rather than outright denial of service.