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

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

ПАН Константин Сергеевич

и

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

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

2 8 НОЯ 2013

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Челябинск — 2013

005540741

Работа выполнена на кафедре системного программирования ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

ЦЫМБЛЕР Михаил Леонидович кандидат физ.-мат. наук, доцент доцент кафедры системного программирования, ФГБОУ ВПО « Южно-Уральский государственный университет» (национальный исследовательский университет)

ЗЫКИН Сергей Владимирович доктор техн. наук, профессор зав. лабораторией методов преобразования и представления информации, ФГБУН «Институт математики им. С.П. Соболева» СО РАН;

СОБОЛЕВ Сергей Игоревич кандидат физ.-мат. наук научный сотрудник, Научно-исследовательский вычислительный центр ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова» Ведущая организация: ФГБУН «Институт программных

систем имени А.К. Айламазяна» РАН

Защита состоится 18 декабря 2013 г. в 12 часов на заседании диссертационного совета Д 212.298.18 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

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

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

Автореферат разослан 15 ноября 2013 г. арь

диссертационного совета

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

У/р^О-*«^ М.Л. Цымблер

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

Актуальность темы. В настоящее время одним из феноменов, оказывающих существенное влияние на область технологий обработки данных, являются сверхбольшие данные. В условиях современного информационного общества имеется широкий спектр приложений (социальные сети, электронные библиотеки, геоинформационные системы и др.), в каждом из которых производятся неструктурированные данные, имеющие сверхбольшие объемы и высокую скорость прироста (от 1 Терабайта в день). Исследования экспертов корпорации ЕМС показывают, что к 2020 г. мировой объем данных достигнет 40 Зеттабайт. Сверхбольшие данные путем интеллектуального анализа преобразуются в сверхбольшие реляционные базы данных, которые сохраняют в структурированном виде полученные результаты анализа, требующие параллельной обработки.

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

Существующие сегодня коммерческие СУБД, использующие фрагментный параллелизм (Teradata, Greenplum, DB2 Parallel Edition и др.), имеют высокую стоимость и, во многих случаях, ориентированы на специфические аппаратно-программные платформы. Альтернативой коммерческим СУБД являются свободные СУБД с открытым исходным кодом. Однако на сегодня отсутствуют свободные СУБД, реализующие фрагментный параллелизм. В связи с этим перспективной является идея модернизации существующего исходного кода свободной последовательной СУБД для построения на ее основе параллельной СУБД для кластерных вычислительных систем путем внедрения фрагментного параллелизма. При этом модернизация исходного кода не должна быть масштабной. Полученная параллельная СУБД должна демонстрировать хорошую масштабируемость, тогда недостаток производительности (по сравнению с коммерческими СУБД) может быть преодолен добавлением в кластер новых вычислительных узлов с сохранением экономичности данного решения.

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

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

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

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

3. Исследовать эффективность предложенных подходов применительно к решению задач классов OLAP и OLTP, связанных с обработкой сверхбольших баз данных.

Методы исследования. Проведенные в работе исследования базируются на реляционной модели данных. При разработке программной системы применялись методы объектно-ориентированного проектирования и язык UML. В разработке алгоритмов использован аппарат теории графов.

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

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

2. Впервые выполнено внедрение фрагментного параллелизма в последовательную СУБД PostgreSQL.

3. Разработан новый алгоритм разбиения сверхбольших графов, состоящих из миллионов вершин и ребер, ориентированный на реляционные СУБД с фрагментным параллелизмом.

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

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

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

— на. международной научной конференции DEXA'2013 (The 24th International Conference on Database and Expert- Systems Applications) (Чешская Республика, Прага, 26-30 августа 2013 г.);

— на международной научной конференции ADBIS'2013 (The 17th East-European Conference on Advances in Databases and Information Systems) (Италия, Генуя, 1-4 сентября 2013 г.);

