Модуль 3. Rate limiting: алгоритмы и Token Bucket на Redis через Lua

Цель модуля: выбрать алгоритм лимитирования осознанно — и реализовать Token Bucket на Redis с атомарностью Lua: разбор боевого скрипта (HSET-бакет, refill, clock-skew защита, TTL от утечки памяти) и его Go-обвязки.

Перед началом: Модуль 1 (клиент, политики отказа). Инструменты: go-redis/v9 (redis.NewScript), стенд boilerplate. Трудоёмкость: ~8–10 ч (теория 4 ч · практика 5 ч).

🔥 Инцидент: «Лимитер, который не лимитит»

Внешний API-провайдер дал лимит: 100 запросов в минуту. Команда поставила «лимитер» — и через неделю провайдер прислал 429 и временный бан. Разбор: проверка была вида GET счётчик → сравнить → INCR, то есть не атомарна: два горутины на двух репликах читали одно значение, обе прошли проверку, обе инкрементировали. А локальный in-memory кэш на каждой реплике умножал лимит ещё и на число подов. Итоговый «лимит» был равен 100 × поды × удача — и на нагрузочном тесте в один поток этого не видно.

Отсюда два правила, на которых стоит весь модуль: решение о лимите принимается атомарно (Lua в Redis — единственное место, где живут и проверка, и инкремент), и состояние лимита — одно на всех (Redis), а не по экземпляру сервиса. А ещё выбор алгоритма — не вкусовщина: fixed window даёт «клык ×2» на границе окна, sliding log точен, но жрёт память. Ниже — таблица выбора и боевой Token Bucket на Lua.

📖 3.1. Зачем лимитируют: четыре мотива

1. Защита сервиса — от сканера, DDoS, сломанного клиента в цикле;
2. Справедливость — один тяжёлый клиент не съедает ресурс соседей;
3. Тарифы — API-планы (free/pro) как продукт;
4. Лимиты внешних провайдеров — не превысить квоту платного API (входящий лимит защищает вас, исходящий — ваши отношения с провайдером; исходящему посвящён Модуль 5).

От мотива зависит, что важнее: точность (тарифы, биллинг), скорость (защита) или поведение при всплесках (burst).

📖 3.2. Алгоритмы: таблица выбора

Для защиты и тарифов token bucket — стандарт индустрии (так считают лимиты у большинства API-провайдеров): он честно пропускает кратковременные всплески до burst и усредняет до rate на длинной дистанции. Именно его берём в Redis.

📖 3.3. Почему Redis и почему Lua

Кластерный лимит = один счётчик на всех репликах приложения. Все инстансы обращаются к одному ключу — лимит точен независимо от числа подов (в отличие от in-memory: N реплик × rps, см. Модуль 4).

Проблема: token bucket — это read-modify-write (прочитать бакет → пополнить → попробовать списать → записать). Два пода, читающие одновременно, оба увидят токены и оба спишут — кластерный лимит нарушен. Решение — Lua-скрипт: Redis исполняет скрипт атомарно (однопоточный цикл команд), гонок нет. Бонус: скрипт экономит round-trip — весь цикл за одну сетевую операцию.

Наивная альтернатива без Lua — INCR key + EXPIRE key 60 (fixed window в две команды): работает, но наследует клык фиксированного окна и отдельную гонку «INCR прошёл, EXPIRE не успел» (лечится NX-версией, но клык остаётся).

📖 3.4. Token Bucket на Lua: разбор боевого скрипта

Показать кодКопировать код

Слева — карта выбора из таблицы выше: если всплески нужно прощать (человек открыл страницу, которая делает 20 запросов разом) — это Token Bucket или GCRA; если окно обязано быть строгим — sliding-семейство, и вопрос только в памяти. Справа — механика выбранного бакета: кран пополняет его со скоростью rate, запрос снимает токен; пусто — 429 с Retry-After, а не бесконечный ретрай. Дальше — этот бакет в Lua, атомарно и с защитой от скачков часов.

Скрипт из production-шаблона (сокращённо, с ключевыми решениями):

lua
-- KEYS[1] — ключ бакета, напр. "ratelimit:192.168.1.1"
-- ARGV[1] rate (токенов/с), ARGV[2] capacity (burst),
-- ARGV[3] now (unix-секунды с дробной частью), ARGV[4] requested (обычно 1)
-- Возвращает: { allowed (0|1), floor(tokens) }

local last_time = redis.call('hget', key, 'last_time')
local tokens    = redis.call('hget', key, 'tokens')

