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

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

Вопрос о планировании нагрузки следует решать ещё на ранней стадии развития любого веб-проекта. «Падение» сервера (а оно всегда происходит неожиданно, в самый неподходящий момент) чревато весьма серьёзными последствиями — как моральными, так и материальными. Первоначально проблемы недостаточной производительности сервера в связи ростом нагрузок можно решать путем наращивания мощности сервера, или же оптимизацией используемых алгоритмов, программных кодов и так далее. Но рано или поздно наступает момент, когда и эти меры оказываются недостаточными.

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

Балансировка нагрузки может осуществляться при помощи как аппаратных, так и программных инструментов. Об основных методах и алгоритмах и балансировки мы бы хотели рассказать в этой статье.

Уровни балансировки

Процедура балансировки осуществляется при помощи целого комплекса алгоритмов и методов, соответствующим следующим уровням модели OSI:

• сетевому;
• транспортному;
• прикладному.

Рассмотрим эти уровни более подробно.

Балансировка на сетевом уровне

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

• DNS-балансировка. На одно доменное имя выделяется несколько IP-адресов. Сервер, на который будет направлен клиентский запрос, обычно определяется с помощью алгоритма Round Robin (о методах и алгоритмах балансировки будет подробно рассказано ниже).
• Построение NLB-кластера. При использовании этого способа серверы объединяются в кластер, состоящий из входных и вычислительных узлов. Распределение нагрузки осуществляется при помощи специального алгоритма. Используется в решениях от компании Microsoft.
• Балансировка по IP с использованием дополнительного маршрутизатора.
• Балансировка по территориальному признаку осуществляется путём размещения одинаковых сервисов с одинаковыми адресами в территориально различных регионах Интернета (так работает технология Anyсast DNS, о которой мы уже писали). Балансировка по территориальному признаку также используется во многих CDN (см. интересный пример реализации).

Балансировка на транспортном уровне

Этот вид балансировки является самым простым: клиент обращается к балансировщику, тот перенаправляет запрос одному из серверов, который и будет его обрабатывать. Выбор сервера, на котором будет обрабатываться запрос, может осуществляться в соответствии с самыми разными алгоритмами (об этом ещё пойдёт речь ниже): путём простого кругового перебора, путём выбора наименее загруженного сервера из пула и т.п.

Иногда балансировку на транспортном уровне сложно отличить от балансировки на сетевом уровне. Рассмотрим следующее правило для сетевого фильтра pf в BSD-системах: так, например, формально тут идет речь про балансировку трафика на конкретном порту TCP (пример для сетевого фильтра pf в BSD-системах):

web_servers = "< 10.0.0.10, 10.0.0.11, 10.0.0.13 >" match in on $ext_if proto tcp to port 80 rdr-to $web_servers round-robin sticky-address

Речь в нём идет о балансировке трафика на конкретном порту TCP.

Рассмотрим теперь другой пример:

pass in on $int_if from $lan_net \ route-to < ($ext_if1 $ext_gw1), ($ext_if2 $ext_gw2) >\ round-robin

В этом правиле речь о балансировке исходящего трафика на сетевом уровне. В нём не указано ни конкретного порта, ни конкретного протокола.

Различие между уровнями балансировки можно объяснить следующим образом. К сетевому уровню относятся решения, которые не терминируют на себе пользовательские сессии. Они просто перенаправляют трафик и не работают в проксирующем режиме.
На сетевом уровне балансировщик просто решает, на какой сервер передавать пакеты. Сессию с клиентом осуществляет сервер.

На транспортном уровене общение с клиентом замыкается на балансировщике, который работает как прокси. Он взаимодействует с серверами от своего имени, передавая информацию о клиенте в дополнительных данных и заголовках. Таким образом работает, например, популярный программный балансировщик HAProxy.

Балансировка на прикладном уровне

При балансировке на прикладном уровне балансировщик работает в режиме «умного прокси». Он анализирует клиентские запросы и перенаправляет их на разные серверы в зависимости от характера запрашиваемого контента. Так работает, например, веб-сервер Nginx, распределяя запросы между фронтендом и бэкендом. За балансировку в Nginx отвечает модуль Upstream. Более подробно об особенностях балансировки Nginx на основе различных алгоритмов можно прочитать, например, здесь.

В качестве ещё одного примера инструмента балансировки на прикладном уровне можно привести pgpool — промежуточный слой между клиентом и сервером СУБД PostgreSQL. С его помощью можно распределять запросы оп серверам баз данных в зависимости от их содержания,: например, запросы на чтение будут передаваться на один сервер, а запросы на запись — на другой. Подробнее о pgpool и специфике работы с ним можно почитать в этой статье).

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

Существует много различных алгоритмов и методов балансировки нагрузки. Выбирая конкретный алгоритм, нужно исходить, во-первых, из специфики конкретного проекта, а во-вторых — из целей. которые мы планируем достичь.

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