— на международной научной конференции SYRCoDIS'2011 (The 7th Spring Researchers Colloquium on Databases and Information Systems) (Москва, 2-3 июня 2011 г.);

— на Международной сунеркомпьютерной конференции «Научный сервис в сети Интернет: все грани параллелизма» (Новороссийск, 2328 сентября 2013 г.);

— на международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2011)» (Москва, 28 марта - 1 апреля 2011 г.);

— на Международной суперкомпьютерной конференции «Научный сервис в сети Интернет: экзафлопсное будущее» (Новороссийск, 1924 сентября 2011 г.);

— на Втором Московском суперкомпьютерном форуме (МСКФ'2011), (Москва, 26-27 октября 2011 г.);

— на международной суперкомпьютерной конференции «Научный сервис в сети Интернет: сунеркомпыотерные центры и задачи» (Новороссийск, 20-25 сентября 2010 г.).

Публикации. По теме диссертации опубликовано 11 печатных работ и получено одно свидетельство Роспатента об официальной регистрации программы для ЭВМ. Работы [1-4] опубликованы в изданиях, включенных ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора и кандидата наук. В совместных работах научному руководителю М.Л. Цымблеру принадлежит постановка задачи, К.С. Пану принадлежат все полученные результаты.

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

Содержание работы

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

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

П.Код_П

11; = {<|4 6 П,<Я0 : ¿ = 0.....9

-г}

Функция фрагментации

сб<4> | (£.код_п 30

00

га н-I

•е

Результирующее отношение

□

а

ш х

X

о; ^

с; и

Рис. 1.

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

Функция фрагментации отношения Л

¡р : Я {0,1,..., к - 1}

вычисляет номер процессорного узла, на котором должен храниться кортеж. Величина к (количество процессорных узлов) называется степенью

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

Vr 6 Д(Ыг) = /а{г.А)),

где /д : Da —» {0,..., к — 1} является некоторой функцией, определенной на домене атрибута А. То есть атрибутная фрагментация предполагает, что функция фрагментации зависит от определенного атрибута фраг-ментируемого отношения. Преимущество атрибутной фрагментации в том, что она допустима основными реляционными операциями: группировка, удаление дубликатов, естественное соединение.

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

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

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

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

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

Параллелизм достигается за счет построения параллельного плана запроса. Параллельный план запроса представляет собой последователь-

ный план запроса, в нужные места которого вставлены операторы exchange (см. рис. 2), обеспечивающие корректный результат при выполнении оригинальных алгоритмов исполнителя запросов.

Обработка запросов на изменение данных (INSERT и UPDATE) обеспечивается посредством модификации плана запроса и оператора обмена. В случае INSERT в корень плана запроса добавляется дополнительная операция выборки, которая отсекает все кортежи, предназначенные для других вычислительных узлов. В случае UPDATE модифицированный алгоритм exchange позволяет перемещать кортежи, которые в результате обновления стали «чужими» (если ip(t') ^ </?(£), то на Узле с номером <p(t) кортеж t удаляется, а на узле с номером (p(t') вставляется кортеж t').

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

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

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

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

Реализация оператора exchange предполагает внедрение в оригинальную СУБД PostgreSQL новых функций и типов данных. На рис. 4 представлен пакет par_ Exchange, содержащий новые классы, добавляемые в СУБД PostgreSQL.

Классы данного пакета Merge, Split, Scatter и Gather реализуют одноименные узлы оператора exchange. Класс Exchange_ Builder выполняет

Рис. 2.

j

Рис. 3.

Рис. 4.

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

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

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

В третьей главе, «Применение параллельной СУБД Pargre-

PargreSQL

PostgreSQL

Storage

Rewriter

«use» - <<use>>

Planner

lib pq_

libpq-be libpq-fe С

par_Storage

par_Exchange

par.Balancer

5 par_Parallelizer

parjlbpq parjibpq-fe

par.Compat

SQL для интеллектуального анализа графов», представлен новый подход к решению задачи разбиения сверхбольших графов, которые состоят из миллионов вершин и ребер, ориентированный на реляционные СУБД с фрагментным параллелизмом. Данная задача решается с целью проверки применимости СУБД PargreSQL к задачам аналитической обработки сверхбольших баз данных. Описаны алгоритмы, которые реализуют стадии разбиения графа в виде запросов SQL.

Задача разбиения графов определяется следующим образом. Пусть имеется граф G = (N, Е), где N — множество взвешенных вершин, Е — множество взвешенных ребер, и целое число р > 0. Требуется найти подмножества вершин Ni, N2, ..., Np из N такие, что

— Uf=1Ai,: = N и Ni П N} = 0 для i ф j\

— W(i) « W/p, г = 1,2,... ,р, где W(i) и W представляют собой суммы весов вершин N и N соответственно:

— величина разреза (cut size), т.е. сумма весов ребер, соединяющих вершины разных подмножеств, минимальна.

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

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

стадий (см. рис. 5): огрубление, начальное разбиение и уточнение. Стадия огрубления выполняется с помощью СУБД PargreSQL и обеспечивает редукцию исходного графа до размеров, позволяющих разместить граф и промежуточные данные в оперативной памяти. На стадии начального разбиения огрубленный граф экспортируется из базы данных и подается на вход сторонней свободной утилиты Chaco, которая может выполнить начальное разбиение огрубленного графа в оперативной памяти с помощью одного из известных алгоритмов. Результат начального разбиения импортируется в базу данных в виде реляционной таблицы. На стадии уточнения разбиения параллельная СУБД PargreSQL с помощью запросов к таблице, полученной на предыдущей стадии, формирует финальное разбиение графа в виде реляционной таблицы из двух столбцов: номер вершины графа и номер подграфа, которому принадлежит эта вершина.

В четвертой главе, «Вычислительные эксперименты», приводятся результаты вычислительных экспериментов, выполненных на суперкомпьютере «Торнадо ЮУрГУ» с использованием разработанной параллельной СУБД PargreSQL. В рамках экспериментов исследованы ускорение и расширяемость СУБД PargreSQL, ее производительность на стандартных тестах консорциума ТРС (Transaction Processing Council), а также эффективность и качество разбиения реальных сверхбольших графов.

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

В экспериментах на исследование ускорения соединяемые отношения имели размеры 300 млн. и 7.5 млн. кортежей соответственно, распределяемые по узлам кластера. Эксперименты показали (см. рис. 6а), что СУБД PargreSQL демонстрирует ускорение, близкое к линейному.

1 S 16 32 64 128

Количество вычислительных узлов

(а) Ускорение СУБД PargreSQL

—О— реальная — линейная

1 8 16 32 64 128

Количество вычислительных узлов

(Ь) Расширяемость СУБД PargreSQL

Рис. 6.

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

емых отношений увеличивались пропорционально увеличению количества используемых узлов кластера с множителем 12 млн. и 0.3 млн. кортежей соответственно. В ходе экспериментов установлено (см. рис. 6Ь), что СУБД PargreSQL имеет расширяемость, близкую к линейной.

Вторая серия экспериментов была направлена на исследование эффективности СУБД PargreSQL на стандартных тестах производительности ТРС-С. Тест ТРС-С измеряет производительность СУБД на последовательности OLTP-запросов, моделирующих складской учет. В тесте использовалось от 1 до 30 параллельно работающих клиентов, выполняющих запросы к СУБД PargreSQL, запущенной на 12 узлах. Размер базы данных составлял 12 «складов».

Табл. 1.

К-во клиентов tpm-C 4- К-во клиентов tpm-C 4- К-во клиентов tpm-C 1 К-во клиентов tpm-C X

29 2202531 24 2165413 16 1882353 8 1156626

26 2197183 23 2156250 15 1747572 7 1150684

30 2195122 22 2146341 14 1647058 5 857142

32 2194285 20 2068965 13 1529411 6 847058

27 2189189 19 2054054 12 1358490 4 657534

31 2188235 18 2037735 11 1346938 3 444444

28 2181818 21 2016000 10 1290322 2 328767

25 2173913 17 1961538 9 1270588 1 150000

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

В третьей серии эксперильентов изучались ускорение и качество разбиения реальных сверхбольших графов, выполненного с помощью СУБД PargreSQL. В данных экспериментах выполнялось разбиение двух графов, представляющих собой карты дорог Люксембурга и Бельгии и содержащих 10° и 106 вершин соответственно. Эксперименты показали (см. рис. 7), что разбиение выполняется с ускорением, существенно превышающим линейное. Это является ожидаемым результатом, поскольку предложенное решение задачи относится к классу embarrassingly parallel («ошеломляюще параллельных»). При этом, однако, имеет место приемлемое качество разбиения исследуемых графов (см. рис. 8): не более 1.5% и не более 15% от общего количества вершин графа соответственно были причислены к неверным подграфам.

Качество разбиения графов оценивалось с помощью метрики Керни-гана—Лина

> и/а Кластер СУБД K-bo узлов K-bo клиентов tpm-C

1 SPARC SuperCluster with ТЗ-4 Servers Oracle Database llg R.2 Enterprise Edition w/RAC w/Partitioning 108 81 30 249 688

2 IBM Power 780 Server Model 9179-MHB IBM DB2 9.7 24 96 10 366 254

3 Sun SPARC Enterprise T5440 Server Cluster Oracle Database llg Enterprise Edition w/RAC w/Partitioning 48 24 7 646 486

Торнадо ЮУрГУ PargreSQL 12 29 2 202 531

4 HP Integrity rx5670 Cluster Itanium2/1.5 GHz-64p Oracle Database lOg Enterprise Edition 64 80 1 184 893

Люксембург Бельгия

4 8 16 32 64 128 Количество вычислительных узлов

(Ь) Качество разбиения графа Бельгии

I- Ю2 ю1

(а) Время разбиения графов

2000

Рис. 7.

128

Количество вычислительных узлов (Ь) Ускорение разбиения графов

(а) Качество разбиения графа Люксембурга

Количество вычислительных узлов

32 64

Количество вычислительных узлов

Рис. 8.

gain(г>) = ^ У/{и, у) - ^ Ш(и, у),

которая вычисляет для вершины у потенциальную выгоду от перемещения ее в другой подграф.

Таким образом, эксперименты показывают хорошую масштабируемость параллельной СУБД Ра^геЗС^Ь и производительность на уровне

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

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

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

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

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

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

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

3. Разработан новый алгоритм разбиения сверхбольших графов, состоящих из миллионов вершин и ребер, ориентированный на реляционные СУБД с фрагментным параллелизмом.

4. Проведены вычислительные эксперименты с СУБД PargreSQL, которые показали успешное применение данной СУБД для решения задач классов OLAP и OLTP, связанных с обработкой сверхбольших баз данных.

Публикации по теме диссертации

Публикации в журналах из списка ВАК

1. Пан К. С. Разработка параллельной СУБД на основе PostgreSQL // Труды Института системного программирования РАН. 2011. Т. 21. С. 357-370.

2. Пан К.С., Цьшблер M.JI. Разработка параллельной СУБД на основе последовательной СУБД PostgreSQL с открытым исходным кодом // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». 2012. № 18(277). Вып. 12. С. 112-120.

3. Pan С., Zymbler M. Taming Elephants, or How to Embed Parallelism into PostgreSQL // Database and Expert Systems Applications - 24th International Conference, DEXA 2013, Prague, Czech Republic, August 26-29, 2013. Proceedings, Part I. Springer, 2013. Lecture Notes in Computer Science. Vol. 8055. P. 153-164.

4. Pan C., Zymbler M. Very Large Graph Partitioning by Means of Parallel DBMS // Proceedings of the 17th East-European Conference on Advances in Databases and Information Systems, ADBIS'2013, September 1-4, 2013, Genoa, Italy. Lecture Notes in Computer Science. Springer, 2013. Vol. 8133. P. 388-399.

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

5. Pan С. Development of a Parallel DBMS on the Basis of PostgreSQL // Proceedings of the Seventh Spring Researchers' Colloquium on Databases and Information Systems (SYRCoDIS'2011). Moscow: Moscow State University, 2011. P. 57-61.

6. Пан К. С. Подход к разбиению сверхбольших графов с помощью параллельных СУБД // Вестник ЮУрГУ. Серия «Вычислительная математика и информатика,». 2012. № 47(306). Вып. 2. С. 127-132.

7. Пан К. С. Разработка параллельной СУБД на основе свободной СУБД PostgreSQL // Научный сервис в сети Интернет: экзафлопс-ное будущее: Труды Международной суперкомпыотерной конференции (Новороссийск, 19-24 сентября 2011 г.). М.: Изд-во МГУ, 2011. С. 566-571.

8. Пан К.С., Цымблер M.J1. Архитектура и принципы реализации параллельной СУБД PargreSQL // Параллельные вычислительные технологии (ПаВТ'2011): труды международной научной конференции (Москва, 28 марта- 1 апреля 2011 г.). Челябинск: Издательский центр ЮУрГУ, 2011. С. 577-584.

9. Пан К. С., Цымблер M.JI. Исследование эффективности параллельной СУБД PargreSQL // Научный сервис в сети Интернет: все грани параллелизма: Труды Международной суперкомпыотерной конференции (Новороссийск, 23-28 сентября 2013 г.). М.: Изд-во МГУ, 2013. С. 148-149.

10. Пан К.С., Цымблер M.JI. Проект PargreSQL: разработка параллельной СУБД на основе свободной СУБД PostgreSQL // Научный сервис в сети Интернет: суперкомпыотерные центры и задачи: Труды Международной суперкомпыотерной конференции (Новороссийск, 20-25 сентября 2010 г.). М.: Изд-во МГУ, 2010. С. 308-313.

11. Пап К. С., Цымблер М.Л. Использование параллельной СУБД Ра^ге-ЭРЬ для интеллектуального анализа сверхбольших графов // Суперкомпьютерные технологии в науке, образовании и промышленности. 2012. № 1. С. 125-134.

12. Соколинский Л.Б., Цымблер М.Л., Пап К.С., Медведев А.А. Свидетельство Роспатента о государственной регистрации программы для ЭВМ «Параллельная СУБД Ра^геБдЬ» № 2012614599 от 23.05.2012.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 12-07-31217 мол_а, 12-07-00443, 09-07-00241) и Президента Российской Федерации (стипендия СП-5427.2013.5).

