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

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

АБРАМОВ Евгений Викторович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И КОМПЛЕКС ПРОГРАММ ДЛЯ ПК-КЛАСТЕРОВ КОНСЕРВАТИВНЫХ БАЗ ДАННЫХ

Специальность 05 13 18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Казань - 2008

Рабо га выполнена в Казанском государственном техническом университете

им АН Туполева

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

доктор физико-математических наук, профессор Райхлин Вадим Абрамович

Официальные оппоненты

доктор технических наук, профессор Столов Евгений Львович

доктор технических наук,

профессор Емалетдинова Лилия Юнеровна

Ведущая организация НИИ математики и механики им Н Г Че-

ботарева (г Казань)

Защита состоится « 29 » февраля 2008 г в 14 00 часов на заседании диссертационного совета Д 212 079 01 в Казанском государственном техническом уни-зерсшегеим АН Туполева по адресу 420111, г Казань, ул К Маркса, 10

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им А Н Туполева

Автореферат разослан « /9 _» января 2008 г

Ученый секретарь диссертационного совета

доктор физико-математических наук, профессор ПГ Данилаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Непрерывный рост объемов баз данных ставит на повестку дня задачу разработки эффективных параллельных СУБД Реальные финансовые ограничения заставляют искать альтернативу мэйнфреймовым платформам. Хорошей альтернативой является кластерная технология Использование аппаратно-программного обеспечения широкого применения (ПК-кластеры или Вест>и(/"-технология) еще более актуализирует эту задачу.

Научная задача диссертационной работы Разработка и исследование высокоэффективных кластерных параллельных СУБД, реализованных по Вео-м>и//-технологии

Цель работы: Построение математических моделей, создание комплекса программ и выработка практических рекомендаций по построению ПК-кластеров баз данных (БД) Решение общей научной задачи и достижение поставленной цели связывается с решением следующих частных задач

- Обобщение мирового опыта построения параллельных СУБД кластерного типа и решение на этой основе задачи внешнего моделирования

- Построение процедурной модели синтеза ПК-кластеров БД как необходимой компоненты внутреннего моделирования

- Разработка с учетом мирового опыта исследовательского прототипа параллельной СУБД как одной из осноЬных компонент внутреннего моделирования и как инструментального средства модельного исследования

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

Методы исследований. Решение указанных задач проводилось на основе методологии конструктивного моделирования систем с использованием методов модальной и нечеткой логик, семантики Крипке, методов обработки результатов эксперимента, теории временных рядов Для установления релевантности предложенной темпорально-нечеткой процедурной модели был разработан исследовательский прототип параллельной СУБД С/м5?еги с использованием методов параллельного программирования

Научная новизна работы

- Развитие элементов теории параллельных СУБД на платформе ПК-кластеров.

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

- Выявление зависимости границы масштабируемости ПК-кластеров БД от объемов баз данных

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

Практическая значимость.

- Разработанный исследовательский прототип параллельной СУБД Clusterix после его доведения до уровня действующего прототипа может быть использован для решения практических задач, требующих больших вычислительных мощностей

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

Результаты диссертации внедрены в учебный процесс КГТУ им А Н Туполева (КАИ) как учебное пособие «Параллельные СУБД. Компьютерный практикум» Его успешная апробация проведена на лабораторных занятиях по дисциплине «Параллельные вычисления» в весеннем и осеннем семестрах 2007 г

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

- систематика исследований в области параллельных СУБД и решение задачи внешнего моделирования;

- темпорально-нечеткая процедурная модель синтеза ПК-кластеров БД;

- разработка исследовательского прототипа параллельной СУБД Clusterix,

- результаты модельных исследований

Апробация работы. Основные результаты работы докладывались и обсуждались на Казанском научном семинаре «Методы моделирования» (Казань, 2001-2007 гг), V Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, ,2002 г ); Международной научно-технической конференции IEEE AIS'03 (Геленджик, 2003 г), Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» (Москва, 2005 г ), Московской секции Международного семинара ACM SIGMOD (МГУ им. Ломоносова, Москва, 2005 г), VII Международной конференции-семинаре «Высокопроизводительные параллельные вычисления на кластерных системах» (ННГУ им Н И Лобачевского, Нижний Новгород, 2007 г ).

Публикации. Основное содержание диссертации отражено в 10 печатных работах Среди них 6 статей, 3 из которых в журнале из перечня ВАК и 4 тезисов докладов

Структура и объём диссертации. Диссертационная работа изложена на 115 страницах машинописного текста, содержит 35 рисунков и 11 таблиц, со-

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

СОДЕРЖАНИЕ РАБОТЫ

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

Работа выполнена в рамках направления конструктивного моделирования систем, развиваемого в КГТУ им А Н Туполева под руководством профессора В А Райхлина Процесс синтеза рассматривается с системных позиций в предположении, что синтезируемый объект моделирует поведение некоторой гипотетической системы Моделирование системы проводится в рамках соответствующей модели синтеза, или S-модели (S - от Synthesis) В силу объективной неопределенности такую модель приходится строить неформально с привлечением эвристики

Характерной особенностью S-модели является постулирование свойств эффективной реализации системы Постулаты являются основой теории Но они всего лишь нестрого индуктивно обобщают накопленный опыг Поэтому система постулатов должна быть открытой

Конечной целью S-моделирования является разработка конструктивного метода, т е процедуры синтеза Эта процедура формируется на основе теории (принятых постулатов) итеративно с учетом результатов модельного эксперимента

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

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

Первыми рассматриваются проекты машин баз данных RAP (Ozkarahan, университет Торонто, 1976), DIRECT (DeWitt, университет Висконсина, 1977), GAMMA (DeWitt, 1984), GRACE (Kitsuregawa, 1983), SDC (Kitsuregawa, 1980e) Данные проекты во много определили развитие современных параллельных СУБД Именно в них были предложены алгоритмы распределения данных, реализованы параллельные алгоритмы выполнения реляционных операций Далее представлены современные коммерческие системы параллельной обработки запросов к базам данных Teradata, Oracle, Informix Обзор завершается рассмог-

рением исследовательских проектов последних лет MySQL Cluster (2004), PGCluster, Омега (JIБ Соколинский, 1997), NEDOIOO (Oguchi, Kitsuregawa, 1996)

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

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

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

- обработка запроса осуществляется на основе ограниченного множества реляционных операций по схеме select-project-join Принятый план обработки запросов — регулярное дерево,

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

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

- применение вертикального (конвейерная обработка) и горизонтального параллелизма,

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

- максимальное использование готовых программно-аппаратных решений Реализация низкоуровневых операций с помощью стандартной СУБД.

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

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

КОНЦЕНТУАЛЬНЫЙ ФРЕЙМ « ПАРАЛЛЕЛЬНАЯ СУБД »

1 Я И 1 1 г КС | | хд 1 1 ОС з 1

г г г

Фрейм ЯИ Фрейм РФК Фрейм ХД Фрейм ООЗ

|Вни лЯЗЙ ВятЯЗ 1 1 НИЗ | |СР |ФМД||ОС ^sjlocxl |РУО||П< ХЗ||СОИ||РРО!

1 у т т г + ' ▼ ▼

МНОЖЕСТВА АЛЬТЕРНАТИВ РЕШЕНИЙ

Рис I Рассматриваемая фреймовая модель

На рисунке фреймы концептуального уровня

ЯИ - языковый интерфейс, РФК - распределение функций между компонентами, ХД - хранения данных, ООЗ - организация обработки запросов, фреймы дочернего уровня

ВншЯИ - типа внешнего языка, ВнтЯИ - тип внутреннего языка, ПИЗ -стратегия параллельного исполнения запросов, СРФ - способ распределения функций, ФМД - физическая модели данных, ООД - организация доступа к данным, OCX - организация структуры хранения данных, РУО - распределение процессоров между уровнями обработки, ПОЗ - план обработки запросов, СОИ - среда обмена информацией, РРО - реализация реляционных операций

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

А, В, С, D, E,F,G,HdW

как внешней компоненты искомой модели Здесь W - искомая архитектура кластера, А — внешний язык запросов есть SQL; В - внутренний язык запросов включает ограниченное подмножество реляционных операторов (селекция, проекция, соединение), С - запрос расщепляется на несколько процессов реализуемых на разных процессорах, D - база данных распределяется между несколькими НМД с применением механизма хеширования, Е - имеется нижний (операции ввода-вывода, селекции и проекции) и верхний (операции проекции и соединения) уровни обработки, F - граф обработки любого запроса формируется в динамике оптимизирующим претранслятором, который расщепляет SQL-запрос пользователя на MySQL-фрагменты отдельных исполнительных уровней, G - используется стратегия МРР (обмен сообщениями), реализуемая на базе сети FastEthernet, Н - реализация реляционных операций средствами MySQL

Поиск решений для фрейма РУО относится к компетенции внутреннего моделирования Для организации этого поиска строится специальная процедурная компонента модели.

Таким образом, задача моделирования сводится к эффективному распределению процессоров между верхним и нижним уровнями обработки кластера БД при заданном числе процессоров кластера N и УБд

В п 2 2 определены дискретные состояния модели Обозначены задачи внутреннего моделирования

Общее число процессоров в кластере (включая узел управления Host) N = 2n + 1, п = 1,2, Верхний исполнительный уровень образуют процессоры JOIN (выполняют операции соединения и проекции) числом р Нижний - процессоры I/O (операции селекции и проекции) числом q = h - р, где h = N - 1 = 2п По условию k"1 = p/q е {0, Уз, lA, 1}

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

I) разработка процедурной компоненты модели синтеза,

