Эффективное использование API с ограничением скорости (Echo Nest) с распределенными клиентами

Фон

Echo Nest имеет ограниченный скоростью API. Данное приложение (идентифицированное в запросах с использованием ключа API) может составлять до 120 вызовов REST в минуту. Ответ службы включает оценку общего количества вызовов, сделанных в последнюю минуту; повторное злоупотребление API (превышение лимита) может привести к отзыву ключа API.

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

Но я работаю над программой, в которой распределенные, независимые клиенты делают запросы параллельно.

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

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

Учитывая все вышеперечисленное, какие подходящие алгоритмы для клиентов, чтобы они соответствовали требованиям к скорости? Обратите внимание, что ограниченное сотрудничество возможно, потому что API возвращает общее количество запросов в последнюю минуту для всех клиентов.

Текущее решение

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

Если количество вызовов меньше 60 (половина предела), клиент не дросселирует. Это позволяет получать быстрые пакеты с небольшим количеством запросов.

В противном случае (т.е. когда есть больше предыдущих запросов) клиент вычисляет предельную скорость, в которой он должен работать (т.е. period = 60 / (120 - number of previous requests)), а затем ждет, пока разрыв между предыдущим вызовом и текущим временем не превысит этот период (в секунд, 60 секунд в минуту, 120 максимальных запросов в минуту). Это эффективно дросселирует скорость так, чтобы, если бы она действовала одна, она не превышала бы предела.

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

Лучшие решения

Я могу представить лучшее решение, которое использует полную локальную историю клиента и моделирует других клиентов, скажем, с помощью скрытой марковской модели. Таким образом, каждый клиент будет использовать отчет API для моделирования других (неизвестных) клиентов и соответственно корректировать его.

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

Существуют ли такие подходы? Может ли кто-либо предоставить реализацию или ссылку? Может ли кто-нибудь подумать о лучшей эвристике?

Я предполагаю, что это известная проблема где-то. В какой области? Теория очередей?

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

Мне также интересно (в меньшей степени, для дальнейшего использования, если программа становится популярной) в решении, для которого требуется центральный сервер для совместной работы.

Отказ

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

Кроме того, каждый клиент имеет локальный кеш, используемый для предотвращения повторных вызовов.

Обновление

Возможно, соответствующая статья.

Ответ 1

Это работало, но было очень шумно, и код был беспорядок. Теперь я использую более простой подход:

Вызов
Из ответа обратите внимание на лимит и количество

Вычислить

barrier = now() + 60 / max(1, (limit - count))**greedy

При следующем вызове подождите barrier

Идея довольно проста: вам нужно подождать некоторое время, пропорциональное тому, как осталось несколько запросов в эту минуту. Например, если счет равен 39, а предел равен 40, вы ждете целую минуту. Но если count равен нулю, вы можете сделать запрос в ближайшее время. Параметр greedy является компромиссом - когда более 1 "первые" вызовы выполняются быстрее, но вы, скорее всего, достигли предела и в конечном итоге ожидаете 60 секунд.

Выполнение этого похоже на подход выше, и он гораздо более надежный. Это особенно хорошо, когда клиенты "раздуты", поскольку вышеприведенный подход запутывается, пытаясь оценить линейные ставки, в то время как это с радостью позволит клиенту "украсть" несколько быстрых запросов, когда спрос будет низким.

Код здесь.

Ответ 2

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

Каждый клиент может отслеживать свою собственную (локальную) скорость соединения, используя очередь временных меток. Временная метка добавляется в очередь на каждом соединении, а отметки времени старше одной минуты отбрасываются. Средняя долгосрочная средняя (более минуты) определяется с первой и последней отметки времени и количества записей (минус один). "Краткосрочная" (мгновенная) ставка может быть найдена из времен последних двух запросов. Верхний предел - это максимум этих двух значений.

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

Каждый клиент вычисляет эти две ставки (локальные и внешние), а затем добавляет их для оценки верхнего предела общей скорости соединений с сервером. Это значение сравнивается с целевой полосой скорости, которая в настоящее время установлена на уровне от 80% до 90% от максимального значения (от 0.8 до 0.9 * 120 в минуту).

Из разницы между оценочной и целевой ставками каждый клиент изменяет собственную скорость соединения. Это делается путем принятия предыдущей дельта (время между последним соединением и предыдущим) и масштабирования ее на 1.1 (если скорость превышает целевую) или 0.9 (если скорость ниже целевой). Затем клиент отказывается создавать новое соединение до тех пор, пока эта масштабированная дельта не пройдет (путем спящего режима, если запрашивается новое подключение).

