Rate limiting: token bucket и окна

Перед началом: модули 1–7 (каналы, select, worker pool, лимиты параллелизма). Инструменты: Go 1.22+, golang.org/x/time/rate, Redis или его эмулятор для глобального лимита. Трудоёмкость: ~4 ч (теория 1.5 ч · практика 2 ч · квиз 0.5 ч).

🔥 Инцидент: пятьдесят инстансов и один лимит партнёра

Интеграция с внешним API: договор — 10 запросов в секунду, кратковременный burst до 20. В сервисе 50 подов, и в каждый поставили локальный token bucket на 10 rps с burst 20: «мы же соблюдаем лимит». В сумме получилось до 500 rps. Партнёр ответил лавиной 429, а затем заблокировал ключ на сутки; наши ретраи только добавили трафика. Локальные лимиты не спасли, потому что лимит партнёра — один на всех, а не на каждый под.

Этот модуль — о том, как считать скорость, где хранить счётчики и почему «отклонить быстро» иногда лучше, чем «подождать в очереди».

📖 Теория

8.1 Token bucket: средняя скорость и burst

Модель проста: есть бакет ёмкостью burst, в него с постоянной скоростью rate доливаются токены; запрос забирает один токен, а если токенов нет — получает отказ или ждёт.

  • rate задаёт среднюю скорость на длинном интервале;
  • burst разрешает кратковременный всплеск: бакет может быть полон, и тогда пройдёт сразу burst запросов.

Burst — не баг, а осознанный кредит: он сглаживает неравномерный трафик, но не позволяет превысить среднюю скорость надолго. burst = 1 даёт строгий метроном, burst = rate — запас на одну секунду.

Учебная реализация на тиках складывает refill токенов каждый тик:

go
func (b *bucket) tick() {
    b.tokens += b.refill
    if b.tokens > b.capacity {
        b.tokens = b.capacity // излишек не копим
    }
}

В продакшене отдельный тикер на каждый лимитер — расточительство. Считают лениво: при каждом запросе добавляют elapsed * rate от прошлого обращения, под мьютексом, и обрезают по burst. Время берут монотонное (time.Since), а не календарное.

8.2 Fixed window vs sliding window

Fixed window — счётчик на календарный интервал: «100 запросов в минуту» сбрасывается в начале минуты. Проблема — склейка на границе: 100 запросов в 59,9 с и ещё 100 в 60,1 с дают 200 за 1,2 секунды, хотя каждый «оконный» лимит формально соблюдён.

Sliding window убирает границу:

  • sliding log хранит метки времени всех запросов и считает окно точно, но память растёт как O(запросов в окне);
  • sliding window counter держит два счётчика — текущий и предыдущий — и берёт взвешенную сумму по доле перекрытия. Это приближение, зато O(1) памяти и почти без склейки.

Token bucket — ещё один способ сгладить границу: он вообще не привязан к календарным окнам, поэтому всплеск ограничен burst в любой момент времени.

8.3 Лимит по ключам и per-instance vs глобальный

Лимит почти всегда нужен по ключу: tenant, пользователь, IP, API-ключ. Тогда строят map[string]*bucket под мьютексом или sync.Map, а старые записи вычищают по TTL/LRU. Здесь есть две ловушки:

  • кардинальность: миллион ключей — миллион бакетов; это уже вектор атаки на память, поэтому нужен верхний предел и eviction;
  • noisy neighbor: без лимита по ключу один tenant выбирает общую квоту и душит остальных.

Теперь главное различие. Per-instance лимитер живёт в памяти процесса: 50 подов × 10 rps = 500 rps суммарно. Разделить бюджет можно (rate/N с запасом), но балансировка неидеальна, поды рестартуют, а горячий шард получает больше. Глобальный лимит требует общей точки: Redis с INCR + EXPIRE для окон или Lua-скрипт с token bucket. Атомарность важна: INCR и установку TTL лучше объединить в одном скрипте. Это сетевой round-trip на каждый запрос, contention и новый режим отказа — что делать, если хранилище лимитера недоступно: пропускать (fail open) или отклонять (fail closed). Часто ставят гибрид: маленький локальный бакет плюс глобальный.

8.4 Load shedding: отклонять быстро вместо очереди

Лимит отвечает на вопрос «сколько мы обещали», а load shedding — «что делать, когда мы уже не справляемся». Очередь при перегрузке не помогает: время ожидания растёт, клиенты уходят по таймауту, их ретраи добавляют нагрузки, память занята ожидающими запросами.

