Балансировка нагрузки¶

Нода получает задачу выполнить некоторую задачу (фрагмент). В процессе исполнения фрагмент может одновременно запускать множество других фрагментов. Если они требуют много ресурсов, нода отдаёт их другим узлам.

Алгоритм (10.2016)¶

Часть первая. Оперативное рапределение задач.

Ноде дается задание выполнить фрагмент
Если нода имеет свободные ресурсы, то фрагмент запускется локально.
Если текущих ресурсов недостаточно для выполнения фрагмента, то выполняется перенаправление задачи на дргуие ноды. Если задачу перенаправить некуда, она складывается в локальную очередь. Важные моменты:
- Определние требуемых ресурсов не учитывает предпологаемую нагрузку запускаемых фрагментов. С точки зрения рантайма они все равны.
- Задачи перенапрваляются на ноды с наименьшей (с точки зрения текущей ноды) нагрузкой.

Часть вторая. Фоновое перераспредление задач по принципу work-stealing.

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

Важные свойства¶

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