В работе описывается сопроцессор баз данных для высокопроизводительных кластерных вычислительных систем с многоядерными ускорителями, использующий распределенные колоночные индексы с интервальной фрагментацией. Работа сопроцессора рассматривается на примере выполнения операции естественного соединения. Параллельная декомпозиция естественного соединения выполняется на основе использования распределенных колоночных индексов. Предложенный подход позволяет выполнять реляционные операции на кластерных вычислительных системах без массовых обменов данными. Приводятся результаты вычислительных экспериментов с использованием сопроцессоров Intel Xeon Phi, подтверждающие эффективность разработанных методов и алгоритмов.
2. Общая архитектура системы
Система баз данных, использующая колоночные индексы и интервальную фрагментацию, включает в себя сервер баз данных и сопроцессор баз данных (рис. 1). Сервер баз данных реализуется в виде СУБД, в которой введен дополнительный уровень абстракции при выполнении реляционной операции: на первой фазе вычисляются адреса кортежей, из которых строится результат (таблица предвычислений, ТПВ); на второй фазе конструируется результирующее отношение путем считывания кортежей по адресам из ТПВ. Для часто повторяющихся ресурсоемких операций администратор создает необходимые колоночные индексы, которые фрагментируются, а затем хранятся и обрабатываются сопроцессором баз данных в оперативной памяти узлов кластерной вычислительная системы с многоядерными ускорителями. Каждый фрагмент колоночного индекса хранится в сжатом виде. На одном вычислительном узле может храниться несколько фрагментов. При необходимости выполнить соответствующую ресурсоемкую операцию в ходе выполнения запроса, вычисление ТПВ выполняется сопроцессором баз данных. Каждый фрагмент колоночного индекса разжимается, обрабатывается и сжимается отдельным ядром многоядерного ускорителя. Балансировка загрузки между ядрами многоядерного ускорителя производится автоматически.
Сопроцессор баз данных включает в себя подсистему «Исполнитель», реализующую выполнение ресурсоемкой части реляционной операции над фрагментами, и подсистему «Координатор», реализующую рассылку запроса от СУБД между подсистемами «Исполнитель», получение от подсистем «Исполнитель» частичных результатов, сбор ТПВ и отправку ТПВ на сервер.
Сопроцессор баз данных Исполнитель 3. Колоночный индекс и интервальная фрагментация
Колоночный индекс IR.B для атрибута B таблицы R представляет собой таблицу из двух колонок с именами A и B (см. рис. 2). Количество строк в колоночном индексе совпадает с количеством строк в индексируемой таблице. Колонка B индекса IR.B включает в себя все значения колонки B таблицы R (с учетом повторяющихся значений), отсортированных в порядке возрастания. Каждая строка x индекса IR.B содержит в колонке A суррогатный ключ (адрес кортежа, представляющий собой идентификатор целочисленного типа, однозначно определяющий кортеж) строки r в таблице R, имеющей такое же значение в колонке B, что и строка x.
Пусть на домене атрибута B задано отношение линейного порядка. Пусть также задано разбиение множества на непересекающихся интервалов, которые называются доменными интервалами и вместе составляют все множество . Колоночный индекс распределяется по узлам вычислительной системы в соответствие с функцией фрагментации , которая ставит в соответствие каждому кортежу индекса некоторый узел вычислительной системы. В i-тый фрагмент попадают кортежи, у которых значение атрибута B принадлежит i-тому доменному интервалу. Будем называть фрагментацию, построенную таким образом, интервальной. Количество фрагментов будем называть степенью фрагментации. Если атрибуты различных колоночных индексов имеют один и тот же домен, то их
. 4. Декомпозиция операции естественного соединения
Пусть заданы два отношения и . Пусть имеется два набора колоночных индексов по атрибутам : ; .
Пусть для всех этих индексов задана интервальная фрагментация степени k, распределяющая индексы по k-узлам вычислительной системы. На каждом i-ом узле ( ) выполняется попарное соединение фрагментов и по для всех , в результат выносятся только суррогатные ключи фрагментов. Результатом операции является таблица из двух колонок (суррогатные ключи фрагмента ) и (суррогатные ключи фрагмента ). Данные вычисления могут выполняться независимо на k различных узлах без обменов данными. Затем каждый из k узлов пересылает полученные таблицы на узел-координатор, где таблицы для одного и того же атрибута объединяются в одну. Таким образом, получаем u таблиц . Следующим шагом в таблицах необходимо найти те кортежи, которые присутствуют во всех таблицах одновременно. Полученное множество является ТПВ. -еерП саклы , 3 0 4 5 двух отношений R и S по двум атрибутам B и C изображен на рис. 4. Используется интервальная фрагментация степени 2. Для колоночных индексов и , и используются следующие функции фрагментации: 0, при x.B 30 IB x IR.B x IS.B x 1, при x.B 30
, 0, при x.C [a..m) IC x IR.C x IS.C x 1, при x.C [m..z] .
На рис. 5 представлено конструирование кортежей результата с использованием полученной ТПВ. 5. Вычислительные эксперименты
Для подтверждения эффективности выполнения реляционных операции с использованием
распределенных колоночных индексов создан прототип колоночного сопроцессора баз данных,
с помощью которого были проведены вычислительные эксперименты. Исходный код
прототипа доступен в репозитории GitHub [
В ходе экспериментов генерировалась тестовая база данных, состоящая из двух отношений
R и S с общим целочисленным атрибутом B. Атрибут B отношения R является первичным
ключом, атрибут B отношения S – внешним ключом. Размеры отношений были следующие: 600 000
кортежей в и 60 000 000 кортежей в . Генерация атрибута B в отношении S производилась
двумя способами. Первый способ предполагал использование равномерного (uniform)
распределения значений в столбце S.B, что означает одинаковое количество кортежей в каждом
фрагменте. При втором способе столбец S.B генерировался с использованием неравномерного
распределения (правила «80-20», «65-20», «45-20») [
Для генерации неравномерного распределения была использована вероятностная модель. В соответствии с этой моделью коэффициент перекоса , ( ) задает распределение, при котором каждому различному значению в S.B назначается некоторый весовой коэффициент , определяемый формулой где N – количество различных значений атрибута S.B и N-е гармоническое число порядка s. В случае распределение весовых коэффициентов соответствует равномерному распределению. При распределение соответствует правилу «80-20», в соответствии с которым, 80% кортежей отношения будет храниться в 20% фрагментов. При распределение соответствует правилу «65-20». При распределение соответствует правилу «45-20».
Для столбцов R.B и S.B были созданы колоночные индексы и соответственно.
Индексы и фрагментировались на основе интервального принципа. Количество
фрагментных интервалов было кратно 600 000 и являлось параметром экспериментов. Каждый фрагмент
колоночных индексов сжимался с помощью библиотеки Zlib [
В ходе экспериментов выполнялось соединение колоночных индексов и по атрибуту B с созданием ТПВ. Операция соединения производилась с использованием алгоритма соединения слиянием (Merge Join, MJ). Особенностью алгоритма MJ является то, что соединение осуществляется за одно сканирование каждой из входных таблиц, что существенно уменьшает количество операций по сравнению с алгоритмом вложенных циклов.
Эксперименты были проведены на узле с многоядерным ускорителем Intel Xeon Phi SE10X кластерной вычислительной системы «Торнадо ЮУрГУ», установленной в Южно-Уральском государственном университете. Многоядерный ускоритель Intel Xeon Phi имеет 61 вычислительное ядро и 8 Гб оперативной памяти.
Операция соединения выполнялась на 1, 2 и 4 нитях, запущенных на одном ядре Intel Xeon Phi (рис. 6). Результаты этого эксперимента показывают, что наибольшее ускорение достигается при запуске на каждом ядре только одной нити.
500 600 750 1 000 1 500 Количество фрагментов
Также нами были исследованы ускорение и расширяемость при выполнении соединения колоночных индексов на 15, 30, 45 и 60 ядрах Intel Xeon Phi. Результаты представлены на рис. 7. Ускорение считалось как отношение времени выполнения соединения на заданном количестве ядер к времени выполнения этого же соединения на 15 ядрах (база данных не менялась). При исследовании расширяемости вычислялись те же отношения времен, но при этом размер базы данных увеличивался пропорционально увеличению количества ядер. Эксперименты показали, что многоядерный ускоритель Intel Xeon Phi демонстрирует линейные ускорение и масштабируемость. Это означает, что при выполнении описанной операции соединения с использованием колоночных индексов в структуре Intel Xeon Phi не возникает узких мест. Это согласуется с высоким процентом утилизации процессорных ядер Intel Xeon Phi при выполнении соединения 2,8 ) . к е с ( ям 2,3 е р В 1,8 1,3 1 нить 2 нити 4 нити сжатых фрагментированных колоночных индексов (измерения с помощью команды Linux TOP показали утилизацию 98%).
Ускорение Расширяемость 4,5 4,0 3,5 ) 3,0 . сек 2,5 ( ям 2,0 е р В 1,5 1,0 0,5 0,0 4,0 3,5 3,0 .) 2,5 к е (ся 2,0 м ер1,5 В 1,0 0,5 0,0 Uniform 80-20 65-20 45-20 15 30 45 Количество фрагментов 60 Рис. 7. Ускорение и расширяемость при увеличении количества используемых ядер Xeon Phi. В следующем эксперименте исследовалась проблема дисбаланса загрузки ядер Intel Xeon Phi при наличии перекосов в распределении значений по фрагментам. Результаты представлены на рис. 8. Эксперимент показал, что деление колоночных индексов на достаточно большое количество фрагментов позволяет эффективно сбалансировать загрузку процессорных ядер даже при наличии большого перекоса в распределении значений в колоночных индексах. 60 200 600
2 000 6 000 20 000 Количество фрагментов 6. Заключение
В статье было представлено описание колоночного сопроцессора баз данных для высокопроизводительных кластерных вычислительных систем с многоядерными ускорителями. Колоночный сопроцессор использует распределенные колоночные индексы с интервальной фрагментацией. Рассмотрена работа колоночного сопроцессора на примере параллельной декомпозиции операции естественного соединения. В рамках проведенных экспериментов было исследовано время выполнения операции естественного соединения двух отношений R и S с использованием колоночного сопроцессора. Исследовались зависимость времени выполнения естественного соединения от количества фрагментов при запуске 1, 2 и 4 нитей на каждом ядре Intel Xeon Phi и влияние количества фрагментов на баланс загрузки процессорных ядер Xeon Phi при равномерном и неравномерном распределении значений атрибута S.B. Проведенные исследования показывают, что предложенный подход на основе использования колоночного сопроцессора баз данных позволяет эффективно выполнять ресурсоемкую операцию естественного соединения двух таблиц на вычислительных кластерах с многоядерными ускорителями. Литература 1. Соколинский Л.Б. Параллельные системы баз данных. М.: Издательство Московского университета, 2013. 184 c. 12. Иванова Е.В., Соколинский Л.Б. Использование распределенных колоночных индексов для выполнения запросов к сверхбольшим базам данных // Параллельные вычислительные технологии (ПАВТ'2014). Труды международной научной конференции. Челябинск: Издательский центр ЮУрГУ, 2014. С. 270–275. Using Intel Xeon Phi coprocessor for execution of natural join on compressed data Leonid Sokolinsky and Elena Ivanova Keywords: columnar data representation, columnar indexes, database coprocessor, interval fragmentation, parallel database systems, cluster computing system with many-core accelerators, Intel Xeon Phi coprocessor In the report describes a database coprocessor for high-performance cluster computing systems with many-core accelerators, which uses distributed columnar indexes with interval fragmentation. An activity of the coprocessor is considered by an example of natural join operation. The parallel decomposition of natural join operation is performed using distributed columnar indexes. The proposed approach allow to perform relational operators on cluster computing systems without massive data exchange. The results of computational experiments with using Intel Xeon Phi coprocessor confirm the effectiveness of the developed methods and algorithms.