- БАЗЫ ДАННЫХ И БАЗЫ ЗНАНИЙ
У л :
МОДЕЛИРОВАНИЕ ИЕРАРХИЧЕСКИХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ БАЗ ДАННЫХ
© 2013 г. П.С. Костенецкий, Л.Б. Соколинский
Южно-Уральский государственный университет (НИУ) 454080 Челябинск, просп. им. Ленина, 76 E-mail: kostenetskiy@gmail.com, sokolinsky@acm.org Поступила в редакцию 06.07.2012
В статье рассматриваются вопросы, связанные с моделированием и анализом иерархических многопроцессорных систем, ориентированных на приложения баз данных. Приводятся требования к модели параллельной системы баз данных. Дается обзор и сравнительный анализ известных моделей параллельных систем баз данных. Предлагается новая модель многопроцессорных систем баз данных DMM (Database Multiprocessor Model), позволяющая моделировать и исследовать произвольные иерархические многопроцессорные конфигурации в контексте приложений баз данных класса OLTP. Приводятся примеры использования модели DMM для имитационного моделир ова-ния приложений параллельных систем баз данных для многопроцессорных систем.
1. ВВЕДЕНИЕ
Современные многопроцессорные системы в большинстве случаев организуются по иерархическому принципу. Например, большая часть вычислительных кластеров сегодня имеют трехуровневую архитектуру. В рамках такой архитектуры многопроцессорная система строится как набор однородных вычислительных модулей, соединенных высокоскоростной сетью. Это - первый (верхний) уровень иерархии. Каждый вычислительный модуль является, в свою очередь, многопроцессорной системой с разделяемой памятью и образует второй уровень иерархии. Так как в современной кластерной системе, как правило, используются многоядерные процессоры, то мы получаем третий уровень иерархии. Еще одним источником многопроцессорных иерархий являются Опё- технологии, позволяющие объединять несколько различных кластеров в единую вычислительную систему. Грид-системы можно разделить на три вида в соответствии с масштабом коммуникационной сети: корпоративный грид (к^га^пё), коопе-
* Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект 09-07-00241-а).
ративный грид (extra-grid) и глобальный грид (inter-grid) [3]. Корпоративные грид-системы формируются путем объединения кластеров одной организации локальной соединительной сетью в целях оптимизации использования вычислительных ресурсов. Кооперативные грид-системы формируются путем объединения кластеров и корпоративных грид-систем географически распределенных организаций в целях объединения усилий для решения больших задач. Глобальные грид-системы объединяют десятки кооперативных грид-систем в единую вычислительную среду посредством сети интернет. Глобальные грид-системы обеспечивают использование вычислительных ресурсов миллионов компьютеров и реализуют наиболее масштабные вычислительные системы. Общая структура многопроцессорной иерархии изображена на рис. 1.
Важным классом приложений для многопроцессорных си х параллельную обработку запросов на многопроцессорных вычислительных системах. В области технологий параллельной обработки запросов для реляционных баз данных достигнуты значительные успехи, воплощенные в целом ряде исследовательских и коммерче-
VH
в s
х &
& V' в л я
о
§ iv Н
о, >
III-III-
Глобальный грид
& Корпоративный грид 1 ЦОД -0 6jiBr3
Кооперативный грид
Кластер
I Процессорный узел | RAM
Многоядерный процессор
Рис. 1.
Структура многопроцессорной иерархии.
ских СУБД. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести DB2 Parallel Edition [211, NonStop SQL [15] и Teradata [14]. Подобные системы объединяют тысячи процессоров и жестких дисков и способны обрабатывать нетабайтные базы данных. Тем не менее, в области параллельных систем баз данных до сих нор остается ряд направлений, требующих дополнительных научных исследований [1|. Одно из них дальнейшее развитие аппаратной архитектуры параллельных систем баз данных. В ближайшем будущем крупные организации будут располагать базами данных объемом в несколько петабайт [5]. Для обработки подобных объемов информации потребуются параллельные машины с новыми иерархическими многопроцессорными мшн'оядерными архитектурами, поддерживающими сотни тысяч процессоров [6], что в десятки раз превышает их число в самых мощных современных системах. В соответствие с этим актуальной является задача моделирования и анализа новых иерархических мнох'опроцессорных архитектур для приложений баз данных.
Статья организована следующим образом. В разделе 2 приводится система требований для моделей параллельных систем баз данных. В разделе 3 дается аналитический обзор известных к настоящему моменту моделей параллельных систем баз данных. В разделе 4 предлагается новая комплексная модель параллельнох'о выпол-
нения транзакций для иерархических мшихшро-цессорных архитектур. В разделе 5 приводятся результаты вычислительных экспериментов по моделированию работы приложений баз данных для различных мнох'опроцессорных конфигураций. В разделе 6 суммируются полученные результаты и обсуждаются направления дальнейших исследований.
2. ТРЕБОВАНИЯ К МОДЕЛИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ
Модели параллельных вычислений для приложений баз данных имеют существенную специфику по сравнению с общими моделями параллельных вычислений. Для тохх), чтобы вычислительная модель адекватно представляла работу параллельной системы баз данных на иерархической мнох'опроцессорной платформе, она должна удовлетворять следующим основным требованиям:
1. Учет специфики приложений баз данных класса ОЬТР.
2. Адекватное представление мши'опроцеееор-ных систем с иерархической структурой соединительной сети.
3. Моделирование дисковых операций ввода/вывода.
4. Моделирование фрагментших) параллелизма.
5. Моделирование передачи сообщений по соединительной сети с иерархической структурой.
6. Адекватный метод оценки стоимости запросов.
7. Ориентация на реляционную модель данных.
8. Моделирование параллельной (распределенной) транзакции.
9. Моделирование межтранзакционного параллелизма.
Рассмотрим эти требования более подробно.
Специфика приложений баз данных класса ОЬТР
Специфика приложений реляционных баз данных класса ОЬТР заключается в следующем. Во-первых, предполагается, что база данных, даже с учетом фрагментации, имеет слишком большой размер для того, чтобы полностью поместиться в оперативную память многопроцессорной системы. Отсюда следует, что при выполнении запроса большая часть времени будет потрачена на обмены с дисками и передачу данных по сети. При этом относительная вычислительная сложность ОЬТР-зшцюсов оказывается столь малой, что ею можно пренебречь, то есть считать равной нулю. Во-вторых, с целью перекрытия задержек ввода-вывода при выполнении смеси транзакций, в реляционных СУБД используется механизм буферизации. Он предполагает разбиение дискового пространства на страницы (блоки) фиксированного размера и предварительную загрузку образов дисковых страниц в оперативную память.
Таким образом, при построении модели мы можем пренебречь существованием процессорных кэшей различного уровня и полагать, что каждый процессор имеет встроенную оперативную память с однородным доступом, которая используется с единственной целью - буферизация дисковых страниц. При этом стоимость доступа к данным в оперативной памяти при выполнении команд процессора может полагаться равной нулю. Мы можем также считать, что стоимость вы-
числений, производимых процессором равна нулю.
Иерархическая структура соединительной сети
Как было показано выше, современные многопроцессорные и многоядерные системы имеют иерархическую структуру соединительной сети. При этом, при переходе с одного уровня иерархии на другой, скорость обменов может изменяться на порядок и более. Следовательно, при создании адекватной модели мы должны учитывать этот факт. Это может быть достигнуто путем введения некоторого параметризованного класса абстрактных сетевых устройств, который обобщал бы в себе свойства реального интер-коннекта, начиная с системной шины и кончая маршрутизаторами. В качестве параметра класса должен фигурировать уровень устройства в сетевой иерархии.
Дисковый ввод/вывод
Наряду с передачей данных по соединительной сети, операции обмена с дисками являются наиболее ресурсоемкими. В соответствие с этим модель должна обеспечивать явное представление дисковых устройств. При этом не важен способ организации дискового устройства. Это может быть отдельный раздел диска, жесткий диск, ЫАГО-массив или параллельная система хранения данных. Универсализация может быть достигнута следующим образом. Все рассматриваемы физические устройства группируются в конечное множество физических классов Д\, Д2,..., Дк- В один класс попадают устройства со сходными стоимостными характеристиками. Для каждого класса фиксируется средняя стоимость операций ввода/вывода. Далее вводится параметризованный класс абстрактных дисковых устройств, у которого в качестве параметра фигурирует номер соответствующего физического класса.
Фрагментный параллелизм
Для достижения высокой степени параллелизма при обработке запроса необходимо использовать фрагментацию отношений по процессорным узлам [22]. При этом в реальных приложениях не
удается избежать перекосов [20] в загрузке процессоров, возникающих по причине неравномерного распределения данных. В работе [18] было показано, что перекосы, возникающие при обработке запросов в параллельных системах баз данных без совместного использования ресурсов, могут приводить к практически полной деградации производительности системы. Модель должна учитывать этот фактор.
Передача сообщений по соединительной сети
При использовании фрагментного параллелизма, в большинстве случаев, не удается избежать обменов по соединительной сети. Рассмотрим следующий пример. Пусть необходимо выполнить естественное соединение трех отношений И(а,Ъ), Б(Ь,с) и У(с,с1). Пусть отношения Я ш Б фрагментированы по атрибуту Ь с помощью одной и той же функции фрагментации /. Это означает, что истинно следующее высказывание:
Ут е К (У в е 5 (т.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.