WWW.KN.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные ресурсы
 

Pages:   || 2 |

«РАЗРАБОТКА МОДЕЛЕЙ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ЗАПРОСОВ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ ...»

-- [ Страница 1 ] --

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

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

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

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

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

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

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

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

Данная цель предполагает решение следующих задач:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Коэффициент ускорения показывает, как изменяется производительность системы при наращивании аппаратной мощности, и определяется следующим образом. Для некоторой задачи определяется время выполнения на исходной заданной конфигурации многопроцессорной системы. Затем система масштабируется в n раз и вычисляется коэффициент изменения времени выполнения, m определяемый как отношение времени выполнения задачи на масштабированной конфигурации ко времени выполнения на исходной системе. Коэффициентом ускорения называют отношение 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).

–  –  –

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

M M M

–  –  –

SD архитектура, по сравнению с SE архитектурой, демонстрирует лучшую масштабируемость и более высокую степень доступности данных при отказах аппаратуры. архитектуры позволяют достичь SD удовлетворительной балансировки загрузки, поскольку каждому процессору доступны все диски. Однако при реализации 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].

N

–  –  –

Рис. 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-кластеры соединяются между собой с помощью высокоскоростной соединительной сети обладает хорошей N. CE-архитектура масштабируемостью подобно SN-архитектуре, и позволяет достигать приемлемого баланса загрузки подобно SE-архитектуре.

–  –  –

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

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

N

–  –  –

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

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

На втором уровне иерархии SM2 модули объединяются в SD2 кластеры. Каждый 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-машину, представляющую собой обычный персональный компьютер или рабочую станцию.

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

В качестве вычислительного процессора в ТПМ для МВС-1000 используется процессор 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 SCSI

–  –  –

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

Основные системные компоненты, образующие ядро прототипа параллельной СУБД Омега, изображены на Рис. 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].

Запрос на языке манипулирования данными

–  –  –

Работа компилятора языка запроса состоит из трех этапов [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]. Следует отметить, что степень конвейерного параллелизма в любом случае ограничена количеством операций, вовлекаемых в конвейер. При этом для реляционных систем баз данных длина конвейера редко превышает 10 операций [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] были определены два основных фактора, влияющие на эффективность распараллеливания: стохастическая природа времени выполнения реляционных операций (перекос выполнения) и перекосы в распределении значений атрибутов соединения (перекос данных). Исполнитель запросов должен иметь возможность автоматически корректировать загрузку процессоров при возникновении таких ситуаций.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

итератор open next close Операция

–  –  –

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

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

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

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

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

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

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

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

read Op1

–  –  –

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

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

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

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

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

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

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

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

output

–  –  –

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

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

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

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

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

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

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

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

Print

–  –  –

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

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

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

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

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

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

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

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

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

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

В системе Омега каждая операция дерева запроса представляется в виде отдельного легковесного процесса (нити). Для синхронизации процессов мы используем некоторый компромисс между описанными моделями синхронизации. Как и в модели, основанной на передаче сообщений, операции начинают выполняться, не дожидаясь требования на свои выходные данные. Операция-поставщик, выполняясь, помещает свои результаты в буфер обмена с операцией-поставщиком, который мы назвали складом [75]. Поставщик, по мере надобности, извлекает данные из склада. Пример такой синхронизация операций в дереве запроса приведен на Рис. 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, 1) если fi(t) = 1.

Дизъюнктивная нить Ti находится в заблокированном 2) k f ij (t ) = 0.

состоянии в момент времени t, если Конъюнктивная j =1 нить Ti находится в заблокированном состоянии в момент времени t, k f ij (t ) = 0.

если j =1 Нить Ti готова к работе, если она не простаивает и не 3) заблокирована.

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

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

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

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

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

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

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

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

Каждые m циклов диспетчеризации счетчики всех нитей 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. Пример использования оператора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждый экземпляр класса Stream имеет следующие атрибуты:

• тип потока;

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

• размер элемента в байтах;

• указатель на рабочий буфер;

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

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

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

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

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

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

• открыть поток;

• закрыть поток;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

–  –  –

Информация о складе содержится в его дескрипторе.

Дескриптор включает в себя следующие поля:

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

• длина элемента;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример фрагмента физического плана запроса, построенного на основе операторных фреймов, изображен на Рис. 20. Данный запрос вычисляет отношение S = PR ( R ) PQ (Q).

PRODUCT

–  –  –

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

3.3. Структура ОПЕРАТОРА Для реализации внутриоперационного (горизонтального) параллелизма в системе Омега используется специальный оператор [19].

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

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

Реализация оператора изображена на Рис. 21. оператор является составным оператором и включает в себя четыре оператора: gather, scatter, split и merge. Все указанные операторы реализуются на базе общего операторного фрейма, описанного в разделе 3.2.

–  –  –

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

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

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

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

Считанные гранулы помещаются в выходной поток (склад) оператора При переполнении склада процесс чтения гранул gather.

приостанавливается.

Оператор merge определяется как дизъюнктивный бинарный оператор, который забирает гранулы из выходных потоков (складов) своих сыновей и помещает их в собственный выходной поток (склад).

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

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

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

В качестве запросов мы использовали мультисоединения, представленные в виде левонаправленных деревьев, подобных дереву, изображенному на Рис. 22.

–  –  –

Здесь join обозначает операцию соединения по некоторому общему атрибуту, store - операцию записи результирующего отношения на диск.

Мы использовали деревья с максимальной глубиной (количеством операций join), равной трем. В контексте Рис. 22 мы предполагаем, что внешнее отношение R имеет три атрибута: a1, a2, a3. Атрибут a1 является атрибутом соединения для внутреннего отношения Q1, атрибут a2 является атрибутом соединения для внутреннего отношения Q2, атрибут a3 является атрибутом соединения для внутреннего отношения Q3.

Основные системные параметры приведены в Табл. 1. Процессорные модули МВС в нашей конфигурации разделены на два Омега- кластера с топологией типа А (см. Рис. 7). Каждый кластер состоит из четырех процессорных модулей и имеет четыре диска. Максимальная длина кратчайшего пути между процессорными модулями кластера равна двум.

–  –  –

Здесь - размер результата соединения, size_of_the_join_result size_of_the_source_relation - размер левого исходного (промежуточного) отношения в дереве запроса.

Мы предполагаем, что все операции join в дереве запроса имеют один и тот же фактор селективности.

Важным параметром базы данных является параметр VCF(R.ai), вычисляемый как отношение V/|R|, где |R| - размер отношения R, V количество различных значений в столбце ai отношения R. В наших экспериментах мы предполагали, что все атрибуты отношения R имеют одинаковое значение параметра VCF.

Фактором, который может существенным образом снизить эффективность распараллеливания реляционных операций, особенно соединения и сортировки, является величина перекоса, присутствующая в данных, подлежащих обработке. Исследования показали, что в реальных базах данных некоторые значения для определенного атрибута встречаются значительно чаще, чем остальные [46, 77, 80]. В частности, Линч (Lynch) отмечает в [77], что для текстовых атрибутов характерно распределение значений по закону Зипфа [117]. Подобная неоднородность называется перекосом значений атрибута [113]. Лакшми (Lakshmi) и Ю (Yu) показали [71], что при наличии перекоса данных ускорение, достигаемое при параллельным выполнении операций соединения, может быть ограничено катастрофическим образом по причине перегрузки одних процессоров и недогрузки других.

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

В соответствие с этим законом вероятность встретить N значений атрибута определятся следующим образом:

p1 = c/1, p2 = c/2,..., pN = c/N, где c = 1/HN, HN - гармоническое число.

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

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

