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

005014624

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

МИНЯЗЕВ РИНАТ ШАВКАТОВИЧ

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

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

и комплексы программ

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

1 5 ^

Казань 2012

005014624

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

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

Официальные оппоненты: Елизаров Александр Михайлович,

доктор физико-математических наук, профессор, Институт математики и механики им. Н.И. Лобачевского Казанского федерального университета, заместитель директора по научной работе

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

Ведущая организация: Институт информатики Академии наук Республики Татарстан, г. Казань

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

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

Автореферат разослан «15 » февраля 2012 г

Ученый секретарь

диссертационного совета Данилаев Петр Григорьевич

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

Актуальность темы. В сфере интеллектуальной обработки данных принят ориентир на использование высокопроизводительных параллельных СУБД: корпоративные базы данных (Stonebraker M., Кузнецов С.Д.), электронная коммерция (Agrawal R., Xu Y.), электронные библиотеки (Елизаров А.М., Когалов-ский М.Р.), геоинформационные системы (Ризаев И .С., Цветков В.Я.), социальные сети, научные базы данных (DeWitt D., Велихов П.Е., Бартунов О.С.). Такие системы ориентированы на функционирование на платформах вычислительных кластеров. Имеются исследовательские и коммерческие проекты параллельных СУБД: DB2 Parallel Edition, Greenplum, NonStop SQL, Teradata, MySQL Cluster, PG Cluster, Oracle EXADATA, Sybase IQ, Microsoft SQL server (проект Madison), NEDO-lOO, Омега и др. Большинство из них - универсально, ориентировано на решение широкого круга задач в различных предметных областях. Для них характерно выполнение множества сравнительно простых операций типа select, insert, delete над динамически изменяемыми данными.

Актуализация задач аналитической обработки данных (OLAP), создания хранилищ данных (data warehouse), построения систем поддержки принятия решений (DSS), интеллектуальный анализ данных (data mining) определяют необходимость построения специализированных высокопроизводительных параллельных СУБД консервативного типа (с эпизодическим обновлением баз данных в специально выделяемое время). Для них характерны работа с базами данных большого объема со множеством отношений, большое число пользователей, высокий удельный вес сложных запросов типа select—project-join с несколькими уровнями вложенности запросов.

Серьезными проблемами для любых параллельных СУБД являются: масштабируемость - как по числу узлов, так и по числу пользователей; обеспечение отказоустойчивости; балансировка нагрузки и размещение данных между узлами (Stonebraker M., Szalay A., Bell G.). Среди перечисленных проблема балансировки нагрузки занимает ключевое место (Lakshmi M.S., Yu P.S., Лепи-хов A.B.). Именно с ее решением связывается повышение эффективности и масштабируемости параллельной СУБД.

Развитие теории параллельных СУБД кластерного типа требует детального анализа динамики таких систем. Только знание особенностей динамики СУБД-кластеров позволит дать объективные рекомендации к их построению. Проведение подобных исследований затруднено отсутствием специализированных инструментальных средств моделирования в составе ранее перечисленных разработок. Исключением является проект параллельной СУБД Clusterix (Абрамов Е.В.). По сути это - специализированная система моделирования кластерных СУБД консервативного типа с регулярным планом обработки запросов. Ее использование как инструментального средства моделирования позволило установить ряд закономерностей по масштабируемости и др. для СУБД-кластеров указанного типа на платформе Pentium-Ill (Райхлин В.А., Абрамов Е.В.). Настоящая работа расширяет область исследований на случай современных платформ.

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

Предмет исследования - правомерность перехода на позиции мультикла-стерных СУБД указанного типа; рекомендации по декомпозиции кластера в целом на составляющие монокластеры и выбору архитектуры монокластера; моделирование процесса распределения запросов между монокластерами; инструментальная система моделирования для проведения необходимого вычислительного эксперимента.

Цель диссертационной работы - повышение эффективности (по критерию «производительность/сложность») использования вычислительных кластеров заданной сложности с многоядерными БМР-узлами при реализации на них параллельных СУБД консервативного типа с регулярным планом обработки запроса.

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

Эта комплексная задача разбивается на 3 подзадачи:

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

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

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

Методы исследования. Исследования проводились с привлечением методологии вычислительного эксперимента; теории системного и параллельного программирования; теории баз данных; методов обработки временных рядов; модальной логики с использованием семантики Крипке и системы нечеткого вывода; принципов построения генетических алгоритмов; методов статистической обработки результатов эксперимента.

Основные научные результаты, полученные автором и выносимые на защиту:

1. Платформо-независимость качественных закономерностей масштабируе-

2

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

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

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

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

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

2. Построена математическая модель процесса распределения запросов между монокластерами с применением семантики Крипке и механизмов нечеткого вывода. Эта модель отличается от ранее использованной для динамической реструктуризации параллельных СУБД (Райхлин В.А., Шагеев Д.О.) изменением семантики миров Крипке (теперь это - миры параметров, а не миры архитектур), специфичным выбором характеристик предпочтения на множестве таких миров (весовые коэффициенты параметров) и критерия предпочтения на множестве монокластеров (минимум веса очереди запросов).

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

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

з

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

Практическую ценность работы составляют:

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на международной молодежной научной конференции «Туполевские чтения» (Казань, 2008 г.), республиканском научном семинаре АН РТ «Методы моделирования» (Казань, 2009-2011 гг.), международных конференциях «Высокопроизводительные параллельные вычисления на кластерных системах» НРС-2008,2009,2011 (Казань, 2008 г.; Владимир, 2009 г.; Нижний Новгород, 2011 г.).

Публикации. Результаты диссертационной работы отражены в 7 публикациях, в том числе 3 - в трудах конференций, 4 - научные статьи (из них 2 - в рецензируемых журналах).

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

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

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

В ПЕРВОЙ ГЛАВЕ даются краткие характеристики множества проектов параллельных СУБД. Они в большинстве своем являются универсальными и «безразмерными» по объему БД. Подчеркивается целесообразность построения специализированных высокопроизводительных параллельных СУБД высокой масштабируемости, предназначенных для аналитической обработки данных, требующей исполнения большого числа сложных запросов типа select-project-join.

