WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

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

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

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

АВТОРЕФЕРАТ

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

Казань 2012

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Казанский национальный исследовательский технический университет им. А.Н.Туполева-КАИ»

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

Официальные оппоненты: Елизаров Александр Михайлович, доктор физико-математических наук, профессор, Институт математики и механики им. Н.И. Лобачевского Казанского федерального университета, заместитель директора по научной работе Ризаев Ильдус Султанович, кандидат технических наук, доцент, Казанский национальный исследовательский технический университет им. А.Н. Туполева кафедра автоматизированных систем обработки информации и управления, профессор Ведущая организация Институт информатики Академии наук Республики Татарстан, г. Казань

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

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

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

Ученый секретарь диссертационного cовета Данилаев Петр Григорьевич

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

Актуальность темы. В сфере интеллектуальной обработки данных принят ориентир на использование высокопроизводительных параллельных СУБД:

корпоративные базы данных (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-100, Омега и др. Большинство из них – универсально, ориентировано на решение широкого круга задач в различных предметных областях. Для них характерно выполнение множества сравнительно простых операций типа select, insert, delete над динамически изменяемыми данными.

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

Серьезными проблемами для любых параллельных СУБД являются:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A, B, C, D, E, F, G, H W.

W – искомая программная модель;

A – внешний язык запросов – SQL;

B – внутренний язык запросов – MySQL;

C – общая стратегия обработки запросов: множество процессоров на запрос;

D – используются одноканальные накопители на магнитных дисках (НМД);

E – база данных распределяется между несколькими НМД с применением механизма хеширования;

F – имеются нижний (операции Input, Select, Project) и верхний (операции Join, Sort) уровни обработки;

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

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

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

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

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

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

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

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

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

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

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

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

Исполнение операций и на исходным отношением БД, получение промеIO_EXEC жуточного отношения R’(сохраняется в главной памяти процессора IO) Проведение операции хеширования (деление по модулю на число процессоIO_HASH ров IO) над отношением R’ по полю, участвующему в соответствующей операции соединения Пересылка частей отхешированных отношений R’ между процессорами IO в IO_WAIT_LOAD соответствии с полученными на предыдущем этапе значениями хешфункций и формирование итоговых отношении R’ на каждом IO Ожидание пока все модули IO выполнят предыдущие операции (барьерная IO_WAIT_SYNC синхронизация модулей IO) Пересылка итоговых промежуточных отношений R’ с процессоров IO на соIO_NET_IO_JOIN ответствующие процессоры JOIN JOIN_creating IN- Создание индексов для промежуточного отношения R’, пришедшего с преDEX before JOIN дыдущего такта работы конвейера IO Выполнение операции соединения над R’ и временным отношением Rв(i-1), JOIN_EXEC пришедшим с предыдущего такта работы конвейера JOIN, формирование временного отношения Rв(i) Проведение операции хеширования (деление по модулю на число процессоJOIN_HASH ров JOIN) над отношением R’ по полю, участвующему в соответствующей операции соединения Перемешивание отхешированных отношений Rв(i) между всеми процессJOIN_WAIT_LOAD сорами JOIN(пересылка кортежей по сети и формирование отношении Rв(i)) Ожидание пока все модули JOIN выполнят предыдущие операции (барьерная JOIN_WAIT_SYNC синхронизация модулей JOIN) JOIN_creating INСоздание индексов для сформированных отношении Rв(i).

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

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

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

3) существенное влияние на быстродействие системы при h < hG этапа IO_EXEC (экспонента на рис. 8; – отношение суммарного объема работ Ti по этапу к общему объему работ по всем этапам T); но при h=hG это влияние существенно ослабевает;

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

Рис. 7. Суммарный объем работ по этапам Тестирование производительности равносложных однокластерных и многокластерных архитектур с помощью Clusterix-I показало правомерность использования подхода мультикластеризации для повышения эффективности параллельных СУБД на платформе вычислительных кластеров с многоядерными узлами и наличие асимптотического ограниче Рис. 8. Выявление временных доминант ния производительности мультикластерных систем с ростом числа монокластеров (рис. 9-10).

В ТРЕТЬЕЙ ГЛАВЕ строится математическая модель для эффективного решения задачи распределения запросов между монокластерами в мультикластерной СУБД и предлагается релевантный этой модели численный метод. Эффективность предложенной модели устанавливается по результатам сравнительного вычислительного эксперимента на множестве различных методов распределений. В качестве оценочных критериев приняты величины среднеквадратического отклонения и математического ожидания времени реакции системы на вновь поступивший запрос.

