«ЛЫМАРЬ Татьяна Юрьевна РАЗРАБОТКА МОДЕЛЕЙ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ЗАПРОСОВ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы ...»

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

ЛЫМАРЬ Татьяна Юрьевна

РАЗРАБОТКА МОДЕЛЕЙ

ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ЗАПРОСОВ

В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ

Специальность 05.13.18 – математическое моделирование,

численные методы и комплексы программ Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

СОКОЛИНСКИЙ Леонид Борисович, канд. физ.-мат. наук, доцент Челябинск-2002 Оглавление Введение

Глава 1. АРХИТЕКТУРА СИСТЕМ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ

ТРАНЗАКЦИЙ

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

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

1.3. Архитектура системы Омега

1.3.1. Аппаратная архитектура системы Омега

1.3.2. Программная структура СУБД Омега

1.4. Организация обработки транзакций в параллельных СУБД..................

1.4.1. Структура СУБД

1.4.2. Формы параллельной обработки транзакций

1.4.3. Архитектура параллельного исполнителя запросов

1.5. Заключительные замечания к главе 1

Глава 2. МЕТОДЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ

ЗАПРОСОВ

2.1. Анализ различных подходов к распараллеливанию запросов 2.1.1. Модели синхронизации операций в дереве запроса

2.1.2. Модели параллелизации запросов в многопроцессорных системах...

2.1.3. Потоковая модель распараллеливания запросов

2.2. Синхронизация выполнения операций в системе Омега

2.3. Параллелизация запросов в системе Омега

2.4. Заключительные замечания к главе 2

Глава 3. ПОТОКОВАЯ МОДЕЛЬ

3.1. Концепция потоков

3.2. Операторный фрейм

3.3. Структура оператора

3.4. Результаты экспериментов

3.5. Заключительные замечания к главе 3

Глава 4. Принципы реализации исполнителя запросов системы Омега.........

4.1. Структура исполнителя запросов

4.1.1. Класс Stock

4.1.2. Класс Stream

4.1.3. Класс Tree

4.1.4. Модуль интерпретатора операций физической алгебры..................

4.1.5. Модуль исполнителя запросов

4.1.6. Пример использования исполнителя запросов

4.2. Реализация реляционных операций

4.3. Заключительные замечания к главе 4

Заключение

Литература

Приложение

Введение В настоящее время системы управления базами данных (СУБД) используются практически во всех сферах человеческой деятельности, связанных с хранением и обработкой информации. Прогресс, достигнутый в области технологий баз данных, в значительной мере базируется на реляционной модели, предложенной Э. Коддом [48] на рубеже 60-70-х годов ХХ века. За свою тридцатилетнюю историю реляционные СУБД прошли путь от научно-исследовательских прототипов, наиболее значительными из которых являются System R [92] и Ingres [99], до коммерческих продуктов, способных хранить и обрабатывать терабайты информации. Однако научная и практическая деятельность человека выдвигает все новые масштабные задачи, требующие обработки сверхбольших баз данных.

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

Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских поставляемым на рынок высокопроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести DB2 Parallel Edition [31], NonStop SQL [26, 42] и NCR Teradata [14]. Подобные системы объединяют до тысячи процессоров и магнитных дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем дополнительных научных исследований [109]. Одной из таких проблем является эффективная организация параллельной обработки потока совершенствования методов организации параллельного выполнения запросов применительно к новым гибридным архитектурам.

В настоящее время одной из перспективных отечественных разработок в сфере многопроцессорных вычислительных систем является многопроцессорный вычислительный комплекс МВС-100/1000 [13].

МВС-100/1000 представляет собой семейство масштабируемых многопроцессорных вычислительных систем с массовым параллелизмом, являющихся совместной разработкой институтов РАН и промышленности.

Вычислительные комплексы МВС-100/1000 используются в ряде академических институтов и университетов России для решения широкого спектра фундаментальных научных и прикладных задач в областях управления динамическими системами и дифференциальных игр, механики сплошной среды, математического программирования, обработки изображений и распознавания образов и др. Однако в настоящее время отсутствует специализированное системное программное обеспечение, позволяющее хранить и обрабатывать на МВС-100/ сверхбольшие базы данных. В Челябинском государственном университете при поддержке Российского фонда фундаментальных исследований (гранты 97-07-90148, 00-07-90077) ведется работа по созданию прототипа параллельной СУБД Омега [21, 94-98] для многопроцессорной вычислительной системы МВС-100/1000. В соответствии с этим актуальной является задача разработки новых моделей параллельного выполнения запросов, ориентированных на архитектуру МВС.

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

1) исследование и анализ существующих моделей и методов организации параллельного выполнения запросов;

2) разработка новых моделей и методов параллельного выполнения распределенной памятью;

3) разработка на базе предложенных моделей и методов исполнителя запросов СУБД Омега;

4) проведение вычислительных экспериментов по исследованию эффективности разработанных моделей и методов.

заключения и приложения.

В первой главе «Архитектура систем параллельной обработки транзакций» формулируются требования к параллельным системам баз данных, приводится классификация архитектур параллельных систем баз данных и производится их сравнительный анализ. Затем описывается трехуровневая иерархическая CD2 архитектура параллельной системы баз данных Омега. Приводится описание аппаратной и программной архитектура системы Омега. Далее дается обзор способов организации параллельной обработки транзакций в параллельных системах баз данных.

Затем формулируются требования, которым должен удовлетворять исполнитель запросов, описываются место и роль исполнителя запросов в программной структуре СУБД.

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

Затем описывается предложенная для системы Омега оригинальная модель синхронизации операций, основанная на понятии Т-фактора.

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

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

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

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

В приложение вынесены алгоритмы реализации реляционных операций.

ГЛАВА 1. АРХИТЕКТУРА СИСТЕМ ПАРАЛЛЕЛЬНОЙ

ОБРАБОТКИ ТРАНЗАКЦИЙ

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

