← Alle AufgabenNode.js · Middle

Ein Rate Limiter mit Token Bucket

Schreib createTokenBucket({ capacity, refillPerSecond, now }). Der Eimer startet voll (capacity Tokens) und füllt sich um refillPerSecond Tokens pro Sekunde, aber nie über capacity. take() entnimmt ein Token und liefert true oder liefert false, wenn kein ganzes Token da ist (die Anfrage wird mit 429 abgelehnt). tokens() liefert die Zahl ganzer Tokens.

Die Zeit kommt von now() in Millisekunden, der Limiter lässt sich also ohne echtes Warten testen. Das Auffüllen ist kontinuierlich: bei 2 Tokens pro Sekunde bringen 250 ms ein halbes Token.

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

Strg+Enter führt die Tests aus. Tab rückt ein; um den Editor per Tastatur zu verlassen, drücke Esc und dann Tab. Der Code wird in diesem Browser gespeichert.

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);