Содержание к диссертации
Введение
Глава 1. Обработка транзакций в многопроцессорных иерархиях 11
1.1. Многопроцессорные иерархии 11
1.2. Организация параллельной обработки запросов 16
1.3. Обзор моделей многопроцессорных систем 18
1.3.1. Аппаратно-архитектурные модели 19
1.3.2. Классификация моделей параллельных вычислений 20
1.3.3. Параллельные вычислительные модели с общей памятью 22
1.3.4. Параллельные вычислительные модели с распределенной памятью 24
1.3.5. Параллельные вычислительные модели с иерархией памяти 28
1.4. Выводы по главе 1 35
Глава 2. Модель мультипроцессоров баз данных 37
2.1. Требования к модели 37
2.1.1. Специфика приложений баз данных класса OLTP 37
2.1.2. Иерархическая структура соединительной сети 38
2.1.3. Дисковый ввод/вывод 39
2.1.4. Фрагментный параллелизм 39
2.1.5. Передача сообщений по соединительной сети 40
2.1.6. Оценка стоимости запросов 40
2.1.7. Специфика реляционной модели данных 41
2.1.8. Параллельные транзакции 41
2.1.9. Межтранзакционный параллелизм 42
2.2. Формальное описание модели 42
2.2.1. Базовые определения 42
2.2.2. Модель аппаратной платформы 44
2.2.3. Модель операционной среды 51
2.2.4. Стоимостная модель 54
2.2.5. Модель транзакций 55
2.3. Выводы по главе 2 63
Глава 3. Эмулятор многопроцессорных иерархических машин баз данных 64
3.1. Модель вариантов использования эмулятора DMS 64
3.2. Архитектура эмулятора DMS 69
3.3. Принципы работы эмулятора DMS 73
3.4. Язык описания конфигураций 76
3.5. Выводы по главе 3 78
Глава 4. Вычислительные эксперименты 80
4.1. Параметры вычислительных экспериментов 80
4.2. Подтверждение адекватности модели DMM 81
4.3. Моделирование SMP-узлов 83
4.4. Влияние интерконнекта и дисков на масштабирование 85
4.5. Оптимизация стоимости расширения системы 87
4.6. Выводы по главе 4 91
Заключение 92
Литература 97
- Организация параллельной обработки запросов
- Передача сообщений по соединительной сети
- Принципы работы эмулятора DMS
- Влияние интерконнекта и дисков на масштабирование
Введение к работе
Актуальность темы. Современные многопроцессорные системы в большинстве случаев организуются по иерархическому принципу. Например, большая часть вычислительных кластеров сегодня имеют трехуровневую архитектуру. В рамках такой архитектуры многопроцессорная система строится как набор однородных вычислительных модулей, соединенных высокоскоростной сетью. Это - первый (верхний) уровень иерархии. Каждый вычислительный модуль является, в свою очередь, многопроцессорной системой с разделяемой памятью и образует второй уровень иерархии. Так как в современной кластерной системе, как правило, используются многоядерные процессоры, то мы получаем третий уровень иерархии. Еще одним источником многопроцессорных иерархий являются Grid-технологии, позволяющие объединять несколько различных кластеров в единую вычислительную систему. Подобная Grid-система будет иметь многоуровневую иерархическую структуру.
Важным классом приложений для иерархических многопроцессорных систем являются задачи, связанные с хранением и обработкой сверхбольших баз данных. В соответствие с этим актуальной является задача моделирования и анализа новых иерархических многопроцессорных архитектур для приложений баз данных.
Цель и задачи исследования. Цель данной работы состояла в построении математической модели иерархической многопроцессорной системы в контексте приложений баз данных, а также в разработке на ее основе методов и алгоритмов моделирования процессов параллельной обработки транзакций, которые могут быть применены для поиска и исследования перспективных аппаратных архитектур. Для достижения этой цели необходимо было решить следующие задачи:
Разработать математическую модель мультипроцессоров баз данных, включающую в себя модель аппаратной платформы, модель операционной среды, стоимостную модель и модель транзакций.
Разработать методы и алгоритмы, позволяющие реализовать предложенную модель на ЭВМ.
Спроектировать и реализовать эмулятор многопроцессорных иерархических машин баз данных.
Произвести проверку адекватности модели мультипроцессоров баз данных путем сравнения результатов, полученных на эмуляторе, с результатами, полученными на реальной параллельной СУБД.
При помощи эмулятора провести вычислительные эксперименты для поиска оптимальных аппаратных архитектур параллельных систем баз данных.
Методы исследования. Проведенные в работе исследования базируются на реляционной модели данных. Для построения моделей использовался математический аппарат, в основе которого лежат теория множеств, теория графов, теория алгоритмов и теория вероятности. При разработке программной системы применялись методы объектно-ориентированного проектирования и язык UML.
Научная новизна работы заключается в следующем:
Разработана математическая модель для описания иерархических многопроцессорных систем, ориентированная на перспективные суперкомпьютерные архитектуры и грид-системы, учитывающая специфику приложений баз данных.
Создана модель операционной среды, позволяющая моделировать работу приложения с интенсивным дисковым вводом-выводом на иерархической многопроцессорной системе.
Разработана стоимостная модель для оценки времени, расходуемого на обмены с дисками и передачу данных внутри иерархической многопроцессорной системы.
Предложена модель для описания выполнения смеси транзакций в многопроцессорной системе.
Теоретическая ценность работы состоит в том, что в ней дано формальное описание модели мультипроцессоров баз данных DMM {Database Multiprocessor Model), включающей в себя модель аппаратной платформы, модель операционной среды, стоимостную модель и модель транзакций. Практическая ценность работы заключается в том, что на базе предложенной модели DMM разработан эмулятор многопроцессорных иерархических машин баз данных DMS (Database Multiprocessor Simulator), позволяющий моделировать и исследовать эффективность различных иерархических многопроцессорных конфигураций в контексте задач баз данных класса OLTP.
Апробация работы. Основные положения диссертационной работы, разработанные модели, методы, алгоритмы и результаты вычислительных экспериментов докладывались автором на следующих международных и всероссийских научных конференциях:
на Международной научной конференции «Высокопроизводительные вычисления, сети и коммуникационные системы (HPCNCS-07)» (9-12 июля 2007 г., Орландо, США);
на Всероссийской научной конференции «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность» (21-26 сентября 2009 г., Новороссийск);
на Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач» (22-27 сентября 2008 г., Новороссийск);
на Международной научной конференции «Параллельные вычислительные технологии» (29 января - 2 февраля 2007 г., Челябинск);
на Втором весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (1-2 июня 2005 г., Санкт-Петербург);
на Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений» (19-24 сентября 2005 г., Новороссийск);
на Международной научной конференции «Суперкомпьютерные системы и их применение» (26-28 октября 2004 г., Минск).
Публикации. По теме диссертации опубликовано 6 печатных работ и получено одно свидетельство Роспатента об официальной регистрации программы для ЭВМ. Статья [1] опубликована в научном журнале «Автоматика и телемеханика», включенном ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора и кандидата наук. В статье [1] П.С. Костенецкому принадлежит раздел 2 (стр. 113-117). В работах [4-6] Л.Б. Соколинскому принадлежит постановка задачи, П.С. Костенецкому принадлежат все полученные результаты.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 112 страниц, объем библиографии - 136 наименований.
Организация параллельной обработки запросов
Основой параллельной обработки запросов в реляционных системах баз данных является фрагментный параллелизм [132]. В предельно упрощенном виде схема обработки запроса с использованием фрагментного параллелизма изображена на рис. 2. Данная форма параллелизма предполагает фрагментацию отношения, являющегося аргументом реляционной операции, по дискам многопроцессорной системы. Способ фрагментации определяется функцией фрагментации, которая для каждого кортежа отношения вычисляет номер процессорного узла, на котором должен быть размещен этот кортеж. Запрос параллельно выполняется на всех процессорных узлах в виде набора параллельных агентов [18], каждый из которых обрабатывает отдельный фрагмент отношения на выделенном ему процессорном узле. Полученные агентами результаты сливаются в результирующее отношение.
Несмотря на то, что каждый параллельный агент в процессе выполнения запроса независимо обрабатывает свой фрагмент отношения, для получения корректного результата необходимо выполнять пересылки кортежей между процессорными узлами. Для организации таких пересылок в соответствующие места дерева плана запроса вставляется оператор exchange [33]. Оператор exchange однозначно задается номером порта обмена и функцией распределения. Функция распределения для каждого входного кортежа вычисляет логический номер процессорного модуля, на котором данный кортеж должен быть обработан. Порт обмена позволяет включать в дерево запроса произвольное количество операторов exchange. Для каждого оператора указывается свой уникальный порт обмена.
Опишем общую схему организации параллельной обработки запросов в параллельной СУБД [18]. Мы будем полагать, что вычислительная система представляет собой кластер, который имеет двухуровневую иерархическую архитектуру и состоит из N вычислительных узлов (см. рис. 3). Будем считать, что каждое отношение базы данных, задействованное в обработке запроса, фрагментировано по всем процессорным модулям вычислительной системы. В соответствие с данной схемой, обработка запроса состоит из трех этапов.
На первом этапе SQL-запрос передается пользователем на выделенную host-машину, где транслируется в некоторый последовательный физический план [21]. На втором этапе последовательный физический план преобразуется в параллельный план, представляющий собой совокупность параллельных агентов. Это достигается путем вставки оператора обмена exchange в соответствующие места дерева запроса. На третьем этапе параллельные агенты пересылаются с host-машины на соответствующие вычислительные узлы, где интерпретируются исполнителем запросов. Результаты выполнения агентов объединяются корневым оператором exchange на нулевом узле, откуда передаются на host-машину. Роль host-машины может играть любой узел вычислительного кластера.
Модели многопроцессорных систем обеспечивают высокоуровневый подход к определению характеристик и сравнению времени выполнения различных программ, при этом абстрагируясь от аппаратного обеспечения и деталей выполнения. Обзор различных моделей многопроцессорных систем и параллельных вычислений можно найти в работах [52, 54, 82, 117, 134]. В зависимости от уровня абстракции модели многопроцессорных систем можно разделить на четыре категории [84]: аппаратные модели, архитектурные модели, вычислительные модели и программные модели. Среди этих категорий, вычислительные модели специфицируют абстрактное представление архитектурных моделей, определяя способ организации вычислений на базе некоторой фиксированной аппаратной архитектуры. При этом они независимы от конкретных языков и систем программирования. В со ответствие с этим, именно вычислительные модели используются для анализа параллельных алгоритмов и оценки эффективности их выполнения на различных аппаратных архитектурах. Вычислительная модель должна отражать ключевые особенности аппаратной архитектуры для того, чтобы верно предсказывать производительность конкретного алгоритма на реальных многопроцессорных системах.
Передача сообщений по соединительной сети
При использовании фрагментного параллелизма, в большинстве случаев, не удается избежать обменов по соединительной сети. Рассмотрим следующий пример. Пусть необходимо выполнить естественное соединение трех отношений R(a,b), S(b,c) и V{c,d). Пусть отношения Rm S фрагментиро-ваны по атрибуту Ъ с помощью одной и той же функции фрагментации/ Это означает, что истинно следующее высказывание:
Mr є R (Vs є S(r.b = s.b = f(r.b) = f(s.b))). Пусть отношение V фрагментироваио по атрибуту с с помощью функции фрагментации g. Тогда, при вычислении (SxV) будет необходимо перераспределять кортежи отношения S по соединительной сети, используя в качестве функции распределения/ В соответствие с этим модель должна предусматривать механизм передачи сообщений по соединительной сети и включать в себя стоимостную функцию для вычисления затрат на межпроцессорные обмены.
Модель должна обеспечивать адекватный механизм оценки стоимости запроса в различных многопроцессорных архитектурах в следующем смысле. Пусть Х- некоторая многопроцессорная иерархическая система баз данных, X — представление этой системы в модели. Пусть Q - некоторый запрос к базе данных, Q - представление этого запроса в модели. Пусть f(Q,X) - функция стоимости выполнения Q в X, предоставляемая моделью. Обозначим через t(Q, X) время выполнения запроса Q в системе X. Тогда функция стоимости/будет адекватной, если для любых систем А иВ и любого запроса Q имеем
Модель должна предоставлять средства для адекватной оценки стоимости алгоритмов, реализующих реляционные операции. Для одной и той же операции в реляционных системах баз данных предусмотрено несколько различных алгоритмов ее выполнения. Эти алгоритмы входят в так называемую физическую алгебру. Например, реляционная операция соединения (JOIN) может быть заменена на одну из следующих операций физической алгебры: NLJ (NestedLoop Join): соединение вложенными циклами; HJ (Hash Join): соединение хешированием; MJ (Merge Join): соединение слиянием; IJ (Index Join): соединение по индексу.
В реальных СУБД этот список может быть уточнен и расширен. Время выполнения различных физических операций соединения для одних и тех же входных отношений может значительно (на порядки) различаться. В соответствие с этим модель должна предоставлять механизмы моделирования выполнения алгоритмов, реализующих реляционные операции.
При использовании фрагментного параллелизма каждое отношение делится на фрагменты, распределяемые по различным процессорным узлам. В соответствие с этим любая транзакция, выполняемая в параллельной СУБД, является параллельной в том смысле, что она распадается на множество агентов, каждый из которых выполняется на отдельном процессорном узле. Агенты обмениваются друг с другом данными и синхронизируются посредством операторов exchange. Модель должна предоставлять адекватные средства для моделирования таких параллельных транзакций.
Любая СУБД, в том числе и параллельная, должна поддерживать межтранзакционный параллелизм [108]. Межтранзакционный параллелизм предполагает выполнение смеси независимых транзакций. Как уже было сказано в предыдущем разделе, каждая такая транзакция распадается на множество параллельных агентов, выполняемых на различных узлах многопроцессорной системы. Соответственно, межтранзакционный параллелизм предполагает выполнение на одном процессорном узле смеси параллельных агентов, принадлежащих различным транзакциям. Выполнение смеси агентов организуется по принципу разделения времени. Такой подход позволяет существенно повысить производительность каждого узла путем перекрытия задержек операций ввода/вывода, выполняемых различными агентами. Таким образом, модель должна поддерживать выполнение смеси параллельных агентов на одном узле в режиме разделения времени.
В соответствие с описанными требованиями в рамках диссертационной работы была предложена новая модель иерархических многопроцессорных систем баз данных DMM {Database Multiprocessor Model) [13, 19], позволяющая моделировать и исследовать произвольные многопроцессорные иерархические конфигурации в контексте приложений класса OLTP. Модель DMM включает себя модель аппаратной платформы, модель операционной среды, стоимостную модель и модель транзакций. В данном разделе строятся формальные описания указанных моделей.
Принципы работы эмулятора DMS
В данном разделе рассматриваются принципы работы эмулятора DMS, моделирующего обработку смеси транзакций в многопроцессорной иерархической системе баз данных.
На рис. 21 показан диаграмма последовательности для операции чтения (см. раздел 2.2.3). Как показано на данной диаграмме, ядро эмулятора инициализирует операцию чтения read процессорного модуля, в качестве параметра выступает уникальный идентификатор idDisk. Если число незавершенных чтений процессорного модуля не превышает максимально допустимое число MAX_READ_COUNT, то проверяется наличие в моделируемой системе дискового модуля с идентификатором idDisk. Если такой модуль присутствует в DM-дереве, процессорный модуль создает новый пакет и, пакету назначается отправитель — диск с уникальным идентификатором idDisk. Адресатом пакета становится создавший его процессор. Пакет начинает свое движение по DM-дереву от диска к процессору. После создания пакета, процессорный модуль увеличивает счетчик на единицу.
Аналогичным образом реализуется операция записи (см. рис. 22). Разница заключается только в том, что пакет начинает свое движение по М-дереву от создавшего его процессора, являющегося, в данном случае, отправителем, к адресату - диску с идентификатором idDisk.
На рис. 23 представлена диаграмма последовательности работы модуля сетевого концентратора. Модуль сетевого концентратора выполняет алгоритм пересылки поступающих во входной буфер пакетов (см. раздел 2.2.3). Пересылка происходит таким образом, что после выполнения каждого такта, пакеты оказываются на один уровень ближе к адресату. Пересылка пакета продолжается до тех пор, пока адресат не получает пакет.
На рис. 24 представлена диаграмма последовательности работы дискового модуля. Дисковый модуль выполняет обработку поступающих во входной буфер пакетов (см. раздел 2.2.3). Дисковый модуль выполняет обработку одного пакета за такт. Если диск является адресатом обрабатываемого пакета, то у процессора отправителя пакета на единицу уменьшается счетчик незавершенных операций записи, после чего пакет удаляется из системы. Таким образом, моделируется запись пакета на жесткий диск. Если диск не является адресатом пакета, то пакет передается во входную очередь вышестоящего сетевого концентратора. Таким образом, моделируется операция чтения с диска.
Для представления информации о мультипроцессорных иерархиях разработан язык описания многопроцессорных иерархических конфигураций HMML (Hierarchical Multiprocessor Markup Language), базирующийся на синтаксисе расширяемого языка разметки XML {Extensible Markup Language) [130]. В алфавит языка HMML входят все символы, допускаемые алфавитом языка XML при использовании таблицы кодировки UTF-8. Комментарии формируются в соответствии с синтаксисом языка XML. Пример описания иерархической многопроцессорной конфигурации приведен нарис. 25.
Во входном файле написанном на языке HMML могут использоваться следующие тэги: id - уникальный идентификатор узла; parent Id - уникальный идентификатор родительского узла; DevType - тип узла (см. 2.2.2), тип Н соответствует модулю сетевого концентратора, Р - процессорному модулю, D - дисковому модулю; costPolinom - структура данных, содержащая коэффициенты стоимостной модели (см. 2.2.4); threshold - пороговый коэффициент т стоимостной модели (см. 2.2.4); info - комментарий, содержащий информацию об узле.
Тэги costPolinom и threshold обязательны при описании модулей сетевых концентраторов и дисковых модулей, но отсутствуют при описании процессорных модулей, так как в OLTP приложениях стоимость операций процессорного модуля крайне мала и ей можно пренебречь (см. 2.2.4).
Для синтаксического анализа входного XML-файла используется XML-схема, представленная на рис. 26.
Влияние интерконнекта и дисков на масштабирование
В ходе данной серии экспериментов с помощью эмулятора моделировалось естественное соединение отношений R и S с использованием алгоритма MHJ. В операции участвовало два вычислительных узла с одним жестким диском и одним одноядерным процессором каждый. Коэффициент перекоса /и задавался равным 0.2, то есть 20% кортежей являлись «своими», а оставшиеся 80% кортежей узлы должны были передавать друг другу по сети. Размеры отношений R и S составляли соответственно 3 000 и 30 000 записей. Графики ускорения, возникающего при увеличении быстродействия жестких дисков и пропускной способности коммуникационной сети, представлены на рис. 30. График зависимости ускорения от пропускной способности сети соответствует ситуации, когда пропускная способность сети фиксировалась равной 20 условным единицам, а быстродействие дисков менялась от 2 до 36 условных единиц. График зависимости ускорения от быстродействия дисков соответствует обратной ситуации, когда быстродействие дисков фиксировалась равным 20 условным единицам, а пропускная способность интерконнекта менялась от 2 до 36 условных единиц.
Из анализа графиков на рис. 30 видно, что при фиксированном быстродействии дисков равном 20 условным единицам, наращивание пропускной способности интерконнекта в диапазоне от двух до 20 условных единиц, оказывает существенное влияние на общий рост производительности системы. В то же время дальнейшее наращивание пропускной способности интерконнекта практически не приводит к росту производительности системы в целом. Аналогичная картина наблюдается и для жестких дисков: при фиксированной пропускной способности сети равной 20 условным единицам, наращивание быстродействия дисков в диапазоне от двух до 20 условных единиц, оказывает существенное влияние на общий рост производительности системы, но дальнейшее наращивание быстродействия дисков практически не приводит к росту производительности системы в целом.
Данный эксперимент показывает, что в вычислительных узлах иерархических многопроцессорных систем баз данных целесообразно устанавливать диски и коммуникационное оборудование приблизительно одинаковой производительности.
Модель DMM и эмулятор DMS могут использоваться при планировании закупок и модернизаций аппаратной части иерархических многопроцессорных систем баз данных. Эмулятор позволяет принимать обоснованные решения по выбору оптимальных аппаратных конфигураций. Рассмотрим применение этого подхода на следующих примерах.
С помощью эмулятора DMS были получены изображенные на рис. 31 графики зависимости времени выполнения транзакции (см. 4.1) от количества и типа узлов в вычислительных кластерах приложений баз данных. В табл. 2 приведены стоимости различных конфигураций вычислительных узлов, содержащих один, два, четыре и восемь процессорных ядер и жестких дисков. В стоимость вычислительных узлов включена стоимость необходимой для их работы инфраструктуры, состоящей из системы бесперебойного электропитания, системы охлаждения, коммуникационной сети InfiniBand QDR, корпусов, блоков питания, монтажных шкафов и др. В со временных центрах обработки данных, построенных на базе отечественных суперкомпьютеров кластерного типа, стоимость инфраструктуры в расчете на один узел кластера, может составлять 250 тыс. руб. Таким образом, полная стоимость одного восьмиядерного вычислительного узла на базе двух четырехъядерных процессоров Intel Хеоп Е5472 [1] с восьмью дисками SAS (Serial Attached SCSI), сегодня составляет 395 тыс. руб., а полная стоимость узла на базе двух двуядерных процессоров Intel Хеоп ЕЗ 110 и с 4 дисками SAS составляет 325 тыс. руб. В табл. 2 для каждого типа узлов представлена стоимость в 2008 г., полученная из архивных источников, текущая рыночная стоимость, а так же прогнозируемая стоимость в 2012 г., полученная из пресс-релизов производителей оборудования.
Рассмотрим пример использования эмулятора DMS. Предположим, что в бюджете некоторой организации в 2010 г. имеется 10 миллионов рублей на приобретение вычислительного кластера для приложений баз данных. Необходимо подобрать на эту сумму наиболее производительную аппаратную архитектуру, варьируя конфигурацию и количество узлов системы. На базе зависимостей, представленных на рис.31, построена табл.3, содержащая различные варианты кластерных конфигураций, стоимость которых составляет около 10 млн. руб. Для каждой конфигурации приведено соответствующее ей время в условных единицах, требуемое для обработки транзакции. По табл. 3 можно определить, что при заданной цене, наибольшую производительность будет обеспечивать конфигурация 4, состоящая из 25 узлов типа 4.