• справедливость: нужно гарантировать, чтобы на обработку каждого запроса выделялись системные ресурсы и не допустить возникновения ситуаций, когда один запрос обрабатывается, а все остальные ждут своей очереди;
• эффективность: все серверы, которые обрабатывают запросы, должны быть заняты на 100%; желательно не допускать ситуации, когда один из серверов простаивает в ожидании запросов на обработку (сразу же оговоримся, что в реальной практике эта цель достигается далеко не всегда);
• сокращение времени выполнения запроса: нужно обеспечить минимальное время между началом обработки запроса (или его постановкой в очередь на обработку) и его завершения;
• сокращение времени отклика: нужно минимизировать время ответа на запрос пользователя.

Очень желательно также, чтобы алгоритм балансировки обладал следующими свойствами:

• предсказуемость: нужно чётко понимать, в каких ситуациях и при каких нагрузках алгоритм будет эффективным для решения поставленных задач;
• равномерная загрузка ресурсов системы;
• масштабирумость: алгоритм должен сохранять работоспособность при увеличении нагрузки.

Round Robin

Round Robin, или алгоритм кругового обслуживания, представляет собой перебор по круговому циклу: первый запрос передаётся одному серверу, затем следующий запрос передаётся другому и так до достижения последнего сервера, а затем всё начинается сначала.

Самой распространёной имплементацией этого алгоритма является, конечно же, метод балансировки Round Robin DNS. Как известно, любой DNS-сервер хранит пару «имя хоста — IP-адрес» для каждой машины в определённом домене. Этот список может выглядеть, например, так:

example.com xxx.xxx.xxx.2 www.example.com xxx.xxx.xxx.3

С каждым именем из списка можно ассоциировать несколько IP-адресов:

example.com xxx.xxx.xxx.2 www.example.com xxx.xxx.xxx.3 www.example.com xxx.xxx.xxx.4 www.example.com xxx.xxx.xxx.5 www.example.com xxx.xxx.xxx.6

DNS-сервер проходит по всем записям таблицы и отдаёт на каждый новый запрос следующий IP-адрес: например, на первый запрос — xxx.xxx.xxx.2, на второй — ххх.ххх.ххх.3, и так далее. В результате все серверы в кластере получают одинаковое количество запросов.

В числе несомненных плюсов этого алгоритма следует назвать, во-первых, независимость от протокола высокого уровня. Для работы по алгоритму Round Robin используется любой протокол, в котором обращение к серверу идёт по имени.
Балансировка на основе алгоритма Round Robin никак не зависит от нагрузки на сервер: кэширующие DNS-серверы помогут справиться с любым наплывом клиентов.

Использование алгоритма Round Robin не требует связи между серверами, поэтому он может использоваться как для локальной, так и для глобальной балансировки,.
Наконец, решения на базе алгоритма Round Robin отличаются низкой стоимостью: чтобы они начали работать, достаточно просто добавить несколько записей в DNS.

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

Также при балансировке по алгоритму Round Robin совершенно не учитывается загруженность того или иного сервера в составе кластера. Представим себе следующую гипотетическую ситуацию: один из узлов загружен на 100%, в то время как другие — всего на 10 — 15%. Алгоритм Round Robin возможности возникновения такой ситуации не учитывает в принципе, поэтому перегруженный узел все равно будет получать запросы. Ни о какой справедливости, эффективности и предсказуемости в таком случае не может быть и речи.

В силу описанных выше обстоятельств сфера применения алгоритма Round Robin весьма ограничена.

Weighted Round Robin

Это — усовершенствованная версия алгоритма Round Robin. Суть усовершенствований заключается в следующем: каждому серверу присваивается весовой коэффициент в соответствии с его производительностью и мощностью. Это помогает распределять нагрузку более гибко: серверы с большим весом обрабатывают больше запросов. Однако всех проблем с отказоустойчивостью это отнюдь не решает. Более эффективную балансировку обеспечивают другие методы, в которых при планировании и распределении нагрузки учитывается большее количество параметров.

Least Connections

В предыдущем разделе мы перечислили основные недостатки алгоритма Round Robin. Назовём ещё один: в нём совершенно не учитывается количество активных на данный момент подключений.

Рассмотрим практический пример. Имеется два сервера — обозначим их условно как А и Б. К серверу А подключено меньше пользователей, чем к серверу Б. При этом сервер А оказывается более перегруженным. Как это возможно? Ответ достаточно прост: подключения к серверу А поддерживаются в течение более долгого времени по сравнению с подключениями к серверу Б.

Описанную проблему можно решить с помощью алгоритма, известного под названием least connections (сокращённо — leastconn). Он учитывает количество подключений, поддерживаемых серверами в текущий момент времени. Каждый следующий вопрос передаётся серверу с наименьшим количеством активных подключений.

Существует усовершенствованный вариант этого алгоритма, предназначенный в первую очередь для использования в кластерах, состоящих из серверов с разными техническими характеристиками и разной производительностью. Он называется Weighted Least Connections и учитывает при распределении нагрузки не только количество активных подключений, но и весовой коэффициент серверов.

