Руководитель проекта Соколинский  Леонид  Борисович

Краткая аннотация Разработана модель DMM (Database Multiprocessor Model), позволяющая моделировать и исследовать иерархические аппаратные архитектуры параллельных систем баз данных. Разработана методика организации параллельного выполнения запросов в иерархических многопроцессорных архитектурах, использующая специальный оператор EXCHANGE. Оператор обмена EXCHANGE инкапсулирует в себе все механизмы, необходимые для реализации внутриоперационного параллелизма. Предложена оригинальная методика зеркалирования данных в иерархических системах баз данных, предполагающая введение функции меры зеркалирования данных. Эта функция отображает номер уровня в иерархии в коэффициент зеркалирования, который определяет меру зеркалирования данных для данного уровня иерархии. На основе данной методики разработан эффективный алгоритм балансировки загрузки. Разработан прототип параллельной СУБД Омега для многопроцессорных вычислительных систем с кластерной архитектурой. Исходные тексты прототипа свободно доступны в Интернет по адресу http://omega.susu.ru/prototype/. На базе прототипа проведены масштабные вычислительные эксперименты на вычислительном кластере Infinity (http://cluster.susu.ru). Проведены эксперименты по исследованию влияния перекосов в распределении данных на время выполнения запросов. Исследованы ускорение и расширяемость прототипа. Проведены эксперименты по сравнительному анализу быстродействия прототипа и СУБД Microsoft SQL сервер. За время выполнения проекта исполнителями опубликовано 14 печатных работ. Полные тексты опубликованных работ доступны по адресу http://omega.susu.ru/grants/rfbr_2003_03-07-90031/index.html#Публикации Результаты проекта докладывались на 9 научных конференциях, семинарах и совещаниях. Слайды презентаций сделанных окладов доступны по адресу http://omega.susu.ru/grants/rfbr_2003_03-07-90031/index.html#Апробация Руководителем проекта Л.Б.Соколинским защищена диссертация на соискание ученой степени доктора физ.-мат. наук. Полный текст диссертации доступен по адресу http://sok.susu.ru/dissertation/. Разработан WWW-сайт, посвященный проекту создания параллельной СУБД Омега: http://omega.susu.ru/. Создана web-страница, посвященная данному гранту РФФИ: http://omega.susu.ru/grants/rfbr_2003_03-07-90031/.

