автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы обработки запросов в системах управления базами данных для многопроцессорных систем с иерархической архитектурой

На правах рукописи

ЛЕПИХОВ Андрей Валерьевич

МЕТОДЫ ОБРАБОТКИ ЗАПРОСОВ В СИСТЕМАХ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ ДЛЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ С ИЕРАРХИЧЕСКОЙ АРХИТЕКТУРОЙ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003455803

Москва - 2008

003455803

Работа выполнена на кафедре системного программирования Южно-Уральского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор

СОКОЛИНСКИЙ Леонид Борисович.

Ведущая организация: Санкт-Петербургский

государственный университет.

Защита состоится 19 декабря 2008 года в 15 часов на заседании диссертационного совета Д 501.002.09 при Московском государственном университете им. М.В. Ломоносова по адресу: 119992, г. Москва, Ленинские горы, д. 1, стр. 4, НИВЦ МГУ, конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИВЦ МГУ.

Автореферат разослан 17 ноября 2008 года.

Ученый секретарь

Официальные оппоненты: доктор технических наук, профессор

КУЗНЕЦОВ Сергей Дмитриевич;

кандидат физико-математических наук ЖУМАТИЙ Сергей Анатольевич.

диссертационного совета

Суворов В.В.

Общая характеристика работы

Актуальность темы. В настоящее время все большее распространение получают параллельные системы баз данных, ориентированные на мультипроцессоры с иерархической архитектурой. Это связано с тем, что современные многопроцессорные системы в большинстве случаев организуются по иерархическому принципу. Большая часть суперкомпьютеров сегодня имеют двухуровневую кластерную архитектуру. В соответствии с данной архитектурой многопроцессорная система строится как набор однородных вычислительных модулей, соединенных высокоскоростной сетью. При этом каждый вычислительный модуль является в свою очередь многопроцессорной системой с разделяемой памятью. Если в системе используются еще и многоядерные процессоры, то мы получаем третий уровень иерархии. Другим источником многопроцессорных иерархий являются грид-технологии, позволяющие объединять несколько различных суперкомпьютеров в единую вычислительную систему. Подобная грид-система будет иметь многоуровневую иерархическую структуру. На нижних уровнях иерархии располагаются процессоры отдельных кластерных систем, соединенные высокоскоростной внутренней сетью. На верхних уровнях располагаются вычислительные системы, объединенные корпоративной сетью. Высший уровень иерархии может представлять сеть Интернет.

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

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

иерархической СУБД. Для достижения этой цели необходимо было решить следующие задачи:

1. Разработать и аналитически исследовать стратегию размещения и репликации базы данных для многопроцессорных иерархических систем.

2. Разработать эффективный алгоритм динамической балансировки загрузки на основе предложенной стратегии размещения данных.

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

4. Реализовать разработанные методы и алгоритмы в прототипе иерархической СУБД «Омега».

5. Провести вычислительные эксперименты для оценки эффективности предложенных решений.

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

Научная новизна работы заключается в следующем:

1) предложена модель симметричной многопроцессорной иерархической системы;

2) предложен метод частичного зеркапирования, использующий функцию репликации, которая сопоставляет каждому уровню иерархии определенный коэффициент репликации;

3) получены аналитические оценки трудоемкости формирования и обновления реплик в методе частичного зеркалирования;

4) разработан новый алгоритм балансировки загрузки для параллельных СУБД с иерархической архитектурой;

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

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

на Четвертом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (1-2 июня 2006 г., Москва);

на Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования» (18-23 сентября 2006 г., Новороссийск); - на Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач» (22-27 сентября 2008 г., Новороссийск);

на Международной научной конференции «Параллельные вычислительные технологии» (29 января - 2 февраля 2007 г., Челябинск).

Публикации. Основные научные результаты диссертации опубликованы в 6 печатных работах, приведенных в конце автореферата. Статья [1] опубликована в научном журнале «Автоматика и телемеханика», включенном ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора наук. В статье [1] A.B. Лепихову принадлежит раздел 3 (стр. 118-124). В работах [4, 5] Л.Б. Соколинскому принадлежит постановка задачи; A.B. Лепихову принадлежат все полученные результаты.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 102 страницы, объем библиографии - 113 наименований.

Содержание работы

Во введении приводится обоснование актуальности темы, формулируются цели работы, ее новизна и практическая значимость; приводится обзор работ по тематике исследования и кратко излагается содержание диссертации.

Первая глава, «Многопроцессорные иерархии», посвящена исследованию многопроцессорных вычислительных систем с иерархической архитектурой.

Иерархические многопроцессорные системы состоят из нескольких уровней иерархии. Первый уровень иерархии представлен многоядерными процессорами. На втором уровне иерархии многоядерные процессоры объединяются в процессорные узлы с SMP-архитектурой. На третьем уровне иерархии процессорные узлы, объединяются в кластер. На четвертом уровне кластеры объединяются в кооперативную грид-систему. На пятом уровне кооперативные грид-системы объединяются в ассоциацию, образующую

5

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

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

Далее строится симметричная модель многопроцессорной иерархии применительно к системам баз данных. В основе симметричной модели лежит понятие БМ-дерева, являющегося ориентированным деревом, узлы которого относятся к одному из трех классов: ф(Г) - класс «процессорные модули»; 2Э(Г) - класс «дисковые модули»; У1(Т) - класс «модули сетевых концентраторов». С каждым узлом V е 9Л(7') в 1>М-дереве Г связывается коэффициент трудоемкости г/(у), являющийся вещественным числом, большим либо равным единицы. Коэффициент трудоемкости определяет время, необходимое узлу для обработки некоторой порции данных.

£>М-деревья А и В называются изоморфными, если существуют взаимно однозначное отображение Г множества ШТ(А) на множество 9Л(Б) и взаимно однозначное отображение § множества <В(А) на множество <Е(5) такие, что:

1) узел V является конечным узлом дуги е в дереве А тогда и только тогда, когда узел А^) является конечным узлом дуги g(e) в дереве В;

2) узел является начальным узлом дуги е в дереве А тогда и только тогда, когда узел АУ) является начальным узлом дуги §(е) в дереве В;

3) реЩА) о адеф(В);

4) ¿е£)(А) о

5) леЭТ(Л) о

6) Я№)) = 1700.

Упорядоченная пара отображений Ч = называется изоморфизмом йМ-дерева А на ИМ-дерево В.

DM-дерево T высоты Н называется симметричным, если выполняются следующие условия:

1) любые два смежных поддерева уровня 1<Н являются изоморфными;

2) любое поддерево уровня Н-1 содержит в точности один диск и один

процессор.

Далее проводится анализ параллельной, распределенной и иерархической СУБД, который показывает, что иерархическая СУБД совмещает в себе черты параллельной и распределенной СУБД. Эта двойственная природа иерархической СУБД вытекает из базовых свойств многопроцессорной иерархии: однородность по горизонтали и неоднородность по вертикали. Неоднородность по вертикали сближает иерархические СУБД с распределенными, а однородность по горизонтали - с параллельными.

Далее описываются две модели реализации параллельных исполнителей запросов, основанные на использовании скобочного шаблона и оператора обмена exchange.

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

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

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

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