Рассмотрены основные известные подходы к повышению производительности параллельных СУБД: фрагментирование и репликация баз данных (DeWitt D., Bellatreche L., Bradley P.), применение специализированных аппаратных модулей (Boncz A., Kersten L.), использование нереляционных моделей дос-

4

[ Исследуемое явление

_*_

тупа к данным (Dean J., Ghemawat S., Abouzeid A., Silberschatz А.) построение специализированных систем (Stonebraker M., Abadi D., Madden S.).

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

Рассмотрены открытые исследовательские проекты параллельных СУБД кластерного типа (MySQL Cluster, PGCluster, NEDO-lOO). Отсутствие в них специализированных инструментальных средств не позволяет использовать их для целей моделирования. Проанализированы имеющиеся средства мониторинга и визуализации аппаратных платформ, на которых функционируют параллельные СУБД (Nagios, OpenNMS, NetXMS). Несмотря на большие функциональные возможности этих систем, они не позволяют собирать информацию относительно работы прикладного и системного программного обеспечения, функционирующего в узлах кластера.

Этапы численного эксперимента в работе укрупненно отражены на рис. 1. Компоненты «компилятор, ОС, компьютер» - это атрибуты используемой программно-аппаратной платформы (вычислительного кластера). Исследуемые явления - динамика монокластера (подзадача 1) и процессы роутеризации (подзадача 2).

Отличием от классической картины (Воеводин Вл.В.) является включение этапа «Модель объекта». Вычислительный эксперимент проводится с использованием необходимого инструментального средства моделирования - имитационной модели объекта (объект - параллельные СУБД рассматриваемого типа). За основу его разработки принята параллельная СУБД Clusterix. Общие принципы построения этой СУБД, учитывающие необходимость моделирования реальных системных ситуаций, определены продукцией:

А, В, С, D, Е, F, G, Н з W. W - искомая программная модель; А - внешний язык запросов - SQL; В - внутренний язык запросов - MySQL;

С - общая стратегия обработки запросов: множество процессоров на запрос; D - используются одноканальные накопители на магнитных дисках (НМД);

Математическая модель

I

Численный методу

~TZ

Программа 1

Результат

И

Анализ вычислений

- - 4- -

Компьютер

Модель объекта

I

Операционная система

Компилятор

Рис.1. Этапы численного эксперимента в рассматриваемом случае

Е - база данных распределяется между несколькими НМД с применением механизма хеширования; F - имеются нижний (операции Input, Select, Project) и верхний (операции

Join, Sort) уровни обработки; G - план обработки запроса регулярен. Исходный SQL-запрос расщепляется на MySQL-фрагменты исполнительных уровней;

Н - используется стратегия МРР с обменом сообщениями, реализуемая на базе Ethernet-сетей с коммутатором в ОС Linux.

СУБД Clusterix предусматривает двухуровневую обработку данных согласно регулярному плану (Райхлин В.А.) (рис. 2). Верхний исполнительный уровень образуют модули Join, (операции соединения х) числом Ь. Нижний - модули НО, (операции селекции а и проекции я) числом d=h-b, где h=2z (общее число узлов кластера). Распределение модулей между узлами определяет архитектуру СУБД Clusterix. Рассмотрение ограничивается случаями a1 =b/d £ {0, Уз, Vi, 1}. Соответствующие архитектуры: «линейка», «асимметрия 1/3», «асимметрия 1/2», «симметрия». База данных распределена в дисковом пространстве 1/Ог путем хеширования записей отношений по основному ключу.

Как отмечено в гл. 4, в случае многоядерных узлов использование СУБД Clusterix в качестве инструментального средства моделирования не представляется возможным. Итогом ее переработки явилась система Clusterix-I.

ВТОРАЯ ГЛАВА рассматривает принципы и целесообразность перехода к мультикластеризации. Для обоснования эффективности подхода мульти-кластеризации устанавливается возможность распространения ранее сформулированной для платформы с одноядерными узлами гипотезы масштабируемости (Райхлин В.А., Абрамов Е.В.) на случай использования вычислительного кластера с многоядерными узлами.

Гипотеза масштабируемости: для кластеров консервативных баз данных, погруженных в среду параллельной СУБД с регулярным планом обработки запросов, всегда существует независимое от архитектуры СУБД граничное число страниц d=dc, при котором производительность кластера близка к максимальной. Значение dG растет с увеличением объема базы данных УБд.

Число страниц (модулей 1/Ог) - число фрагментов, на которое делится база данных. Параметр dG определяет границу эффективной масштабируемости по числу узлов hG=(l+e"') de, не одинаковую для разных архитектур СУБД.

При проведении вычислительного эксперимента на системе Clusterix-I обрабатывались пакеты запросов из теста ТРС-Н при разных объемах БД, архитектурах (конфигурациях) СУБД, числе задействованных узлов кластера h. Подтверждение гипотезы масштабируемости для платформ вычислительных кластеров с многоядерными узлами иллюстрируют рис. 3,4. Для эффективного исполь-

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

щдаТ.се. 7юаю>Т,с"

^СЯМвтрю * * .

muß i ♦зшметрияУ*

та.ОЮ ^ 7 ВСЛМбТрИЯ 1/3 -.по:«: 7 4

едал * :м*:>г,э \

таг, * 7 «мот \

ФХ1Ш 393J0DO ТОГО

L \ i

»

■----■ -

1 2 3 4 5 6 7

V ♦

&с№4метрия ♦ всиыметрияМ ' аспмвтрия 1J3 *-л«йо

s X) н i;

Рнс.З. Время обработки пакетаУБД=ЮЬ Рис. 4. Время обработки пакета Vu-5,4Gb

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

В этой конфигурации на каждом узле кластера запускается по два сервера используемой на нижнем уровне СУБД MySQL. Модули 1/Ог и Joinj (r=j) реализуются на одном узле аналогично архитектуре «линейка», но каждый модуль работает со своим сервером MySQL (рис. 5). Тестирование новой конфигурации на плафторме НРС-кластера показало лучшие масштабируемость и производительность при h = ho по сравнению с «линейкой» (рис. 6).

соямешемная симметрии »-лимсйкв

Рис. 5. Совмещенная симметрия Рис. 6. Сравнение конфигураций

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

7

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

__Этапы исполнения запроса Таблица 1.

IO_EXEC Исполнение операций я и о на исходным отношением БД, получение промежуточного отношения ^(сохраняется в главной памяти процессора 10)

IO_HASH Проведение операции хеширования (деление по модулю на число процессоров Ю) над отношением R' по полю, участвующему в соответствующей операции соединения

lOWAITLOAD Пересылка частей отхешированных отношений R' между процессорами 10 в соответствии с полученными на предыдущем этапе значениями хеш-функций и формирование итоговых отношении Я' на каждом Ю

IOJWAITSYNC Ожидание пока все модули IO выполнят предыдущие операции (барьерная синхронизация модулей 10)

IO_NET_IO_JOIN Пересылка итоговых промежуточных отношений R' с процессоров Ю на соответствующие процессоры JOIN

JOIN creating INDEX before JOIN Создание индексов для промежуточного отношения R', пришедшего с предыдущего такта работы конвейера 10

. JOINEXEC Выполнение операции соединения над R' и временным отношением R^i-i), пришедшим с предыдущего такта работы конвейера JOIN, формирование временного отношения R,^

JOIN_HASH Проведение операции хеширования (деление по модулю на число процессоров JOIN) над отношением R' по полю, участвующему в соответствующей операции соединения

lOINWAITLOAD Перемешивание отхешированных отношений R«^ между всеми процесс-сорами JOIN(nepecbuiKa кортежей по сети и формирование отношении R^iy)

JOIN_WAIT_SYNC Ожидание пока все модули JOIN выполнят предыдущие операции (барьерная синхронизация модулей JOIN)

JOINcreating INDEX after join Создание индексов для сформированных отношении Я,щ.

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

1) независимость производительности системы от выбора интерконнекта (GigabitEthemet или InfiniBand);