2) разработка исследовательского прототипа параллельной СУБД на платформе ПК-кластеров,

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

4) на основе анализа информации, полученной в ходе тестирования кластера, установление существования решения поиска релевантной базы знаний и закономерности масштабирования

В п 2 3 предлагается процедурная компонента модели по выбору адекватной текущей нагрузке конфигурации кластера (распределение процессоров между уровнями обработки) Вектор внешних параметров модели, определяющий характер нагрузки при заданной базе данных, - это некоторая интегрированная характеристика потока запросов, не зависящая от k"1, h и особенностей применяемой СУБД К числу таких параметров предлагается отнести

- Средняя относительная сложность Q одного запроса в текущем пакете запросов (Q — от Quantity —количество)

Q-iLq.ViwqraH [0,1] 1=1

Здесь w - число запросов в пакете, q, - число отношений БД, обрабатываемых в i-запросе пакета

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

и = <£ £>,)/0»Увд) е [0,1], 1=1

где Vj, - объем j-отношения, обрабатываемого в 1-запросе

- Коэффициент сжатия D данных в результате первичной обработки текущего пакета запросов (D — от Decrease—уменьшение)

1=1 у-1 1=1 J-1

Через и,, обозначен объем отношения, получаемого в результате обработки на первом уровне отношения объемом V,,

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

Гипотеза 1, Введенные внешние параметры первичны они определяют степень влияния на производительность всех факторов в совокупности Характер этого влияния и само множество внутренних факторов остаются неизвестными

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

Базой развития модельной процедуры стал ряд соглашений модальной (немонотонной) логики Имея дело с неполной, неточной или изменчивой информацией, наши рассуждения предположительны, всего лишь правдоподобны и потому должны быть модифицируемыми Соответствующие им логические системы вывода называются немонотонными Название «модальная логика» отражает тот факт, что в таких системах используются операторы модальности Пусть £ - модальный язык, включающий модальный оператор общности □ (необходимо, предполагается, известно). Классический вариант формул языка £ имеет вид продукций

