Leaky Bucket

The leaky bucket algorithm is a traffic-shaping mechanism used to control the flow of requests. It's a simple, yet effective, way to smooth out bursts of traffic and enforce a constant output rate.

The analogy is a bucket with a hole in the bottom that leaks water at a steady rate.

• Incoming data is like water being poured into the bucket. It can arrive in sudden, unpredictable bursts.
• The bucket itself represents a buffer or queue with a fixed capacity. It can hold a certain amount of data that's waiting to be processed.
• The hole at the bottom represents the system's processing rate. Data "leaks" out of the bucket at a constant, predefined rate, regardless of how quickly it's coming in.
• If the incoming data rate is higher than the leak rate and the bucket fills up, any excess data is discarded (or "spills over"). This prevents the system from being overwhelmed by a sudden surge of traffic and ensures a predictable, steady output flow.

Example implementation

Pseudo-code

define BUCKET_CAPACITY
define LEAK_RATE // e.g., requests per second
define last_leak_time // timestamp of the last time the bucket leaked

function initialize_bucket(capacity, rate)
    BUCKET_CAPACITY <- capacity
    LEAK_RATE <- rate
    current_level <- 0
    last_leak_time <- current_timestamp()
end function

function handle_request(request)
    // 1. Calculate how much has leaked out since the last check
    current_time <- current_timestamp()
    time_elapsed <- current_time - last_leak_time
    leaked_amount <- time_elapsed * LEAK_RATE

    // 2. Update the bucket level
    current_level <- max(0, current_level - leaked_amount)
    last_leak_time <- current_time

    // 3. Add the new request to the bucket
    current_level <- current_level + 1

    // 4. Check for overflow
    if current_level <= BUCKET_CAPACITY then
        // The request is accepted
        process(request)
    else
        // The bucket is full, drop the request
        current_level <- current_level - 1 // Undo the add
        drop_request(request)
    end if
end function

Simulation