Рассматриваемые мультикластерные СУБД представлены на рис. 11. База данных реплицируется между монокластерами. Распределение непрерывного потока запросов, поступающих от N клиентов – Client_i, { }, между n i 1, N кластерами-компонентами осуществляет модуль ROUTER. Входной поток запросов длины M, поступающий на обработку в систему, формируется случайным образом на множестве Q из запросов теста TPC-H без операций записи. Рассматривается случай, когда очередной запрос от каждого пользователя поступает на вход СУБД не ранее, чем будет получен ответ на предыдущий запрос. Поэтому в любой момент Рис. 11. Мультикластерная СУБД времени суммарное число запросов, находящихся в системе L N. В дальнейшем полагается L=N. Рассматривается множество из двух классов распределений: т. н. «круговые» и «модельное».

Для «круговых» распределений вводится два вида очередей запросов:

внутренних (в кластерах-компонентах) и внешней (в ROUTER). Суммарная длина всех внутренних очередей =kn N, k 1. Длина внешней очереди n L– 0. Первые запросов распределяются по кластерам-компонентам в n n порядке мест, занимаемых ими в обрабатываемой последовательности:

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

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

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

N Обозначим: – задержка ответа на вновь поступающий r-запрос (r R t зr ={ N 1, M }, вычисляемая как разность времен появления результатов обработки r и (r–N) запросов в каждом случае. Путем вычислительного эксперимента для разных распределений будем получать графики временных рядов (r)= фN зr N (r)/M(t N ), варьируя число n монокластеров и количество N пользователей.

t зr зr Среднестатистическое время ожидания ответа на вновь поступивший заN прос оценен величинами математического ожидания M( )) = ( tN ) / m и t зr зr r N N t t зr зr среднеквадратического отклонения = M [ – M( )]2 как характеристику релевантности оценки по M (оценка тем более релевантна, чем меньше ).

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

Модель распределения запросов построена с использованием ряда соглашений модальной (немонотонной) логики. С понятием модальности связывается семантика возможных миров (семантика Крипке). В ней универсум W – множество возможных миров {s, t, u, …}, связанных отношением доступности (предпочтительности) R. Факт доступности мира j после i: iRj, i, j W.

В рассматриваемом случае миры Крипке – это миры параметров. Для них проведена ранжировка степеней влияния тех или иных параметров. Рассматривался случай трех миров W={s, t, u}. Факт предпочтительности в смысле R одного мира, например, s, перед другими обозначается как sR(t,u) и определяется s t u [sRt sRu sR(t,u )]. Далее для повышения чувствительности разрабатываемой модели использовано известное положение (Райхлин В.А.):

s t u [(sRt sRu) (sRt tRu) (sRu uRt) sR(t,u )] (*).

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

В качестве параметров порядка для данных схемы БД, платформы, VБД взяты элементы вектора , который принимается за характеристику нагрузки q-кластера; q – номер внутренней очереди, т. е. номер кластера {1,n} (q – от queue – очередь);

Qq – средняя относительная сложность одного запроса в q-очереди (Q – от Quantity –количество) w q Qq = ( ) / (wqcбд) [0, 1], с i i wq – число запросов в q-очереди, сбд – общее число отношений базы данных, сi – число еще не затронутых обработкой отношений в i-запросе q-очереди.

Эмпирически найденное выражение для подсчета с1:

с1 с, = exp(-b/2).

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

Uq – cредний коэффициент использования базы данных одним запросом qочереди (U – от Usage – использование) w q с i Uq = ( ) / (wq VБД) [0, 1], V ji i 1 j Vji – объем еще не затронутого обработкой j-отношения в i-запросе q-очереди.

Для первоочередного запроса эмпирически найдено:

с 1 с k.

V j1 V jj 1 j Смысл обозначений k и c – прежний;

Eq – оценка относительной длины q-очереди (E – от Estimation – оценка) n Eq = wq / [0, 1].

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

Wq = (kQ Qq)2 + (kU Uq)2 + (kE Eq)2 /3.

Релевантность в данном случае понимается в том смысле, что с уменьшением Wq должно уменьшаться и Tq. Поэтому вновь поступивший запрос следует направлять в очередь с минимальным Wq.

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

kQ = [(Qq/Uq ) (Qq/Eq) + (Qq/Uq) (Uq/Eq) + (Qq/Eq) (Eq/Uq)] /3, kU = [(Uq/Qq) (Uq/Eq) + (Uq/Qq) (Qq/Eq) + (Uq/Eq) (Eq/Qq)] /3, kE = [(Eq/Qq) (Eq/Uq) + (Eq/Qq) (Qq/Uq) + (Eq/Uq) (Uq/Qq)] /3.

Уровни предпочтений Qq/Uq (скорее Qq, чем Uq), Uq/Eq (скорее Uq, чем Eq) и др. вычисляются согласно принятым функциям распределения (х) (рис.

12, случай треугольных зависимостей ), x {Qq, Uq, Eq} и найденной заH,M,L ранее базе знаний. Пусть найденная база знаний отвечает табл. 2, L, M, H – значения лингвистической переменной x. Тогда Eq/Qq = H(Qq) M(Uq) M(Eq), Qq/Eq = H(Qq) L(Uq) L(Eq) и т. д. Запись H(Qq) означает, что (Qq) определяется по графику рис. 12 для H.

