Просмотров: 12973

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


Эта статья — логическое продолжение предыдущей, своего рода вторая её часть.

Допустим, у нас есть веб-проект, который «вырос» из одного веб-сервера (в дальнейшем веб-сервер будем называть просто «сервер»), т.е. этот сервер больше не может справиться с возросшей нагрузкой, хотя все возможные стандартные способы оптимизации уже были использованы.

Также мы убедились на 100%, что узким местом является именно сервер, а не что-нибудь другое типа пропускной способности сети, базы данных, shared cache (общий кэш, доступный всем серверам по сети) и т.п.

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

load balancing * балансировка нагрузки

Введение

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

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

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

Разделим их на два семейства:

  • cache-unaware. Это семейство стратегий не принимает во внимание возможное различие между данными, закэшированными локально на каждом сервере. Такие стратегии хорошо работают в двух случаях:
    • Если сервера вообще ничего не кэшируют локально (stateless servers). Например, если загрузка данных из удаленного ресусра по сети (будь то база данных, сетевая файловая система, shared cache или что-нибудь еще) требует меньше процессорных ресурсов и времени, чем загрузка этих же данных из локального кэша. Такая ситуация возможна, если cache hit ratio для локального кэша стремится к нулю вследствие большого объема данных, которые требуется закэшировать. Также это возможно при частом обновлении данных, так что при очередном запросе они уже устаревают.
    • Если локальные кэши на всех серверах содержат одни и те же данные. В этом случае без разницы, куда будет направлен следующий запрос.

    Для cache-unaware стратегий лучше всего подходит распределение нагрузки на наименее загруженный в данный момент сервер. Эта стратегия позволяет добиться наименьшего времени ожидания в очереди запросов, в соответствии с результатами моделирования, описанными в моей предварительной статье.

  • cache-aware. Это семейство стратегий направляет запросы таким образом, чтобы максимизировать количество cache hit’ов в локальных кэшах серверов.

  • Наиболее известная из этих стратегий — sticky load balancing (SLB). Она основывается на справедливом предположении, что запросы от одного и того же пользователя нуждаются в общих данных, которые поддаются локальному кэшированию на сервере. К таким данным можно отнести пользовательские настройки или данные, имеющие смысл лишь для конкретного пользователя. Очевидно, что направление запросов от одного и того же пользователя на один и тот же сервер позволяет максимизировать cache hit ratio.

    Эта стратегия хорошо работает при следующих условиях:

    • Если пользователь выполняет более одного запроса к серверу в течение короткого промежутка времени.
    • Если при обработке запросов от одного и того же пользователя сервер нуждается в одних и тех же данных, специфичных для этого пользователя, и эти данные требуют больших вычислительных ресурсов либо потребляют много сетевого трафика при вытягивании их из удаленных сервисов. Например, данные, требуемые для генерации user-specific dashboard’ов.

    Принципы, лежащие в основе sticky load balancing (SLB).

  • Как сгруппировать запросы одного и того же пользователя?
  • Обычно группировка осуществляется либо по IP-адресу входящего запроса, либо по идентификатору пользователя (например, user_id, session_id, auth_token). Идентификатор пользователя может находиться в различных местах. Например, в cookies, в http header’ах, в url’е, в query string’е, в теле POST-запроса.

    Главное преимущество группировки по ip в том, что она может быть осуществлена с минимальными затратами ресурсов на сетевом (IP) или транспортном (TCP) уровнях. Более того, в некоторых ОС типа linux, группировка входящих TCP-подключений по source ip  встроена в ядро.

    Изучите, например, опцию —persistent в DNAT target из iptables или опцию —hashmode=sourceip в CLUSTERIP target там же. Это позволяет построить высокопроизводительный load balancer без применения дополнительного софта. Правда, такой load balancer не сможет автоматически перенаправлять запросы в обход вышедших из строя серверов.

    У группировки по IP есть два недостатка:

    • При смене IP -адреса новые запросы будут направлены на произвольный сервер, тем самым снижая cache hit ratio. Обычно смена ip во время пользовательской сессии происходит достаточно редко, так что этим недостатком можно пренебречь.
    • За одним IP может находиться много народу (например, корпоративный прокси или NAT интернет-провайдера). Все запросы от этих пользователей будут направлены на один и тот же сервер. В итоге он может не справиться с нагрузкой в то время, как другие сервера будут простаивать.

    Группировка по идентификатору пользователя является более затратной в плане потребления ресурсов, т.к. она должна осуществляться на уровне протокола HTTP (aka уровень приложения). С другой стороны, она лишена недостатков группировки по IP.

  • Как выбрать сервер, на который будут направлены запросы пользователя?

  • Основная условие данного принципа — равномерно распределить запросы, сгруппированные по IP или идентификатору пользователя, между имеющимися серверами.

    Рассмотрим некоторые алгоритмы, удовлетворяющие этому условию:

    • Таблица ассоциаций. Для каждой группы запросов выбираем сервер с наименьшим количеством ассоциированных групп запросов, а соответствующую ассоциацию между группой запросов и сервером записываем в специальную таблицу ассоциаций load balancer’а.

    • Преимущества:

      • Идеальное распределение групп запросов на имеющиеся сервера.
      • Минимальная потеря ассоциаций при удалении серверов (failover) — теряются только ассоциации с удаленным сервером.
      • Отсутствие потерь ассоциаций при добавлении серверов — новые группы запросов будут добавляться в ассоциацию к новому серверу до тех пор, пока количество ассоциаций нового сервера не сравняется с количеством ассоциаций остальных серверов.
      • Злоумышленники не могут определить сервер, на который будет направлена данная группа запросов.

      Недостатки:

      • Размер таблицы ассоциаций должен контролироваться, чтобы она не заняла всю доступную память в load balancer’е.
      • Т.к. при ограниченном размере таблицы ассоциаций старые ассоциации удаляются, то происходит их безвозвратная потеря. Это означает, что группа запросов из удаленной ассоциации может быть ассоциирована с произвольным сервером в будущем.
      • При наличии нескольких load balancer’ов таблица ассоциаций должна быть синхронизирована между ними. Иначе они будут направлять запросы из одной и той же группы на различные сервера.
      • Таблица ассоциаций может быть безвозвратна утеряна при выходе из строя load balancer’а. В этом случае cache hit ratio резко упадет до нуля и будет оставаться низким, пока не заполнится новая таблица ассоциаций.

      • Простое хэширование. Для хэширования обычно используется следующая формула:
      • server_id = hash(group_key) % servers_count

        где:

        • server_id  — порядковый номер сервера из пула серверов размером servers_count ;
        • group_key  — ключ, по которому производится группировка входящих запросов. Например, IP  или user_id .
        • hash  — хэш-функция, дающая равномерное распределение значений для заданных group_key ’ев.

        При использовании этого алгоритма нет необходимости хранить какие-либо ассоциации на стороне load balancer’а, поэтому он лишен всех недостатков алгоритма с таблицей ассоциаций.

        Недостатки:

        • Полная потеря ассоциаий при удалении (failover) и добавлении серверов. Это автоматически приводит к нулевому cache hit ratio до тех пор, пока не закэшируются новые данные.
        • Злоумышленники могут вычислить сервер, на который будет направлена данная группа запросов, зная параметры вышеуказанной формулы. Это может быть использовано в следующей атаке: допустим, злоумышленникам известен group_key пользователя, на которого они хотят направить свою атаку. Также им известна какая-нибудь брешь в серверном ПО, которая может быть использована для компрометации пользователей, порче их данных или вывода из строя серверов. Тогда они могут подобрать запрос таким образом, чтобы его group_key попадал на сервер, который обслуживает целевого пользователя, после чего воспользоваться брешью на этом сервере для своих черных нужд
        • Consistent hashing.

        • Этот алгоритм имеет те же преимущества и недостатки, что и простое хэширование. Но, в отличие от простого хэширования, consistent hashing теряет только небольшую часть ассоциаций между группами запросов и серверами при удалении и добавлении серверов. Так что этот алгоритм можно считать наилучшим для ассоциации серверов с пользовательскими запросами.

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

    Сравнение cache-aware и cache-unaware стратегий распределения запросов

    Перечислим преимущества cache-aware стратегии перед cache-unaware стратегией:

    • Хорошо оптимизированный проект (т.е. активно использующий локальные кэши для минимизации расходов процессорного времени и сетевого трафика), работающий на одном сервере, намного легче перенести на несколько серверов с помощью cache-aware load balancing.
    • Уменьшает нагрузку на сервера и увеличивает количество запросов, которые могут быть обработаны каждым сервером в единицу времени, т.к. не нужно тратить процессорное время на генерацию данных, если они уже присутствуют в локальном кэше. Также, в отличие от shared cache, локальный кэш может содержать готовые данные, которые не нуждаются в трате сетевого трафика и процессорного времени на serialization перед записью и deserialization перед чтением.
    • Уменьшает нагрузку на внешние источники данных и сеть между серверами и внешними источниками данных, т.к. не нужно тянуть данные, если они уже присутствуют в локальном кэше.
    • Уменьшает время обработки запроса, т.к. не нужно ждать ответа от внешних источников данных, если они уже присутствуют в локальном кэше.
    • Уменьшает суммарный объем памяти, необходимый на локальные кэши, т.к. данные, закэшированные на разных серверах, почти не дублируются. С другой стороны, это дает возможность закэшировать больше различных данных в фиксированном объеме локальных кэшей, тем самым увеличивая эффективный объем кэша.

    Недостатки cache-aware стратегии перед cache-unaware стратегией:

    • Более высокое среднее время ожидания в очереди запросов по сравнению с round robin и least loaded при одинаковой средней загрузке серверов. Этот недостаток нивелируется тем, что cache-aware стратегия обычно может обработать большее количество запросов в единицу времени при сравнимой загрузке серверов по сравнению с cache-unaware стратегиями благодаря вышеуказанным преимуществам.
    • Более сложная синхронизация локальных кэшей по сравнению с shared cache. В случае, если данные кэшируются только в shared cache, текущий запрос может обрабатываться на произвольном сервере, т.к. актуальные данные для данного пользователя всегда можно попытаться вытянуть из общего кэша.

    В cache-aware стратегии же данные могут быть рассинхронизированы, если группа запросов попадет на короткое время на «чужой» сервер, а затем снова перекинется на «свой» сервер. Это возможно в случае кратковременного ложного «выхода из строя» одного из серверов, который быстро возвращается в строй обратно без потери локального кэша.

    Допустим, при запросе на «чужом» сервере пользовательские настройки были изменены. «Свой» сервер ничего про это не знает и использует локально закэшированные настройки пользователя, которые уже устарели.

    Каков же выход из этой ситуации? Можно вообще «забить» на эту проблему, если случаи ложного «выхода из строя» серверов достаточно редки и вас не смущает наличие пары недовольных пользователей, потерявших свои данные из-за этого (к слову, это типичный способ решения данной проблемы в высоконагруженных проектах). Можно перед каждым использованием данных из локального кэша проверять наличие изменений во внешнем хранилище. Но это сильно портит вышеуказанные преимущества cache-aware стратегии.

    Намного лучше воспользоваться помощью shared cache, но использовать его не по прямому назначению — хранение закэшированных данных, а в качестве вспомогательного средства для optimistic locking. Для этого для каждой группы запросов создаем отдельную запись в shared cache, где хранится счетчик изменений данных, входящих в локальный кэш для данной группы. Обычно такой счетчик называется generation counter. Начальное значение этого счетчика выбирается случайным образом. В начале каждого запроса пользователя считываем значение соответствующего счетчика из shared cache и сравниваем его с локальным значением.

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

    Ниже представлен соответствующий псевдокод:

    new_random_counter = random.randint(0, 0xffffffff)
    remote_counter = shared_cache_cas(request_group_key, None, new_random_counter)
    if remote_counter is None:
      remote_counter = new_random_counter
    if remote_counter != local_counter:
      load_new_data_from_backend(request_group_key)
      local_counter = remote_counter
    is_data_changed = process_request(request_group_key)
    if is_data_changed:
      save_data_to_backend(request_group_key)
      remote_counter = shared_cache_cas(request_group_key, 
          local_counter,local_counter + 1)
      if remote_counter is None:
        logging.error('It looks like shared cache doesn\
           't work at the moment')
      elif remote_counter != local_counter:
        # This case is unlikely for cache-aware load balancing, 
        # since it means the user sent two update requests in 
        # a short period of time and these requests were 
        # directed by load balancer to distinct servers.
        logging.error('It looks like somebody updated 
            user\'s data ahead of us. Data can be inconsistent')
      else:
        local_counter += 1

    Хм. Почему бы не использовать shared cache по прямому назначению вместо того, чтобы городить огород с локальными кэшами и generation counter’ами? Ведь в результате мы вынуждены обращаться минимум один раз к shared cache при обработке каждого запроса. А преимущество в том, что в этом случае мы не тратим процессорное время на сериализация больших объемов данных и не засоряем сетевой трафик между серверами и shared cache этими данными.

    Если вам кажется, что овчинка выделки не стоит, то вы всегда можете «забить» на проблемы синхронизации, т.к. в случае SLB эти проблемы возникают лишь в исключительных случаях.

    На просторах Интернета можно наткнуться на FUD о том, что sticky load balancing — это вчерашний день и всем нужно срочно переходить на stateless serversshared cache. В качестве главного аргумента приводится то, что SLB может оказаться виновно в потере пользовательских данных при выходе из строя сервера, хранящего данные из пользовательских сессий.

    load balancing * балансировка нагрузки

    Что ж, такое возможно при неправильном понимании основ кэширования — не стоит полагаться на сохранность данных в кэше, т.к. они в любой момент могут быть утеряны. Это может произойти различными путями — например, кэш разросся до огромных размеров и его нужно сжимать, удаляя оттуда какие-нибудь данные. Или сервис, отвечающий за кэширование, накрылся медным тазом. Так что хранить критические данные пользовательских сессий в локальном кэше без помещения их в хранилище, гарантирующем их сохранность — верх безрассудства. Как видите, вина sticky load balancing в неправильном понимании основ кэширования равняется 0.0 .

    Кроме того: какую прорву локального трафа между кэш-сервером и серверами кластера генерит подход stateless serversshared cache — его пропагандисты, судя по всему в реальной жизни даже не видели. В большинстве случаев понятно, почему им действительно пофиг эта величина, так как они используют Infiniband или 100-Gbit ethernet в локальной сети. Во всех остальных случаях это всё-таки лучше иметь в виду.

    Случай файлообменников

    Файлообменники — это как раз тот распространенный случай, когда sticky load balancing намного предпочтительнее, чем cache-unaware стратегии. Это — огромные файлопомойки, где любой пользователь может скачивать любой файл. Например, типичные представители из этого многочисленного ныне племени: рапидшара и подобные, различные фотоальбомы и медиаколлекции в соцсетях, ютуб, дропбокс и так далее.

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

    Для файлопомоек также можно весьма эффективно использовать CDN’ы или кэширующие обратные прокси (aka веб-ускорители).

    Реклама вместо заключения

    После прочтения предыдущего параграфа должно быть ясно, что SLB — очень полезная вещь для высоконагруженных масштабируемых проектов. Так какой же load balancer поддерживает cache-aware стратегии распределения запросов? На рынке их over 9000. Они в основном представляют из себя черные ящики с сетевыми интерфейсами. Цена такого ящика обычно начинается с $10K.

    Но есть бесплатная open source альтернатива, которая не уступает по возможностям и производительности большинству из этих черных ящиков — HAProxy. В ней присутствует поддержка SLB как на основе source ip , так и на основе произвольных данных в cookies, http headers и url. Так что внимательно читаем мануал к нему и пользуемся на здоровье!

    Ещё раз напомню, что это статья-окончание — её начало «Планирование нагрузки на сервер» было опубликовано ранее. В качестве практического введения в тему (кому это нужно) рекомендую статьи Грегора Рота «Server load balancing architectures»(часть 1, часть 2) с примерами на Java. Вообще следует также учитывать, что в контексте активного использования балансировки на клиентской стороне иногда также появляется множество тонких особенностей (например, у cookie проявляется новая специфика — session affinity и sticky session и т.д.). В этом смысле очень интересна презентация типового решения Load Balancing with Apache, к примеру вот тамошний пример реализации Sticky sessions in PHP.

    twitter.com facebook.com vkontakte.ru odnoklassniki.ru mail.ru ya.ru pikabu.ru blogger.com liveinternet.ru livejournal.ru google.com bobrdobr.ru yandex.ru del.icio.us

Подписка на обновления блога → через RSS, на e-mail, через Twitter
Теги: , , , , , ,
Эта запись опубликована: Четверг, 5 января 2012 в рубрике МненияОбзоры.

3 комментария

Следите за комментариями по RSS
  1. Ссылки пошто на английскую вики? вместо "http://en.wikipedia.org/wiki/Application_Layer" лучше "http://ru.wikipedia.org/wiki/Прикладной_уровень"

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

    - реверсивный кэш-прокси

    - Ну и CDN как обобщенный случай реверсивных кэш-прокси

    Радикально меняют картину. Особенно в сочетании с балансировщиком.

  3. Причем они не только и не столько для файлопомоек, сколько для вполне себе симпатичных фронт-эндов.

Оставьте комментарий!

Не регистрировать/аноним

Используйте нормальные имена. Ваш комментарий будет опубликован после проверки.

Зарегистрировать/комментатор

Для регистрации укажите свой действующий email и пароль. Связка email-пароль позволяет вам комментировать и редактировать данные в вашем персональном аккаунте, такие как адрес сайта, ник и т.п. (Письмо с активацией придет в ящик, указанный при регистрации)

(обязательно)


⇑ Наверх
⇓ Вниз