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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

Абрамов Евгений Викторович

Казань - 2008

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

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

доктор физико-математических наук,

профессор Райхлин Вадим Абрамович

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

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

профессор Столов Евгений Львович

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

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

Ведущая организация:

НИИ математики и механики им. Н.Г. Чеботарева (г. Казань)

Защита состоится « 29 » февраля 2008 г. в 14.00 часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г. Казань, ул. К. Маркса, 10

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

Автореферат разослан « 19 » января 2008 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоверность результатов работы. Задача внешнего моделирования решена с привлечением мирового опыта. Разработанная программная система 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, 1980-е). Данные проекты во много определили развитие современных параллельных СУБД. Именно в них были предложены алгоритмы распределения данных, реализованы параллельные алгоритмы выполнения реляционных операций. Далее представлены современные коммерческие системы параллельной обработки запросов к базам данных: Teradata, Oracle, Informix. Обзор завершается рассмотрением исследовательских проектов последних лет: MySQL Cluster (2004), PGCluster, Омега (Л.Б.Соколинский, 1997), NEDO-100 (Oguchi, Kitsuregawa, 1996).

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

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

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

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

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

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

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

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

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

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

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



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

На рисунке:

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

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

фреймы дочернего уровня

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

Проведенная в главе 1 систематика дает выбор решений на всех множествах альтернатив (пресловутые элементы конструктивной теории), за исключением относящихся к фрейму РУО, в виде продукции A, B, C, D, E, F, G, H W как внешней компоненты искомой модели. Здесь W - искомая архитектура кластера; А - внешний язык запросов есть SQL; В - внутренний язык запросов включает ограниченное подмножество реляционных операторов (селекция, проекция, соединение); C - запрос расщепляется на несколько процессов реализуемых на разных процессорах; D - база данных распределяется между несколькими НМД с применением механизма хеширования; E - имеется нижний (операции ввода-вывода, селекции и проекции) и верхний (операции проекции и соединения) уровни обработки; F - граф обработки любого запроса формируется в динамике оптимизирующим претранслятором, который расщепляет SQL-запрос пользователя на MySQL-фрагменты отдельных исполнительных уровней; G - используется стратегия МРР (обмен сообщениями), реализуемая на базе сети FastEthernet; H - реализация реляционных операций средствами MySQL.

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

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

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

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

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

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

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

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

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

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

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

Q = () ? (w qБД) [0, 1].

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

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

U = () ? (w VБД) [0, 1] ,

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

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

D = () ? () [0, 1].

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

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

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

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

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

?[P1…Pm Y1 …Yq] .

Их левая часть - условие (антецедент), правая - действие (консеквент), Pi и Yj - некоторые предикаты. Использование дизъюнкций в консеквенте обычно запрещают. С понятием модальности связывается семантика «возможных миров» (семантика Крипке). В этой семантике универсум W - множество возможных миров {s, t, u, …}, связанных отношением доступности R. Факт доступности мира j после i обозначается как iRj, i,j W. Пара (W, R) называется структурой, тройка (W, R, J) - моделью, или интерпретацией структуры. Здесь J - отображение из W Ј (”” - знак декартова произведения) в {И, Л}, которое для каждого мира W любой формуле p Ј сопоставляет определенное значение истинности J(, p).

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

Определение 1. Определим sR(t,u) как stu ?[sRt sRu sR(t,u )].

По условию отношение R удовлетворяет аксиомам транзитивности

stu ?(sRt tRu sRu).

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

stu ?[(sRt sRu) (sRt tRu) (sRu uRt) sR(t,u )].

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

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

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

?[(s/t s/u) (s/ t t /u) (s/u u/ t) s/(t,u )]. (1)

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

?[(PQPUPD)ij i / j ]; i, j {s, t, u}; i j. (2)

Здесь P? (? = Q, U, D) и i / j - предикаты, P? = z? (), z? {H, M, L} - множество значений лингвистических переменных: H - высокое, M - среднее, L - низкое. Антецеденты формул интерпретируются на основе «избранных моделей» c учетом мыслимых альтернатив характеристик <Q, U, D>. Каждый вариант включает 6 правил с консеквентами s/t, s/u, t/s, t/u, u/s, u/t. Общее число вариантов * > 2*108. Это обуславливает трудоемкость поиска релевантной базы знаний.

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

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

