Token bucket rate limiter

Token bucket rate limiter

Problem

Implement a token-bucket rate limiter. Each key gets a bucket that holds up to capacity tokens. Tokens refill at a constant refillRate per refillMs milliseconds. On each call, if a token is available it is consumed and the request is allowed; otherwise it is rejected. This allows controlled bursts up to the bucket capacity.

Input

• key: string — The identifier for the client or resource being rate-limited.
• capacity: number — Maximum number of tokens the bucket can hold. Defaults to 10.
• refillRate: number — Number of tokens added per refill interval. Defaults to 1.
• refillMs: number — Refill interval in milliseconds. Defaults to 1000 (1 second).

Output

• boolean — true if a token was available and consumed (request allowed); false if the bucket was empty (request rejected).

Examples

Example 1:

// capacity=5, refillRate=1, refillMs=1000 allow('alice', 5, 1, 1000); // true — tokens: 4 allow('alice', 5, 1, 1000); // true — tokens: 3 allow('alice', 5, 1, 1000); // true — tokens: 2 allow('alice', 5, 1, 1000); // true — tokens: 1 allow('alice', 5, 1, 1000); // true — tokens: 0 allow('alice', 5, 1, 1000); // false — bucket empty

Output: false

The bucket starts full at capacity 5. After 5 rapid calls the bucket is empty; additional calls are rejected until tokens refill.

Example 2:

// Different keys get independent buckets 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 has an independent bucket. Filling one does not affect others.

Constraints

• Refill is computed lazily on each access, not by a background timer.
• Tokens are capped at the bucket capacity and never exceed it.
• Elapsed time since the last refill determines how many tokens to add.
• The remainder of elapsed time is preserved for partial-refill accuracy.

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, refillRate = 1, refillMs = 1000): boolean {
    // Refill the bucket from elapsed time at refillRate per refillMs,
    // cap at capacity, then allow one request when tokens remain.
  }