2) резкое возрастание объемов работ Tj по этапам на кластере при h > 10

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

3) существенное влияние на быстродействие системы при h < ho этапа IO EXEC (экспонента на рис. 8; е - отношение суммарного объема работ Tj по этапу к общему объему работ по всем этапам Ts);~ho при h=ho это влияние существенно ослабевает;

4) слабое влияние интерконнекта на масштабируемость; временной доминантой на границе масштабируемости является этап барьерной синхронизации работы процессоров 10 (IO_WAIT_SYNC - «купол» на рис. 8); влияние этого фактора не растет с переходом к мультикластерной архитектуре, превалируя над ростом влияния интерконнекта при разумных размерах мультикластера.

soooo

45000 4 OOOO 38000 30000 25000

20000

15000 10000 SOCIO

- :о_схгс......

- IO_NET_IO.. JOIN

- IO_NET_CONNECT

- O WAI!,SVNC

- lQ_WAir_LOAO -IO_HASH

—SORT_EXEC -SORT_N£T_RESULT

- SORT_GET_DATA

- SORT_LOAD_DATA

- JO N_FX'_C

-JOIN craatmg INDEXbafor* JOIN'

-JOIN_NET_JOIN_SORT -JOIN_NET_CONNECT -JOIN_WWT_SYNC - JOIN_WAIT J.OAD -JOIN„HASH

1 2 3 * 5 В 7 в в 10 11 12 13 14

Рис. 7. Суммарный объем работ по этапам

Тестирование производительности равносложных однокластер-ных и многокластерных архитектур с помощью С1и81епх-1 показало правомерность использования подхода мультикластеризации для повышения эффективности параллельных СУБД на платформе вычислительных кластеров с многоядерными узлами и наличие асимптотического ограничения производительности мультикластерных систем с ростом числа монокластеров (рис. 9-10).

,^Т,сек______________________________Т, сек

Рис. 8. Выявление временных доминант

^ ^ 3 4 П 345678» 10 11 12

Рис. 9. Мультикластер на НРС-плагформе Рис. 10. Мультикластер на ПК-платформе

В ТРЕТЬЕЙ ГЛАВЕ строится математическая модель для эффективного решения задачи распределения запросов между монокластерами в мультикла-

9

Clier»t_N

Щ внешняя сеть

MorKicluslfr_l

■Itch j _

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

Рассматриваемые мультикластерные СУБД представлены на рис. 11. База данных реплицируется между монокластерами. Распределение непрерывного потока запросов, поступающих от N клиентов - Client i, ie{l,N}, между п

кластерами-компонентами осуществляет модуль ROUTER. Входной поток запросов длины М, поступающий на обработку в систему, формируется случайным образом на множестве Q из 14 запросов теста ТРС-Н без операций записи. Рассматривается случай, когда очередной запрос от каждого пользователя поступает на вход СУБД не ранее, чем будет получен ответ на предыду-

Рис. 11. Мультикластерная СУБД Щий запрос. Поэтому в любой момент

времени суммарное число запросов, находящихся в системе L<N. В дальнейшем полагается L=N. Рассматривается множество из двух классов распределений: т. н. «круговые» и «модельное».

Для «круговых» распределений вводится два вида очередей запросов: внутренних (в кластерах-компонентах) и внешней (в ROUTER). Суммарная длина всех внутренних очередей i „=k-n <N, к>1. Длина внешней очереди Первые i „ запросов распределяются по кластерам-компонентам в порядке мест, занимаемых ими в обрабатываемой последовательности:

в дальнейшем всякий раз пополняется

^^^^мередь

S3

iю—п I ¿„-11-2 in — ir-зймрссь;

п-1 11-- — 211

1 2 - - - и — ¡-запросы

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

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

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

Обозначим: ^ - задержка ответа на вновь поступающий г-запрос (г е Я

={ N + 1,М}, вычисляемая как разность времен появления результатов обработки г и (г-Л) запросов в каждом случае. Путем вычислительного эксперимента для разных распределений будем получать графики временных рядов

(-Лг (г)1М(^г), варьируя число п монокластеров и количество N пользователей.

Среднестатистическое время ожидания ответа на вновь поступивший запрос оценен величинами математического ожидания = (I ) / т и

^ ^ г

среднеквадратического отклонения о=л1 М [1зг- как характеристику ре-

левантности оценки по М (оценка тем более релевантна, чем меньше о).

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

Модель распределения запросов построена с использованием ряда соглашений модальной (немонотонной) логики. С понятием модальности связывается семантика возможных миров (семантика Крипке). В ней универсум XV - множество возможных миров {в, 1, и, ...}, связанных отношением доступности {предпочтительности) И.. Факт доступности мира ] после 1: ¡1^, ¿..¡е \\Л

В рассматриваемом случае миры Крипке - это миры параметров. Для них проведена ранжировка степеней влияния тех или иных параметров. Рассматривался случай трех миров X, и}. Факт предпочтительности в смысле Я одного мира, например, в, перед другими обозначается как вЩ^и) и определяется V в VIV ц □|>Ш Л sR.ii 3 вЩ^и)]. Далее для повышения чувствительности разрабатываемой модели использовано известное положение (Райхлин В.А.):

