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

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

СОКОЛИНСКИЙ Леонид Борисович

МЕТОДЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ НА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ

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

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Работа выполнена на кафедре математического обеспечения ЭВМ Челябинского государственного университета.

Официальные оппоненты: академик РАН, доктор физико-математических наук, профессор

ЕРЕМИН Иван Иванович; I

доктор физико-математических наук, профессор КУЗНЕЦОВ Сергей Дмитриевич;

доктор физико-математических наук ВОЕВОДИН Владимир Валентинович.

Ведущая организация: Уральский государственный университет.

Зашита состоится 4 июня 2003 г. в 10 часов

на заседании диссертационного совета Д 212.296.02 при Челябинском государственном университете по адресу: 454021, Челябинск, ул. Бр. Кашириных, 129.

С диссертацией можно ознакомиться в библиотеке Челябинского государственного университета

Автореферат разослан "_"_2003 г. 1

'5

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

Общая характеристика работы

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

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

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

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

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

1. Провести сравнительный анализ различных подходов к классификации архитектур многопроцессорных систем в контексте параллельных СУБД и выработать адекватные методы классификации современных архитектур параллельных систем баз данных.

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

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

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

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

6. Реализовать предложенные методы и алгоритмы в виде прототипа параллельной СУБД Омега на базе отечественного многопроцессорного вычислительного комплекса МВС-100/1000. Используя данный прототип, провести вычислительные эксперименты на тестовых базах данных, подтверждающие эффективность выработанных подходов.

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

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

Научная новизна работы заключается в следующем:

1) предложена новая гибридная иерархическая архитектура (CDi архитектура) для построения высокоэффективных, масштабируемых, отказоустойчивых параллельных систем баз данных;

2) описана оригинальная аппаратная реализация СТЬ архитектуры, базирующаяся на введении специального вида кластеров (Омега-кластеров) с разделяемыми дисками и двухпроцессорными несимметричными модулями с приватной памятью;

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

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

разработан новый эффективный алгоритм замещения страниц в буферном пуле (алгоритм LFU-Jt), ориентированный на использование в параллельных системах баз данных без совместного использования ресурсов;

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

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

на основе СОг архитектуры впервые создан прототип параллельной СУБД Омега для отечественных многопроцессорных вычислительных комплексов серии МВС;

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

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

1) предложенные подходы, методы и алгоритмы могут быть использованы для проектирования и разработки параллельных систем баз данных на базе широкого спектра многопроцессорных систем, начиная от мультипроцессоров с массовым параллелизмом типа МВС-1000 и кончая кластерами типа Beowulf;

2) алгоритм замещения страниц LFU-iST может быть использован для организации эффективной буферизации в различных параллельных системах баз данных без совместного использования ресурсов, а также для кэширования Web-страниц на ргоху-серверах, обслуживающих большое число пользователей WWW;

3) предложенная технология коллективной разработки больших программных систем для многопроцессорного вычислительного комплекса МВС-100 может быть перенесена в среду МВС-1000 и использована для создания сложных программных систем различного назначения.

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

- на IV Международном семинаре по параллельным и распределенным базам данных PaDD'2001 в составе XII Международной конференции по базам данных и экспертным системам DEXA'2001 (Мюнхен, Германия, 3-7 сентября, 2001 г.) при финансовой поддержке РФФИ (грант 01-07-93514);

4)

5)

( 6) ■

7)

8) 9)

- на Ш Восточно-европейской конференции по базам данных и информационным системам - ADBIS'99 (Марибор, Словения, 13-16 сентября 1999 г.) при финансовой поддержке РФФИ (грант 99-07-93023);

- на Международном симпозиуме по базам данных и информационным системам ADBIS'97 (Санкт-Петербург, 2-5 сентября 1997 г.)

- на IV Международной Балтийской конференции IEEE по базам данных и информационным системам - BalticDB&IS'2000 (Вильнюс, Литва, 1-5 мая 2000 г.);

на 3-й Международной конференции по программированию и информационным технологиям CSIT2001 (Уфа, 21 -26 сентября 2001 г.); f

- на 2-й Международной конференции по программированию и информационным технологиям CSITCOOO (Уфа, 18-23 сентября 2000 г.);

- на 1-й Международной конференции по программированию и информационным .1 технологиям CSIT99 (Москва, 18-22 января 1999 г.);

на Международном семинаре "Методы прикладной математики и информационные технологии в многодисциплинарных исследованиях и проектах" (Омск, 6-8 октября 1998 г.);

- на Международной конференции "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" -DSO'2000 (Екатеринбург, 30 мая - 2 июня 2000 г.);

- на Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (Черноголовка, 30 октября - 2 ноября 2000 г.);

- на Всероссийской научной конференции "Научный сервис в сети Internet" (Новороссийск, 20-25 сентября 1999 г.);

- на Всероссийской научной конференции "Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов" (Новороссийск, 21-26 сентября 1998 г.).

Публикации. По тематике, связанной с диссертацией, автором опубликовано 36 печатных работ, в том числе приведенные в конце автореферата работы [1-20].

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения и библиографии. Объем диссертации составляет 247 страниц, объем библиографии - 246 наименований.

Содержание работы

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

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

SN

SN

SD

SD

Рис. 1. Гибридная архитектура СОЛ' (Р обозначает процессор, М - модуль оперативной памяти, О - дисковое устройство, N - соединительную сеть).

гибридная иерархическая архитектура CDN (см. Рис. 1), которая строится как объединение кластеров с физическим разделением дисков (Ж), представляющих собой на виртуальном уровне системы без совместного использования ресурсов (SN).

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

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

невую иерархическую архитектуру. Первый уровень иерархии представлен несимметричными двухпроцессорными модулями 5Мг с разделяемой памятью. Каждый модуль включает в себя вычислительный и коммуникационный процессоры, взаимодействующие через разделяемую память. Вычислительный процессор используется для выполнения всех процессов базы данных. Коммуникационный процессор используется главным образом для организации обменов сообщениями по соединительной сети. Подобный подход позволяет освободить вычислительный процессор от накладных расходов, связанных с организацией обменов сообщениями, которые могут быть очень существенными. На втором уровне иерархии БМг модули объединяются в Ж>2 кластеры. Каждый Ж>2 кластер включает в себя столько же дисков, сколько в нем 5М} модулей. Указанное свойство обусловлено требованиями СОИ архитектуры. На физическом уровне каждый процессорный модуль имеет доступ к любому диску по общей шине. На третьем уровне иерархии 5Дг кластеры объединяются в единую СДг систему по принципу Для объединения используется некоторая высокоскоростная соединительная сеть N.

На логическом уровне система Омега представляет собой виртуальную машину баз данных с С£> архитектурой, в которой виртуальные процессор и мо-

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

На виртуальном уровне система омега может быть представлена в виде виртуальной параллельной машины баз данных с архитектурой, которую мы обозначим как СИ (С1и$1егес1-ИоМп£). CN архитектура - это двухуровневая иерархическая архитектура, получаемая объединением вН кластеров с помощью глобальной соединительной сети. СИ архитектура не тождественна ЯН архитектуре, так как SN кластер может иметь топологию соединительной сети, отличную от топологии межкластерных соединений, вследствие

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

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

Второй уровень иерархии представлен Омега-кластерами. Все Омега-кластеры имеют стандартную предопределенную архитектуру с небольшим количеством процессорных модулей и дисковой подсистемой, объединенными в единую сеть с высокой степенью связности (длина кратчайшего пути между любыми двумя узлами сети не должна превышать значения 2). Модуль дисковой подсистемы имеет свой коммуникационный процессор, сопряженный с SCSI шиной, к которой может быть подключено до семи дисковых накопителей. Каждый кластер имеет свободные линки для связи с другими кластерами. Примеры возможных конфигураций Омега-кластеров приведены на Рис. 2. Здесь UPM (Uniform Processor Module) - типовой процессорный модуль; DSM (Disk Subsystem Module) - модуль дисковой подсистемы. Конфигурация А предполагает использование ТПМ с четырьмя внешними каналами. Конфигурация В предполагает использование ТПМ с шестью внешними каналами. Использование двух дисковых подсистем в конфигурации В позволяет повысить отказоустойчивость кластера.

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

UPM

UPM

DSM

Г3 to

UPM

UPM

А В

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

Во второй главе, "Методы построения операционного ядра системы Омега",

рассматриваются методы создания операционного ядра системы Омега, которое учитывало бы в полной мере специфику архитектуры CD-i и предоставляло бы необходимые СУБД системные сервисы с эффективной реализацией. В начале главы дается обзор общесистемного программного обеспечения, поставляемого с МВС. Затем описывается общая структура операционного ядра системы Омега. Далее рассматриваются методы управления легковесными процессами и предлагается новая модель организации легковесных процессов, базирующаяся на парадигме "производитель-потребитель" и использую' щая механизм "управление посредством потоков данных". В данной модели процессы ассоциируются с потоками данных и являются средством структуризации программы. По-I токовая модель позволяет обеспечить автоматическую синхронизацию и эффективную диспетчеризацию параллельных процессов. В модели предлагается концепция кванта времени, не зависящая от наличия аппаратного прерывания по таймеру, т В соответствие с потоковой моделью каждый процесс имеет корневую нить, представляющую сам этот процесс. Корневая нить может явно породить произвольное число нитей. Каждая из порожденных нитей может породить свое множество подчиненных нитей. Таким образом, нити процесса образуют иерархию. Считается, что каждая нить "производит" и "поставляет" для породившей ее нити (вверх по иерархии) некоторые объекты данных определенной структуры. При этом она сама "потребляет" некоторые объекты данных определенной структуры, поставляемые подчиненными ей нитями. Для _ организации процесса поставки-потребления с каждой нитью связывается буфер вывода, называемый складом. Функционально данный буфер имеет структуру очереди. Нить-поставщик "складывает" в свой склад производимые ею объекты, а породившая ее нить-потребитель "забирает" эти объекты из ее склада. Каждый раз после помещения очередного объекта в склад нить обязана передать управление менеджеру нитей путем системного вызова функции диспетчеризации schedule. Таким образом, единицей квантования времени является создание одного объекта внутри некоторой нити.

Понятие склада является в определенном смысле некоторой метафорой, призванной облегчить понимание механизма синхронизации нитей в потоковой модели. Данный механизм формализуется в понятии Т-фактора, который можно определить следующим образом. Определим г, как меру заполнения склада нити Т„ 0<т,<1 для всех /. Назовем данную меру Т-фактором нити Г,. Значение г, = 1 соответствует полному заполнению склада нити Г/. Значение г, = О соответствует ситуации, когда склад нити Т, пуст. Определим фактор-функцию Дг) нити 7} как вещественную функцию, вычисляющую значение Т-фактора нити 7} в момент времени t.

Пусть нити Г;/, Т,2, ..., Т,к являются производителями данных для нити Т„ Нить Т) будем называть дизъюнктивной, если для ее работы достаточно, чтобы хотя бы один из складов подчиненных нитей Г,,, Т,2, . . ., Тл был не пуст. Нить 7) будем называть конъюнктивной, если для ее работы необходимо, чтобы все склады подчиненных нитей T,i, . Т,2, ■ ■ ., T,ic были не пусты. Мы будем говорить, что дерево нитей некоторого процесса

' находится в нормальной форме, если все входящие в него нити являются либо дизъюнк-

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

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

a) Нить Т, находится в состоянии простоя в момент времени I, если fff) = 1.

b) Дизъюнктивная нить Т, находится в заблокированном состоянии в момент времени

к

'.если £/„(*) = 0.

1

c) Конъюнктивная нить Т, находится в заблокированном состоянии в момент време-

k

ни t, если П/,(') = 0.

1-1

d) Нить Т, готова к работе, если она не простаивает и не заблокирована.

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

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

Для определения формулы динамического приоритета введем следующие параметры. Пусть с каждой нитью связан счетчик С. Данный счетчик увеличивается на единицу всякий раз, когда нить получает управление. Каждые т циклов диспетчеризации счетчики С всех нитей пересчитываются по формуле С := С* к, где к некоторое фиксированное значение, 0 < к< 1. Пусть г задает значение Т-фактора текущей нити. Пусть dprty обозначает значение динамического приоритета. Тогда формулу вычисления динамического приоритета пользовательской нити можно определить следующим образом:

