Leaky bucket rate limiter

Leaky bucket rate limiter

Problem

Implement a leaky-bucket rate limiter. Each key has a bucket that "leaks" water at a constant rate. An incoming request adds one unit of water; if the bucket is already full the request is rejected. This smooths a bursty input stream into a constant outflow rate.

Input

• key: string — The identifier for the client or resource being rate-limited.
• capacity: number — Maximum water level (bucket size). Defaults to 10.
• leakRate: number — Number of units leaked per leak interval. Defaults to 1.
• leakMs: number — Leak interval in milliseconds. Defaults to 1000 (1 second).

Output

• boolean — true if the bucket was not full and the request dripped in (allowed); false if the bucket was full (rejected).

Examples

Example 1:

// capacity=5, leakRate=1, leakMs=1000 allow('alice', 5, 1, 1000); // true — water level 1 allow('alice', 5, 1, 1000); // true — water level 2 allow('alice', 5, 1, 1000); // true — water level 3 allow('alice', 5, 1, 1000); // true — water level 4 allow('alice', 5, 1, 1000); // true — water level 5 allow('alice', 5, 1, 1000); // false — bucket full (level=5)

Output: false

Rapid requests fill the bucket. After 5 allowed requests the bucket is full; subsequent requests are rejected until water leaks out.

Example 2:

// Different keys are independent for (let i = 0; i < 5; i++) allow('a', 5, 1, 1000); allow('b', 5, 1, 1000); // true — b has its own bucket

Output: true

Each key maintains its own bucket. Filling one does not affect others.

Constraints

• Leakage is computed lazily on each access, not by a background timer.
• Water level never goes below 0.
• Elapsed time since the last leak determines how much water drained.
• Rejected requests do NOT add water to the bucket.

Complexity

• Time: O(1) per call
• Space: O(K) where K is the number of distinct active keys

Starter

export function allow(key: string, capacity = 10, leakRate = 1, leakMs = 1000): boolean {
    // Drain water at leakRate per leakMs from elapsed time, then allow
    // the request only when the bucket is not yet full.
  }