УвУ^иаКэШ АвЯи) V (эШ лЖи)У (эЯи лиШ) => )] (*).

Для получения численных оценок осуществлялся переход с позиций модальной логики на позиции непрерывной логики, для которой значения истинности принадлежат всему интервалу [0,1]. При этом значение истинности любого предиката, входящего в состав формулы, принадлежит тому же интервалу. В таких условиях значение истинности анцедента продукции в целом определяет значение истинности консеквента. Поэтому в продукции (*) знак импликации может быть заменен знаком равенства. Знак «□» можно исключить в силу аксиомы знания, а знак V - за ненужностью при вычислениях.

В качестве параметров порядка для данных схемы БД, платформы, УБД взяты элементы вектора <Qq, Uq, Eq>, который принимается за характеристику нагрузки q-кластера; q е - номер внутренней очереди, т. е. номер кластера (q - от queue - очередь);

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

Wq

Q4 = (£Ci)/ Кс6д) е [0,1], ¡=1 '

wq - число запросов в q-очереди,

свд - общее число отношений базы данных,

С| - число еще не затронутых обработкой отношений в i-запросе q-очереди. Эмпирически найденное выражение для подсчета Cj:

С] я к • с ь к- ехр(-6/2).

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

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

Wo С'

Uq = (g |jVj.)/ (Wq Убд) 6 [0,1],

Vji- объем еще не затронутого обработкой j-отношения в i-запросе q-очереди. Для первоочередного запроса эмпирически найдено:

Сц Ci

Zvji~ k'Ivjr

J=1 j=l

Смысл обозначений k и С i - прежний;

Eq - оценка относительной длины q-очереди (Е - от Estimation - оценка)

Eq = Vtwq€ [0, 1]. 4=1

Введен в рассмотрение вес q-очереди Wq (от Weight - вес), предположительно релевантный времени ее исполнения Tq:

wq= VQcqQЧУ+ (kuUqy + (kE Eq)2 /3 . Релевантность в данном случае понимается в том смысле, что с уменьшением Wq должно уменьшаться и Tq. Поэтому вновь поступивший запрос следует направлять в очередь с минимальным Wq.

Коэффициенты Icq , ки и кЕ характеризуют относительную степень влияния параметров Qq, Uq и Eq на величину Tq. Например, kQ - степень достоверности того, что Qq оказывает большее влияние на Tq , чем Uq и Eq. В соответствии с формулой (*) и известными рекомендациями по мягким вычислениям эти коэффициенты вычисляются по формулам:

12

ко = [«а/и, ) (Оч/Еч) + (ич/Еч) + (Оч/Еч) (Еч/ич)] /3,

ки = [(Ц/Оч) (ич/Еч) + (и^,) (Оч/Еч) + (ич/Еч) (Еч/Оч)] /3, кЕ = [(Еч/С>ч) (Еч/ич) + (Еч/Оч) (Оч/ич) + (Еч/ич) (11^)] /3.

Уровни предпочтений Оч/ич (скорее , чем ич), ич/Еч (скорее ич, чем Еч) и др. вычисляются согласно принятым функциям распределения ц(х) (рис. 12, случай треугольных зависимостей Цн.мх), х € {Qq, ич , Еч} и найденной заранее базе знаний. Пусть найденная база знаний отвечает табл. 2, Ь, М, Н - значения лингвистической переменной х. Тогда

