Какие из перечисленных ниже алгоритмов балансировки существуют

Сравнительный анализ методов балансировки трафика

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

Представим такую сюрреалистичную ситуацию, что мы фермеры, которые занимаются селекционными работами, и выводим, допустим, новые виды картофеля. Ходим мы, выращиваем свои картофелины, картошечка у нас классная, все ее любят, всем она нравится. Продаем ее на рынке и тут подумали: а как бы нам найти еще один способ ее продавать? Вспомнили, что мы ребята с IT’шным прошлым, когда-то этим занимались, в селекционеры мы ушли так, ради хобби, и решили: а давайте мы будем продавать ее в Интернете.

Сходили, недолго думая, купили сервер, запилили на него некий веб-сервис нашего Интернет магазина, и пошли к нам клиенты. Клиенты пошли, продажи растут, нагрузка на сервер повышается, повышается, повышается. Мы понимаем, что нагрузка растет, сервер надо тоже как-то апгрейдить. Увеличиваем его мощности, увеличиваем, увеличиваем, клиентов приходит все больше и больше, и, в конце концов, упираемся в такую ситуацию, что апгрейдить сервер больше некуда.

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

Мы взялись за голову, подумали: что же делать? Начали резко гуглить и наткнулись на такое понятие как «кластеризация». Решили: а чего бы нам не купить еще один сервак и не размазать наш веб-сервер по нему? Сходили, купили, поставили, и думали, что все у нас будет хорошо, что клиенты начнут ходить на оба наши сервера, нагрузочка немного выровняется, и все будет отлично.

Но после запуска, мы понимаем, что нагрузка на один из серверов у нас такая:

а нагрузка на второй сервер по-прежнему такая:

Вопрос: почему так происходит?

А происходит все потому, что мы не учитывали тот факт, что трафик между этими серверами надо как-то балансировать. Собственно, здесь мы переходим к основному вопросу — что же такое балансировка, и какие основные цели она преследует?

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

К балансировке, как и к любой системе, предъявляются некие требования. Требования такие:

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

Подробнее о каждом.

Локально систему балансировки можно применять:

1. на канальном уровне, как с использованием отдельного балансировщика, так и без него;
2. на сетевом уровне;
3. на транспортном уровне.

Балансировка на канальном уровне выполняется за счет следующего. Мы берем и навешиваем на некий специализированный интерфейс всех наших серверов один и тот же IP-адрес нашего ресурса, на который будут приходить запросы, и с которого будут уходить ответы. Но на ARP-запрос с этого IP-адреса сервера не должны отвечать. И мы навешиваем такой же IP-адрес на наш балансировщик, соответственно, на него будут приходить запросы, и отправляться ответы с него, и он же будет отвечать на ARP запросы. Т.о., получая запрос от клиента, наш балансировщик выбирает по определенному алгоритму тот или иной сервер, который будет обрабатывать этот запрос, подменяет destination MAC и отправляет его на обработку на данный сервер. Сервер его у себя обрабатывает, и т.к. мы не делали подмену заголовков на сетевом уровне, то непосредственно, минуя балансировщик, сразу отвечает клиенту через наш шлюз.

Тут к нам приходит руководство, и говорит: «Ребят, мы тут вконтакте посидели, полистали, всякие мемы почитали и поняли, что мужики от своих жен очень часто борща требуют. Подумали мы и решили, что давайте-ка мы сейчас рекламную компанию свеклы сделаем, и будем свеклу продавать. И все деньги вбухаем туда. А вас попросим как-нибудь сократить расходы на вашу классную систему балансировки».

Мы подумали и решили: а почему бы нам не избавиться от балансировщика? Но при этом прикинули, как мы можем без него реализовать балансировку.

А реализовать мы можем ее очень просто: нам необходимо превратить входящий unicast запрос в broadcast, либо в multicast, кто как хочет.

Делается это следующим образом. Все сервера должны на ARP запрос отвечать одним и тем же MAC-адресом, т.е. это может быть либо несуществующий MAC-адрес, либо какой-то мультикастовый. Либо мы можем навесить этот мультикастовый MAC-адрес на наш шлюз. Соответственно, запрос приходит на наш ресурс, и шлюз его просто размножает ко всем серверам, т.о. запросы поступают на все сервера одновременно, и каждый сервер должен сам понимать, должен ли он отвечать на запрос или нет. И понимать может очень просто, можно поставить, например, поставить деление на нуль srcIP, и дальше дело техники.

Плюсы и минусы алгоритма балансировки на канальном уровне.

В первую очередь, он не зависит от протоколов вышележащих уровней, т.е. можно балансировать нагрузку как по HTTP, так и по FTP, так и по SMTP. Затем, мы сокращаем расходы за счет отказа от выделенного балансировщика, в случае, если мы его не используем. Обратный трафик в сторону клиента не нагружает балансировщик, что тоже хорошо, например, для HTTP, когда у нас входящий запрос, как правило, легкий, а ответ на него весит порой в десятки и сотни раз больше. Затем, в современных реалиях очень полезный для нас плюс — это то, что мы используем только один публичный адрес, т.к. публичные IP нынче дорогие, это несомненно огромный плюс для нашей системы. И такая система способствует быстрому добавлению отключения серверов в кластере.

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

Из решений, использующих данный алгоритм балансировки, можно назвать Linux Virtual Server.

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

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

Из недостатков — это повышенная нагрузка на балансировщик за счет обратного трафика. Каждый сервер должен отправить ответ, в первую очередь, на балансировщик, чтобы тот выполнил обратную подмену. Соответственно, в случае с HTTP нагрузка на балансировщик тоже будет большой.

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

Очень интересный пример реализации данного вида балансировки — это балансировка при помощи т.н. алгоритма ECMP, т.е. equal-cost multi-path. Выяснилось, что все современные роутеры могут распределять, балансировать нагрузку сами. Для этого нам достаточно на роутер анонсировать одну и ту же подсеть по разным маршрутам. Балансировщик в данном случае имея два одинаковых маршрута по своим общим метрикам будет распределять нагрузку по ним равномерно.

Но существует ряд нюансов, которые тоже надо учитывать. В первую очередь, наш роутер должен распределять нагрузку таким образом, чтобы пакеты в рамках одной TCP сессии попадали на один и тот же сервер. Это раз. Такой режим на роутерах, по-моему, на современных Cisco’ах называется perdestination и perflow и поддерживается по умолчанию.

Следующий нюанс — если мы пропишем на роутере статические маршруты, то мы должны как-то автоматизировать процесс добавления и удаления серверов из нашего кластера. Для того чтобы избежать этой проблемы, мы можем использовать различные протоколы маршрутизации, такие как BGP. Т.е. на каждый наш сервер мы устанавливаем некий софтварный BGP роутер, который будет анонсировать серверную сеть на роутер, который принимает запросы. Из софтварных таких роутеров можно назвать Квага или Bird.