В числе других усовершенствованных вариантов алгоритма Least Connections следует прежде всего выделить Locality-Based Least Connection Scheduling и Locality-Based Least Connection Scheduling with Replication Scheduling.

Первый метод был создан специально для кэширующих прокси-серверов. Его суть заключается в следующем: наибольшее количество запросов передаётся серверам с наименьшим количеством активных подключений. За каждым из клиентских серверов закрепляется группа клиентских IP. Запросы с этих IP направляются на «родной» сервер, если он не загружен полностью. В противном случае запрос будет перенаправлен на другой сервер (он должен быть загружен менее чем наполовину).

В алгоритме Locality-Based Least Connection Scheduling with Replication Scheduling каждый IP-адрес или группа IP-адресов закрепляется не за отдельным сервером, а за целой группой серверов. Запрос передаётся наименее загруженному серверу из группы. Если же все серверы из «родной» группы перегружены, то будет зарезервирован новый сервер. Этот новый сервер будет добавлен к группе, обслуживающей IP, с которого был отправлен запрос. В свою очередь наиболее загруженный сервер из этой группы будет удалён — это позволяет избежать избыточной репликации.

Destination Hash Scheduling и Source Hash Scheduling

Алгоритм Destination Hash Scheduling был создан для работы с кластером кэширующих прокси-серверов, но он часто используется и в других случаях. В этом алгоритме сервер, обрабатывающий запрос, выбирается из статической таблицы по IP-адресу получателя.

Алгоритм Source Hash Scheduling основывается на тех же самых принципах, что и предыдущий, только сервер, который будет обрабатывать запрос, выбирается из таблицы по IP-адресу отправителя.

Sticky Sessions

Sticky Sessions — алгоритм распределения входящих запросов, при котором соединения передаются на один и тот же сервер группы. Он используется, например, в веб-сервере Nginx. Сессии пользователя могут быть закреплены за конкретным сервером с помощью метода IP hash (подробную информацию о нём см. в официальной документации). С помощью этого метода запросы распределяются по серверам на основе IP-aдреса клиента. Как указано в документации (см. ссылку выше), «метод гарантирует, что запросы одного и того же клиента будет передаваться на один и тот же сервер». Если закреплённый за конкретным адресом сервер недоступен, запрос будет перенаправлен на другой сервер. Пример фрагмента конфигурационного файла:

upstream backend

Начиная с версии 1.2.2 в Nginx для каждого сервера можно указывать вес.

Применение этого метода сопряжено с некоторыми проблемами. Проблемы с привязкой сессий могут возникнуть, если клиент использует динамический IP. В ситуации, когда большое количество запросов проходит через один прокси-сервер, балансировку вряд ли можно назвать эффективной и справедливой. Описанные проблемы, однако, можно решить, используя cookies. В коммерческой версии Nginx имеется специальный модуль sticky, который как раз использует cookies для балансировки. Есть у него и бесплатные аналоги — например, nginx-sticky-module.
Можно использовать метод sticky-sessions и в HAProxy — подробнее об этом можно прочитать, например, здесь.

Заключение

Эта статья по сути представляет собой введение в проблематику балансировки нагрузки. Обсуждение этой темы мы продолжим и в дальнейших публикациях. Если у вас есть вопросы, замечания и дополнения — добро пожаловать в комментарии. Будем также признательны, если вы поделитесь нетривиальными практическими примерами организации балансировки нагрузки для различных проектов.

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

• балансировка нагрузки
• load balancing
• селектел
• selectel

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

Рано или поздно веб-приложения перерастают среду одного сервера. Компаниям требуется увеличить или их доступность, или масштабируемость, или и то, и другое. Чтобы сделать это, они развёртывают своё приложение на нескольких серверах и ставят перед ним балансировщик нагрузок для распределения входящих запросов. Чтобы справляться с нагрузками, большим компаниям могут потребоваться тысячи серверов, на которых запущено веб-приложение.

В этом посте мы рассмотрим способы, которыми один балансировщик нагрузок может распределять HTTP-запросы на множество серверов. Мы начнём снизу и проделаем весь путь вверх до современных алгоритмов балансировки нагрузок.

▍ Визуализация проблемы

Давайте начнём сначала: с одного балансировщика нагрузок , отправляющего запросы одному серверу . Запросы отправляются с частотой 1 запрос в секунду (request per second, RPS), и каждый запрос постепенно уменьшается в размере, пока сервер обрабатывает его.

Для многих веб-сайтов такая система вполне работает. Современные серверы мощны и способны обрабатывать множество запросов . Но что будет, если они перестанут справляться?

Мы видим, что при частоте 3 RPS — часть запросов отбрасывается . Если запрос поступает на сервер , пока обрабатывается другой запрос , то сервер его отбросит . Это приводит к тому, что у пользователя отображается ошибка, и такую ситуацию нужно избегать. Чтобы устранить проблему, можно добавить к нашему балансировщику нагрузок ещё один сервер .