Еч/<2, = ЦН(С>Ч) • Цм(ич) • ЦМ(ЕЧ), (Зч/Е, = цн(<Зч)' Ць(ич) • ць(Еч)

и т. д. Запись означает, что ц(<Зч) определяется по графику рис. 12 для Н.

Характерно, что знак импликации заменяется знаком равенства. Результат вычисления левой части - это оценка уровня предпочтения, например, Еч перед С?ч.

База знаний Таблица 2.

ч<№

ll lm lh ml mm мн hl нм нн

1ц/е, да

ослд, 6л j»/eo

Рис. 12. Функции принадлежности

Случай «круговых» распределений. Совмещения при обработке соседних запросов во внутренних очередях отсутствуют. В тесте ТРС-Н - всего 14 запросов без операций INSERT и UPDATE. Для них получены времена автономной обработки в монокластере СУБД Clusterix-I (конфигурация «линейка», h=3) для платформы НРС-кластера. Эти времена, упорядоченные по возрастанию, представлены в табл. 3. Вес каждого запроса р,= Vt^, где t, - время обработки i-запроса в Clusterix-I, tmax - время обработки самого трудоемкого запроса.

Относительные времена обработки запросов Таблица 3.

№ п/п 1 2 3 4 5 6 7 8 9 10 11 12 13 14

t¡ сек. 10 11 12 22 23 24 37 41 42 43 44 46 50 105

Pi 0,09 0,10 0,11 0,21 0,22 0,23 0,35 0,39 0,40 0,41 0,42 0,44 0,48 1

На множестве выбранных запросов сгенерированы три последовательности длины М=1000 каждая, отвечающие трем законам распределения: равномерному, нормальному (параметр «математическое ожидание» ц=7,5; параметр «дисперсия» а2=3,0) и пуассоновскому (параметр «математическое ожидание» Х=10). Разные законы отвечают различным нагрузочным характеристикам. Из каждой последовательности запросов для анализа выбирался интервал те {10°.900}.

Сравнивались «круговые» распределения запросов при к<= {13}- Полученные графики временных рядов Тзг(г) = 1згк (г) / М(^зг) имеют примерно одинаковый вид для всех рассмотренных случаев, независимо от закона распределения запросов в последовательности. На рис. 13 показан график для случая к=1 при равномерном распределении запросов в последовательности.

13

1.6 г .........: ..............:""..............~ " ................._.....

0,6 < ■ - - ■ - ..........- ------

0.4 -1............ -......................... . - -..... ......... - ---------------------

0.2 .............. -........... ............... - — - ' - ^

Рис. 13. График временного ряда По полученным значениям элементов временных рядов найдены величины М и о для последовательности с равномерным законом распределения запросов (табл. 4). Вариант к=1 оказался наиболее эффективным для СУБД без совмещений.

Сравнение М и а Таблица 4.

к 1 2 3 4 5

М 2,491663 2,489938 2,493 2,491188 2,49315

с 0,365376 0,410244 0,444443 0,494686 0,5336

Анализ при наличии совмещений. Особенностью Clusterix-I является наличие в системе совмещений в обработке соседних запросов во внутренних очередях (длиной не менее 2 запросов) благодаря использованию регулярного плана. «Круговой» вариант распределения к=1 в этом случае заведомо неприемлем.

Моделирование проведено на платформе НРС-кластера. Обрабатывалась запросная последовательность длины М=140, при этом для анализа выбирались me {Тцзо}, п=3, N=20. Установлено качественное совпадение поведения характеристик А/(к) и а(к), ке {2З}, при наличии и отсутствии совмещений. Случай к=1 с совмещениями показал максимум М при минимуме о на множестве ке (£б }• Численный метод определения весовых коэффициентов для «модельного» распределения. Для определения весовых коэффициентов, используемых в модели, требуется произвести поиск локальной базы знаний, релевантной текущему потоку запросов, в динамике работы системы без остановки СУБД. Выполнить такой поиск (он необходимо итеративен) на инструментальной СУБД не представляется возможным из-за естественных временных ограничений и неизвестности гипотетического идеала (эталона, пусть нереализуемого), к которому следует осуществлять приближение.

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

Поиск локальной базы знаний. Предпочтительным способом распределения для СУБД без совмещений оказался «круговой» алгоритм при к=1. Он принимался за эталонный («идеальный»), с ним сравнивалось «модельное» распределение. Требуется итеративным способом найти базу знаний, при использова-

14

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

Д;=<(М)-М0)2+(о -с^ <Я = £ еа0. Здесь: Д ¡ - величина Д в ¡-итерации;

М-, - значение средней задержки на интервале т для ¡-ой базы знаний;

М0 - средняя задержка полученная для эталонного «кругового» распределения при к=1;

- среднеквадратическое отклонение задержек ответа на запрос пользователя для ¡-ой базы знаний; о0 - значение среднеквадратического отклонения задержек полученное для эталонного «кругового» распределения при к=1;

Искомое решение лежит внутри круга радиуса К = еоо0 (рис. 14), где е -заданная величина относительного отклонения от варианта к=1. Предполагается, что среднеквадратичное отклонение является наиболее важной характеристикой. Поэтому значение К определялось по величине о0.

Сравнение М и о Таблица 5.

К=1 МОЭЕ1. К=2

м 2.4916625 2,49189 2,4599375

с 0,36537599 0,353957 0,41024395

оМ 0,14663944 0,15409 0.16476075

100 100,0091 99.9307691

Чо> 100 105.00369 112.279951

М -Ц: М

Рис. 14. Область поиска

База знаний - локальна, так как используемые в модели параметры порядка - это некоторые внешние первичные параметры модели. Они определяют степень влияния на производительность кластера множества других факторов (внешних и внутренних) в совокупности. Характер этого влияния остается неизвестным и, скорее всего, нелинейным. Поэтому найденная база знаний будет справедлива только для данных схемы БД, потока запросов, платформы, УБД, п, Ь.

Генетический подход к поиску. За основу алгоритма поиска релевантной базы знаний принят канонический генетический алгоритм Дж. Холланда. Генотип состоит из 6 генов (рис. 15). Позиция каждого гена в генотипе строго фиксирована. Номер занимаемой им ячейки в таблице базы знаний при ее сканировании слева направо и сверху вниз может варьироваться от 1 до 27 (по числу клеток табл. 2). Соответственно меняется десятичный код гена («номер» на рис. 16). В пределах одного генотипа все номера различны.

1 особь Г

2 особь Г

Точка разрыва

Генотип

Т

и

и

1 потомокр

Рис. 15. Структура генотипа

Г ены

Рис. 16. Иллюстрация процесса скрещивания 15

Начальная популяция формируется случайным образом. Для скрещивания при помощи рулеточного алгоритма в популяции определенное число раз отбираются по два элемента - по две «родительские» особи (рис. 15) с учетом значений их фитнесс-функций Ф. Точка разрыва задается случайным образом.

Далее с вероятностью 0,5 выбирается один из потомков и помещается в новую популяцию. С вероятностью мутации рт к потомку применяется мутация:

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

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

Использованный вычислительный алгоритм. АЛГОРИТМ. Для любой базы знаний текущей эпохи и особи текущей популяции

1. Сформировать первые п «круговых» очередей суммарной длины N.

2. i: = N+l.

3. Инициировать параллельную обработку запросов во всех очередях.

4. Ждать момента завершения обработки первоочередного запроса и его удаления в одной из очередей.

5. Согласно построенной модально-логической модели определить очередь -кандидата на пополнение.

6. Поместить i-запрос в очередь определенного кандидата.

7. i :=i+ 1. Если i< М, то переход к п. 4

8. Подсчитать значение М и а на m для каждой особи. По найденным значениям определить фитнесс функцию. Если хотя бы для одной особи Ф;< R, то эта особь принимается за решение и КОНЕЦ. Если указанному условию удовлетворяет несколько особей, то за решение принимается первое по порядку.

9. Если возможно увеличение номера эпохи, то изменить базу знаний согласно применяемому генетическому алгоритму и перейти к п.1.

10. Сгенерировать новую начальную популяцию. Перейти к п.1

По найденной базе знаний вычисляем весовые коэффициенты для модели.

Результаты сравнения характеристик «модельного» распределения с найденной базой знаний и вычисленными весовыми коэффициентами и «кругового» алгоритма при к=1 и к=2 представлены в табл. 5. Дополнительно указаны степени отклонения Л/ и а в процентах от эталонных значений (к=1). «Модельный» вариант явно предпочтителен в сравнении с к=2.

Заключительный вычислительный эксперимент. Для сравнения «модельного» и «кругового» (при к=2) распределений использована локальная база знаний, полученная ранее для случая без совмещений (табл. 2). На системе Clusterix-I обрабатывалась запросная последовательность длины М=145 (те {41,125}) при n=3, N=20, V6fl=5,4Gb. В табл. 6 приведены значения Ми ст.

Была определена степень отклонения в процентах М и о от эталонных значений (MODEL).

«Модельный» вариант распределения показывает выигрыш в 7% по среднему зна-че-нию задержки перед «круговым» (к=2) при практически неизменном среднеквадратичном отклонении. Полученные оценки качества по Ми а позволяют сделать выбор в пользу «модельного» способа распределений запросов.

В ЧЕТВЕРТОЙ ГЛАВЕ дается описание выполненной разработки специализированного инструментального средства моделирования. В качестве такового понимается не кросс-система, учитывающая особенности протекания процессов в исследуемых объектах, а инструментальная параллельная СУБД, которая воплощает основные тенденции мирового опыта в этом классе информационных систем. Хорошее приближение обеспечивает следование принципам, реализованным ранее в исследовательском прототипе параллельной СУБД Clusterix, но она была «жестко ориентирована» на использование аппаратной платформы кластера Pentium III с одноядерными узлами. Попытки запуска прототипа на современных платформах ПК- и НРС-кластеров с многоядерными узлами не увенчались успехом. Были выявлены следующие причины несовместимости Clusterix с новыми платформами:

- в узлах кластеров установлена новая 64-битная ОС семейства OpenSuse;

- на новой платформе используется новая версия СУБД MySQL 5.0, ориентированная на многоядерные узлы;

- требуют изменения конфигурационные файлы СУБД (ip адреса, номера портов и пр.)

- используется другая сеть для межузлового взаимодействия (GigabitEthernet, InfiniBand вместо FastEthernet);

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

Для устранения выявленных причин несовместимости:

1) были проанализированы и изменены исходные коды программных модулей составляющих основу системы (mlisten, msort, irun, jrun);