о[Р,л .лРщЭУ, v vYJ Их левая часть - условие (антецедент), правая — действие (консеквент), Р, и Yj - некоторые предикаты Использование дизъюнкций в консеквенте обычно запрещают С понятием модальности связывается семантика «возможных миров» (семантика Крипке) В этой семантике универсум W — множество возможных миров {s, t, u, }, связанных отношением доступности R Факт доступности мира j после i обозначается как iRj, i,j eW Пара (W, R) называется структурой, тройка (W, R, J) - моделью, или интерпретацией структуры Здесь J — отображение из Wx£ ("х" - знак декартова произведения) в {И, J1}, которое для каждого мира со е W любой формуле р е £ сопоставляет определенное значение истинности J(®, р)

В дальнейшем рассматривается случай трех миров W = {s, t, и} Факт предпочтительности в смысле R одного мира, например s, перед двумя другими обозначим как sR(t,u)

Определение 1. Определим sR(t,u) как VsVtVu o[sRt asRu =>sR(t,u )J По условию отношение R удовлетворяет аксиомам транзитивности VsVtVu o(sRt AtRu =>sRu)

Утверждение 1.

VsVtvu D[(sRt asRu) V (sRt AtRu)v (sRu AuRt) sR(t,u)]

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

Определение 2. Определим универсум W = {s,t,u} как множество миров, каждому из которых отвечает свой набор рабочих тестов TW Эти миры связаны между собой отношением R предпочтения х / j в контексте «скорее 1, чем)», 1 5tj, или «1 перед]»