Отбрасываемых запросов больше нет! Наш балансировщик нагрузок в этом случае отправляет по очереди запрос каждому серверу ; это называется балансировкой нагрузок циклическим перебором (round robin). Это одна из самых простых разновидностей балансировки нагрузок, которая хорошо работает, когда серверы имеют одинаковую мощность, а запросы одинаково затратны.

▍ Когда round robin не подходит

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

Давайте посмотрим, что произойдёт, когда мы начнём варьировать затраты на запрос . В показанной ниже симуляции запросы имеют разные затраты. Это можно заметить по тому, что на уменьшение некоторым запросам требуется больше времени, чем другим.

Хотя большинство запросов обрабатывается успешно, некоторые приходится отбрасывать . Один из способов решения этой проблемы заключается в создании «очереди запросов».

Очереди запросов позволяют нам справляться с неопределённостью, но при этом приходится идти на компромисс. Мы будем отбрасывать меньшее количество запросов , однако ценой того, что некоторые запросы будут иметь повышенную задержку. Если вы понаблюдаете за показанной выше симуляцией, то заметите, что запросы немного меняют цвет. Чем дольше они не обрабатываются, тем сильнее меняется их цвет. Также вы заметите, что благодаря различиям в стоимости запросов серверы начинают проявлять признаки дисбаланса. Очереди накапливаются на серверах , которым не повезло и которым приходится обрабатывать множество затратных запросов подряд. Если очередь заполнена, мы отбросим запрос .

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

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

Однако несмотря на свои недостатки, round robin по-прежнему остаётся стандартным методом балансировки HTTP-нагрузок для nginx.

▍ Совершенствование round robin

Можно улучшить round robin так, чтобы он лучше справлялся с колебаниями. Существует алгоритм, называющийся «weighted round robin» («взвешенный цикличный перебор»); он заключается в том, что люди присваивают каждому серверу вес, определяющий, сколько запросов ему отправлять.

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

Хотя это позволяет лучше справляться с колебаниями мощности серверов , чем стандартный round robin, нам всё равно нужно решить вопрос колебаний запросов . На практике ручное указание весов быстро оказывается неэффективным. Сложно свести производительность сервера к одному числу, и для этого потребуется тщательное тестирование нагрузок с реальными рабочими нагрузками. Это делают редко, поэтому другой вариант weighted round robin вычисляет веса динамически при помощи вспомогательной метрики: задержки.

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

На этот раз я добавил к каждому серверу текст, отображающий среднюю задержку трёх последних обработанных запросов . Затем мы решаем, отправить ли 1, 2 или 3 запроса каждому серверу , на основании относительного различия в задержках. Результат очень схож с исходной симуляцией weighted round robin,
но отсутствует необходимость заранее указывать вес каждого сервера . Этот алгоритм также сможет адаптироваться к изменениям производительности сервера со временем. Это называется «dynamic weighted round robin».

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

▍ Уходим от round robin

Кажется, dynamic weighted round robin хорошо учитывает колебания и мощности сервера , и затрат на запросы . Но что, если я скажу вам, что можно решать задачу ещё лучше и при помощи более простого алгоритма?

Это называется балансировкой нагрузок по принципу «least connections» (наименьшего количества соединений).

Так как балансировщик нагрузок находится между сервером и пользователем, он может точно отслеживать, сколько ожидающих запросов есть у каждого сервера . То есть при поступлении нового запроса и необходимости выбора, куда его отправить, он знает, у каких из серверов меньше всего работы, и отдаёт приоритет им.

Этот алгоритм работает чрезвычайно хорошо вне зависимости от степени колебаний. Он избавляет от неопределённости, обеспечивая точное понимание того, чем занят каждый из серверов . Он обладает и ещё одним преимуществом: простотой реализации. Поэтому такой алгоритм является стандартным методом балансировки HTTP-нагрузки в балансировщиках нагрузок AWS. Он также используется как опция в nginx, и с ним стоит поэкспериментировать, если вы никогда не меняли стандартный метод.

Давайте посмотрим это в действии в симуляции схожего уровня сложности и с теми же параметрами, что и в алгоритме dynamic weighted round robin. Эти параметры в оригинале статьи тоже рандомизированы, так что можно обновить страницу, чтобы увидеть новые варианты.

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

▍ Оптимизация задержек

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

Часто нас больше волнуют задержки. Они измеряются в миллисекундах с момента создания запроса до его обработки. При обсуждении задержки в этом контексте обычно говорят о разных «перцентилях». Например, 50-й перцентиль (также называемый «медианой») определяется как значение в миллисекундах, ниже которого 50% запросов и выше которого 50% запросов.

Я запустил на 60 секунд три симуляции с одинаковыми параметрами и каждую секунду фиксировал различные измерения. Симуляции отличались лишь алгоритмом балансировки нагрузок. Давайте сравним медианы для каждой из трёх симуляций:

Возможно, вы этого не ожидали, но round robin имеет самую низкую медианную задержку. Если бы мы не рассматривали все остальные точки данных, то упустили бы общую картину. Давайте взглянем на 95-й и 99-й перцентили.

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

