Размещено на http://www.allbest.ru/

4

Размещено на http://www.allbest.ru/

Параллельные базы данных

Введение

Становление систем управления базами данных (СУБД) совпало по времени со значительными успехами в развитии технологий распределенных вычислений и параллельной обработки. В результате возникли распределенные системы управления базами данных и параллельные системы управления базами данных. Именно эти системы становятся доминирующими инструментами для создания приложений интенсивной обработки данных.

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

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

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

1. Теоретическая часть

база данных управление система

1.1 Основные понятия

Распределенная база данных (DDB - distributed database) - это совокупность логически взаимосвязанных баз данных, распределенных в компьютерной сети. Распределенная система управления базой данных определяется как программная система, которая позволяет управлять распределенной базой данных таким образом, чтобы ее распределенность была прозрачна для пользователей. В этом определении следует уточнить две отличительных архитектурных особенности. Первая из них заключается в том, что система состоит из (возможно, пустого) множества узлов приема запросов (query site) и непустого множества узлов данных (data site). Узлы данных обладают средствами для хранения данных, а узлы приема запросов - нет. В узлах приема запросов лишь выполняются программы, реализующие пользовательский интерфейс для доступа к данным, хранящимся в узлах данных. Вторая особенность состоит в том, что узлы логически представляют собой независимые компьютеры. Следовательно, у такого узла имеется собственная основная и внешняя память, установлена собственная операционная система (может быть, одна и та же на всех узлах, а возможно, и нет) и имеется возможность выполнять приложения. Узлы связаны компьютерной сетью, а не входят в мультипроцессорную конфигурацию. Важно подчеркнуть слабую связанность процессоров, которые обладают собственными операционными системами и функционирует независимо.

База данных физически распределяется по узлам данных на основе фрагментации и репликации данных. При наличии схемы реляционной базы данных каждое отношение фрагментируется на горизонтальные или вертикальные разделы. Горизонтальная фрагментация реализуется при помощи операции селекции, которая направляет каждый кортеж отношения в один из разделов, руководствуясь предикатом фрагментации. Например, для отношения Employee возможна фрагментация в соответствии с местоположением рабочих мест служащих. При вертикальной фрагментации отношение делится на разделы при помощи операции проекции. Например, один раздел отношения Employee может содержать поля Emp_number, Emp_name и Address, а другой - поля Emp_number, Salary и Manager. За счет фрагментации данные приближаются к месту их наиболее интенсивного использования, что потенциально снижает затраты на пересылки; уменьшаются также размеры отношений, участвующих в пользовательских запросах.

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

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

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

Распределенная/параллельная база данных - это именно база данных, а не "коллекция" файлов, индивидуально хранимых на разных узлах сети. В этом заключается разница между DDB и распределенной файловой системой.

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

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

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

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

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

В идеале параллельная (и, в меньшей степени, распределенная) СУБД обладает свойством линейной масштабируемости (linear scaleup) и линейного ускорения (linear speedup). Под линейной масштабируемостью понимается сохранение того же уровня производительности при увеличении размера базы данных и одновременном пропорциональном увеличении процессорной мощности и объема памяти. Линейное ускорение означает, что с наращиванием процессорной мощности и объема памяти при сохранении прежнего размера базы данных пропорционально возрастает производительность.

1.2 Технологии распределенных и параллельных баз данных

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

Архитектуры параллельных систем варьируются между двумя крайними точками, называемыми архитектура без разделяемых ресурсов (shared-nothing) и архитектура с разделяемой памятью (shared-memory). Промежуточную позицию занимает архитектура с разделяемыми дисками (shared-disk).

Примерами систем параллельных баз данных являются продукты DBC (Teradata) и NonStop-SQL (Tandem), а также ряд прототипов, таких как BUBBA, EDS, GAMMA, GRACE, PRISMA и ARBRE.

К системам параллельных баз данных с разделяемой памятью относятся XPRS, DBS3 и Volcano, а также перенесенные на мультипроцессоры с разделяемой памятью наиболее известные промышленные СУБД. Первым примером такой системы была реализация СУБД DB2 на IBM3090 с шестью процессорами. Во всех известных на сегодня коммерческих продуктах (таких как Ingres и Oracle) используется только межзапросный (но не внутризапросный) параллелизм.