2) во все внутренние процедуры модулей (рис. 17) были до- Рис , 7 Структурная схема СУБД бавлены функции из новой версии

Сравнение М и а Таблица 6.

к=2 MODEL

м 305.011"65 2S3.952941

а 71.6497189 "0.914016S

ст Л/ 0.23490805 0.249~3S62

107.42 100

V о) 101 100

MySQL 5.0, предназначенные непосредственно для работы множества потЬков:

- myJnitO,

- my_thread_init(),

- my_thread_globalJnit(),

- my_thread_end();

3) для осуществления блочной записи была переработана основная внутренняя функция MySQL, записывающая на диск:

- mi_write(...).

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

4) новая функция встроена в СУБД:

- int mi_write_block (...);

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

6) сетевое взаимодействие между модулями системы было реализовано с помощью функций из библиотеки socket, для устранения разрывов связи при сильной загруженности системы написана дополнительная системная функция, которая была интегрирована в модули СУБД:

- int SetFlag_SA_RESTART() - изменяет стандартное поведение обработчиков сигналов (программное прерывание, доставляемое процессу) ОС Linux, для всех сигналов (кроме сигналов с номерами signum=9,19,32) в структуру sigaction обработчика сигналов добавлен флаг SA_RESTART. Его установка, значительно повысила стабильность работы системы;

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

Разработанная новая система получила название Clusterix-I.

Рекомендации к построению модуля ROUTER В модуле целесообразно реализовать варианты распределений: «модельное», «круговое» (к=1 и к=2). Для «модельного» способа должна быть предусмотрена возможность отслеживания характера поступающих в обработку запросов для фиксации момента, когда необходим поиск новой базы знаний. ROUTER осуществляет динамический анализ лог-файлов, в них фиксируется сложность поступающих запросов. Преобладание в обрабатываемом потоке запросов, сложность которых не укладывается ни в одну из выделенных изначально групп, говорит о необходимости поиска новой базы знаний. Программная система модуля ROUTER представлена структурной схемой рис. 18. Стрелками показан поток передачи команд.

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

В Clusterix-I в модуле ROUTER реализованы: круговой алгоритм распределения при к=2; «модельный» алгоритм; входящая очередь запросов (буфер, реализованный в виде массива структур); механизм ведения очередей поступающих в систему запросов - динамические массивы (библиотека vector в С++); система ведения лог файла работы; служебный фоновый процесс, осуществляющий подключение к мониторам кластеров-компонент в динамике работы; процесс, осуществляющий прием запроса, его обработку и передачу результата пользователю.

В ЗАКЛЮЧЕНИИ сформулированы основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Сформулированная во введении цель работы - повышение эффективности (по критерию «производительность/сложность») использования вычислительных кластеров заданной сложности с многоядерными SMP-узлами при реализации на них параллельных СУБД консервативного типа с регулярным планом обработки запросов - достигнута в диссертации путем проведения комплексного моделирования процессов балансировки нагрузки в рассматриваемых системах с помощью разработанного специализированного инструментального средства - системы моделирования Clusterix-I.

Были получены следующие основные результаты:

1. Обоснована правомерность перехода на позиции мультикластерных СУБД консервативного типа с регулярным планом обработки запросов в составляющих монокластерах на многоядерных SMP-узлах, выработаны рекомендации по декомпозиции кластера в целом на составляющие монокластеры и выбору архитектуры монокластера.

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

3. Построена имитационная модель исследуемого объекта (параллельная

в MOMTORj

Рис. 18 структурная схема ROUTER

СУБД рассматриваемого типа) - инструментальная система моделирования с

необходимыми измерительными средствами.

Приложение к диссертации составляют:

• Оттранслированные запросы теста ТРС-Н.

• Инструкция пользователя системы Clusterix-I.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемых журналах:

1. Минязев Р.Ш., Райхлин В.А. Балансировка нагрузки в мультикластерных СУБД консервативного типа на Beowulf-платформе // Вестник КГТУ им. А.Н. Туполева, 2011. №1. С. 52-57.

2. Райхлин В.А., Минязев Р.Ш. Мультикластеризация распределенных СУБД консервативного типа // Нелинейный мир, 2011. №8. С. 473-481.

