Введение в балансировку нагрузки
1.1. Проблемы, с которыми сталкиваются крупные веб-сайты
Крупным веб-сайтам приходится сталкиваться с проблемами огромного количества пользователей, высокой параллельности и больших объемов данных. Чтобы улучшить общую производительность системы, можно использовать вертикальное и горизонтальное расширение.
Вертикальное расширение: на ранней стадии разработки веб-сайта вычислительная мощность сервера может быть улучшена с автономной точки зрения за счет увеличения аппаратной вычислительной мощности, такой как вычислительная мощность ЦП, объем памяти и диск. Тем не менее, у одной машины есть узкое место в производительности, и как только это узкое место будет достигнуто, если вы захотите улучшить его, стоимость и цена будут чрезвычайно высоки. Это, очевидно, не может решить проблемы крупномасштабных распределенных систем (веб-сайтов), таких как большой трафик, высокая степень параллелизма и большие объемы данных.
Горизонтальное расширение: разделяйте трафик крупных веб-сайтов через кластеры. Серверы приложений (узлы) в кластере обычно проектируются без сохранения состояния, и пользователи могут запрашивать любой узел, и эти узлы вместе разделяют давление доступа. Горизонтальное масштабирование имеет два основных момента:
-
Кластер приложений: разверните одно и то же приложение на нескольких компьютерах, чтобы сформировать кластер обработки, получать запросы, распределяемые устройствами балансировки нагрузки, обрабатывать их и возвращать соответствующие данные.
-
Балансировка нагрузки: Распределяйте запросы доступа пользователей к узлам в кластере по определенному алгоритму.
1.2 Что такое балансировка нагрузки
Балансировка нагрузки (LB) – это незаменимый ключевой компонент системы с высокой степенью параллелизма и высокой доступностью. Цель состоит в том, чтобы попытаться равномерно распределить сетевой трафик на несколько серверов, чтобы улучшить общую скорость отклика и доступность системы.
Основные функции балансировки нагрузки следующие:
Высокий параллелизм: Балансировка нагрузки регулирует нагрузку с помощью алгоритма и пытается равномерно распределить рабочую нагрузку каждого узла в кластере приложений, тем самым улучшая возможности параллельной обработки (пропускную способность) кластера приложений.
Масштабируемость: добавьте или уменьшите количество серверов, а затем распределите управление с помощью балансировки нагрузки. Это делает кластеры приложений масштабируемыми.
Высокая доступность: Балансировщик нагрузки может отслеживать серверы-кандидаты, и когда сервер недоступен, он автоматически пропускает и распределяет запрос на доступные серверы. Это делает кластер приложений высокодоступным.
Безопасность: Некоторое программное или аппаратное обеспечение балансировки нагрузки обеспечивает функции безопасности, такие как: обработка черного и белого списков, брандмауэр, защита от DDos-атак и т. д.
Во-вторых, классификация балансировки нагрузки
Существует множество технологий, поддерживающих балансировку нагрузки, и мы можем классифицировать их по разным параметрам.
2.1 Классификация размеров носителя
С точки зрения операторов, поддерживающих балансировку нагрузки, балансировку нагрузки можно разделить на две категории:Аппаратная балансировка нагрузки, программная балансировка нагрузки
2.1.1 Аппаратная балансировка нагрузки
Аппаратная балансировка нагрузки, как правило, независимый сервер балансировки нагрузки, работающий на специальном процессоре, является дорогостоящим и доступным только местным тиранам. Основные продукты аппаратной балансировки нагрузки: F5 и A10.
Преимущества аппаратной балансировки нагрузки:
-
Мощные функции: поддержка глобальной балансировки нагрузки и предоставление более полных и сложных алгоритмов балансировки нагрузки.
-
Высокая производительность: поскольку аппаратная балансировка нагрузки работает на выделенных процессорах, она имеет большую пропускную способность и может поддерживать более миллиона одновременных операций на одной машине.
-
Высокая безопасность: он часто имеет функции безопасности, такие как брандмауэр и защита от DDoS-атак.
Недостатки аппаратной балансировки нагрузки:
-
Дорого. Покупка и обслуживание аппаратной балансировки нагрузки обходится дорого.
-
Плохая масштабируемость: когда объем доступа внезапно увеличивается, емкость не может быть динамически расширена сверх установленного предела.
2.1.2 Балансировка нагрузки программного обеспечения
Программная балансировка нагрузки является наиболее широко используемой и может использоваться как крупными, так и небольшими компаниями.
Программная балансировка нагрузки реализует балансировку нагрузки на программном уровне и обычно может работать на любом стандартном физическом устройстве.
Основные продукты балансировки нагрузки программного обеспечения:Nginx, HAProxy, LVS.
-
LVS может действовать как балансировщик нагрузки уровня 4. Его производительность балансировки нагрузки лучше, чем у Nginx.
-
HAProxy может действовать как балансировщик нагрузки HTTP и TCP.
-
Nginx, HAProxy могут действовать как балансировщик нагрузки уровня 4 или уровня 7.
Преимущества программной балансировки нагрузки:
-
Хорошая масштабируемость: адаптируйтесь к динамическим изменениям и можете динамически расширяться за пределы исходной емкости, добавляя экземпляры программной балансировки нагрузки.
-
Низкая стоимость: программная балансировка нагрузки может работать на любом стандартном физическом устройстве, что снижает стоимость покупки и эксплуатации.
Недостатки программной балансировки нагрузки:
- Немного хуже производительность: по сравнению с аппаратной балансировкой нагрузки производительность программной балансировки нагрузки немного ниже.
2.2 Классификация сетевых коммуникаций
С точки зрения связи балансировка нагрузки программного обеспечения может быть разделена на четыре уровня и семь уровней балансировки нагрузки.
1) Балансировка нагрузки уровня 7: это пересылка запроса на определенный хост в соответствии с заголовком HTTP-запроса и информацией URL-адреса запрашивающего пользователя.
-
перенаправление DNS
-
HTTP-перенаправление
-
обратный прокси
2) Балансировка нагрузки уровня 4: переадресация запросов на основе IP-адреса и порта.
-
Изменить IP-адрес
-
Изменить MAC-адрес
2.2.1 Балансировка нагрузки DNS
Балансировка нагрузки DNS обычно используется в интернет-компаниях, а сложные бизнес-системы не подходят для использования. Крупные веб-сайты обычно используют балансировку нагрузки DNS в качестве метода балансировки нагрузки первого уровня, а затем используют другие внутренние методы для балансировки нагрузки второго уровня. Балансировка нагрузки DNS — это балансировка нагрузки уровня 7.
DNS — это служба разрешения доменных имен, представляющая собой сетевой протокол OSI Layer 7. DNS спроектирован как распределенное приложение с древовидной структурой, сверху вниз: корневой сервер доменных имен, сервер доменных имен первого уровня, сервер доменных имен второго уровня, ..., локальный сервер доменных имен. Очевидно, что если все данные хранятся на корневых серверах имен, нагрузка и накладные расходы на поиск в DNS могут быть огромными.
Таким образом, DNS-запрос является обратным рекурсивным процессом относительно иерархии DNS.DNS-клиент последовательно запрашивает локальный DNS-сервер, DNS-сервер верхнего уровня, DNS-сервер верхнего уровня, ..., корневой DNS-сервер (также известный как как авторитетный DNS-сервер) DNS-сервер), после попадания немедленно возвращайтесь. Чтобы уменьшить количество запросов, каждый уровень DNS-сервера будет настраивать кеш DNS-запросов.
Принцип работы балансировки нагрузки DNS: на основе кеша DNS-запросов возвращаются IP-адреса разных серверов в зависимости от ситуации с нагрузкой.
Преимущества перенаправления DNS:
Простота в использовании: работа по балансировке нагрузки выполняется DNS-сервером, что избавляет от необходимости поддерживать сервер балансировки нагрузки.
Повышение производительности: он может поддерживать разрешение доменных имен на основе адресов и разрешение на адрес сервера, ближайший к пользователю (по принципу CDN), что может ускорить доступ и повысить производительность;
Недостатки перенаправления DNS:
Плохое удобство использования: разрешение DNS является многоуровневым, после добавления/изменения DNS время разрешения долгое, в процессе разрешения пользователи не смогут получить доступ к веб-сайту;
Низкая масштабируемость: управление балансировкой нагрузки DNS лежит на провайдере доменных имен, и его невозможно улучшить и расширить;
Плохая ремонтопригодность: не может отражать текущее состояние работы сервера, поддерживает мало алгоритмов, не может различать серверы (о нагрузке нельзя судить по состоянию системы и сервиса).
2.2.2 Балансировка нагрузки HTTP
Балансировка нагрузки HTTP реализована на основе перенаправления HTTP. Балансировка нагрузки HTTP — это семиуровневая балансировка нагрузки.
Принцип перенаправления HTTP заключается в том, чтобы вычислить реальный адрес сервера в соответствии с HTTP-запросом пользователя, записать адрес сервера в ответ перенаправления HTTP и вернуть его в браузер для повторного доступа.
Преимущества перенаправления HTTP: Схема проста.
Недостатки HTTP-перенаправления:
Низкая производительность: для каждого доступа требуется два запроса к серверу, что увеличивает задержку доступа.
Более низкий рейтинг в поиске: когда используются перенаправления, поисковые системы видят мошенничество SEO.
Если балансировщик нагрузки выйдет из строя, доступ к сайту будет невозможен.
Из-за очевидных недостатков эта стратегия балансировки нагрузки редко используется на практике.
2.2.3 Балансировка нагрузки обратного прокси-сервера
Обратный прокси-сервер означает, что прокси-сервер принимает сетевые запросы, затем перенаправляет запрос на сервер в интрасети и возвращает результат, полученный от сервера в интрасети, клиенту сетевого запроса. Балансировка нагрузки обратного прокси относится к балансировке нагрузки уровня 7.
Основные продукты обратных прокси-сервисов:Нгинкс, Апач.
В чем разница между прямым прокси и обратным прокси?
Прямой прокси: происходит на стороне клиента и инициируется пользователем. Программное обеспечение для обхода — это типичный прямой прокси.Клиент активно обращается к прокси-серверу, чтобы позволить прокси-серверу получить необходимые данные из внешней сети, а затем переслать их обратно клиенту.
Обратный прокси: происходит на стороне сервера, пользователь не знает о существовании прокси.
Как обратный прокси-сервер обеспечивает балансировку нагрузки? Возьмите Nginx в качестве примера следующим образом:
Сначала установите правила балансировки нагрузки на прокси-сервере. Затем, когда клиентский запрос получен, обратный прокси-сервер перехватывает указанное доменное имя или IP-запрос и распределяет запрос по серверам-кандидатам в соответствии с алгоритмом балансировки нагрузки. Во-вторых, если сервер-кандидат выйдет из строя, обратный прокси-сервер будет иметь отказоустойчивую обработку, например, если запрос на раздачу терпит неудачу более 3 раз, запрос будет распространяться на другие серверы-кандидаты.
Преимущества обратного прокси:
Несколько алгоритмов балансировки нагрузки: поддержка нескольких алгоритмов балансировки нагрузки для удовлетворения потребностей различных сценариев.
Сервер можно отслеживать: на основе протокола HTTP можно отслеживать состояние сервера пересылки, например: загрузку системы, время отклика, доступность, количество подключений, трафик и т. д., чтобы настроить стратегию балансировки нагрузки в соответствии с к этим данным.
Недостатки обратного прокси:
- Дополнительные накладные расходы на пересылку: операция переадресации самого обратного прокси-сервера имеет накладные расходы на производительность, которые могут включать такие операции, как создание соединения, ожидание ответа на соединение и анализ результата ответа.
- Увеличение сложности системы: Обратный прокси-сервер часто используется для горизонтального расширения распределенных приложений, но служба обратного прокси-сервера имеет следующие проблемы.Для решения следующих проблем она увеличит общую сложность и затраты на эксплуатацию и обслуживание системы:
-
Если служба обратного прокси-сервера не работает, она не сможет получить доступ к сайту, поэтому ей требуется решение с высокой доступностью.Обычные решения: активный-резервный режим (один главный и один резервный) и двойной активный режим (взаимно активные и в режиме ожидания).
-
Сама служба обратного прокси-сервера также имеет узкие места в производительности, поскольку количество пересылаемых запросов продолжает расти, поэтому требуется масштабируемое решение.
2.2.4 Балансировка IP-нагрузки
Балансировка нагрузки IP предназначена для выполнения балансировки нагрузки на сетевом уровне путем изменения адреса назначения запроса.
Как показано на рисунке выше, процесс выравнивания IP примерно выглядит следующим образом:
Клиент запрашивает 192.168.137.10, и сервер балансировки нагрузки получает пакет.
Сервер балансировки нагрузки выбирает сервисный узел 192.168.0.1 в соответствии с алгоритмом, а затем меняет адрес запроса пакета на IP узла.
Реальный сервисный узел получает сообщение запроса, обрабатывает его и возвращает данные ответа на сервер балансировки нагрузки.
Сервер балансировки нагрузки изменяет исходный адрес данных ответа на адрес сервера балансировки нагрузки и возвращает его клиенту.
Балансировка нагрузки IP завершает распределение данных в процессе ядра и имеет лучшую производительность подчиненной обработки, чем балансировка нагрузки обратного прокси-сервера. Однако, поскольку все ответы на запросы проходят через сервер балансировки нагрузки, пропускная способность кластера ограничивается пропускной способностью сервера балансировки нагрузки.
2.2.5 Балансировка нагрузки на уровне канала передачи данных
Балансировка нагрузки на канальном уровне относится к изменению MAC-адреса на канальном уровне протокола связи для выполнения балансировки нагрузки.
Лучшим продуктом с открытым исходным кодом для балансировки нагрузки канального уровня на платформе Linux является LVS (Linux Virtual Server). LVS — это система балансировки нагрузки, основанная на структуре netfilter в ядре Linux. Netfilter — это механизм брандмауэра Linux в режиме ядра, который может устанавливать несколько уровней (функций ловушек) в соответствии с правилами для выполнения связанных операций во время потока пакетов.
Рабочий процесс LVS примерно следующий:
когда пользователь получает доступwww.sina.com.cnКогда пользовательские данные проходят через послойную сеть, они наконец попадают на сетевую карту сервера LVS через коммутатор и попадают на сетевой уровень ядра.
После ввода PREROUTING после поиска маршрутизации определяется, что целевой VIP посещения является локальным IP-адресом, поэтому пакет данных попадает в цепочку INPUT.
IPVS работает в цепочке INPUT и будет доступен в соответствии сvip+portОпределите, является ли запрос услугой IPVS, и если да, вызовите зарегистрированную функцию IPVS HOOK, чтобы выполнить основной процесс, связанный с IPVS, принудительно изменить соответствующие данные пакета данных и отправить пакет данных в цепочку POSTROUTING.
После получения пакета данных в POSTROUTING в соответствии с целевым IP-адресом (внутренний сервер) пакет данных, наконец, отправляется на внутренний сервер посредством маршрутизации.
Версия LVS с открытым исходным кодом имеет рабочие режимы 3. Каждый режим имеет совершенно другой принцип работы. Говорят, что каждый режим имеет свои преимущества и недостатки и подходит для различных сценариев применения. Однако конечной важной функцией является достижение сбалансированного планирование трафика и хорошая масштабируемость. В основном он включает три режима: режим DR, режим NAT и режим туннеля.
3. Алгоритм балансировки нагрузки
Реализация балансировщика нагрузки может быть разделена на две части:
Выберите сервер из списка серверов-кандидатов в соответствии с алгоритмом балансировки нагрузки;
Отправить данные запроса на этот сервер.
Алгоритм балансировки нагрузки является ядром ядра службы балансировки нагрузки. Существуют различные продукты балансировки нагрузки, но принципы различных алгоритмов балансировки нагрузки являются общими. Существует много видов алгоритмов балансировки нагрузки, которые подходят для разных сценариев применения.В этой статье представлены только характеристики и принципы наиболее распространенных алгоритмов балансировки нагрузки:Опрос, Случайный выбор, Минимальное активное число, Хэш исходного адреса, Постоянный хэш.
Примечание: Реализация алгоритма балансировки нагрузки, рекомендуемая литератураОписание официального алгоритма балансировки нагрузки Dubbo, исходный код очень подробный и заслуживает изучения.
3.1 Случайный
3.1.1 Случайный алгоритм
СлучайныйАлгоритм случайным образом распределяет запросы по серверам-кандидатам.
Случайный алгоритм подходит для сценариев с одинаковым серверным оборудованием. Любой, кто изучал теорию вероятностей, знает, что при небольшом количестве звонков нагрузка может быть неравномерной, и чем больше количество звонков, тем более сбалансированной является нагрузка.
[Пример] Пример реализации случайного алгоритма
интерфейс балансировки нагрузки
public interface LoadBalance<N extends Node> {
N select(List<N> nodes, String ip);
}
абстрактный класс балансировки нагрузки
public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> {
@Override
public N select(List<N> nodes, String ip) {
if (CollectionUtil.isEmpty(nodes)) {
return null;
}
// 如果 nodes 列表中仅有一个 node，直接返回即可，无需进行负载均衡
if (nodes.size() == 1) {
return nodes.get(0);
}
return doSelect(nodes, ip);
}
protected abstract N doSelect(List<N> nodes, String ip);
}
класс узла сервера
public class Node implements Comparable<Node> {
protected String url;
protected Integer weight;
protected Integer active;
// ...
}
Случайная реализация алгоритма
public class RandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = new Random();
@Override
protected N doSelect(List<N> nodes, String ip) {
// 在列表中随机选取一个节点
int index = random.nextInt(nodes.size());
return nodes.get(index);
}
}
3.1.2 Взвешенный случайный алгоритм
Взвешенное случайное) основан на случайном алгоритме, корректирует веса в соответствии с вероятностью и выполняет распределение нагрузки.
[Пример] Пример реализации взвешенного случайного алгоритма
public class WeightRandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = ThreadLocalRandom.current();
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
AtomicInteger totalWeight = new AtomicInteger(0);
for (N node : nodes) {
Integer weight = node.getWeight();
totalWeight.getAndAdd(weight);
}
if (totalWeight.get() > 0) {
int offset = random.nextInt(totalWeight.get());
for (N node : nodes) {
// 让随机值 offset 减去权重值
offset -= node.getWeight();
if (offset < 0) {
// 返回相应的 Node
return node;
}
}
}
// 直接随机返回一个
return nodes.get(random.nextInt(length));
}
}
3.2 Опрос
3.2.1 Алгоритм опроса
Стратегия алгоритма **Round Robin** заключается в том, чтобы по очереди распределять запросы на серверы-кандидаты.
Как показано на рисунке ниже, балансировщик нагрузки получает 6 запросов от клиента, запрос (1, 3, 5) будет отправлен на сервер 1, а запрос (2, 4, 6) будет отправлен на сервер. 2.
Этот алгоритм подходит для сценариев: возможности обработки каждого сервера схожи, а нагрузка на каждую транзакцию не сильно отличается. Если есть большое несоответствие, то более медленный сервер может иметь невыполненные запросы и в конечном итоге не сможет справиться с чрезмерной нагрузкой.
[Пример] Пример алгоритма опроса
Реализация циклического алгоритма балансировки нагрузки
public class RoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final AtomicInteger position = new AtomicInteger(0);
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
// 如果位置值已经等于节点数，重置为 0
position.compareAndSet(length, 0);
N node = nodes.get(position.get());
position.getAndIncrement();
return node;
}
}
3.2.2 Алгоритм взвешенного кругового перебора
Алгоритм **Weighted Round Robbin** основан на алгоритме циклического перебора, добавляя атрибут веса для корректировки количества запросов к серверу пересылки. Узлы с высокой производительностью и высокой скоростью обработки должны устанавливать более высокие веса, чтобы запросы преимущественно распределялись на узлы с более высокими весами.
Как показано на рисунке ниже, сервер A устанавливает вес равным 5, сервер B устанавливает вес равным 1, а балансировщик нагрузки получает 6 запросов от клиента, тогда запрос (1, 2, 3, 4, 5) будет отправлен на сервер A , (6) Запрос будет отправлен на сервер B.
[Пример] Пример реализации взвешенного циклического алгоритма
Следующая реализация делает некоторые упрощения, основанные на взвешенном циклическом алгоритме Даббо.
public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
/**
* 60秒
*/
private static final int RECYCLE_PERIOD = 60000;
/**
* Node hashcode 到 WeightedRoundRobin 的映射关系
*/
private ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>();
/**
* 原子更新锁
*/
private AtomicBoolean updateLock = new AtomicBoolean();
@Override
protected N doSelect(List<N> nodes, String ip) {
int totalWeight = 0;
long maxCurrent = Long.MIN_VALUE;
// 获取当前时间
long now = System.currentTimeMillis();
N selectedNode = null;
WeightedRoundRobin selectedWRR = null;
// 下面这个循环主要做了这样几件事情：
// 1. 遍历 Node 列表，检测当前 Node 是否有相应的 WeightedRoundRobin，没有则创建
// 2. 检测 Node 权重是否发生了变化，若变化了，则更新 WeightedRoundRobin 的 weight 字段
// 3. 让 current 字段加上自身权重，等价于 current += weight
// 4. 设置 lastUpdate 字段，即 lastUpdate = now
// 5. 寻找具有最大 current 的 Node，以及 Node 对应的 WeightedRoundRobin，
// 暂存起来，留作后用
// 6. 计算权重总和
for (N node : nodes) {
int hashCode = node.hashCode();
WeightedRoundRobin weightedRoundRobin = weightMap.get(hashCode);
int weight = node.getWeight();
if (weight < 0) {
weight = 0;
}
// 检测当前 Node 是否有对应的 WeightedRoundRobin，没有则创建
if (weightedRoundRobin == null) {
weightedRoundRobin = new WeightedRoundRobin();
// 设置 Node 权重
weightedRoundRobin.setWeight(weight);
// 存储 url 唯一标识 identifyString 到 weightedRoundRobin 的映射关系
weightMap.putIfAbsent(hashCode, weightedRoundRobin);
weightedRoundRobin = weightMap.get(hashCode);
}
// Node 权重不等于 WeightedRoundRobin 中保存的权重，说明权重变化了，此时进行更新
if (weight != weightedRoundRobin.getWeight()) {
weightedRoundRobin.setWeight(weight);
}
// 让 current 加上自身权重，等价于 current += weight
long current = weightedRoundRobin.increaseCurrent();
// 设置 lastUpdate，表示近期更新过
weightedRoundRobin.setLastUpdate(now);
// 找出最大的 current
if (current > maxCurrent) {
maxCurrent = current;
// 将具有最大 current 权重的 Node 赋值给 selectedNode
selectedNode = node;
// 将 Node 对应的 weightedRoundRobin 赋值给 selectedWRR，留作后用
selectedWRR = weightedRoundRobin;
}
// 计算权重总和
totalWeight += weight;
}
// 对 weightMap 进行检查，过滤掉长时间未被更新的节点。
// 该节点可能挂了，nodes 中不包含该节点，所以该节点的 lastUpdate 长时间无法被更新。
// 若未更新时长超过阈值后，就会被移除掉，默认阈值为60秒。
if (!updateLock.get() && nodes.size() != weightMap.size()) {
if (updateLock.compareAndSet(false, true)) {
try {
// 遍历修改，即移除过期记录
weightMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
} finally {
updateLock.set(false);
}
}
}
if (selectedNode != null) {
// 让 current 减去权重总和，等价于 current -= totalWeight
selectedWRR.decreaseCurrent(totalWeight);
// 返回具有最大 current 的 Node
return selectedNode;
}
// should not happen here
return nodes.get(0);
}
protected static class WeightedRoundRobin {
// 服务提供者权重
private int weight;
// 当前权重
private AtomicLong current = new AtomicLong(0);
// 最后一次更新时间
private long lastUpdate;
public long increaseCurrent() {
// current = current + weight；
return current.addAndGet(weight);
}
public long decreaseCurrent(int total) {
// current = current - total;
return current.addAndGet(-1 * total);
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
// 初始情况下，current = 0
current.set(0);
}
public AtomicLong getCurrent() {
return current;
}
public void setCurrent(AtomicLong current) {
this.current = current;
}
public long getLastUpdate() {
return lastUpdate;
}
public void setLastUpdate(long lastUpdate) {
this.lastUpdate = lastUpdate;
}
}
}
3.3 Минимальный активный номер
Минимальное активное количествоАлгоритм (наименее активный) распределяет запросы на сервер-кандидат с наименьшим количеством подключений/запросов (сервер, который в настоящее время обрабатывает наименьшее количество запросов).
-
Особенности: Динамическое распределение на основе текущего количества соединений, запрошенных сервером-кандидатом.
-
Сценарий: применимо к сценариям, чувствительным к нагрузке на систему или требующим большой разницы в продолжительности соединения.
Поскольку продолжительность подключения каждого запроса различна, при использовании простого циклического или случайного алгоритма текущее количество подключений к некоторым серверам может быть слишком большим, а количество подключений других серверов слишком маленьким, что приводит к тому, что нагрузка не быть действительно уравновешенным. Хотя опрос или алгоритмы могут выполнять регулировку нагрузки путем взвешивания атрибутов, метод взвешивания с трудом справляется с динамическими изменениями.
Например, на рисунке ниже запрос (1, 3, 5) будет отправлен на сервер 1, но (1, 3) вскоре будет отключен, в это время только (5) запросов на подключение к серверу 1; ( 2, 4, 6)) запрос отправляется на сервер 2 и только (2) отключается. Пока система продолжает работать, Сервер 2 будет находиться под чрезмерной нагрузкой.
Алгоритм минимального активного числа записывает количество соединений, обрабатываемых каждым узлом-кандидатом в текущий момент, а затем выбирает узел с наименьшим количеством соединений. Эта стратегия может отражать текущее состояние сервера динамически и в режиме реального времени, а также разумно и равномерно распределять обязанности, что подходит для сценариев, чувствительных к текущей нагрузке системы.
Например, на рисунке ниже текущее количество соединений на сервере 1 наименьшее, поэтому новый запрос 6 будет отправлен на сервер 1.
Взвешенный минимальный активный номер(Взвешенное наименьшее соединение) На основе минимального активного числа каждому серверу присваивается вес в соответствии с производительностью сервера, а затем в соответствии с весом рассчитывается количество соединений, которые может обработать каждый сервер.
Ключевые моменты для реализации алгоритма минимального активного номера: Чем меньше количество активных вызовов, тем выше вычислительная мощность узла службы, тем больше запросов может быть обработано в единицу времени, и запросы должны быть распределены в службу в первую очередь. В конкретной реализации каждый служебный узел соответствует активному числу активных. Первоначально активное количество всех поставщиков услуг равно 0. Каждый раз при получении запроса активное число увеличивается на 1, а после завершения запроса активное число уменьшается на 1. После того, как служба работает в течение определенного периода времени, поставщики услуг с хорошей производительностью могут быстрее обрабатывать запросы, поэтому количество активных уменьшается быстрее.В это время такие поставщики услуг могут предпочтительно получать новые запросы на обслуживание, что является минимальным активным числом. , Основная идея алгоритма балансировки нагрузки.
[Пример] Реализация алгоритма минимального активного числа
Следующая реализация основана на алгоритме балансировки минимальной активной нагрузки Dubbo с некоторыми изменениями.
public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = new Random();
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
// 最小的活跃数
int leastActive = -1;
// 具有相同“最小活跃数”的服务者提供者（以下用 Node 代称）数量
int leastCount = 0;
// leastIndexs 用于记录具有相同“最小活跃数”的 Node 在 nodes 列表中的下标信息
int[] leastIndexs = new int[length];
int totalWeight = 0;
// 第一个最小活跃数的 Node 权重值，用于与其他具有相同最小活跃数的 Node 的权重进行对比，
// 以检测是否“所有具有相同最小活跃数的 Node 的权重”均相等
int firstWeight = 0;
boolean sameWeight = true;
// 遍历 nodes 列表
for (int i = 0; i < length; i++) {
N node = nodes.get(i);
// 发现更小的活跃数，重新开始
if (leastActive == -1 || node.getActive() < leastActive) {
// 使用当前活跃数更新最小活跃数 leastActive
leastActive = node.getActive();
// 更新 leastCount 为 1
leastCount = 1;
// 记录当前下标值到 leastIndexs 中
leastIndexs[0] = i;
totalWeight = node.getWeight();
firstWeight = node.getWeight();
sameWeight = true;
// 当前 Node 的活跃数 node.getActive() 与最小活跃数 leastActive 相同
} else if (node.getActive() == leastActive) {
// 在 leastIndexs 中记录下当前 Node 在 nodes 集合中的下标
leastIndexs[leastCount++] = i;
// 累加权重
totalWeight += node.getWeight();
// 检测当前 Node 的权重与 firstWeight 是否相等，
// 不相等则将 sameWeight 置为 false
if (sameWeight && i > 0
&& node.getWeight() != firstWeight) {
sameWeight = false;
}
}
}
// 当只有一个 Node 具有最小活跃数，此时直接返回该 Node 即可
if (leastCount == 1) {
return nodes.get(leastIndexs[0]);
}
// 有多个 Node 具有相同的最小活跃数，但它们之间的权重不同
if (!sameWeight && totalWeight > 0) {
// 随机生成一个 [0, totalWeight) 之间的数字
int offsetWeight = random.nextInt(totalWeight);
// 循环让随机数减去具有最小活跃数的 Node 的权重值，
// 当 offset 小于等于0时，返回相应的 Node
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
// 获取权重值，并让随机数减去权重值
offsetWeight -= nodes.get(leastIndex).getWeight();
if (offsetWeight <= 0) {
return nodes.get(leastIndex);
}
}
}
// 如果权重相同或权重为0时，随机返回一个 Node
return nodes.get(leastIndexs[random.nextInt(leastCount)]);
}
}
3.4 Хэш исходного адреса
хэш исходного адресаАлгоритм (IP Hash) В соответствии с IP-адресом источника запроса значение получается путем вычисления хеш-функции, и это значение используется для выполнения операции по модулю в списке серверов-кандидатов, а полученный результат является выбранным сервером.
Гарантируется, что запросы от клиентов с одним и тем же IP-адресом будут перенаправлены на один и тот же сервер для реализации закрепленных сеансов.
Особенности: убедитесь, что определенные пользователи всегда запрашивают один и тот же сервер, если сервер выйдет из строя, сеанс будет потерян.
[Пример] Пример реализации алгоритма хеширования исходного адреса
public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
@Override
protected N doSelect(List<N> nodes, String ip) {
if (StrUtil.isBlank(ip)) {
ip = "127.0.0.1";
}
int length = nodes.size();
int index = hash(ip) % length;
return nodes.get(index);
}
public int hash(String text) {
return HashUtil.fnvHash(text);
}
}
3.5 Непротиворечивое хеширование
Цель алгоритма Consistent Hash заключается в том, чтобы одни и те же запросы как можно чаще попадали на один и тот же сервер.
Согласованное хеширование может очень хорошо решить проблему стабильности.Все узлы хранения могут быть расположены на кольце Hash встык.После вычисления хэша каждый ключ найдет соседний узел хранения по часовой стрелке для хранения. Когда узел присоединяется или выходит, это влияет только на соседние по часовой стрелке последующие узлы узла в хеш-кольце.
1) Тот же запрос означает: обычно при использовании последовательного хеширования необходимо указать ключ для вычисления хэша, который может быть:
ID пользователя
IP запрашивающего
Имя службы запроса, строка, состоящая из списка параметров
2) Насколько это возможно означает, что сервер может отключаться и отключаться, а изменения нескольких серверов не должны влиять на большинство запросов.
Когда сервер-кандидат выходит из строя, запросы, первоначально отправленные на сервер, будут распространяться на другие серверы-кандидаты на основе виртуальных узлов и не вызовут радикальных изменений.
преимущество: добавление и удаление узлов влияет только на соседние по часовой стрелке узлы в хэш-кольце и не влияет на другие узлы.
недостаток: добавление и удаление узлов приведет к тому, что некоторые данные в хеш-кольце не попадут. При использовании небольшого количества узлов изменения узла будут влиять на отображение данных в кольце хеширования в большом диапазоне, что не подходит для распределенной схемы малого количества узлов данных. Обычные согласованные хэш-разделы должны удваивать или вычитать половину узлов, чтобы обеспечить баланс данных и нагрузки при добавлении или удалении узлов.
Уведомление: из-за этих недостатков последовательного разделения хэша некоторые распределенные системы используют виртуальные слоты для улучшения согласованного хеширования, например, система Dynamo.
[Пример] Пример согласованного алгоритма хеширования
public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
@SuppressWarnings("unchecked")
@Override
protected N doSelect(List<N> nodes, String ip) {
// 分片数，这里设为节点数的 4 倍
Integer replicaNum = nodes.size() * 4;
// 获取 nodes 原始的 hashcode
int identityHashCode = System.identityHashCode(nodes);
// 如果 nodes 是一个新的 List 对象，意味着节点数量发生了变化
// 此时 selector.identityHashCode != identityHashCode 条件成立
ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
if (selector == null || selector.identityHashCode != identityHashCode) {
// 创建新的 ConsistentHashSelector
selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, replicaNum));
selector = (ConsistentHashSelector<N>) selectors.get(ip);
}
// 调用 ConsistentHashSelector 的 select 方法选择 Node
return selector.select(ip);
}
/**
* 一致性哈希选择器
*/
private static final class ConsistentHashSelector<N extends Node> {
/**
* 存储虚拟节点
*/
private final TreeMap<Long, N> virtualNodes;
private final int identityHashCode;
/**
* 构造器
*
* @param nodes 节点列表
* @param identityHashCode hashcode
* @param replicaNum 分片数
*/
ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {
this.virtualNodes = new TreeMap<>();
this.identityHashCode = identityHashCode;
// 获取虚拟节点数，默认为 100
if (replicaNum == null) {
replicaNum = 100;
}
for (N node : nodes) {
for (int i = 0; i < replicaNum / 4; i++) {
// 对 url 进行 md5 运算，得到一个长度为16的字节数组
byte[] digest = md5(node.getUrl());
// 对 digest 部分字节进行 4 次 hash 运算，得到四个不同的 long 型正整数
for (int j = 0; j < 4; j++) {
// h = 0 时，取 digest 中下标为 0 ~ 3 的4个字节进行位运算
// h = 1 时，取 digest 中下标为 4 ~ 7 的4个字节进行位运算
// h = 2, h = 3 时过程同上
long m = hash(digest, j);
// 将 hash 到 node 的映射关系存储到 virtualNodes 中，
// virtualNodes 需要提供高效的查询操作，因此选用 TreeMap 作为存储结构
virtualNodes.put(m, node);
}
}
}
}
public N select(String key) {
// 对参数 key 进行 md5 运算
byte[] digest = md5(key);
// 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 方法，
// 寻找合适的 Node
return selectForKey(hash(digest, 0));
}
private N selectForKey(long hash) {
// 查找第一个大于或等于当前 hash 的节点
Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
// 如果 hash 大于 Node 在哈希环上最大的位置，此时 entry = null，
// 需要将 TreeMap 的头节点赋值给 entry
if (entry == null) {
entry = virtualNodes.firstEntry();
}
// 返回 Node
return entry.getValue();
}
}
/**
* 计算 hash 值
*/
public static long hash(byte[] digest, int number) {
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
/**
* 计算 MD5 值
*/
public static byte[] md5(String value) {
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.reset();
byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
md5.update(bytes);
return md5.digest();
}
}
Приведенный выше пример основан на последовательном алгоритме балансировки хеш-нагрузки Dubbo с некоторыми упрощениями.
4. Ссылки
1. Comparing Load Balancing Algorithms
2. «Техническая архитектура крупных веб-сайтов: основные принципы и анализ конкретных случаев»
3. Серия статей об архитектуре крупномасштабных веб-сайтов: подробная балансировка нагрузки (1)
4. Что такое балансировка нагрузки
6. Описание официального алгоритма балансировки нагрузки Dubbo
7. Алгоритмы и средства балансировки нагрузки
8. Используйте синтаксический анализ DNS для балансировки нагрузки веб-сайтов.
Автор: интернет-команда vivo - Чжан Пэн