Всем привет! Меня зовут Никита Звонарёв, я работаю в команде Яндекс 360 и занимаюсь разработкой бэкенда Яндекс Мессенджера. В статье я расскажу о том, как устроен наш ключевой сервис Fanout, через который проходят все запросы чатов, и как наша команда шаг за шагом дорабатывала алгоритмы балансировки, чтобы выдерживать сотни тысяч RPS без сбоев и утренних страданий дежурного инженера.

Fanout можно считать сердцем Мессенджера: он отвечает за такие запросы, как «выдать историю сообщений чата», «обработать отправленные сообщения», «посчитать количество непрочитанных сообщений» и тому подобное. Fanout держит большую нагрузку — несколько десятков машин обрабатывают более 300 тысяч RPS. Сервис написан на C++, а его особенность заключается в наличии собственной системы балансировки нагрузки. Долгое время она работала хорошо, но в какой‑то момент команда столкнулась с трудностями — расскажу о том, как мы их разруливали.

Как устроен Fanout — сердце Мессенджера

В статье мы поговорим не про все части Мессенджера, а только про его «сердце» — Fanout.

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

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

Как устроено шардирование нагрузки

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

Есть важное ограничение — так называемая partition map. Partition map — это схема, которая для каждого воркера описывает, какие партиции можно ему назначить.

Эта схема избыточная: одну и ту же партицию можно назначить разным воркерам. Но есть нюанс — схема несимметричная. Мы не можем произвольно назначить любую партицию на любой воркер. Это сделано для того, чтобы сократить объём метаданных, которые нужно держать в памяти на каждом воркере. Если бы мы не использовали partition map, пришлось бы кешировать метаданные всего сервиса, а для этого просто не хватило бы оперативной памяти.

В итоге partition map помогает снизить нагрузку на кеширование метаданных, но накладывает ограничения на выбор воркера для партиции. Задача балансировки в таком контексте формулируется так: активный балансер должен решить, как назначать партиции воркерам в разных ситуациях. Таких ситуаций как минимум три:

1. Отказ воркера (например, если он стал недоступен по сети).

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

3. Выкатка новой версии Fanout.

Есть ещё случай с расширением кластера, но он уже за рамками этой статьи.

Первая версия балансировщика: решаем вопросы банхаммером

Давайте посмотрим, как всё это работало в первой версии нашего алгоритма балансировки. Важно помнить, что всё распределение должно удовлетворять ограничениям partition map — партиция может попасть только на разрешённые воркеры.

Исторически первая версия балансировщика была написана несколько лет назад. Логика была довольно простой. Сначала мы считывали текущее распределение партиций по воркерам из базы. Затем отправляли healthcheck‑запросы на все воркеры — по сути, обычный пинг. Если воркер отвечал с HTTP‑кодом 200, считали его доступным. Для каждой партиции проверяли, доступен ли её текущий воркер.

Если воркер оказывался недоступен, партиция переназначалась на другой воркер с наименьшим количеством партиций. Новое распределение сохранялось в базе, балансер засыпал на какое‑то время и повторял цикл.

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

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

Что делал дежурный? Брал банхаммер, банил перегруженный воркер, надеясь, что партиции перераспределятся по другим воркерам и всё выровняется. Некоторое время мы так и жили — каждое утро дежурный вручную «отрубал» узлы. Но понятно, что это был путь в никуда: так жить нельзя, нужно было что‑то менять.

Вторая версия балансировщика: запрос extended healthcheck

Постепенно стало понятно, что первый алгоритм распределения далеко не оптимален. Формально кажется, что он должен обеспечивать равномерность, но на практике её не было. Алгоритм никак не учитывал вес партиции: а ведь одна партиция может соответствовать популярному каналу с огромным числом запросов в историю сообщений. Если не учитывать вес, то можно с бóльшей вероятностью получить перегруженный воркер.

Сначала мы сформулировали требования, которым должна удовлетворять новая версия.

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

• Второе — обязательно учесть неравномерность партиций.

• Третье — сформулировать задачу так, чтобы перенос партиций происходил не рывками, а плавно. Резкие перестановки в кластере могут сбросить кеши и создать ещё больше проблем. Алгоритм должен работать скорее стабильно и предсказуемо, чем идеально быстро. По сути, это уже задача из теории управления, а не классическая задача по computer science или на графы.

• Четвёртое — обеспечить устойчивость к единичным всплескам. Если на воркер в какой‑то момент времени внезапно свалится пик запросов, это не должно тут же приводить к цепной реакции перераспределения и дёрганью всего кластера.

С такими идеями мы начали дорабатывать систему. Первое улучшение — заменили старый healthcheck на так называемый extended healthcheck. Теперь это не просто проверка «отвечает ли воркер кодом 200», а полноценный отчёт по его работе за последнее время. Extended healthcheck возвращает количество выполненных запросов, число дропов за последние пару секунд, а также оценку веса для каждой обслуживаемой партиции.