-- Первый запрос: бакет полон
if not last_time then
    last_time = now
    tokens    = capacity
else
    last_time = tonumber(last_time)
    tokens    = tonumber(tokens)
end

-- Refill: токены накопились со времени последнего запроса
local delta = now - last_time
if delta < 0 then
    delta = 0 -- clock skew: время назад после failover — не «награждаем»
end
tokens = math.min(capacity, tokens + delta * rate)

-- Попытка списать
local allowed = 0
if tokens >= requested then
    tokens  = tokens - requested
    allowed = 1
end

-- Сохраняем состояние + TTL от утечки памяти:
-- бакет бесполезен дольше, чем «время полного наполнения»
redis.call('hset', key, 'last_time', now, 'tokens', tokens)
local ttl = math.ceil(capacity / rate) + 1
redis.call('expire', key, ttl)

return { allowed, math.floor(tokens) }

Пять решений, зашитых в эти 30 строк — спрашивайте их на ревью любого лимитера:

1. Бакет в HSET (два поля), а не два ключа — атомарно и одним ключом;
2. Время передаёт приложение (ARGV[3]) — единый источник времени и лёгкость тестов (подставьте «будущее» и проверьте refill). Минус: доверие часам подов — защита delta < 0 от скачка часов обязательна; альтернатива — redis.call('TIME') внутри скрипта (время Redis, но нельзя писать после него в старых версиях — потому now снаружи);
3. math.min(capacity, ...) — бакет не копит «долг» токенов сверх ёмкости; вариант из boilerplate курса: ARGV[3] опционален — не передано, скрипт берёт TIME сервера сам (Redis 7 реплицирует эффекты скриптов, поэтому недетерминированный TIME безопасен);
4. TTL = capacity/rate + 1 — ключ сам удаляется, когда бакет успел бы наполниться полностью: неактивный клиент не занимает память бесконечно;
5. requested как параметр — списание N токенов для «тяжёлых» операций (1 токен = 1 КБ ответа, тяжёлый отчёт = 50 токенов).

📖 3.5. Go-обвязка: redis.NewScript и результат

go
var tokenBucket = redis.NewScript(tokenBucketLua) // кэширует EVALSHA

func (rl *RedisLimiter) Allow(ctx context.Context, key string) (bool, int, error) {
    now := float64(time.Now().UnixNano()) / 1e9
    res, err := tokenBucket.Run(ctx, rl.client,
        []string{rl.prefix + ":" + key},
        rl.rate, rl.burst, now, 1,
    ).Result()
    if err != nil {
        return false, 0, err // политика отказа решает вызывающий (Модуль 1)
    }
    vals := res.([]interface{})
    allowed := vals[0].(int64) == 1
    remaining := int(vals[1].(int64))
    return allowed, remaining, nil
}

• redis.NewScript сам использует EVALSHA (кэш скриптов на сервере) с фолбэком на EVAL при NOSCRIPT — не изобретайте это вручную;
• Политика отказа (Redis недоступен) — не здесь: это решение уровня middleware/обёртки (Модули 1 и 4).

💻 Практика

1. Загрузите скрипт и поиграйте руками (boilerplate курса):

   bash
   make bucket && make drain && make refill

   drain — 10 быстрых вызовов подряд: allowed=1 ровно пять раз (burst), потом 0; refill через 3 секунды — токены восстановились (2/с × 3 с, но не больше capacity=5). Скрипт берёт время с сервера Redis сам — поэтому лаба работает и на macOS.
2. Точность под гонкой: два Go-процесса бьют по одному ключу по 1000 раз; суммарно пропущено ровно burst + скомпенсированный refill — без Lua и без скрипта (два отдельных вызова GET/SET) продемонстрируйте превышение.
3. Клык фиксированного окна: соберите INCR+EXPIRE-вариант и прострелите границу минут: 2 × burst за 2 секунды. Теперь вы понимаете, почему token bucket.
4. Скачок часов: передайте now - 3600 (время назад) — refill не «наградит» бакет.

Артефакт: token_bucket.lua + тест точности под конкуренцией + сравнительная таблица с фиксированным окном.

🧩 Quiz "Проверь себя"

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

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

Механизм готов. Теперь встроим его в путь HTTP-запроса: middleware с X-RateLimit-* заголовками и 429, выбор ключа лимитирования (IP против user — и подмена X-Forwarded-For), и production-архитектура local + global: почему один in-memory лимитер перед Redis экономит и латентность, и сам Redis, и что происходит, когда Redis умирает.