Характерно, что знак импликации заменяется знаком равенства. Результат вычисления левой части – это оценка уровня предпочтения, например, Eq перед Qq.

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

Рис. 12. Функции принадлежности Случай «круговых» распределений. Совмещения при обработке соседних запросов во внутренних очередях отсутствуют. В тесте TPC-H – всего запросов без операций INSERT и UPDATE. Для них получены времена автономной обработки в монокластере СУБД Clusterix-I (конфигурация «линейка», h=3) для платформы HPC-кластера. Эти времена, упорядоченные по возрастанию, представлены в табл. 3. Вес каждого запроса pi= ti/tmax, где ti – время обработки iзапроса в Clusterix-I, tmax – время обработки самого трудоемкого запроса.

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

№ п/п 1 2 3 4 5 6 7 8 9 10 11 12 13 ti сек. 10 11 12 22 23 24 37 41 42 43 44 46 50 1pi 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 На множестве выбранных запросов сгенерированы три последовательности длины M=1000 каждая, отвечающие трем законам распределения: равномерному, нормальному (параметр «математическое ожидание» µ=7,5; параметр «дисперсия» 2=3,0) и пуассоновскому (параметр «математическое ожидание» =10).

Разные законы отвечают различным нагрузочным характеристикам. Из каждой последовательности запросов для анализа выбирался интервал m {100,900}.

Сравнивались «круговые» распределения запросов при k {1,5 }. ПолуN N фN t t зr зr зr ченные графики временных рядов (r) = (r) / M( ) имеют примерно одиk наковый вид для всех рассмотренных случаев, независимо от закона распределения запросов в последовательности. На рис. 13 показан график для случая k=при равномерном распределении запросов в последовательности.

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

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

k 1 2 3 4 M 2,491663 2,489938 2,493 2,491188 2,493 0,365376 0,410244 0,444443 0,494686 0,53Анализ при наличии совмещений. Особенностью Clusterix-I является наличие в системе совмещений в обработке соседних запросов во внутренних очередях (длиной не менее 2 запросов) благодаря использованию регулярного плана.

«Круговой» вариант распределения k=1 в этом случае заведомо неприемлем.

Моделирование проведено на платформе HPC-кластера. Обрабатывалась запросная последовательность длины M=140, при этом для анализа выбирались m { }, n=3, N=20. Установлено качественное совпадение поведения харак41,1теристик M(k) и (k), k { }, при наличии и отсутствии совмещений. Случай 2,k=1 с совмещениями показал максимум М при минимуме на множестве k { }.

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

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

Поиск локальной базы знаний. Предпочтительным способом распределения для СУБД без совмещений оказался «круговой» алгоритм при k=1. Он принимался за эталонный («идеальный»), с ним сравнивалось «модельное» распределение. Требуется итеративным способом найти базу знаний, при использовании которой значения качественных оценок M и для «модельного» распределения близки по заданному критерию близости к получаемым для «идеального» варианта. Этот критерий определим следующей формулой i =(Mi – M0)2+(i – 0)2 R 0.

Здесь: i – величина в i-итерации;

Mi – значение средней задержки на интервале m для i-ой базы знаний;

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

i – среднеквадратическое отклонение задержек ответа на запрос пользователя для i-ой базы знаний;

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

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

Поэтому значение R определялось по величине 0.

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

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

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

В пределах одного генотипа все номера различны.

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

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

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

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

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

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

2. i : = N + 1.

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

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

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

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

7. i := i + 1. Если i M, то переход к п. 8. Подсчитать значение M и на m для каждой особи. По найденным значениям определить фитнесс функцию. Если хотя бы для одной особи i R, то эта особь принимается за решение и КОНЕЦ. Если указанному условию удовлетворяет несколько особей, то за решение принимается первое по порядку.

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

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

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

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

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

«Модельный» вариант распределения Сравнение M и Таблица 6.

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

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

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

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

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

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

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

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

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

my_init(), my_thread_init(), my_thread_global_init(), my_thread_end();

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

– mi_write( …).

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

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

int mi_write_block (…);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оттранслированные запросы теста TPC-H.

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ В рецензируемых журналах:

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

Туполева, 2011. №1. С. 52-57.

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

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

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

4. Минязев Р.Ш. Мультикластерная версия параллельной СУБД Clusterix // Тр.

конф. HPC-2008. – Казань: Изд-во КГТУ им. А.Н. Туполева, 2008. C. 235-238.

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

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

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

Формат 60х84 1/16. Бумага офсетная. Печать офсетная.

Печ. л. 1,25. Усл. печ. л. 1,16. Уч.-изд. л. 1,0.

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

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




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.