← Wszystkie zadaniaNode.js · Middle

Ogranicznik szybkości token bucket

Napisz createTokenBucket({ capacity, refillPerSecond, now }). Wiadro zaczyna pełne (capacity tokenów) i uzupełnia się o refillPerSecond tokenów na sekundę, ale nigdy ponad capacity. take() zabiera jeden token i zwraca true, a gdy nie ma całego tokena, zwraca false (żądanie odrzucane z 429). tokens() zwraca liczbę całych tokenów.

Czas pochodzi z now() w milisekundach, więc ogranicznik da się testować bez prawdziwego czekania. Uzupełnianie jest ciągłe: przy 2 tokenach na sekundę 250 ms dodaje pół tokena.

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

Ctrl+Enter uruchamia testy. Tab robi wcięcie; aby wyjść z edytora klawiaturą, naciśnij Esc, a potem Tab. Kod zapisuje się w tej przeglądarce.

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