Содержание к диссертации
Введение
Глава 1. Архитектура параллельных систем баз данных 16
1.1. Терминология параллельных систем баз данных 16
1.1.1. Формы параллелизма 16
1.1.2. Понятие параллельной системы баз данных 21
1.2. Требования к параллельной системе баз данных 27
1.2.1. Масштабируемость 28
1.2.2. Производительность 30
1.2.3. Доступность данных 35
1.3. Классификация параллельных архитектур 36
1.3.1. Классификация Флинна 37
1.3.2. Структурно-функциональная классификация 40
1.3.3. Классификация Стоунбрейкера 43
1.4. Сравнительный анализ архитектур параллельных систем баз данных .48
1.5. Архитектура системы Омега 51
1.5.1. Три уровня абстракции системной архитектуры.. 52
1.5.2. Аппаратная архитектура системы Омега 54
1.6. Заключительные замечания к главе 1 57
Глава 2. Методы построения операционного ядра системы Омега 59
2.1. Общесистемное программное обеспечение МВС-100/1000 59
2.2. Структура операционного ядра системы Омега 62
2.3. Организация управления легковесными процессами 64
2.3.1. Особенности распараллеливания работ на МВС-100 64
2.3.2. Потоковая модель для управления легковесными процессами 66
2.3.3. Диспетчеризация нитей 69
2.3.4. Реализация менеджера нитей 70
2.4. Система хранения данных 71
2.4.1. Архитектура системы хранения СУБД Омега 71
2.4.2. Электронная дисковая подсистема 75
2.4.3. Система управления файлами 80
2.4.4. Менеджер наборов 81
2.4.5. Менеджер файлов 85
2.5. Организация межпроцессорных коммуникаций 87
2.5.1. Система передачи сообщений 87
2.5.2. Маршрутизатор 90
2.5.3. Кондуктор 91
2.6. Заключительные замечания к главе 2 92
Глава 3. Методы управления буферным пулом 94
3.1. Введение в проблематику буферизации данных 94
3.2. Требования к подсистеме управления буферным пулом СУБД 96
3.2.1. Поиск страницы в буферном пуле 97
3.2.2. Замещение страниц в буферном пуле 97
3.2.3. Избирательное вытеснение страниц 99
3.2.4. Распределение слотов буферного пула между параллельными транзакциями 101
3.3. Методы проектирования подсистемы управления буферным пулом параллельной СУБД Омега 103
3.3.1. Архитектура менеджера буферного пула 104
3.3.2. Метод статических и динамических рейтингов 108
3.4. Заключительные замечания к главе 3 112
Глава 4. Стратегия замещения страниц 114
4.1. Проблема выбора стратегии замещения страниц 114
4.2. Требования к стратегии замещения 116
4.3. Обзор известных стратегий замещения 121
4.3.1. Стратегия LRU 121
4.3.2. Специальные стратегии замещения 122
4.3.3. Общие стратегии замещения 126
4.4. Концепция алгоритма LFU-K 133
4.5. Аналитическая оценка параметра m алгоритма LFU-K 136
4.5.1. Вероятностная модель 136
4.5.2. Мера для определения параметра т 138
4.5.3. Разложение нормальной функции в ряд Тейлора 141
4.5.4. Приближенная мера для параметра т 143
4.6. Реализация алгоритма LFU-K 145
4.7. Результаты экспериментов по сравнительной оценке эффективности алгоритма LFU-2m 149
4.7.1. Стационарное распределение вероятностей обращений 149
4.7.2. Периодическое распределение вероятностей обращений 151
4.7.3. Доступ в режиме OLTP с использованием индексного файла 153
4.7.4. Эксперименты на реальной трассе 154
4.8. Выбор значений параметров алгоритма LFU-2m 154
4.9. Заключительные замечания к главе 4 157
Глава 5. Организация параллельного выполнения запросов в системе с CD2 архитектурой 160
5.1. Стратегия размещения данных в системе Омега 160
5.2. Алгоритм балансировки загрузки внутри Омега-кластера 162
5.3. Организация параллельного выполнения запросов 163
5.3.1. Модели параллелизации запросов 163
5.3.2. Операторный фрейм 166
5.3.3. Оператор обмена exchange 170
5.4. Исполнитель запросов системы Омега 173
5.4.1. Обработка запросов в системе Омега 173
5.4.2. Физическая алгебра 182
5.4.3. Интерфейс исполнителя физических запросов 183
5.4.4. Реализация исполнителя физических запросов 186
5.5. Результаты экспериментов 190
5.6. Заключительные замечания к главе 5 195
Глава 6. Технологические аспекты разработки системы Омега 197
6.1. Технология коллективной разработки СУБД Омега 197
6.2. Организация коллективной разработки 199
6.3. Программная поддержка технологии коллективной разработки 201
6.3.1. Средства поддержки коллективной разработки 201
6.3.2. Интегрированная среда разработчика 204
6.3.3. Расширение среды программирования МВС-100 209
6.4. Заключительные замечания к главе 6 211
Заключение 213
Литература 219
- Понятие параллельной системы баз данных
- Потоковая модель для управления легковесными процессами
- Распределение слотов буферного пула между параллельными транзакциями
- Периодическое распределение вероятностей обращений
Введение к работе
АКТУАЛЬНОСТЬ ТЕМЫ
Комплекс сложных научно-технических проблем, связанных с созданием высокопроизводительных и надежных систем баз данных, в условиях перехода общества от индустриальной эры к информационной не только сохраняет, но и усиливает свою актуальность. Об этом свидетельствуют интенсивные научные исследования в области баз данных, проводимые в России и за рубежом [20, 97, 152].
В настоящее время системы управления базами данных (СУБД) используются практически во всех сферах человеческой деятельности, связанных с хранением и переработкой информации. Прогресс, достигнутый в области технологий баз данных, в значительной мере базируется на реляционной модели, предложенной Э. Коддом [108] на рубеже 60-х - 70-х годов XX века. За свою тридцатилетнюю историю реляционные СУБД прошли путь от научно-исследовательских прототипов, наиболее значительными из которых являются System R [26, 74, 98] и Ingres [219, 220], до коммерческих продуктов, способных хранить и обрабатывать терабайты информации. Однако научная и практическая деятельность человека выдвигает все новые масштабные задачи, требующие обработки сверхбольших баз данных.
Возникновение сверхбольших баз данных связано с расширением видов и сфер применения СУБД. Примерами новых приложений баз данных являются электронная коммерция [151], электронные библиотеки [19, 129, 203], геоинформационные системы [62], мультимедийные архивы [164], научные базы данных [92, 226] и др.
Одной из самых больших научных баз данных является база данных проекта BABAR [131]. Целью эксперимента BABAR является изучение поведения В-мезонов, получаемых на коллайдере РЕР-И в Стэндфордском центре линейного ускорителя (Stanford Linear Accelerator Center). Детектор BABAR поставляет около 500 Гбайт информации ежедневно. Данная информация сохраняется в базе данных BABAR, объем которой сегодня составляет более 500 Тбайт. Система включает в себя 2000 процессоров и 100 серверов.
Другим примером сверхбольшой базы данных является база данных проекта EOS/DIS (Earth Observation System/Data Information System) [92, 122, 130], разрабатываемого агентством NASA в США. Система наблюдения земли EOS включает в себя множество спутников, которые собирают информацию, необходимую для изучения долгосрочных тенденций состояния атмосферы, океанов, земной поверхности. Начиная с 1998 года спутники поставляют информацию в объеме 1/3 петабайт (Petabyte - 1015 байт) в год. Предполагается, что к 2010 году общий объем поддерживаемых в системе данных превысит 20 петабайт.
Еще одним примером системы, требующей обработки сверхбольших объемов данных, является система SkyServer проекта SDSS (Sloan Digital Sky Survey) [229]. Данный проект предполагает создание виртуальной обсерватории, доступной через Интернет. База данных проекта должна объединить в себе полную информацию о наблюдениях всех участков звездного неба различными обсерваториями мира. Начальный объем базы данных проекта оценивается в 40 терабайт. Работы по созданию виртуальной обсерватории ведутся также и в России [10].
Фактически единственным эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных [120], обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах. Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских прототипов к полнофункциональным коммерческим продуктам, поставляемым на рынок высо копроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести DB2 Parallel Edition [15], NonStop SQL [61, 99] и NCR Teradata [32]. Подобные системы объединяют до тысячи процессоров и магнитных дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [234]. Одно из них - дальнейшее развитие аппаратной архитектуры параллельных систем баз данных. Как указывается в Асиломарском отчете о направлениях исследований в области баз данных [86], в ближайшем будущем крупные организации будут располагать базами данных объемом в несколько петабайт. Для обработки подобных объемов информации потребуются параллельные машины с десятками тысяч процессоров, что в сотни раз превышает их число в современных системах. Однако современные архитектуры и технологии параллельных систем баз данных вряд ли допускают масштабирование на два порядка. Для параллельных систем баз данных с тысячами процессорных узлов особое значение приобретает проблема обеспечения отказоустойчивости и высокой доступности данных, так как вероятность отказа некоторой аппаратной компоненты в таких системах возрастает в тысячи раз. Поэтому параллельные системы баз данных должны быть системами высокой готовности.
В соответствие с вышесказанным является актуальной задача разра щ ботки новых архитектур параллельных систем баз данных, способных обеспечить масштабирование системы до нескольких тысяч процессорных узлов, при обеспечении высокой доступности данных и устойчивости к отка » зам различных аппаратных компонент.
ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ
Цель данной работы состояла в разработке и исследовании новой гибридной архитектуры параллельных систем баз данных, которая в большей мере отвечала бы требованиям производительности, масштабируемости и доступности данных по сравнению с существующими архитектурами. Практическая цель работы состояла в разработке и исследовании новых методов передачи сообщений, управления внешней памятью, буферизации и организации параллельного выполнения запросов применительно к новой гибридной архитектуре.
Для достижения этих целей необходимо было решить следующие основные задачи.
1) Провести сравнительный анализ различных подходов к классификации архитектур многопроцессорных систем в контексте параллельных СУБД и выработать адекватные методы классификации современных архитектур параллельных систем баз данных.
2) Выработать систему требований и провести качественный сравнительный анализ возможных классов архитектур параллельных систем баз данных, на основе которого предложить новую гибридную архитектуру, в большей мере отвечающую предъявляемым требованиям.
3) Разработать методы реализации эффективного операционного ядра параллельной СУБД, отвечающего требованиям новой гибридной архитектуры.
4) Выработать систему требований и провести сравнительный анализ известных алгоритмов замещения страниц в буферном пуле в контексте новой гибридной архитектуры параллельных систем баз данных, на основе чего разработать новый алгоритм замещения, в большей мере отвечающий предъявляемым требованиям. Построить математическую модель этого алгоритма, выполнить оценку его параметров и провести вычислительные эксперименты на искусственных и реальных трассах обращений к страницам диска для подтверждения эффективности предлагаемого подхода.
5) Разработать методы организации параллельного выполнения запросов и балансировки загрузки применительно к новой гибридной архитектуре.
6) Реализовать предложенные методы и алгоритмы в виде прототипа параллельной СУБД Омега на базе отечественного многопроцессорного вычислительного комплекса МВС-100/1000 [13, 22]. Используя данный прототип, провести вычислительные эксперименты на тестовых базах данных, подтверждающие эффективность выработанных подходов.
7) Для успешного решения предыдущей задачи выработать технологию коллективной разработки больших программных систем для МВС-100.
МЕТОДЫ ИССЛЕДОВАНИЯ
Проведенные в работе исследования базируются на объектно-реляционной модели данных и используют методы математического моделирования. Для решения поставленных задач применялись аппарат теории вероятностей и математического анализа, методы системного, модульного и объектно-ориентированного программирования, а также технология параллельных систем баз данных.
НАУЧНАЯ НОВИЗНА
Научная новизна работы заключается в следующем:
1) предложена новая гибридная иерархическая архитектура (CZ 2 архитектура) для построения высокоэффективных, масштабируемых, отказоустойчивых параллельных систем баз данных;
2) описана оригинальная аппаратная реализация CD2 архитектуры, базирующаяся на введении специального вида кластеров {Омега-кластеров) с разделяемыми дисками и двухпроцессорными несимметричными модулями с приватной памятью;
3) разработана новая модель организации легковесных процессов, базирующаяся на парадигме "производитель-потребитель" и использующая механизм "управление посредством потоков данных";
4) предложена оригинальная архитектура менеджера буферного пула, основанная на использовании избыточного индекса буферного пула и комбинированном методе вычисления рейтингов страниц;
5) разработан новый эффективный алгоритм замещения страниц в буферном пуле (алгоритм LFU-JT), ориентированный на использование в параллельных системах баз данных без совместного использования ресурсов;
6) предложена новая модель параллелизации запросов (потоковая модель), позволяющая достичь в контексте Омега-кластера хорошего баланса загрузки при относительно низких накладных расходах на межпроцессорные коммуникации и обеспечивающая автоматическую диспетчеризацию и синхронизацию процессов выполнения операций в дереве плана запроса на базе использования специальных промежуточных буферов (складов) для передачи порций данных от операции-производителя к операции-потребителю;
7) разработан оригинальный алгоритм балансировки загрузки на уровне Омега-кластера, в основе которого лежит механизм репликации данных, названный внутрикластерным дублированием ,
8) на основе CD2 архитектуры впервые создан прототип параллельной СУБД Омега для отечественных многопроцессорных вычислительных комплексов серии МВС;
9) предложена технология коллективной разработки больших программных систем для многопроцессорного вычислительного комплекса МВС, включающая в себя комплекс концептуальных, организационных и программных средств.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ
Практическая ценность результатов, полученных в данной работе состоит в следующем:
1) предложенные подходы, методы и алгоритмы могут быть использованы для проектирования и разработки параллельных систем баз данных на базе широкого спектра многопроцессорных систем, начиная от мультипроцессоров с массовым параллелизмом типа МВС-1000 и кончая кластерами типа Beowulf;
2) алгоритм замещения страниц LFU-/T может быть использован для организации эффективной буферизации в различных параллельных системах баз данных без совместного использования ресурсов, а также для кэширования Web-страниц на proxy-серверах, обслуживающих большое число пользователей WWW;
3) предложенная технология коллективной разработки больших программных систем для многопроцессорного вычислительного комплекса МВС-100 может быть перенесена в среду МВС-1000 и использована для создания сложных программных систем различного назначения.
СТРУКТУРА И ОБЪЕМ РАБОТЫ
Диссертация состоит из введения, шести глав, заключения и библиографии. Объем диссертации составляет 247 страниц, объем библиографии - 246 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Первая глава, "Архитектура параллельных систем баз данных", посвящена общим вопросам проектирования архитектуры параллельных систем баз данных. В начале главы дается обзор и классификация различных форм параллельной обработки транзакций, формулируется определение па раллельной системы баз данных и вводится формализованное понятие вирту альной параллельной машины баз данных. Затем анализируются требования к параллельной системе баз данных. Далее делается обзор и анализ различных подходов к классификации архитектур многопроцессорных систем, на основе которого делается выбор в пользу расширенной классификации Сто-унбрейкера. На основе этой классификации дается сравнительный анализ различных архитектур параллельных систем баз данных. Данный анализ показывает, что наиболее предпочтительной является гибридная иерархическая архитектура CDi, которая строится как объединение кластеров с физическим \ разделением дисков, представляющих собой на виртуальном уровне системы
без совместного использования ресурсов. Рассматривается архитектура параллельной системы баз данных Омега, воплощающая в себе подобный под ц ход. Описывается аппаратная реализация системы Омега на базе отечествен ного многопроцессорного вычислительного комплекса МВС.
Во второй главе, "Методы построения операционного ядра системы Омега", рассматриваются методы создания операционного ядра системы Омега, которое учитывало бы в полной мере специфику архитектуры CD2 и предоставляло бы необходимые СУБД системные сервисы с эффективной реализацией. В начале главы дается обзор общесистемного программного обеспечения, поставляемого с МВС. Затем описывается общая структура операционного ядра системы Омега. Далее рассматриваются методы управления легковесными процессами и предлагается новая модель организации легковесных процессов, базирующаяся на парадигме "производитель-потребитель" и использующая механизм "управление посредством потоков • данных". Данная модель обеспечивает автоматическую диспетчеризацию и синхронизацию легковесных процессов и позволяет использовать их в качестве базового средства структуризации программы. Описываются структура и методы реализации системы хранения персистентных данных. Рассматри ваются методы организации межпроцессорных коммуникаций. Предлагается двухуровневая архитектура системы передачи сообщений, позволяющая существенно сократить накладные расходы на межпроцессорные коммуникации в CD2 системах.
Третья глава, "Методы управления буферным пулом", посвящена вопросам эффективной организации менеджера буферного пула применительно к параллельной системе баз данных без совместного использования ресурсов. Формулируются требования к подсистеме управления буферным пулом в контексте СУБД. Описывается общая архитектура подсистемы управления буферным пулом СУБД Омега. Вводится избыточный индекс буферного пула DIR, используемый для доступа к буферизованным страницам и хранящий статистическую информацию о страницах диска. Рассматривается механизм рейтингов, используемый для организации замещения страниц в буферном пуле. Вводится метод статических и динамических рейтингов. Описывается алгоритм вычисления динамического рейтинга. Предложенный подход позволяет использовать комбинированные стратегии замещения, обеспечивая, в то же время, быстрый поиск страниц в буферном пуле и поддержку избирательного вытеснения страниц.
В четвертой главе, "Стратегия замещения страниц", предлагается новый алгоритм замещения LFU-JT, ориентированный, прежде всего, на использование в параллельных системах баз данных без совместного использования ресурсов. В начале главы обсуждаются требования, которым должна удовлетворять общая стратегия замещения страниц с точки зрения параллельной системы баз данных без совместного использования ресурсов. Затем дается обзор известных стратегий замещения и делается вывод о том, что ни одна из этих стратегий в полной мере не удовлетворяет предъявляемым требованиям. Далее на базе производящих функций строится формальная модель для описания предлагаемой нами новой стратегии замещения LFU-/ST. На основе данной модели, путем использования теоретико-вероятностных методов, строится аналитическая оценка для базового параметра алгоритма в зависимости от характера распределения вероятностей обращений к страницам диска. Остальные параметры алгоритма исследуются в вычислительных экспериментах, на основе которых даются конкретные рекомендации для оптимального выбора этих параметров. Рассматриваются практические аспекты реализации стратегии LFU-JT и предлагается конкретная реализация модернизированной версии алгоритма LFU-2/w на псевдокоде. В заключение приводятся результаты экспериментов по сравнительной оценке эффективности алгоритма LFU-2w для различных искусственных и реальных трасс, подтверждающие его высокую эффективность.
Пятая глава, "Организация параллельного выполнения запросов в системе с CD2 архитектурой", посвящена проблемам эффективной организации параллельного выполнения запросов в системе Омега при наличии перекосов данных и выполнения. Предлагается оригинальная стратегия размещения данных в системе Омега, базирующаяся на методе внутрикластерного дублирования. Описывается эффективный алгоритм балансировки загрузки внутри Омега-кластера в условиях перекоса данных. Рассматривается оригинальная потоковая модель параллелизации запросов, объединяющая в себе преимущества ранее известных скобочной и операторной моделей. Потоковая модель является устойчивой к перекосам выполнения и позволяет достичь на Омега-кластерах производительности, сравнимой с производительностью кластеров с разделяемой памятью. Рассматриваются вопросы организации исполнителя запросов системы Омега. Приводятся результаты экспериментов, подтверждающие высокую эффективность предложенных подходов.
В шестой главе, "Технологические аспекты разработки системы Омега", рассматриваются вопросы организации коллективной разработки системы Омега. Описывается технология коллективной разработки больших программных систем для многопроцессорной вычислительной системы МВС, включающая в себя комплекс концептуальных, организационных и г программных средств. В рамках данной технологии предлагается распреде ление функций между различными членами бригады программистов и описываются основные этапы технологического цикла разработки программ. Дается обзор программных средств, использованных в технологии коллективной разработки больших программ для МВС. Описываются методы использования программных пакетов CVS и DOC++. Рассматриваются вопросы построения интегрированной среды разработчика программ для МВС. Рассматривается расширение среды программирования МВС в виде разработанных отладчика и профилировщика. В заключении суммируются основные результаты диссертационной работы, выносимые на защиту, приводятся данные о публикациях и апробациях, и рассматриваются направления дальнейших исследований в данной области.
БЛАГОДАРНОСТИ
Автор выражает глубокую благодарность Российскому фонду фундаментальных исследований, осуществлявшему финансовую поддержку проек- щ та Омега на протяжении всего периода его осуществления.
Автор также благодарит С.Д. Кузнецова, сделавшего целый ряд ценных замечаний по содержанию рукописи, способствовавших формированию финальной редакции текста диссертационной работы.
Понятие параллельной системы баз данных
Основываясь на приведенной выше классификации форм параллельной обработки транзакций, мы можем дать следующее неформальное определение параллельной системы баз данных [235].
Параллельная система баз данных - это СУБД, реализованная на многопроцессорной системе с высокой степенью связности. Под многопроцессорной системой с высокой степенью связности мы понимаем систему, включающую в себя много процессоров и много дисков, в которой процессоры объединены между собой с помощью некоторой соединительной сети, причем время обмена данными по сети сравнимо со временем обмена данными с диском. Приведенное определение исключает из рассмотрения распределенные СУБД, реализуемые на нескольких независимых компьютерах, объединенных локальной и (или) глобальной сетями, для которых характерны свои специфические проблемы, такие как географическая удаленность, локальная автономность, программная и аппаратная гетерогенность [182], и применительно к которым не рассматривается комплекс важных проблем, связанных с большим количеством процессорных узлов. Однако данное определения включает в себя широкий спектр систем, начиная с традиционных однопроцессорных СУБД, портированных на симметричные мультипроцессорные системы и использующих только межтранзакционный параллелизм, и кончая сложными параллельными системами, реализованными на кластерах или мультипроцессорах с массовым параллелизмом, использующими фраг-ментный параллелизм.
Как будет показано в разделе 1.3, существует большое многообразие архитектур многопроцессорных систем. В соответствие с этим существующие классификации архитектур многопроцессорных систем оказываются с точки зрения СУБД либо слишком общими (это относится прежде всего к классификации Флинна, рассмотренной в разделе 1.3.1), либо слишком сложными (см., например, таксономическую систему, приведенную в работе [115]), либо не вполне адекватными (это относится как к классификации Флинна, так и к структурно-функциональной классификации, рассмотренной в разделе 1.3.2). Классификация Стоунбрейкера (см. раздел 1.3.3), разработанная специально для параллельных систем баз данных, к настоящему моменту также перестала быть адекватной [177]. Это обусловлено тем, что существующие классификационные подходы основаны на отображении архитектуры параллельной системы баз данных непосредственно на аппаратную архитектуру многопроцессорной системы, как это оказано на Рис. 2.
Решить указанную проблему можно путем введения некоторого дополнительного уровня абстракции, базирующегося на понятии виртуальной параллельной машины баз данных [213]. Архитектура параллельной системы баз данных отображается на архитектуру виртуальной параллельной машины баз данных, которая в свою очередь отображается на ту или иную аппаратную архитектуру многопроцессорной системы, как это показано на Рис. 3. Более детально вопросы классификации архитектур параллельных систем баз дан ных будут рассмотрены в разделе 1.3.3. Виртуальная параллельная машина баз данных строится из следующих виртуальных устройств: виртуальные процессоры, виртуальные модули памяти, виртуальные диски, виртуальная соединительная сеть. Виртуальный процессор - это виртуальное устройство, используемое для выполнения отдельной задачи, определяемой как процесс базы данных.
Типичным примером процесса базы данных является запрос или агент запроса (при использовании фрагментного параллелизма). В реальной системе виртуальный процессор может быть представлен микропроцессором или процессорным модулем. Если при этом на одном физическом процессоре выполняется несколько процессов базы данных в режиме разделения времени, то мы вправе говорить, что данный физический процессор реализует несколько виртуальных процессоров.
Виртуальный модуль памяти - это виртуальное устройство, используемое для буферизации объектов базы данных. Типичным примером объекта реляционной базы данных является отношение или его фрагмент (при использовании фрагментного параллелизма). Виртуальный процессор не может получить доступ к объекту базы данных иначе, чем через его образ, загруженный в некоторый доступный ему виртуальный модуль памяти. В соответствие с этим количество виртуальных модулей памяти в виртуальной параллельной машине баз данных не может превосходить количество виртуальных процессоров. В реальной системе виртуальный модуль памяти обычно реализуется в виде физических модулей оперативной памяти. При этом один физический модуль памяти может реализовывать несколько виртуальных модулей памяти (см., например, [96]), и несколько физических модулей памяти могут реализовывать один виртуальный модуль памяти (см., например, [73]).
Виртуальный диск - это виртуальное устройство, используемое для хранения объектов базы данных. В реальной системе виртуальный диск обычно реализуется в виде физического дискового устройства или дискового массива [2, 186].
Потоковая модель для управления легковесными процессами
Масштабируемость SN архитектуры характеризуется в Табл. 2 как средняя. Это связано с тем, что при большом количестве процессорных узлов межпроцессорная соединительная сеть становится узким местом [177, 194]. CD, СЕ и CDN архитектуры демонстрируют лучшую масштабируемость за счет того, что наиболее интенсивные коммуникации сосредотачиваются внутри кластеров, разгружая тем самым межкластерную соединительную сеть.
Доступность данных для SN архитектуры мы также классифицировали как среднюю. Это связано с тем, что страховочные копии в SN системе должны фрагментироваться по многим узлам [146] для того, чтобы в случае отказа одного из дисков его страховочная копия была доступна в параллельном режиме (в противном случае может возникнуть серьезный дисбаланс загрузки). Поддержание когерентности фрагментированных страховочных копий потребует определенных накладных расходов, связанных прежде всего с пересылкой большого количества данных по соединительной сети. СЕ архитектура характеризуется "плохой" доступностью данных из-за низкой аппаратной отказоустойчивости SE кластера [187]. CD и CDN архитектуры демонстрируют наилучшую доступность данных, так как все проблемы, связанные с обеспечением высокой доступности (см. раздел 1.2.3), могут быть эффективно решены на уровне отдельных SD кластеров.
Баланс загрузки для SN архитектуры является серьезной проблемой, так как SN системы весьма чувствительны к перекосу данных [157]. Иерархические архитектуры типа СЕ, CD и CDN позволяют достичь лучшей сбалансированности загрузки, так как баланс загрузки может здесь выполняться на двух уровнях - межкластерном и внутрикластерном. SD кластеры позволяют достичь удовлетворительной балансировки загрузки, поскольку каждому процессору доступны все диски. Наилучший баланс загрузки обеспечивают SE кластеры, так как помимо дисков процессорам доступна вся оперативная память [235].
Высокая стоимость межпроцессорных коммуникаций является одной из слабых сторон SN архитектуры [124, 222]. Использование СЕ архитектуры позволяет значительно сократить накладные расходы, связанные с межпроцессорными коммуникациями [147]. Межпроцессорные коммуникации на уровне SE кластера могут быть реализованы очень эффективно через разделяемую память. CD и CDN архитектуры уступают по этому показателю СЕ архитектуре, однако могут превзойти SN архитектуру, так как потенциально внутрикластерные коммуникации могут быть реализованы более эффективно, чем межкластерные [215, 216].
Когерентность кэшей является серьезной проблемой для CD архитектуры, так как в SD кластере одни и те же страницы разделяемых дисков буферизуются в индивидуальных модулях памяти. Копии страниц остаются в буферных пулах некоторое время после завершения обратившейся к ним транзакции, поэтому изменения, сделанные одним узлом SD кластера, могут быть аннулированы изменениями, сделанными другим узлом SD кластера [194]. СЕ архитектура имеет лучшие показатели по данному параметру по сравнению с CD архитектурой, так как SE кластеры используют общий буферный пул в разделяемой памяти. Однако СЕ архитектура уступает по этому параметру SN архитектуре, так как в SE кластере необходимо поддерживать когерентность данных в индивидуальных кэш-памятях процессоров [187]. Отметим, что CDN архитектура свободна от указанного недостатка, так как на виртуальном уровне в ней отсутствует разделение ресурсов. В SN системах проблема когерентности так же отсутствует, так как у них нет разделяемых ресурсов.
Еще одной серьезной проблемой для CD архитектуры являются трудности с организацией блокировок объектов базы данных со стороны обращающихся к ним транзакций. В SD кластере на каждом процессорном узле необходимо поддерживать копию глобальной таблицы блокировок, что может потребовать серьезных накладных расходов [172]. СЕ архитектура в значительной мере избавлена от этой проблемы, так как глобальная таблица блокировок SE кластера хранится в единственном экземпляре в разделяемой оперативной памяти. В SN системах нет необходимости в поддержании глобальной таблицы блокировок по причине отсутствия разделения ресурсов, поэтому SN архитектура занимает наилучшую позицию по данному параметру. CDN архитектура в полной мере наследует это качество от SN архитектуры.
Исходя из проведенного анализа, мы можем сделать вывод, что по сумме показателей, приведенных в Табл. 2, нет весомых причин для поддержки CD архитектуры в чистом виде. СЕ архитектура выглядит более привлекательно, чем SE архитектура. Однако, если принимать во внимание требования к параллельной системе баз данных высокой готовности, сформулированные в разделе 1.2, наилучшим выбором является CDN архитектура. Этот подход был нами использован при проектировании параллельной системы баз данных Омега для МВС-100/1000, архитектура которой будет рассмотрена в следующем разделе.
В данном разделе дается описание системной и аппаратной архитекту ры прототипа параллельной системы баз данных Омега [217], разработанного в Челябинском государственном университете для отечественного многопроцессорного вычислительного комплекса МВС-100/1000 [13, 22]. Подобная архитектура способна обеспечить высокую готовность данных при аппаратных отказах, демонстрируя, в то же время, общую производительность, сравнимую с производительностью систем с СЕ архитектурой.
Распределение слотов буферного пула между параллельными транзакциями
Последовательность обращений к реальной базе данных фактически представляет собой комбинацию (смесь) шаблонов (1) - (6). Стратегия LRU оказывается приемлемой только для шаблона (5), хотя и здесь она проигрывает стратегии LFU [123] (сравни, для примера, результаты экспериментов из раздела 4.7.1 с результатами экспериментов из статьи [150]). Очевидно, что страницы, доступ к которым осуществляется в соответствии с шаблонами (1) и (3), должны вытесняться из буфера немедленно после их использования. Для случаев (2) и (4) мы должны попытаться удержать в буфере все страницы, входящие в цикл. Если это не удается, то мы должны использовать немедленное вытеснение. В любом случае LRU будет наихудшим выбором для случаев (2)и (4).
Особенно важной разновидностью доступа к базе данных является случай (6). В данном случае для нас более важно удерживать в буфере корневую часть В+-дерева [ПО], представляющего индекс, чем его крону, так как обращения к страницам, входящим в корневую часть, будут выполняться на несколько порядков чаще, чем обращения к листьям. Однако LRU при доступе с использованием индекса будет отдавать предпочтение страницам, формирующим крону В+-дерева. Проведенные исследования [221] показывают, что количество промахов может быть сокращено на 10-15%, если мы будем учитывать специфику алгоритмов, используемых в СУБД.
Приведенные выше рассуждения показывают, что менеджер буферного пула СУБД должен допускать использование комбинированной стратегии вытеснения. Возможный механизм реализации такой комбинированной стратегии заключается в следующем [57, 64]. Все страницы, находящиеся в буферном пуле, делятся на непересекающиеся группы. С каждой группой связывается своя стратегия вытеснения. Общая стратегия вытеснения определяется функцией вычисления рейтинга страницы, формула которой зависит от конкретной стратегии, связанной с данной страницей. Подобный механизм был использован при реализации менеджера буферного пула СУБД Омега. Более детально эти вопросы будут рассмотрены в разделе 3.3.
Одним из важных сервисов, предоставляемых СУБД, является восстановление целостности информации в базе данных после программного или аппаратного сбоя [28, 29]. Данный сервис обеспечивает поддержку свойства атомарности транзакций [29, 137, 158], заключающегося в том, что транзакция не может быть выполнена частично. Это означает, что все изменения, сделанные в ходе выполнения транзакции, должны быть аннулированы, если транзакция по тем или иным причинам не может быть выполнена до конца. При этом атомарная транзакция может изменять значительный объем данных и затрагивать большое количество файлов.
Стандартным механизмом реализации данного сервиса является ведение журнала изменений [29]. Прежде чем изменения, выполняемые в ходе транзакции, будут зафиксированы на диске, все новые значения обновляемых элементов базы данных записываются в журнал изменений. После того, как весь список планируемых изменений помещен в журнал, для данной транзакции устанавливается флаг фиксации. Последним шагом выполнения транзакции является внесение актуальных изменений в базу данных в соответствии со списком запланированных изменений. При этом путем достаточно искусного программирования СУБД должна обеспечивать идемпотентность данного шага, то есть финальный результат всегда должен получаться одинаковым вне зависимости от того, сколько раз мы выполнили список запланированных изменений.
В ходе восстановления после сбоя для каждой незавершенной транзакции анализируется флаг фиксации. Если данный флаг установлен, то утилита, выполняющая восстановление, просматривает список запланированных изменений и повторно обновляет все упомянутые в нем элементы базы данных. Если флаг фиксации не установлен, то список планируемых изменений просто удаляется из журнала. Данный метод и его вариации описаны в работах [29, 137, 138, 140, 141].
Имеется следующая важная связь между восстановлением после сбоя и управлением буферным пулом [221]. Страница, содержащая флаг фиксации, не может быть вытеснена на диск до того момента, когда все страницы, содержащие список запланированных изменений, будут вытеснены на диск. Более того, транзакция не может считаться завершенной, пока страница, содержащая флаг фиксации, не будет вытеснена на диск (даже если все актуальные изменения внесены в базу данных).
В соответствие с этим менеджер буферного пула должен поддерживать некоторый механизм избирательного вытеснения страниц, который позволил бы обеспечить сброс на диск списка запланированных изменений и флага фиксации в надлежащем порядке. Для реализации этой возможности в параллельной СУБД Омега нами был использован механизм статических и динамических рейтингов страниц [49, 57, 64]. Данный механизм детально описывается в разделе 3.3.
Системы баз данных, как правило, предусматривают одновременное (параллельное) выполнение многих транзакций. При этом несколько параллельных транзакций могут выполняться на одном процессорном узле с приватной оперативной памятью1 и обращаться к данным, расположенным на одном диске. Для таких транзакций возникает проблема выбора алгоритма распределения слотов буферного пула.
Простейшим решением данной проблемы является отсутствие какого-то бы то ни было деления буферного пула между транзакциями, то есть все транзакции разделяют общий буферный пул. Данное решение может быть достаточно эффективным, если имеет место межтранзакционная локальность обращений [199]. Локальность подразумевает, что вероятность обращения к странице, к которой недавно произошло обращение, будет выше, чем средняя вероятность обращения. Межтранзакционная локальность предполагает, что в последовательности обращений к диску, генерируемой смесью транзакций, имеет место локальность обращений.
Периодическое распределение вероятностей обращений
Существуют две хорошо известные общие модели, используемые при реализации параллельных исполнителей запросов, называемые скобочной и операторной моделями [135].
Скобочная модель была использована в целом ряде параллельных СУБД. В качестве примера можно привести системы Gamma [118] и Bubba [89]. В основе механизма скобочной модели лежит некоторый универсальный скобочный шаблон процесса, который может получать и посылать данные и выполнять какую-либо одну реляционную операцию. Схематично данный скобочный шаблон изображен на Рис. 49 вместе с операциями соединения и агрегации.
Во время параллельного выполнения запроса код, реализующий скобочный шаблон, вызывает соответствующую реляционную операцию, которой передается управление. Сетевые операции ввода-вывода порций данных реализуются в виде стандартных процедур, которые вызываются реляционной операцией по мере необходимости. Каждая операция в скобочной модели имеет не более двух входных потоков (на Рис. 49 они обозначены как inputA и inputB) и один выходной поток (на Рис. 49 он обозначен как output). Этого оказывается достаточным, так как в большинстве систем баз данных используются только унарные и бинарные операции. Скобочный шаблон выполняет роль некоторой капсулы, изолирующей реляционную операцию от ее окружения, например от других операций, которые производят данные для ее входных потоков и потребляет данные из ее выходного потока. Основная проблема, связанная с использованием скобочной модели, заключается в том, что для каждой параллельной операции на всех задействованных процессорных узлах должны быть явно созданы соответствующие скобочные процессы. Это обычно выполняется специальным управляющим процессом, который должен быть запрограммирован с учетом знания структуры всех параллельных алгоритмов, реализующих все реляционные операции. В соответствие с этим мы должны вносить изменения в программный код данного управляющего процесса всякий раз, когда мы добавляем в систему новую операцию или новый алгоритм для уже существующей операции. Таким образом, скобочная модель представляется малопригодной для СУБД, поддерживающих абстрактные (пользовательские) типы данных [223]. Однако поддержка пользовательских типов является одним из важных требований, предъявляемых к современным системам баз данных [75, 114, 225].
Операторная модель была использована при реализации параллельной СУБД Volcano [136] с SE архитектурой. Данная модель характеризуется тем, что все аспекты, связанные с распараллеливанием запроса, инкапсулируются в реализации некоторого специального оператора обмена [134]. Данный оператор имеет стандартный итераторный интерфейс, включающий в себя функции open, next, close [135], и может быть помещен в любое место дерева запроса как обычная реляционная операция. Отличительной чертой операторной модели является расширяемость системы путем добавления новых операций или алгоритмов. Операторная модель оказывается достаточно эффективной для систем с разделяемой памятью. Однако итераторная природа оператора обмена делает данную модель неэффективной для систем с распределенной памятью. При наличии перекосов данных операторы обмена могут стать узким местом в дереве запроса (см. результаты экспериментов в разделе 5.5).
В системе Омега мы используем новый механизм для организации параллельного выполнения запросов, названный потоковой моделью. Данная модель соединяет в себе преимущества скобочной и операторной модели и оптимальным образом учитывает особенности аппаратной архитектуры системы Омега. Потоковая модель основана на парадигме производительпотребитель и использует механизм потоков под управлением данных для эффективной организации обменов данными между операциями. Каждая операция дерева запроса представляется в виде отдельной нити. При этом иерархия операций в дереве запроса отображается в иерархию нитей, описанную в разделе 2.3.2. Для унифицированного представления узлов дерева запроса на физическом уровне используется общий операторный фрейм, структура и специфика использования которого описываются в разделе 5.3.2. Для организации внутриоперационного параллелизма в потоковой модели используется специальный оператор обмена exchange, структура и специфика использования которого описываются в разделе 5.3.3. Потоковая мо дель подобно операторной модели обладает свойством расширяемости, так как все аспекты, связанные с распараллеливанием запроса, инкапсулируются в операторе обмена exchange, который может быть помещен в любом месте дерева запроса как обычная реляционная операция. В то же время, в отличие от итераторного подхода, используемого в операторной модели, в потоковой модели для передачи данных в дереве запроса от одной реляционной операции другой используются промежуточные хранилища, называемые складами. Склад является своеобразным буфером между производителем и потребителем. Состояние склада является основой для синхронизации и диспетчеризации процессов. Подобный подход позволяет в значительной мере предотвратить дисбаланс загрузки при наличии перекоса данных в многопроцессорной системе с распределенной памятью.