Мы видим, что round robin плохо проявляет себя на высоких перцентилях. Почему round robin имеет отличную медиану, но плохие 95-й и 99-й перцентили?

При round robin состояние каждого сервера не учитывается, поэтому довольно много запросов будут отправляться к серверам , находящимся в состоянии простоя. Вот как мы получаем низкий 50-й перцентиль. С другой стороны, мы запросто будем отправлять запросы на перегруженные серверы , таким образом — получая плохие 95-й и 99-й перцентили.

Полные данные мы можем рассмотреть в виде гистрограммы:

Я выбрал параметры этих симуляций таким образом, чтобы избежать отбрасывания всех запросов . Это гарантирует, что мы будем сравнивать одинаковое количество точек данных для всех трёх алгоритмов. Давайте снова запустим симуляции, но с увеличенным значением RPS, чтобы все алгоритмы перестали справляться. Ниже показан график кумулятивных запросов , отбрасываемых с течением времени.

Least connections справляется с перегрузками гораздо лучше, но ценой чуть больших задержек 95-го и 99-го перцентиля. В некоторых случаях это может быть приемлемым компромиссом.

▍ Ещё один алгоритм

Если нам действительно нужно оптимизировать задержки, то требуется алгоритм, учитывающий их. Разве не будет здорово, если мы сможем скомбинировать алгоритмы dynamic weighted round robin и least connections? Так мы получим задержку weighted round robin и надёжность least connections.

Оказывается, не у нас первых возникла такая мысль. Ниже показана симуляция, использующая алгоритм под названием «peak exponentially weighted moving average» (или PEWMA). Название длинное и сложное, но не торопитесь, скоро мы его разберём.

Я подобрал для этой симуляции конкретные параметры, гарантирующие демонстрацию ожидаемого поведения. Если присмотреться, то можно заметить, что алгоритм, спустя какое-то время, перестаёт отправлять запросы самому левому серверу . Он делает так, потому что понимает, что все остальные серверы быстрее, и нет необходимости отправлять запросы самому медленному. Это приведёт к повышению задержки запросов .

Как он это делает? Он сочетает методики из dynamic weighted round robinс методиками из least connections, а поверх добавляет немного своей магии.

Для каждого сервера алгоритм отслеживает задержку последних N запросов . Вместо того, чтобы использовать её как среднее, он суммирует значения, но экспоненциально снижает коэффициент масштаба. Это приводит к тому, что чем старее задержка, тем меньше она влияет на сумму. Недавние запросы влияют на расчёт сильнее, чем старые.

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

Как же он проявляет себя в сравнении с другими алгоритмами? Сначала давайте взглянем на 50-й, 95-й и 99-й перцентиль и сравним их с показанными выше данными least connections.

Мы видим улучшения во всех перцентилях! Гораздо больше они проявляются на высоких перцентилях, но стабильно присутствуют и в медиане. Вот те же данные в виде гистограммы.

А как насчёт отброшенных запросов ?

Изначально производительность лучше, но со временем алгоритм начинает вести себя хуже, чем least connections. Это логично. PEWMA оппортунистичен, он пытается добиться наилучшей задержки, а это значит, что он иногда может обеспечивать неполную загрузку сервера .

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

▍ Заключение

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

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

В конце оригинала статьи есть песочница, в которой можно поэкспериментировать с большинством параметров в реальном времени.

• ruvds_перевод
• балансировка нагрузки
• балансировщик нагрузки
• оптимизация запросов
• веб-серверы

Как устроен балансировщик нагрузки: алгоритмы, методы и задачи

Рассказываем, как устроены алгоритмы и методы балансировки, какие существуют точки отказа в инфраструктуре, в чем преимущества облачных балансировщиков.

Для построения надежной отказоустойчивой инфраструктуры необходимо равномерное распределение нагрузки на серверы. За эту функцию отвечает балансировщик нагрузки — сервис дистрибуции заданий внутри кластера, гарантирующий работу системы даже в случае отказа одного из серверов.

Из статьи вы узнаете, как устроены алгоритмы и методы балансировки, какие существуют точки отказа, в чем разница между Load balancer и прокси.

Что такое балансировка сетевой нагрузки

Балансировка нагрузки — метод распределения сетевого трафика и задач между сетевыми устройствами.

На старте развития сервиса все компоненты (Frontend, Backend, база данных) могут находиться на одном сервере. Если нагрузка растет, его можно масштабировать вертикально: поменять конфигурацию сервера на более мощную или быстро добавить ресурсов в облачный сервер — добавить число vCPU или объем памяти.

На какое-то время этого будет достаточно, но в конечном итоге мощности сервера может не хватить, и задачи разделятся на несколько серверов. Так, фронтенд уйдет на отдельный сервер, бэкенд — на второй, а база данных будет храниться еще на одной машине. Причем каждый из серверов тоже можно «проапгрейдить» вертикально.

В облачных балансировщиках доступны различные комбинации протоколов, которые имеют дело с нагрузкой L4 и нагрузкой L7-уровней.