И также необходимо учитывать, что существуют плюсы и минусы этого метода:

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

Но существуют свои недостатки, такие как, например, необходимость ставить на сервер дополнительный софт. Как я уже говорил, это программные роутеры BGP, хотя они не сильно нагружают наши сервера. Отсутствие server-affinity, т.е. все соединения будут разрываться в том случае, если мы добавляем или удаляем сервера из кластера. Также существует проблема ограниченности одинаковых маршрутов на разных роутерах. На слайде внизу приведены несколько роутеров марки Cisco — для первых двух одновременно поддерживается восемь одинаковых маршрутов, а для последнего поддерживается до 32-х одинаковых маршрутов. Также мы должны обеспечивать равномерность нагрузки, что предъявляет некие требования к производительности наших серверов, например, если мы добавим более производительный сервер в наш кластер, то нагрузка на него будет распределяться ровно такая же, как и на все остальные. И последний минус — это таймауты BGP протокола, т.е. если сервер перестает слать на роутер, анонсировать свою сеть, т.е. он вышел из строя, роутер в течение некоторого таймаута он может все еще распределять нагрузку по данному маршруту.

Из методов глобальной балансировки можно выделить следующие наиболее распространенные методы:

• балансировка на уровне DNS,
• балансировка на прикладном уровне — это проксирование и redirect запросов,
• балансировка на сетевом уровне — рассмотрим алгоритм Anycast.

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

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

Из минусов следует назвать следующие. Сложность отключения серверов, в случае, например, их выхода из строя. В данном случае необходимо предусматривать некоторые способы резервирования этих серверов, например, по протоколу CARP или VRRP. Также сложно распределять нагрузку в нужной пропорции, т.к. DNS сервер ничего не знает о том, насколько загружен каждый сервер, а только лишь выдает их IP. Ограниченность IP-адресов — это наиболее весомый минус данного алгоритма балансировки, т.к. каждый сервер должен иметь свой глобальный IP-адрес, а как я уже говорил, IP-адреса нынче дорогие и ограничены. Кроме того, необходимо держать двойной запас серверной мощности, в том случае, когда у нас один из серверов выйдет из строя, а клиент будет ломиться на его IP и не получит нашего сервиса.

Из реализаций можно назвать любой DNS сервер, в качестве примера можно привести сервер Named из пакета BIND, PowerDNS сервер и т.д.

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

Преимущества такого алгоритма балансировки в том, что мы можем обеспечить server-affinity, т.е. мы можем привязать конкретного клиента к определенному серверу, например, используя различные настройки cookie. Затем, мы можем распределять разные типы запросов разным серверам, т.е. мы, например, можем на одном сервере держать статику, которая у нас мало весит, а на другом сервере держать какой-то тяжелый контент, и, соответственно, понимая, анализируя HTTP заголовок, мы можем направлять запрос пользователя на тот или иной сервер. Благодаря этому алгоритму балансировки мы также можем фильтровать запросы по URL, защищаясь тем самым от различных родов атак, и самостоятельно определять работоспособность каждого узла, т.е. не просто доступность каждого сервера на сетевом уровне, но и понимать насколько работоспособен, в данном случае, наш софт на сервере, и не применять при этом никаких дополнительных средств.

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

Redirect запросов. Redirect запросов имеет довольно ограниченное применение — применяется, в основном, для глобальной балансировки, и, в частности, для HTTP он хорошо применим. Суть его заключается в том, что мы получаем запрос от клиента на наш балансировщик, балансировщик отвечает ему редиректом на наш сервер, на котором содержатся ресурсы. Например, получая запрос по HTTP, балансировщик отвечает ему в ответ — выдает ошибку 302 move temporary с указанием адреса того сервера, на который дальше будет ходить наш клиент.

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

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

Из решений можно назвать программный веб-сервер nginx.

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

Плюсы такого метода в том, что мы обеспечиваем минимальную задержку при обработке запроса, т.к. клиент будет обслуживаться на ближайшем к нему сервере не только с географической точки зрения, но и с топологической. Мы обеспечиваем доставку трафика, минуя магистральные каналы связи, соответственно, получаем некоторое удешевление трафика. Еще плюс в том, что нагрузку распределяет сама сеть, — мы здесь уже фактически никак не участвуем и об этом не заботимся, т.е. этот процесс ложится на плечи Интернет-провайдера. Высокая отказоустойчивость данного алгоритма балансировки, например, если один из серверов выходит из строя, то все запросы к нему будут просто переброшены на ближайший от него сервер. Легко добавлять и выводить из работы любые наши сервера — просто перестаем анонсировать по BGP, например, подсеть, и все запросы пользователей будут маршрутизироваться на другие сервера.

Из минусов следует назвать то, что существует возможность перестроения маршрутов, что для TCP сессии достаточно критично. Например, если в рамках одной сессии пакеты пойдут по другому маршруту на другой сервер, мы получим просто ресет по TCP, и сессия прервется. Отсутствует возможность проконтролировать, с какого узла обслуживается пользователь, т.к. этим рулит сама сеть, мы не можем знать, где сейчас в данный момент обслуживается пользователь, не прибегая к различным дополнительным решениям. Дорогое оборудование, т.е. если, например, мы будем использовать аппаратные роутеры, а это достаточно дорогая штука. Еще такой важный момент, что при использовании балансировки на базе Anycast необходимо учитывать интересы Интернет провайдеров. Т.к. все мы знаем, что Интернет-провайдеры любят пиринговаться друг с другом и, соответственно, в идеале пакеты должны ходить по наиболее короткому маршруту, но по факту получается так, что Интернет-провайдер передает пакеты там, где им дешевле, и это необходимо иметь в виду.

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

• Про Round Robin я выше рассказал. Существенным его недостатком является то, что нагрузка в данном случае распределяется без учета особенностей конкретного сервера. Алгоритм Weighted Round Robin позволяет навесить на каждый сервер определенный весовой коэффициент, который будет учитывать мощность и производительность того или иного сервера, т.о. более производительный сервер будет получать запросы чаще.
• Следующий алгоритм — Least Connections, т.е. в данном случае будут учитываться не просто нагрузка на сервер, но и количество одновременных соединений с данным сервером в данный момент. Если мы хотим, например, улучшить данный алгоритм, то мы можем использовать алгоритм Least Connections, например, с весами, т.е. навесив дополнительно на каждый сервер некий весовой коэффициент в соответствии с его производительностью и мощностью.
• Destination Hash Scheduling и Source Hash Scheduling — это т.н. алгоритмы, которые анализируют IP-адрес либо источника, либо адресата и выбирают из некой статической таблицы тот или иной сервер, на который будет проксироваться дальше запрос.
• И алгоритм Sticky Sessions — в данном случае обеспечивается привязка клиента к определенному серверу и, соответственно, все пакеты в рамках одной сессии будут ходить только на этот сервер.