Другие публикации:

3. Минязев Р.Ш. Реализация многокластерной архитектуры параллельной СУБД // Туполевские чтения: Материалы 16-й Междунар. молод, научн. конф. - Казань: Изд-во КГТУ им. А.Н. Туполева, 2008. Т.З. С. 50-52.

4. Минязев Р.Ш. Мультикластерная версия параллельной СУБД Clusterix // Тр. конф. НРС-2008. - Казань: Изд-во КГТУ им. А.Н. Туполева, 2008. С. 235-238.

5. Минязев Р.Ш., Шагеев Д.О. Сравнительный анализ возможностей позиционирования двух параллельных СУБД на Beowulf-платформу // Тр. конф. НРС-2009. - Владимир: Изд-во ВГУ, 2009. С. 291-293.

6. Минязев Р.Ш., Попов A.B. Временные доминанты кластеров баз данных // Методы моделирования / Под ред. В.А. Райхлина. - Казань: Изд-во «Фэн» («Наука»), 2010. С. 125-134.

7. Минязев Р.Ш. Решение задачи распределения запросов в мультикластерной СУБД без совмещеий // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы XI Всероссийской конференции / Под ред. проф. В.П. Гергеля. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 208-212.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,25. Усл. печ. л. 1,16. Уч.-изд. л. 1,0.

_Тираж 100. Заказ А 20._

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

61 12-5/3228

КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ А.Н.ТУПОЛЕВА - КАИ

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

МИНЯЗЕВ РИНАТ ШАВКАТОВИЧ

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

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

Диссертация

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

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

Казань - 2012

СОДЕРЖАНИЕ

ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ.....................................4

ВВЕДЕНИЕ.....................................................................................5

Глава 1. СОСТОЯНИЕ ВОПРОСА И ПРЕДМЕТ ИССЛЕДОВАНИЙ............14

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

1.2. Проекты высокопроизводительных СУБД.......................................20

1.3. Системы мониторинга и визуализации параллельных СУБД................27

1.4. Прототип базовой системы моделирования......................................30

1.5. Задача работы и пути ее решения..................................................36

1.6. Выводы...................................................................................38

Глава 2. ПРИНЦИПЫ И ЦЕЛЕСООБРАЗНОСТЬ ПЕРЕХОДА К МУЛЬТИ-

КЛАСТЕРИЗАЦИИ..............................................................40

2.1. Принципы перехода к мультикластеризации.................................40

2.2. Временные доминанты функционирования монокластера...................50

2.3. Эффективность перехода к мультикластеризации..............................55

2.4. Выводы...................................................................................57

Глава 3. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ В МУЛЬТИКЛАСТЕРЕ......................................................58

3.1. Постановка подзадачи роутеризации..............................................................58

3.2. Модально-логическая модель распределений...................................62

3.3. Сравнительный анализ для случая «круговых» распределений.............69

3.4. Численный метод определения весовых коэффициентов.....................75

3.5. Заключительный вычислительный эксперимент................................79

3.6. Выводы....................................................................................81

Глава 4. РАЗРАБОТКА ИНСТРУМЕНТАЛЬНОЙ СИСТЕМЫ МОДЕЛИРОВАНИЯ .............................................................................82

4.1 Причины несовместимости базового прототипа с новыми платформами..82

4.2 Выполненные доработки прототипа................................................84

4.3 Рекомендации по построению программного модуля ROUTER.............89

4.4 Выводы....................................................................................92

ЗАКЛЮЧЕНИЕ................................................................................94

ЛИТЕРАТУРА.................................................................................95

ПРИЛОЖЕНИЯ..............................................................................102

Приложение А. Оттранслированные запросы теста ТРС-Н........................ 102

Приложение Б. Инструкция пользователя системы Clusterix-I ................... 112

ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ

ПК - Персональный компьютер

СУБД - Система управления базами данных

БД - База данных

НМД - Накопители на магнитных дисках

ЕС ЭВМ Единая система электронных вычислительных машин

HPC - High performance computer

OLAP - Online analytical processing

DSS - Decision support system

OLTP - Online transaction processing

SMP — Symmetric multiprocessing

EOS — Earth observing system

CERN - European center for nuclear research

SNMP - Simple network management protocol

MPP - Massive parallel processing

WLCG Worldwide large hadron collider computing grid

SLAC Stanford linear accelerator center

SDSS Sloan digital sky survey

EOSDIS Earth observing system data and information system

ATM Asynchronous transfer mode

SDC Super database computer

SCSI Small computer system interface

API Application programming interface

SSH Secure shell

SSL Secure sockets layer

MPP Massive parallel processing

ВВЕДЕНИЕ

Актуальность темы. Основной тенденцией последнего времени в сфере интеллектуальной обработки данных является использование высокопроизводительных параллельных СУБД [1, 20]. Объемы накопленной информации для многих баз данных превышают десятки терабайт. Примерами приложений, работающими с такими объемами данных, являются корпоративные базы данных [2], электронная коммерция [3], электронные библиотеки [4], геоинформационные системы [5, 6], социальные сети [7] и многие другие. Особое место в этом перечне занимают приложения, работающие с научными базами данных [8], где объемы хранимой и обрабатываемой информации достигают петабайт-ных значений. Использование параллельных систем баз данных для хранения и продуктивного анализа накопленных колоссальных объемов информации оказывается единственным приемлемым решением.

Имеется ряд исследовательских и коммерческих проектов параллельных СУБД: DB2 Parallel Edition [9], Greenplum [10], NonStop SQL [11], Teradata [12], MySQL Cluster [13], PG Cluster [14], Oracle EXADATA [15], Sybase IQ [16], Microsoft SQL server (проект Madison) [17], NEDO-lOO [18], Омега [19] и др. Большинство из них характеризуется высокой стоимостью и ориентированностью на использование мощной кластерной аппаратной платформы. Перечисленные системы ориентированы в первую очередь на поддержку работы internet-cep-висов, т.е. на выполнение множества сравнительно простых операций типа select,insert,delete над динамически изменяемыми данными.