Глава имеет следующую структуру. В разделе 1.1 формулируются требования, которым должна соответствовать современная высокопроизводительная параллельная система баз данных. В разделе 1. на базе классификации Стоунбрейкера анализируются достоинства и недостатки различных классов архитектур параллельных систем баз данных, и описывается иерархическая архитектура CD2, использованная в системе Омега. В разделе 1.3 приводится описание аппаратной и программной архитектуры системы Омега. Раздел 1.4 посвящен вопросам организации параллельной обработки транзакций. Описывается типовая структура СУБД, рассматриваются формы параллельной обработки, описываются место и роль исполнителя запросов в программной иерархии СУБД, формулируются требования, которым должен удовлетворять исполнитель запросов.

1.1. ТРЕБОВАНИЯ К ПАРАЛЛЕЛЬНЫМ СИСТЕМАМ БАЗ ДАННЫХ

следующим основным требованиям [1, 68, 101, 110]:

• масштабируемость –возможность пропорционального увеличения соответствующих аппаратных ресурсов;

• производительность – общая характеристика эффективности работы системы;

• отказоустойчивость – способность системы сохранять общую работоспособность при отказе части оборудования;

• высокая готовность данных - способность системы восстанавливать одновременном сохранении способности выполнять запросы к базе данных.

Рассмотрим перечисленные требования более подробно.

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

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

Основными показателями эффективности масштабирования системы являются ускорение и расширяемость [53].

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

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

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

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

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

производительности параллельной системы баз данных влияет целый ряд факторов, среди которых можно выделить следующие [1, 110]:

• Интеграция в СУБД низкоуровневых системных функций. Как показали исследования [11, 100], во многих случаях сервисы, предоставляемые операционными системами общего назначения, оказываются неэффективными и неадекватными с точки зрения СУБД.

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

• Использование легковесных процессов [11, 112, 83]. Наиболее эффективным средством представления операций дерева запроса и системных процессов в параллельной СУБД являются легковесные процессы (нити).

выполнении задачи очень важно, чтобы время выполнения фрагмента задачи на каждом задействованном процессоре было примерно одинаковым. Эту проблему можно решить, равномерно распределив фрагменты задачи между процессорами. Практика использования баз данных показывает, что до выполнения запроса невозможно достоверно предсказать верное распределение данных [46, 77, 80], поэтому СУБД должна обладать эффективным механизмом балансирования загрузки, который позволял бы динамически перераспределять данные между процессорами во время выполнения запроса.

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

• Эффективность алгоритмов реализации реляционных операций. На уровне СУБД обработка пользовательского запроса заключается в выполнении последовательности реляционных операций [60]. Поэтому реляционных операций чрезвычайно важна для обеспечения высокой производительности системы в целом.

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

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

Высокая готовность данных. Под высокой готовностью данных понимается способность системы восстанавливать потерянные данные таким образом, чтобы это было "не очень" заметно для пользователя, выполняющего запросы к базе данных [68]. Если в процессе восстановления 80-90% ресурсов системы тратится исключительно на цели восстановления базы данных, то такая система может оказаться неприемлемой для случаев, когда ответ на запрос должен быть получен немедленно.

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

Существенную роль при обеспечении высокой готовности данных играют следующие факторы [68]:

• оперативное восстановление базы данных;

• восстановление целостности базы данных после сбоя;

• прозрачность для пользователя процессов восстановления системы.

Восстановление целостности базы данных после сбоя предполагает поддержку ACID транзакций и журнализацию изменений [12, 62]. Данные возможности поддерживаются большинством современных СУБД с архитектурой клиент-сервер.

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

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

Итак, мы сформулировали 4 основных требования, предъявляемых к современным параллельным системам баз данных. Как мы увидим в дальнейшем, подходы к решению указанных проблем в определяющей степени зависят от аппаратной архитектуры параллельной системы баз данных.

1.2. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АРХИТЕКТУР ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ

ДАННЫХ

Существует несколько известных видов классификации архитектур многопроцессорных систем [2, 55]. Однако, для параллельных систем баз данных наиболее употребительной классификацией многопроцессорных архитектур является классификация, предложенная Майклом Стоунбрейкером (Michael Stonebraker) в работе [101].

В соответствие с классификацией Стоунбрейкера аппаратные архитектуры параллельных систем баз данных делятся на три основных класса в зависимости от способа разделения аппаратных ресурсов:

SE (Shared-Everything) - архитектура с разделяемыми памятью и (1) дисками [Рис. 1];

SD (Shared-Disks) - архитектура с разделяемыми дисками [Рис. 2];

(2) SN (Shared-Nothing) - архитектура без совместного использования (3) ресурсов [Рис. 3].

В системах с разделяемой памятью и дисками (см. Рис. 1) все процессоры (P) с помощью общей шины соединяются с разделяемой памятью (M) и дисками (D).

Рис. 1. Архитектура с разделяемой памятью и дисками.

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

Однако SE архитектура имеет ряд недостатков, из которых наиболее существенными являются ограниченная масштабируемость и низкая аппаратная отказоустойчивость. При большом количестве процессоров в SE системе начинают возникать конфликты доступа к разделяемой памяти, что может привести к серьезной деградации общей производительности системы [66]. В соответствии с этим масштабируемость реальных SE систем ограничивается 20-30 процессорами [110]. Кроме этого, SE системы не могут обеспечить высокую готовность данных при отказах аппаратуры [85]. Выход из строя практически любой аппаратной компоненты приводит к выходу из строя всей системы. Все это делает невозможным использование SE архитектуры в чистом виде для систем с высокими требованиями к готовности данных.

Существует большое количество параллельных систем баз данных с SE архитектурой. По существу все ведущие коммерческие СУБД сегодня имеют реализацию на базе SE архитектуры. В качестве одного из первых примеров портирования с однопроцессорной системы на SE архитектуру можно привести реализацию DB2 на IBM3090 с 6 процессорами [45].

Другим примером является параллельное построение индексов в Informix OnLine 6.0 [51]. Следует отметить, однако, что подавляющее большинство коммерческих SE систем использует только межтранзакционный параллелизм (то есть внутритранзакционный параллелизм отсутствует).

исследовательских прототипов SE систем, использующих внутризапросный параллелизм, например, XPRS [103], DBS3 [34, 32] и Volcano [59, 61].