Стратегия размещения данных предполагает использование горизонтальной фрагментации отношений. Каждое отношение разбивается на непересекающиеся горизонтальные фрагменты, которые размещаются на различных дисках. Фрагмент делится на логические сегменты, между которыми определено отношение порядка, называемое естественным порядком. На практике естественный порядок может определяться физическим порядком следования кортежей или индексом. Будем обозначать количество кортежей через Т^), а длину сегмента через Ь(/г).

Стратегия репликации описывается следующим образом. На каждом дисковом модуле ё1 е 2)(7") (/' > 0) фрагмент может иметь несколько (возможно неполных) зеркальных копий, называемых репликами, которые располагаются на других дисках. Размер реплики ^ задается коэффициентом репликации р,еЖ, 0 < р; < 1, являющимся атрибутом реплики и вычисляется по следующей формуле

Т(^) = Т(/^0) - [(1 - р,) • )] • . (1)

Пусть фрагмент располагается на диске с!0 е 2>(Г). Мы будем использовать следующий метод для построения реплики Г1 на диске й1 б 33(7") (1 > 0), называемый методом частичного перколирования. Построим последовательность поддеревьев дерева Т

{А/0,А/„...,Л/Я_2Ь (2)

обладающую следующими свойствами:

I(MJ) = j

(3)

для всех 0<]<Н-2. Здесь /(Му) обозначает уровень поддерева Л/;. Для

любого симметричного дерева Т существует только одна такая последовательность. Будем считать, что

Л ='•(/)■ (4)

Для формирования реплики ^ на диске используется описанная выше стратегия репликации с коэффициентом репликации, определяемым по формуле (4).

Следующая теорема дает оценку для размера реплики в методе частичного зеркалирования.

Теорема 1. Пусть Т - симметричное ОМ-дерево высоты Н = И(Т)> 0. Пусть фрагмент Г0 располагается на диске ¿/0 € Х>(Г). Пусть А/ поддерево дерева Г такое, что 1</(М)<Я-1 и с10 еЗЭ(А/). Пусть М' - произвольное смежное с М поддерево дерева Т. Тогда для любого с11 е ■Ю(М') справедлива следующая оценка для размера реплики /; фрагмента , размещенной на диске с!::

где L(F0) - длина сегмента для фрагмента F0.

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

Теорема 2. Пусть Т - симметричное DM-дерево высоты Н> 2. Пусть фрагмент F0 располагается на диске de е 1?(Г). Обозначим степень уровня /

И' >1

дерева Т как 8Г Обозначим R(FV) = ^ Т(/;) - суммарное количество кортежей во всех репликах фрагмента Fa. Тогда

R(F0)=T(F0)|>U)(<S7 -1)П <5; +O(L(F0)). (5)

j=0 1

Далее проводится анализ функции репликации. При выборе функции репликации г{1) целесообразно учитывать коэффициенты трудоемкости узлов DM-лерева. Очевидно, что в симметричном DM-дереве все вершины уровня / имеют одинаковую трудоемкость Назовем симметричное

DM-дерево Г регулярным, если для любых двух уровней / и /' дерева Т справедливо

/</' (6)

Следующая теорема позволяет получить оценку трудоемкости покор-тежного формирования реплики в регулярном ¿Ж-дереве.

Теорема 3. Пусть Т - регулярное DM-дерево высоты Н > 0. Пусть фрагмент FQ располагается на диске dn еЭ(Г). Пусть М поддерево дерева Т такое, что 1 <1(М)<Н -2 и с/0е£)(М). Пусть М' - произвольное смежное с М поддерево дерева Т; Ft — реплика фрагмента F0, размещенная на диске d: б 5D(M'). Обозначим г(/;) - трудоемкость покортежного формирования реплики Ft при отсутствии помех. Тогда

z(F,) = т,(ЦМ) -1) ■ г(1(М) - 1)T(F0) + 0(%), где щ = ^(0) - коэффициент трудоемкости корня дерева Т.

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

Теорема 4. Пусть Г - регулярное DM-mрево высоты Н> 2. Пусть фрагмент F0 располагается на диске d0 е ЩТ). Обозначим степень уровня /

|»17)|

дерева Г как 5Г Обозначим t(F„)= £ - суммарная трудоемкость по-

;=i

кортежного формирования всех реплик фрагмента F0 без учета помех. Тогда

г(^) = T(F0)Z'7-:О П ** + • (7)

