Методы и алгоритмы балансировки нагрузки

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

· Справедливость – необходимо гарантировать выполнение всех запросов.

· Эффективность – все сервера должны использоваться равномерно и брать на себя равномерную нагрузку.

· Сокращение времени выполнения запроса – необходимо сократить время между поступлением запроса и его выполнением.

· Сокращение времени отклика – необходимо минимизировать время ответа на запрос.

· Масштабируемость – при возрастании нагрузки на систему её работа должна оставаться стабильной.

Ниже перечислены некоторые из них.

Round- Robin – самый простой алгоритм балансировки. Задания назначаются на машины в последовательном порядке, то есть первое задание назначается на первую машину, второе – на вторую машину, и так происходит циклически по кругу. Нагрузка сервера, его вычислительная мощность и время выполнения не являются факторами при выборе сервера. Данный алгоритм лучше всего подходит для систем, в которых производительность всех серверов одинаковая, а требования поставленной задачи к каждому серверу похожи [1].

Weighted Round- Robin – это расширенный round-robin алгоритм, в котором каждому серверу назначается коэффициент веса. Веса назначаются в зависимости от вычислительной мощности машины: чем больше производительность сервера, тем больше коэффициент. Сервера с большим коэффициентом получают большее количество задач. Как и в round-robin алгоритме, задачи назначаются на машины последовательно: на машину назначается количество заданий равное весовому коэффициенту, после чего происходит переход на следующую машину. Это позволяет распределить задания более гибко [1].

Least Connections – алгоритм, который учитывает количество активных подключений к серверам. При поступлении запроса алгоритм выбирает сервер с наименьшим количеством активных подключений и назначает запрос на него [1].

Weighted Least Connections – усовершенствованный Least Connections алгоритм, в котором каждому серверу присваивается весовой коэффициент. Сервер выбирается с наименьшим значением метрики. Метрика вычисляется как количество активных подключений, делённое на весовой коэффициент. Данный алгоритм используется, когда сервера имеют разную производительность. Его целью является равномерное распределение подключений между серверами с большой и низкой производительностью. Чем больше вычислительная мощность сервера, тем большее число подключений он может обработать [1].

Source IP- Hash – данный алгоритм генерирует уникальный хэш-ключ из исходного и целевого IP-адреса клиента. Этот ключ используется для распределения пользователя на определённый сервер. Таким образом, пользователь даже после разрыва соединения будет направлен на тот же сервер, с которым взаимодействовал ранее [2].

Постановка задачи

Введём следующие обозначения.

– множество из M машин (серверов);

 – множество из N задач (запросов);

Каждая задача  имеет время выполнения ;

 – множество заданий, назначенных на машину  из множества n;

– общее время работы (нагрузка) машины m_i.

(1)

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

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

Описание алгоритмов

Greedy-Balance

Greedy-Balance алгоритм – это простой жадный алгоритм, который в любом порядке перебирает поставленные задачи и назначает каждую из них на машину с минимальной текущей нагрузкой [3].

Пусть даны непустые множества m и n, и пустое множество заданий A. В множестве n элементы располагаются в любом порядке. Из множества задач берётся элемент  и добавляется в множество , где i – это элемент множества m с минимальным на текущий момент . Так продолжается до тех пор, пока множество n не станет пустым.

На Рис. 1.3 приведён псевдокод алгоритма.

1	void GreedyBalance(queue <task> n, machine m[], queue <task> A []) // n - множество задач, m - множество машин, A - множество задач машин
2	{
3	int min;
4	while(!n.empty())
5	{
6	min = find_min(m); // ищем номер машины с минимальной нагрузкой
7	task temp = n.front(); // берём элемент из множества
8	n.pop(); // убираем задачу из множества
9	m[min].T += temp.T; // прибавляем машине время обработки задачи
10	A[min].push(temp); // добавляем задание во множество задач машины min
11	}
12	}
Рис. 1.3. Псевдокод Greedy-Balance алгоритма.

