@MarkLb

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

Описание ситуации: Есть API, на него обращается ПО "исполнителей" для получения задания. Есть проблема: заказов не всегда есть в таком количестве, чтобы "занять" всех исполнителей. Есть желание избежать обращений каждую секунду, и самостоятельно ориентировать исполнителей через сколько секунд попытаться обратиться ещё раз.

Вопрос: как это самое время высчитывать?

Алгоритм может быть неидеальным("схожие" сайты корректируют вручную), но желательно как можно близким к реальности.
Данные в распоряжении:
1) Количество исполнителей в системе.
2) Количество задач.

Думаю, придётся вводить поле "last_execution" чтобы высчитывать "активных" исполнителей за N время.
Количество исполнителей будет примерно ~15 000. Каждое обращение генерирует:
- 1 SELECT-EXIST запрос
- 1 SELECT-запрос с LEFT JOIN

P.S. Никаких статистических данных, к сожалению, сейчас нет. Есть просто эмпирические данные коллег. Но в процессе работы можно будет скорректировать.

P.S.S. Извиняюсь за 3 тэга. Точно не знаю куда определить: по-сути ищу алгоритм, при этом ограничен PHP, но полагаю что логика исполнения задачи будет возложена на MySQL.

Примечание: Увы, установлено правило, что на стороне "клиентского ПО" нельзя ничего изменить. Данное "ПО" готово ориентироваться только на параметр "retry_after" с кол-вом секунд когда повторить.
  • Вопрос задан
  • 89 просмотров
Пригласить эксперта
Ответы на вопрос 5
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Это известная и сотню раз решенная задача. Гуглите "exponential backoff" или "Экспоненциальная выдержка".
Ответ написан
nokimaro
@nokimaro
Меня невозможно остановить, если я смогу начать.
Почему не выставить задержку исходя из доступных мощностей сервера поделённых на кол-во работников на линии?
Сперва измеряем верхнее значение, например максимальный RPS (запросов в секунду) который может держать сервер без сбоев. Предположим это 1000 rps. Далее устанавливаем предельное значение, например 80% от максимального готовы всегда держать под этот вид запросов. Итого имеем 800 rps. Исходя из этого расчитываем задержку для каждого пользователя. Делаем автоматический перерасчёт задержки каждую минуту или через любой подходящий интервал времени.

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

Единственный вариант когда это может не подойти, если у вас тарификация и оплата сервера по факту испольуземых ресурсов (iops'ы, cpu time и тд). В остальных случаях если есть сервер - пусть работает на максимум своих возможностей.
Ответ написан
sergiks
@sergiks Куратор тега PHP
♬♬
Сервер получает запросы 2 типов: Hit (если для него есть задача) и Miss (когда стукнулся, а заданий нет).
  • Штраф запросу Hit – время, которое появившаяся задача ожидала запроса.
  • Штраф запросу Miss – порядковый номер этого холостого запроса от этого клиента - 1 (1-й запрос бесплатно : )

Задания поступают случайно и непредсказуемо. Исполнители подключаются тоже случайно и непредсказуемо.

Вопрос как минимизировать штрафы.

Маловато данных.

Я бы делал задержку случайной величиной с нелинейным распределением. Вероятнее всего малая задержка, и по экспоненте уменьшается вероятность задержек более длинных.
График
602ff598991c9802769845.png
Или, половина «шляпы» нормального распределения:
602ff62996122863074501.gif

Параметр, которым рулить (и рулить очень плавно) — крутизна этой экспоненты распределения.

Для этого надо оценивать эффективность за последние X секунд-минут-часов.
  • Если больше штрафов за позднее появление рабочего — делать экспоненту круче – чтобы ещё вероятнее была маленькая задержка и менее вероятна длинная.
  • И наоборот, если слишком много обращаются рано — размазывать экспоненту, увеличивая вероятность длинной паузы у очередного запроса.
Ещё чуть усложнить можно, давая штрафам веса в зависимости от их давности: свежие штрафы весомее чем на дальнем-позднем конце окна.
Ответ написан
SilenceOfWinter
@SilenceOfWinter
та еще зажигалка...
как можно вычислить когда будут новые задачи? если никак, то считай исходя из ресурсов хоста: если пользователей мало т.е. ресурсов много - пусть стучатся чаще, много - реже.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы