алгоритм балансировки нагрузки
Описание алгоритма балансировки нагрузки
- Введение в балансировку нагрузки
- Балансировка нагрузки, английское название Load Balance, относится к набору серверов, состоящему из нескольких симметрично расположенных серверов.Каждый сервер имеет эквивалентный статус и может предоставлять услуги независимо, без помощи других серверов.
- Благодаря определенной технологии распределения нагрузки запросы, отправленные извне, равномерно распределяются на сервер в симметричной структуре, а сервер, получивший запрос, самостоятельно отвечает на запрос клиента.
- Балансировка нагрузки позволяет равномерно распределять клиентские запросы к массиву серверов, тем самым обеспечивая быстрый доступ к важным данным и решая проблему большого количества одновременных сервисов доступа.Эта технология кластеризации позволяет достичь производительности, близкой к мейнфреймам, при минимальных вложениях.
- метод балансировки нагрузки
загрузка программного обеспеченияиаппаратная нагрузка
- Балансировка нагрузки программного обеспечения
- Распространенное программное обеспечение для балансировки нагрузки: nginx, LVS, HAproxy.
- материал:
Преимущества и недостатки этих трех программных балансировщиков нагрузки:www.ha97.com/5646.htmlСравнение этих трех программных балансировщиков нагрузки:Woohoo.21Operations.com/archives/58…
- аппаратная балансировка нагрузки
- Обычное оборудование для балансировки нагрузки: Array, F5
- алгоритм балансировки нагрузки
Случайный алгоритм, циклический взвешенный алгоритм, согласованный хэш, алгоритм минимального активного числа
Моделирование алгоритма балансировки нагрузки
- поддержка данных
(1) Случайный алгоритм
1. Простой случайный алгоритм
Этот простой случайный алгоритм используется, когда производительность машины аналогична производительности ежедневной машины. Фактически, некоторые машины в производстве могут иметь более высокую производительность. Он может обрабатывать больше случаев, поэтому мы можем установить вес для каждого сервера.
2. Взвешенный случайный алгоритм - V1
Идея этой версии V1 взвешенного случайного алгоритма относительно проста, и каждый сервер воспроизводится в соответствии со своим соответствующим весом. Этот метод реализации потребляет больше памяти, когда сумма весов особенно велика, потому что IP-адрес необходимо скопировать.Чем больше сумма весов, тем больше памяти требуется для указанных выше ips.
3. Взвешенный случайный алгоритм - V2
Далее представлена еще одна идея реализации. Предположим, есть набор серверов server=[A, B, C], соответствующие веса weights=[5, 3, 2], сумма весов равна 10. (1) Теперь разместите эти веса на одномерных координатах, тогда будет интервал [0, 5], принадлежащий серверу A, интервал [5, 8], принадлежащий серверу B, и интервал [8, 10], принадлежащий серверу C. . (2) Затем сгенерируйте случайное число в диапазоне [0, 10] с помощью случайных чисел, а затем вычислите, на какой интервал попадает случайное число.
(2) Алгоритм опроса
1. Простой алгоритм опроса
Этот простой алгоритм опроса очень справедлив: каждый сервер обслуживает по очереди, но некоторые машины имеют хорошую производительность, поэтомуСпособные люди должны больше работать, то же, что и случайный алгоритм, поэтому мы можем установить вес для каждого сервера.
2. Алгоритм взвешенного опроса
Алгоритм взвешенного кругового перебора: Мысль:
- Например, есть серверы=[A,B,C], соответствующие веса=[2,5,1], а общий вес равен 8.
- Мы можем понять, что есть 8 серверов, 2 A, 5 B и 1 C. Когда звонок сделан, его нужно
- Для последовательного доступа, если есть 10 вызовов, порядок вызовов будет AABBBBBCAA.
шаг:
- Т.к. кол-во звонков будет становиться все больше и больше, а сервер исправлен, то необходимо "ужать" кол-во звонков и взять остаток
- Выровняйте значения веса по одномерным значениям координат: [0,2] — это A, [2,7] — это B, [7,8] — это C
- Далее, это первый раз, чтобы получить запрос.Необходимо выполнить операцию остатка над общим весом, чтобы получить смещение.
У этого алгоритма есть недостаток: когда сервер имеет особенно большой вес, ему необходимо непрерывно обрабатывать запросы, но на самом деле мы хотим добиться эффекта, что на 100 запросов, пока имеется 100*8/50=16 запросов Достаточно, эти 16 раз не должны быть доступны постоянно.Например, предположим, что у нас есть три сервера server=[A,B,C], соответствующие веса=[2,5,1], общий вес равен 7, то приведенный выше Результат алгоритма АААААВС, тогда что, если может быть такой результат: ААБАСАА, вставка В и С в середину 5 А в среднем, это более сбалансировано.
3. Гладкий взвешенный алгоритм опроса
Затем это приводит кгладкий взвешенный круговой алгоритмИдеи:
- Каждому серверу соответствует два веса: weight и currentWeight. Вес фиксирован, currentWeight динамически корректируется, а начальное значение равно 0.
- Когда приходит новый запрос, пройдитесь по списку серверов, добавьте его currentWeight к его собственному весу и найдите наибольший currentWeight после завершения обхода.
- И вычесть максимальный currentWeight из суммы весов, а затем вернуться на соответствующий сервер.
Предполагать: Данные испытаний:
WEIGHT_LIST.put("A", 5); WEIGHT_LIST.put("B", 1); WEIGHT_LIST.put("C", 1);
Процесс операции выглядит следующим образом:
| частота | текущий массив currentWeight (currentWeight+=вес) | Выберите максимальный результат (currentWeight) | массив currentWeight после вычитания суммы весов (max(currentWeight)-=sum(weight)) |
|---|---|---|---|
| 1 | [5,1,1] | A | [-2,1,1] |
| 2 | [3,2,2] | A | [-4,2,2] |
| 3 | [1,3,3] | B | [1,-4,3] |
| 4 | [6,-3,4] | A | [-1,-3,4] |
| 5 | [4,-2,5] | C | [4,-2,-2] |
| 6 | [9,-1,-1] | A | [2,-1,-1] |
| 7 | [7,0,0] | A | [0,0,0] |
| 8 | [5,1,1] | A | [-2,1,1] |
Как показано в таблице, после обработки гладкой линии полученная серверная последовательность имеет вид [A, A, B, A, C, A, A] по сравнению с предыдущей последовательностью [A, A, A, A, A, B, C], распределение лучше. В начальном случае currentWeight=[0, 0, 0], а после обработки седьмого запроса currentWeight снова меняется на [0, 0, 0]. Вы будете удивлены, обнаружив, что на восьмой раз текущий массив currentWeight снова изменится на [5,1,1]!!!
- Конкретная реализация кода выглядит следующим образом:
(3) Последовательный алгоритм хеширования
Когда кластер серверов получает вызов запроса, он может хэшировать запрошенную информацию, такую как IP-адрес клиента или путь и параметры запроса, для получения хеш-значения, которое характеризуется тем же IP-адресом или запросом. путь и параметр запроса одинаковы.Пока можно добавить алгоритм для сопоставления хеш-значения с IP-адресом сервера, один и тот же запрос может быть отправлен на тот же сервер.
Поскольку ситуация запроса, инициированная клиентом, бесконечна, значение хеша также бесконечно, поэтому невозможно сопоставить все значения хеша с ip сервера, поэтому здесь необходимо кольцо хеширования. Как показано ниже:
Вышеописанная ситуация относительно однородна, если сервер ip4 не работает, то будет так:
Вы обнаружите, что прямой диапазон между ip3 и ip1 относительно велик, и на ip1 будет приходиться больше запросов, что несправедливо.Чтобы решить эту проблему, вам нужно добавить виртуальные узлы:
Среди них ip2-1 и ip3-1 — это виртуальные узлы, которые не могут обрабатывать узлы, но эквивалентны соответствующим серверам ip2 и ip3. На самом деле это просто способ борьбы с этим дисбалансом.На самом деле, даже если само кольцо хеширования сбалансировано, вы можете добавить больше виртуальных узлов, чтобы сделать кольцо более сбалансированным, например:
Это цветовое кольцо также справедливо, и только ip1, ip2, ip3, ip4 являются реальными ips сервера, а остальные — виртуальными ips. Так как же нам этого достичь?
- Для нашего IP-адреса сервера мы должны знать, сколько их, и сколько виртуальных узлов нам нужно, также находится под нашим контролем.Чем больше виртуальных узлов, тем более сбалансирован трафик.Кроме того, алгоритм хеширования также очень критичен. Чем больше хеш-алгоритм хэширует трафик, тем больше будет сбалансированность.
- Такое кольцо можно хранить в TreeMap; когда приходит запрос, получить хеш-значение запроса и получить поддерево больше хеш-значения из TreeMap в соответствии с хеш-значением.
- Из полученного поддерева взять первый элемент.
- Конкретная реализация кода:
(4) Алгоритм минимального активного числа
Перед несколькими методами основная цель состоит в том, чтобы сделать количество обращений к назначенному серверу, чтобы попытаться сбалансировать, но на самом деле это так? При том же количестве звонков, балансировку серверной нагрузки делать? Конечно нет, здесь также учитывается время каждого вызова и минимальное количество активных алгоритмов для решения этой задачи.
Чем меньше количество активных вызовов, тем эффективнее работает поставщик услуг и больше запросов может быть обработано в единицу времени. В это время запрос должен быть назначен этому серверу в приоритете
поставщик услуг. В конкретной реализации каждому поставщику услуг соответствует активный номер. Первоначально активное количество всех поставщиков услуг равно 0. Каждый Когда запрос получен, активный счетчик увеличивается на 1, а после завершения запроса активный счетчик уменьшается на 1. После того, как служба работает в течение определенного периода времени, поставщик услуг с хорошей производительностью обрабатывает запрос. Скорость запросов выше, поэтому активное количество уменьшается быстрее.В это время такой поставщик услуг может преимущественно получать новые запросы на обслуживание, что является минимальным Основная идея алгоритма активной балансировки нагрузки. В дополнение к минимальному активному числу реализация алгоритма минимального активного числа также вводит значение веса. так что будь точен При этом алгоритм минимального активного числа реализован на основе взвешенного алгоритма минимального активного числа. Например, в кластере поставщиков услуг есть два Отличный поставщик услуг. В определенное время их активное количество одинаково, и запросы будут распределяться в соответствии с их весами, чем больше вес, тем больше Чем выше вероятность новых запросов. Если два поставщика услуг имеют одинаковый вес, в это время один из них может быть выбран случайным образом.
выполнить:
Поскольку активный номер должен быть скоординирован логикой обработки запроса сервера, активный номер +1 в начале вызова и активный номер -1 в конце, так что вот Эта часть логики не моделируется, и карта используется непосредственно для моделирования.
- Конкретная реализация кода:
//最小活跃算法
public class LeastActive {
private static String getServer() {
//找出当前活跃数最小的服务器
Optional<Integer> minValue = ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
if (minValue.isPresent()) {
List<String> minActivityIps = new ArrayList<>();
ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
if (activity.equals(minValue.get())) {
minActivityIps.add(ip);
}
});
//最小活跃数的ip有多个，则根据权重来选，权重大的优先
if (minActivityIps.size() > 1) {
//过滤出对应的ip和权重
Map<String, Integer> weightList = new LinkedHashMap<>();
ServerIps.WEIGHT_LIST.forEach((ip, weight) -> {
if (minActivityIps.contains(ip)) {
weightList.put(ip, ServerIps.WEIGHT_LIST.get(ip));
}
});
int totalWeight = 0;
boolean sameWeight = true;
Object[] weights = weightList.values().toArray();
//计算出总的权重，判断所有权重是否一样
for (int i = 0; i < weights.length; i++) {
Integer weight = (Integer) weights[i];
totalWeight += weight;
if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
sameWeight = false;
}
}
//生成一个在[0,totalWeight]区间内的随机数
java.util.Random random = new java.util.Random();
int randomPos = random.nextInt(totalWeight);
if (!sameWeight) {
for (String ip : weightList.keySet()) {
Integer weight = weightList.get(ip);
if (randomPos < weight) {
return ip;
}
randomPos = randomPos - weight;
}
}
//如果所有权重都一样，就使用随机算法
randomPos = random.nextInt(weightList.size());
return (String) weightList.keySet().toArray()[randomPos];
} else {
return minActivityIps.get(0);
}
} else {
java.util.Random random = new java.util.Random();
int randomPos = random.nextInt(ServerIps.WEIGHT_LIST.size());
return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[randomPos];
}
}
public static void main(String[] args) {
for (int i=0; i<10; i++){
System.out.println(getServer());
}
}
}
Сводка по балансировке нагрузки:
- Использованная литература:Хироши Ватанабэ.apache.org/this-capable/docs/…