Временная сложность алгоритма O (M·N), где M – количество машин, а N – количество задач. При этом, используя очередь с приоритетом, временная сложность алгоритма составит O (log (M) · N). На Рис 1.4 приведён псевдокод алгоритма с использованием очереди с приоритетом.

 

1	void GreedyBalanceModified(queue <task> n, priority_queue<machine> m) // n - множество задач, m - множество машин
2	{
3	machine min;
4	while(!n.empty())
5	{
6	min = m.top(); // берём машину с минимальной нагрузкой
7	m.pop(); // удаляем машину из очереди с приоритетом
8	task temp = n.front(); // берём элемент из множества задач
9	n.pop(); // убираем задачу из множества
10	min.T += temp.T; // прибавляем машине время обработки задачи
11	m in.A.push(temp); // добавляем задание во множество задач машины min
12	m.push(min);
13	}
14	}
Рис. 1.4. Псевдокод Greedy-Balance алгоритма с применением очереди с приоритетом.

Наглядный пример последовательной работы алгоритма представлен на Рис. 1.5: стрелочки указывают на машину, которой будет назначена текущая задача; каждая задача имеет время выполнения; задачи последовательно назначаются на машину с минимальным временем выполнения на данный момент времени. Период обработки равен 7.

 

Рис. 1.5. Пример работы Greedy-Balance алгоритма.

Sorted-Balance

Sorted-Balance алгоритм – это разновидность жадного алгоритма, которая в порядке убывания времени выполнения задачи распределяет их на машины с минимальной текущей нагрузкой [3].

Даны непустые множества m и n, и пустое множество заданий A. В начале работы алгоритма все задачи множества n сортируются в порядке убывания по времени выполнения . Затем последовательно из множества задач берётся элемент  и добавляется в множество , где i – это номер машины с минимальной нагрузкой. Действия повторяются пока множество n не станет пустым. На Рис. 1.6 приведён псевдокод алгоритма.

1	void SortedBalance(queue <task> n, machine m[], queue <task> A []) // n - множество задач, m - множество машин, A - множество задач машин
2	{
3	int min;
4	Sort(n); // сортируем множество задач по убыванию времени
5	while(!n.empty())
6	{
7	min = find_min(m); // ищем номер машины с минимальной нагрузкой
8	task temp = n.front(); // берём элемент из множества
9	n.pop(); // убираем задачу из множества
10	m[min].T += temp.T; // прибавляем машине время обработки задачи
11	A[min].push(temp); // добавляем задание во множество задач машины min
12	}
13	}
Рис. 1.6. Псевдокод Sorted-Balance алгоритма.

Временная сложность алгоритма O ( + M·N), где  – время выполнения сортировки множества N в порядке убывания времени выполнения. Как и в предыдущем алгоритме, при использовании очереди с приоритетом временная сложность алгоритма составит O ( + log (M)·N). Псевдокод с использованием очереди с приоритетом представлен на Рис. 1.7.

 

 

1	void SortedBalanceModified(queue <task> n, priority_queue<machine> m) // n - множество задач, m - множество машин
2	{
3	machine min;
4	sort(n); // функция сортировки очереди заданий в порядке убывания времени выполнения
5	while(!n.empty())
6	{
7	min = m.top(); // берём машину с минимальной нагрузкой
8	m.pop(); // удаляем машину из очереди с приоритетом
9	task temp = n.front(); // берём элемент из множества задач
10	n.pop(); // убираем задачу из множества
11	min.T += temp.T; // прибавляем машине время обработки задачи
12	m in.A.push(temp); // добавляем задание во множество задач машины min
13	m.push(min);
14	}
15	}
Рис. 1.7. Псевдокод Sorted-Balance алгоритма с применением очереди с приоритетом.

Пример работы алгоритма представлен на Рис. 1.8: в начале работы алгоритма элементы множества n сортируются в порядке убывания, после чего происходит распределение задач между машинами; стрелочки указывают машину назначения. Период обработки равен 6.

Рис. 1.8. Пример работы алгоритма

Анализ алгоритмов

Введём следующие обозначения.

 – период обработки текущей балансировки.

– оптимальная возможная нижняя граница периода обработки текущей балансировки.