Результаты данного эксперимента изображены на Рис. 23. Здесь Z обозначает Зипфово распределение, обозначает равномерное U распределение. В числителе указан закон распределения для атрибутов отношения R, в знаменателе - закон распределения для атрибутов отношений Qi (i=1,2,3). Результаты данного эксперимента показывают, что по сравнению с традиционной итераторной моделью потоковая модель может значительно (на 30-40%) повысить эффективность выполнения мультисоединений при неравномерном распределении значений атрибутов соединения. При этом максимальный эффект достигается при длине склада, составляющей 20-30 гранул.

–  –  –

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

Результаты второго эксперимента изображены на Рис. 24. В данном эксперименте мы исследовали эффективность потоковой модели при различных значениях параметра Как показали результаты VCF.

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

–  –  –

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

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

В последнем эксперименте мы исследовали производительность Омега-кластера в сравнении с производительностью SE кластера. Для этого мы выполнили на МВС эмуляцию 4-процессорного кластера с SE архитектурой путем использования некоторого идеального распределения для генерации значений атрибутов отношений R и Qi.

100%

–  –  –

80% 70% 60%

–  –  –

Рис. 26. Производительность Омега-кластера относительно производительности SE кластера (взята за 100%) для планов различной глубины.

При выполнении мультисоединения данное идеальное распределение исключало какие-либо задержки, связанные с получением требуемого элемента данных в любом узле дерева запроса в любое время на всех процессорах кластера. Результаты данного эксперимента изображены на Рис. 26. Здесь приведена приведена относительная производительность Омега-кластера при выполнении мультисоединений различной глубины. Цифра 100% соответствует времени выполнения соответствующего мультисоединения на SE кластере с тем же количеством процессоров, что и у Омега-кластера. Результаты данного эксперимента показывают, что использование потоковой модели может значительно повысить производительность Омега-кластера. При длине склада, равной 32, производительность Омега-кластера при выполнении мультисоединений составляет около 80% от производительности SE кластера.

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

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

3.5. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ К ГЛАВЕ 3 В данной главе были детально рассмотрены концепции, предложенные нами для реализации описанной в предыдущей главе потоковой модели. Рассмотрена концепция потоков, разработанная нами для унификации интерфейса передачи данных в параллельной системе баз данных Омега, подробно описаны все используемые виды потоков.

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

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

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

ГЛАВА 4. Принципы реализации исполнителя запросов системы Омега В данной главе мы описываем подходы, использованные для реализации исполнителя запросов системы Омега.

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

4.1. Структура исполнителя запросов Иерархия модулей и классов исполнителя изображена на Рис. 27.

–  –  –

Класс Stock реализует абстрактный тип "Склад", необходимый для реализации потоковой модели. Класс Stream реализует абстрактный тип "Поток данных", обобщающий все имеющиеся типы источников данных.

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

Рассмотрим реализацию перечисленных компонент исполнителя запросов более подробно 1.1.9 4.1.1. КЛАСС STOCK Экземпляры класса Stock имеют структуру очереди. В склад можно помещать элементы (widgets), представляющие собой байтовые строки фиксированной длины. Интерфейс класса Stock изображен на Рис. 28.

Экспортируемые методы:

/* Создание экземпляра класса Stock */ stock_t /* =0 - идентификатор склада, иначе - код ошибки */ stock_new(int widgetLen /* размер элемента в байтах */, int stockLen /* максимальное количество элементов в складе */);

/* Удаление экземпляра класса Stock */ int /* =0 - OK, иначе - код ошибки */ stock_release(stock_t /* идентификатор склада */);

/* Данная функция удаляет указанный экземпляр класса Stock из таблицы экземпляров класса и освобождает всю связанную с ним память. */ /* Установка склада */ int /* =0 - ОК, иначе - код ошибки */ stream_reset(stock_t /* идентификатор склада */, int stockLen /* максимальное количество элементов в складе */);