dprty = -(К*С + N*t+ thresholdnice + nice). Здесь К и N некоторые нормализующие константы, которые наряду с т и к являются настраиваемыми параметрами менеджера нитей. Параметр thresholdjuce задает положительное значение порога приятности для пользовательских нитей. Для системных нитей используется формула вычисления динамического приоритета, в которой этот параметр опущен.

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

Клиентская часть системы хранения реализуется в виде иерархии двух подсистем: системы управления файлами и драйвера дисковой подсистемы. Система управления файлами (СУФ) поддерживает представление данных в виде файлов. Файл - это последовательный набор записей одинаковой длины. Файл реализуется как набор страниц диска.

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

' Серверная часть системы хранения запускается на узле-сервере и обрабатывает

► запросы клиентских частей на чтение-запись данных, хранящихся на дисках. Сервер сис-

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

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

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

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

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

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

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

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

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

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

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

• избыточный индекс буферного пула DIR;

• .функция вычисления динамического рейтинга;

• функция вычисления рейтинга;

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

• алгоритм работы диспетчера страниц.

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

1) поиск страниц в буферном пуле;

2) хранение статистической информации об использованных страницах.

В соответствие с этим DIR имеет двойственную природу. С одной стороны, DIR представляет собой обычную хеш-таблицу, индексирующую страницы, хранящиеся в буферном пуле. При обращении к очередной странице диска менеджер буферного пула проверяет наличие ее индекса в DIR. Если индекс указанной страницы в DIR отсутствует, то происходит добавление нового индекса в DIR. Если при этом оказывается, что DIR переполнен, происходит предварительное вытеснение некоторого индекса из DIR. Поиск жертвы осуществляется только среди индексов DIR, соответствующих незагруженным в данный момент в буфер страницам. При этом используются те же рейтинги, что и для буферизованных страниц. С другой стороны, DIR представляет собой информационную таблицу с атрибутами, содержащими различную статистическую информацию об использованных страницах. Примерами подобной статистической информации являются время помещения страницы в буфер, время последнего обращения к странице, общее количество обращений к странице в течение некоторого интервала времени и др. Конкретный набор статистических атрибутов зависит от набора правил вытеснения, встраиваемых в менеджер буферного пула. Избыточность DIR подразумевает, что он может хранить информацию не только о тех страницах, которые в данный момент присутствуют в буферном пуле, но так же и о страницах, которые присутствовали там ранее и были впоследствии из него вытеснены. Оптимальной является ситуация, при которой DIR содержит информацию о всех страницах базы данных, размещенных на данном процессорном узле. 1 Однако и при меньших размерах DIR использование избыточного индекса буферного пула может значительно повысить эффективность работы менеджера буферного пула. Как показали проведенные нами эксперименты, использование DIR, содержащего информа- ! цию о 20-40% страниц базы данных, позволяет увеличить производительность алгоритма замещения страниц на 8-10% при стационарном распределении вероятностей обращения.

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

\

динамических рейтингов. В соответствие с этим методом суммарный рейтинг страницы является неотрицательным вещественным числом из интервала [0;21[ и получается как сумма статического и динамического рейтингов:

•(Суммарный рейтинг> = <Статический рвйтикг> + -(Динамический рейтинг>.

Статический рейтинг - Зто целое число из интервала [0;20]. Статический рейтинг является атрибутом открытого набора страниц. Он может задаваться явно при выполнении операции открытия набора страниц (файла). По умолчанию открытому набору назначается рейтинг, равный 10. Статический рейтинг страницы всегда совпадает с рейтингом набора, которому она принадлежит. Данный рейтинг не меняется на протяжении всего времени работы с открытым набором. Динамический рейтинг - это вещественное неотрицательное число из интервала [0;1[. Динамический рейтинг является атрибутом страницы и сохраняется в ее индексе в DIR. Динамический рейтинг всегда задается менеджером буферного пула неявно путем вычисления функции динамического рейтинга. Непосредственно из определений статического и динамического рейтингов вытекает следующее важное правило идемпотентности статического рейтинга. Если статический рейтинг страницы А больше статического рейтинга страницы В, то суммарный рейтинг страницы А будет всегда больше суммарного рейтинга страницы В вне зависимости от того, какие значения принимают динамические рейтинги этих страниц.

Механизм статического рейтинга позволяет реализовать избирательное вытеснение страниц. Рассмотрим использование статического рейтинга на примере задачи корректного восстановления после сбоя. Страницы, содержащие флаги фиксации, и страницы, на которых записываются планируемые изменения, необходимо разделить в разные наборы. При открытии набора с данными ему присваивается некоторый статический рейтинг. Пусть для определенности значение этого рейтинга будет равным 10. Тогда набору с флагами при открытии необходимо присвоить статический рейтинг, равный 9 (на единицу меньше, чем у набора с данными). А набору, содержащему журнал изменений, необходимо присвоить статический рейтинг, равный 8 (на единицу меньше, чем у набора с флагами). В этом случае, вне зависимости от поведения динамического рейтинга, мы будем иметь следующий порядок вытеснения страниц на диск (следует из правила идемпотентности статического рейтинга):

1) вытеснение страниц журнала изменений;

2) вытеснение страниц с флагами;

3) вытеснение страниц с данными.

Данный порядок шагов 1, 2 и 3 диктуется требованием корректности работы процедуры восстановления после сбоя. При возникновении сбоя на шаге 1 или 2 утилита восстановления удаляет из журнала изменений все записи, для которых не установлен флаг фиксации. При возникновении сбоя на шаге 3 утилита восстановления автоматически повторяет выполнение всех шагов прерванной транзакции, зафиксированных в журнале изменений.

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

• правило вытеснения, ассоциированное с данной страницей;

• значения статистических атрибутов страницы, на которые ссылается правило вытеснения.

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

/* Функция, возвращающая значение динамического рейтинга для страницы г */

If г) . For = "По умолчанию" than

return DIR[г].FC/(FCmax+2) else if DIR[r].FoR = "немедленное вытеснение" then return 0

else if DIR[г].Год - "Удержание" then

return (FCmax+1)/(FCmax+2) else

ошибка: "Неопределенный тип правила вытеснения" end if

Набор

Правило вытеснения FoR (Force Out Rule)

Рис. 3. Алгоритм вычисления функции динамического рейтинга.

Пусть имеется три набора страниц, задействованных в выполнении запроса: А, В и С. Предположим, что страницы набора А просматриваются один раз без повторения. Предположим, что страницы набора В просматриваются в цикле, причем весь цикл можно поместить в буферный пул. Предположим, что страницы набора С просматриваются в соответствии с некоторым статическим распределением вероятностей, например, по правилу "80-20".

Пусть DIR содержит следующие статистические атрибуты:

• FoR (Force Out Rule) - правило вытеснения;

• FC (Frequency Counter) - количество обращений к странице.

Определим FCmax как максимальное значение атрибута FC в таблице DIR. Предположим, что в нашем менеджере буферного пула по умолчанию используется правило вытеснения, определяемое стратегией LFU, в соответствии с которой из буфера вытесняются страницы с наименьшим значением атрибута FC. Назначим наборам страниц правила вытеснения в соответствии с Табл. 1.

В данном контексте алгоритм вы- Табл. 1. Правила вытеснения для наборов. числения функции динамического рейтинга может иметь вид, изображенный на Рис. 3. Безусловно, этот алгоритм нуждается в некоторых доработках для того, чтобы его можно было использовать на практике. Во-первых, это касается выбора правила вытеснения, используемого по умолчанию. В примере выше мы использовали правило, определяемое стратегией LFU. Однако данная стратегия имеет существенный недостаток, заключающийся в том, что в буфере достаточно долго будут оставаться неиспользуемые страницы, которые "накопили" достаточно большое значение атрибута FC во время предшествующих обращений. Выбор стратегии вытеснения, используемой по умолчанию, является критическим для эффективной буферизации. В СУБД Омега мы используем разработанную нами новую стратегию замещения LFTJ-АГ, рассмотрению которой посвящена четвертая глава. Во-вторых, в алгоритме на Рис. 3 мы предположили, что правило вытеснения, ассоциированное с данной страницей, хранится в DIR (атрибут FoR). На самом деле правило вытеснения хранится в виде значения соответствующего атрибута таблицы открытых наборов. Это обеспечивает возможность задания для страницы более одного правила вытеснения, так как один и тот же набор может быть открыт одновременно двумя и более транзакциями. Для разрешения коллизий мы используем механизм " ......

приоритетов. Менеджер буферного пула СУБД Омега поддерживает три правила вытеснения, приведенные вместе с их приоритетами в Табл. 2.

Немедленное вытеснение Удержание

По умолчанию_

Правило вытеснения Приоритет

Удержание 1

LFU-K 2

Немедленное вытеснение 3

В четвертой главе, "Стратегия замещения страниц", предлагается новый алгоритм замещения ЬРи-АГ, ориентированный, прежде всего, на использование в параллельных системах баз данных без совместного использования ресурсов.

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

1) Автономность. Общая стратегия не должна использовать знаний о структуре запроса. Единственная информация, которая может быть использована общей стратегией, - это общая трасса обращений к страницам диска.

2) Адекватность по Зипфу. Общая стратегия должна обеспечивать высокую эффективность на трассах с распределением вероятностей обращений, соответствующим обобщенному распределению Зипфа.

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

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

Далее в диссертации дается обзор известных стратегий замещения и делается вывод о том, что ни одна из этих стратегий в полной мере не удовлетворяет предъявляемым требованиям. В соответствие с этим нами была разработана новая общая стратегия замещения, получившая название ЦЦ-ЛГ, которая в большей мере удовлетворяет требованиям, предъявляемым параллельными системами баз данных без совместного использования ресурсов.

На базе производящих функций строится формальная модель для описания стратегии замещения 1Л1-К. Пусть N - количество кэшируемых страниц диска. Пусть г\, ъ,..., гц- некоторая трасса обращений к страницам диска, М> 1. При этом меньшее значение индекса соответствует более позднему по времени обращению. Пусть задано некоторое целое т, 1 <т<М. Для некоторой фиксированной страницы /, I < 1 < Л', рассмотрим последовательность

Здесь ку - для всех У, 1 <./' < т (¿ц - символ Кронекера). Пусть Р,/(г) - производящая

функция для подпоследовательности к,!,..., к,„ последовательности (1), 1 <1<т. Пусть задано некоторое целое А, 1 < А < т. Определим

Обозначим / = т/А. Без существенного ограничения общности мы можем полагать, что т всегда кратно А. Определим

(О

РГМ=ад, №=РГ1^)-^;^)

для произвольного целого п > 0. Положим

I"

л!

для произвольного целого К > 0.

Формальное определение алгоритма LFIJ-АГ. Для каждой страницы диска, находящейся в буфере, вычисляется значение функции Rlfu-jt- Замещается страница, имеющая минимальное значение Rlfu-jt- Если таких страниц несколько, замещается та из них, которая дольше всего находилась в буфере. При этом алгоритм имеет два настраиваемых параметра muh, удовлетворяющих ограничениям 1 < h <т н I < т < М.

Для получения аналитической оценки параметра т строится вероятностную модель процесса обращения к страницам диска в некоторой абстрактной системе баз данных. Пусть N - количество кэшируемых страниц. Определим р, как вероятность обращения к странице /, 1 <, i< N. По определению имеем

N

Предположим, что вероятности р, не меняются во времени и распределяются по следующему закону:

(3)

где 0 < в < 1, #<?> - гармоническое число порядка в. Здесь в обозначает коэффициент перекоса. Значение 0 = 0 соответствует равномерному распределению (перекос отсутствует), при 0 = 1 мы получим распределение Зипфа, а при © = 1 - log 0.80/ log 0.20 - распределение, близкое к правилу "80-20".

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

Здесь ¿¡(г) - дзета-функция Римана, а В* - числа Бернулли. Используя это приближение, из (3) получаем

1

А»"

П

1-0

(4)

В частности, вероятность обращения к самой "популярной" в нашей модели странице 1 может быть найдена по следующей приближенной формуле:

1-©

