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

• Автор: Соколинский, Леонид Борисович
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2003
• Место защиты: Челябинск
• Количество страниц: 247 с. : ил

1.1. Терминология параллельных систем баз данных

1.1.1. Формы параллелизма.

1.1.2. Понятие параллельной системы баз данных

1.2. Требования к параллельной системе баз данных.

1.2.1. Масштабируемость.

1.2.2. Производительность.

1.2.3. Доступность данных.

1.3. Классификация параллельных архитектур

1.3.1. Классификация Флинна.

1.3.2. Структурнофункциональная классификация

1.3.3. Классификация Стоунбрейкера

1.4. Сравнительный анализ архитектур параллельных систем баз данных .
1.5. Архитектура системы Омега
1.5.1. Три уровня абстракции системной архитектуры
1.5.2. Аппаратная архитектура системы Омега.
1.6. Заключительные замечания к главе 1.
Глава 2. Методы построения операционного ядра системы Омега.
2.1. Общесистемное программное обеспечение МВС0.
2.2. Структура операционного ядра системы Омега.
2.3. Организация управления легковесными процессами.
2.3.1. Особенности распараллеливания работ на МВС0.
2.3.2. Потоковая модель для управления легковесными процессами
2.3.3. Диспетчеризация нитей
2.3.4. Реализация менеджера нитей.
2.4. Система хранения данных
2.4.1. Архитектура системы хранения СУБД Омега
2.4.2. Электронная дисковая подсистема
2.4.3. Система управления файлами.
2.4.4. Менеджер наборов.
2.4.5. Менеджер файлов
2.5. Организация межпроцессорных коммуникаций.
2.5.1. Система передачи сообщений.
2.5.2. Маршрутизатор
2.5.3. Кондуктор
2.6. Заключительные замечания к главе 2.
Глава 3. Методы управления буферным пулом.
3.1. Введение в проблематику буферизации данных .
3.2. Требования к подсистеме управления буферным пулом СУБД
3.2.1. Поиск страницы в буферном пуле.
3.2.2. Замещение страниц в буферном пуле
3.2.3. Избирательное вытеснение страниц.
3.2.4. Распределение слотов буферного пула между параллельными транзакциями
3.3. Методы проектирования подсистемы управления буферным пулом параллельной СУБД Омега
3.3.1. Архитектура менеджера буферного пула
3.3.2. Метод статических и динамических рейтингов
3.4. Заключительные замечания к главе
Глава 4. Стратегия замещения страниц.
4.1. Проблема выбора стратегии замещения страниц.
4.2. Требования к стратегии замещения.
4.3. Обзор известных стратегий замещения.
4.3.1. Стратегия .
4.3.2. Специальные стратегии замещения.
4.3.3. Общие стратегии замещения.
4.4. Концепция алгоритма .
4.5. Аналитическая оценка параметра ш алгоритма
4.5.1. Вероятностная модель
4.5.2. Мера для определения параметра т
4.5.3. Разложение нормальной функции в ряд Тейлора.
4.5.4. Приближенная мера для параметра т.
4.6. Реализация алгоритма
4.7. Результаты экспериментов по сравнительной оценке эффективности алг оритма
4.7.1. Стационарное распределение вероятностей обращений
4.7.2. Периодическое распределение вероятностей обращений.
4.7.3. Доступ в режиме с использованием индексного файла
4.7.4. Эксперименты на реальной трассе.
4.8. Выбор значений параметров алгоритма
4.9. Заключительные замечания к главе
Глава 5. Организация параллельного выполнения запросов в системе с 2 архитектурой.
5.1. Стратегия размещения данных в системе Омега.
5.2. Алгоритм балансировки загрузки внутри Омегакластера
5.3. Организация параллельного выполнения запросов.
5.3.1. Модели параллелизации запросов
5.3.2. Операторный фрейм.
5.3.3. Оператор обмена x
5.4. Исполнитель запросов системы Омега
5.4.1. Обработка запросов в системе Омега
5.4.2. Физическая алгебра
5.4.3. Интерфейс исполнителя физических запросов.
5.4.4. Реализация исполнителя физических запросов
5.5. Результаты экспериментов.
5.6. Заключительные замечания к главе
Глава 6. Технологические аспекты разработки системы Омега
6.1. Технология коллективной разработки СУБД Омега.
6.2. Организация коллективной разработки.
6.3. Программная поддержка технологии коллективной разработки
6.3.1. Средства поддержки коллективной разработки
6.3.2. Интегрированная среда разработчика
6.3.3. Расширение среды программирования МВС0.
6.4. Заключительные замечания к главе
Заключение
Литература


