Sticky load balancing

Введение

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

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

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

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

• Как сгруппировать запросы одного и того же пользователя? Обычно группировка осуществляется либо по 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 doesnt 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 users data ahead of us. Data can be inconsistent')
    else:
      local_counter += 1
  

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

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

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

После прочтения предыдущего параграфа должно быть ясно, что sticky load balancing - очень полезная вещь для высоконагруженных масштабируемых проектов. Так какой же load balancer поддерживает cache-aware стратегии распределения запросов? На рынке их over 9000. Они в основном представляют из себя черные ящики с сетевыми интерфейсами. Цена такого ящика обычно начинается с $10K. Но есть бесплатная open source альтернатива, которая не уступает по возможностям и производительности большинству из этих черных ящиков - HAProxy. В ней присутствует поддержка sticky load balancing как на основе source ip, так и на основе произвольных данных в cookies, http headers и url. Так что внимательно читаем мануал и пользуемся на здоровье!

Место солидарности беларусского ИТ-комьюнити

Далучайся!