Исследуем влияние параметра т на эффективность алгоритма LFU-ДГ в контексте описанной модели. Прежде всего заметим, что в данном контексте

limF*"1

= 0, для

т—ю.

п > 0 и h = т. Поэтому нам достаточно исследовать алгоритм LFU-0. Имеем

limjWo(0 = Pi т

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

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

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

М(т)= /^МАс, (6)

о

где

-{|ир/д+1/2)1пх-4-(в|(1-р(.г)+1/2)1п—

= * (7)

Чем меньше значение меры М, тем точнее может быть определена величина р, по формуле

р, = к!т, (8)

где к - число вхождений / в последовательность п, г2,..., гт.

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

ч

М(т)= (9)

где

2(1 -р,)2 1 -р,

х/ и Х2 - вещественные корни уравнения Р1т (х) = 0, XI <хг (это всегда имеет место при достаточно больших значениях т).

Функция может служить приближенной мерой для определения величины т так как, чем меньше значение интеграла (9), тем точнее будет определяться вероятность выборки страницы по числу ее вхождений в трассу длины т. Таким образом, мы можем задать некоторое фиксированное положительное число Е и выбирать значение т как наименьшее натуральное число такое, что

Й(т)<Е. (10)

Для больших т справедливо соотношение

шр,(1-Р|)-3/4; 1/2-р, 2(1 -р,)2 1-Р, ' То есть мы можем считать, что для больших т величина интеграла (9) пропорциональна

тР\ 0 ~ />|) ~ 3/4 Отвода следует, что соотношение (10) равносильно соотношению

2(1 -р,)2

тМ 1-р,)-3/4 2(1-Р,)2

где Д = СЕ для некоторой константы С> 0. Найдем оценку для величины Д. Для 0 = 0.5 «1 — Iog0.4571og0.20 и N = 32000, из (3) находимр, я 0.0029. Анализ графика М(т) для ©= 0.5 показывает, что приемлемую точность для экспериментальной оценки величины р\ можно получить при т = 500000. Подставляя указанные значения т и р\ в (11), получаем А < 727. Положим Д = 700. Тогда из (11) получаем

М1-А) PiO-A)

(12)

Отсюда, используя формулы (3) и (4), находим окончательную формулу для аналитической оценки параметра т:

71-е.

т > 2Д £(&) +

N"

-1

1-0

-1 L где Д = 700.

(13)

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

Далее рассматриваются практические аспекты реализации стратегии LFU-ЛГ и предлагается конкретная реализация модернизированной версии алгоритма LFU-2m на псевдокоде. В заключение приводятся результаты экспериментов по сравнительной оценке эффективности алгоритма LFU-2m для различных искусственных и реальных трасс, подтверждающие его высокую эффективность. В качестве иллюстрации приведем результаты экспериментов по анализу эффективности алгоритмов замещения на трассах, характерных для параллельных систем баз данных без совместного использования ресурсов. Процессорный узел в такой системе будет генерировать трассу обращений, на которой периоды с относительно стабильным распределением вероятностей обращений будут чередоваться с очень короткими периодами практически мгновенного перераспределения вероятностей обращений между страницами диска. В соответствие с этим мы построили искусственную трассу с периодическим распределением, полученным путем последовательного объединения 1000 отрезков (периодов) длиной по 1000 элементов каждый. На каждом отдельном отрезке все страницы имеют стационарное распределение вероятностей обращений, задаваемое формулой (3). Однако на разных отрезках одна и та же страница имеет различные вероятности обращения. Размер базы данных в этой серии экспериментов составлял 32000 страниц. Результаты этих экспериментов представлены на Рис. 4 и Рис. 5.

Периодическое распределение с в«0.86

Периодическое распределение с

70%: ,---

во%-

— * — ОРТ • • о- • LRU-2

-LFU-2m -LFU

£50%------*

- ■*• —ОРТ -а-LFU-2m

- - о- - LRU-2 -•-LFU

2000 2SOO

Длина буфера (в страницах)

2000 2500

Длина буфера (в страницах)

Рис.4. Сравнение эффективности различных алгоритмов в зависимости от длины буфера для периодического распределения по правилу "80-20" (8=0 86).

Рис. 5. Сравнение эффективности различных алгоритмов в зависимости от длины буфера для периодического распределения по правилу "45-20" (©=0.5).

В качестве ориентира мы включили в наши эксперименты оптимальный алгоритм ОРТ, который всегда вытесняет страницу, к которой дольше всего не будет обращений. В первом эксперименте для генерации отрезков трассы мы использовали распределение (3) с коэффициентом перекоса ® = 0.86. Результаты этого эксперимента показывают (см. Рис. 4), что на периодических трассах эффективность алгоритма LFU-2m может значительно превосходить эффективность алгоритма LRU-2 (примерно на 17%), приближаясь при малых размерах буферного пула к оптимальной. Следует также отметить, что алгоритм LFU, показывавший неплохие результаты для статического распределения, в случае периодического распределения оказывается неадекватным. Во втором эксперименте при " генерации отрезков трассы мы использовали распределение (3) с коэффициентом переко-

са © = 0.5. Результаты этого эксперимента показывают (см. Рис. 5), что при уменьшении коэффициента перекоса относительная эффективность алгоритма LFU-2m снижается, однако и в этом случае LFU-2m по-прежнему заметно превосходит по эффективности алго-► ритм LRU-2 (примерно на 12%).

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

Межкластерная фрагментация предполагает распределение фрагментов отношения по различным Омега-кластерам. Данный вид фрагментации применяется в системе Омега только для очень больших отношений (мы предполагаем, что отношение является "очень большим", если оно занимает более 1% дискового пространства Омега-кластера).

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

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

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

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

