Deviopath › Node.js

Token Bucket Rate Limiter

Hard · Rate Limiting

Node.js APIs often protect themselves with a token bucket: every client has a bucket of tokens, each request spends tokens, and tokens flow back in at a steady rate. Short bursts are allowed, but the average rate is limited.

Implement TokenBucketLimiter with take(key, now, cost = 1), which returns { allowed, remaining, retryAfterMs }. now is a simulated time in milliseconds (never read the real clock).

- Every key has its own bucket. A bucket is created full (capacity tokens) on the first request for that key, with last = now.

- To avoid floating-point drift, store tokens as integer thousandths of a token. On every request, refill first: add (now - last) * refillPerSecond thousandths (capped at capacity * 1000) and set last = now. If now is earlier than last (the clock went backwards), add nothing and keep last.

- If cost > capacity, the request can never succeed: deny it with retryAfterMs: -1.

- Otherwise, if the bucket holds at least cost tokens, subtract them and allow the request with retryAfterMs: 0.

- Otherwise deny it without spending anything. retryAfterMs is Math.ceil(missingThousandths / refillPerSecond) (every millisecond refills refillPerSecond thousandths), or -1 when refillPerSecond is 0.

- remaining is the number of whole tokens left after the request: Math.floor(thousandths / 1000).

The driver runLimiter(config, requests) is already written. Each request is { key, now, cost? } and the driver returns the result of every take call.

Next: Signed Cookies with HMAC