Главная » Хабрахабр » Знакомство с облаком: как работают динамические методы распределения трафика

Знакомство с облаком: как работают динамические методы распределения трафика

В одном из наших прошлых материалов мы рассказывали про статические методы балансировки нагрузки в облаке IaaS-провайдера. Сегодня на очереди динамические методы: «пчелиный» и «муравьиный» алгоритмы, а также подход Biased Random Sampling.

/ Flickr / Quinn Dombrowski / CC BY-SA

Часто информация о загруженности узлов хранится в таблице состояний, из которой системы распределения нагрузки и черпают информацию. Динамические методы балансировки, в отличие от статических, в своей работе учитывают текущее состояние всей системы и реагируют на изменения в ней.

Динамическое распределение нагрузки — выполняется мониторинг

Biased Random Sampling

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

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

Этот метод балансировки нагрузки полностью децентрализован и потому подходит для работы в облачных сетях. Выбор начальной вершины для выполнения задачи делается случайно (отсюда и random sampling); последующие задачи назначаются узлам-соседям, которые также выбираются в произвольном порядке. В том числе географически распределенных.

В тесте с 512 узлами, расположенными в радиусе тысячи км, средняя задержка составила примерно 70 мс (в эксперименте с сетью, не учитывающей географического распределения узлов, этот показатель составлял 92,5 мс). Ученые из Ливерпуля установили, что Biased Random Sampling, дополнительно учитывающий географическое распределение узлов в сети, позволяет снизить латентность при передаче данных на 22%.

«Муравьиный» алгоритм оптимизации (Ant colony optimization)

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

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

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

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

Новые запросы отправляются по кратчайшим незагруженным маршрутам. Это связано с тем, что первые муравьи раньше попадают в узел-приемник и имеют меньший возраст. Это позволяет балансировать ресурсы за счет разгрузки узлов на «плотных» направлениях в сети.

Эта система представляет собой самоорганизующуюся сеть соединенных «камер муравейника» — узлов, способных проводить вычисления и обрабатывать данные. Одну из вариаций этого алгоритма использует фреймворк для P2P-приложений Anthill.

Структура сети-муравейника

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

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

«Пчелиный» алгоритм оптимизации (honeybee foraging)

Первые статьи, в которых описывался метод пчелиного роя, были опубликованы в 2005 году. Он основан на моделировании поведения пчёл при поиске нектара. В ульях есть так называемые пчелы-разведчики, которые ищут поляны с цветами. Когда они находят источник пищи, то возвращаются в улей, чтобы рассказать об этом другим с помощью специального «виляющего танца».

/ Flickr / Irregular Blog — Daedalus / CC BY-SA

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

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

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

Другие материалы из корпоративного блога 1cloud:


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Как Яндекс применил компьютерное зрение для повышения качества видеотрансляций. Технология DeepHD

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

Security Week 36: Telnet должен быть закрыт

Telnet — это очень старый протокол. Википедия сообщает, что он был разработан в 1969 году, много лет активно использовался для удаленного доступа к компьютерам и серверам, причем как под управлением Unix/Linux, так и для систем под Windows (telnet можно было ...