Подход с разделением нагрузки в распределенной системе

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

Например, предположим, что есть два соединения серверов с разной пропускной способностью 500 Мбит/с и еще 250 Мбит/с. Пусть есть 2 пакета. Вместо отправки 2 пакетов на одно и то же соединение, т.е. 500 Мбит/с, 1 пакет будет перенаправлен на соединение 500 Мбит/с, а другой – на соединение 250 Мбит/с. Здесь цель состоит не в том, чтобы использовать одинаковую полосу пропускания для двух соединений, а в том, чтобы разделить нагрузку, чтобы каждое соединение могло разумно справляться с ней без какого-либо трафика.

Зачем использовать распределение нагрузки?

При разработке алгоритмов балансировки нагрузки возникает несколько проблем. Чтобы преодолеть эти проблемы, мы используем алгоритм распределения нагрузки. Проблемы:

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

Алгоритм распределения нагрузки включает такие политики, как политика местоположения, политика передачи процессов, политика обмена информацией о состоянии, политика оценки нагрузки, политика назначения приоритетов и политика ограничения миграции.

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

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

2. Политика передачи процессов: в этой политике используется подход «все или ничего». Пороговое значение всех узлов назначается равным 1. Узел превращается в узел-получатель, если нет процесса, а с другой стороны узел становится узлом-отправителем, если он имеет более 1 процесса. Если узлы становятся бездействующими, они не могут немедленно принять новый процесс и, таким образом, неправильно использует вычислительную мощность. Чтобы решить эту проблему, перенесите процесс на такой узел, который, как ожидается, будет простаивать в будущем. Иногда, чтобы игнорировать вычислительную мощность узлов, алгоритм распределения нагрузки изменяет пороговое значение с 1 на 2.

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

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

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

5. Политика назначения приоритетов: используются некоторые правила для определения приоритета конкретного узла. Правила таковы:

• Эгоистичный: локальный процесс имеет более высокий приоритет, чем удаленный. Таким образом, он имеет худшее время отклика для удаленного процесса и лучшее время отклика для локального процесса.
• Альтруистический: удаленному процессу предоставляется более высокий приоритет, чем локальному процессу. Он имеет лучшее время отклика.
• Промежуточный: количество локальных и удаленных процессов на узле определяет приоритет. В момент, когда количество локальных процессов больше или равно количеству удаленных процессов, локальные процессы получают более высокий приоритет, в противном случае удаленные процессы имеют более высокий приоритет, чем локальные процессы.

6. Политика ограничения миграции. Эта политика определяет абсолютное количество перемещений процесса. Можно использовать одну из двух сопутствующих стратегий.

• Неуправляемый: прибытие удаленного процесса на узел обрабатывается так же, как процесс, возникающий на узле, из-за которого процесс может мигрировать любое количество раз.
• Контролируется: параметр счетчика миграции используется для фиксации ограничения миграции процесса. Таким образом, здесь процесс может мигрировать фиксированное количество раз. Это устраняет нестабильность неконтролируемой стратегии.