Правило: насыщенный сервис должен отклонять запросы быстро, пока может отвечать осмысленно. Способы:

  • 429 Too Many Requests с Retry-After — для квот;
  • 503 Service Unavailable — для временной перегрузки;
  • приоритеты: health-check и критичные ручки не режутся, фоновые задачи откладываются;
  • отказ на входе, до захвата дорогих ресурсов и до создания горутин.

Отклонение — это тоже ответ. Клиент получает сигнал «повтори позже», а не висит тридцать секунд и не занимает соединение.

8.5 Обзор x/time/rate

golang.org/x/time/rate — потокобезопасный token bucket с ленивым пополнением. Основные операции:

go
lim := rate.NewLimiter(rate.Limit(10), 20) // 10 rps, burst 20

if !lim.Allow() {
    http.Error(w, "too many requests", http.StatusTooManyRequests)
    return
}
  • Allow() — неблокирующая проверка: есть токен или нет;
  • Wait(ctx) — резервирует токен и спит до его появления; вернёт ошибку, если отмена или дедлайн не позволяют ждать;
  • Reserve/ReserveN — резерв с явным контролем задержки;
  • SetLimit/SetBurst — меняют параметры на ходу, без пересоздания.

Limiter не распределённый: у каждого процесса свой. Для ключей делают map[string]*rate.Limiter; для глобального лимита — Redis или отдельный сервис.

8.6 Компромиссы

  • Burst большой vs маленький: большой прощает всплески, но позволяет «залп», который добьёт слабого соседа; маленький ровнее, но хуже для естественно неровного трафика.
  • Fixed window vs sliding: fixed проще и дешевле, но склеивает границу; sliding log точен, но дорог по памяти; sliding counter — компромисс с небольшой погрешностью.
  • Локальный vs глобальный лимит: локальный без сети и отказа, но суммарная квота не гарантирована; глобальный честнее, но добавляет round-trip, contention и зависимость.
  • Ждать vs отклонять: ожидание повышает успешность в лёгкой перегрузке, но при насыщении копит очередь и время ответа; отказ быстрее и предсказуемее, но требует retry у клиента.
  • Лимит по ключу vs общий: по ключу честнее, но память растёт с числом ключей; общий дешевле, но один шумный клиент съедает квоту всех.

💻 Практика

  1. Соберите бакет на тиках. 2 заявки за тик, refill = 1, burst = 5. Снимите, сколько заявок проходит в первые тики и когда начинаются отказы; затем переделайте на ленивое пополнение по time.Since.
  2. Покажите склейку окна. Fixed window на 100 запросов в минуту: отправьте 100 в 59,9 с и 100 в 60,1 с. Зафиксируйте 200 запросов за 1,2 с, затем повторите со sliding counter.
  3. Изолируйте шумного tenant. Три ключа, у одного трафик в 10 раз выше. Сделайте лимит по ключу, добавьте TTL-очистку и покажите, что два «тихих» клиента не деградировали.
  4. Запустите сниппет модуля: бакет capacity = 5, refill = 1, по две заявки за тик. Первые четыре тика проходят обе заявки, дальше — ровно одна: за 10 тиков 14 пропущено, 6 отклонено. Вывод печатает остаток токенов и ✓/✗ по каждой заявке.

🧩 Quiz

1. Почему локальный лимит 10 rps на каждом из 50 подов не спасает?
2. Что задаёт ёмкость бакета (capacity) в token bucket?
3. В чём проблема fixed window на границе интервала?
4. Зачем при перегрузке отклонять запрос сразу, а не ставить в очередь?
5. Что вернёт lim.Wait(ctx), если дедлайн не позволяет дождаться токена?

✅ Итоги модуля

Студент должен:

  • Объяснить связь rate, burst и среднего темпа в token bucket
  • Реализовать бакет на тиках и ленивом пополнении по времени
  • Показать склейку fixed window и оценить sliding-варианты
  • Строить лимиты по ключам с eviction и защитой от кардинальности
  • Выбирать локальный или глобальный лимит и знать их цену
  • Применять load shedding вместо бесконечной очереди
  • Пользоваться x/time/rate и понимать разницу Allow и Wait
  • Ответить на все вопросы Quiz

🔗 Мостик к Модулю 9

Rate limiting защищает от слишком частых вызовов, но не от слишком долгих. Медленный хвост внешнего API исчерпывает горутины не хуже лавины, а ретраи без идемпотентности задваивают операции. Дальше — таймауты, бюджет времени, экспоненциальный бэкофф, hedged requests и выбор между «ждать» и «падать быстро».