Обзор
«Балансировка нагрузки» означает, что поставщики услуг могут равномерно отдавать предпочтение запросам с помощью определенного алгоритма, так что дождь и роса подвергаются равномерному воздействию. На рынке представлено множество программно-аппаратных продуктов, и наиболее решаемые основные проблемыкого выбрать.
Классификация
По реализации можно разделить на аппаратную балансировку нагрузки (например, F5, A10), программную балансировку нагрузки (например,LVS, Nginx, HAProxy), балансировка нагрузки DNS. Мы не будем уделять слишком много внимания аппаратной балансировке нагрузки и балансировке нагрузки DNS, а сосредоточимся на программной балансировке нагрузки.
Балансировка нагрузки программного обеспечения разделена на четыре уровня и семь уровней балансировки нагрузки.Балансировка нагрузки четвертого уровня заключается в использовании портов IP-адресов для пересылки запросов на сетевом уровне, который в основном играет роль пересылки и распределения. Балансировка нагрузки уровня 7 предназначена для пересылки запросов на определенный хост в соответствии с заголовком HTTP-запроса и информацией URL-адреса запрашивающего пользователя. LVS — это балансировка нагрузки уровня 4. Nginx и HAProxy может быть четыре или семь.
В дополнение к специальному оборудованию и профессиональному программному обеспечению, такому как Nginx, для обеспечения балансировки нагрузки, это также распространенный способ реализовать его непосредственно в коде. Например, компонент Ribbon в системе Spring Cloud предоставляет несколько стратегий загрузки: опрос, случайный и взвешенный в зависимости от времени отклика.Например, при использовании кластера Memcached для распределения данных в клиенте обычно используется хэш по модулю или согласованное хеширование. равномерно.
Общие алгоритмы
Наиболее распространенными алгоритмами балансировки нагрузки являются случайный, взвешенный случайный, циклический, минимальное количество подключений и последовательное хеширование.Давайте посмотрим, как реализовать их в коде Java. Для удобства сравнения мы определяем интерфейс Balanceable, предполагая, что все серверы, участвующие в процессе балансировки нагрузки, реализуют интерфейс Balanceable.
1. Случайный
В соответствии со значением размера списка внутренних серверов случайным образом выбирается один из них для доступа, код выглядит следующим образом:
public Balanceable choice(Balanceable[] servers) {
int index = (int) (Math.random() * servers.length);
return servers[index];
}Преимущества: простота реализации, случайный выбор одного из них для доступа через системную функцию случайного выбора
Недостаток: Не применимо к ситуации непостоянной грузоподъемности серверных машин.
2. Взвешенный случайный выбор
Каждый узел имеет разные веса.Хотя он выбирается случайным образом, ожидается, что узлы с разными весами имеют разную вероятность быть выбранными.Вероятность выбора с большим весом высока, а вероятность выбора с низким весом мала. код показывает, как показано ниже:
public Balanceable choice(Balanceable[] servers) {
int seed = 0;
for (Balanceable server : servers) {
seed += server.getWeight();
}
int random = r.nextInt(seed);
Collections.sort(Arrays.asList(servers));
int tmp = 0;
for (Balanceable server : servers) {
tmp += server.getWeight();
if (tmp >= random) {
return server;
}
}
return null;
}Предположим, что есть три узла A, B, C и их веса равны 3, 2 и 4 соответственно, тогда это можно выразить так
Возьмем любую точку на прямой, какой узел выбран, в области какого узла на прямой принадлежит эта точка:
Добавьте все веса, чтобы получить S (фактически длину линии)
Возьмем случайное число R из интервала [0, S) (случайным образом выбирается точка на прямой)
Пройдите список узлов, добавьте веса посещенных узлов, чтобы получить V, и сравните значения V и R. Если V > R, текущий узел является выбранным узлом. (Найдите область, в которой позиция R в строке принадлежит какому узлу)
Преимущества: простота реализации, использование весов для изменения вероятности быть выбранным
Недостаток: Не применимо к ситуации непостоянной грузоподъемности серверных машин.
3. Опрос (круговой алгоритм)
Опрос относится к выбору узла по порядку из существующего списка внутренних узлов для предоставления услуг. код показывает, как показано ниже:
Integer pos = 0;
public Balanceable choice(Balanceable[] servers) {
Balanceable result = null;
synchronized(pos) {
if (pos >= servers.length){
pos = 0;
}
result = servers[pos];
pos++;
}
return result;
}Считайте, что все машины выбраны как точки одна за другой, и все точки нанизаны вместе в круг. Представьте, что опрос выполняется в каждой точке круга, проходя по часовой стрелке и останавливаясь в каждом узле. Реализуем отбор по часовой стрелке через количество запросов pos. Поток, которому необходимо изменить pos, может изменить значение только после получения блокировки.Когда значение больше или равно длине списка серверов, он снова начнет обход с 0, чтобы достичь цели цикла в течение одной недели. .
Достоинства: условно говоря, запросы могут быть абсолютно сбалансированы
Недостаток: Для абсолютного баланса необходимоГарантирует взаимную исключительность при изменении pos, введение блокировок синхронизации приведет к снижению производительности
4. Наименьшее соединения
Из списка существующих серверных частей выберите узел, который обрабатывает наименьшее количество подключений/запросов для обслуживания. Так как необходимо определить количество подключений/запросов, каждый узел должен сохранить часть информации о количестве обрабатываемых подключений/запросов, а затем судить при выборе узла, и выбрать узел с наименьшим количеством подключений . код показывает, как показано ниже:
public Balanceable choice(Balanceable[] servers) {
int length = servers.size();
int leastActive = -1;
int leastCount = 0;
int[] leastIndexs = new int[length];
int totalWeight = 0;
int firstWeight = 0;
boolean sameWeight = true;
for (int i = 0; i < length; i++) {
Balanceable invoker = servers[i];
int active = status.getStatus(servers).getActive();
int weight = server.getWeight();
if (leastActive == -1 || active < leastActive) {
leastActive = active;
leastCount = 1;
leastIndexs[0] = i;
totalWeight = weight;
firstWeight = weight;
sameWeight = true;
} else if (active == leastActive) {
leastIndexs[leastCount++] = i;
totalWeight += weight;
if (sameWeight && i > 0
&& weight != firstWeight) {
sameWeight = false;
}
}
}
if (leastCount == 1) {
return servers[leastIndexs[0]];
}
if (!sameWeight && totalWeight > 0) {
int offsetWeight = random.nextInt(totalWeight);
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
offsetWeight -= getWeight(servers[leastIndex]);
if (offsetWeight <= 0)
return servers[leastIndex];
}
}
return servers[leastIndexs[random.nextInt(leastCount)]];
}Сначала найдите текущее минимальное количество активных подключений поставщика услуг.Если количество сервисных подключений одного поставщика услуг меньше, чем у других, выберите поставщика услуг с наименьшим количеством активных подключений для инициирования вызова.Если есть несколько поставщиков услуг Количество активных подключений является наименьшим, затем взвешенный случайный алгоритм выбирается среди этих поставщиков услуг для выбора поставщика услуг.
Преимущества: динамически распределяется в соответствии с текущей ситуацией обработки запросов сервера.
Недостатки: Реализация алгоритма относительно сложна, и необходимо отслеживать количество соединений, запрошенных сервером.
5. Согласованный хэш
Вычислите хэш-значение в соответствии с фиксированным атрибутом бэкэнд-узла, а затем объедините хеш-значения, вычисленные всеми узлами, в хеш-кольцо. Когда приходит запрос, вычислите хэш-значение функции в соответствии с запрошенной функцией (используя ту же хэш-функцию, что и для вычисления хеш-значения внутреннего узла), затем найдите хеш-значение на кольце хэшей по часовой стрелке, а первый - это хеш-значение запрошенной функции. Узел, соответствующий хеш-значению с большим значением, является выбранным узлом.
При выходе из строя определенной части узлов или при динамическом добавлении новых узлов необходимо перемещать только небольшую часть данных в кольцевом пространстве, что обеспечивает лучшую отказоустойчивость и масштабируемость.
Построить хэш-кольцо
public static TreeMap<Long, String> populateConsistentBuckets(
String... servers) {
// store buckets in tree map
TreeMap<Long, String> consistentBuckets = new TreeMap<Long, String>();
MessageDigest md5 = MD5.get();
int totalWeight = servers.length;
for (int i = 0; i < servers.length; i++) {
int thisWeight = 1;
double factor = Math
.floor(((double) (40 * servers.length * thisWeight))
/ (double) totalWeight);
for (long j = 0; j < factor; j++) {
byte[] d = md5.digest((servers[i] + "-" + j).getBytes());
for (int h = 0; h < 4; h++) {
Long k = ((long) (d[3 + h * 4] & 0xFF) << 24)
| ((long) (d[2 + h * 4] & 0xFF) << 16)
| ((long) (d[1 + h * 4] & 0xFF) << 8)
| ((long) (d[0 + h * 4] & 0xFF));
consistentBuckets.put(k, servers[i]);
}
}
}
return consistentBuckets;
}Вышеупомянутое хэш-кольцо имеет проблему, то есть хеш-значения узлов не обязательно равномерно распределены по хеш-кольцу, что приведет к тому, что некоторые узлы будут нести слишком много запросов. Решение состоит в том, чтобы ввести виртуальные узлы: каждый узел повторяется n раз, и хеш-значение этих виртуальных узлов (которое отличается от хеш-значения фактического узла, то есть к атрибуту узла нужно что-то добавить чтобы гарантировать, что каждый виртуальный узел совпадает с фактическим узлом.Значения хэшей разные, и они также отличаются друг от друга) также добавляются в хеш-кольцо для обеспечения более равномерного распределения.
Найдите подходящий узел из кольца:
public static final Long getBucket(TreeMap<Long, String> buckets, Long hv) {
SortedMap<Long, String> t = buckets.tailMap(hv);
return (t.isEmpty()) ? buckets.firstKey() : t.firstKey();
}Здесь есть момент, на который следует обратить внимание, а именно обработка критического значения: за последней точкой на хеш-кольце могут быть какие-то запросы, то есть хеш-значение больше, чем хэш-значение запрошенной функции, не может быть найдено на хеш-кольце. . В случае, когда соответствующий следующий узел не может быть найден в кольце хэширования, обычно в качестве выбранной точки используется первое значение хеш-функции в кольце хэширования, то есть выполняется второй раунд поиска по часовой стрелке.
Преимущества: хорошая отказоустойчивость и масштабируемость, узлы добавляются или удаляются, мигрировать нужно лишь небольшое количество данных
Недостатки: без решения проблемы хотспота некоторым узлам потребуется обрабатывать большое количество запросов.
Суммировать
Балансировка нагрузки, цель которой состоит в том, чтобы позволить каждому серверу получить нагрузку, подходящую для его собственных вычислительных мощностей.
Может быть реализован в аппаратном и программном обеспечении
Несколько распространенных алгоритмов балансировки нагрузки имеют свои преимущества и недостатки, выбирайте разные сценарии для использования
обо мне
Этот обмен здесь первым, пожалуйста, не стесняйтесь указывать на различные ошибки и недостатки, и добро пожаловать, чтобы следовать за мной, чтобы обменяться более техническим контентом.