Моделирование процессов балансировки нагрузки мультикластерных СУБД консервативного типа

Актуальность темы

Основной тенденцией последнего времени в сфере интеллектуальной обработки данных является использование высокопроизводительных параллельных СУБД [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] - в рецензируемых журналах).

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

4.4. ВЫВОДЫ.

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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