• TCP–TCP — классическая L4-балансировка,
• TCP–PROXY — информация о клиенте не теряется и передается в отдельном заголовке соединения,
• UDP–UDP — UDP-протокол быстрее, чем TCP, но менее надежен,
• HTTP–HTTP — L7-балансировка,
• HTTPS–HTTP — L7-балансировка с шифрованием и терминацией SSL-сертификата на балансировщике.

Заключение

На этом мы закончим обзор балансировщиков нагрузки. Мы рассмотрели современные подходы балансировки сетевой нагрузки, изучили функционал Load balancer и алгоритмы балансировки.

Балансировщики нагрузки — обязательный элемент сложной инфраструктуры, которая состоит из нескольких серверов и требует «умных» подходов к управлению трафиком.

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

Вопрос о планировании нагрузки следует решать ещё на ранней стадии развития любого веб-проекта. «Падение» сервера (а оно всегда происходит неожиданно, в самый неподходящий момент) чревато весьма серьёзными последствиями — как моральными, так и материальными. Первоначально проблемы недостаточной производительности сервера применительно к&nbsp ;возрастающим нагрузкам можно решать путем наращивания мощности сервера, или же оптимизацией используемых алгоритмов, программных кодов и т.п. Для решения проблемы высоких нагрузок сегодня чаще всего используется кластеризация: несколько серверов объединяются в кластер; нагрузка между ними распределяется при помощи комплекса специальных методов, называемых балансировкой. Помимо решения проблемы высоких нагрузок в кластере мы получаем зачастую еще и резервирование серверов друг на друга. Балансировка нагрузки может осуществляться при помощи как аппаратных, так и программных инструментов. Об основных методах, алгоритмах и инструментах балансировки мы бы хотели рассказать в этой статье.

Вопрос о планировании нагрузки следует решать ещё на ранней стадии развития любого веб-проекта. «Падение» сервера (а оно всегда происходит неожиданно, в самый неподходящий момент) чревато весьма серьёзными последствиями — как моральными, так и материальными. Первоначально проблемы недостаточной производительности сервера в связи ростом нагрузок можно решать путем наращивания мощности сервера, или же оптимизацией используемых алгоритмов, программных кодов и так далее. Но рано или поздно наступает момент, когда и эти меры оказываются недостаточными.

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

Балансировка нагрузки может осуществляться при помощи как аппаратных, так и программных инструментов. Об основных методах и алгоритмах и балансировки мы бы хотели рассказать в этой статье.

Уровни балансировки

Процедура балансировки осуществляется при помощи целого комплекса алгоритмов и методов, соответствующим следующим уровням модели OSI:

• сетевому;
• транспортному;
• прикладному.

Рассмотрим эти уровни более подробно.

Балансировка на сетевом уровне

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

• DNS-балансировка. На одно доменное имя выделяется несколько IP-адресов. Сервер, на который будет направлен клиентский запрос, обычно определяется с помощью алгоритма Round Robin (о методах и алгоритмах балансировки будет подробно рассказано ниже).
• Построение NLB-кластера. При использовании этого способа серверы объединяются в кластер, состоящий из входных и вычислительных узлов. Распределение нагрузки осуществляется при помощи специального алгоритма. Используется в решениях от компании Microsoft.
• Балансировка по IP с использованием дополнительного маршрутизатора.
• Балансировка по территориальному признаку осуществляется путём размещения одинаковых сервисов с одинаковыми адресами в территориально различных регионах Интернета (так работает технология Anyсast DNS, о которой мы уже писали). Балансировка по территориальному признаку также используется во многих CDN (см. интересный пример реализации ).

Балансировка на транспортном уровне

Этот вид балансировки является самым простым: клиент обращается к балансировщику, тот перенаправляет запрос одному из серверов, который и будет его обрабатывать. Выбор сервера, на котором будет обрабатываться запрос, может осуществляться в соответствии с самыми разными алгоритмами (об этом ещё пойдёт речь ниже): путём простого кругового перебора, путём выбора наименее загруженного сервера из пула и т.п.
Иногда балансировку на транспортном уровне сложно отличить от балансировки на сетевом уровне. Рассмотрим следующее правило для сетевого фильтра pf в BSD-системах: так, например, формально тут идет речь про балансировку трафика на конкретном порту TCP (пример для сетевого фильтра pf в BSD-системах):

web_servers = "< 10.0.0.10, 10.0.0.11, 10.0.0.13 >" match in on $ext_if proto tcp to port 80 rdr-to $web_servers round-robin sticky-address 

Речь в нём идет о балансировке трафика на конкретном порту TCP.

Рассмотрим теперь другой пример:

pass in on $int_if from $lan_net \ route-to < ($ext_if1 $ext_gw1), ($ext_if2 $ext_gw2) >\ round-robin 

В этом правиле речь о балансировке исходящего трафика на сетевом уровне. В нём не указано ни конкретного порта, ни конкретного протокола.

Различие между уровнями балансировки можно объяснить следующим образом. К сетевому уровню относятся решения, которые не терминируют на себе пользовательские сессии. Они просто перенаправляют трафик и не работают в проксирующем режиме.
На сетевом уровне балансировщик просто решает, на какой сервер передавать пакеты. Сессию с клиентом осуществляет сервер.