Различные механизмы реализации синхронных и асинхронных конвейеров в контексте распределенных баз данных были исследованы в работе 8. Следует отмстить, что степень конвейерного параллелизма в любом случае ограничена количеством операций, вовлекаемых в конвейер. При этом для реляционных систем баз данных длина конвейера редко превышает операций 0. Поэтому для достижения более высокой степени распараллеливания наряду к конвейерным параллелизмом необходимо использовать внутриоперационныи параллелизм. Внутрчоперацчонный параллелизм реализуется в основном в форме фрагментного параллелизма 0. Некоторые авторы см. Однако данные формы параллелизма концептуально ничем не отличаются от рассмотренных выше и на практике большого значения не имеют. Фрагмептпый параллелизм предполагает фрагментацию разбиение на непересекающиеся части отношения, являющегося аргументом реляционной операции 5. Одиночная реляционная операция выполняется в виде нескольких параллельных процессов агентов, каждый из которых обрабатывает отдельный фрагмент отношения. Получаемые результирующие фрагменты сливаются в общее результирующее отношение 0. В реляционных системах баз данных фрагментация подразделяется на вертикальную и горизонтальную 0. Вертикальная фрагментация подразумевает разбиение отношения на фрагменты по столбцам атрибутам. Практически все параллельные СУБД, поддерживающие фрагментный параллелизм, используют только горизонтальную фрагментацию. Поэтому везде ниже мы будем рассматривать только горизонтальную фрагментацию. Теоретически фрагментный параллелизм способен обеспечить сколь угодно высокую степень распараллеливания реляционных операций. Однако на практике степень фрагментного параллелизма может быть существенно ограничена следующими двумя факторами. Вопервых, фрагментация отношения может зависеть от семантики операции. Например, операция соединения одних и тех же отношений по разным атрибутам требует различной фрагментации. Однако повторное разбиение фрагментированного отношения на новые фрагменты и распределение полученных фрагментов по процессорным узлам может быть связано с очень большими накладными расходами. Вовторых, перекосы в распределении значений атрибутов фрагментации могут привести к значительным перекосам в размерах фрагментов и, как следствие, к существенному дисбалансу в загрузке процессоров. Основываясь на приведенной выше классификации форм параллельной обработки транзакций, мы можем дать следующее неформальное определение параллельной системы баз данных 5. Параллельная система баз данных это СУБД, реализованная на многопроцессорной системе с высокой степенью связности. Под многопроцессорной системой с высокой степенью связности мы понимаем систе. Приведенное определение исключает из рассмотрения распределенные СУБД, реализуемые на нескольких независимых компьютерах, объединенных локальной и или глобальной сетями, для которых характерны свои специфические проблемы, такие как географическая удаленность, локальная автономность, программная и аппаратная гетерогенность 2, и применительно к которым не рассматривается комплекс важных проблем, связанных с большим количеством процессорных узлов. Однако данное определения включает в себя широкий спектр систем, начиная с традиционных однопроцессорных СУБД, портированных на симметричные мультипроцессорные системы и использующих только межтранзакционный параллелизм, и кончая сложными параллельными системами, реализованными на кластерах или мультипроцессорах с массовым параллелизмом, использующими фрагментный параллелизм. Как будет показано в разделе 1. В соответствие с этим существующие классификации архитектур многопроцессорных систем оказываются с точки зрения СУБД либо слишком общими эго относится прежде всего к классификации Флинна, рассмотренной в разделе 1. Флинна, так и к структурнофункциональной классификации, рассмотренной в разделе 1. Классификация Стоунбрейкера см. Это обусловлено тем, что существующие классификационные подходы основаны на отображении архитектуры параллельной системы баз данных непосредственно на аппаратную архитектуру многопроцессорной системы, как это оказано на Рис.