Дальше хочу озвучить несколько решений интеграторов, потому что они часто применяются. Мы в своем сервисе эти решения не используем, поэтому я их просто назову. Здесь перечислены решения от Cisco — это решения Cisco ACE, некий хардварный балансировщик, который имеет теоретически пропускную способность до 16 Гбит в секунду и поддерживает практически все названные мною методы и алгоритмы балансировки. Также от Cisco есть решение под названием Cisco CSS, имеет гигабитные порты, позволяет балансировать трафик на сетевом уровне и выполнять глобальную балансировку на уровне DNS. От компании F5 решение — BigIP, довольно-таки гибкое, имеет свой скриптовый язык и благодаря ему, мы можем настраивать балансировку таким образом, как нам удобнее, и как мы этого хотим. И решение от компании radware, называется оно Alteon NG — выполняет и поддерживает практически все алгоритмы балансировки, позволяет анализировать настройку куки, выполнять привязку клиента к конкретному серверу и ряд других особенностей. Кому интересно, тот может погуглить и найти информацию, она доступна.

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

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

Балансировка — это очень просто! Даже коты балансировать умеют, как мы видим.

Контакты

Этот доклад — расшифровка одного из лучших выступлений на обучающей конференции разработчиков высоконагруженных систем HighLoad++ Junior.

Также некоторые из этих материалов используются нами в обучающем онлайн-курсе по разработке высоконагруженных систем HighLoad.Guide — это цепочка специально подобранных писем, статей, материалов, видео. Уже сейчас в нашем учебнике более 30 уникальных материалов. Подключайтесь!

Ну и главная новость — мы начали подготовку весеннего фестиваля «Российские интернет-технологии», в который входит восемь конференций, включая HighLoad++ Junior. Такие доклады, как этот — наша основная гордость!

• сергей зубов
• highload junior
• балансировка

Балансировка нагрузки на кластер MySQL с помощью HAProxy

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

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

• драйвер JDBC для MySQL (MySQL Connector/J);
• драйвер, используемый по умолчанию в PHP MySQL для master-slave (mysqlnd-ms).

Эти драйверы позволяют обеспечить прозрачность подключения клиентов к автономному серверу MySQL, решению MySQL Cluster (NDB) или топологии, использующим репликацию MySQL.

Однако при использовании этих драйверов с кластером Galera для MySQL или MariaDB есть ряд проблем, так как они не обладают расширенной информацией о состоянии Galera. Например, узел-донор Galera может находиться в режиме «только для чтения» , когда помогает другому узлу повторно синхронизироваться (если для передачи снимка состояния (SST) используется mysqldump или rsync), или в случае split brain он может быть в состоянии Non-Primary. То есть, существуют случаи, когда даже драйверы с поддержкой пуллинга и балансировки не предоставляют необходимый уровень поддержки кластера.

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

Статья является переводом и адаптацией англоязычного руководства от Severalnines — разработчика инструмента ClusterControl.

Что такое HAProxy?

HAProxy, или High Availability Proxy, является программным балансировщиком нагрузки TCP/HTTP. Он распределяет рабочую нагрузку по серверам для обеспечения максимальной производительности и оптимизации использования ресурсов. HAProxy поддерживает гибко настраиваемые методы проверки доступности, обработки отказов и восстановления после них.

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

В одном из вариантов настройки HAProxy устанавливается на каждом сервере приложений, выполняющем запросы к базе данных. Такой вариант отлично подходит при наличии нескольких серверов, что позволяет контролировать нагрузку и скрыть организацию кластера СУБД. Приложение подключается к локальному HAProxy (например, устанавив mysql-соединение на 127.0.0.1:3306) и может получить доступ ко всем серверам базы данных. Веб-сервер и HAProxy вместе образуют рабочий блок, поэтому веб-сервер не будет работать, если HAProxy недоступен.

Использование HAProxy для балансировки нагрузки дает следующие преимущества:

• Все приложения получают доступ к кластеру через указанные IP-адреса. Внутренняя топология кластера базы данных скрывается за HAProxy.
• Соединения MySQL распределены между доступными узлами БД.
• Можно добавлять или удалять узлы базы данных без необходимости внесения каких-либо изменений в приложения.
• Как только достигается максимальное количество соединений с базой данных, новые соединения ставятся в очередь. Это удобный способ ограничения количества запросов на соединение с базой данных, обеспечивающий защиту от перегрузки.

ClusterControl поддерживает развертывание HAProxy из пользовательского интерфейса, поддерживая стандартные алгоритмы балансировки, предоставляемые HAProxy:

• Round Robin. Каждый сервер получает запросы пропорционально своему весу, при этом веса серверов могут меняться на лету.
• Least Connection. Выбирается сервер с наименьшим количеством активных соединений.
• Source Hash Scheduling. Сервер для соединения назначается на основе хэша IP-адреса отправителя запроса и весов серверов.

Подробную информацию о каждом алгоритме можно найти в документации HAProxy.

Проверка доступности сервера MySQL

HAProxy может проверить доступность сервера, просто подключившись к порту MySQL (обычно 3306), однако часто этого недостаточно. Возможна ситуация, когда экземпляр запущен, но не может корректно обслуживать запросы. Тогда необходимо выполнить определенные проверки в зависимости от типа кластера — Galera, репликации MySQL или MySQL Cluster.

Скрипт проверки на доступность

Лучший способ проверить, доступен ли сервер MySQL — использовать сценарий, который определяет доступность сервера путем изучения его внутреннего состояния, которое зависит от используемого решения кластеризации. ClusterControl предоставляет собственную версию скрипта проверки на доступность под названием mysqlchk. Он располагается на каждом сервере MySQL, участвующем в балансировке нагрузки, и возвращает код состояния HTTP и/или результат в стандартном потоке вывода (stdout), что полезно для проверки доступности TCP.

Использование mysqlchk для Galera Cluster

Если сервер MySQL исправен, сценарий вернет код состояния HTTP 200 OK с кодом завершения 0 . В противном случае вернется HTTP 503 Service not available и код завершения равный 1 . Использование xinetd — самый простой способ обеспечить выполнение скрипта проверки на доступность. HAProxy подключается к порту, на котором запущен скрипт, выполняемый в рамках xinetd, и запрашивает статус доступности.

