Привет, это Всеволод Иванов и Артём Икчурин из Yandex Infrastructure — в нашей инфраструктурной команде Cloud Storage Services мы занимаемся разработкой хранилищ, которые внутри компании используются самыми разными сервисами. В Яндексе есть несколько систем хранения для разных задач, в том числе объектное хранилище для неструктурированных данных.
Несколько лет назад мы искали способы ограничить нагрузку на внутренний сервис S3 — так появилось наше собственное решение Yet Another Rate Limiter, или YARL, о котором мы уже писали на Хабре. Сегодня расскажем, как развивается наш лимитер. Так что если вам интересны высокие нагрузки, рекомендуем ознакомиться с предыдущей статьёй и затем вместе с нами отправиться под кат за продолжением.
Что важно помнить про YARL
Освежим в памяти несколько ключевых моментов из прошлой серии, про которые важно знать для понимания последующей истории:
В нашем хранилище сейчас находится несколько эксабайт данных (1018 Б), и в пиках мы обрабатываем несколько миллионов RPS‑запросов от внешних клиентов Яндекса.
Квота — это сущность, описывающая ресурс, который мы потребляем. Она содержит параметры лимитирования: лимит, который указывает, сколько событий мы можем обрабатывать в секунду для этого ресурса. Ещё есть два дополнительных параметра, которые называются low burst и high burst, и используются для вероятностного лимитирования.
Счётчик — это просто число, нужное для того, чтобы считать потребление квот. Это временная сущность, она живёт в памяти приложений, создаётся, когда квоты начинают использоваться, и удаляется, когда квоты больше не используются.
Квоты работают на базе алгоритма Leaky Bucket. В каждой статье, которую вы откроете с описанием этого алгоритма, будет нарисовано ведро, в которое сверху наливается вода.
В основе архитектуры сервиса находится мультимастер рутов, который обеспечивает отказоустойчивость. Руты — это сервисы, выступающие точками правды о том, что же происходит на кластере, которые хранят у себя потребление всех квот, созданных в системе. Каждый клиент синхронизируется с каждым рутом.
Для хранения персистентных данных, а именно параметров квот, которые мы создавали, у нас есть база данных, она позволяет не терять их между рестартами приложений и рутов.
Ещё один кубик в нашей схеме — это агрегатор. Он выступает посредником между клиентами и рутами, чтобы разгрузить последние от слишком большого количества запросов. Может устанавливаться как на каждом хосте, если на нём есть несколько клиентов YARL, так и на каждый дата‑центр. Сначала клиенты синхронизируются с агрегатором, и уже дальше он синхронизируется с рутами.
Иерархические квоты
С момента публикации первой статьи мы добавили несколько фичей в наш лимитер. Сначала напомним про иерархию квот, с помощью которой мы теперь умеем указывать зависимости между ними.
Запросы в хранилище очень разные. Есть просто читающие запросы, которые достаточно легкие и хорошо кешируются. Таких запросов можно обрабатывать очень много. Есть тяжёлые пишущие операции разных типов. Допустим, мы хотим ограничить количество запросов для каждого типа пишущей операции на 20 RPS, потому что столько выдерживает наш сервис для каждой операции по отдельности. Но что если мы получим максимум запросов по всем типам пишущих запросов? Тогда бы нам хотелось также ограничить и суммарную нагрузку, скажем, на 30 RPS.
Надо просто завести ещё одну квоту на общее количество write‑запросов. Чтобы лимитироваться сразу об две квоты, доработки в YARL не требовались.
Но если попробовать сделать Limit‑запрос последовательно по всем квотам, то при отклонении запроса последней квотой мы будем получать нечестные инкрементирования для пройденных квот. И это проблема, потому что мы начинаем пропускать меньше запросов, чем должны.
Вместо привычного запроса «Limit» к YARL‑клиенту по одной квоте (проверить квоту и инкрементировать, если запрос разрешён), нужно сделать сначала Check‑запросы для двух квот и, если все проверки успешны, то делать Increment для обеих квот.
Это вполне рабочая схема, однако усложняет код проверки. А если мы захотим добавить ещё одну общую квоту, но только для части пишущих запросов? Или создать общую квоту с читающими запросами?
Чтобы не приходилось каждый раз руками поддерживать сложные зависимости в коде, мы создали иерархические квоты. Они позволяют нам указывать иерархию нескольких квот, чтобы лимитер сам делал проверку и обновление всех квот выше по иерархии. В коде нам остаётся сделать только один запрос.
Приоритетные квоты
Новая фича — это приоритетные квоты. Она, как и иерархические, вытекает из того, что все запросы не одинаковые. Причём не только с точки зрения нагрузки на сервис, но и с той точки зрения, что приходят от разных клиентов. У нас есть как внешние клиенты, которые пользуются Яндексом и заказывают такси, смотрят погоду, делают что‑то ещё, так и роботы, которые приходят во внутреннее хранилище и выкачивают изображения для обучения нейросетей.
Во время пиковых нагрузок нам бы хотелось не трогать внешних пользователей сервисов Яндекса, а в первую очередь начинать деградацию и резать запросы роботов, потому что они могут прийти потом ночью и сделать всё, что им нужно. Чтобы у нас появилась такая возможность, мы решили создать приоритетные квоты.
Работают они следующим образом: для высокоприоритетных и низкоприоритетных запросов мы меняем параметры вероятностного лимитирования. Для низкоприоритетных запросов мы сдвигаем границу high burst в центр диапазона, и таким образом низкоприоритетные запросы начинают резаться гораздо агрессивнее. Для высокоприоритетных запросов мы, наоборот, двигаем нижнюю границу к центру диапазона нашей квоты, из‑за чего они не лимитируются, когда burst незначительный.
За счёт того, что две этих фигуры чётко отделены друг от друга, мы получаем ещё одно важное свойство системы. Высокоприоритетные запросы могут вытеснять собой низкоприоритетные запросы. На слайде ниже пример: на сервис подали нагрузку в 100 RPS низкоприоритетных запросов, а потом через какое‑то время подали ещё 30 RPS высокоприоритетных запросов.
За счёт того, как мы организовали работу с приоритетными квотами, высокоприоритетные запросы вытеснили с собой низкоприоритетные, ни одного высокоприоритетного запроса отклонено не было. И суммарная нагрузка на сервис осталась всё той же 100 RPS.
Динамические квоты
Допустим, мы хотим для каждого пользователя нашего клиента задать лимит в 100 RPS. Заранее мы не знаем всех идентификаторов наших клиентов, так как к нам ходят внешние люди, и логично использовать их IP‑адреса. Все айпишники прочитать можно, но сразу завести под все айпишники квоты невозможно, потому что их огромное количество и они часто обновляются. Поэтому хочется иметь такую фичу, которая позволила бы создать какую‑то базовую квоту, а дальше «на лету» под каждого уникального клиента создавать свой счётчик, который ограничивает потребление им ресурсов.
Вот пример, как это используется: внутри Яндекса есть такой сервис, как Аватарница. Он работает поверх нашего хранилища и занимается тем, что подготавливает различные картинки и превьюшки, которые затем показываются на всех ресурсах Яндекса. Одна из фишек сервиса в том, что сервисы, которые нами пользуются, могут не загружать картинки напрямую к нам, а просто указывать URL‑адреса, с которых мы должны эти картинки скачать.
Имена всех урлов заранее неизвестны, и мы бы хотели ограничивать нагрузку на эти внешние ресурсы, потому что не знаем, что стоит за этими доменными именами. Это может быть как огромный хостинг, который даже не заметит нагрузку от нас, так и локальный местечковый сайт, который начнёт деградировать уже при дополнительной нагрузке в 10 RPS. Поэтому нам хотелось ограничивать количество запросов ко всем внешним ресурсам, не зная заранее всех возможных имен.
Суть работы динамической квоты на этот случай: для других квот у нас была чёткая корреляция со счётчиком, который считает её потребление. В случае динамических квот мы разорвали это отношение один к одному и сделали так, что каждой квоте теперь может соответствовать несколько счётчиков, у каждого из которых теперь появляется какое‑то своё дополнительное имя лимитируемой сущности. Каждый счётчик считает потребление ресурсов, привязанное к этой сущности.
Что если нам хочется сделать исключение из правила и поменять лимит точечно для одной сущности? Что если у нас есть есть огромный хостинг, который выдерживает 1000 RPS и мы хотим разжать лимит для него? Тогда можно просто создать квоту с именем quota+entity_name. YARL перед проверкой по правилам quota будет сначала пробовать найти отдельную квоту для этой сущности и если она есть, то лимитировать по ней.
Несекундные квоты
Изначально YARL задумывался как способ лимитирования нагрузки в десятки RPS. Однако по многочисленным просьбам мы добавили возможность создавать квоты, привязанные не к секундам, а к произвольному интервалу времени.
Все запросы можно свести к одному примеру — тяжёлые запросы, обработка которых занимает ощутимо больше секунды.
Основная идея реализации этих квот очень простая, если вы уже понимаете применение алгоритма Leaky Bucket к обычным секундным квотам.
Пусть мы хотим получить квоту с ограничением в Limit запросов на период в T секунд. Тогда каждый запрос будет увеличивать счётчик сразу на +T вместо обычных +1. При этом из ведра будет «вытекать» всё тот же Limit в секунду. Low burst и high burst при этом также умножаются на T.
Но лучше разобрать это на примере. Пусть, мы хотим получить квоту на 10 запросов в минуту. Тогда можем задать следующие параметры:
T = 60 секунд.
Limit = 10 запросов.
Low burst = Limit = 10 запросов.
High burst = 2 * Limit = 20 запросов (мы разрешаем burst из 10 запросов).
Но, как было сказано выше, «под капотом» YARL будет домножать burst на T. Поэтому при расчётах для low burst и high burst будут использоваться 600 и 1200, соответственно.
Теперь давайте нарисуем на графике как будет работать лимитирование при использовании этой квоты. Для упрощения, тут всего две «волны» запросов — один запрос в момент T0 и 12 в момент T1. Обычно запросы идут постоянно и график leaky bucket скорее похож на «пилу».
Получается, что клиенты, которые хотели квоту на 10 RPM могли просто создать RPS‑квоту с low burst = 600, limit = 10 и использовать запросы с весом в 60? Не совсем. Дело в том, что YARL использует «ленивую» синхронизацию счётчиков. Это значит, что клиент синхронизировал значение счётчика с рутом только если в этот счётчик были запросы с момента последней синхронизации. Рут в ответ на такой запрос возвращал только те счётчики, которые запросил сам клиент. Что будет, если при таком подходе попробовать создать эту 10-RPM‑квоту на кластере из 100 хостов? Каждый хост, на котором ещё не было обращения к этой квоте, будет пропускать запрос и только потом однократно получать истинное значение счётчика. В такой конфигурации можно за минуту пропустить более 100 запросов, а потом на много минут уйти в состояние, где все хосты будут отклонять все запросы.
Поэтому нам потребовалось научиться отправлять клиенту все значения для несекундных счётчиков, которые были изменены с момента последнего синка с этим клиентом. В контексте RPM‑квот может показаться, что это просто исправление изначальной недоработки сервиса. Однако, для квот с десятками RPS такой подход нетипичен для подобных задач. Нужно понимать, что имеет в себе ряд ограничений.
Как и в случае RPS‑квот, мы сталкиваемся с определённой инертностью системы. Если в вышеупомянутую квоту за одну секунду придёт 1000 запросов в 100 разных хостов, то все они будут пропущены, а квота потом будет долго отклонять все запросы.
Поэтому при использовании этих квот нужно учитывать, что YARL может обеспечить честный подсчёт только «eventually» (хоть это и вопрос нескольких секунд).Точкой правды выступают изолированные друг от друга рут‑сервера, которые хранят всю информацию о счётчиках в runtime. Поэтому перезагрузка рута приводит к потере стейта. Таким образом, при последовательном рестарте всех рутов при релизе квоты с T=час будут просто обнуляться.
Это ограничение можно снять, если пересмотреть базовую концепцию о том, что руты независимые, и научить их после рестарта собирать стейт из других рутов.
Партицирование счётчиков
Итак, мы сделали:
Динамические квоты, которые позволяют без особого труда создать огромное количество счётчиков.
Несекундные квоты, более прожорливые по CPU на рут‑серверах.
Могут ли быть динамические несекундные квоты? Да, конечно. Например, нам нужно ограничить тяжёлые запросы отдельно для каждого пользователя. Сразу стало понятно, что пользователей может быть много, что стало вызовом к масштабированию YARL.
Основная проблема в том, что нам нужно поддерживать синхронизацию счётчиков достаточно быстрой. Стандартный период синхронизации это одна секунда, поэтому тайминг синхронизации должен быть гораздо меньше, даже в 99-м перцентиле.
Нагрузочное тестирование показало, что приемлемые тайминги при большом количестве пользователей мы имеем при около 100k счётчиков. Но что, если потребуется поддержать порядка миллиона счётчиков?
Для этой цели было реализовано партицирование счётчиков. Каждый счётчик принадлежит к одной партиции по хешу от ID квоты и имени сущности (если это динамическая квота). Партиции синхронизируются с рутом по отдельности, поэтому мы получаем много запросов с маленькими таймингами. С таким подходом нам удалось поддержать около 5 миллионов счётчиков с активным обновлением, что на данный момент покрывает потребности всех клиентов YARL.
При текущей архитектуре дальнейшее увеличение количества счётчиков упирается в первую очередь в то, что каждый рут должен обрабатывать все счётчики. Так что мы ограничены пределами вертикального масштабирования. Поэтому в случае, если текущих возможностей YARL окажется недостаточно, планируется научиться шардировать руты и распределять партиции по ним.
Что в итоге
YARL помогает ограничивать как потребление наших внутренних ресурсов, так и ресурсов, которые лежат вне нашей системы. Также он позволяет некоторым сервисам Яндекса плавно деградировать в случае каких‑то нештатных ситуаций либо при скачках нагрузки. Под плавной деградацией мы понимаем то, что наш сервис не сразу падает под нагрузкой, а начинает подконтрольно нам откидывать пользовательские запросы и при этом всё ещё выдавать тот максимум, который система способна обработать в текущий момент времени.
Для простеньких случаев, когда у вас маленький сервис, вы можете использовать локальные лимитеры. Если применять Nginx, то можно использовать тот модуль, про который мы рассказывали, либо построить какие‑то несложные централизованные системы. Например, можно поднять свой Redisis и там разместить счётчики, которые будут вам подсказывать, сколько ресурсов сейчас потребляется и можно ли обрабатывать новые.
Если же у вас какая‑то сложная система, в которой вы хотите обрабатывать нестандартные ситуации, то всегда можно построить собственное решение.
Больше про эволюцию хранилищ в Яндексе мы также расскажем на infra.conf'26 — приходите 4 июня послушать коллег, а также подписывайтесь на канал Yandex Infrastructure, чтобы быть в курсе других событий и новостей от инфраструктурной команды Яндекса.