/* Данная функция удаляет из склада элементы и устанавливает новый размер склада. */ /* Добавление элемента в склад */ char* /* указатель на старый хвост очереди, представляющей указанный склад */ stock_accept(stock_t /* идентификатор склада */);

/* Данная функция увеличивает значение указателя "хвост" на длину одного элемента.

Если свободное пространство отсутствует до начала выполнения данной операции, никаких действий не производится. */ /* Удаление элемента из склада */ char* /* указатель на старую голову очереди, представляющей указанный склад */ stock_eject(stock_t /* идентификатор склада */);

/* Данная функция увеличивает значение указателя "голова" на длину одного элемента.

Если очередь была пуста к моменту выполнения данной операции, никаких действий не производится. */ /* Вычислить коэффициент заполнения склада */ int stock_factor(stock_t /* идентификатор склада */);

–  –  –

Память для склада выделяется динамически (с помощью функции malloc) при его создании (функция stock_new). Память, выделенная для склада, освобождается динамически (с помощью функции free) при уничтожении объекта (функция stock_release).

–  –  –

Класс Stream предоставляет методы для создания абстрактных объектов типа "Поток". Каждый экземпляр (объект) класса Stream имеет набор экспортируемых атрибутов (свойств), изображенных на Рис. 29. В общем случае, после создания нового объекта класса Stream пользователь должен присвоить экспортируемым атрибутам конкретные значения.

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

Экспортируемые атрибуты:

typedef struct{ int vFile; /* идентификатор виртуального файла */ int widgetLen;/* размер элемента в байтах */ int rep; /* представление - representation */ char* buf; /* указатель на рабочий буфер */ stream_openF_t openF;/* Указатель на функцию открытия потока */ stream_closeF_t closeF;/* Указатель на функцию закрытия потока */ stream_resetF_t resetF;/* Указатель на функцию установки потока в начальное состояние */ stream_readF_t readF; /* Указатель на функцию чтения из потока */ stream_writeF_t writeF; /* Указатель на функцию записи в поток */ stream_writeEodF_t writeEodF; /* Указатель на функцию записи в поток признака конца данных */ stream_factorF_t factorF; /* Указатель на функцию вычисления коэффициента заполнения потока*/ } stream_a_t;

Рис. 29. Экспортируемые атрибуты объекта класса Stream.

Интерфейс класса Stream в сокращенном виде изображен на Рис. 30.

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

ЭКСПОРТИРУЕМЫЕ МЕТОДЫ I: БАЗОВЫЕ ФУНКЦИИ

/* Создание экземпляра класса Stream */ stream_t /* =0 - идентификатор потока, иначе - код ошибки */ stream_new(int vFile /* идентификатор источника данных */);

/* Удаление экземпляра класса Stream */ int /* =0 - OK, иначе - код ошибки */ stream_release(stream_t /* идентификатор потока */);

/* Данная функция удаляет указанный экземпляр класса Stream из таблицы экземпляров класса и освобождает всю связанную с ним память. */ /* Доступ к атрибутам экземпляра класса Stream */ stream_a_t* stream_a(stream_t /* идентификатор потока */);

/* Данная функция возвращает указатель на структуру(struct), содержащую в качестве компонентов атрибуты указанного потока. */

ЭКСПОРТИРУЕМЫЕ МЕТОДЫ II: СЕРВИСНЫЕ ФУНКЦИИ

/* Создание потока типа Fl (File) */ stream_t /* =0 - идентификатор потока, иначе - код ошибки */ stream_newFl(int /* идентификатор файла */);

/* Прежде чем в поток типа Fl будет производиться запись (чтение) соответствующий файл должен быть открыт для записи (чтения). */ /* Создание потока типа Cn (Conductor channel) */ stream_t /* =0 - идентификатор потока, иначе - код ошибки */ stream_newCn(int /* № узла кластера */, int /* № порта */, int /* длина элемента */);

/* Создание потока типа Rt (Router channel) */ stream_t /* =0 - идентификатор потока, иначе - код ошибки */ stream_newRt(int /* № кластера */, int /* № порта */, int /* длина элемента */);