В системах с разделяемыми дисками (см. Рис. 2) каждый процессор (P) имеет собственную приватную память (M) [89]. Процессоры соединяются друг с другом и с дисковыми подсистемами (D) с помощью некоторой соединительной сети (N). При этом любой процессор имеет доступ к любому диску.

SD архитектура, по сравнению с SE архитектурой, демонстрирует лучшую масштабируемость и более высокую степень доступности данных удовлетворительной балансировки загрузки, поскольку каждому процессору доступны все диски. Однако при реализации SD систем возникает ряд серьезных технических проблем, среди которых наиболее существенными являются проблема организации глобальной таблицы блокировок и проблема обеспечения когерентности кэшей [89]. Трудности с организацией блокировок объектов базы данных со стороны обращающихся к ним транзакций возникают, так как на каждом процессорном узле необходимо поддерживать копию глобальной таблицы блокировок, что может потребовать серьезных накладных расходов [79].

Примерами параллельных систем баз данных с SD архитектурой являются IBM IMS [105], Oracle Parallel Server [72] на nCUBE [6] и VAXcluster [70], IBM Parallel Sysplex [69, 81] и др.

В системах без совместного использования ресурсов (см. Рис. 3) каждый процессор (P) имеет собственную приватную память (M) и собственный диск (D). Процессоры соединяются друг с другом с помощью некоторой соединительной сети (N) позволяющей организовывать обмен сообщениями между процессорами [53].

Рис. 3. Архитектура без совместного использования ресурсов.

SN архитектура имеет наилучшие показатели по отказоустойчивости.

Масштабируемость SN архитектуры характеризуется как средняя. Это связано с тем, что при большом количестве процессорных узлов межпроцессорная соединительная сеть становится узким местом [81, 89].

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

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

Действительно, в SN системе невозможно непосредственно переключить простаивающий процессор на обработку данных, хранящихся на "чужом" диске. Чтобы разгрузить некоторый процессорный узел, необходимо часть "необработанных" данных переместить по соединительной сети на существенному возрастанию пересылок больших объемов данных по коммуникаций является одной из слабых сторон SN архитектуры [53, 101].

Поэтому перекосы в распределении данных по процессорным узлам могут привести к полной деградации общей производительности SN системы [71].

исследовательских прототипов и несколько коммерческих систем с SN архитектурой, использующих фрагментный параллелизм. В качестве примеров исследовательских прототипов SN систем можно привести следующие системы: ARBRE [74], BUBBA [36], EDS [93], GAMMA [52], KARDAMOM [41], PRISMA [28]. Примерами коммерческих систем с SN архитектурой являются NonStop SQL [26, 42, 53], Informix PDQ [47], Teradata DBC/1012 [14, 84], IBM DB2 PE [31] и др.

Сравнительный анализ SE, SD и SN архитектур был выполнен Стоунбрейкером в классической работе [101]. Этот анализ показал, что для масштабируемых высокопроизводительных систем баз данных из трех указанных архитектур наиболее предпочтительной является SN архитектура.

Классификация Стоунбрейкера долгое время фактически являлась стандартной и была использована в целом ряде работ, посвященных анализу архитектур параллельных систем баз данных (см., например, работы [31, 33, 53, 66, 110]). Однако в последнее время данная классификация стала подвергаться критике, как более не охватывающая всего многообразия существующих архитектур [81]. Наиболее весомым аргументом против этой классификации стало появление гибридных (иерархических) многопроцессорных систем, совмещающих в себе черты как SE так и SN архитектур [30, 66, 81, 87, 110]. Эти архитектуры в полной мере наследуют достоинства предшествующих архитектур и, в то же время, облегчают корректировку недостатков, так как решение проблем может выполняться на двух уровнях - межкластерном и внутрикластерном.

Примером такой архитектуры является CE-архитектура (ClusteredEverything), в которой SE-кластеры объединяются в единую SN-систему, как это показано на Рис. 4. SE-кластер представляет собой фактически самостоятельный мультипроцессор с разделяемой памятью и дисками.

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

P P P P P P

D D D D D D

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

параллельной системы баз данных Омега [98] для МВС [4, 8]. Гибридная архитектура, предложенная для системы Омега была названа CD архитектурой (см. Рис. 5).

Рис. 5. Трехуровневая иерархическая архитектура CD2 архитектура.

CD2 архитектура [19, 95] представляет собой трехуровневую иерархическую архитектуру. Первый уровень иерархии представлен несимметричными двухпроцессорными модулями с разделяемой памятью (SM2). Каждый SM2 модуль включает в себя вычислительный (PC) и разделяемую память (M). Вычислительный процессор используется для выполнения всех процессов базы данных. Коммуникационный процессор используется главным образом для организации обменов сообщениями по соединительной сети (N). Подобный подход позволяет освободить существенными [53, 100].

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

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

На третьем уровне иерархии SD2 кластеры объединяются в единую CD2 систему по принципу SN. Для объединения используется некоторая высокоскоростная соединительная сеть N.

Описанный подход позволяет избежать проблем, связанных с реализацией глобальной таблицы блокировок и поддержкой когерентности кэшей, характерных для SD систем [110], так как на виртуальном уровне в CD2 архитектуре отсутствует разделение ресурсов. CD2 архитектура также демонстрирует наилучшую отказоустойчивость и готовность данных, так как все проблемы, связанные с обеспечением этих свойств могут быть эффективно решены на уровне отдельных SD кластеров. Как и другие гибридные архитектуры [38, 49, 66, 87, 116], CD2 демонстрирует высокую масштабируемость за счет того, что наиболее интенсивные коммуникации сосредотачиваются внутри кластеров, разгружая тем самым межкластерную соединительную сеть. CD2 позволяет достичь хорошей сбалансированности загрузки, так как баланс загрузки может выполняться на двух уровнях - межкластерном и внутрикластерном.

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

