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

• Автор: Лепихов, Андрей Валерьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Челябинск
• Количество страниц: 102 с. : ил.

ОГЛАВЛЕНИЕ
Введение

Глава 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. Оператор обмена x
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. Спецификация языка .
3.2.2. Спецификация логфайла.
3.3. Реализация СУБД Омега
3.3.1. Реализация оператора обмена x.
3.3.2. Механизм балансировки загрузки.
Глава 4. Вычислительные эксперименты
4.1. Операция соединения методом хеширования в оперативной памяти.
4.2. Параметры вычислительных экспериментов.
4.3. Исследование параметров балансировки загрузки
4.4. Исследование влияния балансировки загрузки на время выполнения запросов
4.5. Исследование масштабируемости алгоритма балансировки загрузки
Заключение
Литература


В рамках этого направления решались задачи оптимизации запросов для параллельной обработки [, ], адаптивной обработки запросов [, ] и управления вычислительными ресурсами [, ]. Результатом данных научных исследований стало появление ряда коммерческих параллельных СУБД с архитектурой без совместного использования ресурсов, среди которых наиболее известными являются Non Stop SQL [], Teradata [] и DB2 Parallel Edition [5]. В работе [] было показано, что перекосы [], возникающие при обработке запросов в параллельных системах баз данных без совместного использования ресурсов, могут приводить к практически полной деградации производительности системы. Поэтому теме балансировки загрузки посвящено значительное количество работ (см. Исследования проблемы балансировки загрузки осуществлялись в рамках следующих двух основных подходов. Первый подход состоит в предупреждении перекосов и предполагает разработку стратегии размещения данных, при которой нагрузка будет равномерно распределяться между процессорными узлами системы [, , ]. Наибольший интерес здесь представляет подход, называемый адаптивным распределением [, ]. В соответствии с этим подходом способ размещения данных может меняться, когда СУБД находит лучшую стратегию размещения данных. Второй подход заключается в динамическом перераспределении данных между вычислительными узлами в процессе обработки запроса [, ]. Однако следует отметить, что в общем виде проблема балансировки загрузки для параллельных систем баз данных без совместного использования ресурсов не решена до сих пор. В середине девяностых годов начались исследования в области иерархических СУБД. В работе [] предложен метод динамической балансировки загрузки при обработке запросов в двухуровневых иерархических многопроцессорных системах. Первый (локальный) уровень представляет собой 8МР-систему, второй (глобальный) - набор БМР-узлов, объединенных коммуникационной сетью. Главной идеей метода является использование межоператорного параллелизма на первом уровне иерархии и фраг-ментного параллелизма на втором уровне. При этом эффективная динамическая балансировка происходит только на первом уровне. Данный метод не может быть расширен для использования в многопроцессорных иерархиях с большим количеством уровней. В работе [] была предложена методика оптимизации операций параллельного ввода/вывода, ключевым элементом которой является использование репликации для уменьшения времени простоя вычислительных узлов. Развитие данной методики в работе [] привело к разработке стратегии распределения данных в параллельных СУБД, использующих репликацию для оптимизации параллельного ввода/вывода. Итогом этих исследований стала работа [], в которой предложено решение проблемі,! Данное решение позволяет уменьшить накладные расходы на передачу данных по сети в процессе балансировки загрузки. Однако метод балансировки загрузки предлагается в весьма узком контексте пространственных баз данных в специфическом сегменте диапазонных запросов. Еще одним актуальным направлением исследований является параллельная обработка запросов в среде грид [, ]. В работе [] выполнен анализ операции соединения методом хеширования и выделены наиболее значимые параметры, влияющие на скорость выполнения оператора соединения. В рамках проекта GParGR. ES [] разработано программное обеспечение промежуточного слоя для параллельной обработки ОЬАР-запросов в грид средах. Проект СРаЮКЕБ реализован на базе СУБД PostgreSQL и предназначен для использования в двухуровневых многопроцессорных иерархиях. Нижний уровень представляет собой вычислительный кластер. Верхний уровень представляет собой грид-систему, являющуюся набором вычислительных кластеров, объединенных некоторой коммуникационной сетью. В целях балансировки загрузки системы при обработке сложных ОЬАР-запросов база данных дублируется на всех сайтах грид-системы. Следует, отметить, что методы параллельной обработки запросов, предложенные в данной работе, не могут использоваться в многопроцессорных иерархиях с большим числом уровней.