Свидетельство о регистрации программы

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

0420И5519'

>Ъ

ПАН Константин Сергеевич

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

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: ЦЫМБЛЕР Михаил Леонидович, кандидат физ.-мат. наук, доцент

Челябинск — 2013

Оглавление

Введение 4

1. Фрагментный параллелизм и СУБД с открытым кодом 15

1.1. Фрагментный параллелизм......................................15

1.2. Обзор последовательных свободных СУБД с открытым исходным кодом..................................................18

1.3. Архитектура СУБД PostgreSQL.................................23

1.3.1. Взаимодействие процессов СУБД.........................23

1.3.2. Этапы обработки запроса.................................24

1.3.3. Модульная структура.....................................25

1.3.4. Размещение компонентов.................................26

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

2. Внедрение параллелизма в последовательную СУБД 29

2.1. Методы внедрения фрагментного параллелизма................29

2.1.1. Тиражирование запросов.................................30

2.1.2. Организация обменов.....................................30

2.1.3. Построение параллельного плана запроса................32

2.1.4. Обработка запросов на изменение данных................33

2.1.5. Хранение метаданных о фрагментации...................35

2.1.6. Портирование приложений................................35

2.1.7. Модификация исходных текстов..........................35

2.2. Архитектурные подходы и алгоритмы...........................36

