Распределённый rate limiter

Начни там, где алгоритм чист: один процесс, без сети, вся тонкость — в математике пополнения. Token bucket держит до `burst` токенов и пополняется со скоростью `rate` токенов/сек; каждый запрос стоит один токен, и запрос разрешён, только если ведро непусто. Хитрость в том, что ты не запускаешь фоновый таймер пополнения — ты считаешь пополнение лениво на каждом запросе из `elapsed = now - lastRefill`, затем зажимаешь до `burst`. Это позволяет клиенту простаивать, накопить полный burst и потратить его одним всплеском (скажем, 100 запросов в ведре на 100 при пополнении 10/с) — ровно то bursty-but-bounded поведение, что тебе нужно, и ровно поэтому наивные счётчики fixed-window ощущаются неправильно. Доведи математику и зажим до точности здесь, в одном потоке, до того как всё это должно пережить Redis round trip в 0.5–2 мс или гонку двух инстансов.

В момент, когда ты запускаешь два инстанса приложения за балансировщиком, состояние в памяти процесса врёт: каждый инстанс держит своё ведро, так что N инстансов пропускают N× от лимита. Счётчик должен жить в одном общем месте, и Redis — обычный выбор, потому что однопоточный сервер даёт точку сериализации и операции за доли миллисекунды. Но read-modify-write, разбитый по сети (GET, вычислить, SET), — это гонка: между твоими GET и SET другой инстанс может декрементировать, и два запроса дважды потратят последний токен. Этот этап — про то, чтобы перенести состояние ведра (tokens, lastRefill) в Redis и доказать, что опасность конкуренции существует, до того как ты починишь её правильно в Lua — замерь over-admission под конкурентным молотом, чтобы у следующего этапа была базовая линия для побития.

Почини гонку, схлопнув read-modify-write в одну атомарную единицу. Lua-скрипт Redis (через EVAL/EVALSHA) выполняется до конца без переплетения, потому что Redis однопоточен — так что всё обновление ведра (прочитать tokens+lastRefill, пополнить из elapsed, зажать до burst, декрементировать если разрешено, записать назад) становится одним неделимым шагом, и многоузловой double-spend просто не может случиться. На senior-глубине важны два правила дизайна: (1) передавай `now` в скрипт аргументом, а не вызывай `redis.call('TIME')`, чтобы скрипт был детерминированным и безопасным для репликации/AOF на узлах с расхождением часов; (2) держи скрипт крошечным и O(1) — он держит единственный поток, так что медленный скрипт стопорит каждого другого клиента. Перезапусти конкурентный молот из прошлого этапа и смотри, как over-admission уходит в ноль.

Теперь обоснуй алгоритм, потому что у выбора есть реальные режимы отказа. Счётчик fixed-window (инкремент ключа, истекающего на границе окна) — самый дешёвый, один INCR, но допускает 2× burst через границу: клиент может выпустить `limit` запросов в последнюю секунду окна A и ещё `limit` в первую секунду окна B, удвоив задуманную скорость на один миг. Sliding-window log чинит это точно, храня метки времени по каждому запросу, но его расход памяти растёт с частотой запросов (sorted set из N записей на ключ). Sliding-window counter дёшево аппроксимирует его, взвешивая предыдущее окно. Реализуй хотя бы одну альтернативу рядом со своим token bucket и нагрузи их все при всплесках трафика, чтобы сформулировать, с числами, компромисс точность-против-памяти, а не утверждать его.

Лимитер, который просто роняет запросы, — плохой сосед; воспитанный точно говорит клиенту, как отступить. Возвращай 429 Too Many Requests с `Retry-After` (секунды до доступности токена, вычисленные из дефицита ведра и скорости пополнения) и стандартными заголовками `RateLimit-Limit / -Remaining / -Reset`, чтобы клиенты сами тормозили до блокировки. Затем закали политику: выбирай ключ лимита осознанно (API-ключ лучше голого IP, потому что NAT/CDN ставит тысячи пользователей за один IP, а единственный подделываемый заголовок подделать легко), и реши, что происходит, когда сам Redis недоступен. Fail-open держит сайт живым, но даёт атакующему тривиальный обход (урони Redis — лимитер исчезает); fail-closed защищает бэкенд, но превращает мигание Redis в полный простой. Senior-ответ обычно — ограниченный локальный фолбэк, а не бинарный выбор.

Докажи это под реальной нагрузкой и сделай читаемым, когда оно ведёт себя плохо. Нагрузи лимитер как развёрнутый (несколько инстансов, настоящий Redis, смешанный разрешённый/затроттленный трафик) и найди QPS, при котором узким местом становится Redis round trip, а не твоё приложение: при ~0.5–2 мс на EVALSHA синхронная проверка лимитера ограничивает пропускную способность каждого инстанса, а медленный или горячий Redis добавляет эту латентность к каждому запросу. Снимай RED-метрики (rate запросов, throttle/error rate, длительность проверки лимитера) и трейс-span на вызов Redis, чтобы видеть собственную латентность лимитера в водопаде запроса. Затем отработай инцидент: горячий ключ (один злоупотребляющий тенант или все запросы по одному значению из-за бага) концентрирует нагрузку на одном слоте Redis, p99 проверки лимитера взлетает, и лимитер начинает тормозить трафик, который должен был защищать. Обнаружь это по своему дашборду, смягчи и найди корневую причину.