Однако тенденции развития технологии аналитической обработки данных OLAP (online analytical processing) [21] и актуализация смежных задач, сопутствующих OLAP (создание хранилищ данных (data warehouse) [22], построение систем поддержки принятия решений (DSS) [23], интеллектуальный анализ данных (data mining) [24]), определяют необходимость построения специализированных высокопроизводительных параллельных СУБД консервативного типа (с эпизодическим обновлением баз данных в специально выделяемое время) с хорошей масштабируемостью, функционирующих на сравнительно

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

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

Проведение подобных исследований затруднено отсутствием универсальных кросс-систем и специализированных инструментальных средств моделирования в ранее перечисленных разработках. В настоящее время имеются проекты универсальных систем моделирования [25]. Но они не ориентированы на детальный анализ процессов, протекающих в параллельных СУБД. Исследовательский проект параллельной СУБД Clusterix [26] является в этом смысле редким исключением. По сути это - специализированная система моделирования кластерных СУБД консервативного типа с регулярным планом обработки запросов [27]. Детальный анализ динамики на ее основе помогает развитию элементов теории таких СУБД. Ее использование как инструментального средства моделирования позволило сформулировать гипотезу масштабируемости [28], установить рост масштабируемости с переходом к СУБД с многокластерной

архитектурой [29] и др.

Серьезными проблемами для любых параллельных СУБД являются: масштабируемость - как по числу узлов, так и по числу пользователей [30, 31], обеспечение отказоустойчивости [32, 33], балансировка нагрузки и размещение

данных между узлами [34, 35, 36].

Среди перечисленных проблема балансировки нагрузки занимает ключевое место [35, 37]. Именно с ее решением связывается повышение эффективности и масштабируемости параллельной СУБД. Над этой проблемой работает множество коммерческих организаций (Google, Microsoft, Yahoo, Intel, IBM). Ее

исследованию посвящено множество работ. Разработаны масштабируемые протоколы репликации данных для кластерных систем высокой отказоустойчивости [38]. Созданы масштабируемые алгоритмы кластеризации данных для больших баз данных [39]. Разработаны средства управления и мониторинга для кластерных СУБД [40]. Развиты методы горизонтального и вертикального разделения данных между узлами в параллельных СУБД [41]. Имеются проекты использования не реляционной модели МарЯес1исе при построении параллельных СУБД [42]. Проводятся исследования по организации асинхронного взаимодействия (с хорошей масштабируемостью) в параллельных СУБД [43]. В работе [44] предложено решение проблемы балансировки загрузки для систем без совместного использования ресурсов, основанное на репликации. Данное решение позволяет уменьшить накладные расходы на передачу данных по сети в процессе балансировки загрузки. Однако этот подход применим в весьма узком контексте пространственных баз данных в специфическом сегменте диапазонных запросов. В работе [34] задача балансировки загрузки решается путем частичного перераспределения данных перед началом выполнения запроса. Данный подход уменьшает суммарное количество пересылок данных между вычислительными узлами в ходе обработки запроса, однако накладывает серьезные требования на скорость межпроцессорных коммуникаций.

Решение задачи балансировки нагрузки для параллельных СУБД, функционирующих на платформах вычислительных кластеров заданной сложности связывается с программной настройкой кластера на архитектуру мультикласте-ра. Такое решение требует детального изучения вопросов выбора сложности монокластера (выделяемого настройкой «тяжелого» [45] узла), его архитектуры и балансировки нагрузки между монокластерами. В настоящей работе изучению этих вопросов уделено основное внимание.

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

Предмет исследования - правомерность перехода на позиции мульти-кластерных СУБД указанного типа; рекомендации по декомпозиции кластера в целом на составляющие монокластеры и выбору архитектуры монокластера; моделирование процесса распределения запросов между монокластерами; инструментальная система моделирования для проведения необходимого вычислительного эксперимента.

Цель диссертационной работы - повышение эффективности (по критерию «производительность/сложность») использования вычислительных кластеров заданной сложности с многоядерными БМР-узлами при реализации на них параллельных СУБД консервативного типа с регулярным планом обработки запроса.

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

Эта комплексная задача разбивается на 3 подзадачи:

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

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

3. Построение имитационной модели исследуемого объекта (параллельной СУБД рассматриваемого типа) - инструментальной системы моделирования с необходимыми измерительными средствами.

Методы исследования. Исследования проводились с привлечением методологии вычислительного эксперимента; теории системного и параллельного программирования; теории баз данных; методов обработки временных рядов; модальной логики с использованием семантики Крипке и системы нечеткого вывода; принципов построения генетических алгоритмов; методов статистической обработки результатов эксперимента.

Основные научные результаты, полученные автором и выносимые на защиту:

1. Платформо-независимость качественных закономерностей масштабируемости монокластеров параллельных СУБД консервативного типа с регулярным планом обработки запросов, выявленных ранее [28] для случая вычислительных кластеров с одноядерными узлами; рекомендации по декомпозиции базового кластера в целом на монокластеры; наиболее эффективные конфигурации таких монокластеров и их временные доминанты для случая многоядерных БМР-узлов; эффективность выбора для мультикластерных СУБД регулярного плана обработки запросов в составляющих кластерах и существенное улучшение масштабируемости с переходом на позиции мультикластеризации.

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

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

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

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

2. Построена математическая модель процесса распределения запросов между монокластерами с применением семантики Крипке и механизмов нечеткого вывода. Эта модель отличается от ранее использованной для динамической реструктуризации параллельных СУБД [46] изменением семантики миров Крипке (теперь это - миры параметров, а не миры архитектур), специфичным выбором характеристик предпочтения на множестве таких миров (весовые коэффициенты параметров) и критерия предпочтения на множестве монокластеров (минимум веса очереди запросов).

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

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

Практическую ценность работы составляют:

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на международной молодежной научной конференции «Туполевские чтения» (Казань, 2008 г.), республиканском научном семинаре АН РТ «Методы моделирования» (Казань, 2009-2011 гг.), международных конференциях «Высокопроизводительные параллельные вычисления на кластерных системах» НРС-2008, 2009, 2011 (Казань, 2008г.; Владимир, 2009 г.; Нижний Новгород, 2011 г.).

Публикации. Результаты диссертационной работы отражены в 7 публикациях, в том числе 3 - в трудах конференций [90,91,92], 4 - научные статьи [29,62,79,83] (из них 2 [62,79] - в рецензируемых журналах).

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

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