Схема работы предлагаемого алгоритма балансировки загрузки иллюстрируется на Рис. 6 на примере кластера с двумя процессорами. Здесь процессору Р, сопоставлен диск Dj, а процессору Р2 - диск D2. Предположим, что нам необходимо выполнить некоторую операцию, аргументом которой является отношение R (в общем случае R может представлять только часть хранимого отношения). Мы делим фрагменты, на которые разбито отношение R внутри Омега- | кластера, на две примерно равные части. Первая часть назначается для обработки процес- 1 copy Pi, вторая - процессору Pi (на Рис. 6 данной стадии соответствует момент времени 1 to). Пусть в момент времени (/ процессор Pi закончил обработку своей части отношения R, в то время как процессор Р2 успел выполнить только часть назначенной ему работы. В ' этом случае происходит повторное перераспределение необработанной части отношения R между двумя процессорами (на Рис. 6 данной стадии соответствует момент времени ti). Процесс продолжается до тех пор, пока отношение R не будет полностью обработано (на Рис. 6 данной стадии соответствует момент времени t.j). Алгоритм очевидным образом обобщается на произвольное число процессоров. Отличительной особенностью предло- , женного алгоритма балансировки загрузки процессоров является то, что он не требует 1 перемещения по соединительной сети больших объемов данных. Как показывают проведенные нами эксперименты, использование указанного алгоритма балансировки загрузки позволяет достичь на Омега-кластерах производительности, сравнимой с производительностью SE кластеров даже при наличии сильных перекосов данных.

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

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

D, R D,

&

Ь

©\

(ЕХ

D, R D, R

© | МММ xnnj

1,

© D) R © Р. R

Ь

- назначено для обработки

-обработано

Рис. б. Схема работы алгоритма балансировки загрузки для кластера с двумя процессорными узлами.

R

Рис. 7. Операторный фрейм.

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

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

__• указатель на функцию тела

£>— нити, реализующую соответ-

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

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

• указатель на выходной поток (см. ниже);

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

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

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

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

Пример фрагмента физического плана запроса, построенного на основе операторных фреймов, изображен на Рис. 8. Данный запрос вычисляет отношение

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

Рис. 8. Пример дерева запроса, реализованного с помощью операторных фреймов

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

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

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

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

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

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

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

Менеджер запросов системы Омега поддерживает потоки следующих предопределенных типов: хранимый файл; временный файл; канал кондуктора; канал маршрутизатора; склад.

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

Для реализации внутриоперационного (фрагментного) параллелизма в системе Омега используется специальный оператор обмена exchange. Оператор exchange реализуется на основе использования стандартного операторного фрейма и может быть добавлен в качестве узла в любое место дерева запроса. Оператор exchange имеет два специальных параметра, определяемых пользователем: номер порта обмена и указатель на функцию распределения. Функция распределения для каждой гранулы данных вычисляет логический номер процессорного узла, на котором данная гранула должна быть обработана. Параметр "порт обмена" позволяет включать в дерево запроса произвольное коли- v чество операторов exchange (для каждого оператора указывается свой уникальный порт обмена). Пример использования оператора обмена exchange для распараллеливания запроса приведен на Рис. 9. Здесь изображен физический план выполнения запроса, реализующего соединение двух отношений R и Q по некоторому общему атрибуту. Мы пред- ; полагаем, что отношение Q фрагментировано по атрибуту соединения с помощью некоторой функции h, а отношение R фрагментировано по некоторому другому атрибуту, не являющемуся атрибутом соединения. В данном контексте для распараллеливания операции соединения необходимо вставить в дерево запроса между оператором чтения scan R и оператором соединения join один оператор обмена exchange.

join

Q ecanQ j

ДГ Q

Рис. 9. Пример использования оператора обмена exchange.

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

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

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

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

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

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

Отличительной особенностью оператора обмена exchange является то, что

Рис. 10. Структура оператора обмена exchange

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

Предложенные подходы были нами реализованы в исполнителе запросов системы Омега для МВС-100. Исполнитель запросов является резидентной программой, загружаемой вместе с операционным ядром системы Омега на всех типовых процессорных модулях. Входными данными исполнителя являются параллельные агенты физического плана запроса. Общая схема обработки запроса в системе Омега представлена на Рис. 11 (мы здесь предполагаем, что Омега-кластер состоит из четырех процессорных модулей). В соответствие с этой схемой запрос на языке SQL передается пользователем на host-машину. Там он транслируется в некоторый последовательный физический план. Данный последовательный физический план преобразуется в параллельный план 1-го уровня. представляющий собой совокупность агентов 1-го уровня. Каждый агент 1-го уровня, кроме реляционных операций, может содержать специальные параллельные операции psplit (расщепление) и pmerge (слияние). Параллельный план 1-го уровня задает распараллеливание запроса с точностью до Омега-кластера.

Запрос I на SOLI

J s

ti г i

|| p/^N- з «< 8 si

38 z s i ? г

3 tt

и

в

If

а о-

5

Э

= *

¡1 si

U

РМ

«КЗ

pM^j-Q РМ^П pm^-Q

По

PMk0 ~M

PMk1 -M

HMK ti

PMk: -H

C2ic

Пользователь

Host-машина

МВС

Рис. 11. Схема обработки запроса в системе Омега, о - последовательный физический план; А, -агент 1-го уровня; а^ - агент 2-го уровня; РМ,, - процессорный модуль; О, - Омега-кластер.

На следующем этапе параллельный план 1-го уровня преобразуется в параллельный план 2-го уровня. При этом каждый агент 1-го уровня отображается в п агентов 2-го уровня. Здесь и обозначает количество процессорных модулей в Омега-кластере (на

Рис. 12. Левоориентированное дерево.

Рис. 11 п = 4). Это достигается путем вставки оператора обмена exchange в соответствующие места дерева запроса. Параллельный план 2-го уровня задает распараллеливание запроса с томностью до процессорного модуля.

На завершающем этапе агенты 2-го уровня пересылаются с host-машины на соответствующие процессорные модули МВС, где интерпретируются исполнителем запросов. Результаты выполнения агентов в пределах одного Омега-кластера объединяются корневым оператором exchange на нулевом процессорном модуле. Если запрос выполнялся на нескольких Омега-кластерах, то суммарный результат получается путем выполнения операции pmerge на нулевом узле одного из Омега-кластеров, откуда передается на host-машину.

В соответствии с принципами, описанными в данной главе, нами был спроектирован и реализован прототип менеджера запросов параллельной СУБД Омега для платформы МВС-100 в 8-процессорной конфигурации. Используя данный прототип, мы провели ряд вычислительных экспериментов, в которых исследовали эффективность потоковой модели при различных значениях параметров системы и базы данных. В качестве запросов мы использовали мультисоединения, представленные в виде левоориен-трованных деревьев, подобных дереву, изображенному на Рис. 12. Здесь join обозначает операцию соединения по некоторому общему атрибуту, Store - операцию записи результирующего отношения на диск. Мы использовали деревья с максимальной глубиной (количеством операций join), равной трем. В контексте Рис. 12 мы предполагаем, что отношение R имеет три атрибута: а/, а2, а3. Атрибут а/ является атрибутом соединения для отношения Qi, атрибут а; является атрибутом соединения для отношения Qi, атрибут aj является атрибутом соединения для отношения Q3.

Основные системные па- _ . , „ „

Табл. 3. Параметры системы Омега при проведении раметры приведены в Табл.3. экспевиментов.

Процессорные модули МВС в нашей конфигурации разделены на два Омега-кластера с топологией типа Л (см. Рис. 2). Каждый кластер состоит из четырех процессорных модулей. Максимальная длина кратчайшею пути между процессорными модулями кластера равна двум. Параметр VCF(R а) вычисляется как отношение V/\R\, где |Л| - размер отношения R, V - количество различных значений в столбце а, отношения R. В наших экспериментах мы предполагали, что все атрибуты отношения R имеют одинаковое значение параметра VCF.

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

Параметр Значение

Параметры кластера

Быстродействие процессора 20 MIPS

Пропускная способность пинка 20 Мбит/сек

Количество процессорных узлов 4

Количество дисков 4

Цлина кратчайшего пути 2 (максимум)

Параметры загрузки

Стоимость диспетчеризации 500 инструкций

Размер гранулы данных 1000 байт

Стоимость обработки гранулы 8000 инструкций

Параметры базы данных

Размер отношения 1600 гранул

VCF(R аJ 01

Распределение для R а, Зипфово (правило 80-20)

Распределение для 0, а, Зипфово (правило 80-20)

Параметры запроса

Фактор селективности 1

Глубина дерева запроса 3

Фактор селективности определяется как отношение size _of _the _ join _ result size _of _the_ source _ relation Здесь size_ofjheJoinjresult - размер результата соединения, size_of_the_source_relation -размер левого исходного (промежуточного) отношения в дереве запроса. Мы предполагали, что все операции,/о/п в дереве запроса имеют один и тот же фактор селективности.

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

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

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

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

Размер склада (в гранулах)

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

440 I-1 I I I I I I

2 6 10 14 18 22 26 30 34 38 Размер склада (в гранулах)

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

-e-SF = 05 —Л— SF = 0 7S —В—SF = 1

о о о e »оi

2 6 10 14 18 22 26 30 34 38 Размер склада (в гранулах)

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

2 6 10 14 18 22 26 30 34 38 Размер склада (в гранулах)

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

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

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

Для организации коллективной разработки параллельной СУБД Омега нами была предложена технология разработки программ для МВС-100, включающая в себя соответствующие организационные и программные средства. Данная технология базируется на следующих базовых структурно-информационных компонентах: репозиторий проекта, библиотека проекта и справочник по функциям библиотеки проекта. Репозиторий проекта хранит все исходные тексты подсистем и все изменения, которые были в них произведены после включения в репозиторий. Используя репозиторий проекта, разработчики могут получать актуальные версии файлов исходных текстов по номеру версии проекта, дате создания и модификации и др. Библиотека проекта (O-Ltb) хранит объектный код функций подсистем проекта. Разработчик использует библиотеку проекта для компиляции исходных текстов своих подсистем, использующих функции подсистем проекта, созданных другими разработчиками. Справочник по функциям Q-Lib представляет собой ги-

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

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

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

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

Если при дальнейшей разработке проекта в подсистеме обнаруживается ошибка, то программист копирует в свой рабочий каталог библиотеку O-Lib и удаляет из этой копии библиотеки все модули своей подсистемы, получая библиотеку Ш-Lib. После этого программист возобновляет работу над своей подсистемой, только теперь в технологическом цикле вместо O-Lib он использует O'-Lib.

Рис. 17. Технологический цикл коллективной разработки системы Омега.

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

Основные результаты диссертационной работы

На защиту выносятся следующие новые научные результаты.

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

' дительность, масштабируемость, доступность данных, баланс загрузки и простота

реализации. Построена конкретная реализация CDi архитектуры в виде прототипа ' параллельной системы баз данных Омега на базе отечественного многопроцессор-

ного комплекса МВС.

2. Разработаны методы создания эффективного операционного окружения для систем баз данных с С£>2 архитектурой. В частности, предложена новая модель организации легковесных процессов, базирующаяся на парадигме "производитель-потребитель" и использующая механизм "управление посредством потоков данных". Данная модель обеспечивает автоматическую диспетчеризацию и синхронизацию легковесных процессов и позволяет использовать их в качестве базового средства структуризации программы. Разработана оригинальная архитектура менеджера буферного пула, базирующаяся на использовании избыточного индекса буферного пула и новом методе вычисления рейтингов страниц. Описанный подход позволяет использовать комбинированные стратегии замещения, обеспечивая, в то же время, быстрый поиск страниц в буферном пуле и поддержку избирательного вытеснения страниц. Кроме этого, предложен оригинальный метод двухуровневой организации межпроцессорных коммуникаций, позволяющий существенно сократить накладные расходы на передачу сообщений внутри процессорных кластеров системы с CDj архитектурой. Описанные модели и методы реализованы в операционном ядре прототипа параллельной СУБД Омега для МВС, включающим в себя систему хранения, менеджер легковесных процессов и систему передачи сообщений.

3. Предложен новый алгоритм замещения страниц в буферном пуле, получивший название LFU-АГ. Проведен сравнительный анализ алгоритма LFU-AT и известных алгоритмов замещения, показывающий, что LFU-АГ в большей мере удовлетворяет требованиям, предъявляемым параллельными системами баз данных без совместного использования ресурсов, чем другие алгоритмы. Построена теоретико-вероятностная модель, на основе которой получены аналитические оценки для ба-

1 зового параметра алгоритма LFU-К. Остальные параметры алгоритма исследованы

в вычислительных экспериментах, на основе которых даны конкретные рекомендации для оптимального выбора этих параметров. Предложена эффективная реализация алгоритма LFU-2, которая может быть на практике использована для t управления буферным пулом в системах баз данных. На искусственных и реаль-

ных трассах обращений к страницам базы данных проведены вычислительные эксперименты, сравнивающие эффективность алгоритма LFU-2 с алгоритмами LFU, LRU, LRU-2, 2Q, ОРТ и АО. Данные эксперименты подтверждают высокую эффективность алгоритма LFU-2. При этом на трассах, характерных для параллельных систем баз данных без совместного использования ресурсов, эффектив-

ность алгоритма LFU-2 значительно превышает эффективность известных алгоритмов замещения.

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

5. Предложена технология коллективной разработки больших программных систем для многопроцессорного вычислительного комплекса МВС, включающая в себя комплекс концептуальных, организационных и программных средств. Данная технология была применена при разработке прототипа параллельной СУБД Омега для МВС. Общий объем отлаженного кода составил около 60 тысяч строк на языке Си (в том числе лично автором диссертации разработано более 30 тысяч строк).

Основные публикации по теме диссертации

Основные результаты диссертации полностью опубликованы автором в следующих работах:

1. Соколинский Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой // Программирование. -2001. -№6. -С. 13-29.

2. Соколинский Л.Б. Эффективный алгоритм замещения страниц для буферизации обменов с дисками в параллельной системе баз данных без совместного использования ресурсов // Вычислительные методы и программирование. -2002. -Том 3, №1. -С. 113-130.

3. Соколинский Л.Б. Структура средств компьютерной поддержки процесса прототипи-рования параллельной СУБД Омега для мультипроцессорной вычислительной системы МВС-100/1000 // Программные продукты и системы. -1999. -№2. -С. 15-19.

4. Sokolinsky L В. Design and Evaluation of Database Multiprocessor Architecture with High Data Availability // 12th International DEXA Workshop, Munich, Germany, 3-7 September, 2001, Proceedings. -IEEE Computer Society, 2001. -P. 115-120.

5. Sokolinsky L.B. Operating System Support for a Parallel DBMS with an Hierarchical Shared-Nothing Architecture // Advances in Databases and Information Systems, Third East European Conference, ADBIS'99, Maribor, Slovenia, September 13-16, 1999, Proceedings of Short Papers. -Maribor: Institute of Informatics, 1999. -P. 38-45.

6. Sokolinsky L.B. Choosing Multiprocessor System Architecture for Parallel Database Systems // Proc. of the 2nd Int. Workshop on Computer Science and Information Technologies (CSIT2000), Ufa, Russia, September 18-23,2000. Ufe State Aviation Technical University. -2000.-Vol. l.-P. 176-186.

7. Sokolinsky LB. Interprocessor Communication Support in the Omega Parallel Database System // Proc. of the 1st Int. Workshop on Computer Science and Information Technolo-gies(CSIT99), Moscow, January 18-22,1999.

8. Соколинский Л.Б. Проектирование и анализ архитектур параллельных машин баз данных с высокой отказоустойчивостью // Высокопроизводительные вычисления и их приложения: Труды Всероссийск. науч. конф. (30 октября - 2 ноября 2000 г.,

г. Черноголовка). -М.: Иэд-во МГУ, 2000. -С. 56-61.

9. Соколинский Л.Б. Эффективная организация легковесных процессов в параллельной СУБД Омега для МВС-100 // Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов: Тез. докл. Всероссийск. науч. конф. (21-26 сентября 1998 г., г. Новороссийск). -М.: Изд-во МГУ, 1998. -С. 132-138.

10. Lymar Т. У., Sokolinsky L.B. Data Streams Organization in Query Executor for Parallel DBMS // Databases&Information System. Proceedings of the 4th IEEE International Baltic Workshop, Lithuania, Vilnius, May 1-5,2000. -Vilnius: Technica. -2000. -Vol. 1. -P. 85-88.

11. Sokolinsky L.B., Axenov O., Gutova S. Omega: The Highly Parallel Database System Project // Proceedings of the First East-European Symposium on Advances in Database and Information Systems (ADBIS'97), St.-Petersburg, September 2-5, 1997. -St.-Peteisburg: Nevsky Dialect. -1997. -Vol. 2. -P. 88-90.

12. Zymbler M.L., Sokolinsky L.B. Implementation Principles of File Management System for Omega Parallel DBMS // Proc. of the 2nd Int. Workshop on Computer Science and Information Technologies (CSIT2000), Ufa, Russia, September 18-23,2000. -Ufe State Aviation Technical University, 2000. -Vol. 1. -P. 173-178.

13. Лымарь Т.Ю., Соколинский Л.Б. Инкапсуляция параллелизма в исполнителе запросов СУБД Омега // Высокопроизводительные вычисления и их приложения: Труды Всероссийск. науч. конф. (30 октября - 2 ноября 2000 г., г. Черноголовка). -М.: Изд-во МГУ, 2000.-С. 136-140.

14. Лымарь Т.Ю., Соколинский Л.Б. Организация параллельного исполнителя запросов на базе многопроцессорного вычислительного комплекса МВС-100/1000 // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -2002. -№1(6). -С. 177-188.

15. Соколинский Л.Б., Цымблер М.Л. Принципы реализации системы управления файлами в параллельной СУБД Омега для МВС-100 // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -1999. -№2(5). -С. 176-199.

16. Цымблер ММ., Соколинский Л.Б. Организация обработки больших объемов данных в многопроцессорных системах с массовым параллелизмом // Высокопроизводительные вычисления и их приложения: Труды Всероссийск. науч. конф. (30 октября - 2 ноября 2000 г., г. Черноголовка). -М.: Изд-во МГУ, 2000. -С. 186-190.

йооу-й т п

-- 6 8 58

17. Лымарь Т.Ю., Соколинский Л.Б. Управление потоками данных в параллельном исполнителе запросов СУБД Омега для МВС-100/1000 // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде (080'2000). Сб. докл. к Междунар. конф. (Екатеринбург, 30 мая - 2 июня 2000 г.). -Екатеринбург: УрО РАН, 2000. -С. 326-328.

18. Цымблер М.Л., Соколинский Л.Б. Выбор оптимальной стратегии вытеснения страниц в параллельной СУБД омега для мультипроцессорной системы МВС-100 // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде ф80'2000). Сб. докл. к Междунар. конф. (Екатеринбург, 30 мая - 2 июня 2000 г.). -Екатеринбург: УрО РАН, 2000. -С. 337-340.

19. Соколинский Л.Б., Цымблер М.Л. Проект создания параллельной СУБД Омега на базе суперкомпьютера МВС-100/1000 // Телематика'98: Тез. докл. Всероссийск. науч,-метод. конф. (8-11 июня 1998 г., Санкт-Петербург). -СПб: Вузтелекомцентр, 1998. -С. 154-155.

20. Цымблер М.Л., Соколинский Л.Б., Федрушков В.В. Использование 1п1ете1-технологий в коллективной разработке больших программных систем // Научный сервис в сети Интернет: Тез. докл. Всероссийск. науч. конф. (20-25 сентября 1999 г., г. Новороссийск). -М.: Изд-во МГУ, 1999. -С. 207-210.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 00-07-90077,97-07-90148).

Подписано в печать 03.03.03. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,9. Уч.-изд. л. 3,3. Тираж 100 экз. Заказ № 49. Бесплатно

Челябинский государственный университет 454021 Челябинск, ул. Братьев Кашириных, 129

Полиграфический участок Издательского центра ЧелГУ 454021 Челябинск, ул. Молодогвардейцев, 576

Введение.

Глава 1. Архитектура параллельных систем баз данных.

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

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

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

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

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

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

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

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

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

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

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

1.4. Сравнительный анализ архитектур параллельных систем баз данных .48 Ф 1.5. Архитектура системы Омега.

1.5.1. Три уровня абстракции системной архитектуры.

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

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

Глава 2. Методы построения операционного ядра системы Омега.

2.1. Общесистемное программное обеспечение МВС-100/1 ООО.

2.2. Структура операционного ядра системы Омега.

2.3. Организация управления легковесными процессами.

2.3.1. Особенности распараллеливания работ на МВС-100.

2.3.2. Потоковая модель для управления легковесными процессами.

2.3.3. Диспетчеризация нитей.

2.3.4. Реализация менеджера нитей.

• 2.4. Система хранения данных.

2.4.1. Архитектура системы хранения СУБД Омега.

2.4.2. Электронная дисковая подсистема.

• 2.4.3. Система управления файлами.

2.4.4. Менеджер наборов.

2.4.5. Менеджер файлов.

2.5. Организация межпроцессорных коммуникаций.

2.5.1. Система передачи сообщений.

2.5.2. Маршрутизатор. f 2.5.3. Кондуктор.

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

Глава 3. Методы управления буферным пулом.

3.1. Введение в проблематику буферизации данных.

3.2. Требования к подсистеме управления буферным пулом СУБД.

3.2.1. Поиск страницы в буферном пуле.

3.2.2. Замещение страниц в буферном пуле.

3.2.3. Избирательное вытеснение страниц.

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

3.3. Методы проектирования подсистемы управления буферным пулом параллельной СУБД Омега.

3.3.1. Архитектура менеджера буферного пула.

3.3.2. Метод статических и динамических рейтингов.

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

Глава 4. Стратегия замещения страниц.

4.1. Проблема выбора стратегии замещения страниц.

4.2. Требования к стратегии замещения.

4.3. Обзор известных стратегий замещения.

4.3.1. Стратегия LRU.

4.3.2. Специальные стратегии замещения. ш 4.3.3. Общие стратегии замещения.

4.4. Концепция алгоритма LFU-K.

4.5. Аналитическая оценка параметра ш алгоритма LFU-K.

• 4.5.1. Вероятностная модель.

4.5.2. Мера для определения параметра т.

4.5.3. Разложение нормальной функции в ряд Тейлора. щ 4.5.4. Приближенная мера для параметра т.

4.6. Реализация алгоритма LFU-K.

4.7. Результаты экспериментов по сравнительной оценке эффективности алгоритма LFU-2m.

4.7.1. Стационарное распределение вероятностей обращений.

4.7.2. Периодическое распределение вероятностей обращений.

4.7.3. Доступ в режиме OLTP с использованием индексного файла. р 4.7.4. Эксперименты на реальной трассе.

4.8. Выбор значений параметров алгоритма LFU-2m.

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

I Глава 5. Организация параллельного выполнения запросов в системе с CD архитектурой.

5.1. Стратегия размещения данных в системе Омега.

5.2. Алгоритм балансировки загрузки внутри Омега-кластера.

5.3. Организация параллельного выполнения запросов.

5.3.1. Модели параллелизации запросов.

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

5.3.3. Оператор обмена exchange.

5.4. Исполнитель запросов системы Омега.

5.4.1. Обработка запросов в системе Омега.

5.4.2. Физическая алгебра.

5.4.3. Интерфейс исполнителя физических запросов.

5.4.4. Реализация исполнителя физических запросов.

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

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

I Глава 6. Технологические аспекты разработки системы Омега.

6.1. Технология коллективной разработки СУБД Омега.

6.2. Организация коллективной разработки.

6.3. Программная поддержка технологии коллективной разработки.

6.3.1. Средства поддержки коллективной разработки.

6.3.2. Интегрированная среда разработчика.

6.3.3. Расширение среды программирования МВС-100.

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

АКТУАЛЬНОСТЬ ТЕМЫ

Комплекс сложных научно-технических проблем, связанных с созданием высокопроизводительных и надежных систем баз данных, в условиях перехода общества от индустриальной эры к информационной не только сохраняет, но и усиливает свою актуальность. Об этом свидетельствуют интенсивные научные исследования в области баз данных, проводимые в России и за рубежом [20, 97, 152].

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

Возникновение сверхбольших баз данных связано с расширением видов и сфер применения СУБД. Примерами новых приложений баз данных являются электронная коммерция [151], электронные библиотеки [19, 129, 203], геоинформационные системы [62], мультимедийные архивы [164], научные базы данных [92, 226] и др.

Одной из самых больших научных баз данных является база данных проекта BaBar [131]. Целью эксперимента BaBar является изучение поведения В-мезонов, получаемых на коллайдере PEP-II в Стэндфордском центре линейного ускорителя (Stanford Linear Accelerator Center). Детектор BaBar поставляет около 500 Гбайт информации ежедневно. Данная информация сохраняется в базе данных BaBar, объем которой сегодня составляет более 500 Тбайт. Система включает в себя 2000 процессоров и 100 серверов.

Другим примером сверхбольшой базы данных является база данных проекта EOS/DIS (Earth Observation System/Data Information System) [92, 122, 130], разрабатываемого агентством NASA в США. Система наблюдения земли EOS включает в себя множество спутников, которые собирают информацию, необходимую для изучения долгосрочных тенденций состояния атмосферы, океанов, земной поверхности. Начиная с 1998 года спутники поставляют информацию в объеме 1/3 петабайт (Petabyte - 1015 байт) в год. Предполагается, что к 2010 году общий объем поддерживаемых в системе данных превысит 20 петабайт.

Еще одним примером системы, требующей обработки сверхбольших объемов данных, является система SkyServer проекта SDSS (Sloan Digital Sky Survey) [229]. Данный проект предполагает создание виртуальной обсерватории, доступной через Интернет. База данных проекта должна объединить в себе полную информацию о наблюдениях всех участков звездного неба различными обсерваториями мира. Начальный объем базы данных проекта оценивается в 40 терабайт. Работы по созданию виртуальной обсерватории ведутся также и в России [10].

Фактически единственным эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных [120], обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах. Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских прототипов к полнофункциональным коммерческим продуктам, поставляемым на рынок высонепроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести DB2 Parallel Edition [15], NonStop SQL [61, 99] и NCR Teradata [32]. Подобные системы объединяют до тысячи процессоров и магнитных дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [234]. Одно из них - дальнейшее развитие аппаратной архитектуры параллельных систем баз данных. Как указывается в Асиломарском отчете о направлениях исследований в области баз данных [86], в ближайшем будущем крупные организации будут располагать базами данных объемом в несколько петабайт. Для обработки подобных объемов информации потребуются параллельные машины с десятками тысяч процессоров, что в сотни раз превышает их число в современных системах. Однако современные архитектуры и технологии параллельных систем баз данных вряд ли допускают масштабирование на два порядка. Для параллельных систем баз данных с тысячами процессорных узлов особое значение приобретает проблема обеспечения отказоустойчивости и высокой доступности данных, так как вероятность отказа некоторой аппаратной компоненты в таких системах возрастает в тысячи раз. Поэтому параллельные системы баз данных должны быть системами высокой готовности.

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

ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ

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

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

1) Провести сравнительный анализ различных подходов к классификации архитектур многопроцессорных систем в контексте параллельных СУБД и выработать адекватные методы классификации современных архитектур параллельных систем баз данных.

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

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

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

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

