← Усі задачіNode.js · Middle

Обмежувач частоти token bucket

Напишіть createTokenBucket({ capacity, refillPerSecond, now }). Відро починає повним (capacity токенів) і поповнюється на refillPerSecond токенів за секунду, але не більше за capacity. Метод take() забирає один токен і повертає true, а якщо цілого токена немає - false (запит відхиляється з 429). tokens() повертає кількість цілих токенів.

Час береться з now() у мілісекундах - так обмежувач можна тестувати без справжнього очікування. Поповнення неперервне: за 250 мс при 2 токенах на секунду набігає половина токена.

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

Ctrl+Enter - запустити тести. Tab - відступ; щоб вийти з редактора клавіатурою, натисніть Esc, а потім Tab. Код зберігається в цьому браузері.

Тести (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);