Ведро с токенами

Прогресс комнаты 0 / 4

Задание 1Введение

Цель: Реализовать алгоритм token bucket.

Напишите token_bucket(capacity, rate, events). Ведро в начале полное; между событиями пополняется на rate токенов в секунду, но не выше capacity. Каждый запрос (время в секундах, по возрастанию) забирает 1 токен, если он есть. Верните, какие запросы пропущены.

Задание 2Теория и инструменты

Ведро допускает короткие всплески до capacity и среднюю скорость rate запросов в секунду.

Так работают лимиты в Nginx, AWS API Gateway и многих API.

Инструменты

Python 3 или Node.js
Встроенные тесты в редакторе

Больше теории — в разделе «Обучение: Защита (код)».

Задание 3Практика: напишите код

Примеры

Пример 1

token_bucket(2, 1, [0, 0, 0, 1, 1, 5])
→ [true, true, false, true, false, true]

Пример 2

token_bucket(1, 1, [0, 0, 1, 1, 2])
→ [true, false, true, false, true]

Ещё 3 скрытых тестов.

Пошаговый план — открывайте по одному шагу

1
Начните с полного ведра.
2
Перед каждым запросом добавьте (t − last)·rate, но не выше capacity.
3
Пропустите запрос, если есть целый токен.

Подсказки — каждая до решения стоит −50 очков

Войдите, чтобы открыть подсказку 1

Войдите, чтобы открыть подсказку 2

Задание 4Как защититься

Храните состояние ведра в общем хранилище (Redis), если серверов несколько.

Разборы участников

Разборы открываются после того, как вы решите комнату, — чтобы не спойлерить ответ.