Датские инженеры представили алгоритм, который уже используют крупные ИТ-компании и облачники. Рассказываем, как он устроен и обсуждаем перспективы.
Сложности балансировки на масштабе
По оценкам Cisco, в период с 2017 по 2022 год объем передаваемых в интернете данных увеличится в три раза (стр.4), при этом 82% всего трафика займет видеоконтент. Столь стремительный рост отразится на работе балансировщиков нагрузки в дата-центрах ИТ-компаний и стриминговых платформ, которым приходится распределять трафик между множеством серверов на лету.
Классическим методом решения задачи считается «согласованное хеширование» (consistent hashing), когда каждому серверу в сети назначают несколько хешей, составленных на основе имени или идентификатора. Далее, аналогичные значения вычисляют для каждого входящего запроса, и его обработку передают машине, хеш которой оказался наиболее близким. Однако такой подход не лишен недостатков — тип континента, оказавшийся популярнее остальных, может не получить необходимых ресурсов для обработки в силу неравномерного распределения трафика.
Решение этой проблемы нашли инженеры из исследовательской лаборатории при Копенгагенском университете. Они представили алгоритм, объединяющий согласованное хеширование с форвардингом.
Датское решение вопроса
Суть в следующем — сперва администратор определяет (стр.1) коэффициент уравновешивания (balancing factor) со значением больше единицы. Его выбирают экспериментально, в зависимости от поставленных задач — обычно на отрезке от 1,25 до 2. Далее, каждый раз, когда в систему поступает новый запрос, балансировщик вычисляет среднюю нагрузку на инфраструктуру по формуле: число необработанных запросов, поделенное на количество доступных серверов. Полученное значение он умножает на коэффициент уравновешивания и получает «целевую нагрузку». Это — максимально допустимая нагрузка на один сервер. Балансировщик передает свежий запрос той машине, объем задач которого не превышает пороговое значение.
Если нагрузка выросла и «пробила» граничные показатели, система вычисляет хеш запроса и ищет подходящий сервер по методике consistent hashing. Согласно заявлениям разработчиков, алгоритм за десять итераций распределяет нагрузку между серверами с разницей всего в 10%. Изучить его особенности с математическими выкладками можно с помощью whitepaper’а.
Кто использует
Работу над алгоритмом датские инженеры ведут еще с 2016 года. Тогда они представили его первую версию, которая была в десять раз медленнее, но уже помогла сократить нагрузку на ИТ-инфраструктуру крупных фирм с миллионами серверов и исключить ситуации, когда один сервер перегружен, а оставшиеся простаивают. Решение на практике опробовал хостинг Vimeo. Компания в восемь раз сократила объем ресурсов для работы стриминговых сервисов.
Google также развернули алгоритм в своих дата-центрах, к слову, сотрудники корпорации принимали участие в его разработке. Специалисты из Копенгагенского университета надеются, что их алгоритмом воспользуется больше организаций, поэтому они передали его в open source.
Авторы также убеждены, что их решение сделает ЦОДы более экологичными. Сегодня они потребляют порядка 400 ТВт·ч электричества ежегодно. В итоге на их долю приходится 2% мировых выбросов углерода. Новый алгоритм поможет сократить энергопотребление и вред, наносимый окружающей среде.
Альтернативные решения
Разработками алгоритмов балансировки нагрузки занимаются и другие организации — например, Twitter. Компания использует свою версию согласованного хеширования — она реализована в открытом фреймворке Finagle. Балансировщик выбирает подмножество серверов для подключения — «апертуру». Ее минимальный размер составляет 1/N, где N — число доступных машин. Далее, все запросы распределяются равномерно между серверами. При добавлении или отключении вычислительных ресурсов апертура меняется для достижения лучшей производительности.
В целом Finagle помимо балансировки нагрузки способен решать задачи обнаружения сервисов и маршрутизации, что требует более глубокого изучения функциональности и доступных интерфейсов. Но, в любом случае, конкуренция на рынке load balancer’ов играет на руку индустрии. Компании получают возможность экономить на инфраструктуре и направлять средства на развитие продуктов и сервисов.
О чем еще мы пишем на Хабре:
Почему шифрование DNS не всегда эффективно — обсуждаем мнения
Что дает экспериментальная система связи для защиты от MITM-атак
Материалы из корпоративного блога Vas Experts:
tumbler
По хеш-рингу определяется основной сервер, а если он загружен больше чем на 125%-200% от средней нагрузки, то происходит прыжок на следующий сервер кольца.
В целом неплохо, но есть проблемы с одним единственным супер-горячим запросом: он будет ходить по одной и той же цепочке серверов, что в реальном мире может приводить тупо к перегрузке серверов по очереди.