State representation for the Token Bucket rate limiting algorithm.

The token bucket algorithm maintains a bucket that holds tokens up to a maximum capacity. Each incoming request consumes one or more tokens from the bucket. Tokens are replenished at a fixed rate. If insufficient tokens are available, the request is either delayed or rejected.

Token Bucket Properties

• Bursty Traffic: Allows bursts of traffic up to the bucket capacity
• Rate Control: Long-term average rate is controlled by token replenishment rate
• Memory Efficient: Only requires tracking token count and last update time

Use Cases

• API rate limiting with burst allowance
• Network traffic shaping
• Resource allocation with temporary overages

Example

-- Initial state with 50 tokens, last updated at Unix timestamp 1640995200
let initialState = TokenBucketState 
      { tokens = 50
      , lastUpdate = 1640995200 
      }

-- After consuming 10 tokens
let afterConsumption = initialState { tokens = 40 }

State representation for the Leaky Bucket rate limiting algorithm.

The leaky bucket algorithm models a bucket with a hole in the bottom that drains at a constant rate. Incoming requests add water to the bucket, and if the bucket overflows, requests are rejected. This provides smooth rate limiting without bursts.

Leaky Bucket Properties

• Smooth Rate: Enforces a consistent output rate regardless of input bursts
• No Bursts: Unlike token bucket, doesn't allow temporary rate exceedance
• Queue Modeling: Can model request queuing with bucket level representing queue depth

Use Cases

• Smooth traffic shaping for network connections
• Audio/video streaming rate control
• Database connection throttling
• Prevention of thundering herd problems

Mathematical Model

The bucket level changes according to:

newLevel = max(0, oldLevel + requestSize - drainRate * timeDelta)

Where:

• requestSize is the size of the incoming request
• drainRate is the constant drain rate (requests per second)
• timeDelta is the elapsed time since last update

Example

-- Initial state: half-full bucket at timestamp 1640995200.5
let initialState = LeakyBucketState 
      { level = 0.5
      , lastTime = 1640995200.5 
      }

-- After 1 second with drain rate 0.1/sec and no new requests
let afterDrain = initialState 
      { level = 0.4  -- 0.5 - 0.1*1.0
      , lastTime = 1640995201.5 
      }