Рейтлимитинг

Зачем нужно лимитирование нагрузок? Пусть ответ на этот вопрос и является довольно понятным, давайте всё же посмотрим на несколько кейсов:

• ваш сервис участвует в некотором сезонном событии, которое потенциально приносит огромную нагрузку.

Конечно в таком случае вы должны заранее оценить кол-во запросов по всем сервисам и подготовить ресурсы с запасом, чтобы выдержать всех клиентов (вы же хотите заработать побольше деняк?). Но всякое может быть и иногда лучше каким-то пользователям в моменте не ответить (такая вот graceful degradation), чем совсем лечь и не ответить никому. Потому можно срезать нагрузку выше той, которую вы можете держать.

• вы пилите сервис в инфре, на который завязано много других сервисов.

В таком случае лимитировать нагрузку становится ещё важнее, так как рандомный скачок на одном клиенте может привести к проблемам со всеми. А это потенциально сильно больше убытков, чем просто уронить один отдельный сервис.

• вас могут задудосить!

В мире есть не только милые добрые мишки-разработчики, которые хотят помочь всем вокруг. Есть и злые хацкеры, которые так и хотят кому-нибудь что-нибудь сломать.

DDoS -- это атака, целью которой является вывести систему из строя путём её бесконтрольной нагрузки. Условно злодей может посылать на ваc неприлично много запросов /ping (лёгкий запрос, который проверяет, жива ли машинка), с которыми ваши машинки не справятся. Но эффективнее конечно изучить сам сервис и выбрать запросы потяжелее, чтобы они принесли больше нагрузки.

Потому вам, как стороне бизнеса, хочется уметь от подобных ситуаций защищаться. Каким образом это можно делать?

Есть несколько классический подходов к лимитированию.

Во-первых, вы можете лимитировать нагрузку на стороне клиента (в рамках пользователя):

• ограничивать количество параллельных запросов;
• просто ограничивать количество запросов.

Например, бесплатные версии некоторых клиентов популярных нейронок вроде ChatGPT/Midjourney не позволяют делать больше X запросов за какой-то период; а ещё вы могли встречаться с подобным на литкоде, если у вас нет премиума, иногда вам явно пишут, что нельзя так часто отправлять решения. Хотя скорее это всё же происходит на стороне сервера, но концепция понятна.

И на стороне сервера (в целом всё аналогично, но в случае клиента для кейсов выше вы можете убрать нагрузку заранее). Вообще можно каким-то образом трекать текущее состояние системы (здоровье) и подстраивать лимитирование под него. Но это совсем запарные подходы.

В обоих случаях можно ещё лимитировать отдельные тяжёлые запросы.

Предположим, наш график запросов без рейт-лимитера выглядит так:

Когда мы включаем рейт-лимит, мы можем жёстко зафиксировать какую-то планку, выше которой запросы мы не обрабатываем:

Однако это не самое лучшее решение. Если пользователю не повезло оказаться 101м запросом, мы его просто отбросим и он будет вынужден заретраить. Хотя вдруг мы этот один запрос всё-таки ещё тянем? Здесь нам может помочь burst-limiting:

Тут у нас есть два лимита. Soft (выше в 100 rps) и hard (200 rps). По хард лимиту мы срезаем запросы аналогично тому, что мы делали выше. Но ещё мы вводим правило, что мы не хотим обрабатывать более 10k запросов в минуту. Софт лимит нужен для учёта того, как много запросов сейчас вылезли за границу и как много в следующий момент времени нам нужно обрезать (т.е. если мы сейчас обработали 120 запросов, то в следующую секунду сможем только 80). Получается, софт лимит это про какое-то ограничение в среднем.

Стоит понимать, что лимитировать мы можем не только запросы, но и кол-во байт от клиентов/кол-во пакетов некоторого размера и любые другие параметры, которые можно зафиксировать и измерить.

А ещё "лимитировать нагрузку" совсем не означает, что вы должны варварски отбросить все запросы сверх лимита. Вполне можно класть их в очередь на выполнение, увеличив тем самым время ответа, но обработав запрос позже.

Burst-лимитирование это про то, чтобы не позволить резким скачкам ("взрывам") нагрузки сломать вашу систему. Как конкретно реализовывается burst-лимитирование, посмотрим ниже.

Leaky Bucket

Leaky bucket -- концепция, когда вы отрезаете всё, что каким-то образом переполняет вашу текущую капасити.

Есть две популярные реализации этого подхода, которые возникли независимо и были названы одинаково, что иногда вызывает недопонимания.