j=0 к*/* I

Определим рекурсивно нормальную функцию репликации г(1) следующим образом:

т){!){8,-\)8м

Справедлива следующая теорема.

Теорема 5. Пусть Т- регулярное ЛЛ^-дерево высоты И >2. Пусть Р -множество фрагментов, составляющих базу данных. Пусть К - множество всех реплик всех фрагментов из множества Ж, построенных с использованием нормальной функции репликации. Пусть Т(Е) - размер базы данных в кортежах (здесь мы предполагаем, что все кортежи имеют одинаковую длину в байтах), г(К) - суммарная трудоемкость покортежного формирования всех реплик без учета помех. Тогда

где к - некоторая константа, не зависящая от Г.

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

Далее описывается предлагаемый в диссертационном исследовании метод балансировки загрузки. Пусть задан некоторый запрос (2, имеющий п входных отношений. Пусть £2 - параллельный план запроса (}. Каждый агент <2 б £} имеет п входных потоков . .,л„. Входной поток представляет собой структуру, абстрагирующую параллельного агента от входного отношения.

На начальном этапе выполнения запроса выполняется инициализация агента, Затем агент переводится в активное состояние и начинает обработку данных, поставляемых его входными потоками. После того, как все данные из потока выработаны, агент переходит в пассивное состояние.

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

Далее предлагается оптимистическая стратегия выбора аутсайдера и функция балансировки. Оптимистическая стратегия основана на механизме рейтингов. Каждому агенту параллельного плана в процессе балансиров-

ки загрузки присваивается рейтинг. В качестве аутсайдера всегда выбирается агент, имеющий максимальный положительный рейтинг. Если таковые агенты отсутствуют, то освободившийся агент завершает свою работу. Для вычисления рейтинга оптимистическая стратегия использует рейтинговую функцию у : О. -» R следующего вида:

Здесь Я - положительный весовой коэффициент, регулирующий влияние коэффициента репликации на величину рейтинга; В - целое неотрицательное число, задающее нижнюю границу количества сегментов, которое можно передавать при балансировке нагрузки.

Функция балансировки Л для каждого потока J, агента-аутсайдера определяет количество сегментов, передаваемых агенту-лидеру на обработку. Мы предлагаем следующую функцию балансировки:

A(i1) = min(fiI/2l,r(/(^))s(/)).

где q, - количество сегментов в отрезке, подлежащем обработке.

В третьей главе, «Иерархическая СУБД «Омега», описывается реализация прототипа иерархической СУБД «Омега» для многопроцессорных иерархий. СУБД «Омега» включает в себя следующие подсистемы: Пользователь, Клиент, Координатор и Ядро СУБД.

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

Основной задачей Координатора является доставка запроса от Клиента на Ядра СУБД. Координатор принимает запрос от каждого обратившегося к нему Клиента и передает его Ядрам СУБД, которые будут выполнять обработку данного запроса.

Ядро СУБД непосредственно выполняет обработку запроса и передает результат тому Координатору, от которого поступил запрос.

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

Далее описывается реализация оператора обмена exchange, который обеспечивает параллельное выполнение запроса. Оператор exchange вводит в набор физических операций четыре новых оператора: merge, split,

scatter и gather, каждый из которых реализован в соответствии с итера-торной моделью управления.

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

Операторы scatter и gather определяют стратегию обменов кортежами между параллельными агентами в процессе обработки запроса. В данной реализации предлагается стратегия пакетированной передачи кортежей, предназначенная для эффективного использования коммуникационной сети.

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

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

В предлагаемой реализации процедура балансировки загрузки носит асинхронный характер. При возникновении ситуации балансировки интерпретатор передает менеджеру агентов сообщение о необходимости выполнения балансировки и не прерывает обработку запроса.

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

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

коэффициент перекоса //, в соответствии с которым кортежи подразделяются на два класса: «свои» и «чужие» Коэффициент /л указывает процентное содержание «чужих» кортежей во фрагменте.

В первой серии экспериментов были исследованы параметры балансировки загрузки, такие как интервал балансировки и размер сегмента. Исследование интервала балансировки загрузки (см. рис. 1) показывает, что накладные расходы при увеличении частоты опроса узлов не оказывают существенного воздействия на итоговое время выполнения запроса. Этот факт достигается благодаря асинхронному методу реализации балансировки загрузки в прототипе иерархической СУБД «Омега». Проведенные эксперименты показывают, что хорошим выбором будет использование интервала балансировки равного 1 секунде.

Исследование влияния размера сегмента на эффективность балансировки (см. рис. 2) показывает, что сегменты небольшого размера ухудшают показатели балансировки, поскольку существенно возрастает количество «мелких» балансировок, что ведет к росту накладных расходов на перераспределение заданий между параллельными агентами. Большие значения размера сегмента также являются неэффективными, так как в этом случае размер сегмента становится сравнимым с размером фрагмента, что делает балансировку невозможной. Результаты экспериментов показывают, что оптимальным будет промежуточное значение, которое в данном случае равно 20 ООО кортежей. Эта величина составляет примерно 0.01% от средней величины фрагмента.

Во второй серии экспериментов исследовалось влияние метода балансировки загрузки на время обработки запросов. Результаты данных испытаний показаны на рис.3. Данные эксперименты показывают, что оптимальным выбором является значение р=0.8, которое позволяет практически полностью устранить негативное влияние перекосов по атрибуту фрагментации.

Последняя серия экспериментов была посвящена исследованию масштабируемости предложенного в диссертационной работе метода балансировки загрузки. Результаты этих экспериментов представлены на рис. 4, рис. 5 и рис. 6. В экспериментах, показанных на графике 4, было исследовано влияние величины коэффициента перекоса по атрибуту соединения на ускорение. Результаты данных экспериментов показывают, что балансировка загрузки дает наибольший эффект при значении ¡л=50%.

В экспериментах, показанных на графике 5, исследовалось влияние коэффициента репликации на коэффициент ускорения. Результаты данных экспериментов демонстрируют увеличение коэффициента ускорения при выполнении балансировки загрузки. При этом следует отметить, что в данном случае хорошим выбором будетр~0.8.

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

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

Рис 1. Зависимость времени выполнения запроса от интервала балансировки (п=64, ц =50%).

Рис 2. Зависимость времени выполнения запроса от размера сегмента (л=64,/и =50%).

Рис 4. Зависимость коэффициента ускорения от перекоса по значению атрибута соединения }1 (/7=64, р~0.5).

Рис 3. Влияние коэффициента репликации на время выполнения запроса (М =50%, и=64).

20 40 60 80 95 99 100 Количество "Чужих" кортежей (в %)

0.2 0.4 0.5 0.6 0.8 Коэффициент репликации

—О-8 узлов

• -О — 16 узлов —¿х—32 узла - О - • 64 \-зла

0.00 0.20 0.40 0.60 0.80 1.00 Коэффициент репликации

Рис 5. Зависимость ускорения от коэффициента репликации р. {п=64у /л~50%).

Рис 6. Влияние перекоса по данным на коэффициент ускорения (д—50%, р=0.50).

0.01 0.5 1 2 4 6 8 10 Интервал балансировки (сек.)

0 0.2 2 20 200 400 800 1600 2000 PaiMep сегмента (тыс. кортежей)

Основные результаты диссертационной работы

На защиту выносятся следующие новые научные результаты.

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

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

3. Разработан прототип иерархической СУБД «Омега», реализующий предложенные методы и алгоритмы. Проведены тестовые испытания СУБД «Омега» на вычислительных кластерах, входящих в грид-систему «СКИФ-Полигон», подтвердившие эффективность предложенных алгоритмов, методов и подходов.

Публикации по теме диссертации

Статьи, опубликованные в научных журналах из списка ВАК

1. Лепихов Aß. Технологи и параллельных систем баз данных для иерархических многопроцессорных сред,/ Лепихов A.B., Соколинский Л.Б., Кос-тенецкий П.С. // Автоматика и телемеханика. -2007. -No. 5. -С. 112-125.

Другие публикации

2. Лепихов A.B. Модель вариантов использования параллельной системы управления базами данных для грид // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». -Челябинск : ЮУрГУ, 2008 г. -No. 15 (115).-Вып. 1.-С. 42-53.

3. Лепихов А. В. Балансировка загрузки при выполнении операций соединения в параллельных СУБД для кластерных систем // Научный сервис в сети Интернет: решение больших задач. Труды Всероссийской научной конференции (22-27 сентября 2008 г., г. Новороссийск). -М.: Изд-во МГУ, 2008.-С. 292-295.

4. Лепихов A.B. Стратегия размещения данных в многопроцессорных системах с симметричной иерархической архитектурой/A.B. Лепихов,

Л. Б. Соколинский // Научный сервис в сети Интернет: технологии параллельного программирования. Труды Всероссийской научной конференции (18-23 сентября 2006 г., г. Новороссийск). -М.: Изд-во МГУ, 2006. -С. 39-42.

5. LepikhovA. V. Data Placement Strategy in Hierarchical Symmetrical Multiprocessor Systems / A. V. Lepikhov, L.B. Sokolinsky II Proceedings of Spring Young Researchers' Colloquium in Databases and Information Systems (SYRCoDIS'2006), June 1-2,2006. -Moscow, Russia: Moscow State University. -2006. -C. 31-36.

6. A.B. Лепихов Свидетельство Роспатента об официальной регистрации программы для ЭВМ «Параллельная СУБД «Омега» для кластерных систем» ¡А.В. Лепихов, Л.Б Соколинский, М.Л. Цымблер-, -№2008614996 от 03.10.2008.

Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект 06-07-89148).

Подписано в печать 16.11.2008 Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л 1,2. Тираж 100 экз. Заказ № 76 Бесплатно

Южно-Уральский государственный университет 454080 Челябинск, пр, Ленина, 76

Типография Издательства ЮУрГУ 454080, г Челябинск, пр. им В.И. Ленина, 76

Введение.

Глава 1. Многопроцессорные иерархии.

1.1. Предпосылки появления многопроцессорных иерархий.

1.1.1. Многоядерные процессоры.

1.1.2. Вычислительные кластеры.

1.1.3. Грид.

1.2. Структура многопроцессорной иерархической системы.

1.3. Формальная модель многопроцессорной иерархии.

1.4. СУБД для многопроцессорных иерархий.

1.5. Организация параллельной обработки запросов.

1.5.1. Скобочный шаблон.

1.5.2. Оператор обмена exchange.

1.5.3. Параллельная обработка запроса.

Глава 2. Размещение данных и балансировка загрузки.

2.1. Фрагментация и сегментация данных.

2.2. Репликация данных.

2.2.1. Алгоритм построения реплики.

2.2.2. Метод частичного зеркалирования.

2.2.3. Функция репликации.

2.3. Метод балансировки загрузки.

2.3.1. Схема работы параллельного агента.

2.3.2. Алгоритм балансировки загрузки.

2.3.3. Стратегия выбора аутсайдера.

2.3.4. Функция балансировки.

Глава 3. Иерархическая СУБД «Омега».

3.1. Модель вариантов использования СУБД «Омега».

3.1.1. Общие требования к иерархической СУБД.

3.1.2. Структура иерархической СУБД.

3.1.3. Варианты использования системы «Омега».

3.2. Форматы входных и выходных данных.

3.2.1. Спецификация языка RQL.

3.2.2. Спецификация лог-файла.

3.3. Реализация СУБД «Омега».

3.3.1. Реализация оператора обмена exchange.

3.3.2. Механизм балансировки загрузки.

Глава 4. Вычислительные эксперименты.

4.1. Операция соединения методом хеширования в оперативной памяти.

4.2. Параметры вычислительных экспериментов.

4.3. Исследование параметров балансировки загрузки.

4.4. Исследование влияния балансировки загрузки на время выполнения запросов.

4.5. Исследование масштабируемости алгоритма балансировки загрузки

АКТУАЛЬНОСТЬ ТЕМЫ

В настоящее время все большее распространение получают параллельные системы баз данных, ориентированные на мультипроцессоры с иерархической архитектурой [15]. Это связано с тем, что современные многопроцессорные системы в большинстве случаев организуются по иерархическому принципу. Большая часть суперкомпьютеров сегодня имеют двухуровневую кластерную архитектуру. В соответствии с данной архитектурой многопроцессорная система строится как набор однородных вычислительных модулей, соединенных высокоскоростной сетью. При этом каждый вычислительный модуль является в свою очередь многопроцессорной системой с разделяемой памятью. Если в системе используются еще и многоядерные процессоры, то получаем третий уровень иерархии.

Другим источником многопроцессорных иерархий являются Grid-технологии [48], позволяющие объединять несколько различных суперкомпьютеров в единую вычислительную систему. Подобная Grid-система будет иметь многоуровневую иерархическую структуру. На нижних уровнях иерархии располагаются процессоры отдельных кластерных систем, соединенные высокоскоростной внутренней сетью. На верхних уровнях располагаются вычислительные системы, объединенные корпоративной сетью. Высший уровень иерархии может представлять сеть Интернет.

Иерархические многопроцессорные системы обладают рядом особенностей. В рамках одного уровня иерархии скорость обмена сообщениями между вычислительными узлами практически одинакова. При переходе на более высокие уровни иерархии скорость межпроцессорных обменов может уменьшаться на несколько порядков. Следовательно, системы управления базами данных (СУБД) для многопроцессорных иерархий, или кратко -иерархические СУБД, занимают промежуточное положение между паралдельными СУБД, для которых характерна одинаковая скорость межпроцессорных обменов, и распределенными СУБД, в которых скорость обмена сообщениями может значительно отличаться для разных пар вычислительных узлов. Детально сходства и различия этих трех классов СУБД будут обсуждаться в главе 1. Анализ показывает, что не все алгоритмы и методы, используемые в параллельных и распределенных СУБД, могут быть перенесены в иерархические СУБД, а те алгоритмы и методы, которые такой перенос допускают, как правило, нуждаются в существенной адаптации. В соответствии с этим актуальной является задача разработки эффективных алгоритмов и методов обработки запросов, ориентированных на применение в системах баз данных с иерархической многопроцессорной архитектурой, масштабируемой до десятков тысяч процессорных узлов.

ОБЗОР РАБОТ ПО ТЕМАТИКЕ ИССЛЕДОВАНИЯ

Современные исследования в области иерархических СУБД опираются на алгоритмы и методы, применяемые в распределенных и параллельных системах баз данных.

Основы технологии распределенной обработки запросов в реляционных базах данных были впервые разработаны и реализованы в СУБД System R* [27]. Дальнейшее развитие технологии распределенной обработки запросов получили в ряде исследовательских прототипов (см., например, [21, 35, 105, 106]). Однако до появления успешных коммерческих проектов распределенных СУБД пришлось решить ряд проблем, таких как синхронизация доступа к распределенным данным [29,62,92], управление распределенными транзакциями [55, 109], поддержка репликации данных [34, 103, 108], многоуровневая защита данных [44, 90] и др. Более полный обзор результатов и исследовательских проблем в области распределенных СУБД можно найти в работах [53, 72, 107].

Базовые принципы построения параллельных СУБД были разработаны и реализованы в девяностых годах прошлого века в ряде прототипов, из которых наиболее известными являются Volcano [60], GAMMA [41], BUB-ВА [22] и GRACE [51]. В прототипе GRACE (архитектура с общей памятью) были предложены параллельные алгоритмы соединения, основанные на сортировке и хешировании [71]. В прототипе параллельной СУБД Volcano (архитектура с общей памятью) реализована операторная модель параллельного выполнения запросов [58]. В рамках проекта GAMMA (архитектура без совместного использования ресурсов) реализована технология горизонтальной фрагментации базы данных [77] и предложены параллельные алгоритмы обработки запросов, основанные на хешировании [42]. Среди ключевых направлений проекта BUBBA (архитектура без совместного использования ресурсов) можно выделить следующие: разработка стратегии оптимального размещения данных [37], управление параллельными потоками данных [17] и автоматическое распараллеливание запросов [23].

Проведенные исследования показали, что наилучшей базовой архитектурой для параллельных систем баз данных является архитектура без совместного использования ресурсов [104]. Поэтому в дальнейшем основные усилия были сконцентрированы в области поиска эффективных методов и алгоритмов параллельной обработки запросов в системах без совместного использования ресурсов. В рамках этого направления решались задачи оптимизации запросов для параллельной обработки [52, 65], адаптивной обработки запросов [40, 56] и управления вычислительными ресурсами [32, 57]. Результатом данных научных исследований стало появление ряда коммерческих параллельных СУБД с архитектурой без совместного использования ресурсов, среди которых наиболее известными являются Non Stop SQL [28], Teradata [87] и DB2 Parallel Edition [5].

Для параллельных систем баз данных без совместного использования ресурсов особое значение имеют проблема балансировки загрузки [66, 113], и связанная с ней проблема размещения данных [83, 112]. В работе [75] было показано, что перекосы [82], возникающие при обработке запросов в параллельных системах баз данных без совместного использования ресурсов, могут приводить к практически полной деградации производительности системы. Поэтому теме балансировки загрузки посвящено значительное количество работ (см., например, [63,66,91,99,102,113]). Исследования проблемы балансировки загрузки осуществлялись в рамках следующих двух основных подходов. Первый подход состоит в предупреждении перекосов и предполагает разработку стратегии размещения данных, при которой нагрузка будет равномерно распределяться между процессорными узлами системы [67, 78, 99]. Наибольший интерес здесь представляет подход, называемый адаптивным распределением [68, 79]. В соответствии с этим подходом способ размещения данных может меняться, когда СУБД находит лучшую стратегию размещения данных. Второй подход заключается в динамическом перераспределении данных между вычислительными узлами в процессе обработки запроса [64, 66]. Однако следует отметить, что в общем виде проблема балансировки загрузки для параллельных систем баз данных без совместного использования ресурсов не решена до сих пор.

В середине девяностых годов начались исследования в области иерархических СУБД. В работе [25] предложен метод динамической балансировки загрузки при обработке запросов в двухуровневых иерархических многопроцессорных системах. Первый (локальный) уровень представляет собой SMP-систему, второй (глобальный) - набор SMP-узлов, объединенных коммуникационной сетью. Главной идеей метода является использование межоператорного параллелизма на первом уровне иерархии и фраг-ментного параллелизма на втором уровне. При этом эффективная динамическая балансировка происходит только на первом уровне. Данный метод не может быть расширен для использования в многопроцессорных иерархиях с большим количеством уровней.

В работе [45] была предложена методика оптимизации операций параллельного ввода/вывода, ключевым элементом которой является использование репликации для уменьшения времени простоя вычислительных узлов. Развитие данной методики в работе [46] привело к разработке стратегии распределения данных в параллельных СУБД, использующих репликацию для оптимизации параллельного ввода/вывода. Итогом этих исследований стала работа [47], в которой предложено решение проблемы балансировки загрузки для архитектур вычислительных систем без совместного использования ресурсов, основанное на репликации. Данное решение позволяет уменьшить накладные расходы на передачу данных по сети в процессе балансировки загрузки. Однако метод балансировки загрузки предлагается в весьма узком контексте пространственных баз данных в специфическом сегменте диапазонных запросов.

Еще одним актуальным направлением исследований является параллельная обработка запросов в среде грид [57, 97]. В работе [81] выполнен анализ операции соединения методом хеширования и выделены наиболее значимые параметры, влияющие на скорость выполнения оператора соединения. В рамках проекта GParGRES [73] разработано программное обеспечение промежуточного слоя для параллельной обработки OLAP-запросов в грид средах. Проект GParGRES реализован на базе СУБД PostgreSQL и предназначен для использования в двухуровневых многопроцессорных иерархиях. Нижний уровень представляет собой вычислительный кластер. Верхний уровень представляет собой грид-систему, являющуюся набором вычислительных кластеров, объединенных некоторой коммуникационной сетью. В целях балансировки загрузки системы при обработке сложных OLAP-запросов база данных дублируется на всех сайтах грид-системы. Следует, отметить, что методы параллельной обработки запросов, предложенные в данной работе, не могут использоваться в многопроцессорных иерархиях с большим числом уровней. Вместе с тем, размещение полной копии базы данных на каждом из сайтов грид-системы может порождать значительные накладные расходы при распространении обновлений.

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

ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ

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

1. Разработать и аналитически исследовать стратегию размещения и репликации базы данных для многопроцессорных иерархических систем.

2. Разработать эффективный алгоритм динамической балансировки загрузки на основе предложенной стратегии размещения данных.

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

4. Реализовать разработанные методы и алгоритмы в прототипе иерархической СУБД «Омега».

5. Провести вычислительные эксперименты для оценки эффективности предложенных решений.

МЕТОДЫ ИССЛЕДОВАНИЯ

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

НАУЧНАЯ НОВИЗНА

Научная новизна работы заключается в следующем:

1. Предложена модель симметричной многопроцессорной иерархической системы.

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

3. Получены аналитические оценки трудоемкости формирования и обновления реплик в методе частичного зеркалирования.

4. Разработан новый алгоритм балансировки загрузки для параллельных СУБД с иерархической архитектурой.

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

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ

Теоретическая ценность работы состоит в том, что дано формальное описание симметричной многопроцессорной системы с иерархической архитектурой. Представлены доказательства теорем об оценке размера реплик и оценке трудоемкости формирования реплик без учета помех для метода частичного зеркалирования.

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

СТРУКТУРА И ОБЪЕМ РАБОТЫ

Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 102 страницы, объем библиографии - 113 наименований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

На защиту выносятся следующие новые научные результаты:

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

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

3. Разработан прототип иерархической СУБД «Омега», реализующий предложенные методы и алгоритмы. Проведены тестовые испытания СУБД «Омега» на вычислительных кластерах, входящих в гридсистему «СКИФ-Полигон», подтвердившие эффективность предложенных алгоритмов, методов и подходов.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Лепихов А.В.Технологии параллельных систем баз данных для иерархических многопроцессорных сред / Лепихов А.В., Соколинский Л.Б., Костенецкий П. С. // Автоматика и телемеханика. -2007. -No. 5.

-С. 112-125.

2. Лепихов А.В. Модель вариантов использования параллельной системы управления базами данных для грид // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». -Челябинск : ЮУрГУ, 2008 г. -№ 15 (115). -Вып. 1. -С. 42-53.

3. Лепихов А.В. Балансировка загрузки при выполнении операций соединения в параллельных СУБД для кластерных систем // Научный сервис в сети Интернет: решение больших задач. Труды Всероссийской научной конференции (22-27 сентября 2008 г., г. Новороссийск). -М.: Изд-во МГУ, 2008. -С. 292-295.

4. Лепихов А.В. Стратегия размещения данных в многопроцессорных системах с симметричной иерархической архитектурой /А.В. Лепихов,

Л.Б. Соколинский II Научный сервис в сети Интернет: технологии параллельного программирования. Труды Всероссийской научной конференции (18-23 сентября 2006 г., г. Новороссийск). -М.: Изд-во МГУ, 2006. -С. 39-42.

5. Lepikhov А. V. Data Placement Strategy in Hierarchical Symmetrical Multiprocessor Systems / A. V. Lepikhov, L.B. Sokolinsky // Proceedings of Spring Young Researchers' Colloquium in Databases and Information Systems (SYRCoDIS'2006), June 1-2, 2006. -Moscow, Russia: Moscow State University. -2006. -C. 31-36.

6. А.В. Jlenuxoe Свидетельство Роспатента об официальной регистрации программы для ЭВМ «Параллельная СУБД «Омега» для кластерных систем» / А.В. Jlenuxoe, Л.Б. Соколиискии, М.Л. Цымблер; -№2008614996 от 03.10.2008.

Статья [1] опубликована в научном журнале «Автоматика и телемеханика», включенном ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора наук. В статье [1] А.В. Лепихову принадлежит раздел 3 (стр. 118-124). В работах [4, 5] Л.Б. Соколинскому принадлежит постановка задачи; А.В. Лепихову принадлежат все полученные результаты.

АПРОБАЦИЯ РАБОТЫ

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

- на Четвертом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (1-2 июня 2006 г., Москва);

- на Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования» (18-23 сентября 2006 г., Новороссийск);

- на Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач» (22-27 сентября 2008 г., Новороссийск);

- на Международной научной конференции «Параллельные вычислительные технологии» (29 января - 2 февраля 2007 г., Челябинск).

НАПРАВЛЕНИЯ ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ

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

1. Аналитическое исследование метода частичного зеркалирования: получение аналитических оценок трудоемкости обновления реплик с учетом помех.

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

3. Дальнейшее развитие метода частичного зеркалирования. Предполагается применение данного метода в алгоритме GRACE-соединения и гибридного соединения.

4. Реализация метода частичного зеркалирования и алгоритма балансировки загрузки в параллельной СУБД с открытым исходным кодом.

ЗАКЛЮЧЕНИЕ

В диссертационной работе были рассмотрены вопросы параллельной обработки запросов в многопроцессорных системах с иерархической архитектурой. Была детально исследована проблема балансировки загрузки и связанная с ней проблема размещения данных. Введена модель симметричной многопроцессорной иерархической системы, которая описывает представительный класс реальных систем и является математическим фундаментом для определения стратегии распределения данных в многопроцессорных иерархиях. Для симметричной иерархии предложен алгоритм формирования реплик, базирующийся на логическом разбиении фрагмента отношения на сегменты равной длины. На основе данного алгоритма разработан метод частичного зеркалирования, использующий функцию репликации. Функция репликации отображает уровень иерархии в коэффициент репликации, который определяет размер реплики по отношению к реплици-руемому фрагменту. Доказаны теоремы, позволяющие получить оценки для размеров реплик и трудоемкости их формирования без учета помех. Предложен вариант функции репликации, при котором трудоемкость обновления реплик в многопроцессорной иерархической системе пропорциональна размеру обновляемой части базы данных при условии, что соединительная сеть обладает достаточной пропускной способностью. Описан алгоритм балансировки загрузки, в основе которого лежит метод частичного зеркалиро вания. Предложена стратегия выбора аутсайдера и конкретная формула для вычисления функции балансировки. Построена модель вариантов использования иерархической многопроцессорной системы, описаны основные требования к иерархической СУБД. Приведена общая структура и варианты использования ключевых подсистем. Предложена оригинальная реализация оператора обмена exchange, в основе которой находится механизм пакетирования передаваемых данных и асинхронный режим передачи сообщений. Выполнено проектирование и реализация предложенных методов и алгоритмов в прототипе иерархической СУБД «Омега». Отлаженный код системы составил 10 ООО строк на языке Си. С прототипом иерархической СУБД «Омега» проведены масштабные вычислительные эксперименты на кластере «СКИФ Урал». Результаты проведенных вычислительных экспериментов подтверждают эффективность предложенных методов и алгоритмов.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проект 06-07-89148).

В заключение перечислим основные полученные результаты диссертационной работы, приведем данные о публикациях и апробациях, и рассмотрим направления дальнейших исследований в данной области.

1. Абламейко С.В., Абрамов С.М., Анищенко В.В., Парамонов Н.Н. Принципы построения суперкомпьютеров семейства «СКИФ» и их реализация// Ежеквартальный научный журнал «Информатика». ОИПИ НАН Беларуси, -2004. №1. С. 89-106.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2002. -608 с.

3. Воеводин Вл.В. Решение больших задач в распределенных вычислительных средах. //Автоматика и Телемеханика. -2007, No. 5, С. 32-45.

4. Гарей а-Моли и а Г., Ульман Д., Уидом Д. Системы баз данных.-М.: Издательский дом «Вильяме», 2004. —1088 с.

5. Игнатович Н. Семейство реляционных баз данных IBM DB2 // СУБД. -1997.-№2.-С. 5-17.

6. Кнут Д.Э. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд. -М.: Издательский дом «Вильяме», 2000. -720 с.

7. Кузнецов С.Д. SQL. Язык реляционных баз данных. -М.: Майор, 2001. -192 с.

8. Кузьминский М. Процессоры для высокопроизводительных вычислений // Открытые системы. -2007. -№ 9. -С. 14-19.

9. Лепихов А.В. Модель вариантов использования параллельной системы управления базами данных для грид // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование» —2008. —№ 15 (115). -Вып. 1.-С. 42-53.

10. Лепихов А.В., Соколинский Л.Б., Костенецкий П.С. Технологии параллельных систем баз данных для иерархических многопроцессорных сред // Автоматика и телемеханика. -2007. -No. 5. -С. 112-125.

11. Новиков Б.А., Домбровская Г.Р. Настройка приложений баз данных. -СПб.: БХВ-Петербург, 2006. -240 с.

12. Соколинский Л.Б. Обзор архитектур параллельных систем баз данных // Программирование. -2004. -№ 6. С. 49-63.

13. Четверушкин Б.Н. Высокопроизводительные многопроцессорные вычислительные системы // Вестник российской академии наук. -2002. -Том 72, №9. -С. 786-794.

14. Alexander W., Copeland G. Process and dataflow control in distributed data-intensive systems // Proceedings of the 1988 ACM SIGMOD international conference on Management of data, Chicago, Illinois, United States, 1988 -ACM. -1988.-P. 90-98.

15. Alfawair M., Aldabbas O., Bartels P., Zedan H. Grid Evolution // IEEE International Conference on Computer Engineering & Systems, Cairo, Egypt,27.29 November, 2007, Proceedings. -IEEE Computer Society, 2007 -P.158-163.

16. Baker M., Apon A., Femer C., Brown J. Emerging Grid Standards // Computer. -2005. -Vol. 38, No. 4 -P. 43-50.

17. Bell G., Gray J. What's next in high-performance computing // Communications of. ACM. -2002. -Vol. 45, No. 2 -P. 91-95.

18. Bernstein P., et al. Query processing in a system for distributed databases (SDD-1) // ACM Transactions on Database Systems -1981. -Vol. 6, No. 4. -P. 602-625.

19. Bora! H., Alexander IV., Clay L., Copeland G., Sanforth S., Franklin M., Hart В., Smith M., Valduriez P. Prototyping Bubba: a Highly Parallel Database System // IEEE Trans, on Knowledge and Data Engineering. -1990. -Vol. 2, No. l.-P. 4-24.

20. В oral H. Parallelism in bubba // Proceedings of the first international symposium on Databases in parallel and distributed systems, Austin, Texas, United States, 1988. -IEEE Computer Society Press. -1988. -P. 68-71.

21. Borkar S. Y. et al. Platform 2015: Intel processor and platform evolution for the next decade: tbp.berkeley.edu/~jdonald/researclT/cmp/borkar2015.pdf. -2005.

22. Bouganim L., Florescu D., Valduriez P. Dynamic Load Balancing in Hierarchical Parallel Database Systems // Proceedings of the 22th international Conference on Very Large Data Bases, September 03 06, 1996. -Morgan Kaufmann. -1996. P. 436-447.

23. C.avin R, Hutchby J.A., Zhirnov V., Brewer J.E., BourianojfG. Emerging Research Architectures // Computer. -2008. Vol. 41, No. 5. -P. 33-37.

24. Chamberlin D.D., et al. A History and Evaluation of System R // Communications of the ACM. -1981. -Vol. 24, No. 10. -P. 632-646.

25. Chandy K.M., Misra J. A distributed algorithm for detecting resource deadrlocks in distributed systems // First ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing Ottawa, Canada, August 18-20, 1982, Proceedings.-ACM, 1982. P. 157-164.

26. Chen H., Decker J., Bierbaum N. Future Networking for Scalable I/O // 24th IASTED international Conference on Parallel and Distributed Computing and Networks, Innsbruck, Austria, February 14- 16, 2006, Proceedings -ACTA Press, 2006. P. 128-135.

27. Chen Т., Raghavan R., Dale J.N. Cell Broadband Engine Architecture and its first implementation -A performance View // IBM J. Res. Dev., -Vol. 51, №. 5. -2007.

28. Chi en A., Colder В., Elbert S., Bhatia K. Entropia: architecture and performance of an enterprise desktop grid system // J. Parallel Distrib. Comput. -2003. -Vol. 63, No. 5. -P. 597-610.

29. Chu W. W., Hellerstein J. The Exclusive-Writer Approach to Updating Replicated Files in Distributed processing Systems // IEEE Trans, on Computers -1985. -Vol. 34, No. 6. -P. 489-500.

30. Chu W. W., Merzbacher M., Berkovich L. The design and implementation of CoBase. SIGMOD Record. -1993. -Vol. 22, No. 2. -P. 517-522.

31. Coffman E.G., Denning P.G., Operating Systems Theory. -Prentice Hall, 1973.

32. Copeland G., Alexander W„ Boughter E., Keller T. Data placement in Bubba // Proceedings of the 1988 ACM SIGMOD international Conference on Management of Data, United States, Chicago, Illinois, June 01 -03, 1988. P. 99-108.

33. Conway S., Walsh R. HPC Management Software: Reducing the Complexity of HPC Cluster and Grid Resources. Whitepaper: http://www.findwhitepapers.coni/networking/grid-computing/., 2008.

34. Crawford C.H., Henning P., Kistler M., Wright С. Accelerating computing with the cell broadband engine processor // 5th Conference on Computing Frontiers, Ischia, Italy, May 5-7, 2008, proceedings. -ACM, 2008. P. 3-12.

35. Deshpande A., Ives Z., Raman V. Adaptive query processing. Found. Trends databases.-2007.-Vol. l,No. 1 P. 1-140.

36. DeWitt D.J., et al. The Gamma database machine project // IEEE Transactions on Knowledge and Data Engineering. -1990. -Vol. 2, No. 1. P. 44-62.

37. DeWitt D.J., Gerber R.H. Multiprocessor Hash-Based Join Algorithms // Proceedings of 11th International Conference on Very Large Data Bases, Stockholm, Sweden, August 21-23, 1985. Morgan Kaufmann. -1985. -P. 151-164.

38. DeWitt D.J., Gray J. Parallel Database Systems: The Future of High-Performance Database Systems // Communications of the ACM. -1992. -Vol. 35, No. 6.-P. 85-98.

39. Dwyer P.A., Jelatis G.D., Thuraisingham B.M. Multi-level security in database management systems // Computers and Security. 1987. -Vol. 6, No. 3. -P. 252-260.

40. Ferhatosmanogly F., Hakcm S. Optimal Parallel I/O Using Replication // In Proceedings of the 2002 international Conference on Parallel Processing Workshops, August 18-21, 2002. -IEEE Computer Society. -2002.-P. 506.

41. Ferhatosmanoglu H., Tosun A. Canahuate G., Ramachandrcm, A. Efficient parallel processing of range queries through replicated declustering // Distrib. Parallel Databases-2006. -Vol. 20, No. 2. -P. 117-147.

42. Foster I. Т., Grossman R.L. Blueprint for the future of high-performance networking: Data integration in a bandwidth-rich world // Communications of the ACM. -2003. -Vol. 46, No. 11. -P. 50-57.

43. Foster I.T., Kesselman C\, Nick J., Tuecke S. The Physiology of the Grid: An Open Grid Service Architecture for Distributed Systems Integration. Global Grid Forum: http://www.globus.org/ogsa/., 2002

44. Foster I. What is the Grid? A Three Point Checklist: http://www.gridtoday.com/02/0722/100136.html., 2002.

45. Ganguly S., Hasan IV., Krishnamurthy R. Query optimization for parallel execution // ACM SIGMOD international Conference on Management of Data, San Diego, California, United States, June 02 05, 1992, Proceedings. -ACM, 1992.-P. 9-18.

46. Garcia-Molina H., Lindsay В. Research directions for distributed databases // SIGMOD Record. -1990. -Vol. 19, No. 4 -P. 98-103.

47. Geer D. Grid Computing Using the Sun Grid Engine. Whitepaper: http://whitepapers.silicon.eom/0,39024759,60108958p,00.htm., 2003.

48. Gligor V., Popescu-Zeletin R. Transaction management in distributed heterogeneous database management systems I I Information Systems. -1986. -Vol. 11, No. 4.-P. 287-297.

49. Goimaris A., Paton N. W., Fernandas A., Sakellariou R. Adaptive Query Processing: A Survey. In 19th British National Conference on Databases, Sheffield, UK, 2002. -P. 11-25.

50. Goimaris A., Sakellariou R., Paton N. W., Fernandes A. A. A novel approach to resource scheduling for parallel query processing on computational grids // Distrib. Parallel Databases. -Vol. 19, No. 2-3 -2006. P. 87-106.

51. Graefe G. Encapsulation of Parallelism in the Volcano Query Processing Systems // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. -ACM Press, 1990.-P. 102-111.

52. Graefe G. Query Evaluation Techniques for Large Databases 11 ACM Computing Surveys. -1993. -Vol. 25, No 2. -P. 73-169.

53. Graefe G. Volcano An Extensible and Parallel Query Evaluation System // IEEE Trans. Knowl. Data Eng. -1994. -Vol. 6, No. 1. -P. 120-135.

54. Jennings N.R., Wooldridge M. Agent Technology: Foundations, Applications and Markets. -Springer Verlag, 1998. -325 p.

55. Haliei U., DogacA. Concurrency Control in Distributed Databases Through Time Intervals and Short-Term Locks // IEEE Transactions on Software Engineering. -1989. Vol. 15, No. 8. P. 994-1003.

56. Helal A., Yuan D., El-Rewini H. Dynamic Data Reallocation for Skew Management in Shared-Nothing Parallel Databases // Distrib. Parallel Databases. -1997. -Vol. 5, No. 3. P. 271-288.

57. Hong W., Stonebraker M. Optimization of parallel query execution plans in XPRS // First international Conference on Parallel and Distributed information Systems, Miami, Florida, United States, 1991. -IEEE Computer Society Press, 1991.-P. 218-225.

58. Ни a K. A., Lee С., Hua С. M. Dynamic Load Balancing in Multicomputer Database Systems Using Partition Tuning. IEEE Trans, on Know!, and Data Eng. -1995. -Vol. 7, No. 6. P. 968-983.

59. Hua K.A., Lee C. Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning // Proceedings of the 17th International Conference on Very Large Data Bases, September 03-06, 1991, San Francisco, CA. Morgan Kaufmann, 1991, -P. 525-535.

60. Hua K.A., Lee C. An adaptive data placement scheme for parallel database computer systems // Proceedings of the sixteenth international conference on Very large databases, Brisbane, Australia. -Morgan Kaufmann. -1990.1. P. 493-506.

61. Katayama Y. Trends in Semiconductor Memories. IEEE Micro 17, 6 (Nov. 1997), 10-17.

62. Kim C. Future Memory Technology Trends and Challenges // 7th international Symposium on Quality Electronic Design, March 27 29, 2006, proceedings. -IEEE Computer Society. -P. 513.

63. Kitsuregawa M, Tanaka Н, Moto-Oka Т. Application of Hash to Data Base Machine and Its Architecture // New Generation Comput. -1983. -Vol. 1, No. 1 P. 63-74.

64. Kossmann D. The state of the art in distributed query processing. ACM Comput. Surv. -2000. -Vol. 32, No. 4 -P. 422-469.

65. Kotowski N., Lima A., Pacini E., Valduriez P. Mattoso M. Parallel query processing for OLAP in Grids // Concurrency and Computation: Practice and Experience. -Wiley InterScience. -2008.

66. Koupras E. Grid Computing: Past, Present and Future. IBM Whitepaper: http://www-03.ibm.com/grid/pdf/innovperspective.pdf., june 2006.

67. Livny M., Khoshafian S., В oral H. Multi-disk management algorithms // SIGMETRICS Perform. Eval. Rev. -1987. Vol. 15, No. 1. -P. 69-77.

68. Lo Y., Hua K.A., Young H.C. GeMDA: A Multidimensional Data Partitioning Technique for Multiprocessor Database Systems // Distributed and Parallel Databases. -2001. Vol. 9, No. 3. P. 211-236.

69. Lowenthal D.K., Andrews G.R. An Adaptive Approach to Data Placement. // 10th international Parallel Processing Symposium, April 15- 19, 1996, Proceedings. -IEEE Computer Society, 1996. P. 349-353.

70. Maertens H. A Classification of Skew Effects in Parallel Database Systems // 7th International Euro-Par Conference, August 28-31, 2001, Manchester, UK, Proceedings. Springer. Vol. 2150. -2001. -P.291-300.

71. Mehta M., DeWitt D.J. Data Placement in Shared-Nothing Parallel Database Systems // The VLDB Journal. -January 1997. -Vol. 6, No. 1. -P. 53-72.

72. Meuer H. W. The TOP500 Project: Looking Back Over 15 Years of Super-computing Experience // Informatik Spektrum. -2008. -Vol. 31, No. 3. -P. 203-222.

73. Moore N., C.ontiA, LeeserM, Smith L.AVforce: An Extensible Framework for Reconflgurable Supercomputing // IEEE Computer. -2007. Vol. 40, No. 3. -P.39-49.

74. Parkhurst J., Darringer J., Grundmann B. From single core to multi-core: preparing for a new exponential // IEEE/ACM international Conference on Computer-Aided Design, San Jose, California, November 05 09, 2006. -ACM, 2006. -P. 67-72.

75. Pfister G. Sizing Up Parallel Architectures // Database Programming Design OnLine http://www.dbpd.com., -1998. Vol. 11, No. 5.

76. Rubinovitz H., Thuraisingham B. Security constraint processing in a distributed database environment // 22nd Annual ACM Computer Science Conference on Scaling Up, Phoenix, Arizona, United States, March 08 10, 1994, Proceedings. -ACM, 1994. -P. 356-363.

77. Rahm E. Marek R. Dynamic Multi-Resource Load Balancing in Parallel Database Systems. Proceedings of the 21th international Conference on Very Large Data Bases, San Francisco, September 11-15, 1995. Morgan Kauf-mann.-1995. P. 395^06.

78. Reddy P.K., Bhalla S. Deadlock prevention in a distributed database system // ACM SIGMOD Record. -1993. -Vol. 22, No. 3. -P. 40^6.

79. Reed D. A. Grids, the TeraGrid, and Beyond // Computer. -2003. Vol. 36, No. l.-P. 62-68.

80. RFC4180: Common Format and MIME Type for Comma-Separated Values (CSV) Files: http://tools.ietf.org/html/rfc4180., October 2005.

81. Roberts L. G. Beyond Moore's Law: Internet Growth Trends // Computer -2000. Vol. 33, No. 1-P. 117-119.

82. Roure D., Baker M., Jennings N. R. Shadbolt N. The evolution of the Grid, in: Grid Computing: Making The Global Infrastructure a Reality, Berman F., Hey A. Fox G. -Wiley Publishing Company, 2003, -P. 65-100.

83. Rumbaugh J. Getting Started Using Use Cases to Capture Requirements // Journal of Object Oriented Programming. -1994. -vol. 7, No 5. -P. 8-12.

84. Scheuermann P., Weikum G., Zabback P. Data partitioning and load balancing in parallel disk systems // The VLDB Journal. -1998. -Vol. 7, No. 1.1. P. 48-66.

85. Schoene R., Nagel W.E., Oiger S Analyzing Cache Bandwidth on the Intel 2 Core Architecture // Parallel Computing: Architectures, Algorithms and Applications. -2007. -Vol. 38. -P. 365-372.

86. Selic B. UML 2: a model-driven development tool // IBM Syst. J. -2006. -Vol. 45, No 3.-P. 607-620.

87. Shekhctr S., Ravada S., Kumar V., Chubb D., Turner G. Declustering and Load-Balancing Methods for Parallelizing Geographic Information Systems. IEEE Trans, on Knowl. and Data Eng. -1998. Vol. 10, No. 4. P. 632-655.

88. Son S. H. Replicated data management in distributed database systems // ACM SIGMOD Record. -1988. -Vol. 17, No. 4. -P. 62-69.

89. Stonebraker M. The case for shared nothing // Database Engineering Bulletin. -1986. -Vol. 9, No. 1. -P. 4-9.

90. Stonebraker M., Aoki P., Litwin W„ PfefferA., Sah A., SidellJ., Staelin C., Yu A. Mariposa: a wide-area distributed database system // The VLDB Journal.-1996.-Vol. 5, No. l.-P. 48-63.

91. Stonebreaker M. The design and implementation of distributed INGRES // The INGRES papers: anatomy of a relational database system. Addison

92. Wesley Series In Computer Science. Addison-Wesley Longman Publishing Co., Boston, MA, 187-196.

93. Thomas G., et ah Heterogeneous distributed database systems for production use. ACM Comput. Surv. -1990. -Vol. 22, No. 3. P. 237-266.

94. Thomas R. Majority Consensus Approach to Concurrency Control for Multiple Copy Distributed database Systems // ACM Trans. Database Syst. -1979. -Vol. 4, No. 2. -P. 180-209.

95. Traiger I.L., Gray J.N., Galtieri C.A., Lindsay B.G. Transactions and Consistency in Distributed Database Management Systems // ACM Trans. Database Syst. -1982. -Vol. 7, No. 3. P. 323-342.

96. Vanga! S. An 80-Tile 1.28TFLOPS Network-on-Chip in 65nm CMOS // Solid-State circuits conference, February 11-15,2007. -P. 98-105.

97. Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques / IEEE Computer society. -1998. -P. 203-218.

98. Xu, Y., Kostamaa, P., Zhou, X, and Chen, L. Handling data skew in parallel joins in shared-nothing systems // ACM SIGMOD international Conference on Management of Data Vancouver, Canada, June 09 12, 2008, proceedings. -ACM, -2008. P. 1043-1052.