Комментарии 26
Написан на Go? Эрланговский рейтлимитер забросили как только ушло эрланг-лобби? :)
Да, YARL написан на Go.
Похоже, что примерно так и получилось. Я, к сожалению, не знаю истории развития и заморозки лимитера на эрланге.
А исходники закрыты?
А GC в Go вас не смутил и не мешает? Основная цель ведь максимально быстро давать ответ.
Нет, не мешает. Никаких специальных приседаний для борьбы с GC мы не делали.
GC начиная с версии 1.5-1.6 уже не такой злой, каким был. Это раньше он мог на 50-100мс залочить исполнение программы и хрустеть там себе памятью.
Сейчас он блокирует мир на очень короткое время и влияния GC мы пока на метриках не видим.
Я немного пропустил, кто организует утечку?
Выбирается некий "мастер YARL", который применяет на себе spent_quota -=(limit*seconds_since_last_update) а потом синхронизируется со всеми серверами, или это делается как-то иначе?
все на самом деле чуть-чуть хитрее. Нижняя граница ведра вычисляется как unix_timestamp*limit, а верхняя как unix_timestamp*limit + low_burst, т. е. они динамические, а суммарное значение счетчика строго возрастает. Получается, что "утечка" организуется благодаря текущему времени, за счет смещения границ ведра. В текущее значение при синхронизации с рутом добавляется то, что насчиталось с момента предыдущей синхронизации. Если это значение ниже нижней границы, то "доливаются" запросы до нижней границы. Синхронизация выполняется параллельно с несколькими рутами, и просто выбирается наибольшее значение счетчика.
Что такое "постреливать запросы клиента"?
Это значит кидать в клиента HTTP 429.
Спасибо за статью, пришел к такому же решению. Делал свой middleware на go c локальными счетчиками и синхронизацией, идентификатор брал из jwt-токена или сессии. Надо будет обдумать ваше решение с lowBurst и highBurst, мне помимо счетчиков нужен был именно sliding window rate limiter, но я вроде не стал его реализовывать.
Только к исчерпанию квоты относился более лояльно, не хранил локально значения, позволял пока делать запросы до следующей синхронизации. Но я получается хранил списки тех, кто исчерпал свою квоту на это месяц. Переполнение счетчиков тоже не волновало, т.к. если они переполнились, то значит это наш косяк и можно простить.
Я правильно понимаю, что в вашем случае задача была измерять квоту на длинной дистанции (суммарное потребление чего-то за неделю/месяц/квартал)?
Если да, то такие штуки мы тоже делаем, но не через YARL. Это задача, которой я очень вскользь коснулся, когда говорил об учёте потребления дисков (объём объектов в бакетах). У такой задачи безусловно есть свои особенности, но обычно там сильно меньше требования и к скорости реакции на событие, и к скорости подсчёта потребления. Его можно хоть в фоне делать отдельной джобой по крону.
YARL затачивался именно под производные величины по времени. Кажется, математически это записывается как-то так: 
Такие штуки очень резко меняются и там за лишнюю минуту времени реакции можно весь сервис успеть в ступор поставить. Поэтому важно как можно раньше понимать, что нужно начинать отстреливать клиентов.
В нашем случае мы тоже не стреляем запросы до синхронизации: пока синхронизация не пройдёт, каждая отдельная тачка в кластере просто не знает, сколько всего прилетело в кластер. Просто мы синкаемся раз в секунду, поэтому реакция выглядит вполне шустро.
Да, я думаю, это частый кейс, квоты на API, например, бесплатный тариф 10 тыс. запросов в месяц. Делали чтобы каждый сервис часто не дергал базу, синхронизация была раз в минуту чтобы у пользователя графики были красивые. Отдельное ограничение на количество запросов тоже делали, но с фиксированным окном. Я понял в чем различие в вашим кейсом, у нас нет своих кластеров, но если было бы нужно, мы могли бы тоже настроить чтобы через пару минут поднимались доп. контейнеры в облаке. Раз в секунду слишком часто для нас.
Интересное решение! Спасибо за описание!
Спасибо за статью. Я правильно понимаю, что каждый сервис локально у себя хранит данные в виде user_id => его текущие квоты по данному сервису?
И да, и нет.
YARL встраивается в приложение. Либо в nginx с помощью модуля, либо в go-код прям вкомпиливанием пакета. Т.е. приложение в итоге знает обо всех квотах и счетчиках, которые имеют отношение к приложению.
Но модуль/пакет YARL при этом ничего не знает о логике приложения, и приложение не знает о кишках YARL'а. Общение происходит через простой интерфейс: "вот тебе уникальное имя квоты (текстовое), накрути/проверь/залимитируй".
Приложение, имея доступ к информации о запросе, может из этой информации сгенерить какое-то уникальное имя квоты. Тут мы в S3 можем использовать User ID, имя бакета, тип HTTP-запроса или любое другое свойство, которое из этого запроса можно достать. Из этих данных приложение генерит имя квоты и скармливает YARL'у.
Так что приложение хранит у себя в памяти алгоритм генерации имени квоты для запроса, а модуль YARL хранит в памяти 2 map'ы: ``<quota uniq name> => <quota info>`` и ``<counter ID> => <counter value>``. По имени квоты он достаёт из map'ы её параметры (лимит, high/low burst и ID счетчика), а по текущему значению счетчика понимает, нужно ли блокировать запрос.
В такой схеме достаточно в базе YARL завести квоту с правильным именем, чтобы начать лимитировать запросы с определенными свойствами. Например, если приложение для чтения любого объекта из бакета myawesomebucket проверяет квоту "s3_myawesomebucket_object:get", то достаточно добавить в базу YARL запись с таким именем и запросы автоматом начнут ограничиваться через пару-тройку секунд.
Limiter хранит все квоты и счётчики в памяти и регулярно синхронизируется с корневым сервером (YARL root), получая от него оперативную информацию о свежих значениях.
а как боретесь с выпадением/обновлением root'а? Что будет, если он окажется перегружен?
Про выпадение/обновление:
Никак не боремся. Система устойчива к исчезновению любого из root-серверов, она этого даже не замечает.
Каждый инстанс сервиса (в нашем случае хост с сервисом S3) просто отправляет свои счётчики во все root-серверы, о которых она знает, независимо друг от друга. Т.е. мы в конфиге S3 прям прописываем: вот тебе 3 root'а - ходи в них. Когда этот инстанс от каждого из root'ов получает свежие значения счетчиков для всего кластера, он выбирает самое большое значение и использует его.
Синхронизация происходит в фоне, так что залипший синхронизирующий запрос к одному из root'ов никак не сказывается на скорости обработки клиентского запроса. Выпал root - все синхронизации к нему будут таймаутиться, от него к каждому инстансу не будут приходить счётчики кластера. Инстанс будет просто опираться на данные от двух оставшихся root'ов. Выпадет второй root - будем лететь на одном. Выпадут все - лимитирование из распределенного превратится в локальное: синхронизация вырубится и каждая из тачек продолжит накручивать локальные счётчики (сколько конкретно в неё пришло), но не будет знать об общей нагрузке на кластер. В этом случае нам проще считать, что лимитирование вырубается, т.к. у нас в кластере больше 300 машин: чтобы накрутить тот же счётчик до условных 1 000RPS без синхронизации, нужно на весь кластер равномерно подать 300*1000 = 300 000 RPS.
Как только root вернётся - инстансы начнут с ним синхронизироваться и счётчики root'а быстро вернутся к актуальным значениям.
Про "перегруженный" root:
В нашей архитектуре все root'ы обрабатывают одинаковую нагрузку. Если будет тупить какой-то один или два из трёх - это никак не скажется на лимитах. От таких тупящих root'ов на инстансы будет приходить меньшее значение счётчиков и они просто будут отбрасываться (из трёх разных чисел для одинакового счётчика от трёх рутов мы просто выбираем больший). Могут оказаться перегруженными все 3 рута одновременно. Мы пока до такого не доходили, но если такое случится, то YARL начнёт "занижать" нагрузку на весь кластер: часть хостов не смогли отправить счётчики -> суммарный счётчик для кластера складывается из меньшего количества значений -> оценка нагрузки на кластер меньше реальной -> мы лимитируем запросы позже, чем должны.
То есть снаружи эта ситуация будет выглядеть так, будто мы равномерно увеличили лимиты всем клиентам.
YARL: как Яндекс построил распределённый Rate Limiter с нулевым влиянием на время ответа сервисов