Алгоритм, чтобы сгладить пиковое использование с течением времени?

Question

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

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

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

(В конечном итоге и несколько менее актуально, я буду реализовывать этот алгоритм с использованием C #.)

Answer 1

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

http://en.wikipedia.org/wiki/Hash_function

По сути, разделите все, что вы хотите, чтобы ваше окно обновления было на соответствующее количество сегментов. Один из вариантов может быть 3 часа * 60 минут * 60 секунд = 10800 сегментов. Затем используйте его в качестве размера хеш-таблицы для выбранной функции хеширования. Ваш уникальный ввод может быть идентификатором устройства. Не забудьте использовать GMT для выбранного времени. Ваш предпочтительный язык программирования, вероятно, имеет ряд встроенных функций хеширования, но в статье должны быть приведены ссылки, с которых можно начать, если вы хотите реализовать их с нуля.

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

Вот более конкретная информация о том, как реализовать различные функции:

http://www.partow.net/programming/hashfunctions/index.html

Answer 2

Вы говорите, что можете указать устройствам, в какое время подключаться, поэтому я не понимаю, зачем вам нужно что-то случайное или модульное. Когда каждое устройство подключается, выберите время завтра, которое в настоящее время не имеет много назначенных устройств, и назначьте устройство этому времени. Если все устройства потребляют примерно одинаковое количество ресурсов для обслуживания, то тривиальный жадный алгоритм даст совершенно плавное распределение - назначьте каждому устройству то время, которое в данный момент меньше всего перегружено. Если сервер обрабатывает другую работу, а не только эти устройства, вам следует начать с его типичного профиля нагрузки, а затем добавить к нему нагрузку на устройство. Я бы не стал называть это «аналитическими вычислениями», просто сохраняя гистограмму ожидаемой нагрузки в зависимости от времени в течение следующих 24 часов.

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

Answer 3

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

Это даст вам оптимально равномерное распределение во всех случаях.

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

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

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

Если вы хотите обеспечить стабильное распределение устройств по регионам, рассчитайте соотношение устройств по регионам.и распределите распределение слотов соответствующим образом.Например, если у вас есть 50/25/25 по часовому поясу соответственно, назначьте слоты для первого часового пояса, затем следующие два слота для оставшихся часовых поясов, а затем повторите.