В первой версии у вас есть счётчик, который инкрементируется при появлении новых запросов и декриментируется при их удалении. Когда счётчик становится равным лимиту, все новые запросы можно отбрасывать. Этот подход иногда называют leaky bucket as a meter.

Вторая версия -- очередь, имитирующая течение воды в подобной ситуации. У вас есть очередь, в которую вы добавляете задачи и достаёте их (поддерживая FIFO). Ограничение для кол-ва запросов -- фиксированная верхняя граница размера очереди. Это чаще называют leaky bucket as a queue.

Второй подход обычно используют когда вы хотите ограничить проходимость канала, обрабатывающего ваши запросы. Первый же является решением в общем виде, над которым можно наворачивать ещё что-то.

Подробнее можно почитать тут.

Token bucket

Token bucket -- подход, в котором вы проверяете, можете ли в данные момент выполнить задачу.

В бакете у вас хранятся некоторые токены, которые являются "разрешением"/"билетом" для задачи. Они добавляются в бакет с некоторой скоростью 1/r, где r -- ваш лимит. Когда появляется новая задача, необходимо проверить, есть ли токен в бакете, и, если да, достать его оттуда и отправить задачу на выполнение. Чтобы в бакете не накопилось слишком большое количество токенов, его размер обычно тоже ограничивают.

Управляя размером вашего бакета и скоростью добавления токенов, вы можете не только лимитировать нагрузку, но и контролировать IO flow в вашей системе (одно из основных применений этого подхода).

Концептуально token bucket это примерно то же, что и leaky bucket as a meter.

Чуть (совсем чуть) больше информации можно найти в этой статье.

Window подходы

Оконные подходы к лимитированию -- это когда вы смотрите на какой-то промежуток времени и отрезаете нагрузку не только в моменте, но и суммарно. Конечно, прошлые алгоритмы были ровно про это же, но концептуально следующие являются более явным решением в такой формулировке.

Обычно тут используется окно некоторого размера: например, минута или час. Вы храните счётчик, в котором лежит количество текущих обрабатываемых/пришедших запросов, с помощью которого можете обрезать лишние значения.

Иногда это окно определяется нижней границей текущего временного интервала (fixed window). Например, если запрос пришёл в 00:00:01, то он попадает в окно, которое начинается в 00:00:00.

С одной стороны, тут вы можете обрабатывать новые запросы, не обрезая их из-за всплеска на границе предыдущего окна. Но с другой, как раз всплеск на границе может привести к тому, что количество обрабатываемых запросов в моменте сильно растёт.

Иногда окно не фиксируют и считают количество запросов за последний промежуток времени (sliding log). В случае этого алгоритма вы считаете запросы от каждого клиента, что позволяет вам лимитировать пользователей по отдельности -> нагрузка от одного пользователя не повлияет на других. Однако, такое решение требует больше памяти и в целом вычислений. Плюс, это не защищает от естественного роста кол-ва пользователей (а дудосят часто как раз не от одного лица).

Потому есть совмещённое решение -- sliding window. Это когда вы считаете нагрузку просто за последний промежуток времени в целом.

Проблемы с лимитированием

Когда ваша система большая, лимитировать нагрузку на одном узле становится недостаточно: количество балансеров/инстансов лимитера растёт. Потому необходимо как-то их синхронизировать, т.к. иначе пользователь-злодей может легко отправлять запросы на разные узлы, при этом завалив вашу систему.

Самый простой способ справиться с подобным -- привязать одного пользователя к конкретному узлу балансера/лимитера. Но лучше хранить информацию про лимиты в централизованном хранилище. Там конечно свои проблемы, но про это уже не будем.

Можно почитать статью про то, как на базе leaky bucket устроен YARL -- один из яндексовых рейтлимитеров. Он как раз решает вопросы, связанные с централизованным хранением информации о лимитировании.

Тыква

Опа. В самом конце расскажу ещё про один подход ограничения нагрузки, когда всё и так плохо. Его иногда называют тыква или dummy.

Предположим, у вас что-то уже сломалось. Не обязательно по причине высокой нагрузки. Вы вполне могли выкатить релиз с багом и теперь не можете, например, создавать заказы. В таком случае было бы хорошо сообщить пользователю о том, что у вас какие-то проблемы. Это может быть небольшая плашка, которую видно из любой точки вашего приложения/сайта.

Когда вы явно говорите пользователю, что что-то не работает, вы можете естественным образом срезать нагрузку с части сервиса: он просто не будет пытаться создавать условный заказ, если понимает ситуацию.

По-хорошему это должна быть логика на проксе/около неё/какой-то ручке, которая дёргается клиентом регулярно, чтобы вы не нагружали лишней нагрузкой бекенд.

Вместо логического завершения