Примеры параллельных СУБД с разделяемыми дисками: продукт IMS/VS Data Sharing (IBM), а также продукты VAX DBMS и Rdb компании DEC. Реализация Oracle на компьютерах VAXcluster (DEC) и NCUBE также использует разделение дисков, поскольку этот подход требует минимальных расширений в ядре СУБД. Отметим, что во всех этих системах применяется только межзапросный параллелизм.

Обработка и оптимизация запросов

Обработка запроса (query processing) - это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня. Стандартным языком запросов, поддерживаемым современными СУБД, является SQL. Оптимизация запроса (query optimization) - это процедура выбора "наилучшей" стратегии выполнения запроса из множества альтернатив.

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

Для заданного SQL-запроса существует более чем одно алгебраическое представление, причем некоторые из них могут быть "лучше" других. "Качество" алгебраического выражения определяется исходя из объема затрат, необходимых для его вычисления. Традиционная процедура состоит в том, чтобы сначала оттранслировать SQL-запрос в какое-нибудь выражение, а затем, применяя правила эквивалентных алгебраических преобразований, получать из него другие алгебраические преобразования, пока не будет найдено "наилучшее". При поиске "наилучшего" выражения используется функция стоимости, в соответствии с которой вычисляется сумма затрат, необходимых для выполнения запроса. Этот процесс и называется оптимизацией запросов.

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

Внутриоперационный (intra-operation) параллелизм достигается за счет выполнения операции сразу на нескольких узлах многопроцессорной машины. Для этого необходимо предварительное разбиение операндов, т.е. их горизонтальная фрагментация по узлам. Способ разделения базового отношения относится к области физического проектирования базы данных. Обычно разделение производится путем применения некоторой хэш-функции к тому атрибуту отношения, который будет часто являться атрибутом соединения. Набор узлов, в которых хранится отношение, называется домашним набором (home). Домашним набором узлов операции (home of an operation) называется набор узлов, в которых она выполняется; оно должно совпадать с домашним набором узлов ее операндов, чтобы операция имела доступ к своим операндам. Это значит, что для бинарных операций, таких как соединения, может потребоваться переразделение (repartitioning) одного из операндов. В некоторых случаях оптимизатор, возможно, сочтет целесообразным провести переразделение обоих операндов. Для реализации внутриоперационного параллелизма в параллельных СУБД применимы некоторые методы, разработанные для распределенных баз данных.

Межоперационный (inter-operation) параллелизм имеет место, когда одновременно выполняются две или более операции, независимые или связанные общим потоком данных. Термином поток данных (dataflow) мы обозначаем форму параллелизма, реализуемую методами конвейерной обработки (pipelining). При независимом параллелизме операции выполняются одновременно или в произвольном порядке. Независимый параллелизм возможен, только если операции не содержат в качестве операндов общих данных.

1.3 Управление одновременным доступом

Если несколько пользователей одновременно (concurrently) осуществляет доступ (на чтение и запись) к совместно используемой базе данных, то для поддержки согласованного состояния данных требуется синхронизовать доступ. Синхронизация достигается путем применения алгоритмов управления одновременным доступом (concurrency control algorithm), гарантирующих следование критериям корректности, таким как сериализуемость. Доступ пользователей к данным инкапсулируются в рамках транзакций, которые на нижнем уровне выглядят как последовательности операций чтения и записи данных. Алгоритмы управления одновременным доступом обеспечивают соблюдение свойства изолированности выполнения транзакций, которое заключается в том, что воздействия одной транзакции на базу данных не будут зависеть (т.е. будут изолированы) от других транзакций, пока эта первая транзакция не завершит свое выполнение.

Наиболее популярные алгоритмы управления одновременным доступом основаны на механизме блокировок. В таких схемах всякий раз, когда транзакция пытается получить доступ к какой-либо единице памяти (как правило, странице), на эту единицу накладывается блокировка в одном из режимов - совместном (shared) или монопольном (exclusive). Блокировки накладываются в соответствии с правилами совместимости блокировок, исключающими конфликты чтение-запись, запись-чтение и запись-запись.

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

1.4 Размещение данных

