Автоматика и телемеханика, Л- 5, 2007
PACS 89.20.Ff
© 2007 г. П.С. КОСТЕНЕЦКИЙ, A.B. ЛЕПИХОВ, Л.В. СОКОЛИНСКИЙ, д-р физ.-мат. наук (Южно-Уральский государственный университет)
ТЕХНОЛОГИИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ ДЛЯ ИЕРАРХИЧЕСКИХ МНОГОПРОЦЕССОРНЫХ СРЕД1
Предлагается новый подход к размещению данных и балансировке загрузки в многопроцессорных системах реляционных баз данных с иерархической архитектурой. Описана модель DMM. позволяющая моделировать и исследовать произвольные многопроцессорные иерархические конфигурации в контексте приложений класса OLTP. Рассмотрен важный подкласс многопроцессорных иерархий, названных симметричными. Для симметричных иерархий предложена новая стратегия размещения данных, базирующаяся па методе частичного зеркалировапия. Получены аналитические оценки затрат дискового пространства па репликацию даппых. Для симметричных иерархий, обладающих некоторой регулярностью, доказаны теоремы, дающие оценку трудоемкости формирования реплик. Предложен эффективный метод балансировки загрузки, использующий технику частичного зеркалировапия. Представленные методы ориентированы па использование в кластерах и Grid-системах.
1. Введение
В настоящее время все большее распространение получают иерархические многопроцессорные архитектуры. В многопроцессорной системе с иерархической архитектурой процессорные устройства, память, диски и пр. связываются друг с другом в соответствии с некоторой иерархией. На первом уровне иерархии находятся процессорные ядра, размещенные на одном кристалле. На втором уровне находятся многоядерные процессоры, объединенные в многопроцессорные модули с общей памятью SMP. На третьем уровне SMP-модули объединяются в кластер с помощью высокоскоростной соединительной сети. Четвертый уровень представляют корпоративные Grid-системы, включающие в себя несколько кластеров. Корпоративные Grid-системы могут объединяться в кооперативные Grid-объединения на базе Интернет. И так далее. Одним из наиболее важных приложений для многопроцессорных систем являются параллельные системы баз данных, способные хранить и обрабатывать петабайты данных [1]. Параллельным системам баз данных посвящено большое количество работ, обзор которых можно найти в [2]. однако проблематика систем баз данных с иерархической многопроцессорной архитектурой до настоящего времени исследовалась мало.
В статье рассматриваются вопросы организации параллельных систем баз данных. ориентированной на эффективное использование многопроцессорных иерархий. Выделяются следующие аспекты: моделирование иерархических архитектур, распределение данных и балансировка загрузки. Иерархические архитектуры порождают большое количество различных классов конфигураций. Некоторая клас-
1 Работа выполнена ири финансовой поддержке Российского фонда фундаментальных исследований (проект 06-07-89148) и Южно-Уральского государственного университета (грант 2006-112).
сификация таких архитектур дана в [3]. Исследование подобных архитектур затруднено. так как практическое конструирование мультипроцессоров требует больших финансовых затрат, связанных с приобретением и реконфигурацией дорогостоящего оборудования.
Как следствие актуальной становится задача разработки моделей представления многопроцессорных систем баз данных, которые позволяли бы исследовать различные многопроцессорные конфигурации без их аппаратной реализации. Моделирование одноуровневых архитектур для оперативной обработки транзакций было выполнено Стоунбрейкером и Бхайдом [4. 5]. В [6. 7] моделируются некоторые классы двухуровневых конфигураций, однако в общем виде многопроцессорные иерархические конфигурации не исследовались. В связи с этим возникает проблема выбора оптимального класса конфигураций для определенного класса приложений баз данных. В данной работе описана модель DMM (Database Multiprocessor Model), позволяющая моделировать и исследовать произвольные многопроцессорные иерархические конфигурации в контексте приложений класса OLTP (Ori-Lirie Transaction Processing) [8].
Проблема распределения данных и связанная с ней проблема балансировки загрузки в параллельных системах баз данных без совместного использования ресурсов использовались в целом ряде работ (см., например, [9 12]), однако все эти исследования были ориентированы, главным образом, на одноуровневые многопроцессорные системы. В статье предлагается стратегия размещения данных для иерархических вычислительных систем и алгоритм балансировки загрузки, основанный на методе частичного зеркалирования. Данный алгоритм используется при обработке запросов в прототипе параллельной системы баз данных «Омега» [13].
Статья организована следующим образом. В разделе 2 приводится описание DMM-модели. Представлены модели аппаратной платформы и операционной среды, приведены стоимостная модель и модель транзакций. В разделе 3 рассматриваются стратегия размещения данных и алгоритм балансировки загрузки в иерархической вычислительной системе. Вводится формальное определение симметричной многопроцессорной иерархии. Описывается механизм репликации данных на основе сегментов. Доказываются теоремы, дающие оценки для суммарного размера реплик и трудоемкости формирования реплик при отсутствии помех. Представлен алгоритм балансировки загрузки, основанный на описанном механизме репликации. В разделе 4 суммируются полученные результаты и обсуждаются направления дальнейших исследований.
2. Моделирование иерархических архитектур
Предлагается новая модель DMM, позволяющая моделировать и исследовать произвольные многопроцессорные иерархические конфигурации в контексте приложений класса OLTP. Модель DMM включает в себя модели аппаратного и программного обеспечения, а также стоимостную модель.
2.1. Модель аппаратной платформы
Аппаратное обеспечение параллельной системы баз данных представляется в виде DM-дерева. DM-дерево это ориентированное дерево [14], узлы которого относятся к одному из трех классов:
1) процессорные модули:
2) дисковые модули:
3) модули сетевых концентраторов.
Дуги дерева соответствуют потокам данных. Процессорные модули являются абстрактным представлением реальных процессорных устройств. Дисковые .модули
Рис. 1. Пример DM-дерева.
представляют накопители на жестких магнитных дисках. Модули сетевых концентраторов используются для представления произвольного интерконнекта, соединяющего различные процессорные и дисковые устройства. В качестве интерконнекта могут фигурировать как отдельные сетевые устройства (коммутатор, концентратор и др.). так и системная шина, соединяющая процессор с периферийными устройствами. Модель DMM не предусматривает представление модулей оперативной памяти, так как в задачах OLTP время взаимодействия процессоров и оперативной памяти несоизмеримо меньше времени обменов данными с внешними устройствами.
На структуру DM-дерева накладываются следующие ограничения:
1) корнем DM-дерева может быть только модуль сетевого концентратора:
2) дисковые и процессорные модули не могут иметь дочерних узлов, т.е. они всегда являются листьями DM-дерева.
Пример двухуровневого DM-дерева изображен на рис. 1.
2.2. Модель операционной среды
В рамках модели DMM наименьшей неделимой единицей обработки данных является пакет. Предполагается, что все пакеты имеют одинаковый размер. Пакет содержит заголовок, включающий в себя адрес отправителя, адрес получателя и другую вспомогательную информацию. Передача пакета может соответствовать передаче одного или нескольких кортежей в реальной системе баз данных.
Поскольку рассматриваются только приложения класса OLTP, то можно пренебречь накладными расходами на обмены между двумя процессорами через общую оперативную память и затратами на обработку данных внутри процессоров. В модели DMM любой процессорный модуль может обмениваться данными с любым дисковым модулем. С каждым дисковым модулем и модулем сетевого концентратора в модели DMM ассоциируется очередь, в которую помещаются пересылаемые пакеты.
Модель DMM допускает асинхронный обмен пакетами в том смысле, что процессорный модуль может инициализировать новый обмен, не дожидаясь завершения предыдущего. Однако будем предполагать, что процессорный модуль может иметь в каждый момент не более sr незавершенных операций чтения и sw незавершенных операций записи.
Время работы системы в модели DMM делится па дискретные промежутки, называемые тактами. Такт определяется как фиксированная последовательность шагов. семантика которых будет определена ниже.
Пусть P обозначает множество всех процессорных модулей DM-дерева, D - множество всех дисковых модулей, N - множество всех модулей сетевых концентраторов, M = P U D U N - множество всех узлов DM-дерева. Для произвольного M G M введем следующие обозначения: F(M) - родительский модуль узла M, T(M) - под-
M
Процессорный модуль P G P может инициировать операции чтения и записи пакетов. Определим их семантику следующим образом.
Операция чтения. Пусть процессорному модулю P требуется прочитать пакет E с диска D G D Если процессор P ранее инициализировал sr еще незавершенных операций чтения, то он переводится в состояние ожидания. Если количество незавершенных операций чтения меньше sr, то в очередь диска D помещается пакет E с адресом получателя a(E) = P и адресом отправителя (3(E) = D. Псевдокод данного алгоритма будет иметь следующий вид:
if r(P) < sr then E
P
в очередь D; r(P) + +;
else
wait: end if,
r( P) P s r
малыгое допустимое число незавершенных операций чтения.
PE на диск D G D Псевдокод алгоритма, инициирующего запись, следующий: if w(P) < sw then
E
D
родительского сетевого концентратора: w(P) + +;
else
wait: end if.
w(P) P sw
максимальное допустимое число незавершенных операций записи.
Модуль сетевого концентратора N G N осуществляет перманентную передачу пакетов по соединительной сети, выполняя следующий алгоритм:
E N;
if a(E) G T(N) then
Поместить E в очередь F(N);
else
Найти максимальное поддерево U
дерева T(H), содержащее a(E); if T(a(E)) = U then
if a(E) G P then r(a(E)) --;
else
Поместить E в очередь a(E);
end if
else
Поместить
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.