6) Реализовать предложенные методы и алгоритмы в виде прототипа параллельной СУБД Омега на базе отечественного многопроцессорного вычислительного комплекса МВС-100/1 ООО [13, 22]. Используя данный прототип, провести вычислительные эксперименты на тестовых базах данных, подтверждающие эффективность выработанных подходов.

7) Для успешного решения предыдущей задачи выработать технологию коллективной разработки больших программных систем для МВС-100.

МЕТОДЫ ИССЛЕДОВАНИЯ

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

НАУЧНАЯ НОВИЗНА

Научная новизна работы заключается в следующем:

1) предложена новая гибридная иерархическая архитектура (Сйг архитектура) для построения высокоэффективных, масштабируемых, отказоустойчивых параллельных систем баз данных;

2) описана оригинальная аппаратная реализация С/)2 архитектуры, базирующаяся на введении специального вида кластеров (Омега-кластеров) с разделяемыми дисками и двухпроцессорными несимметричными модулями с приватной памятью; разработана новая модель организации легковесных процессов, базирующаяся на парадигме "производитель-потребитель" и использующая механизм "управление посредством потоков данных"; предложена оригинальная архитектура менеджера буферного пула, основанная на использовании избыточного индекса буферного пула и комбинированном методе вычисления рейтингов страниц; разработан новый эффективный алгоритм замещения страниц в буферном пуле (алгоритм ЦГО-^, ориентированный на использование в параллельных системах баз данных без совместного использования ресурсов; предложена новая модель параллелизации запросов {потоковая модель), позволяющая достичь в контексте Омега-кластера хорошего баланса загрузки при относительно низких накладных расходах на межпроцессорные коммуникации и обеспечивающая автоматическую диспетчеризацию и синхронизацию процессов выполнения операций в дереве плана запроса на базе использования специальных промежуточных буферов (складов) для передачи порций данных от операции-производителя к операции-потребителю; разработан оригинальный алгоритм балансировки загрузки на уровне Омега-кластера, в основе которого лежит механизм репликации данных, названный внутрикластерным дублированием', на основе С£>2 архитектуры впервые создан прототип параллельной СУБД Омега для отечественных многопроцессорных вычислительных комплексов серии МВС; предложена технология коллективной разработки больших программных систем для многопроцессорного вычислительного комплекса

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ

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

1) предложенные подходы, методы и алгоритмы могут быть использованы для проектирования и разработки параллельных систем баз данных на базе широкого спектра многопроцессорных систем, начиная от мультипроцессоров с массовым параллелизмом типа МВС-1000 и кончая кластерами типа Beowulf;

2) алгоритм замещения страниц LFU-/T может быть использован для организации эффективной буферизации в различных параллельных системах баз данных без совместного использования ресурсов, а также для кэширования Web-страниц на ргоху-серверах, обслуживающих большое число пользователей WWW;

3) предложенная технология коллективной разработки больших программных систем для многопроцессорного вычислительного комплекса МВС-100 может быть перенесена в среду МВС-1000 и использована для создания сложных программных систем различного назначения.

СТРУКТУРА И ОБЪЕМ РАБОТЫ

Диссертация состоит из введения, шести глав, заключения и библиографии. Объем диссертации составляет 247 страниц, объем библиографии - 246 наименований.

