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

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

.

В настоящее время все большее распространение получают параллельные системы баз данных, ориентированные на мультипроцессоры с иерархической архитектурой [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, Л. Б. Соколиискии, М.Л. Цымблер- -№ 2 008 614 996 от 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−89 148).

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