Nearly Stateless L4 Balancer: алгоритм и патч на GitHub. Доклад Яндекса

Меня зовут Александр Азимов, я руковожу группой сетевого R&D в Yandex Infrastructure — команде, которая в том числе создаёт системы управления трафиком всего Яндекса. Cегодня мы поговорим о том, как почти полностью избавиться от стейтов на L4-балансировщике.

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

Для тех, кому удобнее смотреть, — запись доклада на эту тему с прошлого nexthop:

Начнём с задач балансировки 

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

Работает ли такая балансировка? Ну конечно, работает. А масштабируется? Тут уже есть некоторый нюанс. Мы рано или поздно упрёмся в размер ECMP‑группы.

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

Поскольку это устройство работает обычно и c IP, и с транспортными заголовками (TCP/UDP), его и называют L4-балансировщиком. Давайте рассмотрим основные механизмы, которые должно реализовать в себе такое устройство.

Асимметрия 

На примере того, как это работает в Яндексе:

• Пакеты получаются L4-балансировщиком.

• TCP‑соединение не терминируется, а L4-балансировщик, используя хеш‑функцию и таблицу соединений, выбирает, в какой сервер надо отправить пакет, и упаковывает пакет пользователя в какой‑то внешний заголовок. В нашем случае это просто IP‑заголовок.

• Пакет долетает до HTTP‑сервера. На HTTP‑сервере на лупбэке есть виртуальный адрес, который анонсирует L4-балансировщик. TCP‑соединение терминируется, а обратный трафик идет напрямую от HTTP‑сервера к клиенту.

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

Health Checks

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

Здесь может быть достаточно много возможностей и гибкости в этих настройках. Дополнительно L4-балансировщик должен проверять доступность сервисов, которые запущены на серверах. Это может быть проверка на основе TCP, проверка на уровне HTTP, но в любом случае должна проверяться доступность. И если сервер недоступен, он должен убираться из группы балансировки.

Hash&State

Остановимся немного глубже на том, как происходит балансировка. В простейшем случае мы берем хеш от заданных полей IP‑заголовка, заданных полей TCP‑заголовка и делим по модулю на число серверов. И таким образом получаем соответствие хеша с сервером.

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

Следовательно, чтобы при изменении списка серверов у нас не рвались TCP‑соединения, нам нужен стейт TCP‑соединений, которые уже прошли через наш балансировщик. Давайте посмотрим, как он возникает в классическом случае.

Как работает классическая L4-балансировка 

Итак, мы получаем SYN‑пакет, считаем хеш‑функцию, выбираем сервер и добавляем информацию о соответствии соединения и сервера в таблицу соединений. При последующих проходах ACK‑пакетов мы проверяем, есть ли у нас запись в таблице соединений. Если записи нет, то этот пакет вообще сбрасывается.

При прохождении ACK‑пакетов обычно у нас нет лукапов по хешрингу. У нас есть первый лукап по хешрингу для SYN‑пакета, и дальше у нас происходят лукапы по таблице соединений.

Напомню ещё раз про TCP‑соединение: мы видим только его половину, только входящий поток. Мы можем добавить соединение при получении SYN‑пакета, а как нам удалить соединение?

Здесь нам не обойтись без таймеров.

При получении SYN‑пакета и добавлении соединения в таблицу соединения мы инициализируем таймер. И после того, как мы получаем ACK‑пакет, мы не добавляем новое соединение, мы находим то соединение, которое уже было, и, например, обновляем таймер или вообще его сбрасываем. Проходит какое‑то время без обновления таймера, он истекает. Мы после этого удаляем TCP‑соединение из таблицы соединений.

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

1. Обычно L4-балансировщик работает только на входящем трафике, то есть трафик маршрутизируется асимметрично.

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

3. И он хранит информацию о соединениях. То есть каждое TCP‑соединение оказывается в таблице активных соединений.

А теперь вопрос: что может пойти не так с балансировщиком, который видит только половину соединения, но при этом хранит информацию об активных соединениях в своей памяти? У нас есть угроза того, что таблица соединений начнёт неконтролируемо расти, особенно если у нас начинаются какие‑нибудь вариации DDoS, например, если это SYN‑флуд.

Как быть с риском DDoS: варианты из литературы

Мы видим SYN‑пакет, мы заводим соединения. Смотрим на элементы всей схемы.

У L3-балансировщика проблемы начинаются, только когда у него заканчивается канальная ёмкость, так что он должен быть неуязвим к такому типу атак. Сервер, используя SYN‑cookie, защищается от распухания таблицы соединений. А L4-балансировщик никак от SYN‑флуда защититься не может, он оказывается слабым звеном.

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

Первый тип — а давайте‑ка мы сделаем offload стейта в сеть, а она как‑нибудь разберётся.

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

Второй вариант — это offload непосредственно в TCP.

У нас есть TCP options, которые не очень широки, но всё же. Предложение заключается в том, что в options мы закодируем непосредственно адрес сервера, на котором терминируется соединение. А ещё давайте закодируем в него идентификатор, чтобы потом L4-балансировщик уже мог использовать именно ID для отправки пакетов на сервер.

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

Какие могут быть альтернативы

