Типичная схема бэкэнд‑приложения выглядит стандартно: группа экземпляров сервиса и балансировщик перед ними. Пользователь отправляет запрос на балансировщик, а тот проксирует его на конкретный инстанс.
Эта схема отлично работает на лёгких API‑запросах, но рассыпается, как только трафик становится тяжелее. В случае с Яндекс Диском речь идёт о массовой загрузке файлов.
Меня зовут Илья Абрамов, я разработчик в Диске, и в статье я расскажу, почему для загрузки данных нам пришлось отказаться от классических балансеров, как наш первоначальный алгоритм страдал от высокой дисперсии загруженности узлов, и какую архитектуру мы применили, чтобы заметно сгладить этот разброс и статистически улучшить показатели утилизации сети.
Проблема сетевых лимитов
В современных дата‑центрах серверы обычно оснащены сетевыми картами на 10 или 25 Гбит/с.
Если в качестве балансировщика используется программное L7-решение (например, Nginx или HAProxy), оно становится узким местом:
Полоса пропускания: весь входящий трафик должен пройти через балансировщик. Если пользователи суммарно льют 100 Гбит/с, вам нужно либо 10 балансировщиков на полной нагрузке, либо невероятно дорогое аппаратное решение.
Масштабируемость: возникает архитектурный перекос. Чтобы наращивать количество бэкендов, вам приходится пропорционально увеличивать количество балансировщиков.
Кроме того мы на ровном месте увеличили нагрузку на сеть дата‑центра, ведь данные сначала передаются от пользователя в балансер, а затем те же данные пересылаются из балансера в сервис.
В Диске мы в свое время приняли радикальное решение: полностью отказаться от промежуточных балансировщиков при загрузке файлов. В нашей текущей архитектуре путь данных выглядит иначе: пользователь отправляет тяжелый трафик напрямую в сервис.
Но чтобы это заработало и не превратилось в хаос, нам пришлось переосмыслить сам принцип того, как клиент находит нужный сервер.
Специфика Яндекс Диска добавляет проблем: миллионы пользователей с разной скоростью интернета загружают файлы самых разных размеров — от крошечных документов до многогигабайтных архивов.
Мы не можем позволить клиенту самому выбирать узел для загрузки — это привело бы к хаотичному распределению нагрузки и смерти отдельных серверов. Балансировка всё равно необходима, но мы решили делать её до начала передачи данных.
Мы разделили процесс на два типа запросов:
Control‑запросы (управляющие): это легковесные HTTP‑запросы. Их задача — получить добро на загрузку и узнать адрес целевого сервера. Они проходят через стандартный балансировщик, так как почти не создают сетевой нагрузки.
Data‑запросы (данные): Те самые тяжеловесные потоки байтов, которые идут напрямую от пользователя к выбранному серверу, минуя промежуточные звенья.
В итоге архитектура загрузки в Диске кристаллизовалась в виде двух ключевых компонентов:
Балансерун (Balancer). Его работа — выбрать наиболее подходящий экземпляр сервиса для конкретного пользователя. Чтобы делать это эффективно, Балансерун в реальном времени держит в памяти актуальный список всех «живых» серверов (через Service Discovery) и мониторит их состояние. На выходе он отдает пользователю уникальную ссылку на загрузку.
Кладун (Uploader). Это сервис, который принимает входящий data‑запрос по прямой ссылке и занимается непосредственно сохранением файла в целевое хранилище.
Схема взаимодействия выглядит так:
Пользователь спрашивает у Балансеруна: «Куда мне положить файл?»
Балансерун анализирует загрузку системы и отвечает: «Вот тебе ссылка на сервер № 3».
Пользователь открывает прямое соединение с этим сервером и отправляет данные в Кладун.
Стандартные алгоритмы балансировки
Разделение на Control и Data‑запросы было придумано ради экономии сетевых ресурсов. Сеть — самый критичный и конечный ресурс в нашей системе. Если хост перегружен, пользователи либо вообще не могут загрузить файл, либо сталкиваются с катастрофическим падением скорости.
Наша идеальная цель — равномерная утилизация сети на всех аплоадерах. Но, как выяснилось, найти алгоритм для достижения этого идеала не так‑то просто. Давайте разберем это на примере стандартных подходов.
Моделируем Random‑балансировку
Представим систему из трех аплоадеров и одного балансировщика. Входящей нагрузки пока нет.
Приходит первый пользователь. Балансировщик выбирает узел № 1. Пользователь начинает лить файл на скорости 500 Мбит/с.
Приходит второй пользователь. Поскольку выбор случайный, есть вероятность, что он снова попадет на узел № 1. Допустим, его скорость — 700 Мбит/с. К этому моменту первый пользователь еще не закончил сессию, и суммарная нагрузка на первый узел вырастает до 1200 Мбит/с.
Приходит третий пользователь — и «рандом» снова отправляет его на первый узел. Нагрузка достигает 1700 Мбит/с.
В итоге у нас есть перекос: первый аплоадер задыхается, в то время как два других простаивают с нулевой нагрузкой.
Почему так происходит? Если посмотреть на это с точки зрения теории вероятностей, мы для каждого аплоадера несколько раз выбираем значение скорости из распределения и суммируем их. Согласно центральной предельной теореме, сумма этих независимых случайных величин будет иметь распределение, близкое к нормальному.
Проблемы Random балансировки
«Нормальное распределение» в контексте сетевой нагрузки значит, что в среднем наши аплоадеры будут загружены умеренно, но у распределения всегда будут «хвосты». В этих хвостах находятся узлы, которые либо простаивают, либо перегружены до предела.
Проблема в том, что у нормального распределения есть стандартное отклонение. А в масштабах Яндекс Диска это отклонение означает, что всегда будут узлы, нагруженные значительно сильнее (или слабее) среднего.
Ещё одна проблема заключается в высокой дисперсии. Она гарантирует, что перегруженных аплоадеров будет не один или два, а достаточно много, чтобы это стало заметно пользователям.
Может показаться, что строгая очередность (Round‑Robin) решит проблему, ведь она распределяет количество запросов идеально поровну. Но давайте смоделируем ситуацию:
У нас есть два пустых аплоадера. Первый пользователь уходит на узел № 1 и начинает лить данные на скорости 500 Мбит/с.
Второй пользователь отправляется на узел № 2. Но он зашел с мобильного интернета где‑нибудь в дороге, и его скорость — всего 10 Мбит/с.
Приходит третий пользователь. Очередь вернулась к началу, и мы снова отправляем его на узел № 1. Допустим, он добавляет еще 1000 Мбит/с.
Итог: На первом узле — 1500 Мбит/с, на втором — жалкие 10 Мбит/с. Мы снова получили критический перекос.
Проблемы Round‑Robin и Random идентичны: они никак не учитывают реальную скорость загрузки. Мы по‑прежнему суммируем случайные величины с огромным разбросом и получаем нормальное распределение с гигантской дисперсией.
Переход к балансировке с обратной связью
Стало очевидно: стандартные алгоритмы нам не подходят. Чтобы победить дисперсию, нам нужно научить балансировщик «видеть», что происходит на бэкендах.
Мы решили пойти по пути сбора метрик. Идея следующая: раз в K секунд каждый аплоадер передает балансировщику пакет данных о своем состоянии. Мы собираем всё, что может влиять на успех загрузки:
Текущую утилизацию сети;
Нагрузку на дисковую подсистему;
Размер очереди активных загрузок;
Другие системные параметры.
Затем мы агрегируем эти данные в единый коэффициент, который называем суммарной загрузкой узла. Теперь задача балансировщика сводится к простому правилу: при поступлении запроса выбирать узел с минимальным значением этого коэффициента.
Ловушка «слепого» периода
Давайте посмотрим, что произойдет, если мы будем просто выбирать наименее загруженный узел (алгоритм Least Loaded), опираясь на периодические отчеты от аплоадеров.
Представим систему: два балансировщика и три аплоадера. Один узел свободен, а на два других кто‑то загружает файлы со скоростью 10 Мбит/с.
Приходит первый пользователь. Балансировщик видит, что узел № 2 абсолютно пуст, и отправляет запрос туда. Пользователь начинает лить данные на скорости 500 Мбит/с.
Но есть нюанс: мы собираем метрики раз в K секунд. В этом промежутке балансировщики остаются «слепыми» — они не знают, что на втором узле только что началась тяжелая сессия.
Приходит второй пользователь, затем третий... Балансировщики, сверяясь со старыми данными, по‑прежнему считают второй узел самым свободным и продолжают направлять трафик именно туда.
Когда время K наконец проходит и мы собираем свежие метрики, оказывается, что второй узел уже безнадежно перегружен, в то время как остальные простаивали. Из‑за задержки в обратной связи система сама создает перекосы, которые должна была устранять.
Чтобы сгладить этот эффект, мы решили скорректировать логику. Вместо того чтобы всегда выбирать один «самый лучший» узел, мы будем выбирать случайный узел из N самых свободных. Такой алгоритм назовём Top‑N Random.
Top‑N Random балансировка
Идея в том, что небольшая доля случайности размазывает нагрузку в те самые «слепые» периоды. Если в топе окажутся три примерно одинаково свободных узла, балансировщики распределят новых пользователей между ними, а не положат какой‑то один конкретный сервер.
Моделирование Top‑N Random показало, что мы лишь снижаем вероятность катастрофы, но не исключаем её. Всегда существует шанс, что несколько балансировщиков одновременно выберут один и тот же узел из топа, и мы снова получим перегруженный «хвост» распределения. С ростом N проблема сглаживается, но мы возвращаемся к тому, с чего начали — к высокой дисперсии обычного рандома.
Стало ясно: нам была нужна глобальная переработка логики. Чтобы решить эту задачу, мы запустили полноценный НИОКР совместно с аспирантами ИТМО. Мы передали им обезличенные данные и профили нагрузок Яндекс Диска, а коллеги провели глубокий аудит наших подходов.
Анализ выявил три фундаментальные проблемы:
Балансировщики работают изолированно. Если один Балансерун назначил тяжелую загрузку на Кладуна, остальные узнают об этом слишком поздно.
Сбор статистики раз в K секунд делает систему слишком медленной для динамично меняющегося трафика.
Мы не учитывали два параметра запроса — скорость пользователя и размер файла.
Результатом этой работы стал алгоритм HOBA (Hierarchical Optimized Balancing Algorithm).
HOBA‑балансировка
Архитектура НОВА строится на трёх китах, которые закрывают слабые места предыдущих подходов:
Локальные пулы. Мы распределили всех Кладунов (аплоадеров) по непересекающимся пулам. Теперь каждый балансировщик локально обновляет состояние каждого узла в своем пуле сразу в момент назначения загрузки. Балансировщик помнит, сколько работы он уже отправил на конкретный сервер, не дожидаясь подтверждения от самого сервера.
Учёт скорости. Теперь мы храним и используем данные о скорости пользователя. Это может быть скорость текущей сессии, средняя скорость последних загрузок этого клиента или медианное значение по системе, если данных о пользователе нет. Балансировщик оперирует не количеством запросов, а прогнозируемой нагрузкой на канал.
Изменение роли глобальной статистики. Сбор статистики раз в K секунд остался, но его роль изменилась. Теперь эти данные используются не для принятия мгновенных решений, а для корректировки «картины мира» балансировщика. Глобальные метрики исправляют накопленную погрешность локальных расчетов. Благодаря этому интервал K удалось существенно увеличить, разгрузив тем самым шину управления.
HOBA в динамике: локальное знание и глобальные риски
Представим систему из двух балансировщиков. У каждого в ведении свой непересекающийся пул из двух Кладунов“ Когда приходит запрос, Балансерун выбирает свободный узел в своем пуле и мгновенно прибавляет к его виртуальной нагрузке ожидаемую скорость пользователя. Теперь его «картина мира» актуальна в ту же миллисекунду, без ожидания отчётов по сети.
Казалось бы, задача решена. Но в распределенных системах исправление одной проблемы неизбежно подсвечивает новые:
Точка отказа: если один балансировщик падает, его пул аплоадеров мгновенно выпадает из работы. Никто другой не знает о существовании этих узлов, и мощности простаивают.
Проблема масштабирования: если мы добавляем в систему новый Балансерун, он стартует с пустым пулом и никого не балансирует, пока мы вручную не перенарежем ресурсы. А при добавлении нового Кладуна, он не будет назначен ни в какой пул, а значит не сможет принимать нагрузку.
Нам понадобился механизм динамического распределения аплоадеров по пулам балансировщиков. К алгоритму перераспределения пулов (ребалансировке) мы предъявили два жестких требования:
Децентрализация: мы сознательно отказались от роли «главного координатора». В высоконагруженных системах центральный узел — это всегда риск: либо он сам станет бутылочным горлышком, либо его падение парализует всю логику балансировки.
Минимизация миграций: каждый Балансерун накапливает уникальную локальную информацию о Кладунах в своем пуле (текущие сессии, предсказанные скорости). Если при изменении состава системы мы начнём хаотично перекидывать аплоадеров между пулами, эта информация потеряется. Нам придётся ждать следующего сбора метрик (интервал K), и в это время система снова будет «слепой».
Почему обычный хэш не работает
Первое, что приходит на ум при необходимости распределить ресурсы — это классическое хэширование с остатком от деления. Пронумеруем всех Балансерунов (0,1,..., M−1, где М — число Балансерунов в системе). Для каждого Кладуна вычислим хэш от его ID и возьмем его по модулю количества балансировщиков:
pool_id = hash(uploader_id) % MНо как только один Балансерун падает, число M меняется. Из‑за смены делителя остаток от деления пересчитывается для всех узлов сразу. В итоге почти каждый Кладун мигрирует в новый пул.
Для нас это катастрофа: мы мгновенно теряем всю накопленную локальную статистику на всех балансировщиках. Система забывает, кто и с какой скоростью сейчас грузит файлы, и на интервал K (до следующего сбора метрик) мы остаемся совершенно беззащитными перед перегрузками.
Rendezvous Hashing
Чтобы решить проблему массовых миграций, мы внедрили алгоритм Rendezvous Hashing (также известный как Highest Random Weight Hashing).
Его логика в корне отличается от деления по модулю:
Для каждой пары «Аплоадер + Балансировщик» вычисляется определённая весовая функция.
Аплоадер назначается в пул того балансировщика, для которого эта функция выдает максимальное значение.
Если один балансировщик падает, пересчёт происходит только для тех Кладунов, которые принадлежали именно ему. Все остальные пары «Аплоадер + Балансировщик» сохраняют свои веса относительно друг друга, а значит, остаются в своих прежних пулах.
Мы получили то, что искали: минимальное количество перемещений при изменении конфигурации. Локальные данные на живых балансировщиках сохраняются, а нагрузка от упавшего узла равномерно и предсказуемо распределяется между оставшимися.
Борьба с перекосами пулов
Rendezvous‑хэширование отлично справляется с миграциями: если Балансерун падает, свои пулы меняют только Кладуны, которые были к нему привязаны.
При добавлении нового узла система так же плавно перераспределяется. Благодаря равномерности хэш‑функции, в среднем мы получаем равные по размеру пулы.
Но «в среднем» — опасная ловушка для Highload‑систем. Случайность есть случайность, и в реальности мы можем столкнуться с перекосами:
один балансировщик может получить в свой пул три аплоадера, а другой — ни одного.
если часть Кладунов в одном пуле выйдет из строя, балансировщик останется с недостаточным ресурсом, в то время как соседние узлы будут простаивать.
Чтобы избежать такой несправедливости, мы ввели механизм ограничения размера пула.
Мы определили «идеальный» размер пула как:
Теперь процесс назначения Кладуна в пул выглядит чуть сложнее, чем просто поиск максимума:
Мы вычисляем веса для всех пар «Аплоадер + Балансировщик».
Проверяем балансировщик с самым высоким весом. Если его пул еще не заполнен — задача решена.
Если же пул лидера уже достиг своего лимита (
max_pool_size), мы просто берем следующий по величине результат весовой функции.
Пример: допустим, Кладун с ID 4 по всем расчетам должен попасть в пул к Балансеруну № 1. Но этот балансировщик уже укомплектован под завязку. Тогда алгоритм смотрит, кто выдал второй лучший результат веса — например, Балансерун № 0 — и отправляет аплоадера к нему.
Вообще, если ограничивать размер пулов только сверху, то при небольшом (но отличном от нуля) остатке от деления uploaders_num на balancers_num, можно получить ситуацию, когда пул одного балансера заполнен ровно на этот остаток.
Чтобы избежать такого, можно подпирать размер пула балансерунов не только сверху, но и снизу.
Введем число
Для начала будем назначать аплоадеры только на те балансеры, размер пулов которых меньше min_pool_size (заметим, что в конце концов каждый балансер будет иметь пул размера min_pool_size). Затем для оставшихся аплоадеров выберем балансер, дающий максимум весовой функции — тогда разница между наиболее и наименее заполненными пулами не будет превышать единицы.
Такое решение, хотя и несколько ухудшает свойство рандеву хеширования, обеспечивающее нам минимум перемещений Кладунов между пулами, избавляет нас от проблем с перекосом пулов. Теперь нагрузка распределяется по балансировщикам максимально плотно и равномерно, исключая ситуации, когда один узел перегружен, а другой полностью свободен.
Несмотря на все преимущества HOBA, мы не строим иллюзий — это не «серебряная пуля». Над нашими Балансерунами по‑прежнему стоит внешний L7-балансировщик. Теоретически сохраняется риск, что он отправит всех «быстрых» пользователей на один узел, а «медленных» — на другой. Вероятность такого сценария крайне мала, но она существует, и на этом уровне абстракции мы принимаем это как неизбежную погрешность.
Результаты: что нам дал новый алгоритм
Если сравнить распределение загрузки сети до и после внедрения HOBA, разница очевидна:
На графике распределения «холм» нового алгоритма (синий) стал уже и выше, что соответствует снижению стандартного отклонения на 22%. Это означает, что мы снизили количество тех самых опасных «хвостов», что привело к паданию загруженности сети в нашей системе.
Важно отметить, что предлагаемый алгоритм в большей степени призван решать именно проблемы, связанные с высокой дисперсией сетевой загруженности аплоадеров, возникающей вследствие большого разброса скоростей интернета пользователей. Так, например, даже в системе, где все пользователи загружают одинаковые по размеру файлы, наш алгоритм все еще значительно увеличивал бы равномерность утилизации сети среди Кладунов.
Выводы
К каким урокам мы пришли в процессе этого пути:
Любой математически идеальный алгоритм может разбиться о реальность ваших данных. Всегда лучше начать с анализа того, как именно ведут себя ваши пользователи.
Типовые инструменты вроде Round Robin решают большинство задач. Начинать строить свой НИОКР стоит только тогда, когда нагрузки становятся действительно аномальными.
Ищите вдохновение в смежных областях. Хорошие идеи часто лежат на поверхности, но в соседнем отделе. Rendezvous‑хэширование — классика шардирования баз данных, но, как выяснилось, оно идеально подходит и для динамического распределения пулов балансировки.