1.3. АРХИТЕКТУРА СИСТЕМЫ ОМЕГА 1.1.1 1.3.1. АППАРАТНАЯ АРХИТЕКТУРА СИСТЕМЫ ОМЕГА В данном разделе дается описание аппаратной архитектуры прототипа параллельной системы баз данных Омега [98], разработанного в Челябинском государственном университете для отечественного многопроцессорного вычислительного комплекса МВС-100/1000 [4, 8].

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

Система Омега имеет трехуровневую иерархическую аппаратную архитектуру. Первый уровень иерархии представлен типовыми процессорными модулями (ТПМ), выпускаемыми промышленностью для комплектования многопроцессорных систем МВС-100/1000. Общая структура ТПМ изображена на Рис. 6.

Рис. 6. Структура типового процессорного модуля (ТПМ) МВС-100/1000.

ТПМ имеет архитектуру с разделяемой памятью и включает в себя вычислительный процессор Pc и коммуникационный (сетевой) процессор Pn. Взаимодействие вычислительного и коммуникационного процессоров осуществляется через общую оперативную память (SRAM). Кроме этого, коммуникационный процессор имеет собственную приватную память (DRAM). Коммуникационный процессор оснащен высокоскоростными внешними каналами (линками) для соединения с другими ТПМ модулями.

ТПМ устанавливаются в стойках промышленного стандарта (от 4 до 64 процессорных модулей в одной стойке). Стойки могут соединяться между собой для формирования единой вычислительной системы, объединяющей в себе до тысячи процессоров. Управление МВС осуществляется через host-машину, представляющую собой обычный персональный компьютер или рабочую станцию.

В качестве вычислительного процессора в ТПМ для МВС- используется суперскалярный процессор i860 фирмы Intel. В качестве коммуникационного процессора используется транспьютер T805, имеющий четыре внешних канала с пропускной способностью 20 Мбит/с каждый. Модуль оснащается разделяемой оперативной памятью объемом 8-32 Мбайт.

В качестве вычислительного процессора в ТПМ для МВС- используется процессор Alpha 21164 фирмы DEC-Compaq. В качестве коммуникационного процессора используется микропроцессор TMS320C44 фирмы Texas Instruments, имеющий 4 внешних канала с пропускной способностью 20 Мбайт/с каждый, либо микропроцессор SHARC ADSP 21060 фирмы Analog Devices, имеющий 6 внешних каналов с пропускной способностью 40 Мбайт/с каждый. Модуль оснащается разделяемой оперативной памятью объемом 0,1-2 Гбайт.

Второй уровень иерархии представлен Омега-кластерами [19, 21, Все Омега-кластеры имеют стандартную предопределенную 95].

архитектуру с небольшим количеством процессорных модулей и дисковой подсистемой, объединенными в единую сеть с высокой степенью связности (длина кратчайшего пути между любыми двумя узлами сети не должна превышать значения 2). Модуль дисковой подсистемы имеет свой коммуникационный процессор, сопряженный с SCSI шиной, к которой может быть подключено до семи дисковых накопителей. Каждый кластер имеет свободные линки для связи с другими кластерами.

Примеры возможных конфигураций Омега-кластеров приведены на Рис. 7. Здесь UPM (Uniform Processor Module) - типовой процессорный модуль; DSM (Disk Subsystem Module) - модуль дисковой подсистемы.

Конфигурация А предполагает использование ТПМ с четырьмя внешними каналами. Конфигурация В предполагает использование ТПМ с шестью внешними каналами. Использование двух дисковых подсистем в конфигурации B позволяет повысить отказоустойчивость кластера.

UPM UPM

UPM UPM

DSM UPM UPM

UPM UPM

UPM UPM

Рис. 7. Два варианта конфигурации Омега-кластера.

объединяются в единую систему по схеме SN. При этом топология межкластерных соединений не фиксируется и может варьироваться от простой линейки до гиперкуба.

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

1.1.2 1.3.2. ПРОГРАММНАЯ СТРУКТУРА СУБД ОМЕГА Прототип параллельной системы управления базами данных (СУБД) Омега включает в себя оптимизирующий компилятор с языка SQL, планировщик запросов и дистрибутивное ядро, загружаемое на всех процессорных модулях.

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

Рис. 8. Программная иерархия системы Омега.

Менеджер файлов, менеджер сообщений и менеджер нитей фактически образуют операционное окружение СУБД Омега [97]. Необходимость создания специализированного системного окружения была обусловлена тем, что соответствующие сервисы, предоставляемые операционными системами общего назначения (для МВС-100 - это микро-ОС Router и распределенный аналог ОС UNIX - Helios) оказываются, как правило, неадекватными и недостаточно эффективными для нужд СУБД [100].

Менеджер нитей [24, 96, 97] обеспечивает поддержку легковесных процессов (нитей управления), позволяющих эффективно выполнять на одном процессорном узле несколько задач в режиме разделения времени.

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

Менеджер сообщений [96] состоит из двух подсистем: кондуктора и маршрутизатора. Кондуктор обеспечивает передачу сообщений между узлами одного Омега-кластера путем реализации архитектуры виртуальных каналов [96]. Виртуальный канал кондуктора однозначно идентифицируется путем указания номера процессора-реципиента и номера порта обмена. Маршрутизатор обеспечивает передачу сообщений между различными Омега-кластерами в пределах всей системы. Он также реализует архитектуру виртуальных каналов. Обе подсистемы имеют сходный внешний интерфейс. Однако, кондуктор имеет совершенно отличный внутренний протокол межпроцессорного обмена данными, в котором по существу используется знание предопределенной топологии межпроцессорных соединений Омега-кластера. Это позволяет существенно повысить эффективность межпроцессорных обменов внутри Омега-кластеров по сравнению с операционными системами общего назначения.

Менеджер файлов [22, 27, 118] включает в себя две подсистемы, менеджер фрагментов и менеджер буферного пула. Менеджер фрагментов поддерживает внутрикластерную фрагментацию и репликацию данных и использует стандартный механизм для страничной организации внешней памяти на магнитных дисках с длиной страницы, равной 4 Кбайтам. Менеджер буферного пула управляет буферами в оперативной памяти, используемыми для обеспечения эффективного доступа к страницам внешней памяти на магнитных дисках. Для вытеснения страниц из буферного пула в системе Омега был использован оригинальный механизм, базирующийся на избыточном индексе буферного пула и динамических рейтингах страниц.

