Software & Systems

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

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

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

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

Фрагментация описывает разбиение отношений в БД. Разбиение отношений на минимальные, не делимые далее фрагменты позволит разместить их с максимально возможной гибкостью. Для получения такого набора фрагментов для каждого отношения R на основании транзакций определяется набор минтерм предикатов и группы атрибутов. Причем предикаты описывают применение ГФ, а группы атрибутов – ВФ. Группы атрибутов получаются разбиением множества атрибутов, используемых в транзакциях.

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

Схема размещения указывает местоположение фрагментов. Она описывается матрицей D, строками которой являются узлы ВС, а столбцами – сформированный набор фрагментов. Единица в ячейке матрицы Di,j означает наличие фрагмента i в узле j. Для удовлетворения свойства полноты схемы размещения каждый фрагмент должен находиться хотя бы в одном узле (в каждой колонке должна быть хотя бы одна единица).

При исполнении реляционного запроса необходимо принять следующие решения.

1.   В какой последовательности производить операции соединения.

2.   В каком узле производить операцию соединения.

3.   Применять ли технику semi-join при соединении. Идея semi-join состоит в отправке на узел 2 колонок отношения A, по которым осуществляются соединение, нахождение и отправка на узел 1 только тех записей из B, которые удовлетворяют условию соединения. Как правило, техника semi-join позволяет получить выигрыш в случае, когда отношение B содержит «тяжелые» колонки, например, мультимедийную информацию.

4.   Применять ли технику double-pipelined hash join. Идея double-pipelined hash-join состоит в формировании двух хэш-таблиц Ha и Hb, после чего записи из A и B обрабатываются по одной в каждый момент. Для записи из A в Hb ищутся соответствующие записи, после чего запись из A и найденные записи из B возвращаются как результаты соединения и запись из A помещается в хэш-таблицу Ha. Далее берется запись из B и обрабатывается аналогичным образом.

5.   Какие узлы, имеющие необходимые фрагменты, использовать при внутриоператорном параллелизме.

Все задачи, входящие в процесс проектирования РаБД, NP-полные. Во многих работах отмечается, что для решения задач кластеризации и компоновки наиболее успешно применяются генетические алгоритмы (ГА), в основу которых положены идеи естественного отбора в биологических популяциях. В ГА любое решение задачи синтеза представляется хромосомой, состоящей из генов. Значениями генов являются значения проектных параметров. Направленный перебор решений осуществляется с помощью генетических операторов выбора родителей, скрещивания, мутации, селекции, переупорядочения. Помимо NP-полноты, задачи проектирования РаБД обладают свойством взаимозависимости, то есть входными данными для следующей задачи является решение предыдущей. Таким образом, для получения проекта РаБД, близкого к оптимальному, целесообразно применять вложенные ГА.

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

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

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

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

где k – количество узлов ВС; n – количество запросов; fij – частота возникновения j-го запроса в i-м узле; Qij – временной коэффициент j-го запроса, порожденного в i-м узле; Wij – коэффициент использования ресурсов при обработке j-го запроса, порожденного в i-м узле; ct и ca – коэффициенты важности времени ответа и готовности транзакции, лежат в пределах от 0 до 1. Значения коэффициентов определяются проектировщиком на основании требований к РаБД.

Временной коэффициент j-го запроса определяется как Qij=Tijd/Tijl, то есть равен отношению времени ответа на запрос, исполненный в РаБД, к расчетному времени ответа на запрос, исполненный локально в узле i при условии наличия в нем всех необходимых фрагментов. Коэффициент использования ресурсов равен сумме коэффициентов использования ЦП и ВЗУ узлов, вовлеченных в операцию, и коэффициента использования СР.

Эксперимент проводился для следующей конфигурации: ВС состоит из 3 узлов, равноудаленных друг от друга; логическая схема БД имеет 2 отношения; производится 3 запроса на выборку и 2 запроса на обновление данных, которые формируют 4 группы атрибутов и 5 предикатов.

Измерения показали, что оптимальные зна- чения для параметров ГА лежат в пределах, приведенных в таблице 1. Запуск алгоритма с другими значениями параметров ухудшает качество результата или увеличивает время работы.

Таблица 1

Оптимальные параметры ГА

Схождение популяций, при котором 90 % лучших особей имеют расхождение в значении функции приспособленности не более 10 %, наблюдалось примерно после 500¸700 поколений внешнего ГА и 2500¸3000 поколений внутреннего ГА. Были промоделированы различные соотношения скорости передачи данных по сети (R) к скорости чтения данных в узле (S) и различные коэффициенты важности времени ответа и готовности транзакции в целевой функции. В таблице 2 приведены результаты моделирования.

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

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

Таблица 2

Зависимость эффективности проекта и степени репликации от физических характеристик ВС и коэффициентов целевой функции

Алгоритм был реализован на языке C#. Время работы алгоритма на компьютере Intel Pentium Core2 2Ггц приведено в таблице 3. Для 3 узлов и 9 фрагментов был произведен поиск оптимального решения методом полного перебора, для большего числа узлов и фрагментов время полного перебора значительно возрастает, поэтому оно было оценено аналитически.

Таблица 3

Время работы ГА и поиска полным перебором

Время поиска оптимального решения полным перебором с увеличением числа фрагментов растет экспоненциально, в то время как время работы ГА увеличивается квадратично.

Таким образом, предложенный ГА позволяет получить оптимальное или близкое к оптимальному решение задачи в рамках используемой модели, обеспечивая квадратичный рост времени работы с увеличением пространства возможных решений.

В дальнейшем возможно расширение модели РаБД за счет интеграции различных способов распространения обновлений [2], что позволит проектировщику приблизить модель к реальной вычислительной среде. Также необходимо дальнейшее исследование зависимости скорости схождения популяций от параметров ГА.

Список литературы

1.  Ceri S., Negri M., Pelagatti G. Horizontal data partitioning in database design. // ACM SIGMOD international conference on Management of data. Orlando, Florida. – 1982. – pp. 128–136.

2.  Стеен М., Тенебаум Э. Распределенные системы. Принципы и парадигмы. – СПб: Питер, 2003. – 880 с.