2.2.1. Подсистема тиражирования...............................37

2.2.2. Подсистема портирования................................38

2.2.3. Оператор обмена (exchange)..............................39

2.2.4. Параллелизатор плана запроса...........................45

2.2.5. Запросы на изменение данных............................48

2.2.6. Запросы на определение данных..........................49

2.3. Архитектура параллельной СУБД Ра^геБС^Ь...................50

2.3.1. Взаимодействие процессов СУБД.........................51

2.3.2. Этапы обработки запроса.................................52

2.3.3. Модульная структура.....................................53

2.3.4. Размещение компонентов.................................54

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

3. Применение параллельной СУБД Ра^ге8(ЗЬ для интеллектуального анализа графов 57

3.1. Определение задачи разбиения графа...........................57

3.2. Обзор существующих решений задачи разбиения графа........58

3.3. Разбиение графа с помощью СУБД Ра^геБС^Ь..................61

3.3.1. Реляционная схема данных...............................62

3.3.2. Огрубление графа.........................................64

3.3.3. Уточнение разбиения графа..............................66

3.4. Выводы но главе 3...............................................69

4. Вычислительные эксперименты 71

4.1. План и аппаратная платформа экспериментов..................71

4.2. Ускорение и расширяемость.....................................72

4.3. Производительность на тестах ТРС.............................75

4.4. Исследование разбиения сверхбольших графов..................76

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

Заключение 81

Литература 89

Приложение. Статистические данные о популярности

современных свободных СУБД 100

Введение

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

В настоящее время одним из феноменов, оказывающих существенное влияние на область технологий обработки данных, являются сверхбольшие данные. В условиях современного информационного общества имеется широкий спектр приложений (социальные сети [24, 64], электронные библиотеки [1, 90], геоинформационные системы [59, 78] и др.), в каждом из которых производятся неструктурированные данные, имеющие сверхбольшие объемы и высокую скорость прироста (от 1 Терабайта в день). Исследования экспертов корпорации ЕМС показывают, что к 2020 г. мировой объем данных достигнет 40 Зеттабайт1.

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

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

В настоящее время параллельные системы баз данных [32], которые обеспечивают обработку запросов на многопроцессорных и многоядерных вычислительных системах, признаются научным сообществом как единственное эффективное средство для организации хранения и обработки сверхбольших баз данных. Базисной концепцией параллельных систем баз данных является фрагментный параллелизм, предполагающий разбиение

'Press Release ЕМС2. URL: http://www.emc.com/about/news/press/2012/20121211-01.htm (дата обращения: 10.03.2013).

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

Однако существующие сегодня коммерческие СУБД, использующие фрагментами параллелизм (Teradata [69], Greenplum [88], IBM DB2 Parallel Edition [22] и др.), имеют высокую стоимость и, во многих случаях, ориентированы на специфические аппаратно-программные платформы. Например, аппаратно-программные решения корпорации Teradata предлагаются по ценам от $16 500 за 1 терабайт обслуживаемой базы данных2; СУБД Greenplum продается по бессрочной лицензии, которая стоит $16 ООО за используемое вычислительной системой процессорное ядро или $70 ООО за 1 терабайт обслуживаемой базы данных, а годовая поддержка продукта стоит 22% от суммы покупки3. СУБД Oracle Real Application Cluster предлагается по цепе $10 ООО за процессор при бессрочной лицензии4.

Идеологически близкими к параллельным СУБД, основанным на концепции фрагментного параллелизма, являются кластерные СУБД с ПО промежуточного уровня [19]. В зависимости от функций, которые выполняет промежуточное ПО, можно различать кластерные СУБД, ориентированные на приложения класса OLTP, и кластерные СУБД, ориентированные на приложения класса OLAP.

В случае сценария OLTP (Online Transaction Processing, оперативная обработка транзакций) СУБД обрабатывает большое количество коротких транзакций и промежуточное ПО обеспечивает межтранзакционный параллелизм. Подключающиеся к системе клиенты распределяются для обработки нескольким экземплярам СУБД, что позволяет повысить доступность системы при большом количестве клиентов.

Сценарий OLAP (Online Analytical Proicessing, оперативная аналитическая обработка) подразумевает, что СУБД выполняет сложные запро-

2Teradata Workload-Specific Platform Pricing. URL: http://www.teradata.eom/t/WorkArea/ DownloadAsset.aspx?id=4682 (дата обращения: 01.10.2013).

3Greenplum update - Release 3.3. URL: http://www.dbms2.com/2009/06/05/ greenplum-update-release-З-З/ (дата обращения: 01.10.2013).

4Oracle Online Store. URL: http://shop.oracle.com (дата обращения: 01.10.2013)

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

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

Рис. 1. Кластер баз данных для OLTP

Одним из представителей такого подхода к созданию кластерных СУБД является система MySQL Cluster [79]. Данная СУБД представляет собой модифицированную версию MySQL. СУБД MySQL использует слой абстракции для обеспечения низкоуровневого хранилища данных и таким образом поддерживает множество различных движков хранилищ, реализованных в виде подключаемых модулей. MySQL Cluster — это версия MySQL, которая использует в качестве хранилища систему NDB. NDB позволяет хранить данные в памяти множества узлов с учетом фрагментации и репликации. Архитектура системы MySQL Cluster показана на рис. 2.

Следует отметить, что MySQL Cluster ориентирована на параллельную

Custom " Clients (NDB API)

:onnector/NET

Clients / APIs

mysql || MySOL cfient г ДР1

MySQL php I Connect or/J capi l|_ 4}_