Исполнитель запросов предоставляет пользователю средства для формирования и выполнения дерева запроса. Подробнее его роль и структура будет описана в главе 4.

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

1.1.3 1.4.1. СТРУКТУРА СУБД Система управления базой данных (СУБД) представляет собой программное обеспечение, которое управляет всем доступом к базе данных [5]. Концептуально это происходит следующим образом.

1) Пользователь выдает запрос на доступ к данным, применяя некоторый язык манипулирования данными, обычно это язык SQL.

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

3) СУБД выполняет необходимые операции в базе данных.

Рассмотрим процесс обработки запроса более подробно. Схема обработки запроса изображена на Рис. 9.

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

Компилятор переводит исходный запрос пользователя с языка SQL в некоторое внутреннее представление, более подходящее для машинных манипуляций. Наиболее распространенными способами внутреннего представления являются реляционная алгебра и представление запроса в виде дерева [60]. Чаще всего для внутреннего представления запросов используется та или иная модификация абстрактного синтаксического дерева, которое называется деревом запроса [5].

Рис. 9. Схема обработки запроса типичной СУБД.

Работа компилятора языка запроса состоит из трех этапов [57]:

• перевод текста SQL запроса в дерево запроса;

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

• преобразование дерева, переводящее дерево запроса в дерево операций реляционной алгебры, называемое логическим планом запроса.

Результат работы компилятора – логический план выполнения запроса - передается для дальнейшей обработки оптимизатору запросов.

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

1) формируется множество алгебраически эквивалентных вариантов логического плана запроса;

2) для каждой операции каждого варианта плана определяется множество алгоритмов ее реализации;

3) для каждой пары смежных операций в планах выполнения запроса определяются возможные механизмы передачи данных (через диск, сеть или основную память).

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

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

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

Физический план выполнения передается исполнителю запросов.

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

1.1.4 1.4.2. ФОРМЫ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ТРАНЗАКЦИЙ Существует несколько форм параллельной обработки транзакций, рассматриваемых в научной литературе [9, 60, 89, 109]. Классификация различных форм параллелизма схематично изображена на Рис. 10.

Рис. 10. Классификация форм параллельной обработки.

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

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

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

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

параллельное выполнение независимых поддеревьев дерева, представляющего запрос. Основная проблема, связанная с кустовым параллелизмом, заключается в том, что очень трудно обеспечить, чтобы два под запроса одного запроса начали генерировать выходные данные в правильное время и в правильном темпе. При этом правильное время далеко не всегда означает одинаковое время, например для входных потоков операции хеш-соединения, а правильный темп далеко не всегда означает одинаковый темп, например для случая, когда входные потоки соединения слиянием имеют различные размеры [60]. В силу указанных причин кустовой параллелизм редко используется на практике. В научных публикациях кустовой параллелизм исследовался главным образом в контексте оптимизации запросов с мультисоединениями [44, 43, 91]. В разделе 1.1.8 нами будет предложен оригинальный механизм организации параллельного выполнения запросов, названный потоковой моделью.

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

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

Подобный подход впервые был использован при реализации System R [92] и получил называние синхронного конвейера [86]. Основным недостатком синхронного конвейера является блокирующий характер операций конвейерной обработки отдельных гранул. Если некоторая операция задерживается с обработкой очередной гранулы данных, то она блокирует работу всего конвейера. Для преодоления указанного недостатка может быть использован асинхронный конвейер, в котором поставщик и потребитель работают независимо друг от друга, а данные передаются через некоторый буфер. Поставщик помещает производимые гранулы в буфер, а потребитель забирает гранулы из данного буфера в соответствующем порядке. При этом необходимо определенное управление потоком данных, которое препятствовало бы переполнению указанного буфера в случае, когда потребитель работает медленнее, чем поставщик. Подобный подход был использован в параллельной СУБД Volcano [59] и в распределенной СУБД R* [73]. Различные механизмы реализации синхронных и асинхронных конвейеров в контексте распределенных баз данных были исследованы в работе [106]. Следует отметить, что степень конвейерного параллелизма в любом случае ограничена количеством операций, вовлекаемых в конвейер. При этом для реляционных систем баз данных длина конвейера редко превышает операций [53]. Поэтому для достижения более высокой степени распараллеливания наряду к конвейерным параллелизмом необходимо использовать внутриоперационный параллелизм.

Внутриоперационный параллелизм реализуется в основном в форме фрагментного параллелизма [53]. Некоторые авторы (см., например, [89]) рассматривают и другие формы внутриоперационного параллелизма, базирующиеся на делении операции на подоперации.

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

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

результирующее отношение [53].

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

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

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

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

1.1.5 1.4.3. АРХИТЕКТУРА ПАРАЛЛЕЛЬНОГО ИСПОЛНИТЕЛЯ ЗАПРОСОВ специальный компонент СУБД, называемый исполнителем запросов. Как уже упоминалось ранее, в системной иерархии СУБД он занимает место между компилятором языка запросов и файловой системой.

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

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

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

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

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

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

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

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

Исполнитель запросов параллельной СУБД должен удовлетворять следующим требованиям:

1) автоматическая параллелизация запросов;

2) автоматические диспетчеризация и синхронизация процессов выполнения реляционных операций в дереве запроса;

3) расширяемость путем добавления новых параллельных алгоритмов выполнения реляционных операций;

4) устойчивость к перекосам данных и перекосам выполнения;

5) эффективность.

Рассмотрим приведенные требования более подробно.

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

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

параллельных систем баз данных с распределенной памятью, является проблема эффективной балансировки загрузки процессоров при наличии перекосов. В работе [71] были определены два основных фактора, влияющие на эффективность распараллеливания: стохастическая природа времени выполнения реляционных операций (перекос выполнения) и перекосы в распределении значений атрибутов соединения (перекос данных). Исполнитель запросов должен иметь возможность автоматически корректировать загрузку процессоров при возникновении таких ситуаций.

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

