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

Question

[Mark]

Описание ситуации: Есть 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" с кол-вом секунд когда повторить.

Comments

[Сергей Соколов]

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

«Правильным» решением тут конечно будет держать постоянные подключения от исполнителей: будь то WebSocket, как уже посоветовали, или просто подключение любой стандартной библиотекой к Redis на вашем сервере.

В исходных данных вы не указали трудоёмкость задач: одинакова ли, какое время занимает, зависит ли от исполнителя.

[Сергей Соколов]

Ещё не понятно, как появляются новые задания: линейно раз в N минут, или случайно, то густо то пусто.

[Сергей Соколов]

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

[Mark]

Сергей Соколов,
1) По изменений ПО понял свою ошибку, добавил комментарий:

Примечание: Увы, установлено правило, что на стороне "клиентского ПО" нельзя ничего изменить. Остаётся только высчитывать грамотный алгоритм, чтобы определить параметр "retry_after"

.
2) Задачи появляются случайным образом на протяжении дня.

можно ли поменять направление вызовов, чтобы это сервер обращался к исполнителям?

К текущей задачи это не касается, но буду рад за информацию по этому вопросу(интересно). По-сути, мы высылаем данные исполнителю, что-то вроде WebHook. Но как это реализовать для софта? Вижу такой алгоритм:
1. При запуске ПО разработчик создаёт "адрес"(как? с помощью IP, открывается какой-то порт?), высылает на сервер.
2. Сервер регистрирует адрес. Когда появляется новое задание - шлёт на "вебхук" ПО данные.
3. При выключении ПО/если ПО не обновляет информацию об статусе раз в N минут/более N неотвеченных запросов от ПО - удаляем "адрес".

Так?

[Mark]

Сергей Соколов, 3) Исполнитель появляется "случайно"(когда захотел - тогда включился).

4) Цель: Сформировать число, через которое мог бы обратиться исполнитель к серверу за задачей.
"Миссия": Простая оптимизация работы сервера. Чтобы не перенагружать его.

"Простым языком"/Примером: Сегодня по заказам "негусто", штук 100 в час появилось. А 6000 исполнителей онлайн каждую секунду шлют запрос на проверку задач. А вчера было "погуще", 2000 заказов/час.

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

[Anton Kuzmichev]

Mark, попробуйте тогда капнуть в сторону long-polling'а, если у вас строго HTTP API. Самые простейшие чаты 90х работали на нём и успешно. Потому что всё остальное будет довольно труднонастраиваемым балансом между частотой запросов и временным лагом между появлением задания и его взятием.

[Сергей Соколов]

1. При запуске ПО разработчик создаёт "адрес"(как? с помощью IP, открывается какой-то порт?), высылает на сервер.
2. Сервер регистрирует адрес. Когда появляется новое задание - шлёт на "вебхук" ПО данные.
3. При выключении ПО/если ПО не обновляет информацию об статусе раз в N минут/более N неотвеченных запросов от ПО - удаляем "адрес".

Mark, да, вполне разумный сценарий, предполагающий, что ПО серверное: «рабочие» это, пусть и временные, сервера с постоянным IP. Ну либо возятся открывают порт на своем роутере, чтобы ваш сервер снаружи мог достучаться до софта на их ноутбуках – это уже менее юзабельно.

Answer 1

[Rsa97]

Websocket

Comments

[Mark]

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

[Антон Шаманов]

+1, так у тебя и так по клиента ждет заказа

Answer 2

[Wataru]

Это известная и сотню раз решенная задача. Гуглите "exponential backoff" или "Экспоненциальная выдержка".

Comments

[Mark]

Спасибо, изучаю материал. Есть вопрос(извиняюсь, если звучит глупо - не имею опыта в направлении, слышал первый раз):

Суть заключается: не ограничивать число запросов, но когда сервер сляжет реализуется механизм "экспоненциальной выдержки", чтобы сервер мог подняться?

[Wataru]

Mark, Сервер, если не может обработать запрос сразу отвечает клиенту "я занят". Клиент, если получает от сервера это, или таймаут или ошибку запроса - откатывается.

[Mark]

Илья Николаевский, понял, похоже видел такой алгоритм в Telegram когда их сервер был недоступен. Спасибо!
Но я внёс коррективу, которую при создании вопроса упустил:

Увы, установленоправило, что на стороне "клиентского ПО" нельзя ничего изменить. Данное "ПО" готово ориентироваться только на параметр "retry_after" с кол-вом секунд когда повторить.

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

"Простым языком"/Примером: Сегодня по заказам "негусто", штук 100 в час появилось. А 6000 исполнителей онлайн каждую секунду шлют запрос на проверку задач. А вчера было "погуще", 2000 заказов/час.

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

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

[Wataru]

Mark, Можно эту же логику сделать на сервере. Или для каждого клиента считайте, сколько раз он уже посылал запрос и был послан, или считайте, сколько было отказов всем клиентам в какое-то окно времени.

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

Answer 3

[nokimaro]

Почему не выставить задержку исходя из доступных мощностей сервера поделённых на кол-во работников на линии?
Сперва измеряем верхнее значение, например максимальный RPS (запросов в секунду) который может держать сервер без сбоев. Предположим это 1000 rps. Далее устанавливаем предельное значение, например 80% от максимального готовы всегда держать под этот вид запросов. Итого имеем 800 rps. Исходя из этого расчитываем задержку для каждого пользователя. Делаем автоматический перерасчёт задержки каждую минуту или через любой подходящий интервал времени.

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

Единственный вариант когда это может не подойти, если у вас тарификация и оплата сервера по факту испольуземых ресурсов (iops'ы, cpu time и тд). В остальных случаях если есть сервер - пусть работает на максимум своих возможностей.

Answer 4

[Сергей Соколов]

Сервер получает запросы 2 типов: Hit (если для него есть задача) и Miss (когда стукнулся, а заданий нет).

• Штраф запросу Hit – время, которое появившаяся задача ожидала запроса.
  
• Штраф запросу Miss – порядковый номер этого холостого запроса от этого клиента - 1 (1-й запрос бесплатно : )
  

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

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

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

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

График

Или, половина «шляпы» нормального распределения:

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

Для этого надо оценивать эффективность за последние X секунд-минут-часов.

• Если больше штрафов за позднее появление рабочего — делать экспоненту круче – чтобы ещё вероятнее была маленькая задержка и менее вероятна длинная.
  
• И наоборот, если слишком много обращаются рано — размазывать экспоненту, увеличивая вероятность длинной паузы у очередного запроса.
  

Ещё чуть усложнить можно, давая штрафам веса в зависимости от их давности: свежие штрафы весомее чем на дальнем-позднем конце окна.

Answer 5

[Антон Шаманов]

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