4X1/1/

SQL Nodes Щ Щг

mysqld Eh1.. mysqld|j|L,_

Data Nodes

i i,

ч. 'ч г ф

NDB

Management

Server ndbjiigmd

Рис. 2. Архитектура СУБД MySQL Cluster

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

Решение Oracle Real Application Clusters (Oracle RAC) [77] также представляет собой пример кластерной СУБД. В качестве промежуточного программного обеспечения в данном продукте используется система Oracle Clusterware, предоставляющая следующие основные функции: управление членством узлов в кластере, мониторинг состояния служб кластера, восстановление после сбоя одного или нескольких узлов и др. СУБД Oracle RAC построена на основе архитектуры с разделяемыми дисками. В СУБД Oracle RAC поддерживается хранение до трех реплик базы данных, вследствие чего обеспечивается высокая готовность данных и балансировка нагрузки между узлами кластера. Однако Oracle Clusterware не обеспечивает внутризапросный параллелизм, в силу чего основным назначением Oracle RAC являются приложения класса OLTP. Кроме того, Oracle RAC может

включать в себя не более 100 узлов.

Системы MySQL Cluster и Oracle RAC основаны на использовании общего хранилища. Хранилище может быть реализовано в виде множества вычислительных узлов, обеспечивающих распределенное хранение данных в оперативной памяти (как в MySQL Cluster, см. рис. За), или как некоторый общий диск (как в Oracle RAC, см. рис. ЗЬ).