1.5. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ К ГЛАВЕ В данной главе были рассмотрены существующие подходы к проектированию архитектур систем параллельной обработки транзакций.

На основе сформулированных требований, которым должна соответствовать современная высокопроизводительная параллельная система баз данных, и классификации Стоунбрейкера был проведен сравнительный анализ современных архитектур параллельных систем баз данных. Этот анализ показал, что наилучшие показатели имеет CD архитектура, предложенная и описанная в работах [19, 20, 21, 94, 95].

Далее описана аппаратная и программная архитектуры параллельной системы баз данных Омега, для которой была разработана CD архитектура.

ЗАКЛЮЧИТЕЛЬНАЯ ЧАСТЬ ГЛАВЫ ПОСВЯЩЕНА

РАССМОТРЕНИЮ МЕТОДОВ ОРГАНИЗАЦИИ

ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ТРАНЗАКЦИЙ В

МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ. ОПИСАНЫ

СУЩЕСТВУЮЩИЕ ФОРМЫ ПАРАЛЛЕЛЬНОЙ

ОБРАБОТКИ. РАССМОТРЕНА ТИПОВАЯ СТРУКТУРА

СУБД, ОПИСАНЫ МЕСТО И РОЛЬ ИСПОЛНИТЕЛЯ

ЗАПРОСОВ В ПРОГРАММНОЙ ИЕРАРХИИ СУБД,

СФОРМУЛИРОВАНЫ И ПРОАНАЛИЗИРОВАНЫ

ОСНОВНЫЕ ТРЕБОВАНИЯ, КОТОРЫМ ДОЛЖЕН

УДОВЛЕТВОРЯТЬ ИСПОЛНИТЕЛЬ ЗАПРОСОВ. ГЛАВА 2.

МЕТОДЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ

ЗАПРОСОВ

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

2.1. АНАЛИЗ РАЗЛИЧНЫХ ПОДХОДОВ К РАСПАРАЛЛЕЛИВАНИЮ ЗАПРОСОВ

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

1.1.6 2.1.1. Модели синхронизации операций в дереве запроса Одной из основных проблем, возникающих при реализации исполнителей запросов, является проблема эффективной синхронизации выполнения операций в дереве запроса. Модель синхронизации определяет, в каком порядке и с какой скоростью должны выполняться смежные узлы дерева запроса. Существуют две известные модели синхронизации, используемые при реализации исполнителей запросов итераторная модель и модель, основанная на передаче сообщений [60].

В итераторной модели с каждой операцией в дереве запроса связан итератор, интерфейс которого состоит из трех стандартных методов: Open, Next и Close. Когда операции-потребителю нужна очередная гранула данных, она выполняет вызов метода Next, ассоциированного с операциейпоставщиком. Если дерево имеет больше двух уровней, то операцияпоставщик сама будет нуждаться во входных данных и, в свою очередь осуществит вызов Next применительно к ее дочерним операциям.

Механизм такого взаимодействия операций в дереве запроса схематично изображен на Рис. 11.

Итераторная модель синхронизация операций используется в большинстве современных СУБД. Примерами таких систем являются System R[92], Ingres [99], Informix [47].

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

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

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

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

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

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

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

Рис. 12. Модель, основанная на передаче сообщений.

Классическим примером использования модели, основанной на передаче сообщений, является менеджер запросов экспериментальной параллельной СУБД Gamma [52].

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

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

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

1.1.7 2.1.2. МОДЕЛИ ПАРАЛЛЕЛИЗАЦИИ ЗАПРОСОВ В МНОГОПРОЦЕССОРНЫХ

СИСТЕМАХ

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

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

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

AGGREGATION JOIN

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

PRODUCT

PRODUCT

SCAN SCAN

Рис. 14. Пример дерева запроса, реализованного на базе скобочной модели.

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

Кроме того, при использовании скобочной модели возникает проблема управления скобочными процессами каждой параллельной операции на всех задействованных процессорных узлах. Это обычно выполняется специальным управляющим процессом, который должен быть запрограммирован с учетом знания структуры всех параллельных алгоритмов, реализующих все реляционные операции. В соответствие с этим мы должны вносить изменения в программный код данного управляющего процесса всякий раз, когда мы добавляем в систему новую операцию или новый алгоритм для уже существующей операции. Таким образом, скобочная модель плохо адаптируется к добавлению новых реляционных операций и алгоритмов и поэтому представляется пользовательских типов является одним из важных требований, предъявляемых к современным системам баз данных [29, 50, 104].

Таким образом, скобочная модель не удовлетворяет требованию расширяемости.

Скобочная модель была использована в целом ряде параллельных СУБД. В качестве примера можно привести системы Gamma [52] и Bubba [36].

Операторная модель была предложена в работе [59] группой разработчиков параллельной СУБД Volcano [60, 61].

специального оператора обмена, инкапсулирующего в себе все аспекты, связанные с распараллеливанием запроса. В системе Volcano этот оператор обозначен как оператор Exchange [59]. Оператор обмена использует итераторную модель синхронизации и имеет стандартный итераторный интерфейс, включающий в себя функции open, next, close. Оператор Exchange не оказывает никакого влияния на работу других операций в дереве запроса, поэтому может быть помещен в любое место дерева запроса как обычная реляционная операция. Пример использования операторной модели параллелизации запросов изображен на Рис. 15.

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

Рис. 15. Пример использования операторной модели параллелизации запросов.

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

Одна из сложных проблем, возникающих при использовании параллельных баз данных, – проблема перекосов в распределении данных легко решается при использовании оператора обмена, если система баз данных имеет архитектуру с разделяемой памятью. В этом случае данные можно легко перераспределить через общую память, и операторная модель оказывается достаточно эффективной. Если же мы имеем дело с архитектурой с распределенной памятью, то эффективность применения описанного оператора обмена сильно снижается из-за его итераторного характера (см. п.1.1.6). При наличии перекосов данных операторы обмена могут стать узким местом в дереве запроса, что будет подтверждено экспериментами, описанными в разделе 3.4.

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