Балансер собирает эти extended healthcheck и для каждого воркера оценивает суммарный вес партиций. На основе этой информации вычисляется критерий перегруженности: мы применяем медианный фильтр к выборке дропов за последнюю минуту и сравниваем медиану с порогом. Если узел стабильно дропает больше допустимого уровня, значит, его нужно разгрузить.

Чтобы считать веса партиций, мы придумали собственную метрику — среднее время исполнения запроса. Это отдельная история, о которой я расскажу чуть подробнее далее.

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

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

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

Третья версия балансировщика: как нам помогли идеи из экономики

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

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

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

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

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

Плюс индекса Джини в том, что его значения всегда лежат в диапазоне от 0 до 1 — это удобно для интерпретации. Кроме того, он устойчив к переменному числу воркеров: мы просто подставляем текущее количество доступных узлов, которые прошли healthcheck, и получаем адекватную оценку. Значение индекса не скачет сильно при небольших изменениях числа работающих воркеров, что тоже важно.

Так у нас появилась третья версия алгоритма. Мы фиксируем для индекса Джини верхнее и нижнее пороговые значения. Если текущее значение превысило верхний порог — активируем булев флаг F. Если опустилось ниже нижнего порога — сбрасываем его. Логика дальше простая: если перегруженного воркера нет, а флаг F активен, то мы выбираем партицию P с воркера с наибольшим весом. Всё остальное остаётся таким же, как во второй версии алгоритма.

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

Четвертая версия балансировщика: finish him!

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

Воркер начинал дропать запросы, активировался наш алгоритм, который переносил тяжёлую партицию на другой воркер — и тот тоже начинал её дропать. Партиция снова мигрировала. Воркеры начинали гонять партицию туда‑сюда, как мячик в теннисе. Получался сплошной «упс»: постоянные дропы, лишняя инвалидация кешей — всё это ухудшало производительность.

В общем случае это называется «автоколебания»: незатухающие колебания, которые система поддерживает сама за счёт своего же алгоритма. Их не стоит путать с резонансом — никто извне не шлёт нам пульсирующую нагрузку строго с периодом (по крайней мере, в начальный момент времени), мы сами её провоцируем своим регулятором.

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

Дельфинирование и флаттер наглядно

Это дельфинирование:

А это флаттер:

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

Откуда взять идею, как бороться с такими колебаниями? Тут пригодился урок механики из XIX века.

Как нам (внезапно) помог центробежный регулятор

Был такой учёный и государственный деятель Иван Алексеевич Вышнеградский. Он изучал устойчивость регулятора Уатта. Это устройство регулировало подачу пара на турбину: если частота вращения слишком низкая — поток пара увеличивался; если слишком высокая — уменьшался. Задача регулятора — поддерживать стабильную частоту вала.

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

Главный вывод, к которому пришёл Вышнеградский, звучал просто, но был нетривиален для XIX века: трение — это необходимое свойство любого чувствительного и устойчивого регулятора. Другими словами, без трения регулятор Уатта не мог работать стабильно. Для инженеров того времени это утверждение было почти шокирующим: все считали, что чем лучше смазать механизм, тем он надёжнее. Но именно для регулятора Уатта всё оказалось наоборот — без трения начинались колебания.

Этот урок мы смогли применить и к нашему алгоритму. По сути, наш балансировщик — это такой многомерный дискретный регулятор Уатта. А значит, и ему нужно «трение», чтобы избежать автоколебаний. Как его имитировать? Очень просто: не позволять одной и той же партиции мигрировать слишком часто. Если партицию P за последние T минут уже переносили L раз, мы запрещаем перемещать её снова, даже если воркер перегружен. Всё остальное остаётся таким же, как в третьей версии алгоритма.

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

В итоге дропы снизились на порядки. Даже если возникают локальные проблемы или выбивается узел, кластер теперь балансируется сам — без участия дежурного. Не нужно вмешиваться ни во время утренних пиков, ни при выкладке новой версии Fanout. Дополнительно оказалось удобно и плавно закрывать локацию для ремонта — система сама перераспределяет партиции, не создавая дополнительную нагрузку на наших дежурных и SRE.

Выводы

Из этого проекта мы сделали несколько выводов:

1. Не стоит бояться искать аналогии — могут выручить даже законы механики и математики из XIX века.

2. Простые метрики вроде индекса Джини могут быть применимы в подобных алгоритмах.

3. При реализации алгоритма не стоит забывать про «страшные» слова: устойчивость регуляторов, робастное оценивание весов, правильная обработка корнер‑кейсов.

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

А вы применяли в своей работе знания из смежных дисциплин?