Нужен in-memory rate limiter без сторонних библиотек: не больше n вызовов за
окно window на каждый ключ (пользователя, IP, API-токен). Лимитер вызывается из
множества горутин, и блокировок должно быть как можно меньше.
type Limiter interface {
Allow(key string) bool
}
// NewLimiter создаёт лимитер «не больше n вызовов за window на ключ», n >= 1.
// now — источник времени; nil означает time.Now.
func NewLimiter(n int, window time.Duration, now func() time.Time) *SlidingLimiter
func (l *SlidingLimiter) Allow(key string) bool
Требования
- Алгоритм — скользящее окно (sliding window log). Вызов в момент
t
разрешается, если за полуинтервал (t − window, t] по этому ключу было
разрешено меньше n вызовов. Отказы не считаются.
- Фиксированные окна («сбрасываем счётчик раз в
window») не подходят: на стыке
двух окон они пропускают до 2n вызовов. Token bucket тоже не подходит, у него
другая семантика.
- Ключи независимы: исчерпанный лимит одного ключа не влияет на другие.
- Время берётся только из
now(). Так тесты управляют часами без Sleep.
Allow безопасен при конкурентных вызовах: при n = 50 и сотне горутин,
которые долбят один ключ в один и тот же момент, разрешено ровно 50.
Код проходит go test -race.- Минимум блокировок: проверки разных уже известных ключей не ждут друг
друга. Пока идёт
Allow по одному ключу (включая вызов now()), Allow по
другому ключу не блокируется. Один мьютекс на весь лимитер не подходит.
Пример
l := NewLimiter(3, time.Second, nil)
l.Allow("u1") // true
l.Allow("u1") // true
l.Allow("u1") // true
l.Allow("u1") // false — 3 за секунду уже было
l.Allow("u2") // true — у другого ключа свой лимит
// через секунду после первого вызова снова освободится один слот
Ключей могут быть миллионы, и большинство из них один раз пришли и пропали.
// Cleanup удаляет состояние ключей, у которых за последнее окно не было разрешённых вызовов.
func (l *SlidingLimiter) Cleanup()
// Len — число ключей, для которых лимитер сейчас хранит состояние.
func (l *SlidingLimiter) Len() int
- После
Cleanup ключи без событий в (now − window, now] удалены, остальные на
месте, и лимиты по ним продолжают действовать.
Cleanup безопасен при параллельных Allow: удаление не должно «потерять»
только что разрешённый вызов.
Устно: какие гонки возможны (check-then-act на создании ключа, удаление ключа
во время Allow)? Как на лимитер влияет GC, если хранить []time.Time на ключ и
держать миллионы ключей? Чем sliding window log отличается от sliding window
counter и token bucket, и что выбрать для API-гейтвея?