Основные результаты диссертации полностью опубликованы в работах [33-35, 44-58, 63-65, 166, 213-217, 246]. Статья [47] стала призером конкурса РФФИ {грант 00-07-99602) среди научно-популярных статей, посвященных научным исследованиям, проводимым при финансовой поддержке РФФИ. Статья [54] была отмечена редколлегией как одна из лучших за весь период существования указанного научного журнала.

АПРОБАЦИЯ РАБОТЫ

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

- на IV Международном семинаре по параллельным и распределенным базам данных PaDD'2001 в составе XII Международной конференции по базам данных и экспертным системам DEXA'2001 (Мюнхен, Германия, 3-7 сентября, 2001 г.) при финансовой поддержке РФФИ {грант 01-07-93514);

- на III Восточно-европейской конференции по базам данных и информационным системам - ADBIS'99 (Марибор, Словения, 13-16 сентября

1999 г.) при финансовой поддержке РФФИ {грант 99-07-93023);

- на Международном симпозиуме по базам данных и информационным системам ADBIS'97 (Санкт-Петербург, 2-5 сентября 1997 г.).

- на IV Международной Балтийской конференции IEEE по базам данных и информационным системам - BalticDB&IS'2000 (Вильнюс, Литва, 1-5 мая 2000 г.);

- на 3-й Международной конференции по программированию и информационным технологиям CSIT'2001 (Уфа, 21-26 сентября 2001 г.);

- на 2-й Международной конференции по программированию и информационным технологиям CSIT'2000 (Уфа, 18-23 сентября 2000 г.);

- на 1-й Международной конференции по программированию и информационным технологиям CSIT'99 (Москва, 18-22 января 1999 г.); на Международном семинаре "Методы прикладной математики и информационные технологии в многодисциплинарных исследованиях и проектах" (Омск, 6-8 октября 1998 г.);

- на Международной конференции "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" -DSO'2000 (Екатеринбург, 30 мая - 2 июня 2000 г.);

- на Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (Черноголовка, 30 октября - 2 ноября

2000 г.);

- на Всероссийской научной конференции "Научный сервис в сети Internet" (Новороссийск, 20-25 сентября 1999 г.);

- на Всероссийской научной конференции "Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов" (Новороссийск, 21-26 сентября 1998 г.).

НАПРАВЛЕНИЯ ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ

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

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

2) Доказательство или опровержение гипотезы оптимальности алгоритма LFU-Ä", утверждающей, что любой алгоритм вытеснения, использующий не больше информации о трассе, чем использует алгоритм LFU-Ä, не может показывать эффективность, превышающую эффективность алгоритма LFU-J5T.

3) Исследование применимости стратегии замещения LFU-J5T для кэширования Web-страниц на ргоху-серверах, обслуживающих большое число пользователей WWW. В рамках этого направления мы предполагаем интегрировать алгоритм LFU-2 в программу Squid операционной системы UNIX/Linux и провести вычислительные эксперименты по оценке эффективности этого алгоритма в сравнении с другими известными алгоритмами.

4) Разработка методов оптимизации параллельных запросов, ориентированных на системы баз данных с CD2 архитектурой.

5) Разработка методов и алгоритмов для поддержки абстрактных типов данных в параллельных системах баз данных с CD2 архитектурой.

6) Разработка объектно-реляционной версии прототипа параллельной СУБД Омега для многопроцессорного вычислительного комплекса МВС-1000.

ЗАКЛЮЧЕНИЕ

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

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 00-07-90077, 97-07-90148).

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

1. Андреев А.Н., Воеводин Вл.В., Жуматий С.А. Кластеры и суперкомпьютеры - близнецы или братья? // Открытые системы. -2000. -№5-6. -С. 9-14.

2. Байкова И., Кулагин М. Современные дисковые системы RAID // Открытые системы. 1995. №3. С. 50-55.

3. Барон Г.Г. Параллельные архитектуры серверов баз данных // СУБД. -1995. -№2. -С. 32-44.

4. Бек Л. Введение в системное программирование. -М.: Мир, 1988. -448 с.

5. Бек К. Экстремальное программирование // Открытые системы. -2000. -№ 1-2. -С. 59-65. •

6. Борисов М. UNIX-кластеры // Открытые системы. -1995. -№2. -С. 22-28.

7. Брукс Ф.ГТ. Как проектируются и создаются программные комплексы. -М.: Наука, 1979. -252 с.

8. Ван ТасселД. Стиль, разработка, эффективность, отладка и испытание программ. -М.: Мир, 1985. -281 с.

9. Велъбицкий КВ. Технология программирования. -Киев: Техшка, 1984. -250 с.

10. Витковский В.В. и др. Проект Российской виртуальной обсерватории // Научный сервис в сети Интернет: Труды Всероссийск. науч. конф. (23-28 сентября 2002 г., г. Новороссийск). -М.: Изд-во МГУ, 2002. С. 11.

11. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем. -М: Изд-во МГУ, 1994. -103 с.

12. Волков A.A. Тесты ТРС // СУБД. -1995. -№2. -С. 70-78.

13. Голъдштейн M.JI. Мультипроцессорная вычислительная система на базе транспьютерной идеологии // Алгоритмы и программные средства параллельных вычислений: Сб. науч. тр. / ИММ УрО РАН. -Екатеринбург: УрО РАН, 1995. -С. 61-68.

14. Дубова Н. Суперкомпьютеры nCube // Открытые системы. -1995. -№2. -С. 42-47.

15. Игнатович Н. Семейство реляционных баз данных IBM DB2 // СУБД. -1997.-№2.-С. 5-17.

16. Керниган Б.В., Пайк P. UNIX универсальная среда программирования. -М.: Финансы и статистика, 1992. -304 с.

17. КнутД.Э. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд. -М.: Издательский дом "Вильяме", 2000. -720 с.

18. КнутД.Э. Искусство программирования, т. 3. Сортировка и поиск, 2-е изд. -М.: Издательский дом "Вильяме", 2000. -832 с.

19. Когаловский М.Р., Новиков Б.А. Электронные библиотеки новый класс информационных систем // Программирование. -2000. -№3. -С. 3-8.

20. Когаловский М.Р. Энциклопедия технологий баз данных. -М.: Финансы и статистика, 2002. -800 с.

21. Корнеев В. Архитектуры с распределенной разделяемой памятью // Открытые системы. -2001. -№3. -С. 15-23.

22. Корнеев В.В. Параллельные вычислительные системы. -М.: "Нолидж", 1999. -320 с.

23. Корнеев В.В., Гареев А.Ф., Васютин C.B., РайхВ.В. Базы данных. Интеллектуальная обработка информации. 2-е издание. -М.: Нолидж, 2001.-496 с.

24. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД // Программирование. -1989, №6. -С. 46-59.

25. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД// Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М.: ВИНИТИ, 1989. -С. 76-153.

26. Кузнецов С.Д. Развитие идей и приложений реляционной СУБД System R // Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М.: ВИНИТИ, 1989. -С. 3-75.

27. Кузнецов С.Д. Операционные системы для управления базами данных // СУБД. -1996. -№3. -С. 95-102.

28. Кузнецов С Д. Реляционные системы управления базами данных: введение // Открытые системы. -1995. -№4. -С. 17-27.

29. Кузнецов С Д. СУБД и файловые системы. -М.: Майор, 2001. -176 с.

30. Кузьминский М., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. -1995. -№6. -С. 33-40.

31. Лацис А.О. Разработка ОС коллективного использования для многопроцессорной супер-ЭВМ МВС-100 // Транспьютерные системы и их применение: Тез. докл. Всероссийск. науч. конф. -М.: ИПМ им. Келдыша, 1995. -С. 17-24.

32. Лисянский К, Слободяников Д. СУБД Teradata для ОС UNIX // СУБД. -1997. -№5-6.-С. 25-46.

33. Лымарь Т.Ю., Соколинский Л.Б. Организация параллельного исполнителя запросов на базе многопроцессорного вычислительного комплекса МВС-100/1 ООО // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -2002. -№1(6). -С. 177-188.

34. Митчел Д.А.П., Томпсон Дж.А., Мансон Г.А., Брукс Г.Р. Внутри транспьютера. -М.: Мейкер, 1993. -206 с.

35. Оззу М.Т., Валдуриз П. Распределенные и параллельные системы баз данных // СУБД. -1996. -№4. -С. 4-26.

36. Петренко А.К. Методы отладки и мониторинга параллельных программ // Программирование. -1994. -№ 3. -С 39-63.

37. Позин Б.А. Современные средства программной инженерии для создания открытых прикладных информационных систем // СУБД. -1995. -№ 1. -С. 139-144.

38. Самофалов В.В., Василиади A.A. Сборочное параллельное программирование // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -1999. -№2(5). -С. 161-175.

39. Сафонов В.О. Языки и методы программирования в системе "Эльбрус". -М.: Наука, 1989. -392 с.

40. Сафонов В. О., Соколинский Л.Б. Применение знаний об интерфейсах втехнологии разработки модульных надежных программ // Методы повышения качества программного обеспечения. -Владивосток. -1990. -С. 58-60.

41. Соколинский Л.Б. Исполнитель физических запросов СУБД Омега.