На транспортном уровене общение с клиентом замыкается на балансировщике, который работает как прокси. Он взаимодействует с серверами от своего имени, передавая информацию о клиенте в дополнительных данных и заголовках. Таким образом работает, например, популярный программный балансировщик HAProxy.

Балансировка на прикладном уровне

При балансировке на прикладном уровне балансировщик работает в режиме «умного прокси». Он анализирует клиентские запросы и перенаправляет их на разные серверы в зависимости от характера запрашиваемого контента. Так работает, например, веб-сервер Nginx, распределяя запросы между фронтендом и бэкендом. За балансировку в Nginx отвечает модуль Upstream. Более подробно об особенностях балансировки Nginx на основе различных алгоритмов можно прочитать, например, здесь .

В качестве ещё одного примера инструмента балансировки на прикладном уровне можно привести pgpool — промежуточный слой между клиентом и сервером СУБД PostgreSQL. С его помощью можно распределять запросы оп серверам баз данных в зависимости от их содержания,: например, запросы на чтение будут передаваться на один сервер, а запросы на запись — на другой. Подробнее о pgpool и специфике работы с ним можно почитать в этой статье ).

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

Существует много различных алгоритмов и методов балансировки нагрузки. Выбирая конкретный алгоритм, нужно исходить, во-первых, из специфики конкретного проекта, а во-вторых — из целей. которые мы планируем достичь.

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

• справедливость: нужно гарантировать, чтобы на обработку каждого запроса выделялись системные ресурсы и не допустить возникновения ситуаций, когда один запрос обрабатывается, а все остальные ждут своей очереди;
• эффективность: все серверы, которые обрабатывают запросы, должны быть заняты на 100%; желательно не допускать ситуации, когда один из серверов простаивает в ожидании запросов на обработку (сразу же оговоримся, что в реальной практике эта цель достигается далеко не всегда);
• сокращение времени выполнения запроса: нужно обеспечить минимальное время между началом обработки запроса (или его постановкой в очередь на обработку) и его завершения;
• сокращение времени отклика: нужно минимизировать время ответа на запрос пользователя.

Очень желательно также, чтобы алгоритм балансировки обладал следующими свойствами:

• предсказуемость: нужно чётко понимать, в каких ситуациях и при каких нагрузках алгоритм будет эффективным для решения поставленных задач;
• равномерная загрузка ресурсов системы;
• масштабирумость: алгоритм должен сохранять работоспособность при увеличении нагрузки.

Round Robin

Round Robin, или алгоритм кругового обслуживания, представляет собой перебор по круговому циклу: первый запрос передаётся одному серверу, затем следующий запрос передаётся другому и так до достижения последнего сервера, а затем всё начинается сначала.

Самой распространёной имплементацией этого алгоритма является, конечно же, метод балансировки Round Robin DNS. Как известно, любой DNS-сервер хранит пару «имя хоста — IP-адрес» для каждой машины в определённом домене. Этот список может выглядеть, например, так:

example.com xxx.xxx.xxx.2 www.example.com xxx.xxx.xxx.3 

С каждым именем из списка можно ассоциировать несколько IP-адресов:

example.com xxx.xxx.xxx.2 www.example.com xxx.xxx.xxx.3 www.example.com xxx.xxx.xxx.4 www.example.com xxx.xxx.xxx.5 www.example.com xxx.xxx.xxx.6 

DNS-сервер проходит по всем записям таблицы и отдаёт на каждый новый запрос следующий IP-адрес: например, на первый запрос — xxx.xxx.xxx.2, на второй — ххх.ххх.ххх.3, и так далее. В результате все серверы в кластере получают одинаковое количество запросов.

В числе несомненных плюсов этого алгоритма следует назвать, во-первых, независимость от протокола высокого уровня. Для работы по алгоритму Round Robin используется любой протокол, в котором обращение к серверу идёт по имени.
Балансировка на основе алгоритма Round Robin никак не зависит от нагрузки на сервер: кэширующие DNS-серверы помогут справиться с любым наплывом клиентов.

Использование алгоритма Round Robin не требует связи между серверами, поэтому он может использоваться как для локальной, так и для глобальной балансировки,.
Наконец, решения на базе алгоритма Round Robin отличаются низкой стоимостью: чтобы они начали работать, достаточно просто добавить несколько записей в DNS.

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

Также при балансировке по алгоритму Round Robin совершенно не учитывается загруженность того или иного сервера в составе кластера. Представим себе следующую гипотетическую ситуацию: один из узлов загружен на 100%, в то время как другие — всего на 10 — 15%. Алгоритм Round Robin возможности возникновения такой ситуации не учитывает в принципе, поэтому перегруженный узел все равно будет получать запросы. Ни о какой справедливости, эффективности и предсказуемости в таком случае не может быть и речи.

В силу описанных выше обстоятельств сфера применения алгоритма Round Robin весьма ограничена.

