← All tasksNode.js · Middle

A token bucket rate limiter

Write createTokenBucket({ capacity, refillPerSecond, now }). The bucket starts full (capacity tokens) and refills by refillPerSecond tokens per second, but never above capacity. take() removes one token and returns true, or returns false when there isn't a whole token (the request is rejected with 429). tokens() returns the number of whole tokens.

Time comes from now() in milliseconds, so the limiter can be tested without real waiting. Refill is continuous: at 2 tokens per second, 250 ms adds half a token.

function createTokenBucket({ capacity, refillPerSecond, now = Date.now }) {
  return {
    take() {
      // ...
      return true;
    },
  };
}

Ctrl+Enter runs the tests. Tab indents; to leave the editor with the keyboard, press Esc and then Tab. Your code is saved in this browser.

Tests (5)

let t = 0;
const bucket = createTokenBucket({ capacity: 3, refillPerSecond: 1, now: () => t });
expect([bucket.take(), bucket.take(), bucket.take(), bucket.take()]).toEqual([true, true, true, false]);

let t = 0;
const bucket = createTokenBucket({ capacity: 2, refillPerSecond: 1, now: () => t });
bucket.take(); bucket.take();
expect(bucket.take()).toBe(false);
t = 1000;
expect(bucket.take()).toBe(true);
expect(bucket.take()).toBe(false);

let t = 0;
const bucket = createTokenBucket({ capacity: 5, refillPerSecond: 2, now: () => t });
for (let i = 0; i < 5; i++) bucket.take();
t = 60_000;
expect(bucket.tokens()).toBe(5);

let t = 0;
const bucket = createTokenBucket({ capacity: 1, refillPerSecond: 2, now: () => t });
bucket.take();
t = 250;
expect(bucket.take()).toBe(false);
t = 500;
expect(bucket.take()).toBe(true);

let t = 0;
const bucket = createTokenBucket({ capacity: 10, refillPerSecond: 1, now: () => t });
expect(bucket.tokens()).toBe(10);
bucket.take(); bucket.take(); bucket.take();
expect(bucket.tokens()).toBe(7);