/* Создание потока типа St (Stock) */ stream_t /* =0 - идентификатор потока, иначе - код ошибки */ stream_newSt(int /* длина элемента */, int /* длина склада*/);

/* Создание потока типа Tf (Temporary file) */ stream_t /* =0 - идентификатор потока, иначе - код ошибки */ stream_newFt(int /* длина записи (включая дескриптор) */);

/* Открытие потока */ int /* =0 - OK, иначе - код ошибки */ stream_open(stream_t /* идентификатор потока */);

/* Закрытие потока */ int /* =0 - ОК, иначе - код ошибки */ stream_close(stream_t /* идентификатор потока */);

/* Установка потока */ int /* =0 - ОК, иначе - код ошибки */ stream_reset(stream_t /* идентификатор потока */);

/* Чтение из потока */ int /* =TH_TERMINATE, если чтение завершено, TH_CONTINUE – в противном случае */ stream_read(void* param);

/* Записать в поток */ int /* =TH_TERMINATE, если запись завершена, TH_CONTINUE – в противном случае */ stream_write(void* param);

/* Записать в поток признак конца данных */ int /* =TH_TERMINATE, если запись завершена, TH_CONTINUE – в противном случае */ stream_writeEod(void* param);

/* Вычислить коэффициент заполнения потока */ int stream_factor(stream_t /* идентификатор потока */);

/* Проверка конца данных */ int /* =1, если в потоке – конец данных,=0 - иначе */ stream_eod(stream_t /* идентификатор потока */);

Рис. 30. Интерфейс класса Stream.

4.1.3. КЛАСС TREE 1.1.11 Класс Tree реализует абстрактный тип "Дерево запроса". Класс Tree не поддерживает дисциплину скобочной модели. В Tree-деревьях не предопределяются потоковые связи между узлами. Это означает, что выходной поток сына не обязан являться входным потоком отца, как это имеет место в скобочной модели.

Интерфейс класса Tree изображен на Рис. 31.

–  –  –

/* Тип объектов класса Tree (указатель на корень) */ typedef tree_node_t* tree_t;

/* Указатель на функцию обработки узла */ typedef void (*tree_actionF_t)(tree_t);

Экспортируемые методы :

/* Создать узел */ tree_node_t* /* != NULL - указатель на узел, иначе - ошибка */ tree_createNode(void);

/* Обход дерева */ void tree_traversal( tree_t /* указатель на корень */;

tree_actionF_t /* указатель на функцию обработки узла */);

/* Данная функция выполняет указанную операцию для всех узлов дерева запроса посредством рекурсивных вызовов себя самой */ /* Уничтожить дерево */ void tree_destroy(tree_t);

/* Данная функция освобождает всю память, занятую узлами указанного дерева */

–  –  –

4.1.4. МОДУЛЬ ИНТЕРПРЕТАТОРА ОПЕРАЦИЙ ФИЗИЧЕСКОЙ 1.1.12 АЛГЕБРЫ Модуль интерпретатора операций физической алгебры описывает структуру и типы параметров операций с различными кодами и предоставляет процедуры реализации операций. Интерфейс модуля интерпретатора операций физической алгебры изображен на Рис. 32

–  –  –

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

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

4.1.5. МОДУЛЬ ИСПОЛНИТЕЛЯ ЗАПРОСОВ 1.1.13 Модуль исполнителя реализует концепцию параллелизации запросов, описанную в разделе 2.3, и предоставляет методы создания, исполнения и уничтожения деревьев физических запросов. Интерфейс модуля исполнителя запросов изображен на Рис. 33

ЭКСПОРТИРУЕМЫЕ МЕТОДЫ I: БАЗОВЫЕ ФУНКЦИИ