Weighted Round Robin

Это — усовершенствованная версия алгоритма Round Robin. Суть усовершенствований заключается в следующем: каждому серверу присваивается весовой коэффициент в соответствии с его производительностью и мощностью. Это помогает распределять нагрузку более гибко: серверы с большим весом обрабатывают больше запросов. Однако всех проблем с отказоустойчивостью это отнюдь не решает. Более эффективную балансировку обеспечивают другие методы, в которых при планировании и распределении нагрузки учитывается большее количество параметров.

Least Connections

В предыдущем разделе мы перечислили основные недостатки алгоритма Round Robin. Назовём ещё один: в нём совершенно не учитывается количество активных на данный момент подключений.

Рассмотрим практический пример. Имеется два сервера — обозначим их условно как А и Б. К серверу А подключено меньше пользователей, чем к серверу Б. При этом сервер А оказывается более перегруженным. Как это возможно? Ответ достаточно прост: подключения к серверу А поддерживаются в течение более долгого времени по сравнению с подключениями к серверу Б.

Описанную проблему можно решить с помощью алгоритма, известного под названием least connections (сокращённо — leastconn). Он учитывает количество подключений, поддерживаемых серверами в текущий момент времени. Каждый следующий вопрос передаётся серверу с наименьшим количеством активных подключений.

Существует усовершенствованный вариант этого алгоритма, предназначенный в первую очередь для использования в кластерах, состоящих из серверов с разными техническими характеристиками и разной производительностью. Он называется Weighted Least Connections и учитывает при распределении нагрузки не только количество активных подключений, но и весовой коэффициент серверов.

В числе других усовершенствованных вариантов алгоритма Least Connections следует прежде всего выделить Locality-Based Least Connection Scheduling и Locality-Based Least Connection Scheduling with Replication Scheduling.

Первый метод был создан специально для кэширующих прокси-серверов. Его суть заключается в следующем: наибольшее количество запросов передаётся серверам с наименьшим количеством активных подключений. За каждым из клиентских серверов закрепляется группа клиентских IP. Запросы с этих IP направляются на «родной» сервер, если он не загружен полностью. В противном случае запрос будет перенаправлен на другой сервер (он должен быть загружен менее чем наполовину).

В алгоритме Locality-Based Least Connection Scheduling with Replication Scheduling каждый IP-адрес или группа IP-адресов закрепляется не за отдельным сервером, а за целой группой серверов. Запрос передаётся наименее загруженному серверу из группы. Если же все серверы из «родной» группы перегружены, то будет зарезервирован новый сервер. Этот новый сервер будет добавлен к группе, обслуживающей IP, с которого был отправлен запрос. В свою очередь наиболее загруженный сервер из этой группы будет удалён — это позволяет избежать избыточной репликации.

Destination Hash Scheduling и Source Hash Scheduling

Алгоритм Destination Hash Scheduling был создан для работы с кластером кэширующих прокси-серверов, но он часто используется и в других случаях. В этом алгоритме сервер, обрабатывающий запрос, выбирается из статической таблицы по IP-адресу получателя.

Алгоритм Source Hash Scheduling основывается на тех же самых принципах, что и предыдущий, только сервер, который будет обрабатывать запрос, выбирается из таблицы по IP-адресу отправителя.

Sticky Sessions

Sticky Sessions — алгоритм распределения входящих запросов, при котором соединения передаются на один и тот же сервер группы. Он используется, например, в веб-сервере Nginx. Сессии пользователя могут быть закреплены за конкретным сервером с помощью метода IP hash (подробную информацию о нём см. в официальной документации ). С помощью этого метода запросы распределяются по серверам на основе IP-aдреса клиента. Как указано в документации (см. ссылку выше), «метод гарантирует, что запросы одного и того же клиента будет передаваться на один и тот же сервер». Если закреплённый за конкретным адресом сервер недоступен, запрос будет перенаправлен на другой сервер. Пример фрагмента конфигурационного файла:

upstream backend

Начиная с версии 1.2.2 в Nginx для каждого сервера можно указывать вес.

Применение этого метода сопряжено с некоторыми проблемами. Проблемы с привязкой сессий могут возникнуть, если клиент использует динамический IP. В ситуации, когда большое количество запросов проходит через один прокси-сервер, балансировку вряд ли можно назвать эффективной и справедливой. Описанные проблемы, однако, можно решить, используя cookies. В коммерческой версии Nginx имеется специальный модуль sticky, который как раз использует cookies для балансировки. Есть у него и бесплатные аналоги — например, nginx-sticky-module .
Можно использовать метод sticky-sessions и в HAProxy — подробнее об этом можно прочитать, например, здесь.

Заключение

Эта статья по сути представляет собой введение в проблематику балансировки нагрузки. Обсуждение этой темы мы продолжим и в дальнейших публикациях. Если у вас есть вопросы, замечания и дополнения — добро пожаловать в комментарии. Будем также признательны, если вы поделитесь нетривиальными практическими примерами организации балансировки нагрузки для различных проектов.