Рис. 3. Кластер баз данных общим хранилищем

Если кластерная СУБД ориентирована на OLAP, то есть на обработку сложных аналитических запросов к данным большого объема, то промежуточный слой ПО должен обеспечивать внутризапросный параллелизм, осуществляя прием запросов пользователя, их преобразование и распределение на узлы кластера, слияние частичных результатов и передачу их пользователю. Архитектура взаимодействия клиента и сервера в таких СУБД представлена на рис. 4.

Концепция кластерной СУБД на основе ПО промежуточного слоя реализована в исследовательских проектах PowerDB-IR [39], C-JDBC [28] и ParGRES [68]. Продолжением проекта ParGRES является разработка GParGRES [53], которая представляет собой программное обеспечение промежуточного слоя для объединения ParGRES-кластеров в грид. Результаты вычислительных экспериментов показывают, как правило, хорошую

Рис. 4. Кластер баз данных с ПО промежуточного слоя

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

По-видимому, единственной существующей в настоящее время системой с открытым исходным кодом для параллельной обработки сложных запросов к реляционным данным является СУБД HadoopDB [17], которая представляет собой архитектурный гибрид вычислительной парадигмы MapReduce и технологий реляционных СУБД.

Парадигма распределенных вычислений MapReduce [33] для кластерных систем, разработанная корпорацией Google, может быть описана кратко следующим образом. Один из узлов кластерной системы трактуется как мастер, остальные — рабочие. Обработка данных выполняется в виде последовательности из двух шагов: Map и Reduce. На шаге Map узел-мастер получает входные данные и распределяет их по узлам-рабочим. Pia шаге Reduce узел-мастер выполняет свертку данных, предварительно обработанных рабочими, и отправку конечного результата пользователю. В качестве подсистемы, реализующей MapReduce-вычислвния, в СУБД HadoopDB в используется система Hadoop [89]. Hadoop обеспечивает коммуникационную инфраструктуру, объединяющую узлы кластера, па которых выполняются экземпляры СУБД PostgreSQL. Запросы пользователя на языке SQL транслируются в задания для среды MapReduce, которые далее передаются в экземпляры СУБД.

