Равномерный поток гигантских данных: синхронизация контрольных точек спасает серверы от перегрузки
Потоки событий редко бывают однородными: несколько доминирующих ключей могут генерировать на порядки больше событий, чем остальные, перегружая получающих их потоки обработки и ограничивая пропускную способность. Мы представляем CheckCo, алгоритм балансировки нагрузки, координируемый по контрольным точкам, построенный на основе динамического оракула, который оценивает частоту каждого ключа из живого потока без предварительной статистики. Работники подсчитывают события для каждого ключа локально; на каждом барьере контрольной точки счетчики объединяются в функцию разделения, которая делит каждый ключ на несколько частей, примерно пропорциональных его предполагаемой частоте, и упаковывает разделения в рабочие процессы, и эта функция маршрутизирует следующее окно контрольной точки. Мы получаем аппроксимационные границы результирующего дисбаланса нагрузки на основе результатов классического планирования и оцениваем его общее разветвление ключей. В производственном конвейере, обрабатывающем более 100 миллиардов событий в день, наиболее загруженный работник получает лишь на 9.8% больше событий, чем в среднем за день (коэффициент дисбаланса 1,10), против 8,03 для маршрутизации на основе ключей в моделировании; при моделировании CheckCo также требуется менее половины разветвления по сравнению с более ранними разделителями, которые достигают сопоставимого баланса. Изменения в распределении ключей отражаются при маршрутизации со следующей контрольной точки, и нагрузка остается сбалансированной при перезапуске задания.
## В чем суть открытия На протяжении десятилетия архитекторы распределенных вычислительных систем сталкивались с фундаментальным противоречием природы сетевого трафика. В реальных телеметрических и веб-потоках распределение идентификаторов событий подчиняется степенному закону Ципфа: подавляющая часть ключей встречается редко, тогда как доли процента доминирующих категорий генерируют колоссальный объем сообщений. Классическое хэш-секционирование привязывает все события одного типа к конкретному узлу-обработчику, в результате чего единственный вычислительный узел захлебывается трафиком, ограничивая пропускную способность всего распределенного кластера. Попытки решить эту проблему путем слепого рассеивания записей по всем узлам подряд устраняют перегрузку, но порождают разрушительное веерное ветвление: каждый узел открывает сетевой канал под каждый ключ, а целевые хранилища засоряются миллионами микроскопических файлов. Существовавшие адаптивные эвристики, вроде схемы двух случайных выборов или фиксированного расширения для популярных ключей, либо не справлялись с экстремальным перекосом трафика, превышающим емкость двух серверов, либо выделяли популярным ключам избыточное число рабочих узлов без учета их реального веса. Исследователи предложили элегантный выход из тупика, превратив саму процедуру обеспечения отказоустойчивости потокового фреймворка в инструмент глобальной координации без дополнительных сетевых издержек. ## Как это устроено: принцип работы Архитектура CheckCo связывает балансировку с механизмом выравнивания распределенных контрольных точек. В момент прохождения через вычислительный граф служебных меток отсечки каждый параллельный узел передает накопленную локальную статистику частот ключей через дополнительный канал вывода. Получатель объединяет эти данные в единую глобальную частотную карту, превращаясь в динамический оракул текущей нагрузки. Вместо эвристического угадывания алгоритм формализует задачу как классическое расписание задач для многопроцессорных систем. Сначала вычисляется целевая емкость одного узла. Если поток конкретного ключа превышает этот предел, ключ дробится на дискретные фрагменты расчетного размера, гарантируя, что ни одна порция не превысит допустимый максимум. Полученные порции раскладываются по узлам при помощи детерминированного жадного алгоритма наименьшей текущей загрузки, а входящие события маршрутизируются тривиальным вычислением остатка от деления идентификатора события на число фрагментов. Для подавления