В параллельной системе баз данных правильное размещение данных имеет решающее значение для обеспечения балансировки нагрузки. В идеале можно полностью избежать интерференции между одновременно выполняемыми параллельными операциями, если каждая из них будет работать с независимым набором данных. Независимые наборы данных получаются путем декластеризации (declustering) (горизонтального разделения) отношений на основе функции (хэш-функции или интервального индекса), применяемой к одному или более атрибутам, и размещения каждого раздела на отдельном диске. Как и в случае горизонтальной фрагментации в распределенных базах данных, декластеризация полезна для достижения межзапросного параллелизма, когда независимые запросы работают с разными фрагментами, а также внутризапросного параллелизма, когда операции, относящиеся к одному запросу, выполняются одновременно над различными фрагментами. Декластеризация может проводиться по одному или по нескольким атрибутам. В последнем случае запрос с условием сравнения по равенству для этих атрибутов может обрабатываться в одном узле без коммуникаций с другими узлами. Выбор между хэшированием и интервальной индексацией делается на этапе проектирования: хэширование требует меньше памяти, но поддерживает только запросы с условием сравнения по равенству, а интервальной индексация поддерживает также интервальные запросы. Декластеризация, которая вначале была предложена для систем без разделения ресурсов, оказалась полезной и для систем с разделяемой памятью, поскольку она способствует снижению конфликтности при доступе к памяти.

Полная декластеризация, когда каждое отношение разделяется по всем узлам системы, вызывает проблемы при работе с небольшими отношениями, а также в системах с очень большим числом узлов. Более удачен подход переменной декластеризации (variable declustering), при котором каждое отношение хранится в некотором числе узлов, которое является функцией от размера отношения и частоты доступа к нему.

Когда критерии, используемые для размещения данных, приводят к существенной деградации балансировки нагрузки, требуется произвести динамическую реорганизацию базы. Очень важно, чтобы реорганизацию можно было проводить в оперативном режиме (не прекращая текущей обработки транзакций), причем достаточно эффективно (применяя методы параллелизма). Существующие СУБД способны производить реорганизацию баз данных только статический. Статическая реорганизация проводится периодически и служит для изменения размещения данных либо в связи с увеличением размера базы данных, либо из-за изменения характера доступа к данным. В отличие от статической, динамическая реорганизация базы данных не требует остановки работы системы и обеспечивает плавный переход к новому размещению данных. Существенно, чтобы реорганизация была прозрачна для откомпилированных программ, работающих в параллельной системе. В частности, она не должна приводить к необходимости перекомпиляции программ. Это значит, что откомпилированные программы не должны зависеть от размещения данных. Отсюда следует, что оптимизатору не должно быть известно фактическое местоположение дисков, на которых хранится то или иное отношение, а также узел, где будет выполняться конкретная операция. Множество узлов, где хранится отношение в момент выполнения некоторой операции, называется домашним множеством отношения. Множество узлов, на которых выполняется операция, называется домашним множеством операции. Оптимизатор, тем не менее, должен обладать некоторым абстрактным знанием о структуре домашнего множества (например, "отношение R хэшировано на 20 узлах по атрибуту A"), а система поддержки времени выполнения производит ассоциирование между абстрактным домашним множеством и реальными узлами.

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

Еще один фактор, усложняющий задачу размещения данных, - это репликация данных для обеспечения высокого уровня доступности. Наивный подход здесь заключается в том, чтобы иметь две копии одних и тех же данных - первичную и резервную - на двух отдельных узлах. Но в случае отказа одного узла нагрузка на второй удвоится, что приведет к нарушению балансировки нагрузки. Для решения этой проблемы в последнее время было предложено несколько стратегий репликации для поддержки высокого уровня доступности. Интересный подход, который можно назвать расслоенной (interleaved) декластеризацией, применен в Teradata, где резервная копия декластеризуется между несколькими узлами. В случае отказа первичного узла его нагрузка распределяется между узлами, содержащими резервную копию. Однако реконструкция первичной копии из фрагментов ее резервной копии может оказаться дорогостоящей операцией. Существенны также затраты, требуемые на поддержание согласованного состояния резервной копии в нормальном режиме. Более разумное решение, названное цепочной (chained) декластеризацией, применено в Gamma, где первичная и резервная копии хранятся на двух соседних узлах. В режиме сбоя загрузка отказавшего узла распределяется между всеми остальными узлами, которые используют копии данных как первичного, так и вторичного узла. Поддержание согласованных копий в этом случае обходится дешевле. Открытым остается вопрос о процедуре размещения данных с учетом их реплицирования. Так же, как и размещение фрагментов в распределенных базах данных, эта проблема должна рассматриваться как одна из проблем оптимизации.