Полученные за отчетный период важнейшие результаты 1) Разработан прототип параллельной СУБД Омега для многопроцессорных вычислительных систем с кластерной архитектурой. Исходные тексты прототипа свободно доступны в Интернет по адресу http://omega.susu.ru/prototype/. 2) Разработана оригинальная модель DMM (Database Multiprocessor Model), позволяющая моделировать и исследовать иерархические аппаратные архитектуры параллельных систем баз данных. 3) Предложена формализация понятия "параллельная система баз данных'', базирующаяся на концепции виртуальных машин. На основе данной формализации разработан новый подход к классификации архитектур параллельных систем баз данных. Сформулированы требования к параллельной системе баз данных, служащие критериями для сравнения различных архитектур. Рассмотрены различные классы архитектур параллельных систем баз данных и проведен их сравнительный анализ. 4) Предложена методика зеркалирования данных в иерархических системах баз данных, предполагающая введение для иерархической системы функции меры зеркалирования данных. Эта функция отображает номер уровня в иерархии в коэффициент зеркалирования, который определяет меру зеркалирования данных для данного уровня иерархии. На основе данной методики разработан эффективный алгоритм балансировки загрузки. 5) Разработана методика организации параллельного выполнения запросов в иерархических многопроцессорных архитектурах, использующая специальный оператор EXCHANGE. Оператор обмена EXCHANGE инкапсулирует в себе все механизмы, необходимые для реализации внутриоперационного параллелизма. 6) На базе прототипа параллельной СУБД Омега проведены вычислительные эксперименты на кластере Infinity (http://cluster.susu.ru). Проведены эксперименты по исследованию влияния перекосов в распределении данных на время выполнения запросов. Исследованы ускорение и расширяемость прототипа. Проведены эксперименты по сравнительному анализу быстродействия прототипа и СУБД Microsoft SQL сервер. 7) Разработан подход к параллельной обработке XML-данных. Данный подход основан на отображении маркированного ориентированного графа, представляющего XML-документ в соответствии со стандартом DOM (Document Object Model) обработки XML-данных, в реляционное отношение, подвергаемое горизонтальной или/и вертикальной фрагментации. Параллельная обработка фрагментов данного отношения основана на использовании специального оператора обмена EXCHANGE, разработанного в рамках данного проекта. 8) Разработана технология отладки параллельных MPI-программ в среде Windows, базирующаяся на оригинальном эмуляторе обменов сообщениями по стандарту MPI. Процессы и сообщения между ними эмулируются с помощью потоков ОС Windows, что позволяет использовать встроенный отладчик среды программирования MS Visual C++. 9) Разработан и апробирован электронный учебный курс "Практикум по программированию параллельных систем баз данных". Материалы курса опубликованы в Интернете по адресу http://pdbs.susu.ru. 10) Разработана архитектура менеджера буферного пула, базирующаяся на использовании избыточного индекса буферного пула DIR и методе статических и динамических рейтингов страниц. Данная архитектура позволяет реализовать комбинированную стратегию замещения страниц, в максимальной степени учитывающую специфику работы систем баз данных. Исследована применимость алгоритма LFU-K, разработанного ранее в рамках данного проекта для параллельной СУБД Омега, для кэширования данных на прокси-серверах. Проведенные исследования трасс, полученных на реальных прокси-серверах, показали, что этот алгоритм может с успехом применяться и для кэширования данных на прокси-серверах. 11) Руководителем проекта Л.Б. Соколинским защищена диссертации на соискание ученой степени доктора физико-математических наук (см. http://sok.susu.ru/dissertation/). 12) По тематике проекта исполнителями опубликовано 14 печатных работ (2 статьи в научных журналах, 8 статей в сборниках, 2 статьи в продолжающихся изданиях, 1 диссертационная работа, 1 автореферат диссертационной работы). Результаты проекта докладывались исполнителями на 2 всероссийских и 6 международных научных конференциях и семинарах. 13) В рамках проекта подготовлены следующие информационные WWW-ресурсы: http://omega.susu.ru/index.html - web-сайт проекта разработки параллельной СУБД для мультипроцессорных вычислительных систем с кластерной архитектурой; http://omega.susu.ru/prototype/index.html - web-страница прототипа параллельной СУБД Омега и сопутствующих разработок; http://omega.susu.ru/grants/rfbr_2003_03-07-90031/index.html - web-страница данного проекта РФФИ; http://cluster.susu.ru/index.html - web-сайт высокопроизводительного вычислительного кластера Infinity; http://pdbs.susu.ru/index.html - web-сайт электронного учебного курса "Практикум по программированию параллельных систем баз данных".

