Есть сотни тыс. периодических заданий, где каждое должно выполняться со своим собственным периодом повтора: раз в 12 часов, у других раз в 15 минут, например.
Помимо периода P, у задания ещё два параметра: время T, когда его уже можно начать выполнять (не раньше), и коэффициент срочности K, который означает, как быстро с момента T линейно растёт приоритет этого задания. При прочих равных K = 1/Period
Рабочий процесс дискретный, запускается «шагами» раз в 5 минут по крону. Каждый раз берет охапку заданий, из тех, что уже можно исполнять, ориентируясь на приоритеты на данный момент этих заданий, и не больше, чем своя «ёмкость», которая ограничена.
Ситуация: в один момент времени внезапно пришла сразу 1000 новых заданий. При ёмкости в 300 задач за один шаг такой пик вызовет лавину задержек у всех задач. Поэтому эту 1000 заданий надо постепенно раскидать, чтобы они шли не в единый момент, а +-. Но «разъехались» они по этим новым своим позициям не мгновенно, а в течение какого-то времени. Напр. можно ограничивать скорость «сползания» каждой задачи в % от её периода.
Вопрос: как корректировать фазу периодических заданий, чтобы пики нагрузки «размазывались» по времени? При этом надо, чтобы если какое-то задание и сдвигалось, оно делало это постепенно, маленькими шагами. Тут важно, чтобы интервал выполнения каждого задания был максимально приближен к целевому – у кого-то это 12 часов, у кого-то 15 минут.
По аналогии с физическим миром, как я себе представляю, это похоже на насыпание частиц (кристаллов песка) на поверхность. Чтобы песчинки в итоге распределились более ли менее равномерно, надо поверхность встряхивать, снова и снова. Каждый раз частицы стремятся удалиться от соседей. И это постепенно приводит к равномерному распределению.
Может, есть известный алгоритм, описывающий такую модель?
Ответ
Можно организовать приоритетную очередь заданий. Постараюсь объяснить. Допустим у Вас есть 1000 заданий, каждое со своей периодичностью. Т.е. Вы знаете, в какие моменты времени каждая из этих задач должна в следующий раз запуститься. В таком случае при наступлении некоторого момента времени, когда должна запуститься одна или несколько задач, Вы их не запускаете, а ставите в очередь определенным образом. Например, ёмкость рабочего процесса 300 задач. В некоторый момент времени должно запуститься 450 задач. 300 из них Вы запускаете на выполнение (задержка 0*T), остальные остаются в очереди. Через 5 минут Вы должны запустить еще 170 задач. Вы эти 170 ставите в начало очереди, так что бы рабочий процесс забрал сначала их (задержка 0*T), затем он доберёт до свой емкости из прошлых задач еще 130 (задержка 1*T). Через следующие 5 минут все повторится. При этом есть вероятность, общее количество заданий превысит физический предел обработки 24 часа * 12 задач в час * 300 заданий в обработке. В этом случае часть заданий, которая превышает это число, вообще не будет обрабатываться. Однако и от этого можно избавиться, достаточно для каждого задания отслеживать, сколько оно находится в очереди. Если это значение превысило некоторый порог (необходимо будет рассчитать или определить опытным путём), то повышать приоритет задания, сдвигая его в начало очереди, т.е. запускать "принудительно". Если у Вас задания нескольких разных типов, можно ввести более развитую приоритетную систему.
Комментариев нет:
Отправить комментарий