1.5 Проблемы сетевой масштабируемости

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

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

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

1.6 Распределенная и параллельная обработка запросов

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

Стоимостная модель - центральное звено глобальной оптимизации запросов, поскольку она предоставляет необходимую абстракцию среды выполнения распределенной СУБД в терминах методов доступа, а также абстракцию самой базы данных в терминах информации об ее физической схеме и соответствующей статистики. Стоимостная модель используется для предсказания затрат на выполнение альтернативных планов запроса. Со стоимостными моделями зачастую связан ряд серьезных ограничений, которые снижают эффективность оптимизации, направленной на улучшение общей пропускной способности системы. Полезными здесь могут быть работы по созданию расширенных алгоритмов оптимизации на основе параметризуемой стоимостной модели, которую можно настраивать экспериментальным способом. Хотя языки запросов становятся все более развитыми (новые версии SQL), на стадии глобальной оптимизации применяется весьма ограниченное их подмножество, а именно, подмножество, позволяющее формулировать SPJ-запросы (select-project-join - селекция-проекция-соединение) с конъюнктивными предикатами. Это важный класс запросов, для которого существуют развитые методы оптимизации. Разработаны, в частности, различные теории оптимального упорядочения соединений и полусоединений. В то же время, имеются и другие важные классы запросов, для которых еще предстоит создать соответствующие методы оптимизации: запросы с дизъюнкциями, объединениями, фиксированными точками (fixpoint), агрегацией и сортировкой. Многообещающий подход к этой проблеме заключается в отделении чисто языковые аспекты от собственно оптимизации, которую можно доверить нескольким "экспертам оптимизации".

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

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

Критически важной проблемой с точки зрения стратегии поиска является проблема упорядочения соединений, которая является NP-полной от числа отношений. Типичный подход к решению этой задачи - применение динамического программирования, которое является детерминированной стратегией. Эта почти исчерпывающая стратегия, гарантирующая нахождение наилучшего плана из всех возможных. Затраты (по времени и памяти) на ее реализацию приемлемы для небольшого числа отношений. Однако уже для 5-7 отношений такой подход становится слишком дорогостоящим. В связи с этим в последнее время возрос интерес к стратегиям случайного перебора (randomized strategy), которые снижают сложность оптимизации, но не гарантируют нахождение наилучшего плана. Стратегии случайного перебора исследуют пространство решений контролируемым образом, в том смысле что оптимизация завершается по исчерпанию заданного для нее бюджета времени. Еще один способ снизить сложность оптимизации - применение эвристических подходов. В отличие от детерминированных стратегий, стратегии случайного перебора позволяют управлять соотношением затрат на оптимизацию и выполнение запросов.

1.7Распределенная обработка транзакций

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

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

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

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

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

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

2. Практическая часть

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

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

2.1 Процесс выполнения запроса к хранилищу данных в параллельной системе баз данных

В современных параллельных системах баз данных используется гибрид физической модели 3NF и многомерных представлений, поскольку системы очень хорошо обрабатывают соединения и обладают зрелым и надежным оптимизатором. Представления в ПСБД не материализуются до выполнения соответствующих запросов, что делает возможным отражать в плане запроса с соединением потребности каждого индивидуального запроса, минимизировать объем данных, которые требуется перераспределять или дублировать. Хэширование на первичном индексе упрощает разделение, и распределение памяти происходит только на уровне базы данных, а не на основе принципа таблица-раздел и индекс-раздел. В оптимизаторах ПСБД используется пересечение индексов, что обеспечивает эффективность почти такого же уровня, который дают битовые индексы, без потребности в накладных расходах для их поддержки. Это означает, что ПСБД нуждается в создании меньшего числа индексов, что приводит к дальнейшему сокращению требуемых объемов памяти и времени для поддержки индексов. Наличие возможности синхронного сканирования (sync scan) позволяет использовать время, требуемое для сканирования больших таблиц, для выполнения нескольких (и даже сотен и тысяч) параллельно выполняемых запросов, делающих одну и ту же работу, что повышает пропускную способность системы на несколько порядков.