Методы и подходы, использованные в ходе выполнения проекта МЕТОДЫ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ЗАПРОСОВ В ИЕРАРХИЧЕСКИХ МНОГОПРОЦЕССОРНЫХ АРХИТЕКТУРАХ. Разработана оригинальная методика организации параллельного выполнения запросов в иерархических многопроцессорных архитектурах, использующая специальный оператор обмена EXCHANGE. Оператор EXCHANGE может быть вставлен в любое место дерева физического плана выполнения запроса. Он позволяет перераспределять данные между процессорами в соответствии с семантикой вышестоящей (в дереве) реляционной операции. Оператор EXCHANGE инкапсулирует в себе всю специфику, связанную с параллелизацией запроса. Общая схема порождения параллельного плана выполнения запроса в иерархической системе выглядит следующим образом. Сначала формируется последовательный план. Последовательный план преобразуется в параллельный план первого (высшего) уровня путем формирования параллельных агентов. В каждый параллельный агент при этом встраиваются операторы EXCHANGE там, где это необходимо. Затем каждый параллельный агент первого уровня рекурсивно подвергается дальнейшей параллелизации и преобразуется в параллельный план второго уровня, состоящий из параллельных агентов второго уровня, в которые добавлены новые операторы EXCHANGE. Процесс повторяется до тех пор, пока не будет достигнут самый нижний уровень многопроцессорной иерархии. Предложенный подход позволяет внедрять параллелизм в последовательные СУБД и использовать последовательные алгоритмы выполнения реляционных операций. МЕТОДЫ ПАРАЛЛЕЛЬНОЙ И РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ ЗАПРОСОВ Предложена оригинальная методика зеркалирования данных в иерархических системах баз данных. Для иерархической системы вводится функция меры зеркалирования данных, отображающая номер уровня в иерархии в коэффициент зеркалирования. Коэффициент зеркалирования определяет меру зеркалирования данных для данного уровня иерархии. Для первого (самого нижнего) уровня иерархии коэффициент зеркалирования может быть равным единице. Это означает, что фрагментированные данные должны дублироваться на всех сыновьях узла. SMP система тривиальным образом всегда обеспечивает зеркалирование с коэффициентом 1, так как дисковый пул разделяется всеми процессорами. В случае, когда система имеет МРР архитектуру из n узлов, зеркалирование с коэффициентом 1 приводит к тому, что все n дисков содержат одни и те же фрагменты. Зеркалирование с коэффициентом 0.5 применительно к МРР архитектуре означает, что 50% каждого фрагмента, хранящегося на диске i, зеркалируется на остальных n-1 дисках. Функция меры зеркалирования строится таким образом, чтобы коэффициент зеркалирования убывал по мере повышения уровня иерархии. В простейшем случае функция репликации может иметь вид f(j)=(m+1-j)/m, где m – количество уровней в иерархии. Предложенный подход позволяет реализовать следующий эффективный алгоритм балансировки загрузки. Пусть, например, в МРР системе осуществляется зеркалирование данных с коэффициентом 0.5. Пусть R_i обозначает фрагмент отношения R, обрабатываемый i-тым узлом. Предположим, что фрагмент R_l обработан на 25%, в то время, как фрагмент R_k обработан на 100%. В этом случае k-тый процессор может немедленно начать обрабатывать те 50% фрагмента R_k, которые зеркалированы на l-том узле. ПРОТОТИП ПАРАЛЛЕЛЬНОЙ СУБД Разработан прототип параллельной СУБД Омега для многопроцессорных вычислительных систем с кластерной архитектурой. Входным языком прототипа является язык, базирующийся на реляционной алгебре. Прототип выполняет следующие основные функции: формирование последовательного плана исполнения запроса, преобразование последовательного плана в параллельный план, исполнение запроса. Прототипа включает в себя следующие подсистемы: интерпретатор запросов, генератор последовательных планов, параллелизатор, генератор физических планов и исполнитель. Интерпретатор выполняет синтаксический анализ текста запроса и строит дерево разбора, отражающее структуру запроса. Генератор последовательных планов преобразует дерево разбора в последовательный логический план выполнения запроса. Параллелизатор преобразует последовательный логический план в параллельный логический план, вставляя в соответствующие места дерева запроса операторы обмена EXCHANGE. Генератор физических планов преобразует логический план в параллельный физический план запроса.Исполнитель запроса осуществляет обход дерева физического плана и выполнение соответствующих алгоритмов, реализующих физические операции. Исходные тексты прототипа свободно доступны в Интернет по адресу http://omega.susu.ru/prototype/. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ НА КЛАСТЕРЕ INFINITY. На базе прототипа проведены масштабные вычислительные эксперименты на вычислительном кластере Infinity (http://cluster.susu.ru). Для проведения экспериментов разработан и реализован генератор тестовых баз данных. Проведены эксперименты по исследованию влияния перекосов в распределении данных на время выполнения запросов. Исследованы ускорение и расширяемость прототипа. Проведены эксперименты по сравнительному анализу быстродействия прототипа и СУБД Microsoft SQL Server. МОДЕЛИРОВАНИЕ И АНАЛИЗ ИЕРАРХИЧЕСКИХ АРХИТЕКТУР ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ. Разработана оригинальная модель DMM (Database Multiprocessor Model), позволяющая моделировать и исследовать иерархические аппаратные архитектуры параллельных систем баз данных. Модель DMM включает в себя модель аппаратной платформы, модель программной среды, стоимостную модель и модель транзакций. Детальное описание модели DMM приводится в техническом отчете, размещенном по адресу http://omega.susu.ru/reports/TR11-03-07-90031-Y3N1.pdf. Разработан эмулятор виртуальных мультипроцессоров баз данных (ЭВМБД). ЭВМБД представляет собой программный комплекс, позволяющий моделировать и исследовать произвольные многопроцессорные иерархические конфигурации в контексте задач баз данных класса OLTP. Это дает возможность исследовать широкий спектр перспективных гибридных и иерархических кластерных архитектур без больших затрат на их аппаратную реализацию. Основные результаты, полученные по данному направлению, опубликованы в работах [КостенецкийC_04], [КостенецкийC_05], [KostenetskiySK_05]. ИССЛЕДОВАНИЕ АРХИТЕКТУР ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ. Введено понятие виртуальной параллельной машины баз данных, которое может служить эффективным инструментом при проектировании сложных гибридных архитектур параллельных систем баз данных. Данный инструмент позволяет определять различные уровни абстракции при проектировании системной архитектуры. Этапы проектирования представляют собой иерархию виртуальных машин. Каждая следующая виртуальная машина реализует предыдущую. В целях классификации и сравнительного анализа архитектур современных параллельных систем баз данных проанализирован классификационный подход М. Стоунбрейкера, предложенный в середине 80-х годов ХХ века. Показано, что классификация Стоунбрейкера нуждается в определенном уточнении и обобщении. Данное обобщение и уточнение было нами выполнено путем использования абстракции виртуальных параллельных машин баз данных и введения дополнительных классов иерархических кластерных архитектур. Сформулированы и рассмотрены основные требования к параллельной системе баз данных. На основе сформулированных требований и обобщенной классификации Стоунбрейкера был проведен сравнительный анализ современных архитектур параллельных систем баз данных. Этот анализ показал, что наилучшие показатели имеет гибридные архитектуры класса CDN. Эксперименты, проведенные на базе системы Омега, подтверждают сделанный вывод. Основные результаты, полученные по данному направлению, опубликованы в работах [Соколинский_03], [Соколинский_04] [Sokolinsky_04a]. ИССЛЕДОВАНИЕ МЕТОДОВ ПОДДЕРЖКИ ПОЛЬЗОВАТЕЛЬСКИХ ТИПОВ ДАННЫХ В ПАРАЛЛЕЛЬНЫХ СИСТЕМАХ БАЗ ДАННЫХ Выполнено исследование методов поддержки пользовательских типов данных в параллельных системах баз данных. Предложен следующий оригинальный подход к параллельной обработке XML-данных. Фрагментация XML-данных основана на представлении XML-документа в виде маркированного ориентированного графа, вершинами которого являются информационные узлы XML-документа, а дугами - семантические ссылки между информационными узлами. Представление XML-документа в виде графа выполняется в соответствии со стандартом DOM (Document Object Model) обработки XML-данных. Полученный граф отображается в реляционное отношение, в котором хранятся атрибуты вершин и дуг графа (уникальный идентификатор дуги, уникальный идентификатор вершины, уникальный идентификатор родительской вершины, имя информационного узла, значение информационного узла). Данное отношение затем подвергается фрагментации. Поддерживается вертикальная и горизонтальная фрагментация. Параллельная обработка фрагментов данного отношения основана на использовании специального оператора обмена EXCHANGE, разработанного в рамках данного проекта. ТЕХНОЛОГИЯ ОТЛАДКИ ПАРАЛЛЕЛЬНЫХ MPI-ПРОГРАММ В СРЕДЕ WINDOWS. Предложено решение для отладки параллельных MPI-программ в среде Windows. Данное решение основано на эмуляции параллельных процессов и обменов данными между ними с помощью стандартных средств ОС Windows. Разработан эмулятор обменов сообщениями, который представляет собой динамически компонуемую библиотеку, интерфейс которой есть подмножество функций стандарта MPI, используемое в разработке прототипа СУБД Омега. Таким образом, эмулятор позволяет запускать прототип непосредственно из среды MS Visual C++ (без загрузчика) и использовать весь спектр средств встроенного отладчика. Переход от отладки к тестированию и обратно не требует изменения исходных текстов модулей и связан лишь с изменением параметров их компоновки. Эмулятор обеспечивает представление процессов, запускаемых на процессорных узлах, в виде процессов ОС Windows, каждый из которых представляет собой совокупность следующих потоков (нитей): мастер, отправитель, получатель и терминатор. Поток-мастер выполняет собственно код процесса. Поток-отправитель обрабатывает массив, элементами которого являются очереди сообщений, передаваемых другим процессам программы. Поток-получатель обрабатывает очередь сообщений, поступающих от потоков-отправителей других процессов программы. Поток-терминатор выполняет аварийное завершение всех процессов программы, если поток-мастер одного из процессов выполнил функцию MPI_Abort. Разработанный эмулятор имеет самостоятельное значение и может быть использован не только в рамках разработки прототипа параллельной СУБД, но и для отладки параллельных программ, выполняющих обмен сообщениями на основе стандарта MPI. Основные результаты, полученные по данному направлению, опубликованы в работе [Лепихов_04]. ЭЛЕКТРОННЫЙ УЧЕБНЫЙ КУРС "ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ". В рамках проекта разработан электронный учебный курс "Практикум по программированию параллельных систем баз данных" для студентов старших курсов и аспирантов, специализирующихся в области системного программирования. Целью практикума является разработка прототипа параллельной СУБД. Студенты обеспечиваются библиотекой функций прототипа, справочником по функциям библиотеки и набором контрольных тестов прототипа. С помощью готовых интерфейсов и библиотеки функций прототипа студентам необходимо выполнить реализацию модулей прототипа в порядке сверху-вниз в соответствии с модульной структурой прототипа. При проверке прототипа на контрольных тестах необходимо заменить библиотечные функции собственными реализациями. Разработанный электронный учебный курс был успешно апробирован на Зимней школе-практикуме молодых ученых и специалистов "Технологии параллельного программирования" (25 января-7 февраля 2004 г., Нижний Новгород). Материалы курса размещены в сети Интернет по адресу http://pdbs.susu.ru. Основные результаты, полученные по данному направлению, опубликованы в работах [ЦымблерСЛ_04], [Лепихов_04]. МЕТОДЫ И АЛГОРИТМЫ УПРАВЛЕНИЯ БУФЕРНЫМ ПУЛОМ Разработана оригинальная архитектура менеджера буферного пула, базирующая на использовании избыточного индекса буферного пула DIR и методе статических и динамических рейтингов страниц. Избыточный индекс буферного пула DIR представляет собой хеш-таблицу, обеспечивающую быстрый поиск страниц в буферном пуле. Кроме этого, он включает в себя атрибуты, содержащие статистическую информации об использованных страницах. Отличительной особенностью метода статических и динамических рейтингов является то, что суммарный рейтинг страницы формируется из двух независимых рейтингов: статического и динамического. Статический рейтинг задается пользователем при открытии набора страниц и позволяет организовать избирательное вытеснение страниц. Динамический рейтинг страницы вычисляется системой на базе статистических атрибутов и правила вытеснения, ассоциированного с данной страницей. Динамический рейтинг позволяет реализовать комбинированную стратегию замещения страниц, в максимальной степени учитывающую специфику работы систем баз данных. Исследована применимость алгоритма LFU-K для веб-кэширования. Алгоритм LFU-K был разработан ранее в рамках данного проекта для параллельной СУБД Омега. Выполнен анализ трасс, полученных на реальных прокси-серверах, для обнаружения набора свойств сетевого трафика. На основе проведенного анализа сделано заключение о целесообразности использования при Web-кэшировании политики LFU-K, которая опирается на информацию о динамических изменениях популярности документов. Выполнены вычислительные эксперименты, позволяющие сравнить эффективность предложенной политики с наиболее популярными алгоритмами замещения. Основные результаты, полученные по данному направлению, опубликованы в работах [ПрищепаС_03], [Prischepa_04], [Sokolinsky_04b]. ПУБЛИКАЦИИ ПО ПРОЕКТУ [КостенецкийC_04] Костенецкий П.С., Соколинский Л.Б. Моделирование и анализ иерархических архитектур параллельных систем баз данных // Международная научная конференция "Суперкомпьютерные системы и их применение" (SSA'2004): Доклады конференции (26-28 октября 2004 г., Минск). -Мн.: ОИПИ НАН Беларуси. -2004. -C. 116-120. [КостенецкийC_05] Костенецкий П.С., Соколинский Л.Б. Моделирование иерархических архитектур параллельных систем баз данных // Научный сервис в сети Интернет: технологии распределенных вычислений: Труды Всероссийск. науч. конф. (19-24 сентября 2005 г., г. Новороссийск). -М.: Изд-во МГУ. -2005. -C. 21-24. [Лепихов_04] Лепихов А.В. Реализация функций стандарта MPI для эмуляции обменов сообщениями между узлами многопроцессорной вычислительной системы // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы четвертого международного научно-практического семинара и Всероссийской молодежной школы. -Самара: Изд-во Самарского научного центра РАН. -2004. -C. 179-180. [ПрищепаС_03] Прищепа В.В., Соколинский Л.Б. Эффективный алгоритм кэширования для прокси-серверов сети Интернет // Научный сервис в сети Интернет: Труды Всероссийск. науч. конф. (22-27 сентября 2003 г., г. Новороссийск). -М.: Изд-во МГУ. 2003. C. 175-178. [Соколинский_03] Соколинский Л.Б. Классификация и анализ параллельных архитектур систем баз данных // Алгоритмы и программные средства параллельных вычислений: [Сб. науч. Тр.]. -Екатеринбург: УрО РАН. -2003. -Вып. 7. -C. 185-216. [Соколинский_04] Соколинский Л.Б. Обзор архитектур параллельных систем баз данных // Программирование. -2004. -№6. -C. 1-15. [ЦымблерСЛ_04] Цымблер М.Л., Соколинский Л.Б., Лепихов А.В. Прототипирование параллельной СУБД как основа учебного курса по параллельным системам баз данных // Международная научная конференция "Суперкомпьютерные системы и их применение" (SSA'2004): Доклады конференции (26-28 октября 2004 г., Минск). -Мн.: ОИПИ НАН Беларуси. -2004. -C. 212-217. [KostenetskiySK_05] Kostenetskiy P.S., Sokolinsky L.B., Kulig A. Simulating multiprocessor database system architectures // Proceedings of Spring Young Researcher’s Colloquium in Databases and Information Systems (SYRCoDIS'2005). June 1-2, 2005. Research-in-progress reports. -St.-Petersburg, Russia: VVM.com.Ltd. -2005. -P. 25-27. [Prischepa_04] Prischepa V.V. An Efficient Web Caching Algorithm Based on LFU-K Replacement Policy // Proceedings of the Spring Young Researcher's Colloquium on Database and Information Systems (St. Petersburg, May 27-28, 2004). -SPb.: NIIMM. -2004. -P. 46-49. [Sokolinsky_04a] Sokolinsky L.B. Survey of Architectures of Parallel Database Systems // Programming and Computer Software. 2004. Vol. 30. No. 6. P. 337-346. [Sokolinsky_04b] Sokolinsky L.B. LFU-K: An Effective Buffer Management Replacement Algorithm // Database Systems for Advances Applications, 9th International Conference, DASFAA 2004, Jeju Island, Korea, March 17-19, 2004, Proceedings. Lecture Notes in Computer Science, Vol. 2973. -Springer. -2004. -P. 670-681.

Адреса (полностью) ресурсов в Internet, подготовленных авторами по данному проекту http://omega.susu.ru/index.html http://omega.susu.ru/prototype/index.html http://omega.susu.ru/grants/rfbr_2003_03-07-90031/index.html http://cluster.susu.ru/index.html http://pdbs.susu.ru/index.html