Наконец, ничто не заставляет всех клиентов одинаково распределять пропускную способность. Поэтому я добавляю дополнительные 10% к местной оценке курса. Это приводит к преимущественной переоценке ставки для клиентов с высокими ставками, что делает их более склонными к снижению их ставки. Таким образом, у "жадных" клиентов есть немного более сильное давление, чтобы уменьшить потребление, которое в долгосрочной перспективе представляется достаточным для сбалансированного распределения ресурсов.

Важная информация:

Принимая максимум "долгосрочных" и "краткосрочных" оценок, система является консервативной (и более стабильной) при запуске дополнительных клиентов.
Ни один клиент не знает общее количество клиентов (если он не равен нулю или один), но все клиенты запускают один и тот же код, поэтому могут "доверять" друг другу.
Учитывая вышеизложенное, вы не можете делать "точные" расчеты о том, какую скорость использовать, но вы можете сделать "постоянную" коррекцию (в данном случае коэффициент +/- 10%) в зависимости от глобального скорость.
Регулировка частоты подключения клиента производится до дельта между двумя последними соединениями (настройка на основе среднего значения в течение всей минуты происходит слишком медленно и приводит к колебаниям).
Сбалансированное потребление может быть достигнуто путем ненадлежащего наказания жадных клиентов.

В (ограниченных) экспериментах это работает достаточно хорошо (даже в худшем случае нескольких клиентов, начинающихся сразу). Основными недостатками являются: (1) он не допускает начального "всплеска" (что бы повысить пропускную способность, если на сервере мало клиентов, а у клиента всего несколько запросов); (2) система все еще колеблется в течение ~ минуты (см. Ниже); (3) обработка большего количества клиентов (в худшем случае, например, если все они начинаются сразу) требует большего усиления (например, 20% -ная коррекция вместо 10%), что делает систему менее стабильной.

"Используемая" сумма, сообщаемая сервером (test), построенная по графику против времени (эпоха Unix). Это для четырех клиентов (цветных), которые пытаются максимально использовать как можно больше данных.

Осцилляции происходят из обычного сигнала запаздывания источника - коррекции. Они затухают по (1), используя верхний предел скоростей (предсказывая долгосрочную скорость от мгновенного значения) и (2) с использованием целевой полосы. Вот почему был бы оценен ответ, сообщенный кем-то, кто понимает теорию управления...

Мне не ясно, что важно оценивать локальные и внешние ставки отдельно (они могут помочь, если краткосрочная ставка для одного высока, а долгосрочная ставка для другой высокая), но я сомневаюсь, что ее удаление улучшится вещи.

В заключение: все это в значительной степени, как я ожидал, для такого подхода. Это своего рода работа, но поскольку он простой подход с обратной связью, он только стабилен в пределах ограниченного диапазона параметров. Я не знаю, какие альтернативы могут быть возможны.

Ответ 3

Поскольку вы используете API Echonest, почему бы вам не воспользоваться заголовками ограничения скорости, которые возвращаются при каждом вызове API?

В общем, вы получаете 120 запросов в минуту. Существует три заголовка, которые могут помочь вам самостоятельно регулировать потребление API:

X-Ratelimit-Used
X-Ratelimit-Remaining
X-Ratelimit-Limit

** (Обратите внимание на нижний регистр "ell" в "Ratelimit" - документация заставляет вас думать, что он должен быть капитализирован, но на практике это более строгий вариант.)

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

Довольно аккуратно, да? Ну, я боюсь, что есть руб...

Этот 120-запрос в минуту действительно является верхней границей. Вы не можете рассчитывать на это. В документации указано, что стоимость может колебаться в зависимости от нагрузки системы. В некоторых случаях я видел это как минимум 40 штук, и в некоторых случаях он выглядел ниже нуля (я действительно надеюсь, что это ошибка в API-интерфейсе echonest!)

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

Это хорошо работает до момента. Поскольку Echonest не корректирует предел в предсказуемом маннаре, на практике практически невозможно избежать 400.

Вот несколько ссылок, которые я нашел полезными:

http://blog.echonest.com/post/15242456852/managing-your-api-rate-limit http://developer.echonest.com/docs/v4/#rate-limits