42. Технич. отчет OMEGA04. ЧелГУ, 1999. -26 с. (http://www.csu.ru/~sok/papers/omegarep/engine.html)

43. Соколинский Л.Б. Организация параллельного выполнения запросов вмногопроцессорной машине баз данных с иерархической архитектурой // Программирование. -2001. -№6. -С. 13-29.

44. Соколинский Л.Б. Организация формульных вычислений в составе баз данных // Приборы и системы управления. -1997. -№3. -С. 50-52.

45. Соколинский Л.Б. Параллельные машины баз данных // Природа. Естественно-научный журнал Российской академии наук. -2001. -№8. -С. 10-17.

46. Соколинский Л.Б. Система управления файлами СУБД Омега. Технич. отчет OMEGAÛ3. -ЧелГУ, 1998. 25 с. (http://www.csu.ru/~sok/papers/omegarep/filesys.html)

47. Соколинский Л.Б. Структура системного окружения СУБД Омега. Технич. отчет OMEGA02. -ЧелГУ, 1998. (http://www.csu.ru/~sok/papers/omegarep/structure.html)

48. Соколинский Л.Б. Структура средств компьютерной поддержки процесса прототипирования параллельной СУБД Омега для мультипроцессорной вычислительной системы МВС-100/1 ООО // Программные продукты и системы. -1999. -№2. -С. 15-19.

49. Соколинский Л.Б. Эффективный алгоритм замещения страниц для буферизации обменов с дисками в параллельной системе баз данных без совместного использования ресурсов // Вычислительные методы и программирование. -2002. -Том 3, №1. -С. 113-130.

50. Соколинский Л.Б., Захарьевич В.А. Объектно-ориентированное программирование в среде Clipper 5.0 // Материалы I Межрегионального семинара по объектно-ориентированному программированию (24-26 сентября 1991, Минск). -Минск: НИФ "SCI", 1991. -С. 19-23.

51. Соколинский Л.Б., Лымаръ Т.Ю. О выборе оптимального плана выполне• ния запроса в параллельной системе баз данных // Проблемы оптимизации и экономические приложения: Тезисы докладов международной конференции. -Омск: Омск. гос. ун-т, 1997. -С. 146.

52. Соколинский Л.Б., Цымблер М.Л. Принципы реализации системы управления файлами в параллельной СУБД Омега для МВС-100 // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -1999.-№2(5). -С. 176-199.

53. Соколинский Л.Б., Цымблер М.Л. Проект создания параллельной СУБД Омега на базе суперкомпьютера МВС-100/1 ООО // Телематика'98: Тез.• докл. Всероссийск. науч.-метод. конф. (8-11 июня 1998 г., Санкт-Петербург). -СПб: Вузтелекомцентр, 1998. -С. 154-155.

54. Титчмарш Е.К. Теория дзета-функции Римана. -М.: ИЛ, 1953. -346 с.

55. Ульман Дж., УидомДж. Введение в системы баз данных. -М.: ЛОРИ, 2000. -347 с.6\.Хаманн Ф. Отказоустойчивая операционная система Tandem NonStop Kernel // Открытые системы. -1997. -№3. -С. 32-36.

56. Цветков В.Я. Геоинформационные системы и технологии. -М.: Финансы и статистика, 1998.

57. Шалунов С.В. Операционная среда Emacs // Открытые системы. -№ 4. -1997.-С. 11-15.

58. Шмидт В. Системы IBM SP2 // Открытые системы. -1995. -№6. -С. 53-60.

59. Шнитман В. Отказоустойчивые серверы ServerNet // Открытые системы. -1996.-№3.-С. 5-11.

60. ШэнкДэ/с. Технология клиент/сервер и ее приложения. Руководство Novell. -М.: ЛОРИ, 1995. -418 с.

61. Apers P.M.G., van den Berg С.A., Flokstra J., Grefen P. W.P. J., Kersten M.L., Wilschut A.N. Prisma/DB: a Parallel Main-Memory Realational DBMS // IEEE Transactions on Knowledge and Data Engineering. -1992. -Vol. 4, No. 6.-P. 541-554.

62. AhoA. V., Denning P. J., Ullman J.D. Principles of Optimal Page Replacement // Journal of the ACM. -1971. -Vol. 18, No. l.-P. 80-93.

63. Alonso R., Barbara D., Garcia-Molina H. Data Caching Issues in an Information Retrieval System // ACM Transactions on Database Systems. -1990. -Vol. 15, No. 3. -P. 359-384.

64. Amza C., et al. ThreadMarks: Shared Memory Computing on Networks of Workstations // IEEE Computer. -1996. -Vol. 29, No. 2. -P. 18-28.

65. Astrakan M. M., et al. System R: Relational Approach to Database Management // ACM Transactions on Database Systems. -1976. -Vol. 1, No. 2. -P. 97-137.

66. Bach M.J. The Design of the UNIX Operating System. -Prentice-Hall, 1987.

67. Ballinger C., Fryer R. Born To Be Parallel: Why Parallel Origins Give Teradata an Enduring Performance Edge // IEEE Data Engineering Bulletin. -1997. -Vol. 20, No. 2. -P. 3-12.

68. Baru C. K., et al. DB2 Parallel Edition // IBM System Journal. -1995. -Vol. 34, No. 2. -P. 292-322.

69. BeladyL.A. A Study of Replacement Algorithms for Virtual-Storage Computer // IBM Systems Journal. -1966. -Vol. 5, No. 2. -P. 78-101.

70. Bell C.G., Gray J. What's next in high-performance computing? // Communications of the ACM. -2002. -Vol. 45, No. 2. -P. 91-95.

71. Bell D., MorreyL, PoghJ. Software Engineering. A programming Approach. -Prentice Hall, 1992. -338 P.

72. Bergsien B., Couprie M., Valdurez P. Overview of Parallel Architectures for Databases // The Computer Journal. -1993. -Vol. 36, No. 8. -P. 734-740.

73. Berliner B. CVS: Parallelizing Software Development. http://www.hu.freebsd.org/hu/doc/psd/28.cvs/paper.html.

74. Bernstein P.A., et al. The Asilomar Report on Database Research // ACM SIGMOD Record. -1998. -Vol. 27, No. 4. -P. 74-80.

75. BhideA. An Analysis of Three Transaction Processing Architectures // Fourteenth International Conference on Very Large Data Bases (VLDB'88), August 29 September 1, 1988, Los Angeles, California, USA, Proceedings. -Morgan Kaufmann, 1988. -P. 339-350.

76. BoralH., Alexander W., ClayL., Copeland G., Sanforth S., Franklin M., Hart B., Smith M., Valduriez P. Prototyping Bubba: a Highly Parallel Database System // IEEE Trans, on Knowledge and Data Engineering. -1990. -Vol. 2, No. 1. -P. 4-24.

77. Boral H., DeWitt D.J. Applying Data Flow Techniques to Data Base Machines // IEEE Computer. -1982. -Vol. 15, No. 8. -P. 57-63.91 .Bouganim L., Florescu D., Valduriez P. Dynamic Load Balancing in

78. Hierarchical Parallel Database Systems // VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. -Morgan Kaufmann, 1996. -P. 436-447.

79. Brown P., Stonebraker M. BigSur: A System For the Management of Earth Science Data // VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. -Morgan Kaufmann, 1995. -P. 720-728.

80. Bultzingsloewen G. Optimizing SQL Queries for Parallel Execution // ACM SIGMOD Record. -1989. -Vol. 18, No. 4. -P. 4-11.

81. Bultzingsloewen G.v., et al. KARDAMOM A Dataflow Database Machine

82. For Real-Time Applications // SIGMOD Record. -1988. -Vol. 17, No. 1. -P. 44-50.

83. Carey M.J., JauhariR., Livny M. Priority in DBMS Resource Scheduling // Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. -Morgan Kaufmann, 1989. -P. 397-410

84. R.T., Vianu V. SIGMOD Sister Societies // SIGMOD Record. -2000. -Vol. 29, No. l.-P. 4-15.

85. Chamberlin D.D., et al. A History and Evaluation of System R // Communications of the ACM. -1981. -Vol. 24, No. 10. -P. 632-646.

86. Chambers L., Cracknell D. Parallel Features of NonStop SQL // Proceedings of « the 2nd International Conference on Parallel and Distributed Information

87. Chen M.-S., YuP.S., Wu K.-L. Optimization of Parallel Execution for Multi* Join Queries // IEEE Transactions on Knowledge and Data Engineering. -1996.-Vol. 8, No. 3.-P. 416-428.

88. Christodoulakis S. Estimating record selectivities // Information Systems. -1983.-Vol. 8, No. 2. -P. 105-115.

89. CoddE.F. A Relational Model of Data for Large Shared Data Banks // Communications of the ACM. -1970. -Vol. 13, No. 6. -P. 377-387.

90. Coffman E.G., Denning P.J. Operating Systems Theory. -Prentice-Hall, 1973.

91. Comer D. The Ubiquitous B-Tree // ACM Computing Surveys. -1979. -Vol. 11, No. 2.-P. 121-137.

92. Copeland G.P., Keller T. A Comparison Of High-Availability Media Recovery Techniques // Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 June 2, 1989. -ACM Press, 1989. -P. 98-109.

93. Cyclic CVSweb page. http://www.cyclic.com/cyclic-pages/web-cvsweb.html.

94. Darwen H., Date C.J. The Third Manifesto // ACM SIGMOD Record. -1995. -Vol. 24, No. 1.-P. 39-49.

95. Dasgupta S. A Hierarchical Taxonomic System for Computer Architectures I I IEEE Computer. -1990. -Vol. 23, No. 3. -P. 64-74.

96. Davison W. Parallel Index Building in Informix OnLine 6.0 // Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. -ACM Press, 1992. -P. 103.

97. Denning P J. The Working Set Model for Program Behaviour // Communications of the ACM. -1968. -Vol. 1 l,No. 5. -P. 323-333.

98. DeWitt D.J., et al. The Gamma database machine project // IEEE Transactins on Knowledge and Data Engineering. -1990. -Vol. 2, No. 1. -P. 44-62.

99. DeWitt D.J., Gerber R.H. Multiprocessor Hash-Based Join Algorithms // VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23,1985, Stockholm, Sweden. -Morgan Kaufmann, 1985. -P. 151-164.

100. Dozier J. Access to data in NASA's Earth observing system // Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. -ACM Press, 1992. -P. 1.

101. Effelsberg W., Haerder T. Principles of Database Buffer Management // ACM Trans, on Database Systems. -1984. -Vol. 9, No. 4. -P. 560-595.

102. Englert S., Glasstone R„ Hasan W. Parallelism and its Price: A Case Study of NonStop SQL/MP // ACM SIGMOD Record. -1995. -Vol. 24, No. 4. -P. 61-71.

103. Faloutsos C., Ng R.T., Sellis T.K. Predictive Load Control for Flexible Buffer Allocation // 17th International Conference on Very Large Data Bases, September 3-6,1991, Barcelona, Catalonia, Spain, Proceedings. -Morgan Kaufmann, 1991. -P. 265-274.

104. Flynn M.J. Computer Organization and Architecture // Operating Systems, An Advanced Course. -Springer, 1978 (Lecture Notes in Computer Science;1. Vol. 60). -P. 17-98.

105. Flynn M.J. Very High Speed Computing Systems // Proc. IEEE. -1966. -Vol. 54.-P. 1901-1909.

106. Flynn M.J., Rudd K. W. Parallel architectures // ACM Computing Surveys. 1996. -Vol. 28, No. 1. -P. 67-70.

107. FoxE.A., Akscyn R.M., Furuta R.K., LeggettJ.J. Digital libraries // Communications of the ACM. -1995. -Vol. 38, No. 4. -P. 22-28.

108. Frew J., Dozier J. Data Management for Earth System Science // ACM SIGMOD Record. 1997. -Vol. 26, No. 1. -P. 27-31.

109. Gaponenko I., et al. The BaBar Database: Challenges, Trends and Projections II Proc. of Int. Conf. on Computing in High Energy and Nuclear Physics (CHEP'01), September 3 7, 2001, Beijing, China. -Science Press, 2001.

110. Garcia-Molina H., Ullman J.D., WidomJ. Database System Implementation. -Prentice Hall, 2000. -653 p.

111. Gibson G.A., Vitter J.S., Wilkes J. Strategic directions in storage I/O issues in large-scale computing // ACM Computing Surveys. -1996. -Vol. 28, No. 4. -P.779-793.

112. Graefe G. Encapsulation of Parallelism in the Volcano Query Processing Systems // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. -ACM Press, 1990. -P. 102-111.

113. Graefe G. Query evaluation techniques for large databases // ACM Comput• ing Surveys. -1993. -Vol. 25, No. 2. -P. 73-169.

114. Graefe G. Volcano An Extensible and Parallel Query Evaluation System // IEEE Transactions on Knowledge and Data Engineering. -1994. -Vol. 6, No. 1. -P. 120-135.

115. Gray J. Notes on Data Base Operating Systems // Operating Systems, An

116. Advanced Course.-Springer, 1978 (Lecture Notes in Computer Science; Vol.60). -P. 393-481.

117. Gray J., et al. The Recovery Manager of the System R Database Manager // ACM Computing Surveys. -1981. -Vol. 13, No. 2. -P. 223-243.

118. Gray J., Graefe G. The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb // SIGMOD Record. -1997. -Vol. 26, No. 4. -P. 63-68.

119. Gray J., Reuter A. Transaction Processing: Concepts and Techniques. -Morgan Kaufmann, 1993. 1070 p.

120. Haerder T., Reuter A. Principles of Transaction-Oriented Database Recovery m II ACM Computing Surveys. -1983. -Vol. 15, No. 4. -P. 287-317.

121. Hasan W. Optimization of SQL Queries for Parallel Machines. (Lecture notes in computer science, Vol. 1182). -Berlin, New York: Springer, 1996. -133 p.

122. Heising W.P. Note on Random Addressing Techniques // IBM Systems Journal. -1963. -Vol. 2, No. 2. -P. 112-116.

123. Hong W., Stonebraker M. Optimization of Parallel Query Execution Plans in XPRS // Distributed and Parallel Databases. -1993. -Vol. 1, No. 1. -P. 9-32.

124. Hsiao H. I., De Witt D. J. A Performance Study of Three High Availability Data Replication Strategies // Distributed and Parallel Databases. -1993. -Vol. 1, No. l.-P. 53-80.

125. Jarke M., Koch J. Query optimization in database systems I I ACM Computing Surveys. -1984. -Vol. 16, No. 2. -P. 111-152.

126. Kalakota R., Whinston A. Readings in Electronic Commerce. -Addison-Wesley, 1997.

127. Kim W. Highly Available Systems for Database Applications // ACM Computing Surveys. -1984. -Vol. 16, No. 1. -P. 71-98.

128. King G. M., Dias D. M, Yu P. S. Cluster Architectures and S/390 Parallel Sysplex Scalability // IBM Systems Journal. -1997. -Vol. 36, No. 2. -P. 221-241.

129. Kotsis G. Interconnection Topologies for Parallel Processing Systems // PARS Mitteilungen. -1993. -No. 11. -P. 1-6.

130. Kronenberg N.P., Levy H.M., Strecker W.D. VAXclusters: A Closely-Coupled Distributed System // ACM Transactions on Computer Systems. -1986. -Vol. 4, No. 2. -P. 130-146.

131. Lakshmi M.S., Yu P.S. Effectiveness of Parallel Joins // IEEE Transactions on Knowledge and Data Engineering. -1990. -Vol. 2, No. 4. -P. 410-424.

132. Lampson B. W. Atomic Transactions // Distributed Systems Architecture and Implementation, An Advanced Course. -Springer, 1981 (Lecture Notes in Computer Science; Vol. 105). -P. 246-265.

133. Lohman G.M., et al Query Processing in R* // Query Processing in Database Systems. -Springer, 1985. -P. 31-47.

134. Lorie R., et al. Adding Intra-transaction Parallelism to an Existing DBMS:

135. Early Experience // Data Engineering Bulletin. -1989. -Vol. 12, No. 1. -P. 2-8.

136. Lu G. Multimedia Database Management System. -Artech House, 1999.

137. Lu H., Shan M.-C., Tan K.-L. Optimization of Multi-Way Join Queries for Parallel Execution // 17th International Conference on Very Large Data Bases, September 3-6,1991, Barcelona, Catalonia, Spain, Proceedings. -Morgan

138. Kaufmann, 1991. -P. 549-560.

139. Makowski A.M., Nelson R. Optimal Scheduling for a Distributed Parallel

140. Processing Model. Tech. Rept. 17449, IBM Research, 1992.

141. Mattson R.L., et al. Evaluation techniques for storage hierarchies // IBM Systems Journal. -1970. -Vol. 9, No. 2. -P. 78-117.

142. Menon J. A Study of Sort Algorithms for Multiprocessor Database Machines // VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28,1986, Kyoto, Japan, Proceedings. -Morgan Kaufmann, 1986. -P. 197-206.

143. NgR.T., Faloutsos C., Sellis T.K. Flexible Buffer Allocation Based on Marginal Gains//Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. -ACM Press, 1991. -P. 387-396.

144. Nick J. M., Moore B. B., Chung J.-Y., Bowen N. S. S/390 Cluster Technology: Parallel Sysplex // IBM Systems Journal. -1997. -Vol. 36, No. 2. -P. 172-201.

145. Nicola V.F., Dan A., Dias D.M. Analysis of the generalized clock buffer replacement scheme for database transaction processing // ACM SIGMETRICS Performance Evaluation Review. -1992. -Vol. 20, No. 1. -P. 34-46.

146. Norman M. G., Zurek T., Thanisch P. Much Ado About Shared-Nothing // ACM SIGMOD Record. -1996. -Vol. 25, No. 3. -P. 16-21.

147. OldehoeftR. R. Multithreaded Computer Systems // Proceedings• Supercomputing'92, November 16-20,1992, Minneapolis, MN, USA. -IEEE Computer Society, 1992. -P. 772-775.

148. O'Neil E.J., O'Neil P.E., Weikum G. An optimality proof of the LRU-K page replacement algorithm // Journal of the ACM. -1999. -Vol. 46, No. 1. -P. 92112.

149. Orfali R, Harkey D., Edwards J. Essential Client/Server Survival Guide. -NY: John Wiley, 1994. -P. 109.

150. Ozsu M.T., Valduriez P. Principles of Distributed Database System. -Englewood Cliffs, NJ: Prentice-Hall, 1991. 562 p.

151. Palmer M., Zdonik S.B. Fido: A Cache That Learns to Fetch // 17th1.ternational Conference on Very Large Data Bases, September 3-6, 1991, t Barcelona, Catalonia, Spain, Proceedings. -Morgan Kaufmann, 1991.-P. 255-264.

152. Patterson D.J. Hardware Technology Trends and Database Opportunities, SIGMOD Conference 1998 Keynote Speech, Video // ACM SIGMOD Digital Symposium Collection. -1999. -Vol. 1, No. 2.

153. Patterson D.A., Gibson G.A., Katz R.H. A Case for Redundant Arrays of Inexpensive Disks (RAID) // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988. 1988. P. 109-116.

154. Pfister G. Sizing Up Parallel Architectures // DataBase Programming & Design OnLine (http://www.dbpd.com). May 1998. -Vol. 11, No. 5.

155. PGI Supercompilers and Advanced Development Tools for the Intel i860. http://www.pgroup.com/i860home.html.

156. Pramanik S., Tout W.R. The NUMA with Clusters of Processors for Parallel Join // IEEE Transactions on Knowledge and Data Engineering. -1997. -Vol. 9, No. 4. -P. 653-666.

157. Query Processing in Parallel Relational Database Systems / edited by. Lu H., Ooi B.-C., Tan K.-L. -IEEE Computer Society Press, 1994. -382 p.

158. Rabinovich M.t Spatscheck O. Web Caching and Replication. -Addison-Wesley, 2001.-361 p.

159. Rahm E. A Framework for Workload Allocation in Distributed Transaction Processing Systems // Journal of Systems and Software. -1992. -Vol. 18. -P. 171-190.

160. Rahm E. Parallel Query Processing in Shared Disk Database Systems // ACM SIGMOD Record. -1993. -Vol. 22, No. 4. -P. 32-37.

161. Reiter A. A Study of Buffer Management Polices for Data Management Systems. Tech. Summary Rep. No. 1619, Mathematics Research Center, Univ. of Wisconsin, Madison, March 1976.

162. Richardson J.P., Lu H., Mikkilineni K. Design and Evaluation of Parallel Pipelined Join Algorithms // Proceedings of the ACM SIGMD 1987 Annual Conference, San Francisco, California, May 27-29, 1987. -ACM Press, 1987. -P. 399-409.

163. Rodriguez-Rosell J. Empirical data reference behavior in database system // IEEE Computer. -1976. -Vol. 9, No. 11. -P. 9-13.

164. Rodriguez-Rosell J., DupuyJ.P. The Working Set Model for Program Behaviour // Communications of the ACM. -1973. -Vol. 16, No. 4. -P. 247-253.

165. Sacco G. M., Schkolnick M. Buffer management in relational database systems // TODS. -1986. -Vol. 11, No. 4. -P. 473-498.

166. SchatzB., Chen H. Digital Libraries: Technological Advances and Social Impacts // IEEE Computer. -1999. -Vol. 32, No. 2. -P. 45-50.

167. SevcikK.C. Application Scheduling and Processor Allocation in Multiprogrammed Parallel Processing Systems. Technical Report CSRI-282. Computer Systems Research Institute. University of Toronto. Toronto, Canada, 1993.-34 p.

168. Shasha D. Database Tuning A Principled Approach. -Prentice-Hall, 1992.

169. Skillicorn D.B. A Taxonomy for Computer Architectures // IEEE Computer. -1988.-Vol. 21, No. 1.-P. 46-57.

170. Measurement and Modeling of Computer Systems, May 1-4, 1999, Atlanta, Georgia, USA, Proceedings. -1999. -P. 122-133.

171. Smith A.J. Sequentiality and Prefetching in Database Systems // ACM Transactions on Computer Systems. -1978. -Vol. 3, No. 3. -P. 223-247.

172. Sokolinsky L.B. Interprocessor Communication Support in the Omega Parallel Database System // Proc. of the 1st Int. Workshop on Computer Science and Information Technologies(CSIT*99), Moscow, January 18-22, 1999.

173. Sterling T., et all BEOWULF: A Parallel Workstation for Scientific

174. Computation // Proceedings of the 1995 International Conference on Parallel

175. Processing, August 14-18,1995, Urbana-Champain, Illinois, USA. Volume I: Architecture. -CRC Press, 1995. -P. 11-14.

176. Stonebraker M., et al. The Design and Implementation of INGRES // ACM Transactions On Database Systems. -1976. -Vol. 1, No. 3. -P. 189-222.

177. Stonebraker M. Retrospection on a Database System // ACM Transactions On Database Systems. -1980. -Vol. 5, No. 2. -P. 225-240.

178. Stonebraker M. Operating System Support for Database Management // Communications of the ACM. -1981. -Vol. 24, No. 7. -P. 412-418.1.

179. Stonebraker M. The case for shared nothing // Database Engineering Bulletin. -1986. -Vol. 9, No. l.-P. 4-9.9 223. Stonebraker M. Inclusion of New Types in Relational Data Base Systems //

180. DE 1986: Proceedings of the Second International Conference on Data Engineering, February 5-7, 1986, Los Angeles, California, USA. -IEEE Computer Society, 1986. -P. 262-269.

181. Stonebraker M., Katz R.H., Patterson D.A., Ousterhout J.K. The Design of

182. XPRS // Fourteenth International Conference on Very Large Data Bases, August 29 September 1, 1988, Los Angeles, California, USA, Proceedings.-Morgan Kaufmann, 1988. -P. 318-330.

183. Stonebraker M., et al. Third-Generation Database System Manifesto // ACM

184. SIGMOD Record. -1990. -Vol. 19, No. 3. -P. 31-44.

185. Stonebraker M., Frew J., Gardeis K., Meredith J. The Sequoia 2000

186. Benchmark // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. -ACM Press, 1993.-P. 2-11.

187. Strickland J.P., Uhrowczik P.P., Watts V.L. IMS/VS: An Evolving System // IBM Systems Journal. -1982. -Vol. 21, No. 3. -P. 490-510.

188. Szalay A.S., et al The SDSS SkyServer Public Access to the Sloan Digital Sky Server Data// Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6,2002. -ACM Press, 2002.

189. TengJ.Z., Gumaer R.A. Managing IBM Database 2 Buffers to Maximize Performance // IBM Systems Journal. -1984. -Vol. 23, No. 2. -P. 211-218.

190. The Benchmark Handbook for Database and Transaction Processing Systems, Second Edition. -Morgan-Kaufmann, 1993. -592 p.

191. Thorington J.M.Jr., David J. IRWIN, An Adaptive Replacement Algorithm for Paged Memory Computer Systems // IEEE Transactions on Computers. October 1972. -Vol. 21, No. 10. -P. 1053-1061.

192. Torvalds L. The Linux edge // Communications of the ACM. -1999. -Vol. 42, No. 4. -P. 38-39.

193. Valduriez P. Parallel Database Systems: Open Problems and New Issues // Distributed and Parallel Databases. -1993. -Vol. 1, No. 2. -P. 137-165.

194. Valduriez P. Parallel Database Systems: the case for shared-something // Proceedings of the 9th International Conference on Data Engineering, April 19-23, 1993, Vienna, Austria. -IEEE Computer Society, 1993. -P. 460-465.

195. Valduriez P., Gardarin G. Join and Semijoin Algorithms for a Multiprocessor Database Machine // ACM Transactions on Database Systems. -1984. -Vol. 9, No. l.-P. 133-161.

196. Van Vleck T. H., Clingen C. T. The Multics System Programming Process // Proceedings of the 3rd International Conference on Software Engineering, May 10-12, 1978, Atlanta, Georgia, USA. -IEEE Computer Society, 1978.-P. 278-280.

197. W. Hasan, D. Florescu, P. Valduriez Open Issues in Parallel Query Optimization // ACM SIGMOD Record. -1996. -Vol. 25, No. 3. -P. 28-33.

198. Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques. -IEEE Computer society, 1998. -P. 203-218.

199. Wilschut A.N., FlokstraJ., Apers P.M.G. Parallel Evaluation of Multi-Join Queries // Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995. -ACM Press, 1995.-P. 115-126.

200. Wunderling R., Zöckler M. DOC++. A Documentation System for C/C++ and Java. http://www.zib.de/Visual/software/doc++.

201. Xu Y., Dandamudi S.P. Performance Evaluation of a Two-Level Hierarchical Parallel Database System // Proceedings of the Int. Conf. Computers and Their Applications, Tempe, Arizona, 1997. P. 242-247.

202. Yu P. S., Cornell D. W. Optimal Buffer Allocation in A Multi-Query Environment // Proceedings of the Seventh International Conference on Data Engineering, April 8-12, 1991, Kobe, Japan, IEEE Computer Society, 1991. -P. 622-631.

203. Zipf G.K. Human Behavior and the Principle of Least Effort: an Introduction to Human Ecology. -Cambridge, Mass.: Addison-Wesley, 1949. -573 p.