/* Создание корня дерева запроса (query tree) */ en_qt_t /* указатель на корень */ en_qtMakeRoot( /* КОП (Код Операции) */ int, /* параметры операции */ void*, /* nice - приятность процесса (антиприоритет) */ int, /* выходной поток */ stream_t, /* указатель на левое поддерево */ en_qt_t, /* указатель на правое поддерево */ en_qt_t );

/* Создание внутреннего узла */ en_qt_t /* указатель на созданный узел */ en_qtMakeNode( /* КОП (Код Операции) */ int, /* параметры операции */ void*, /* nice - приятность процесса (антиприоритет) */ int, /* тип выходного потока */ int, /* указатель на левое поддерево */ en_qt_t, /* указатель на правое поддерево */ en_qt_t );

/* Создание листа */ en_qt_t /* указатель на лист */ en_qtMakeLeaf( /* КОП (Код Операции) */ int, /* параметры операции */ void*, /* nice - приятность процесса (антиприоритет) */ int, /* тип выходного потока */ int, /* входной поток A */ stream_t, /* входной поток B */ stream_t );

/* Открыть потоки в дереве */ void en_qtOpenStreams(en_qt_t /* указатель на корень */);



Pages:   || 2 |
Похожие работы:

«ТЕПЛОВЫЧИСЛИТЕЛЬ ВЗЛЕТ ТСРВ ИСПОЛНЕНИЕ ТСРВ-043 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ Часть I В84.00-00.00 РЭ Россия, Санкт-Петербург В84.00-00.00-43 Система менеджмента качества АО "Взлет" сертифицирована на соответствие ГОСТ ISO 9001-2011 (ISO 9001:2008) А...»

«Буртелов Лев Вадимович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССА ЭКСТРУЗИИ ПСЕВДОПЛАСТИЧНЫХ СРЕД НА ОДНОЧЕРВЯЧНЫХ МАШИНАХ НА ПРИМЕРЕ РЕЗИНОВОЙ СМЕСИ Специальность 05.17.08 — Процессы и аппараты химических технологий 05.13.18 — Математическое...»

«УДК 536.242.2 Э. Г. БРАТУТА, д-р. техн. наук, профессор А. В. ШЕРСТЮК, аспирант Национальный технический университет "Харьковский политехнический институт" МОДЕРНИЗАЦИЯ АММИАЧНОЙ ХОЛОДИЛЬНОЙ МАШИНЫ С Ц...»

«БЮЛЛЕТЕНЬ Обзор новостей за 17 февраля 2009 г. СОДЕРЖАНИЕ ПРИРОДНЫЕ РЕСУРСЫ ТЕЛЕКОММУНИКАЦИИ, ТРАНСПОРТ, СТРОИТЕЛЬСТВО И ИНФРАСТРУКТУРА ПРОМЫШЛЕННОСТЬ И ТОРГОВЛЯ БАНКИ И ФИНАНСЫ РУБРИКИ ПРИРОДНЫЕ РЕСУРСЫ Неверно истолковали Добро пожаловать,...»

«ЧЕРНОСКУТОВ ДМИТРИЙ ВЛАДИМИРОВИЧ ПОВЫШЕНИЕ КОММУТАЦИОННОЙ СПОСОБНОСТИ ВЫСОКОВОЛЬТНОЙ АППАРАТУРЫ 05.09.01 – Электромеханика и электрические аппараты АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Екатери...»

«УДК 621.313.333 А.М. Галиновский, канд. техн. наук (Украина, Киев, НТУУ "Киевский политехнический институт"), Е.А. Ленская (Украина, Киев, Национальное Агентство по энергоэффективности и энергосбережению Украины) МНОГОФАЗНО-ОДНОФАЗНЫЕ РЕВЕРСИВНЫЕ ЭЛЕКТРОМАШИННО-ВЕ...»