Давайте сначала сделаем шаг в сторону и поговорим про консистентное хеширование.

В примере, который я показывал в первой части, при изменении списка серверов у нас радикально менялось соответствие между ключами и серверами. Это создаёт проблемы на L4-балансировщике. Те же самые проблемы могут быть и на L3-балансировщике.

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

Посмотрим это на уже известном нам примере: это настоящий консистентный хеш, который я применил к тому же списку.

Как можно видеть, при добавлении сервера 3 у нас меняются только соответствующие поля. Может быть, нам здесь повезло, потому что на десяти ключах могло случиться разное. Но важно, что консистентный хеш и правда способен уменьшить дельту между хеш‑функцией «до» и хеш‑функцией «после».

Достаточно ли этого, чтобы полностью отказаться от стейтов? Конечно, нет. Мы будем терять меньший процент TCP‑соединений, но если мы просто заменим хеш‑функцию A на хеш‑функцию B, всё равно часть соединений порвётся. А мы находимся в реальном мире, нам ценны наши пользователи и их TCP‑соединения. Но как выйти из ситуации? В момент состояния А у нас одна хеш‑функция, в момент состояния B — другая. И они между собой не встречаются. Нам ничего не остаётся, кроме как менять правила.

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

Нужно ли хранить стейт для той части ключей, которая стабильна? Нет, не нужно. А вот для нестабильной части всё интереснее. Давайте посмотрим детально.

Рассмотрим жизнь одинокого SYN‑пакета.

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

Теперь становится ещё сложнее. Посмотрим на ACK-пакет. Будем здесь идти медленно.

Начало такое же, как было в классической обработке. ACK‑пакет пришёл, мы проверяем, есть ли для него стейт. Если стейт есть, ранее мы получали SYN‑пакет и хешринг был нестабилен, то мы сразу же идём по этому стейту, отправляем пакет. Если стейта нет, мы делаем проверку, а стабилен ли хешринг? Если хешринг стабилен, то нам не нужно заводить стейт, и мы тоже отправляем пакет. А если хешринг не стабилен и для него не было стейта, то это значит, что ранее был SYN‑пакет, который пошёл по старому хешрингу. И значит, мы заводим стейт для этого хеша со старым хешрингом. И тоже его отправляем. Здесь очень важно, как между собой связаны старый и новый хешринг.

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

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

Зачем этот таймер? Он нужен, чтобы получить все ACK‑пакеты нестабильной части хешринга, для которых TCP‑соединение было установлено до изменения списка серверов. Это обеспечивает, что мы гарантированно создадим соединение для всей нестабильной части, пока не истечёт таймер. Какого размера нужен таймер? Точно такой же, какой у нас был для времени жизни TCP‑соединения. Когда этот таймер истечёт, либо мы промаппили все соединения, которые были раньше, либо они завершились просто по тайм‑ауту. Нам не нужно больше ничего: все соединения, которые были нестабильны, мы замаппили, и здесь возможен merge нового хешринга со старым. Через относительно небольшой тайм‑аут мы снова переходим в полностью стабильное состояние без стейтов. Стейты у нас стекут по тайм‑ауту, как это было раньше, но новых стейтов создаваться не будет.

Что показала проверка теории на практике

Когда мы начинали этот эксперимент, YaNet был ещё маленьким, консистентного хеша там не было, и мы взяли балансировщик L4, на котором консистентный хеш уже был. В нашем случае это был IPVS с хеш‑функцией Maglev. Это консистентный хеш, который несколько лет назад предложил Google. Соответственно, на основе реализации Maglev‑хеша мы реализовали наш Maglev Hashing Stateless (MHS) и добавили его в IPVS. Давайте посмотрим на результаты этих экспериментов.

Слева оригинальный ванильный Maglev Scheduler, справа — наш.

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

Хорошо, количество стейтов уменьшилось, а как это повлияет на CPU?

И здесь результаты оказались даже лучше, чем мы ожидали. Серверы были абсолютно идентичны. Это были два брата‑близнеца, перед которыми стоял L3-балансировщик, и обеспечил им равномерное получение нагрузки. На 250 000 RPS на сервере, на котором крутился классический Maglev, утилизация CPU была уже в районе 30%. В нашей реализации, если не было изменения серверов, утилизация была меньше процента. При 10% флапов, то есть 10% непрерывно меняющегося списка серверов, утилизация росла, но она всё равно была в четыре раза меньше, чем в классическом MH от IPVS.

---

Подведём итоги. Наш алгоритм инвариантен относительно реализации конкретного L4-балансировщика. Он позволяет значительно снизить число стейтов. Если серверы стабильны, стейтов просто нет. В реализации IPVS он позволил многократно уменьшить потребление CPU для обработки такого же объёма трафика. Если мы уменьшаем количество стейтов или полностью от них избавляемся, это позволяет нам сделать устройство куда более устойчивым к DDoS‑атакам.

Мы решили не держать реализацию нашего MHS Scheduler в себе и выложили патч на GitHub. Так что вы можете сами перепроверить наши результаты, и если вы используете IPVS в проде, воспользоваться нашей реализацией для повышения устойчивости фермы балансировки к DDoS.