Когда в 1988 году фирма Teradata впервые начала обслуживать сверхбольшие базы данных, обнаружились некоторые странные проблемы. Даже при использовании подхода с отказом от общих ресурсов (shared-nothing) для обработки и сканирования больших таблиц требуется большое время. В результате инженеры разработали методы, заставляющие оптимизатор сначала обрабатывать малые таблицы измерений, соединяя их с целью создания первичного индекса для большой таблицы фактов и сокращая тем самым время ответа для многих запросов. Эти методы были включены в оптимизаторы ПСБД. Как показывает рисунок 1, у большой таблицы (Sales) имеется составной первичный индекс, составленный из внешних ключей таблиц измерений Stores, Items и Weeks. В звёзднообразной схеме все четыре таблицы логически, а иногда и физически, объединяются. Запрос (Select), представленный на рис. 2, позволяет произвести выборку из Stores, Items и Weeks с пересечением с указанными данными из Sales. В частности, здесь необходимо узнать общий объем продаж всех телевизоров в некоторой группе штатов (скажем Colorado и Minnesota) в течение двух недель перед Super Bowl, и результаты запроса необходимо вывести в соответствии с размером экрана телевизора и в лексикографическом порядке названий магазинов. Указанное представление (View) эмулирует звезнообразную схему, в запросе не принимается во внимание базовая физическая модель, и запрос прост (особенности модели скрываются представлением).

Sales (большая таблица, около 4 миллионов строк)
Item	Store	Week

Таблица Items (2 миллиона строк)	Таблица Store (2000 строк)	Таблица Week (65 строк)

Рис. 1. Таблица (Sales) со звезднообразной схемой и составным первичным индексом.

Рис. 2. Запрос к таблице Sales.

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

1. Каждый AMP-процесс (Access Module Processes) производит выборку из таблицы Weeks по условию <Week selection criteria>. Промежуточный результат (Spool) дублируется на всех AMP (см. 1 на рис. 3).

2. Все AMP производят выборку из таблицы Stores по условию <Store selection criteria>. Выполняется соединение со Spool по фиктивному условию (строится декартово произведение). Spool дублируется на всех AMP (см. И1?И2).

3. Все AMP производят выборку из таблицы Items по условию <Item selection condition>. Выполняется соединение со Spool по фиктивному условию. Результат перераспределяется между всеми AMP и сортируется (см. И1?И2?И3)

4. На всех AMP выполняется соединение Sales и Spool с использованием MERGE JOIN (сканирование строк с сопоставлением хэш-кодов).

Рис. 3. Организация выполнения запроса к хранилищу данных в ПСБД.

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

? архитектура SE (SMP) -системы, где ресурсы являются разделяемыми (дисковая подсистема, оперативная память, системная шина),

? кластерная архитектура SD - системы, в которых отсутствуют разделяемые ресурсы за исключением подсистемы дисковой памяти и соединительной шины,

? архитектура SN (MPP) - системы, где разделяется только шина, соединяющая узлы.

Ниже приводится преобразование Лапласа-Стилтьеса (ПЛС) времени выполнения запроса к хранилищу данных, которое справедливо для каждого АМР параллельной системы баз данных.

2.2 Чтение данных измерений

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

Где K - число измерений.

производящая функция числа записей i-го измерения в узле, Vi - общее число записей i-го измерения, n - число AMP- узлов (AMP-процессоров), pi - вероятность, что запись i-го измерения удовлетворяет условию поиска по этому измерению в запросе, ч2(s) - ПЛС времени обработки записи блока листового уровня индекса (ч(s)) и записи таблицы измерения (ч(s)).



Это ПЛС учитывает, что блок чередования, где хранится требуемая запись таблицы (или индекса), читается с диска (цD(s)), запись сохраняется и читается из ОП, обрабатывается процессором (цPI(s)).

2.3 Обмен записями таблиц измерений и декартова произведения между узлами

Введём следующие формулы.

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

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

Каждая запись произведения рассматриваемого узла , дублируется на другие узлы. Записи декартова произведения, поступившие из других узлов, сохраняются и читаются в КЭШе процессора данного узла. Каждая запись декартова произведения продублирована на каждом узле, т.е. что записи поступили от других узлов .

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

И так получим:

Где

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

Определяется следующими рекуррентными формулами:



Поясним формулы (6). С вероятностью запись декартова произведения передаётся в n-й узел (испытание по схеме Бернулли успешно). С вероятностью () запись передаётся в другие узлы. Производящая функция числа таких записей равна и т.д. по рекурсии.

Приведённая ниже формула определяет время пересылки промежуточных декартовых произведений измерений (s), время межпроцессорного обмена записями окончательного декартова произведения ( и число записей таблицы фактов, обрабатываемых на данном (i-ом) узле (z):

ПЛС учитывает, что поступившие в i-ый узел записи декартова произведения от других узлов сохраняются в ОП и читаются в кэш процессора.

2.4 ПЛС времени выполнения запроса к ROLAP в ПСБД.

Это ПЛС имеет следующий вид:

 определяется выражением, - выражением, - определяется выражением, - ПЛС времени, затраченного узлом на агрегирование факта одной записи, - ПЛС времени сортировки на одно сравнение в ОП.

Таблица №1.

(обмен между процессорами осуществляется через ОП)

В табл. 1 приведены выражения для ПЛС цD(s), цM(s), цN(s), цPI(s), цPJ(s), цPA(s), цPS(s) - это ПЛС случайного времени обработки записи (исходной, промежуточной, результирующей) в ресурсе (диске, ОП, шине, процессоре).

1-pD - вероятность, что запись находится в кэше (СУБД или диска),

лD, лM, лN - интенсивности запросов к разделяемому ресурсу (на чтение записей из RAID-массива, на запись/чтение записей таблиц из ОП, на передачу записей по соединительной шине), мDB=1/tБЧ - интенсивность чтения блоков чередования с диска RAID-массива, tБЧ - среднее время чтения блока чередования,

NR - количество дисков в RAID-массиве (с учётом зеркальных),

мM - интенсивность записи/чтения записей таблиц из ОП,

мN - интенсивность передачи записей по соединительной шине,

мPI - интенсивность обработки записей в процессоре при их поиске и чтении с помощью индекса,

мPJ - интенсивность построения записей декартова произведения в процессоре,

мPS - интенсивность сравнений записей БД в процессоре при их сортировке,

мPA - интенсивность агрегации записей (значений фактов),

QPS - значение коэффициента при среднем значении,

(n-1) в табл. 1 означает, что заявка не ждёт сама себя в очереди к ресурсу.

Таким образом, в статье приведён вывод преобразования Лапласа-Стилтьеса случайного времени выполнения запроса к хранилищу данных для различных архитектур: SE (SMP), SD (кластер), SN (MPP), смешанной архитектуры на основе SMP-узлов. Это преобразование позволяет оценивать моменты случайного времени разных порядков (математическое ожидание, дисперсию и т.д.).

Заключение

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

Мы не охватили ряд смежных вопросов. Две важные проблемы, не рассмотренные здесь, - это системы мультибаз данных и распределенные объектно-ориентированные базы данных. Многие информационные системы развиваются независимо, опираясь на собственные реализации СУБД. Позже, когда появляется необходимость "интегрировать" эти автономные и часто разнородные системы, возникают серьезные трудности. Системы, которые предоставляют доступ к подобным, независимо разработанным разнородным базам данных, называются мультибазами данных (multidatabase system).

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

Список использованной литературы

1. М. Тамер Оззу, Патрик Валдуриз. Распределенные и параллельные системы баз данных: [Электронный ресурс]. [http://citforum.ru/database/classics/distr_and_paral_sdb/]. Проверено 26.11.2010.

2. Григорьев Ю.А., Плужников В.Л. Оценка времени соединения таблиц в параллельной системе баз данных// Информатика и системы управления. - 2011. - № 1. - С. 3-16.

3. Кузнецов С. Essential Modelling Options: [Электронный ресурс]. [http://citforum.ru/database/digest/dig_1612.shtml]. Проверено 14.03.2011.

4. Григорьев Ю.А., Плутенко А.Д. Теоретические основы анализа процессов доступа к распределённым базам данных. - Новосибирск: Наука, 2002. - 180 с.

5. Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы. Общий подход. - М.: БИНОМ. Лаборатория знаний, 2006. - 406 с.

6. Григорьев Ю.А., Плужников В.Л. Анализ времени обработки запросов к хранилищу данных в параллельной системе баз данных // Информатика и системы управления. - 2011. - № 2. - С. 94-106.

Размещено на Allbest