Содержание к диссертации
Введение
Глава 1. Обзор технологий распределенной обработки больших объемов данных 12
1.1. Тенденции развития вычислительных технологий и технологий передачи данных 12
1.2. Методы распределенной обработки больших объемов данных 13
1.3. Методы обработки потока данных 13
1.4. Технологии передачи данных в распределенных системах
1.4.1. Передача данных в интерконнектах суперкомпьютеров 15
1.4.2. Технологии, использующие систему хранения данных
1.4.3. Специализированные транспортные протоколы передачи данных
4.3.1. Алгоритмы управления перегрузкой для TCP 19
1.4.3.2. Протоколы передачи данных на базе UDP 20
1.4.3.3. Анализ эффективности протоколов 21
1.5. Выводы по главе 23
Глава 2. Модель обработки потока данных в распределенных системах 25
2.1. Идея модели обработки потока данных 25
2.1.1. Особенности инфраструктуры распределенных суперкомпьютерных систем 28
2.2. Модель очередей для обработки потока данных 30
2.2.1. Пример применения предложенной модели в проекте пределенный PIV 33
2.3. Математическое обоснование преимущества системы с общей редью 35
2.3.1. Система массового обслуживания En/M /1 36
2.3.2. Система массового обслуживания M/M/n 38
2.3.3. Сравнение систем En/M /1 и M/M/n 39
2.4. Технология взаимодействия оконечных систем и менеджера оче
редей 41
2.4.1. Алгоритм распределения элементов потока данных по вычислителям 42
2.4.2. Метод взаимодействия оконечных систем и менеджера очередей
2.5. Преимущества модели очередей и технологии взаимодействия оконечных систем с менеджером очередей 45
2.6. Методика оценки требуемых коммуникационных и вычислителных ресурсов 47
2.7. Выводы по главе 53
Глава 3. Программная инфраструктура распределенной обработки данных 54
3.1. Анализ существующих технологий работы с очередями в распределенных системах 54
3.1.1. Скорость упаковки данных и диспетчеризации 56
3.1.2. Простота реализации формата передачи данных 56
3.1.3. Поддержка сторонних транспортных протоколов 56
3.1.4. Простота использования 57
3.1.5. Безопасность 57 3.1.6. Поддержка структурированных сообщений 57
3.2. Протокол SciMP 58
3.2.1. Формат пакета протокола SciMP 59
3.2.2. Возможности протокола SciMP 60
3.2.3. Иллюстрация работы протокола SciMP
3.3. Методы обработки параллельных сетевых соединений 62
3.4. Программное обеспечение распределенной обработки данных
3.4.1. Сервер очередей 67
3.4.2. Клиентская библиотека 70
3.4.3. Управляющее программное обеспечение 73
3.5. Выводы по главе 76
Глава 4. Апробация предложенных решений 77
4.1. Условия проведения экспериментов 77
4.1.1. Характеристики оконечных систем 78
4.1.2. Настройки сетевых подсистем в оконечных системах 79
4.1.3. Схема установки программного обеспечения
4.2. Тестирование эффективности алгоритмов TCP 81
4.3. Исследование и анализ пропускной способности системы
4.3.1. Определение диапазонов значений варьируемых параметров 85
4.3.2. Обработка потока данных с использованием транспортного протокола TCP 87
4.3.3. Обработка потока данных с использованием транспортного протокола UDT 4.4. Тестирование масштабируемости программного обеспечения 100
4.5. Тестирование программного обеспечения при обработке продолжительных потоков данных 104
4.6. Выводы по главе 107
Заключение 108
Список литературы
- Технологии передачи данных в распределенных системах
- Математическое обоснование преимущества системы с общей редью
- Простота реализации формата передачи данных
- Исследование и анализ пропускной способности системы
Технологии передачи данных в распределенных системах
Обзор состояния методов и технологий обработки потоков данных показал отсутствие целостного решения для распределенных систем. Существующие подходы распределенной обработки больших объемов информации, базирую щиеся на парадигме MapReduce или/и ориентированные на пакетный режим работы суперкомпьютера, архитектурно не могут обеспечить обработку потока данных.
В области технологий передачи данных сложилось разделение на две ос новные группы: высокоуровневые решения по передаче преимущественно фай лов между дисковыми хранилищами и низкоуровневые протоколы высокоско ростной передачи данных. Высокоуровневые решения требуют использования дополнительных компонент, что негативно влияет на скорость обмена, а также из-за устоявшейся архитектуры и требований к совместимости ограничены в возможностях по адаптации к конкретным условиям эксплуатации. Специализи рованные транспортные протоколы лишены этих недостатков, однако, требуют разработки собственных алгоритмов для передачи данных между приложения ми.
На основе вышеперечисленных ограничений было принято решение о раз работке и исследовании специализированной модели обработки потока данных в распределенных системах на основе отказа от промежуточного хранения дан ных на хранилищах распределенной системы и параллелизма на уровне пере дачи данных. Прототипом этой модели является концепция очередей данных, позволяющая перенести место решения задачи диспетчеризации данных с мно жества вычислительных узлов на отдельный компонент – менеджер очередей. Для передачи данных по высокоскоростным линиям связи большой протяжен ности было принято решение использовать на транспортном уровне как сер висы, предоставляемые операционной системой (протокол TCP с различными алгоритмами управления перегрузкой), так и специализированный потокоори ентированный транспортный протокол передачи данных UDT. На прикладном уровне обмен данными осуществляется с помощью специально разработанного протокола обмена сообщениями с менеджером очередей. Глава2
Модель обработки потока данных в распределенных системах Предварительные исследования[ 1] показали невозможность эффективно го применения классических методов передачи файлов в распределенной вы числительной системе для передачи больших потоков данных. В результате анализа были выявлены следующие основные причины, влияющие на низкую эффективность передачи данных в классических моделях:
Локальная обработка экспериментальных данных 1. Нецелесообразность размещения супервычислителей рядом с каждой уни кальной экспериментальной установкой, требующей обработку данных в реальном времени. Ограниченность подключенных к этим установкам ком пьютеров, вычислительная производительность которых сдерживает раз витие математического аппарата и постановки сложных экспериментов (рисунок 2.1).
Классическая схема загрузки данных для обработки через хранилище данных суперкомпьютера
Развитие технологий передачи данных привело к тому, что скорости пере дачи данных по сети намного превысили скорости обмена данными с дисками, а компонента задержек на сетевом оборудовании стала много меньше, чем за держки обращения к дискам[ 15].
В настоящее время существуют высокоскоростные сети передачи данных, которые позволяют соединять экспериментальные установки, системы хране ния данных и супкркомпьютеры. В УрО РАН развитие высокоскоростной научно-образовательной сети передачи данных выполняется в рамках проекта «Инициатива GIGA» 51].
Это позволило выдвинуть идею модели обмена данными (рисунок 2.3), суть которой заключается в прямом ввооде потока данных в память вычисли тельных узлов исключая промежуточное сохранение данных в системе хране ния суперкомпьютера и экспериментальных установок[ 51].
Развитием идеи прямого ввода данных в вычислительные узлы супервы числителя является разработанная модель на базе очередей данных, параллель ной передачи данных по высокоскоростным протяженным каналам связи (ри сунок 2.4) и распределения блоков данных по запросам вычислителей[ 12]. Раз работанная модель уточняет механизмы передачи данных и алгоритмы распре деления данных по вычислительным узлам суперкомпьютеров.
Особенности инфраструктуры распределенных суперкомпьютерных систем Рассмотрим ситуацию, когда требуется обрабатывать поток эксперимен тальных данных на удаленном суперкомпьютере. При этом между источником данных и удаленным суперкомпьютерным центром создается высокоскоростной канал связи, который подключается напрямую к внутреннему интерконнекту или через управляющий узел суперкомпьютера.
Математическое обоснование преимущества системы с общей редью
Линии Le[n] и VKe[n] показывают характеристики системы с предварительным распределением данных Еп/М/1): а линии L и W - многоканальной системы с общей очередью (М/М/п). Из графиков следует, что при прочих равных условиях система с общей очередью показывает меньшую среднюю длину очереди и среднее время ожидания. Необходимо отметить, что меньшее среднее время ожидания и средняя длина очереди влияет не только на время до полу чения результата расчета, но и на требуемые ресурсы менеджера очередей, так как на каждый находящийся в очереди элемент требуется затратить некоторый объем памяти, а в системе с предварительным распределением данных очереди будут не только длиннее, но и их количество будет равно числу обработчиков.
Технология взаимодействия оконечных систем и менеджера очередей На решение проблемы недостаточной эффективности классических прото колов передачи данных направлен предлагаемый алгоритм распределения дан ных по вычислительным узлам и протокол передачи данных между компонен тами системы. Под оконечными системами понимаются системы, работающие на уровнях генерации и обработки данных. Это могут быть экспериментальные установки, вычислительные кластеры и суперкомпьютеры, хранилища данных и т.д. Менеджер очередей – это компонент, реализующий уровень распределе ния данных.
Основными направлениями увеличения эффективности передачи данных по высокоскоростным протяженным линиям связи является: 1. параллелизм передачи данных; 2. специализированные транспортные протоколы передачи данных; 3. специализированные алгоритмы управления перегрузкой TCP; 4. настройки параметров сетевого стека операционных систем. Предлагаемые архитектурные решения направлены на максимальное ис пользование всех вышеперечисленных методик увеличения эффективности пе редачи данных. 2.4.1. Алгоритм распределения элементов потока данных по вычислителям Для определения алгоритма распределения элементов потока данных по вычислителям необходимо: 1. Выбрать подходящую стратегию распределения данных очереди. 2. Определить процедуру выбора вычислителя, которому будет отправлено следующее собщение из очереди.
Ориентация на обработку данных в реальном времени (минимальные за держки диспетчеризации и сохранения порядка передачи сообщений) обуслав ливают использование дисциплины распределения данных FIFO (First In, First Out – первым пришел, первым ушел).
Исходя из необходимости разработки универсального подхода, который мог бы работать при различной структуре обрабатываемых потоков данных и суперкомпьютеров, узлы которых могут обладать различной производитель ностью было предложено определять вычислитель, которому будет передано следующее сообщение из очереди по запросам от самих вычислителей. Этот под ход является ключевым моментом разработанного алгоритма диспетчеризации данных, который позволяет прикладной программе обработки данных после об работки текущего измерения запрашивать у менеджера очередей новую порцию данных. Такой способ обеспечивает автоматическое и динамическое распределение нагрузки от структурированного потока данных по вычислительным узлам суперкомпьютера.
В предлагаемой модели очередей существует два тракта передачи данных: от уровня генерации данных на уровень распределения данных; от уровня распределения данных на уровень обработки данных. Взаимодействие по ним сводится к основным операциям загрузки данных в очередь и получения данных из очереди и сервисным операциям, например, операциям создания и удаления очереди. Вышеизложенный подход, при кото ром инициатива во взаимодействии принадлежит оконечным системам, был ре ализован в виде синхронного обмена сообщениями между взаимодействующими компонентами (рисунок 2.13).
Такой подход позволил упростить логику взаимодействия компонентов и, как следствие, увеличить производительность возможных реализаций протоко ла.
Передача сообщений реализуется с помощью разработанного прикладного протокола SciMP (Scientific Message Protocol). Необходимо отметить, что пред лагаемый подход позволяет передавать прикладные данные (например, изобра жения в случае задачи PIV) не только в пакетах протокола SciMP, но и альтер нативными способами.
По умолчанию предполагается, что все прикладные данные будут переда ваться средствами протокола SciMP. Но в иных случаях, возможен и альтерна тивный способ передачи прикладных данных. Тогда разработанный протокол и программное обеспечение будут использоваться для решения задачи диспет черизации данных по вычислительным узлам, но не для решения задачи их транспортировки на вычислительные узлы.
Например, если между вычислительной средой и источником данных есть доступная система хранения данных, которая удовлетворяет всем требованиям по скорости чтения/записи данных, то источник данных может записывать дан ные на эту систему хранения, а вычислительные узлы производить чтение.В этом случае менеджеру очередей для решения задачи диспетчеризации будет достаточно передавать только метаданные измерений (идентификаторы измере ний, пути к файлам на разделяемой системе хранения), которые после передачи прикладным программам вычислительных узлов покажут им, откуда необходи мо производить чтение непосредственно данных для обработки.
Простота реализации формата передачи данных
Практическое применение разработанной модели и технологии обмена данными требует создания методики оценки необходимых для работы коммуникационных и вычислительных ресурсов в зависимости от скорости генерации данных Источником данных, а также формулирование области применения данного подхода.
Предлагаемая методика разрабатывалась для случая обработки потока экспериментальных данных удаленной системой с возвратом результатов обработки обратно на источник данных через менеджер очередей.
Симметричность задачи относительно потока исходных данных и потока результатов позволяет проводить оценку требуемых коммуникационных ресурсов с использованием потока с максимальным требованием к скорости передачи данных vs (байт/с), значение которой будет определяться следующим образом:
Vmax = піах л, )- (2.25) Необходимо отметить, что в простейшем случае, когда на каждое исходное сообщение будет отправляться одно сообщение результатов обработки, при устойчивом функционировании системы коэффициент /ІГ будет равен Л.
Очевидно, что для устойчивого функционирования системы, скорость передачи данных в полнодуплексном канале связи должна быть не меньше, чем интенсивность обмена данными: v = vmax. (2.26) Одновременно с этим для обеспечения синхронной обработки потока данных потребуется не менее, чем п обработчиков: п = \(т +2 RTT) Л]. (2.27)
Слагаемое 2 RTT в формуле (2.27) необходимо для учета времени передачи запроса данных и подтверждения приема результатов обработки менеджеру очередей (рисунок 2.14). Если результаты расчета передаются обратно менеджеру очередей, то время этой передачи также необходимо прибавлять к т, так как разработанное решение предполагает интерактивный протокол взаимодействия.
Так как, в транспортных протоколах с гарантией доставки, всегда есть обратный трафик, в котором пересылаются подтверждения доставки, то введем коэффициент ks, который будет показывать долю служебного (заголовки протоколов) и обратного трафика по отношению к объему пользовательских данных. Тогда оценка для v перепишется следующим образом:
Величину ks можно оценить на основе описаний стеков протоколов, начиная от канального до транспортного уровней. Коэффициент ks состоит из двух частей. Первая часть - это доля служебного трафика, передающегося в прямом Рисунок 2.14. Временная диаграмма процесса обработки сообщения направлении относительно объема полезных данных – заголовочныеполя токольных блоков данных. Вторая часть – это доля обратного трафика, при помощи которого получатель передает отправителю подтверждения успешной доставки данных. время для достижения максимально возможной скорости передачи данных, необходимо добавить поправочный коэффициент, учитывающий данный недостаток реальных транспортных протоколов. Так как возможным способом повышения эффективности является параллелизм, те. одновременная передача данных в нескольких параллельных соединениях, то этого возможно добиться путем увеличения числа задействованных вычислителей на пр штук. Тогда оценка числа требуемых вычислительных узлов примет вид: где пр показывает сколько активных параллельных соединений нужно использовать для выхода на близкую к максимальной эффективность работы транспортных протоколов. Добавление пр обработчиков к обработчикам, требующимся для расчетов, позволяет создать необходимый запас процессов, не занятых вычислениями, и, тем самым, обеспечить нужное количество активных потоков при передаче данных по сети.
Число активных потоков пр напрямую зависит от пропускной способности канала связи, времени RTT, используемых алгоритмов управления перегрузкой, уровня потерь и искажений данных в линии и т.д. В связи с этим, аналитическое определение данного числа потоков с большой вероятностью невозможно, но его оценка может быть выполнена экспериментальным путем. Для этого необходимо определить максимально достижимые скорости передачи данных по существующему каналу связи, в зависимости от алгоритма управления перегрузкой и числа парраллельных потоков. Решение данной задачи было автоматизировано с помощью приложения для тестирования скорости передачи данных Iperf [56] и скрипта, написанного на языке Bash для операционной системы Linux, код которого приведен в приложении А.
Исследование и анализ пропускной способности системы
Методика оценки вычислительных ресурсов, предложенная во второй гла ве диссертационной работы требует, чтобы теоретическая оценка была выше экспериментальной, тогда при запуске задачи на счет будет гарантировано по лучено не менее, чем необходимо, на основании экспериментальной оценки, до полнительных сетевых соединений, компенсирующих негативные эффекты от использования TCP на протяженных линиях связи.
Графики показывают, что при правильном подборе коэффициентов пред ложенная формула дает прогнозируемо завышенный результат, однако, в дан ном случае завышение является допустимым и даже благоприятным явлением, так как повышает устойчивость системы в случае каких-либо отклонений в про цессе вычислений. В области потоков данных с высокой частотой генерации данных, и, как следствие, высоких скоростей передачи данных, вопрос подбора правильных коэффициентов становится затруднен. Из графиков следует, что в этой области, выбранное значение коэффициента np = 1 приводит к заниженной оценке.
Причиной этого является тот факт, что первоначальный выбор значения коэффициента np проводился только с учетом характеристик выделенной про тяженной линии связи без учета структуры и характера загрузки интеркон некта суперкомпьютера. Сравнение алгоритмов работы TCP на выделенном и разделяемом канале связи показывает, что при малом числе параллельных со единений алгоритмы используют не всю свободную от фонового трафика про пускную способность канала связи. Поэтому, несмотря на то, что остаточной пропускной способности интерконнекта суперкомпьютера было достаточно для передачи данных эксперимента, TCP не мог достигнуть этой скорости передачи данных малым числом параллельных соединений.
Для проверки этой гипотезы была проведена дополнительная серия измеений для случаев, где выбор параметра np вызывал сомнения. Это тестирование было проведено со следующим числом дополнительных узловлов, при котором будет достигнут приемлемый размер очереди и, как лед ствие, интенсивность запросов на получение данных для обработки будет не ниже интенсивности поступления новых данных, будет являться тот факт, что необходимое в тесте полнительх узлов в максимальной протестированной конфигурации.
Из графиков следует, что минимально необходимое число узлов оказалось во всех случаях на нижней границе исследуемого множества, что говорит о пра вильности первоначальной гипотезы о необходимости уточнять правило выбора параметра np при высокой интенсивности потка данных для того, чтобы учесть наличие фонового трафика во внутреннем интерконнекте суперкомпьютера.
Таким образом, в случае высокой интенсивности генерируемого потока экс периментальных данных потребуются более высокие значения коэффициента np – числа дополнительных вычислителей (потоков данных). Во первых, это компенсирует инертность разгона транспортных протоколов. Во вторых, если в магистральной сети данные передавались без конкурирующего трафика, то внутри суперкомпьютера сеть передачи данных не была выделенной, сдова тельно, наблюдалась конкуренция за пропускную способность со служебным трафиком и трафиком между хранилищем данных и вычислительными узла ми.
Обобщенная диаграмма зависимости числа дополнительных вычислитель ных узлов от параметров исходного потока данных (скорость потока исходных данных и отношение времени обработки данных к времени между событиями генерации сообщений( tt), которое показывает минимально необходимое число обработчиков для синхронной обработки данных) показана на рисунке 4.30.
Таким образом из графиков следует, что в области высокой интенсивности генерируемого потока данных реальный коэффициент np для протокола TCPс алгоритмом управления перегрузкой bic равнялся 11, т.е. требовалось 11 допол нительных потоков данных (вычислительных узлов) для передачи исследуемых потоков исходных данных на обработку в квазиреальном времени.
