Как реализовать rate limiter через token bucket?

Middle+
535 просмотров
AFK Offer AI

Token bucket — алгоритм, где есть ведро с токенами. Токены добавляются с фиксированной скоростью (например, 10/сек). Каждый запрос забирает один токен. Если токенов нет — запрос отклоняется. Ведро имеет максимальную ёмкость (burst), что позволяет кратковременные всплески. В Go это golang.org/x/time/rate: NewLimiter(rate.Limit(10), 20) — 10 токенов/сек, burst 20. Allow() проверяет мгновенно, Wait(ctx) блокирует до появления токена, Reserve() резервирует и говорит, сколько ждать. Элегантный алгоритм, который одновременно контролирует среднюю скорость и допускает burst.

Следующий вопрос

Что такое space complexity?