Реализуйте rate limiter по алгоритму token bucket, который ограничивает
среднюю частоту разрешённых операций до rps в секунду и допускает
всплеск до ёмкости бакета — rps токенов.
Метод Allow() должен быть неблокирующим: он мгновенно возвращает true,
если в бакете есть токен, и false — если он пуст. Со временем токены
пополняются со скоростью rps в секунду до ёмкости rps. Это не лимит
на каждое скользящее секундное окно: начальный запас допускает короткий всплеск.
type RateLimiter struct {
// ...
}
// NewRateLimiter создаёт лимитер на rps разрешений в секунду.
func NewRateLimiter(rps int) *RateLimiter
// Allow возвращает true, если операция укладывается в лимит.
// Метод не ждёт появления токена; короткая блокировка для защиты состояния допустима.
func (rl *RateLimiter) Allow() bool
Метод Allow() вызывается конкурентно из множества горутин, поэтому доступ к
внутреннему состоянию обязан быть потокобезопасным. Проверка идёт под детектором
гонок (-race).
В тесте при rps=100 выполняется быстрый «всплеск» из множества вызовов
Allow(); число true в пределах одного окна должно быть близко к 100
(допускается небольшой разброс). После паузы бакет должен восполниться и снова
разрешать запросы.
На что смотрит интервьюер:
- Понимание алгоритма token bucket: ёмкость =
rps, токены тратятся на
каждый разрешённый запрос и пополняются по времени.
- Потокобезопасность горячего пути:
sync/atomic или sync.Mutex,
отсутствие гонок под -race.
Allow() не ждёт токенов — возвращает false при пустом бакете.
Короткое ожидание мьютекса при конкуренции допустимо.- Бонус: горячий путь без аллокаций (zero-alloc), refill через сравнение
временных меток, а не через фоновый таймер на каждый вызов.