Если в качестве метода проверки используется httpchk, HAProxy будет проверять код состояния HTTP, а если используется tcp-check, он будет проверять наличие ожидаемой строки в потоке данных.

На схеме ниже показан процесс проверки на доступность узла Galera для кластера multi-master:

Файл шаблона скрипта находится на сервере ClusterControl по адресу /usr/share/cmon/templates/mysqlchk.galera . ClusterControl автоматически устанавливает cкрипт mysqlchk на каждый узел, участвующий в балансировке нагрузки.

Использование mysqlchk для кластера с репликацией MySQL

Этот скрипт основан на стандартном mysqlchk, но предназначен для корректного мониторинга бэкенд-серверов, использующих репликацию MySQL. Шаблон доступен в хранилище Github, можно использовать его вместо шаблона по умолчанию в /usr/share/cmon/templates/mysqlchk.mysql до начала развертывания HAProxy. Как и в случае mysqlchk для Galera Cluster, для выполнения скрипта проверки доступности потребуется xinetd.

Скрипт определяет роль репликации MySQL согласно схеме ниже:

Настройка HAProxy для кластера с репликацией MySQL требует двух разных обработчиков HAProxy, например, порт 3307 для записи в Master и порт 3308 для чтения со всех доступных Slave-узлов (включая Master).

Использование mysqlchk-iptables для Galera Cluster

Это фоновый скрипт, который проверяет доступность узла Galera и добавляет порт перенаправления, используя iptables, если узел Galera доступен (вместо возврата HTTP-ответа). Это позволяет другим балансировщикам нагрузки TCP с более ограниченными возможностями проверки на доступность правильно контролировать бэкенд-серверы Galera.

При использовании mysqlchk-iptables вместо HAProxy можно использовать любой обратный прокси-сервер для балансировки запросов между узлами Galera, а именно:

• nginx 1.9 (—with-stream)
• keepalived
• IPVS
• distributor
• balance
• pen

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

Способы проверки доступности

HAProxy определяет доступность сервера, выполняя операцию проверки доступности. HAProxy поддерживает несколько методов проверки бэкенда на доступность, которые можно активировать посредством следующих опций:

• mysql-check
• tcp-check
• httpchk

Проверка mysql-check

Проверка состоит из отправки двух пакетов MySQL: пакета аутентификации клиента и пакета QUIT, чтобы правильно закрыть сеанс MySQL. Затем HAProxy анализирует пакет инициализации «рукопожатия» MySQL и/или пакет ошибок. Это простой, но полезный тест, который позволяет убедиться в том, что соединение с сервером MySQL осуществимо. Для его работы необходимо добавить пользователя MySQL, например так:

USE mysql; INSERT INTO user (Host,User) values ('',''); FLUSH PRIVILEGES;

Обратите внимание, что он не проверяет наличие или согласованность базы данных. Для этого необходимо использовать внешнюю проверку (через xinetd), которая описана в следующем разделе.

Проверка tcp-check

По умолчанию, сервер считается доступным тогда, когда он может принимать периодические TCP-соединения. Это недостаточно надежно, поскольку сервер базы данных может отвечать на запросы на подключение, даже находясь в нерабочем состоянии. Кроме того, существуют проверки, которые необходимо выполнить в зависимости от типа кластеризации — Galera или MySQL Cluster (NDB).

Скрипт mysqlchk, предоставляемый ClusterControl, поддерживает возврат кода состояния HTTP и стандартный вывод (stdout). Используя tcp-check и анализ стандартного вывода, можно расширить возможности скрипта, чтобы обеспечить бОльшую точность определения состояния узла репликации Galera или MySQL. Пример конфигурации ниже демонстрирует использование скрипта:

listen haproxy_192.168.55.110_3307 bind *:3307 mode tcp timeout client 10800s timeout server 10800s balance leastconn option tcp-check tcp-check expect string is\ running. option allbackups default-server port 9200 inter 2s downinter 5s rise 3 fall 2 slowstart 60s maxconn 64 maxqueue 128 weight 100 server galera1 192.168.55.111:3306 check server galera2 192.168.55.112:3306 check server galera3 192.168.55.113:3306 check

Приведенные выше строки конфигурации говорят HAProxy, что нужно выполнить проверку доступности с использованием последовательной отправки/ожидания TCP. Он подключается к порту 9200 базы данных и ожидает строку, содержащую «is running». Чтобы проверить вывод mysqlchk, установите подключение по telnet к узлу базы данных от узла HAProxy:

$ telnet 192.168.55.111 9200 Trying 192.168.55.171. Connected to 192.168.55.171. Escape character is '^]'. HTTP/1.1 200 OK Content-Type: text/html Content-Length: 43 MySQL is running. Connection closed by foreign host.

Можно использовать аналогичную конфигурацию для репликации MySQL, где ожидается строка для Master — «MySQL Master is running». По умолчанию ClusterControl использует httpchk, как описано в следующем разделе.

Проверка httpchk

Для проверки доступности сервера метод httpchk использует статусы протокола HTTP. Использование httpchk является предпочтительным вариантом, поскольку при HTTP-соединении без хранения состояния используется меньше ресурсов.

listen haproxy_192.168.55.110_3307 bind *:3307 mode tcp timeout client 10800s timeout server 10800s balance leastconn option httpchk option allbackups default-server port 9200 inter 2s downinter 5s rise 3 fall 2 slowstart 60s maxconn 64 maxqueue 128 weight 100 server galera1 192.168.55.111:3306 check server galera2 192.168.55.112:3306 check server galera3 192.168.55.113:3306 check

В приведенном выше примере HAProxy будет подключаться к порту 9200, где под управлением xinetd выполняется скрипт проверки доступности. HAProxy будет анализировать статус HTTP. Если сервер исправен, скрипт mysqlchk вернет HTTP 200 OK , в ином случае — HTTP 503 Service not available .

Обнаружение сбоев обслуживания и отказоустойчивость

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

Существует несколько пользовательских параметров, которые определяют, насколько быстро HAProxy сможет обнаружить, что сервер недоступен. Ниже приведен пример конфигурации HAProxy, развернутой ClusterControl и расположенной в /etc/haproxy/haproxy.cfg :

listen haproxy_192.168.55.110_3307 bind *:3307 mode tcp timeout client 10800s timeout server 10800s balance leastconn option httpchk option allbackups default-server port 9200 inter 2s downinter 5s rise 3 fall 2 slowstart 60s maxconn 64 maxqueue 128 weight 100 server galera1 192.168.55.111:3306 check server galera2 192.168.55.112:3306 check server galera3 192.168.55.113:3306 check

Краткое объяснение каждой строки выше:

• Раздел listen описывает полный прокси-сервер с его внешними и внутренними частями, объединенными в одном разделе. Здесь же указывается имя экземпляра HAproxy. Следующая строка, описывающая раздел, должна начинаться с отступа.
• Параметр bind определяет, на каком IP и порту будут обслуживаться запросы от клиентов. В примере указана привязка ко всем IP-адресам на этом хосте через порт 3307. Клиенты должны будут подключиться к порту, заданному в этой строке.
• Параметр mode задает режим работы HAProxy. Для MySQL экземпляр должен работать в режиме чистого TCP. Будет установлено полнодуплексное соединение между клиентами и серверами, а проверка трафика Layer 7 не будет проводиться.
• Параметр timeout client определяет максимальное время бездействия на стороне клиента. Рекомендуется задать то же значение, что и для timeout server.
• Параметр timeout server — максимальное время бездействия на стороне сервера. Рекомендуется задать то же значение, что и для timeout client.
• Параметр balance определяет алгоритм балансировки нагрузки. ClusterControl поддерживает такие алгоритмы, как Round Robin, Least Connection и Source Hash Scheduling. Least Connection является наиболее предпочтительным вариантом, так как тогда соединение будет устанавливливаться с сервером базы данных с наименьшим числом соединений.
• Опция option httpchk — задает способ проверки на доступность бэкенда. Позволяет выполнить проверку доступности на основе HTTP. ClusterControl настраивает скрипт, работающий под управлением xinetd, на каждом сервере СУБД, участвующем в балансировке.
• Опция option allbackups определяет такое поведение, что когда основные серверы недоступны, балансировка нагрузки будет выполняться между backup-серверами.
• Параметр default-server определяет свойства по умолчанию для серверов, перечисленных в опции server.
  • Атрибут port порт проверки на доступность бэкенда. ClusterControl настраивает процесс xinetd так, чтобы он выполнял скрипт проверки на порту 9200 на каждом сервере базы данных.
  • Inter: интервал между проверками, в примере он составляет 2 секунды.
  • Downinter: интервал между проверками, когда сервер недоступен. В примере он составляет 5 секунд, после чего сервер считается недоступен.
  • Rise: количество проверок, которые должен пройти сервер, чтобы получить статус доступного к работе. Сервер будет считаться доступным после 3 последовательных успешных проверок на доступность.
  • Fall: количество проверок, которые должен пройти сервер, чтобы получить статус отказавшего. Сервер будет считаться недоступным после 2 последовательных неудачных проверок на доступность.
  • Slowstart: через 60 секунд число принятых сервером соединений после перехода в состояние доступности увеличится с 1 до 100% от стандартного динамического предела.
  • Maxconn: HAProxy прекратит принимать соединения, когда число соединений составит 64.
  • Maxqueue: максимальное количество соединений для этого сервера, которые будут ожидать в очереди. При достижении заданного лимита, следующие запросы будут пересылаться на другие серверы, а не ожидать обслуживания неопределенное количество времени.
  • Weight: в Galera все узлы обычно обрабатываются имеют один вес и равнодоступны.

  Согласно приведенным выше настройкам сервер MySQL не проходит проверку на доступность, когда:

  • HAProxy не смог подключиться к порту 9200 сервера MySQL;
  • подключение к порту 9200 устанавливается, но возвращает код ответа HTTP, отличный от «HTTP/1.1 200 OK» (метод httpchk).

  Логика обработки состояний отказа и доступности следующая:

  • Каждые 2 секунды HAProxy выполняет проверку на доступность порта 9200 внутреннего сервера ( port 9200 inter 2s ).
  • Если проверка на доступность не пройдена, начинается отсчет fall. Через 5 секунд, если вторая попытка оказалась безуспешной, HAProxy отметит сервер MySQL как недоступный ( downinter 5s . fall 2 ).
  • Cервер MySQL автоматически исключается из списка доступных серверов.
  • Как только сервер MySQL возвращается в рабочий режим, если проверка на доступность завершается успешно, запускается отсчет rise, который проверяет, была ли успешной следующая по порядку попытка подключения. Если количество успешных ответов достигнет 3, сервер будет считаться доступным ( rise 3 ).
  • Сервер MySQL автоматически включается в список доступных серверов.
  • Сервер MySQL начинает постепенно принимать соединения в течение 60 секунд ( slowstart 60s ).
  • Сервер MySQL полноценно работает.

  Разделение операций чтения/записи с помощью HAProxy

  HAProxy как балансировщик нагрузки MySQL работает на уровне TCP. Он не понимает запросы MySQL, которые работают на более высоком уровне и пересылаются серверам MySQL. В связи с этим HAProxy пользуется особой популярностью в рамках установок с репликацией multi-master, таких как Galera Cluster и MySQL Cluster, где все бэкенд-серверы MySQL равнодоступны. Все серверы MySQL могут обрабатывать перенаправленные операции чтения/записи. Работа на транспортном уровне также требует меньше вычислительных затрат по сравнению с балансировкой нагрузки обратным прокси, понимающим запросы SQL, таким как MaxScale или ProxySQL.

  Все же это не означает, что HAProxy не подходит для установок с репликацией master-slave. Однако, распределение операций в этом случае происходит сложнее. Операции записи направляются только на Master, в то время как операции чтения могут быть направлены любому узлу, пока узел не начинает отставать.

  Чтобы HAProxy мог обрабатывать операции чтения и записи по отдельности, необходимо:

  • Настроить проверку на доступность и роль сервера MySQL. Скрипт проверки должен:
    • сообщить о роли в репликации (master, slave или none);
    • сообщить об отставании узла slave (если есть slave);
    • должен быть доступен через HAProxy (настраивается через xinetd или порт пересылки).
    • обработчик операций чтения служит для передачи всем узлам запросов чтения;
    • обработчик операций записи служит для передачи операций записи единственному Master.
    • создайте/измените приложение, чтобы отправлять операции чтения и записи соответствующим обработчикам;
    • используйте коннектор приложения, который поддерживает встроенное разделение для операций чтения/записи. Для Java можно использовать Connector/J, для PHP — php-mysqlnd для master-slave. Это сведет к минимуму изменения на стороне приложения.

    Интеграция HAProxy с ClusterControl

    ClusterControl интегрирован с HAProxy для упрощения развертывания и управления балансировщиком нагрузки в сочетании с кластерным бэкендом MySQL, таким как Galera или MySQL NDB Cluster. Также можно добавить существующий/уже развернутый экземпляр HAProxy в ClusterControl, чтобы отслеживать и управлять им напрямую из пользовательского интерфейса ClusterControl.

    

    Для настройки HAProxy перейдите в ClusterControl > Manage > Load Balancer > Install HAProxy и введите нужную информацию:

    • HAProxy Address. IP-адрес или имя узла HAProxy. ClusterControl должен иметь возможность подключаться по SSH без пароля.
    • Listen Port. Порт, который будет прослушивать экземпляр HAProxy. Этот порт будет использоваться для подключения к серверам MySQL с балансировкой нагрузки.
    • Policy. Алгоритм балансировки нагрузки. Поддерживаемые значения:
      • lessconn — соединение устанавливается с сервером с наименьшим числом соединений;
      • roundrobin — каждый сервер используется по очереди, в соответствии со своим весом;
      • source — IP-адрес клиента хэшируется и делится на общий вес, поэтому он всегда будет попадать на один и тот же сервер, пока ни один сервер не выйдет из строя или отключится.
      • ClusterControl скомпилирует последний доступный исходный пакет, загруженный с http://www.haproxy.org/#down.
      • Эта опция требуется только в том случае, когда необходимо использовать последнюю версию HAProxy, или если возникли проблемы с менеджером пакетов дистрибутива ОС. В репозиториях пакетов некоторых старых версий ОС нет HAProxy .
      • Stats Socket. Расположение файла сокета UNIX для запроса статистики. По умолчанию используется /var/run/haproxy.socket , изменять его не рекомендуется.
      • Admin Port. Порт для доступа к странице статистики HAProxy. По умолчанию 9600.
      • Admin User. Пользователь с правами администратора для доступа к странице статистики.
      • Admin Password. Пароль для пользователя-администратора.
      • Backend Name. Имя обработчика для бэкенда. Без пробелов.
      • Timeout Server. Максимальное время бездействия на стороне сервера заданное в секундах.
      • Timeout Client. Максимальное время бездействия на стороне клиента заданное в секундах.
      • Max Connections Frontend. Максимальное количество одновременных подключений к HAProxy.
      • Max Connection Backend per instance. Ограничение числа подключений, которые могут быть сделаны от HAProxy к каждому серверу MySQL. Соединения, полученные после достижения этого значения, HAProxy поставит в очередь. Рекомендуется установить значение меньше, чем max_connections для MySQL, чтобы не допустить переполнения сообщениями.
      • Xinetd allow connections from. Сеть, которой разрешено подключаться к скрипту проверки доступности, выполняемому в рамках xinetd на сервере MySQL.

      Когда поля в диалоговом окне заполнены, нажмите «Install HAProxy», чтобы запустить задание развертывания:

      

      В процессе работы задания ClusterControl выполняет следующие задачи:

      • устанавливает вспомогательные пакеты,
      • настраивает балансировщик,
      • настраивает скрипт mysqlchk (из шаблона) на каждом узле Galera,
      • устанавливает и настраивает xinetd в /etc/xinetd.d/mysqlchk ,
      • регистрирует узел HAProxy в ClusterControl.

      Отследить прогресс развертывания можно в ClusterControl > Logs > Jobs , как показано в примере ниже:

      

      По умолчанию для обслуживания входящих соединений HAProxy будет слушать порт 3307, распределяя запросы между серверами MySQL, входящими в кластер.

      Поскольку при балансировке соединения к серверам MySQL будут открываться не с серверов приложений, а с сервера HAProxy, необходимо добавить права для тех же пользователей, которые используются приложениями, но для IP-адресов, используемых серверами HAProxy:

      mysql> GRANT ALL PRIVILEGES ON mydb.* TO 'appuser'@'ha.pr.ox.yip' IDENTIFIED BY 'password';

      ClusterControl автоматически перезапускает процесс HAProxy в случае сбоя.

      Резервирование HAProxy с помощью Keepalived

      Поскольку подключение всех приложений к кластеру обслуживается через HAProxy, этот узел становится единой точкой отказа, чтобы этого избежать можно настроить два идентичных экземпляра HAProxy (один активный и один резервный) и использовать Keepalived для реализации VRRP между ними. VRRP предоставляет активному серверу HAProxy виртуальный IP-адрес и в случае сбоя передает его резервному серверу.

      При добавлении Keepalived в схему инфраструктура будет выглядеть примерно так:

      

      В этом примере в качестве балансировщика нагрузки перед кластером базы данных используются два узла с переключением IP-адресов. Виртуальный IP-адрес (VIP) будет передаваться между HAProxy №1 (Master) и HAProxy №2 (Backup). Когда HAProxy №1 выходит из строя, VIP передается HAProxy №2, а как только HAProxy №1 снова запускается, VIP возвращается к HAProxy №1, так как он имеет более высокий приоритет. Процесс восстановления после сбоев происходит автоматически и контролируется посредством Keepalived.

      Для установки Keepalived необходимо как минимум два экземпляра HAProxy. Нажмите «Install HAProxy», чтобы установить еще один экземпляр HAProxy, а затем перейдите в ClusterControl > Manage > Load Balancer > Install Keepalived, чтобы установить или добавить существующий экземпляр Keepalived, как показано на следующем снимке экрана:

      

      Убедитесь в том, что сетевая среда поддерживает VRRP (протокол IP 112) для проверки доступности соединения между двумя узлами. Также, если установлен Keepalived версии 1.2.8 и новее, можно разрешить Keepalived работать в среде без многоадресной рассылки, настроив одноадресную рассылку. ClusterControl будет использовать данный режим по умолчанию.

      Более подробно о том, как ClusterControl настраивает Keepalived, что ожидать при аварийном переключении и восстановлении после отказа, читайте в статье.

      Статистика HAProxy

      Помимо развертывания и управления, ClusterControl также дает возможность просматривать статистику HAProxy из пользовательского интерфейса в разделе ClusterControl > Nodes > choose the HAProxy node, как на снимке ниже:

      

      Можно включить/отключить сервер от балансировки нагрузки, отметив/сняв галочку с кнопки-флажка в столбце «Включено». Это очень полезно, когда нужно, чтобы приложение преднамеренно пропустило подключение к серверу, например, для проведения технического обслуживания или тестирования и проверки новых параметров конфигурации или оптимизированных запросов.

      Также можно получить доступ к оригинальной странице статистики HAProxy, подключившись к порту 9600 на узле HAProxy:

      

      Как видно из легенды таблицы, зеленые строки указывают на то, какие серверы доступны, а красные — какие недоступны. Когда сервер становится доступным, справа появляется столбец регулирования (Thrtle), в котором отражается прогресс запуска (slowstart 60s). Этот сервер будет постепенно получать соединения, его вес будет динамически регулироваться в течение 60 секунд, пока не достигнет ожидаемого значения (weight 100):

      

      Устранение неполадок и обходные пути

      В этом разделе приведены рекомендации для решения некоторых распространенных проблем, возникающих при настройке MySQL с HAProxy, Keepalived и ClusterControl.

      Взаимные блокировки MySQL в Galera (Deadlocks)

      Кластер Galera имеет известные ограничения, одним из которых является то, что он использует оптимистическую блокировку всего кластера. Это может вызвать откат некоторых транзакций. С увеличением числа доступных для записи узлов Master частота отката транзакций может увеличиться, особенно если в одном и том же наборе данных есть конфликт записи. Конечно, можно повторить транзакцию, и, возможно, она будет выполнена при повторных попытках, но это увеличит задержку транзакции. Однако некоторые архитектурные решения, применяемые в приложениях, подвержены возникновению ситуации взаимной блокировки (deadlock).

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

      В следующем примере показаны фрагменты обработчиков HAProxy, предназначенных для выполнения операций чтения/записи в равнодоступном кластере на порту 3307 и операций чтения/записи с выделенным сервером на порту 3308:

      listen haproxy_192.168.55.110_3307_multi bind *:3307 mode tcp timeout client 10800s timeout server 10800s balance leastconn option httpchk option allbackups default-server port 9200 inter 2s downinter 5s rise 3 fall 2 slowstart 60s maxconn 64 maxqueue 128 weight 100 server galera1 192.168.55.111:3306 check server galera2 192.168.55.112:3306 check server galera3 192.168.55.113:3306 check listen haproxy_192.168.55.110_3308_single bind *:3308 mode tcp timeout client 10800s timeout server 10800s balance leastconn option httpchk option allbackups default-server port 9200 inter 2s downinter 5s rise 3 fall 2 slowstart 60s maxconn 64 maxqueue 128 weight 100 server galera1 192.168.55.111:3306 check server galera2 192.168.55.112:3306 check backup server galera3 192.168.55.113:3306 check backup

      Подробнее об этом читайте в статье.

      Сервер MySQL не доступен

      Обычно это происходит, когда HAProxy закрыл соединение по тайм-ауту, или соединение закрыто на стороне сервера. Иногда можно увидеть данное состояние, когда сервер перегружен и соединение столкнулось с одним из следующих тайм-аутов (следующие значения используются по умолчанию для переменных MySQL в ClusterControl):

      • connect_timeout — 10 с;
      • deadlock_timeout_long — 50000000 с;
      • deadlock_timeout_short — 10000 с;
      • delayed_insert_timeout — 300 с;
      • innodb_lock_wait_timeout — 50 с;
      • interactive_timeout — 28800 с;
      • lock_wait_timeout — 31536000 с;
      • net_read_timeout — 30 с;
      • net_write_timeout — 60 с;
      • slave_net_timeout — 3600 с;
      • thread_pool_idle_timeout — 60 с;
      • wait_timeout — 28800 с.

      Мы рекомендуем настроить значения net_read_timeout и net_write_timeout с тем же значением, что и для timeout client и timeout server в файле конфигурации HAProxy.

      Оборудование разной производительности

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

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

      . default-server port 9200 inter 2s downinter 5s rise 3 fall 2 slowstart 60s maxconn 64 maxqueue 128 weight 100 server galera1 192.168.55.111:3306 check server galera2 192.168.55.112:3306 check server galera3 192.168.55.113:3306 check weight 50

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

      АВЛ-дерево

      АВЛ-дерево (англ. AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

      АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

      Высота дерева

      АВЛ-дерево с [math]n[/math] ключами имеет высоту [math]h = O(\log n)[/math] .

      Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math] , высоту поддерева [math]T[/math] — как [math]h(T)[/math] .

      Пусть [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] , тогда [math]m_h = F_ — 1[/math] , где [math]F_h — h[/math] -ое число Фибоначчи.

      Если [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] . Тогда как легко видеть, [math]m_ = m_ + m_h + 1[/math] . Равенство [math]m_h = F_ — 1[/math] докажем по индукции.

      База индукции [math]m_1 = F_3 — 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math] .

      Допустим [math]m_h = F_ — 1[/math] — верно.

      Тогда [math]m_ = m_h + m_ + 1 = F_ — 1 + F_ — 1 + 1 = F_ — 1[/math] .

      [math]F_h = \Omega(\varphi^h)[/math] , [math]\varphi = \dfrac< \sqrt+1>[/math] . То есть

      [math]n \geqslant \varphi^[/math]

      Логарифмируя по основанию [math]\varphi[/math] , получаем

      [math]\log_n \geqslant h[/math]

      Балансировка

      Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев [math]|h(L) — h(R)| = 2[/math] , изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева [math]|h(L) — h(R)| \leqslant 1[/math] , иначе ничего не меняет. Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева [math]diff[i] = h(L) — h(R)[/math]

      Для балансировки вершины используются один из 4 типов вращений:

      [math]diff[a] = -2[/math] и [math]diff[b] = -1[/math]

      [math]diff[a] = -2[/math] и [math]diff[b] = 0[/math] .

      [math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]

      [math]diff[a] = -1[/math] и [math]diff[b] = 1[/math]

      [math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 1[/math]

      [math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = -1[/math]

      [math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math] .

      [math]diff[a] = 0[/math] , [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math]

      [math]diff[a] = 1[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

      [math]diff[a] = 0[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

      Малый левый поворот:

      function rotateLeft(Node a): Node b = a.right a.right = b.left b.left = a корректировка высоты a корректировка высоты b

      Большой левый поворот пишется проще:

      function bigRotateLeft(Node a): rotateRight(a.right) rotateLeft(a)

      Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на [math]1[/math] и не может увеличиться.

      Все вращения, очевидно, требуют [math]O(1)[/math] операций.

      Операции

      Добавление вершины

      Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным [math]2[/math] или [math]-2[/math] , то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

      Так как в процессе добавления вершины мы рассматриваем не более, чем [math] O(h) [/math] вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет [math] O(\log) [/math] операций.

      Удаление вершины

      Для простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её, иначе найдём самую близкую по значению вершину [math]a[/math] , переместим её на место удаляемой вершины и удалим вершину [math]a[/math] . От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным [math]2[/math] или [math]-2[/math] , следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

      В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, [math] O(h) [/math] операций. Таким образом, требуемое количество действий — [math] O(\log) [/math] .

      Поиск вершины, минимум/максимум в дереве, etc.

      Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.

      Слияние двух AVL-деревьев

      Дано два дерева [math]T_1[/math] и [math]T_2[/math] , все ключи в [math]T_1[/math] меньше ключей в [math]T_2[/math] , [math]h(T_1) \leqslant h(T_2)[/math] .

      В дереве [math]T_1[/math] удаляем самую правую вершину, назовём её [math]b[/math] . Высота дерева [math]T_1[/math] может уменьшиться на единицу. В дереве [math]T_2[/math] идём от корня всегда в левое поддерево и, когда высота этого поддерева [math]P[/math] будет равна высоте дерева [math]T_1[/math] , делаем новое дерево [math]S[/math] , корнем [math]S[/math] будет вершина [math]b[/math] , левым поддеревом будет дерево [math]T_1[/math] , а правым дерево [math]P[/math] . Теперь в дереве [math]T_2[/math] у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево [math]S[/math] и запускаем балансировку. Таким образом, дерево [math]T_2[/math] будет результатом слияния двух АВЛ-деревьев.

      Дерево [math]T_1[/math] и [math]T_2[/math] до слияния

      

      Дерево [math]T_2[/math] после слияния

      

      Алгоритм разделения AVL-дерева на два

      Алгоритм первый

      Пусть у нас есть дерево [math]T[/math] . Мы должны разбить его на два дерева [math]T_[/math] и [math]T_[/math] такие, что [math]T_ \leqslant x[/math] и [math]x \lt T_[/math] .

      Предположим, что корень нашего дерева [math]\leqslant x[/math] , в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_[/math] . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math] ). Если же корень оказался [math]\gt x[/math] , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.

      Пусть мы пришли в поддерево [math]S[/math] , корень которого [math]\leqslant x[/math] . В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_[/math] . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math] , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL’ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math] ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math] . Теперь нам нужно объединить его с уже построенным ранее [math]T_[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math] ). Для этого мы ищем в дереве [math]T_[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math] , сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_[/math] меньше ключей в [math]T'[/math] , поэтому мы можем это сделать). Теперь в дереве [math]T_[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math] , правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.

      Если мы пришли в поддерево [math]Q[/math] , корень которого [math]\gt x[/math] , совершаем аналогичные действия: делаем NULL’ами ссылки на корень [math]Q[/math] , запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины [math]Q[/math] и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее [math]T_[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_[/math] .

      Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_[/math] . [math]x = 76[/math] .

      

      Рис. 1. Разделение АВЛ-дерева на два.

      Корень дерева [math]\leqslant x[/math] , поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_[/math] . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math] , [math]T'[/math] становится [math]T_[/math] . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math] . Следовательно, строим из него и его правого поддерева [math]T_[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math] . Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_[/math] (рис. 3).

      

      Рис. 2. Создание T’.

      

      Рис. 3. Объединение T’ и T1.

      Далее действуем по алгоритму и в итоге получаем (рис. 4):

      

      Рис. 4. АВЛ-деревья после разделения.

      Данный алгоритм имеет сложность [math]O(\log^ n)[/math] .

      Алгоритм второй

      Рассмотрим решение, которое имеет сложность [math]O(\log)[/math] .

      Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_[/math] и [math]T_[/math] , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево [math]T_[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.

      Пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math] . Тогда сольем его с уже построенным на тот момент [math]T_[/math] ( [math]T_[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_[/math] и [math]h(T_) \leqslant h(S)[/math] ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве [math]S[/math] нашли самое правое поддерево [math]K[/math] , высота которого равна высоте [math]T_[/math] . Тогда сделаем новое дерево [math]T'[/math] , корнем которого будет вершина [math]S[/math] (без нее это дерево является сбалансированным), правым поддеревом — [math]T_[/math] , левым — [math]K[/math] . И подвесим [math]T'[/math] на то место, где мы остановились при поиске [math]K[/math] . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, [math]\gt x[/math] , все аналогично.

      Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла [math]77[/math] . Ключ больше [math]x[/math] , поэтому эта вершина станет деревом [math]T_[/math] и передастся наверх. Теперь мы поднялись в узел [math]75[/math] . Он со своим левым поддеревом станет деревом [math]T_[/math] и мы снова поднимемся наверх в узел [math]70[/math] . Он со своим левым поддеревом снова должен отойти в дерево [math]T_[/math] , и так как теперь дерево [math]T_[/math] уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)

      

      После мы поднимемся в вершину с ключом [math]80[/math] . Она с правым поддеревом отойдет в дерево [math]T_[/math] (рис. 6).

      

      И на последней итерации мы поднимемся в корень дерева с ключом [math]50[/math] , он с левым поддеревом отойдет в дерево [math]T_[/math] , после чего алгоритм завершится.

      Пусть поддеревьев с ключами [math]\leqslant x[/math] оказалось больше, чем поддеревьев с ключами [math]\gt x[/math] . Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту [math]H_[/math] (она может быть не равна [math]1[/math] , если мы придём в [math]x[/math] ). Его мы передаем наверх и вставляем в поддерево высотой [math]H_[/math] . [math]H_ \leqslant H_[/math] , так как разница высот поддеревьев у любой вершины не больше [math]1[/math] , и мы при переходе от [math]H_[/math] к [math]H_[/math] поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за [math]H_ — H_[/math] , получим в итоге дерево высоты не большей, чем [math]H_[/math] . Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за [math]H_ — H_[/math] и так далее. Таким образом мы получим [math](H — H_) + (H_ — H_) + (H_ — H_) + \cdots + (H_ — H_) = H — H_ = O(\log)[/math] .

      Итоговая асимптотика алгоритма — [math]O(\log)[/math] .

      АВЛ-дерево с O(1) бит в каждом узле

      Идея

      В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на [math]1[/math] , то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём фактор баланса. Таким образом в каждом узле будет храниться [math]1[/math] — если высота правого поддерева выше левого, [math]0[/math] — если высоты равны, и [math]-1[/math] — если правое поддерево выше левого.

      Операции

      Операция добавления
      Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Пересчитываем баланс данного узла [math]a[/math] . Если он оказался [math]0[/math] , то высота поддерева с корнем в этой вершине не изменилась и пересчет балансов останавливается. Дальше начинаем подниматься вверх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева изменилась, и подъём продолжается. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]-1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.

      Операция удаления
      Если вершина — лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math] , поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева не изменилась, и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]-1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.

      Балансировка

      Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота — трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины [math]i[/math] как [math]balance[i][/math] . Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины [math]a[/math] , если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения [math]2[/math] или [math]-2[/math] в вершине [math]a[/math] . На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.

      1 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = -1[/math]

      2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 0[/math]

      1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]

      2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 1[/math]

      1 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 1[/math]

      2 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = -1[/math]

      3 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 0[/math]

      1 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = -1[/math] и [math]balance[c] = 0[/math]

      2 вариант: [math]balance[a] = 1[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

      3 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

      Примеры

      Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.

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

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

      Заключение

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

      Похожие публикации:

      1. Где в вао шлифануть гбц
      2. Как подтянуть рулевую рейку на ниссан тиида
      3. Как прокачать суппорт без штуцера
      4. Масло для авд высокого давления какое нужно