1.1.8 2.1.3. ПОТОКОВАЯ МОДЕЛЬ РАСПАРАЛЛЕЛИВАНИЯ ЗАПРОСОВ Исходя из проведенного анализа, можно сделать вывод, что ни одна из известных моделей синхронизации и распараллеливания запросов в исполнителям запросов, в контексте иерархических архитектур с распределенной памятью. Итераторная модель синхронизации неэффективна при реализации на архитектурах с распределенной памятью;

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

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

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

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

2.2. СИНХРОНИЗАЦИЯ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ В СИСТЕМЕ ОМЕГА

В системе Омега каждая операция дерева запроса представляется в виде отдельного легковесного процесса (нити). Для синхронизации процессов мы используем некоторый компромисс между описанными моделями синхронизации. Как и в модели, основанной на передаче сообщений, операции начинают выполняться, не дожидаясь требования на свои выходные данные. Операция-поставщик, выполняясь, помещает свои результаты в буфер обмена с операцией-поставщиком, который мы назвали складом [75]. Поставщик, по мере надобности, извлекает данные из склада. Пример такой синхронизация операций в дереве запроса приведен на Рис. 16. Если склад оказывается заполнен, то операцияпоставщик вынужден приостановить свою работу до тех пор, пока потребитель не заберет хотя бы одну гранулу данных. Состояние склада является основой для синхронизации и диспетчеризации процессов.

Рис. 16. Синхронизация операций в потоковой модели.

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

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

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

Каждая операция дерева запроса представляется в виде отдельного легковесного процесса (нити). Для синхронизации и диспетчеризации нитей в системе Омега используется оригинальная модель управления процессами, базирующаяся на понятии Т-фактора. В данной модели каждый процесс рассматривается как корневая нить (в системе Омега на одном процессорном модуле может быть запущен только один процесс). С помощью вызова функции менеджера нитей fork корневая нить может породить произвольное число нитей, которые будут считаться дочерними по отношению к ней. Любая дочерняя нить аналогичным образом может породить произвольное число нитей, которые будут считаться дочерними по отношению к данной нити. Таким образом, нити образуют иерархию, поддерживаемую менеджером нитей.

С каждой нитью связывается числовая функция, выдающая значения в интервале (0;1) и называемая фактор-функцией. Значение, выдаваемое фактор-функцией в некоторый момент времени, будем называть Т-фактором нити в данный момент времени. Т-факторы используются менеджером нитей для управления процессом диспетчеризации и синхронизации нитей.

Т-фактор можно определить следующим образом. Определим i как меру заполнения склада нити Ti, 0i1 для всех i. Назовем данную меру Т-фактором нити Ti. Значение i = 1 соответствует полному заполнению склада нити Ti. Значение i = 0 соответствует ситуации, когда склад нити Ti пуст.

Определим фактор-функцию fj(t) нити Tj как вещественную функцию, вычисляющую значение Т-фактора нити Tj в момент времени t.

Пусть нити Ti1, Ti2,..., Tik являются производителями данных для нити Ti. Нить Tj будем называть дизъюнктивной, если для ее работы достаточно, чтобы хотя бы один из складов подчиненных нитей Ti1, Ti2,..

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

Определим для нитей следующие три возможных состояния.

Нить Ti находится в состоянии простоя в момент времени t, нить Ti находится в заблокированном состоянии в момент времени t, заблокирована.

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

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

Параметр nice может принимать целое значение в диапазоне от -20 до +20.

При этом значение -20 соответствует максимальной приятности и минимальному приоритету, а значение +20 соответствует минимальной приятности и максимальному приоритету. Увеличение значение параметра nice соответствует увеличению приятности и уменьшению приоритета.

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

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

Для определения формулы динамического приоритета введем следующие параметры.

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

пересчитываются по формуле C := C*k, где k некоторое фиксированное значение, 0 < k< 1.

Пусть задает значение Т-фактора текущей нити. Пусть dprty обозначает значение динамического приоритета. Тогда формулу вычисления динамического приоритета пользовательской нити можно определить следующим образом:

dprty = -(K*C + N* + threshold_nice + nice).

Здесь K и N некоторые нормализующие константы, которые наряду с m и k являются настраиваемыми параметрами менеджера нитей. Параметр threshold_nice задает положительное значение порога приятности для пользовательских нитей. Для системных нитей используется формула вычисления динамического приоритета, в которой этот параметр опущен.

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

2.3. ПАРАЛЛЕЛИЗАЦИЯ ЗАПРОСОВ В СИСТЕМЕ ОМЕГА

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

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

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

• указатель на функцию тела нити, реализующую соответствующую операцию физической алгебры;

• указатель на фактор-функцию нити;

• указатель на выходной поток;

• указатель на левого сына (может быть пустым);

• указатель на правого сына (может быть пустым);

• тип нити (конъюнктивная или дизъюнктивная).

Фактор-функция, как правило, вычисляет количество гранул данных, Максимальное количество сыновей ограничивается числом два, так как в системе Омега физическая алгебра состоит только из унарных и бинарных операций [7]. Схематически операторный фрейм изображен на Рис. 17.

Выполнение физического плана происходит следующим образом.

операторному фрейму в дереве фреймов, представляющем данный физический план. Указатель на соответствующий операторный фрейм присваивается переменной cargo, ассоциированной с данной нитью (менеджер нитей для каждой нити поддерживает атрибут cargo типа void*). Это необходимо для того, чтобы в теле нити и в теле факторфункции в процессе их выполнения можно было бы через данный атрибут получить доступ к значению любого атрибута (слота) соответствующего операторного фрейма. Сразу после своего запуска нить проверяет значение указателя на левого сына своего операторного фрейма. Если данный указатель не пуст, то запускается нить, соответствующая левому сыну, и переменной cargo, ассоциированной с этой нитью, присваивается указатель на левого сына. Аналогичные действия выполняются для правого сына. Таким образом, рекурсивно, будут запущены нити для всех узлов дерева запроса. Причем иерархия нитей будет в точности соответствовать иерархии операторных фреймов.

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