Здесь (x?) [0, 1] - функция принадлежности, x? [0, 1] - результат перевода z? в конкретные цифровые значения для данного рабочего теста TW. Переход к нормированной переменой x? позволяет унифицировать встраиваемые в инструментальную среду типовые зависимости H,M,L(x). По ним определяются значения z , z {H,M,L}, для каждого P? . Подстановка этих значений в формулы из Ј вместо соответствующих предикатов используется для оценки степени правдоподобия вывода

(TW)st s/ t .

Коэффициент правдоподобия Kst интерпретации (TW)st

Kst = z?.

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

z? = z? .

Согласно (1), степень близости Ks теста TW миру s из W = {s, t, u} будем оценивать по ранее найденным Kst , Ksu, Ktu и Kut :

Ks = (Kst*Ksu) (Kst*Ktu) (Ksu*Kut) .

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

Ks = [ (Kst*Ksu) + (Kst*Ktu) + (Ksu*Kut) ] /3.

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

TW i, i {s, u, t},

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

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

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

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

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

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

Данный план реализует выполнение запроса по схеме select-project-join.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SELECT список_атрибутов FROM список_отношений

[WHERE условие_1 [[ AND условие_k ] …]]

[GROUP BY список_атрибутов] [ORDER BY список_атрибутов].

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

Предикаты запроса вида:

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

Предикаты запроса вида:

<отношение_А.атрибут_B><условие><отношение_А.атрибут_С> реализуется на уровне I/O, т.к. оно является условием селекции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для любой архитектуры производительность монотонно повышается с ростом h, если hhB, где hB - число узлов кластера в точке ветвления (ветвление проявлено только при VБД = 575 Мбайт - см. рис. 9, где hB12). При этом значительный эффект наблюдается в сравнительно узком диапазоне значений h;

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

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

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

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

hG = (1 + k-1) mG ,

свою для каждой архитектуры. Она максимальна для «симметрии» : (hG)сим = 2mG .

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

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

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

После этого в соответствии с локальной базой знаний первого приближения для всех позиций окон в каждом тесте находятся модельные оценки их принадлежности тому или иному миру. Найденные оценки сравниваются с полученными экспериментально. Если для каждого теста большей частью модельные оценки совпадают между собой и с результатами эксперимента, то эти оценки правильно определяют приоритетную архитектуру, и сформированная база знаний релевантна рассматриваемому потоку. Иначе база знаний корректируется, вычисления повторяются. И так до тех пор, пока не будет выполнено условие релевантности. В результате исследований для VБД = 575 Mбайт и h = mG = 8 (k-1ас=?) была эвристически построена локальная база знаний процедурной модели (2):

(MHM s / t ) , ?(MHL t / s ),

(LHL s / u), ?(LLM u / s ), (3)

(HHH t / u ), ?(MHH u / t ).

В табл.1 представлены результаты натурного и модельного экспериментов для 5 вариантов перестановок каждого из сформированных тестов на множестве позиций окон размерами w = 5 - 10 (всего - 225 окон).

Таблица 1

14-запросная выборка теста TPC-D, h=8	Спецтест длины 14 из 4 запросов теста TPC-D, h=8
k-1opt	rexp	rmod	rexp	rmod	texp сек
		прав	общ		прав	Общ
0	225	219	219	-	-	-	481
1/3	-	-	-	-	-	-	318
1	-	-	6	225	225	225	220

В таблице:

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

Таблица 2

По окнам, w = 5 - 10	По тесту в целом (w = 14)
k-1opt	rexp	rmod	По окнам с k-1opt (эксперимент)	k-1	rmod	texp.ср cек	exp.ср
			k-1	exp.ср
0	41	225	0	0,96	0	5	632	1,10
			?	1,00
			1	1,42
?	153	-	0	1,11	?	-	572	1.00
			?	1.00
			1	1,16
1	31	-	0	1,17	1	-	704	1,23
			?	1,00
			1	0,95

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

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

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

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

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

На рис. 10: - относительное число «оконных» результатов, отвечающих той или иной оптимальной архитектуре, на множестве окон при данном объеме выборки K; - номер «скользящей» выборки на рассматриваемом двойном тесте. В данном случае локальная модель (3) позволяет правильно предсказать очередную приоритетную архитектуру в динамике обработки потока запросов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНО В РАБОТА

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

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

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

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

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

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

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

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

Размещено на Allbest.ru

...