Эксперименты показывают [17, 74], что, хотя система HadoopDB способ-

на демонстрировать устойчивость к отказам и падению производительности узлов, свойственную системам MapReduce, в большинстве случаев параллельные СУБД существенно превосходят ее в производительности. Одной из причин отставания производительности HadoopDB от параллельных СУБД являются предусмотренные архитектурой этой системы накладные расходы на взаимодействие между средой MapReduce и PostgreSQL [3].

Еще одной системой баз данных, которую можно отнести к данному классу, является vParNDB [63]. Она представляет собой ПО промежуточного слоя, которое переписывает запросы таким образом, чтобы они выполнялись параллельно с использованием нескольких узлов MySQL Cluster, подключенных к общему хранилищу NDB. Хотя эксперименты на тестах TPC-II показывают хорошее ускорение с использованием такого подхода, любые решения на основе MySQL Cluster наследуют все ограничения данной СУБД.

В настоящее время надежной альтернативой коммерческим СУБД являются свободные СУБД с открытым кодом [35, 73], однако проведенный обзор дает основания полагать, что на сегодя отсутствуют свободные СУБД, реализующие фрагментный параллелизм. Данный факт объясняется тем, что параллельная СУБД относится к классу сложного системного программного обеспечения, разработка которого требует существенных финансовых и временных затрат

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

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

поденных компьютеров, используемый в качестве единого вычислительного ресурса. Кластеры сочетают в себе экономичность и высокую вычислительную мощность и в настоящее время претендуют на доминирующее положение в области высокопроизводительных вычислений5'6.

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

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

Цель и задачи исследования

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

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

5ТОР500 supercomputer sites. URL: http://www.top500.org (дата обращения: 01.10.2013)

GTOP50 суперкомпьютеров России. URL: http://www.supercomputers.ru (дата обращения: 01.10.2013)

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

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

3. Исследовать эффективность предложенных подходов применительно к решению задач классов OLAP и OLTP, связанных с обработкой сверхбольших баз данных.

Методы исследования

Проведенные в работе исследования базируются на реляционной модели данных. При разработке программной системы применялись методы объектно-ориентированного проектирования и язык UML. В разработке алгоритмов использован аппарат теории графов.

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

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

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

2. Впервые выполнено внедрение фрагментного параллелизма в последовательную СУБД PostgreSQL.

3. Разработан новый алгоритм разбиения сверхбо