Поток является обобщением понятия склада и действует как виртуальный FIFO-файл. Исполнитель запросов системы Омега поддерживает потоки следующих предопределенных типов: хранимый файл; временный файл; канал кондуктора; канал маршрутизатора; склад.

Подробнее концепция потоков будет рассмотрена в следующей главе.

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

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

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

Пример использования оператора для распараллеливания запроса приведен на Рис. 18. Здесь изображен физический план выполнения запроса, реализующего соединение двух отношений R и Q по некоторому общему атрибуту. Мы предполагаем, что отношение Q фрагментировано по атрибуту соединения с помощью некоторой функции h, а отношение R фрагментировано по некоторому другому атрибуту, не являющемуся атрибутом соединения. В данном контексте для распараллеливания операции соединения необходимо вставить в дерево запроса один оператор между оператором чтения scan R и оператором соединения join.

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

2.4. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ К ГЛАВЕ В данной главе были детально рассмотрены основные концепции, используемые при проектировании исполнителя запросов. Были рассмотрены и проанализированы основные проблемы, связанные с эффективностью, синхронизацией выполнения операций в дереве запроса и параллелизацией запросов.

Дан обзор известных моделей синхронизации операций в дереве запроса. Были рассмотрены способы параллелизации запросов.

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

синхронизации и параллелизации запросов, названная потоковой.

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

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

ГЛАВА 3. ПОТОКОВАЯ МОДЕЛЬ

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

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

1) обмены между операциями, выполняющимися на одном процессоре;

процессорах внутри одного кластера;

3) обмены между операциями, выполняющимися в разных кластерах;

4) обмены между операциями и диском.

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

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

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

Поток представляет собой реализацию фрагмента отношения на уровне физической алгебры. Потоки являются аргументами и результатами операций физической алгебры, то есть входными и выходными данными узлов дерева запроса. Логически поток представляет собой виртуальный файл типа FIFO. Его можно создавать (метод New), уничтожать (метод Delete), открывать (метод Open), закрывать (метод Close), устанавливать в начальное состояние (метод Reset). В поток можно помещать (записывать) записи (метод Write) и из потока можно извлекать (считывать) записи (метод Read) по правилу FIFO (первым записан, - первым считан).

В исполнителе запросов системы Омега имеются следующие типы потоков: «Склад», «Файл», «Временный файл», «Канал кондуктора» и «Канал маршрутизатора». Для каждого из стандартных классов система предоставляет готовую реализацию методов New, Delete, Open, Close, Reset, Write и Read. Кроме этого, пользователь может определять дополнительные классы потоков, но в этом случае реализацию данных методов он должен указывать явно.

Приведенная концепция обмена данными между узлами дерева запроса реализована в исполнителе запросов классом Stream.

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

• идентификатор виртуального файла;

• указатели на функции обращения к потокам.

абстрактных объектов типа "Поток" и сервисные функции, реализующие конкретные типы потоков и доступ к ним.

В число базовых функций входит функция доступа к атрибутам потока. Базовые функции добавления и удаления экземпляра класса Stream выполняют указанное действие в массиве дескрипторов потоков.

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

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

К сервисным функциям относятся следующие функции:

• установить поток в начальное состояние;

• проверить завершение обмена в потоке;

• вернуть количество гранул в потоке.

Операции чтения и записи для потоков всех типов являются асинхронными и запускаются как отдельные нити. (Такой режим обращения к потоку актуален для всех типов потоков, кроме типа «Склад», но для сохранения общности чтение/запись в склад также оформлены как асинхронные функции). Как следствие, завершение обмена в потоке необходимо пользователю проверять самостоятельно посредством специальной функции th_test, определяющей, завершена работа нити или нет.

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

Рассмотрим подробнее реализацию каждого из типов потоков.

хранимый файл. Это означает, что перед созданием и использованием потока соответствующий файл должен быть открыт в нужном режиме ("только чтение", если применительно к данному потоку не допускается запись, или "чтение и запись", если запись в поток допускается). Операции открытия, закрытия и установки потока «Файл» не влияют на состояние хранимого файла, соответствующие действия выполняются над файловым итератором: при открытии потока он создается, при закрытии – уничтожается, при установке указатель итератора устанавливается перед первой записью файла. Операция чтения записей файла также реализуется с помощью действий над итератором: указатель текущей записи передвигается на следующую позицию и возвращается в функцию в качестве результата. Таким образом, потоки типа «Файл» допускают повторное использование данных.

Представлением потока «Временный файл» является временный файл. Он создается и уничтожается вместе с соответствующим потоком.

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

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

Представлением потока типа «Канал маршрутизатора» является канал Омега-маршрутизатора. Механизм его работы аналогичен каналу кондуктора.

Потоки типа «Склад». В системе Омега склад является основным видом потоков, используемых для представления деревьев запросов.

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

На Рис. 19 приведена схема обращения процессов к складу. Нить Т (поставщик) поэлементно записывает свои выходные данные в конец склада («хвост» очереди), нить Т2 (потребитель) по мере надобности забирает по одному элементу с начала склада (из «головы» очереди). При этом обход выделенной области памяти осуществляется по кругу. Память под экземпляры класса выделяется динамически.

Информация о складе содержится в его дескрипторе. Дескриптор включает в себя следующие поля:

• максимальное количество элементов в складе;

• адрес блока памяти выделенного под склад;

• указатели на текущую «голову» склада;

• указатели на текущий «хвост» склада.

Дескрипторы объектов хранятся в статической таблице.

Интерфейс класса Stock включает в себя следующие функции:

1) создание и удаление экземпляра класса;

2) очистка склада;

3) добавление элементов;

4) удаление элемента из склада;

5) вычисление коэффициента заполнения склада.

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

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

не допускают повторного использования данных.

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

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

1) указатель на функцию тела нити, реализующей соответствующую операцию физической алгебры;

2) указатель на фактор-функцию нити;

3) указатель на выходной поток;

4) указатель на левого сына (может быть пустым);

5) указатель на правого сына (может быть пустым);

6) тип нити (конъюнктивная или дизъюнктивная).