«УТВЕРЖДЕНО внеочередным общим собранием акционеров ОАО "ВСЗ" Протокол № 28 от "15" ноября 2012 года ПОЛОЖЕНИЕ ОБ ОБЩЕМ СОБРАНИИ АКЦИОНЕРОВ ОТКРЫТОГО АКЦИОНЕРНОГО ОБЩЕСТВА "ВЫБОРГСКИЙ СУДОСТРОИТЕЛЬНЫЙ ЗАВОД" Ленинградская область, город Выборг Российская Федерация Положение об Общем соб...»

«Строительство коттеджа S=144м2 из газобетонных блоков Комплектация 1 (общестроительные работы) – 63200$ (360$ за 1м2) или эквивалент 512000 грн Комплектация 2 (под финишную отделку) – 92800$ (527$ за 1м2) или эквивалент 751700 грн Площадь помещений: Прихожая: 5,52 Спальня 2: 15,01 С/У: 5,...»

«217 "ВОТ ЗДЕСЬ ВИДНО ВСЕ!": САМОРЕПРЕЗЕНТАЦИЯ ГОРОДСКОГО ОБЩЕСТВЕННОГО ДВИЖЕНИЯ М.М. Закирова В статье представлены результаты социологического исследования городского общественного движения жильцов против застройки тер ритории городского двора ("уплотнительной застрой...»

«УДК 004.415.25 Н.И. Курченков, Н.Н. Дацун Донецкий национальный технический университет, г. Донецк кафедра прикладной математики и информатики nikita.kurchenkov@g mail.co m МОДИФ ИКАЦИЯ АЛГОРИТМА ПОИСКА ПУ ТЕЙ J UMP POINT SEARCH ДЛ Я РОБОТА ROBOTINO Аннотация Курченко...»

«v.1.0 2011 Теплосчетчики ультразвуковые Струмень ТС-07 Руководство по эксплуатации СИФП 80.00.000 РЭ ИСО 9001:2008 СОДЕРЖАНИЕ ВВЕДЕНИЕ 1 НАЗНАЧЕНИЕ И ОБЛАСТЬ ПРИМЕНЕНИЯ 2 ТЕХНИЧЕСКИЕ ХАРАКТЕРИСТИКИ ТЕПЛОСЧЕТЧИКА 3 СХЕМА СОСТАВЛЕНИЯ УСЛОВНОГО ОБ...»

«Техническая карта материала Издание: 11/12/2008, UA_09/2011_AS Идентификационный №: Sika® Ceram-209 Sika® Ceram-209 Высококачественный эластичный клей на основе цемента для тонкослойной укладки к...»

«ПАСПОРТ БЕЗОПАСНОСТИ в соответствии с регламентом (EС) № 1907/2006 (REACH)   Дата обработки: 05.09.2016 Напечатано: 05.09.2016 Версия: 3   Cтраница 1/7 SIHA Желатин мелкозернистый, холодорастворимый, флотационный желатин РАЗДЕЛ 1: Идентификация химической продукции и сведения о производителе или поставщике 1.1. Идентификатор продукта Тор...»

«НАУЧНО-ПРОИЗВОДСТВЕННОЕ ПРЕДПРИЯТИЕ ВЫКЛЮЧАТЕЛЬ ВЫСОКОВОЛЬТНЫЙ ВАКУУМНЫЙ типа ВБУ-35 ТЕХНИЧЕСКОЕ ОПИСАНИЕ И ИНСТРУКЦИЯ ПО ЭКСПЛУАТАЦИИ ИБКЖ.674153.013.ТО СОДЕРЖАНИЕ 1. Введение 2. Назначение 3. Технические данные 4. Состав выключателя 5. Уст...»

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

«Правительство Российской Федерации Нижегородский филиал Федерального государственного автономного образовательного учреждения высшего профессионального образования Национальный исследовательский университет Высшая школа экономики Факультет экономики Программа дисциплины...»

«ОСОБЕННОСТИ ЭВАКУАЦИИ ЛЮДЕЙ ПРИ ПОЖАРЕ С ПРОМЫШЛЕННЫХ СООРУЖЕНИЙ ВЗРЫВОПОЖАРООПАСНЫХ ПРОИЗВОДСТВ Д.О. Бугаевский, Е.А. Апойкова, К.А. Скляров Федеральное государственное образовательное учреждение высшего образования Воронежский государственный арх...»

«ПРОГРАММА "100 ЛУЧШИХ ТОВАРОВ РОССИИ" ЛАУРЕАТЫ 2015 СОДЕРЖАНИЕ 1. НОМИНАЦИЯ "ПРОДОВОЛЬСТВЕННЫЕ ТОВАРЫ" стр. 2 2. НОМИНАЦИЯ "ПРОМЫШЛЕННЫЕ ТОВАРЫ ДЛЯ НАСЕЛЕНИЯ" стр. 20 3. НОМИНАЦИЯ "ПРОДУКЦИЯ ПРОИЗВОДСТВЕННО-ТЕХНИЧЕСКОГО НАЗНАЧЕНИЯ" стр. 27 4. НОМИНАЦИЯ "ИЗДЕЛИЯ НАРОДНЫХ И ХУ...»

«Информация о научной деятельности кафедры автомобильных дорог и аэродромов в 2016 году 1. Адрес: г. Макеевка, ул. Державина, 2, тел. 8(0623) 22-05-45; Е-mail: bratv@yandex.ru 2. Руководитель:...»

«ЗУБКОВ Юрий Юрьевич ДЕФОСФОРАЦИЯ ВЫСОКОЛЕГИРОВАННЫХ РАСПЛАВОВ С ЦЕЛЬЮ ВОВЛЕЧЕНИЯ В ПРОИЗВОДСТВО ОТХОДОВ МЕТАЛЛА И ШЛАКА С ПОВЫШЕННЫМ СОДЕРЖАНИЕМ ФОСФОРА Специальность 05.16.02 – Металлургия черных,...»

«ВЕДОМСТВЕННЫЕ СТРОИТЕЛЬНЫЕ НОРМЫ ПРАВИЛА ПРИЕМКИ В ЭКСПЛУАТАЦИЮ ЗАКОНЧЕННЫХ КАПИТАЛЬНЫМ РЕМОНТОМ ЖИЛЫХ ЗДАНИЙ ВСН 42-85(р) ГОСГРАЖДАНСТРОЙ ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ГРАЖДАНСКОМУ СТРОИТЕЛЬСТВУ И АРХИТЕКТУРЕ ПРИ ГОССТРОЕ СССР Разработаны ЦНИИЭП жилища Госгражданстроя (кандидаты техн. наук...»

«ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Рабочая программа по химии составлена в соответствии с федеральным компонентом государственного стандарта основного общего образования, одобренным совместным решением коллегии Минобразования России и Президиу...»

«Ultima ratio Вестник Академии ДНК-генеалогии Proceedings of the Academy of DNA Genealogy Boston-Moscow-Tsukuba Volume 7, No. 3 March 2014 Академия ДНК-генеалогии Boston-Moscow-Tsukuba ISSN 1942-7484 Вестник Академии ДНК-генеалогии. Научно-публицистическое издание Академии ДНК-генеалогии. Издательство Lulu inc., 2014. Авто...»

«Аудит сайта etsy.com Диагностика сайта Отчёт позволяет оценить общие параметры и характеристики сайта: возраст; тематический индекс цитирования (тИЦ); статический вес главной стран...»

«KERN & Sohn GmbH Тел.: +49-[0]74339933-0 Ziegelei 1 Факс: +49-[0]7433-9933-149 D-72336 Balingen Интернет: www.kern-sohn.com E-mail: info@kern-sohn.com Инструкция по обслуживанию Аналитические весы и прецизионные весы KERN ALJ/ALS/PLJ/PLS Версия 3.7 03...»








 
2017 www.kn.lib-i.ru - «Бесплатная электронная библиотека - различные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.