Отображение универсума W на множество состояний модели (к"'=0 - «линейка», к =1 - «симметрия», к"'=1/2 или 1/3 - «асимметрия») считае1ся известным и однозначным Поэтому задача моделирования сводится к выбору мира из W, принадлежность к которому для данного теста TW наиболее правдоподобна Для оценки степени правдоподобия используется утверждение 1 В новых обозначениях

□[(s/t л s/u) v (s/1 л t /и) v (s/u а и/1) => s/(t,u)] (1)

Ядро базы знаний формируется в виде продукций:

□[(Р0лРилРо)а => i/j ]; i,je{s,t,u}; i * j. (2)

Здесь Pf (t = Q, U, D) и i/j - предикаты, Pt = ze(X), ze e {II, M, L} - множество значений лингвистических переменных: Н — высокое, М — среднее, L — низкое. Антецеденты формул интерпретируются на основе «избранных моделей» с учетом мыслимых альтернатив характеристик' <Q, U, D>. Каждый вариант включает 6 правил с консеквентами s/t, s/u, t/s, t/u, u/s, u/t. Общее число вариантов С2i* ц6 > 2*108. Это обуславливает трудоемкость поиска релевантной базы знаний.

Предлагаемая модельная процедура основана на использовании аппарата ' нечетких множеств. Нечеткое множество для Р{ = ze е {H,M,L}, 1 е {Q, U, D} определяется как {< ц(хе) /xj>} (рис.2).

\

к ->

Рис.2. Избранный вид функции принадлежности

Здесь |л(хе) е [0, 1] - функция принадлежности, хе е. [О, 1] - результат перевода в конкретные цифровые значения для данного рабочего теста Т\У. Переход к нормированной переменой хс позволяет унифицировать встраиваемые в инструментальную среду типовые зависимости Цп.м.ьОО- По ним определяются значения [1г , ■/. е {Н,М,Ь}, для каждого Ре. Подстановка этих значений в формулы из £ вместо соответствующих предикатов используется для оценки степени правдоподобия вывода

(ТЮх =>я/1.

Коэффициент правдоподобия Кй интерпретации (1"\У)5(

Кд = ^ \h-t-

При этом конъюнкция вычисляется через произведение

, ^Цй =П ■

х

Согласно (1), степень близости К5 теста Т\У миру 8 из * = {в, I, и} будем оценивать по ранее найденным К«, К5и, К„, и К,«:

К, = (К5(*К5Ц) V (К5,*К«Й) V (К5„*КЦ|). При этом значение дизъюнкции вычисляется как среднее арифметическое компонент:

К3 = [ (Кя*К8и)+ (К^К.п) + (К511*К,„) ] /3.

Аналогично вычисляются К{ и Ки. Решение

е 1, 1е {б, и, г},

принимается из сравнения альтернатив по критерию максимума К,.

Характерной особенностью данной модели является использование небольшого количества внешних параметров По условию именно они определяют степень влияния на производшельность всех факторов в совокупное ги. Характер этого влияния остается неизвестным Из-за неполноты информации задача формирования релевантной базы знаний в терминах внешних параметров оказывается трудно разрешимой Использование утверждения 1 повышает чувствительность модели, так как дает «многоракурсные» оценки Но модель является локальной Бе приходится строить каждый раз для различных потоков запросов, объемов баз данных УЬд и размеров кластера N.

В третьей главе «Разработка параллельной СУБД С1ив1епх» решается одна из основных задач внутреннего моделирования - разработка исследовательского прототипа параллельной СУБД

Из первой главы становится ясным, что параллельной СУБД, ориентированной на аппаратно-программные компоненты широкого применения, на настоящий момент не существует Поэтому встала самостоятельная и весьма серьезная предзадача разработки релевантной основной задаче исследований параллельной СУБД, названной С1ш1епх

В п 3 1 излагаются основные принципы построения прототипа Основным из которых является регулярный план обработки запроса ( рис 3).

Ямса

Рис З.План обработки запроса

Данный план реализует выполнение запроса по схеме sclect-pioject-join В прототипе реализовано несколько уровней обработки Уровень первичной обработки (уровень I/O) выполняет функции хранения горизонтально распределенных отношений базы данных и реализует реляционные операции селекция (select), проекция (project) Основным предназначением данного уровня является фильтрация данных исходного отношения посредством операций селекции и проекции перед передачей их на вторичный уровень обработки

Уровень вторичной обработки (уровень JOIN) предназначен для выполнения операции соединения (join) Здесь реализован параллельный алгоритм эк-висоединения с применением механизма динамической сегментации отпоше-

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

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

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

Для выполнения реляционных операций каждый процессор обработки оснащен стандартной сервером СУБД MySQL. На него возлагаются низкоуровневые функции управления данными (работа с файлами БД, индексами и др.). Для организации распределенной обработки процессоров обработки разработаны соответствующие программные модули, которые были написаны на языке С++ и погружены в ОС Linux Red Hat 7.2. Межсетевое взаимодействие модулей осуществляется на основе библиотеки сетевого программирования через «соке-ты».

В п. 3.2. содержится описание программных модулей системы (рис.4). В качестве тестовой базы данных, на которой выполняется тестирование системы выбран тест TPC-D. Данный тест описывает некую гипотетическую систему обработки отчетов. Его основными особенностями является: запросы с интенсивным использованием операции соединения и агрегации, отсутствие модификации данных.

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

Рис. 4. Состав и взаимодействие модулей кластера

Схема базы данных этого теста содержит 8 отношений При тестировании используются БД объемами 575, 788 и 1000 Мбайт

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

В п 3 4 представлен алгоритм динамического сегментирования, являющийся основным этапом выполнения параллельного соединения (hash join), рассмотрены особенности его реализации в среде MySQL

Суть динамического сегментирования заключается в формировании для каждого из двух отношений (S и R ), участвующих в операции соединения, непересекающихся сегментов кортежей (s=ys(, Л = (JR(, ¡ = /(vg) - функция

1 ч

хеширования, I < ; < ^ ) Разделение осуществляется применением функции хеширования к значениям атрибутов vg кортежей, участвующих в соединении. В качестве такой функции используется деление по модулю q Тогда соединение сегментов R, и Sj с разными номерами (г Ф j) всегда будет давать пустое результирующее множество Поэтому операцию соединения следует выполнять только между сегментами R, и S, параллельно на q процессорах Такая сегментация выполняется средствами программных модулей (I/O и JOIN), непосредственно операция соединения — средствами СУБД MySQL Особенностью данного алгоритма является реализация операции соединения только по равенству атрибутов (эквисоединение) Результат выполнения динамического сегментирования формируется непосредственно в виде временных отношений СУБД MySQL, что потребовало применения системных функций СУБД MySQL Это позволило значительно сократить накладные расходы интерфейсной составляющей

Для сбора статистической информации о ходе выполнения запросов в системе была разработана специальная подсистема описанная в п.З 5 Подсистема сбора статистической информации представляет собой распределенную по узлам кластера систему, построенную по технологии «клиент-сервер» Основной ее функцией является передача в реальном времени коротких сообщений о выполнении текущих операций с процессоров обработки на процессор управления Наиболее важными операциями, информация о которых передается на MONITOR, являются- выполнение SQL-запроса, работа с индексами, передача данных по сети, динамическое сегментирование и др.

Полученная от подсистемы сбора статистики информация служит для визуального анализа динамики работы кластера Для этого была разработана программа визуализации StatVisio Chisterix, описанная в п 3 6

Пользовательский интерфейс программы StatVisio Clusterix представлен на рис 5 По оси абсцисс отложено время работы системы, по оси ординат -контрольные точки В верхней части диаграммы располагаются контрольные точки, относящиеся к MONITOR, затем идут контрольные точки для модулей I/O, SORT и JOIN Каждый отдельный запрос в пакете имеет свою цветовую окраску Это позволяет отличать одни запросы от других Программа предоставляет удобный интуитивно понятный интерфейс, который позволяет визуально оценить работу системы при выполнении пакета запросов, увидеть «узкие

моста» системы. Данная программа оказала существенную помощь в оптимизации работы кластера на этане его разработки.

1'ио. 5.Нользовательский интерфейс программы StatVisio Clusterix

В u.3.7 представлена подсистема конфигурирования кластера. Основная функция подсистемы -■ хранение информации о различных конфигурациях кластера и системной КД. БД содержит значения параметров программных, моделей (IP-адреса и номера сетевых портов), но которым при старте кластера определяется текущий состав и взаимосвязи узлов кластера. При запуске системы программные модули инициируются в соответствии с текущей конфигурацией.

В системе реализовано три типа конфигураций: «линейка» (рис. б), «симметрия» (рис. 7), «асимметрия» (рис.8). На каждом из узлов кластера может быть запушен один или несколько программных модулей, реализующих функции уровня I/O (irun) и/или JOIN (Jruri). Конфигурация «линейка» характеризуется тем, что па каждом узле кластера функционируют оба модуля (в режиме разделения нремени). В конфигурации «симметрия» на каждом процессоре функционирует' только одии из модулей. При этом количество процессоров, на которых функционируют модули irun и jrun, одинаково (р = q). В конфигурации «асимметрия» количество процессоров JOIN, меньше числа процессоров I/O

(р<ч)-

Рис. 6. Архитектура «линейка»

Рис. 7 Архитектура «симметрия»

Рис. 8. Архитектура «асиммегрия» В п.3.8 рассмотрены основные подходы к реализации нрстранслятора, ос~ новной функцией которого является трансляция запросов пользователей в команды регулярного плана обработки (рис. 3). Особенность заключается и том, что запрос пользователя и множество команд плана обработки, его реализующих, являются SQL-запросами. Запросы пользователей, обрабатываемые в сис теме, соответствуют следующему шаблону SQI,-запроса:

select список атрибутов from список отношений [where условие 1 [[ and yciloouejc ] ...]] [ghoijp by список атрибутов] [order 1iy список атрибутов].

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

-- Предикаты запроса вида: <иияотношения, ими атри6ута><условие><копстаита> реализуются на уровне I/O. Данное условие выполняет фильтрацию данных па более рашшх стадиях обработки данных. Это позволяет уменьшить объем данных при маршрутизации данных по сети между узлами кластера на более поздних стадиях обработки.

■ - Предикаты запроса вида: <отношенпе А.атрибут 1}><усло(ше><отношеиие Л.атрибут ('> реализуется на уровне I/O, т.к. оно является условием селекции.

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

о

ловие касается команд как I/O, так и JOIN Данное условие обеспечивает максимальную фильтрацию данных, при продвижении по дереву обработки запроса, что обеспечивает уменьшение объемов данных, передаваемых по сети

- У временных и промежуточных отношений автоматически создаются индексы по атрибутам, участвующим в операции эквисоединения

- Первым обрабатывается отношение, размеры которого максимальны Этим условием достигается уменьшение объема данных, пересылаемых по сети

- План обработки строится из условия уменьшения размеров обрабатываемых данных по ходу выполнения плана обработки

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

- Перенос части функций агрегации с уровня SORT на более низкий уровень (уровни I/O и JOIN) Это обеспечивает более высокую степень параллелизма при выполнении функций агрегации

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

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

В пЗ.10 перечислены системные лог-файлы кластера, их описание и структура

В четверной главе «Модельное исследование» представлены результаты модельного эксперимента В п 4 1 определены условия проведения эксперимента

• Рассматриваемые кластеры строятся из стандартных сетевых компонентов широкого применения

• Базы данных (БД) консервативны, т е динамическое обновление данных в них отсутствует Условие консервативности системы означает, что характер нагрузки должен отвечать тестам без операций insert, update, delete (и в этом смысле подобным тесту TPC-D)

• Объемы БД (Убд) не превышают 1 Гбайт

• Параметры потока запросов (характеристика «нагрузки») меняются во времени сравнительно медленно, т е эволюционно

• Поток запросов стационарен в том смысле, что его параметры изменяются в пределах, выявленных на этапе тестирования Это означает отсутствие тренда параметров, но не исключает наличие (квази)-периодической и случайной составляющих

• Все проведенные в этой главе экспериментальные результаты относятся к последней версии исследовательского прототипа СУБД Clusterix

• Кластер состоит из 15 персональных компьютеров Pentium IlI/0,8GHz/128MB/10GB, объединенных локальной сетью 100Mb/s FastEthernet с помощью коммутатора D-Link DES-1016D.

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

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

т,с.

■"—симметрия •-линейка А - вссим отри я 1/2 о— ассиметрия 1/3

О 2 4 6 8 10 12 14 16

Рис. 9.Среднее время выполнения пакета запросов на БД объемом 575 Мбайт

Согласно этим результатам при h<16:

- для любой архитектуры производительность монотонно повышается с ростом h, если h<hu, где Ьв - число узлов кластера в точке ветвления (ветвление проявлено только при Убд = 575 Мбайт - см. рис. 9, где hB»12). При этом значительный эффект наблюдается в сравнительно узком диапазоне значений h;

- архитектура «линейка» для БД с объемами 788 и 1000 Мбайт не имеет альтернатив. Альтернатива «линейке» наблюдается только для БД объемом 575 Мбайт при h=14. Но здесь переход к новой архитектуре малоэффективен.

По результатам проведенных исследований выдвигается

Гипотеза 2. Если параметры нагрузки кластеров консервативных баз данных, погруженных в среду параллельной СУБД Clusterix, фиксированы, то существует независимое от архитектуры граничное число страниц m = mG, при котором объемы работ на кластере всегда близки к минимальным, а производительность - к максимальной. Значение та растет с увеличением У$д.

Согласно гипотезе, параметр та = qa определяет границу эффективной масштабируемости

hG = (l+k-')m0,

ctoto для каждой архитектуры. Она максимальна для «симметрии» : (hG)c„M = 2in0.

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

Тестовый этап. Пусть имеем временной ряд запросов, 'отвечающий некотором} тесту TW, Пронумеруем запросы в порядке их поступления. 1, .. , w, w+1, , К Здесь К - объем теста, w - размер скользящего окна Сначала окно охватывает запросы от 1 до w Затем — от 2 до (w + I) И т д Общее число позиции окна в рассматриваемом тесте равно (К - w + 1) Для получения приемлемой погрешности целесообразно принять w а 5

Любой тест в целом обрабатывается на трех вариантах архитектуры - «линейка», «симметрия», «асимметрия» Для каждого варианта измерительная система кластера фиксирует динамику событий Это позволяет экспериментально определить оптимальные по производительности «оконные» архитектуры при практически автономной (если wä 5) обработке ряда запросов, выделяемого каждой позицией окна Архитектура, релевантная тесту в цепом, безусловно совпадает с оценками для подавляющей части окон И так — для всех тестов

После этого в соответствии с локальной базой знаний первого приближения для всех позиций окон в каждом тесте находятся модельные оценки их принадлежности тому или иному миру Найденные оценки сравниваются с полученными экспериментально Если для каждого теста большей частью модельные оценки совпадают между собой и с результатами эксперимента, то эти оценки правильно определяют приоритетную архитектуру, и сформированная база знаний релевантна рассматриваемому потоку Иначе база знаний корректируется, вычисления повторяются И так до тех пор, пока не будет выполнено условие релевантности. В результате исследований для УБд = 575 Мбайт и h = tri(, = 8 (кГ'ас=!/з) была эвристически построена локальная база знаний процедурной модели (2)

d(MaHaM =>s/t), d(MaHaL =>t/s), □(LaHaL =>s/u), d(LaLaM du/s), (3)

□(HaHaH =>t/u), d(MaHaH Du/t) В табл 1 представлены результаты натурного и модельного экспериментов для 5 вариантов перестановок каждого из сформированных тестов на множестве позиций окон размерами w = 5 - 10 (всего - 225 окон)

Таблица 1

14-запросная выборка теста TPC-D, h=8 Спецтест длины 14 из 4 запросов теста TPC-D, h=8

k 0pt Гехр г, Г!Сн1 Гор Гц od texp сек

прав общ прав Общ

0 225 219 219 - - - 481

1/3 - - - - - - 318

1 - - 6 225 225 225 220

В таблице

гсхр - число позиций окон с данным к"'ор( по данным натурного эксперимента на кластере, гтой - число правильных (прав) и общее (общ) число распознаваний моделью для того же к !ор[, 1схр - среднее время обработки спецтеста в целом

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

Таблица 2

По окнам, V/ = 5 — 10 По тесту в целом = 14)

По окнам с к_10р1 ^ехрср сек

к"1 Гехр ^тск) (эксперимент) к"' Гтос! *^ехр ср

к"' Т-ехр ср

0 0,96

0 41 225 1/з 1,00 0 5 632 1,10

1 1,42

0 1,11

1/з 153 - 1/з 1 00 Уз - 572 1 00

1 1,16

0 1,17

1 31 - 1/з 1,00 1 - 704 1,23

1 0,95

Для большинства практических применений совсем не обязательно ре-конфигурировать кластер, если ожидаемый от такого действия выигрыш в производительности составит не более 10 - 15 % Поэтому с фактом ошибочном ассоциации моделью (3) спецтеста для «асимметрии» длины 14 из 3 запросов теста ТРС-О, Ь=8 (см табл.2, случай 5 перестановок) можно примириться

В табл 2 гехрср- относительные результаты усреднения экспериментальных времен обработки на множествах соответствующих окон (отнесенные к случаю «асимметрии») Но если выигрыш в 10 — 15 % существен, то база знаний (3) требует уточнения Сделать это эвристически совсем не просто, так как на поверку модель оказывается чрезвычайно чувствительной к перестановкам

Моделирование в процессе работы системы Здесь локальная база знаний фиксирована По-прежнему используется метод «скользящего окна» размером V/ на выборке длиной К , но экспериментальная проверка оптимальности выбранной архитектуры не проводится Архитектура, приоритет которой подтвержден моделью, считается адекватной нагрузке на весь установочный период

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

Графики рис 11 представляет экспериментальные и модельные результаты, полученные для «двойного» теста длины 28 как конкатенации двух тестов табл 2 длиной 14 каждый

На рис 10 6 — относительное число «оконных» результашв, отвечающих той или иной оптимальной архитектуре, на множестве окон при данном объеме выборки К, % — номер «скользящей» выборки на рассматриваемом

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

8

Рис. 10. Результаты модельного эксперимента

Полученные результаты позволяют сформулировать

Утверждение 2. Решение задачи поиска релевантной базы знаний для предложенной темпоралъно-нечеткой процедурной модели для случая эволюционирующего стационарного потока запросов в общем случае существует.

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

Гипотеза 3. Если поток стационарен и в процессе тестирования выявлены все типы запросов для данного потока, то построенная в этом процессе локальная модель остается справедливой для всего потока независимо от изменения характера распределения разнотипных запросов в скользящей выборке.

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

Стационарность потока не исключает динамического изменения его параметров от одного установочного периода к другому. При этом одновременно меняется и величина т,3. Выполнение условия т0 < Ь является предпосылкой смены приоритета от «линейки» к «симметрии» или «асимметрии». В динамике работы системы соотношение между Ь и то может изменяться как в ту, так и в другую сторону. Поэтому развитие СУБД С1ш1еггх в направлении автоподстройки параметра к"1 под данную нагрузку для фиксированных УБД и Ь является целесообразным.

Такое развитие связывается в работе с построением процедурной модели синтеза кластеров баз данных За основу построения предлагаемой модели взята гипотеза первичности внешних параметров Из-за неполноты информации задача формирования релевантной базы знаний в терминах внешних параметров оказывается алгоритмически неразрешимой Вместе с тем, как показано на конкретном примере, ее решение в общем случае существует Но модель оказывается локальной, справедливой только для данного потока, схемы БД и заданных значений УБД, h

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

Весь модельный эксперимент был проведен с помощью программного комплекса, разработанного на основе Microsoft Excel (темпорально-нечеткая процедурная компонента), Microsoft VisualBasic и СУБД MySQL (результаты экспериментов на кластере)

В заключении сформулированы основные результаты диссертации

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2 Разработан исследовательский прототип оригинальной СУБД Clusterix

3 Разработана темпорально-нечеткая процедурная модель выбора конфигурации ПК-кластеров БД

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

5 Подтверждено существование границы масштабируемости параллельных ПК-кластеров БД и установлен факт роста этой границы с увеличением объемов баз данных

6 Найден вид предпочтительной архитектуры кластеров БД при работах до грани масштабируемости

7 Даны практические рекомендации по динамической перестройке архитектур кластера

Основное содержание диссертации опубликовано в работах 1. Абрамов ЕВ О применимости нечетких моделей к синтезу распределенных информационных систем II Новые информационные т ехнологии и системы Труды V Международной научно-технической конференции - 11енза, 2002 С 209

2 Райхлин В А , Абрамов Е В К теории моделей синтеза кластеров баз данных // Вестник К1ТУ им А Н Туполева 2004 №1 С 44-49

3 Райхлин В А , Абрамов Е В Кластеры баз данных Моделирование эволюции // Вестник КГТУ им АН Туполева 2006 №3 С 22-27

4 Абрамов Е В Параллельная СУБД Clusterix Разработка прототипа и его на-íypHoe исследование // Вестник КГТУ им Туполева 2006. №2 С 52-55

5 Абрамов ЕВ Параллельная СУБД с ориентацией на технологию Beowulf// Всероссийский конкурс инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» - Москва, 2005 С 34-35

6 Абрамов Е В , Куревин В В Разработка и реализация алгоритма претранс-ляции запросов для PC-кластеров баз данных // XIV Туполевские чтения Труды Международной молодежной научной конференции - Казань, 2006 С 39-40

7 Абрамов Е В , Куревин В В Вопросы построения Linux-кластеров баз данных // Эволюционное моделирование - Казань Фэн (Наука), 2004 С 278288

8 Абрамов ЕВ Параллельная СУБД Clusterix Разработка и исследование //Труды московской секции международного семинара ACM SIGMOD -Москва, 2005

Интернет-адрес http //synthesis ipi ас ru/sigmod/seminar/s20051229

9 Райхлин В А , Морозов А В , Вершинин И С , Абрамов Е В Интеллектуальные модели синтеза // Труды Международной научно-технической конференции ШЕЕ AIS'03 Т2-М Физматлит, 2003 С 158-171

10 Райхлин В А , Абрамов Е В , Шагеев Д О Вопросы самоорганизации информационных кластеров // Моделирование процессов - Казань Изд-во КГТУ, 2006 С 68-86

Формат 60 х 84 1/6 Бумага офсетная Печать офсетная Печ л 1 25 Уел печ л 1,16 Уел кр-отт 1,16 Уч-изд л 1,0 Тираж 100 Заказ Л1

Типография Издательства Казанского государственного технического университета 420111, Казань, К Маркса, 10

Введение.

1. Систематика мирового опыта разработок в области параллельных

СУБД.

1.1 Ретроспектива. Машины баз данных.

1.2Современные параллельные СУБД.

1.3Исследовательские проекты параллельных СУБД.

Выводы по главе 1.

2. Внешняя и процедурная компоненты модели.

2.1 Предлагаемое решение задачи внешнего моделирования.

2.2Формулировка задач внутреннего моделирования.

2.3Процедурная компонента модели.

Выводы по главе 2.

3. Разработка параллельной СУБД С1ш1епх.

3.1 Архитектурная основа параллельной СУБД Ск^епх.

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

3.3Алгоритм работы системы.

3.4Выполнение динамического сегментирования.

3.5Подсистема сбора статистической информации.

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

3.7Подсистема конфигурирования.

3.8Оптимизирующий претранслятор.

3.9Управление кластером.

3.10 Системные лог-файлы системы.

Выводы по главе 3.

4. Модельное исследование.

4.1 Условия модельного эксперимента.

4.2Предварительное исследование.

4.3Принципы динамической реконфигурации.

Выводы по главе 4.

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

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

Работа выполнена в рамках направления конструктивного моделирования систем, развиваемого в КГТУ им. А.Н.Туполева под руководством профессора В.А.Райхлина. Основные концептуальные моменты этого направления состоят в следующем [1]. Процесс синтеза рассматривается с системных позиций в предположении, что синтезируемый объект моделирует поведение некоторой гипотетической системы. Моделирование системы проводится в рамках соответствующей модели синтеза, или S-модели (S - от Synthesis). В силу объективной неопределенности такую модель приходится строить неформально с привлечением эвристики.

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

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

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

Актуальность

Непрерывный рост объемов баз данных ставит на повестку дня задачу разработки эффективных параллельных СУБД. Реальные финансовые ограничения заставляют искать альтернативу мэйнфреймовым платформам. Хорошей альтернативой является кластерная технология. Применение стандартного серийного аппаратно-программного обеспечения {Веом?и1/-то,хяо1юткя) еще более актуализирует данную тему. Однако вопросы построения кластерных параллельных СУБД по такой технологии исследованы до сих пор недостаточно.

Цель

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

Задачи

Для достижения поставленной цели в работе исследуются и решаются следующие задачи:

1. Обобщение мирового опыта построения параллельных СУБД кластерного типа и решение на этой основе задачи внешнего моделирования.

2. Построение процедурной модели синтеза Веомт1/~кластеров БД как необходимой компоненты внутреннего моделирования.

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

4. Установление закономерностей для границ масштабируемости Вео\уи1£-кластеров БД, фактов существования в общем случае решения задачи поиска релевантной базы знаний и эффективности предложенной процедурной модели в процессе модельного эксперимента.

Научная новизна

• Построение основ теории параллельных СУБД на платформе Веот^-кластеров.

• Использование парадигмы внешних параметров и нечеткая трактовка темпоральности в контексте семантики Крипке при построении процедурной модели синтеза параллельной СУБД кластерного типа.

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

• Выявление зависимости границы масштабируемости Веомпл1/-кластеров БД от объемов баз данных.

Практическая значимость работы

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

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

Результаты диссертации использованы в учебном процессе кафедры Компьютерных систем КГТУ им. А.Н. Туполева (КАИ).

Апробация результатов работы

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

1. Республиканском научном семинаре АН РТ «Методы моделирования» (Казань, 2001-2007гг.);

2.-V Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2002 г.);

3. Международной научно-технической конференции IEEE AIS'03 (Геленджик, 2003 г.);

4. Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» (Москва,

2005г.);

5. Московской секции Международного семинара ACM SIGMOD (МГУ им. Ломоносова, Москва, 2005 г.);

6. VII Международной конференции-семинаре «Высокопроизводительные параллельные вычисления на кластерных системах» (ННГУ им. Н.И.Лобачевского, Нижний Новгород, 2007 г.).

На защиту выносятся следующие положения:

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

2. Темпорально-нечеткая процедурная модель синтеза Вео\уи1/~ кластеров БД и ее программная реализация.

3. Разработка исследовательской версии параллельной СУБД С/мя/епх.

4. Результаты модельных исследований.

Публикации

Основное содержание диссертации опубликовано в 10 работах, включая 6 статей [40, 57, 60, 63, 65, 66], 4 тезиса докладов [55, 61, 62, 64].

Структура и объем работы

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

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

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

•Разработан исследовательский прототип оригинальной СУБД С/ш*ега:. •Разработана темпорально-нечеткая процедурная модель выбора конфигурации Веомш1/~кластеров БД.

•Экспериментально показано существование решения задачи поиска релевантной базы знаний построенной модели в общем случае. •Подтверждено существование границы масштабируемости параллельных £ео-и>и//-кластеров БД и установлен факт роста этой границы с увеличением объемов баз данных.

•Найден вид предпочтительной архитектуры кластеров БД при работах до грани масштабируемости.

•Даны практические рекомендации по динамической перестройке архитектур кластера.

ЗАКЛЮЧЕНИЕ

1. Райхлин В.А. Конструктивное моделирование систем. - Казань: ФдН (Наука), 2005.

2. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ - Петербург, 2004.

3. What makes a cluster a Beowulf? Интернет-адрес: http://www.beowulf.org/overview/index.html

4. Сбитнев Ю. Практическое руководство по параллельным вычислениям. Интернет-адрес: http://linux-cluster.org.ru

5. Озкарахан Э. Машины баз данных и управление базами данных: Пер. с англ. М.: Мир, 1989.

6. Калиниченко JI.A., Рыбкин В.М. Машины баз данных и знаний. М.: Наука, 1990.

7. DeWitt D.J. et al. The Gamma database machine project // IEEE Transactions on Knowledge and Data Engineering. 1990. V. 2. №1. P. 44 -62.

8. Левин Л. Teradata совершенствует хранилища данных. // PC Week. 2005. №2.

9. Dewitt D.J., Gerber R. Microprocessor Hash-Based Join Algorithms // VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. P. 151 168.

10. Schneider D.A., DeWitt D.J. A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment. Computer Sciences Department, University of Wisconsin, Madison. P. 110—121.

11. Лесянский К., Слободяников Д. СУБД Teradata для ОС UNIX Интернетадрес: http://www.citforum.ru 75.Болиджер К. Врожденный параллелизм // Открытые системы. 2006. №2.

12. Интернет-адрес: http://www.osp.ru/os/2006/02/l 156526/ 16. Oracle Real Application Clusters lOg. Интернет-адрес: http://www.oracle.com/technology/products/database/clustering/pdf/twprac 10gr2.pdf

13. Сиколенко B.B. Сервер Oracle: текущее состояние. Интернет-адрес:www.citforum.ru/database/articles/oracleo v. shtml 75.Parallel Hardware Architecture. Oracle7 Parallel Server Concepts and

14. Administrator's Guide. 19.Oracle 8i Parallel Server. Concepts. Realease 2 (8.1.6). December 1999.

15. Дубова H. Суперкомпьютеры nCube // Открытые системы. 1995. №2.

16. Архитектура сервера INFORMIX-OnLine Dynamic Server 7.1 и коммуникационные средства. Интернет-адрес: http://www.computer-museum.ru/histsoft/ji95021 .php

17. Барон Г.Г. Параллельные архитектуры серверов баз данных // СУБД №2. 1995. Интернет-адрес: http://www.computer-museum.ru/histsoft /ji95011.htm

18. MySQL Cluster configuration Интернет-адрес: http://mysql.com/products/database/cluster/

19. PostgresSQL Интернет-адрес: http://pgpool.projects.postgresqI.org/pgpool П/en/

20. PGCluster Интернет-адрес: http://pgcluster.projects.postgresql.org/

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

22. Воронин В.Г. Принципы разработки SQL компилятора для СУБД Омега. Технический отчет ОмегаЮ. - Челябинск: ЧелГУ, 2002

23. А 100 Node ATM connected PC cluster. Интернет-адрес: http.V/www.tkl.iis.u-tokyo.ac.jp/Kilab/Research/NEDO-lOO/index.html

24. Oguchi M., Kitsuregawa M. Data Mining on PC Cluster connected with Storage Area Network: Its Preliminary Experimental Results. 2001.

25. Oguchi M., Kitsuregawa M. Parallel Data Mining on ATM Connected PC Cluster and Optimization of its Execution Environments. 2000.

26. Оззу M.T., Валдуриз П. Распределенные и параллельные системы баз данных // СУБД. 1996. №4.ii.DeWitt D.J., Gray J. Parallel Database Systems: The future of high -performance database systems // Communications of the ACM. 1992 V.35. № 6. P. 85 98.

27. Bodal H., Dewitt J. Database machines: An idea whose time has passed? A critique of the future of database machines // Database Machine, Munich, Sep 1983, P.166-187.

28. Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 1980.

29. Шуленин А. Процессор запросов Microsoft SQL Server. О некоторых стратегиях оптимизатора при построении сложных, параллельных и распределенных планов // СУБД. 1998. №3. С.37.

30. Александров А. Машины хранилищ данных // Открытые системы. 2006. №2.

31. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», ' 1999.

32. ЗР.ДеВитт Д., Грей Д. Параллельные системы баз данных: будущее высокоэффективных систем баз данных // СУБД. 1995. №2.

33. Райхлин В.А., Абрамов Е.В. К теории моделей синтеза кластеров- баз данных //Вестник КГТУ им. А.Н.Туполева. 2000. №3. С.53 58.

34. Тейз -А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию. -М.: Мир. 1990.

35. Тейз А., Грибомон П., Юлен Г. и др. Логический подход к искусственному интеллекту: от модальной логики к логике баз данных. — М.: Мир. 1998.

36. Аверкин А.Н., Батыршин И.З., Блишун А.Ф. Нечеткие множества в моделях управления и искусственного интеллекта /Под ред. Д.А. Поспелова. М: Наука, 1986.

37. Малышев Н.Г., Берштейн Л.С., Боженюк A.B. Нечеткие модели для экспертных систем в САПР. М.: Энергоатомиздат, 1991.

38. Райхлин В.А. Моделирование машин баз данных распределенной архитектуры //Программирование. 1996. №2. С.7 16.

39. Ульман Дж. Основы систем баз данных М.: Финансы и статистика, 1983.4&Дж.Грофф, П. Вайнберг SQL: Полное руководство: Пер. с англ. — 2-е изд., перераб. и доп. К.:Издательская группа BHV, 2001.

40. ТРС BENCHMARK D. Standard Specification. Revision 2.1. Интернет-адрес: http://www.tpc.org

41. Что такое Beowulf? Интернет-адрес: http://parallel.rU/computers/reviews/beowulf.html#pl

42. Уолтон Ш. Создание сетевых приложений в среде Linux. М.: Издательский дом «Вильяме», 2001.

43. Митчел М., Оулдем Д., Самьюэл А. Программирование для Linux. -М.: Издательский дом «Вильяме», 2003.

44. Снейдер Й. Эффективное программирование TCP/IP. Библиотека программиста СПб.: Питер, 2002.

45. Дюбуа П. MYSQL М.: Издательский дом «Вильяме», 2001.

46. Главные компоненты временных рядов: метод «Гусеница» /Под ред. ДА. Данилова и A.A. Жиглявского. С.Пб.: Санкт Петербургский университет, 1997

47. Райхлин В.А., Абрамов Е.В. Кластеры баз данных. Моделирование эволюции // Вестник КГТУ им. А.Н. Туполева. 2006. №3. С.22-27.

48. Лукашин Ю.П. Адаптивные методы краткосрочного прогнозирования временных рядов. М.: Финансы и статистика, 2003.

49. Дуброва Т.А. Статистические методы прогнозирования. — М.: ЮНИТИ, 2003.

50. Абрамов Е.В. Параллельная СУБД Clusterix. Разработка прототипа и его натурное исследование //Вестник КГТУ им. А.Н. Туполева. 2006. №2. С.52-55.

51. Абрамов Е.В. О применимости нечетких моделей к синтезу распределенных информационных систем. // Труды V Международной научно-технической конференции Новые информационные технологии и системы. Пенза.:ПГУ, 2002. С.209

52. Абрамов Е.В., Куревин В.В. Вопросы построения Linux-кластеров баз данных. // Эволюционное моделирование. Казань: Фэн, 2004. С.278-288.

53. Абрамов Е.В. Параллельная СУБД Clusterix. Разработка и исследование. Труды московской секции международного семинара ACM SIGMOD. Интернет-адрес: http://synthesis.ipi.ac.ru/sigmod/seminar/s20051229