Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2009 г.

Распределенные и параллельные системы баз данных

М. Тамер Оззу, Патрик Валдуриз

Источник: журнал Системы Управления Базами Данных # 4/1996, издательский дом «Открытые системы»
Новая редакция: Сергей Кузнецов, 2009 г.

Оригинал: M. Tamer Ozsu, Patrick Valduriez. Distributed and parallel database systems.

Содержание

Введение
Основные понятия
Технологии распределенных и параллельных баз данных
Исследовательские проблемы
Заключение
Определения терминов
Литература

Введение

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

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

Параллельный компьютер, или мультипроцессор сам по себе является распределенной системой, составленной из узлов (процессоров, компонентов памяти), соединенных быстрой сетью внутри общего корпуса. Технология распределенных баз данных может быть естественным образом пересмотрена и распространена на параллельные системы баз данных, т. е. системы баз данных на параллельных компьютерах [DeWitt and Gray, 1992, Valduriez, 1993]. Благодаря применяемому в системах этого типа параллелизму при управлении данными [Boral, 1988] пользователи получают серверы баз данных высокой производительности и высокой доступности за существенно меньшую цену, чем эквивалентные системы на основе мэйнфреймов [DeWitt and Gray, 1992, Valduriez, 1993].

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

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

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

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

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

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

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

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

Ниже перечислены характерные черты параллельных и распределенных СУБД.

  1. Распределенная/параллельная база данных – это именно база данных, а не "коллекция" файлов, индивидуально хранимых на разных узлах сети. В этом заключается разница между DDB и распределенной файловой системой. Распределенные данные представляют собой DDB, только если они связаны в соответствии с некоторым структурным формализмом (таким как реляционная модель), а для доступа к ним имеется единый высокоуровневый интерфейс.
  2. Система обладает полной функциональностью СУБД. Она не сводится по своим возможностям ни к распределенным файловым системам, ни к системам обработки транзакций. Обработка транзакций – только одна из функций, предоставляемых подобными системами. Наряду с этим они должны также обеспечивать функции запросов и структурной организации данных, которые необязательно поддерживаются системами обработки транзакций.
  3. Распределение (включая фрагментацию и репликацию) данных по множеству узлов невидимо для пользователей. Это свойство называется прозрачностью. Технология распределенных/параллельных баз данных распространяет основополагающую для управления базами данных концепцию независимости данных на среду, где данные распределены и реплицированы по множеству компьютеров, связанных сетью. Это обеспечивается за счет нескольких видов прозрачности: прозрачность сети (следовательно, прозрачность распределения), прозрачность репликации и прозрачность фрагментации. Прозрачность доступа означает, что пользователи имеют дело с единым логическим образом базы данных и осуществляют доступ к распределенным данным точно так же, как если бы они хранились централизованно. В идеале полная прозрачность подразумевает наличие языка запросов к распределенной СУБД, не отличающегося от языка для централизованной СУБД.

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

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

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

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

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

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

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

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

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

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

Архитектурные проблемы

Существует множество альтернатив распределенной обработки. Наиболее популярна в настоящее время архитектура клиент-сервер [Orfali et al., 1994], когда множество машин-клиентов осуществляют доступ к одному серверу баз данных. В таких системах, которые можно определить как системы типа много-клиентов/один-сервер, проблемы управления базой данных решаются относительно просто, поскольку вся она хранится на одном сервере. Задачи, с которыми приходится здесь сталкиваться, – это управление буферами клиентов, кэширование данных и, возможно, блокировки. Управление данными реализуется централизованно на одном сервере.

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

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

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

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

Примерами систем параллельных баз данных являются продукты DBC (Teradata) и NonStop-SQL (Tandem), а также ряд прототипов, таких как BUBBA [Boral et al., 1990], EDS [EDS, 1990], GAMMA [DeWitt et al., 1990], GRACE [Fushimi et al., 1986], PRISMA [Apers et al., 1992] и ARBRE [Lorie et al., 1989].

Подход c разделяемой памятью заключается в том, что каждый процессор посредством быстрых линий связи (высокоскоростных шин или координатных коммутаторов) соединен со всеми модулями памяти и дисковыми устройствами. Существуют несколько типов мэйнфреймов, следующих этому подходу: IBM3090, DPS8 (Bull), а также симметричные многопроцессорные системы типа Sequent и Encore. Две сильные стороны систем с разделяемой памятью – простота и хорошая балансировка нагрузки. Три наиболее существенные проблемы, связанные с этим подходом, – стоимость, ограниченная масштабируемость, невысокая надежность.

К системам параллельных баз данных с разделяемой памятью относятся XPRS [Stonebraker et al., 1988], DBS3 [Bergsten et al., 1991] и Volcano [Graefe, 1990], а также перенесенные на мультипроцессоры с разделяемой памятью наиболее известные промышленные СУБД. Первым примером такой системы была реализация СУБД 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-запрос в какое-нибудь выражение, а затем, применяя правила эквивалентных алгебраических преобразований, получать из него другие алгебраические преобразования, пока не будет найдено "наилучшее". При поиске "наилучшего" выражения используется функция стоимости, в соответствии с которой вычисляется сумма затрат, необходимых для выполнения запроса. Этот процесс и называется оптимизацией запросов.

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

Исходной информацией для локализации данных служит исходное алгебраическое выражение, полученное на шаге декомпозиции запроса. В исходном алгебраическом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Основная роль локализации данных заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. На этом шаге выявляются фрагменты, реально участвующие в запросе, и запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Как отмечалось выше, правила фрагментации выражаются посредством реляционных операций (селекции для горизонтальной фрагментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации. Программа локализации для горизонтально (вертикально) фрагментированного отношения представляет собой объединение (union) (соединение (join)) соответствующих фрагментов. Таким образом, на шаге локализации данных каждое глобальное отношение запрос заменяется его программой локализации, а затем результирующий фрагментный запрос упрощается и реструктурируется с целью получения другого "хорошего" запроса. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и на шаге декомпозиции, окончательный запрос над фрагментами может быть еще далек от оптимального; данный процесс лишь исключает "плохие" алгебраические запросы.

Исходной информацией для третьего шага является фрагментный запрос, т. е. алгебраическое выражение над фрагментами. Цель глобальной оптимизации – найти стратегию выполнения запроса, близкую к оптимальной. Напомним, что нахождение оптимальной стратегии – вычислительно трудноразрешимая задача. Стратегию выполнения распределенного запроса можно выразить в терминах операций реляционной алгебры и коммуникационных примитивов (операций send/receive), используемых для пересылки данных между узлами. На предыдущих шагах запрос уже был в определенной мере оптимизирован, в частности, за счет удаления избыточных выражений. Однако проведенная оптимизация не зависела от характеристик фрагментов, например их мощности. Кроме того, на предыдущих шагах еще не учитывались коммуникационные операции. Путем изменения порядка операций внутри одного фрагментного запроса можно получить много эквивалентных планов его выполнения. Оптимизация запроса заключается в нахождении "наилучшего" плана из множества возможных планов, исследуемых оптимизатором1).

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

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

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

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

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

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

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

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

Наиболее популярные алгоритмы управления одновременным доступом основаны на механизме блокировок. В таких схемах всякий раз, когда транзакция пытается получить доступ к какой-либо единице памяти (как правило, странице), на эту единицу накладывается блокировка в одном из режимов – совместном (shared) или монопольном (exclusive). Блокировки накладываются в соответствии с правилами совместимости блокировок, исключающими конфликты чтение-запись, запись-чтение и запись-запись. Согласно известной теореме, сериализуемость транзакций заведомо гарантируется, если блокировки, относящиеся к одновременно выполняемым транзакциям, удовлетворяют простому правилу: "Ни одна блокировка от имени какой-либо транзакции не должна устанавливаться после снятия хотя бы одной ранее установленной блокировки". Это правило известно под названием двухфазной блокировки [Gray, 1979], поскольку транзакция проходит при этом сначала фазу "роста", когда она устанавливает блокировки, а затем фазу "сжатия", когда блокировки снимаются. В общем случае снятие блокировок до завершения транзакции проблематично. Поэтому в большинстве алгоритмов управления одновременным доступом применяется более жесткий подход, когда блокировки не снимаются до конца транзакции.

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

  1. выполнение этого множества транзакций является сериализуемым в каждом узле и
  2. порядок сериализации этих транзакций во всех узлах один и тот же.

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

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

Блокирование первичных копий (primary copy locking) – это алгоритм управления одновременным доступом, применяемый для баз данных с репликациями, где копии одних и тех же данных могут храниться в нескольких узлах. Одна из таких копий определяется как первичная копия, и для доступа к любому элементу данных необходимо установить блокировку на его первичную копию. Множество первичных копий элементов данных известно всем узлам распределенной системы, и запросы транзакций на блокирование направляются в узлы, где хранятся первичные копии. Если в распределенной базе данных репликации не используются, то данный алгоритм сводится к алгоритму распределенного блокирования. Алгоритм блокирования первичных копий был предложен для прототипа распределенной версии Ingres.

Алгоритм распределенного (или децентрализованного) блокирования (distributed (decentralized) locking), предполагает распределение обязанностей по управлению блокировками между всеми узлами системы. Для выполнения транзакции необходимо участие и взаимная координация менеджеров блокировок в нескольких узлах. Блокировки устанавливаются во всех узлах, данные которых участвуют в транзакции. Алгоритмам распределенного блокирования не свойственны издержки механизма централизованного блокирования, связанные с перегруженностью центрального узла. Однако алгоритмы этого типа сложнее, а коммуникационные затраты, необходимые для установки всех требуемых блокировок, выше. Алгоритмы распределенного блокирования применяются в системах System R* и NonStop SQL.

Общий побочный эффект всех алгоритмов управления одновременным доступом посредством блокирования – возможность тупиковых ситуаций (deadlock). Задача обнаружения и преодоления тупиков особенно сложна в распределенных системах. Тем не менее, благодаря относительной простоте и эффективности алгоритмов блокирования, они имеют значительно большую популярность, чем альтернативные алгоритмы, основанные на временных метках (timestamp-based algorithms), а также алгоритмы оптимистического управления одновременным доступом (optimistic concurrency control). Алгоритмы, основанные на временных метках, выполняют конфликтующие операции транзакций в соответствии с временными метками, назначаемыми транзакциям при их поступлении в систему. Алгоритмы оптимистического управления одновременным доступом исходят из предположения о том, что конфликты между транзакциями редки, и доводят транзакцию до конца, а затем производят проверку корректности. Если выясняется, что фиксация данной транзакции повлечет нарушение сериализуемости, то транзакция откатывается и запускается снова.

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

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

В распределенной СУБД различаются четыре типа сбоев: сбой транзакции (transaction failure), сбой узла (системы) (site (system) failure), сбой носителя (диска) (media (disk) failure) и сбой коммуникационной линии (communication line failure).

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

Сбои узлов (систем) могут быть вызваны аппаратными отказами (процессора, оперативной памяти, питания) или программными ошибками (в системном или прикладном коде). Системные сбои приводят к потере содержимого оперативной памяти. Поэтому в этом случае пропадут все элементы базы данных данных, находящиеся в буферах оперативной памяти (и называемые также неустойчивой базой данных (volatile database)). В то же время данные, находящиеся во вторичной памяти (называемые также стабильной базой данных (stable database)), остаются в сохранности. Для поддержания сохранности данных обычно применяют протоколы журнализации (logging protocol), например, журнализация с упреждающей записью (Write-Ahead Logging), которые создают в системных журналах записи обо всех изменениях в базе данных и в подходящие моменты времени перемещают журнальные записи, а также страницы неустойчивой базы данных в стабильную память. В распределенной базе данных проблема системных сбоев выражается еще и в том, что отказавший узел не может участвовать в выполнении какой-либо транзакции.

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

Рассмотренные выше три типа сбоев характерны и для централизованных, и для распределенных СУБД. Коммуникационные сбои, напротив, являются специфической проблемой распределенных баз данных. Они подразделяются на несколько разновидностей, наиболее распространенными из которых являются ошибки в сообщениях, нарушение упорядоченности сообщений, потерянные (недоставленные) сообщения, повреждения линий связи. Первые две из них относятся к компетенции сетевых протоколов и не учитываются в реализациях распределенных СУБД. Последние же две находятся в ведении СУБД и должны учитываться в протоколах обеспечения надежности. Если один узел ожидает сообщения от другого, а оно не поступает, то причин тому может быть несколько: (а) сообщение утрачено; (b) возникло повреждение на линии связи, соединяющей два эти узла; (c) узел, от которого ожидается сообщение, отказал. Таким образом, не всегда возможно отличить коммуникационный сбой от системного. Ожидающий узел по истечении определенного промежутка времени просто решает, что узел-партнер стал недоступен. Протоколы распределенных СУБД должны уметь адекватно реагировать на подобные неопределенные ситуации. Серьезным последствием повреждений на линиях связи может стать разделение сети (network partitioning), когда множество узлов распадается на группы, внутри которых имеется связь, а коммуникации между группами невозможны. В такой ситуации исключительно сложно обеспечить доступ пользователей к системе, гарантируя при этом ее согласованность.

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

Для обеспечения атомарности и долговечности необходимы атомарные протоколы фиксации (atomic commitment protocol) и протоколы распределенного восстановления (distributed recovery protocol). Наиболее популярным протоколом атомарной фиксации является протокол двухфазной фиксации транзакций (two-phase commit). Протоколы восстановления надстраиваются над протоколами локального восстановления, которые зависят от режима взаимодействия СУБД с операционной системой.

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

  1. Если хотя бы один узел отказывается зафиксировать транзакцию (голосует за ее аварийное завершение), то распределенная транзакция аварийно завершается во всех участвующих в ней узлах.
  2. Если все узлы голосуют за фиксацию транзакции, то она фиксируется во всех участвующих в ней узлах.

В простейшем варианте работа 2PC выглядит следующим образом. В узле, где инициируется транзакция, создается процесс-координатор (coordinator); во всех прочих затрагиваемых ею узлах создаются процессы-участники (participant). Вначале координатор рассылает участникам сообщение "приготовиться", и каждый из них независимо решает, может ли транзакция завершиться на данном узле. Участники, которые готовы завершить транзакцию, посылают координатору сообщение "голосую за фиксацию". Участники, не имеющие возможности зафиксировать свою часть транзакции, возвращают сообщение "голосую за аварийное завершение". Проголосовавший участник не может изменить свое решение. Координатор, собрав голоса участников, решает судьбу транзакции согласно правилам 2PC. Если он принимает решение зафиксировать транзакцию, то всем участникам рассылается сообщение "глобальная фиксация". Если решено завершить транзакцию аварийным образом, то участникам, проголосовавшим за ее фиксацию, посылается сообщение "глобальное аварийное завершение". Участникам, проголосовавшим за прерывание, сообщение посылать не нужно, поскольку они сами способны принять решение, исходя из правил 2PC. Это называется односторонним выбором участником аварийного завершения (unilateral abort option).

Протокол предполагает два "раунда" обмена сообщениями между координатором и участниками, отсюда название 2PC. Имеется несколько вариаций классического 2PC, таких как линейный 2PC и распределенный 2PC, не получивших широкого признания среди поставщиков распределенных СУБД. Две наиболее важные разновидности протокола – 2PC с предполагаемой фиксацией (presumed commit 2PC) и 2PC с предполагаемым аварийным завершением (presumed abort 2PC) [Mohan and Lindsay, 1983].Их важность определяется тем, что они позволяют сократить число сообщений, которыми должны обменяться узлы, и число операций ввода-вывода. Протокол с предполагаемым прерыванием вошел в стандарт X/Open XA и принят как часть стандарта ISO для открытой распределенной обработки (Open Distributed Processing).

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

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

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

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

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

В распределенных базах данных с поддержкой репликации2) каждому логическому элементу данных соответствует несколько физических копий. Так, размер зарплаты некоторого служащего (логический элемент данных) может храниться на трех узлах (физические копии). В такого рода системах возникает проблема поддержкой согласованности копий. Наиболее известным критерием согласованности является критерий полной эквивалентности копий (one copy equivalence), который требует, чтобы по завершении транзакции все копии логического элемента данных были идентичны.

Если поддерживается прозрачность реплицирования, то транзакция будет выдавать операции чтения-записи, относящиеся к логическому элементу данных x. Протокол управления репликами отвечает за отображение операций над x в операции над физическими копиями x (x1, x2 ,..., xn). Типичный протокол управления репликами, следующий критерию полной эквивалентности копий, известен под названием ROWA (Read-Once/Write-All – чтение из одной копии, запись во все копии). Протокол ROWA отображает чтение x [Read(x)] в операцию чтения какой-либо из физических копий xi [Read(xi). Из какой именно копии будет производиться чтение, неважно – этот вопрос может решаться из соображений эффективности. Каждая операция записи в логический элемент данных x отображается на множество операций записи во все физические копии x.

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

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

Идея, согласно которой для завершения транзакции достаточно модифицировать некоторое подмножество копий, легла в основу механизма голосования на основе кворума, используемого в протоколах управления репликами. Алгоритм консенсуса большинства можно сформулировать немного с другой точки зрения: каждой копии данных приписывается одно и то же число голосов, и транзакция, изменяющая логический элемент данных, может успешно завершиться, если она наберет большинство голосов. На той же идее основан ранний алгоритм голосования на основе кворума (quorum-based voting algorithm) [Gifford, 1979], который также присваивает копиям данных (возможно, не одно и то же) число голосов. Для выполнения любой операции чтения или записи элемента данных требуется получить кворум чтения (read quorum) (Vr) или кворум записи (write quorum) (Vw). Если элемент данных имеет в сумме V голосов, то при определении кворумов должны соблюдаться следующие правила.

1. Vr + Vw > V (две транзакции не могут одновременно читать и модифицировать один и тот же элемент данных во избежание конфликта чтение-запись);

2. Vw > V/2 (две транзакции не могут одновременно производить запись одного и того же элемента данных во избежание конфликта запись-запись).

Проблема, присущая этому подходу, состоит в том, что транзакция должна набрать кворум даже для чтения. Из-за этого существенно и неоправданно замедляется доступ к базе данных на чтение. Был предложен альтернативный протокол голосования на базе кворума, где этот серьезный недостаток преодолевается [Abbadi et al., 1985]. Однако этот протокол исходит из совершенно нереалистичных предположений о свойствах коммуникационной системы. Базовые требования состоят в том, что всем узлам немедленно становится известно об отказах, приводящих к изменениям в топологии сети, и каждый узел располагает представлением той части сети, где содержатся узлы, с которыми он взаимодействует. В общем случае невозможно гарантировать выполнимость этих требований. Таким образом, протокол полной эквивалентности копий является ограничительным с точки зрения доступности системы, а протоколы, основанные на голосовании, слишком сложны, и с ними связаны высокие накладные расходы. Поэтому в современных промышленных распределенных СУБД ни один из этих методов не используется. Для практического применения были исследованы некоторые более гибкие технологии репликаций, где тип согласования копий находится под контролем пользователя. На основе этого принципа уже создано или создается несколько разновидностей серверов репликации. К сожалению, в настоящее время не существует стройной теории, которая бы позволяла судить о согласованности реплицированной базы данных в условиях, когда применяются относительно нестрогие политики репликаций. Исследования в этой области находятся лишь в зачаточном состоянии.

Исследовательские проблемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Критически важной проблемой с точки зрения стратегии поиска является проблема упорядочения соединений, которая является NP-полной от числа отношений [Ibaraki and Kameda, 1984]. Типичный подход к решению этой задачи – применение динамического программирования [Selinger et al., 1979], которое является детерминированной стратегией. Эта почти исчерпывающая стратегия, гарантирующая нахождение наилучшего плана из всех возможных. Затраты (по времени и памяти) на ее реализацию приемлемы для небольшого числа отношений. Однако уже для 5-7 отношений такой подход становится слишком дорогостоящим. В связи с этим в последнее время возрос интерес к стратегиям случайного перебора (randomized strategy), которые снижают сложность оптимизации, но не гарантируют нахождение наилучшего плана. Стратегии случайного перебора исследуют пространство решений контролируемым образом, в том смысле что оптимизация завершается по исчерпанию заданного для нее бюджета времени. Еще один способ снизить сложность оптимизации – применение эвристических подходов. В отличие от детерминированных стратегий, стратегии случайного перебора позволяют управлять соотношением затрат на оптимизацию и выполнение запросов [Ioannidis and Wong, 1987, Swami and Gupta, 1988, Ioannidis and Kang, 1990].

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

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

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

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

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

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

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

Заключение

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

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

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


Определения терминов

Алгоритм голосования на базе кворума (quorum-based voting algorithm). Протокол управления репликами, при котором транзакция, для того чтобы выполнить операцию чтения или записи элемента данных, должна собрать необходимый кворум голосов его физических копий.

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

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

Архитектура без разделяемых ресурсов (shared-nothing architecture:). Архитектура параллельной СУБД, в которой каждый процессор имеет монопольный доступ к своей собственной оперативной памяти и к собственному набору дисков.

Архитектура с разделяемой памятью (shared-memory architecture). Архитектура параллельной СУБД, в которой каждый процессор посредством быстрых линий связи (высокоскоростной шины или коммутатора) имеет доступ к любому модулю памяти и к любому дисковому устройству.

Архитектура с разделяемыми дисками (shared-disk architecture). Архитектура параллельной СУБД, в которой каждый процессор имеет разделяемый доступ к любому диску системы посредством коммуникационных средств и монопольный доступ к собственной оперативной памяти.

Атомарность (atomicity). Свойство обработки транзакций, заключающееся в том, что либо выполняются все операции транзакции, либо не выполняется ни одна (принцип "все или ничего").

Блокирование (locking). Метод управления одновременным доступом, при котором на единицы хранения базы данных (страницы) накладываются блокировки от имени транзакции, которой необходим доступ к ним.

Внутризапросный параллелизм (intra-query parallelism). Параллельное выполнение множества независимых операций, которые могут относиться к одному и тому же запросу.

Внутриоперационный параллелизм (intra-operation parallelism). Параллельное выполнение одной реляционной операции в виде множества субопераций.

Двухфазовая фиксация транзакций (two-phase commit). Протокол атомарной фиксации, который гарантирует одинаковое завершение транзакции на всех затрагиваемых ею узлах. Название связано с тем, что в ходе выполнения протокола происходит два "раунда" обмена сообщениями между узлами.

Двухфазовое блокирование (two-phase locking). Алгоритм блокирования, при котором транзакция не имеет права установить новую блокировку на элемент данных, пока не сняты предыдущие.

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

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

Линейная масштабируемость (linear scaleup). Сохранение той же скорости обработки при увеличении размера базы данных вместе с одновременным пропорциональным наращиванием процессорной мощности и объема памяти.

Линейное ускорение (linear speedup). Пропорциональное увеличение скорости обработки при увеличении процессорной мощности и объема памяти и сохранении прежнего размера базы данных.

Межзапросный параллелизм (intra-query parallelism). Параллельное выполнение нескольких запросов, относящихся к разным транзакциям.

Независимость данных (data independence). Устойчивость прикладных программ и запросов к изменениям в физической организации базы данных (независимость от физических данных) или в ее логической организации (независимость от логических данных) и обратная независимость.

Неустойчивая база данных (volatile database). Часть базы данных, хранимая в буферах оперативной памяти.

Обработка запроса (query processing). Процесс трансляции декларативного запроса в последовательность низкоуровневых операций манипулирования данными.

Оптимизация запроса (query optimization). Процесс нахождения "наилучшей" стратегии выполнения запроса из некоторого множества альтернатив.

Параллельная система управления базами данных (parallel database management system). Система управления базами данных, реализованная на сильносвязанной многопроцессорной архитектуре.

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

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

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

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

Протокол ROWA (Read-Once/Write-All protocol). Протокол управления реплицированием, который логическую операцию чтения отображает на операцию чтения любой физической копии, а логическую операцию записи – на множество операций записи во все физические копии элемента данных.

Распределенная система управления базами данных (distributed database management system). Система, которая управляет базой данных, распределенной по узлам компьютерной сети, и обеспечивает для пользователей прозрачность распределения данных.

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

Стабильная база данных (stable database). Часть базы данных, хранимая во вторичной памяти.

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

Тупик (deadlock). Ситуация, когда множество транзакций образует цикл, ожидая снятия блокировок, установленных другими транзакциями из этого множества.

Литература

[Abbadi et al., 1985] A. E. Abbadi, D. Skeen, and F. Cristian. An Efficient, Fault-Tolerant Protocol for Replicated Data Management. – Proc. 4th ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, Portland, Oreg., March 1985, pp. 215-229.

[Apers et al., 1992] P. Apers, C. van den Berg, J. Flokstra, P. Grefen, M. Kersten, A. Wilschut. Prisma/DB: a Parallel Main-Memory Relational DBMS. – IEEE Trans. on Data and Knowledge Eng., 1992, 4(6), pp. 541-554.

[Bell and Grimson, 1992] D. Bell and J. Grimson. Distributed Database Systems. – Reading, MA: Addison-Wesley, 1993.

[Bergsten et al., 1991] B. Bergsten, M. Couprie, P. Valduriez. Prototyping DBS3, a Shared-Memory Parallel Database System. – Proc. Int. Conf. on Parallel and Distributed Information Systems, Miami, Florida, December 1991, pp. 226-234.

[Bernstein et al., 1987] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. – Reading, MA: Addison-Wesley, 1987.

[Boral, 1988] H. Boral. Parallelism and Data Management. – Proc. 3rd Int. Conf. on Data and Knowledge Bases, Jerusalem, June 1988, pp. 362-373.

[Boral et al., 1990] H. Boral, W. Alexander, L. Clay, G. Copeland, S. Danforth, M. Franklin, B. Hart, M. Smith, and P. Valduriez. Prototyping Bubba: a Highly Parallel Database System. – IEEE Trans. on Knowledge and Data Engineering, March 1990, 2(1), pp. 4-24.

[Ceri and Pelagatti, 1984] S. Ceri and G. Pelagatti. Distributed Databases: Principles and Systems. – New York: McGrow-Hill, 1984.

[Ceri et al., 1987] S. Ceri, B. Pernici, and G. Wiederhold. Distributed Database Design Methdologies. – Proc. IEEE, May 1987, 75(5), pp. 533-546.

[Copeland et al., 1988] G. Copeland, W. Alexander, E. Bougherty, and T. Keller. Data Placement in Bubba. – Proc. ACM SIGMOD Int. Conf. on Management of Data, Chicago, May 1988, pp. 99-108.

[DeWitt et al., 1990] D.J. DeWitt, S. Ghandeharizadeh, D.A. Schneider, A. Bricker, H.-I. Hsiao, and R. Rasmussen. The GAMMA Database Machine Project. – IEEE Trans. on Knowledge and Data Eng, March 1990, 2(1), pp. 44-62.

[DeWitt and Gray, 1992] D. DeWitt and J. Gray. Parallel Database Systems: The Future of High-Performance Database Systems. -Communications of ACM, June 1992, 35(6), pp. 85-98. Русский перевод: Д. Девитт, Д. Грэй. Параллельные системы баз данных: будущее высоко эффективных систем баз данных. – СУБД N2, 1995.

[Dogac et al., 1994] A. Dogac, M.T. Ezsu, A. Biliris, and T. Sellis (eds.) Advances in Object-Oriented Database Systems. – Berlin: Springer-Verlag, 1994.

[EDS, 1990] European Declarative System (EDS) Database Group. EDS-Collaborating for a High-Performance Parallel Relational Database. – Proc. ESPRIT Conf, Brussel, November 1990.

[Elmagarmid, 1992] A.K. Elmagarmid (ed.). Transaction Models for Advanced Database Applications. – San Mateo, CA: Morgan Kaufmann, 1992.

[Freytag et al., 1993] J-C. Freytag, D. Maier, and G. Vossen. Query Processing for Advanced Database Systems. – San Mateo, CA: Morgan Kaufmann, 1993.

[Freytag, 1987] J-C. Freytag. A Rule-based View of Query Optimization. – Proc. ACM SIGMOD Conf. on Management of Data, San Francisco, 1987, pp 173-180.

[Fushimi et al., 1986] S. Fumishi, M. Kutsuregawa, and H. Tanaka. An Overview of the System Software of a Parallel Relational Database Machine GRACE. – Proc 12th Int. Conf. on Very Large Data Bases, Kyoto, August 1986, pp. 209-219.

[Garcia-Molina and Lindsay, 1990] H. Garsia-Molina and B. Lindsay. Research Directions for Distributed Databases. – IEEE Q. Bull. Database Eng., December 1990, 13(4), pp. 12-17.

[Ghandeharizadeh et al., 1992] S. Ghandeharizadeh, D. DeWitt, W. Quresh. A Performance Analysis of Alternative Multi-Attributed Declustering Strategies. – ACM SIGMOD Int. Conf. on Management of Data. San Diego, CA, June 1992, pp. 29-38.

[Gifford, 1979] D.K. Gifford. Weighted Voting for Replicated Data. -Proc. 7th ACM Symp. on Operating System Principles, Pacific Grove, CA, December 1979, pp. 150-159.

[Graefe, 1990] G. Graefe. Encapsulation of Parallelism in the Volcano Query Processing Systems. – Proc. ACM SIGMOD Int. Conf, Atlantic City, NJ, May 1990, pp. 102-111.

[Gray, 1981] J. Gray. The Transaction Concept: Virtues and Limitations. – Proc. 7th Int. Conf. on Very Large Data Bases, Cannes, France, September 1981, pp. 144-154.

[Gray, 1979] J.N. Gray. Notes on Data Base Operating Systems. In Operating Systems: An Advanced Course, R. Bayer, R.M. Graham, and G. Seegmuller (eds.). – New York: Springer-Verlag, 1979, pp. 393-481.

[Gray and Reuter, 1993] J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. – San Mateo, CA: Morgan Kaufmann, 1993.

[Hsiao and DeWitt, 1991] H.-I. Hsiao and D. DeWitt. A Performance Study of three High-Availability Data Replication Strategies. -Proc. Int. Conf. on Parallel and Distributed Information Systems, Miami, December 1991, pp. 18-28.

[Ibaraki and Kameda, 1984] T. Ibaraki and T. Kameda. On the Optimal Nesting Order for Computing N-Relation Joins. – ACM Trans. Database Syst., September 1984, 9(3), pp. 482-502.

[Ioannidis and Wong, 1987] Y. Ioannidis and E. Wong. Query Optimization by Simulated Annealing. – Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1987, pp. 9-22.

[Ioannidis and Kang, 1990] Y. Ioannidis and Y.C. Kang. Randomized Algorithms for Optimizing Large Join Queries. – Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1990, pp. 312-321.

[Lorie et al., 1989] R. Lorie, J-J. Daudenarde, G. Hallmark, J. Stamos, H. Young. Adding Intra-Parallelism to an Existing DBMS: Early Experience. – IEEE Bull. on Database Engineering, March 1989, 12(1), pp. 2-8.

[Mohan and Lindsay, 1983] C. Mohan and B. Lindsay. Efficient Commit Protocols fpr the Tree of Processes Model of Distributed Transactions. – Proc. 2nd ACM SIGACT-SIGMOD Symp. on Priciples of Distributed Computing, 1983, pp. 76-88.

[Orfali et al., 1994] R. Orfali, D. Harkey and J. Edwards. Essential Client/Server Survival Guide. – New York: John Wiley, 1994.

[Ezsu, 1994] M.T. Ezsu. Transaction Models and Transaction Management in Object-Oriented Database Management Systems. (In Advances in Object-Oriented Database Systems. A. Dogac, M.T. Ezsu. , A. Biliris, and T. Sellis (eds). – Berlin: Springer-Verlag, 1994, pp. 147-183.)

[Ezsu. and Valduriez, 1991a] M.T. Ezsu. and P. Valduriez. Principles of Distributed Database Systems. – Englewood Cliffs, NJ: Prentice-Hall, 1991.

[Ezsu. and Valduriez, 1991b] M.T. Ezsu and P. Valduriez. Distributed Database Systems: Where Are We Now? – IEEE Computer, August 1991, 24(8), pp. 68-78.

[Ezsu et al., 1994] M.T. Ezsu, U. Dayal, and P. Valduriez (eds). Distributed Object Management. – San Mateo: Morgan Kaufmann, 1994.

[Selinger et al., 1979] P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price. Access Path Selection in a Relational Database Management System. – Proc. ACM SIGMOD Int. Conf. on Management of Data, Boston, Mass., May 1979, pp. 23-34.

[Shasha, 1992] D. Shasha. Database Tuning: a Principled Approach. – Englewood Cliffs, NJ: Prentice Hall, 1992.

[Sheth and Larson, 1990] A. Sheth and J. Larson. Federated Databases: Architectures and Integration. – ACM Comput. Surv., September 1990, 22(3), pp. 183-236.

[Stonebraker, 1989] M. Stonebraker. Future Trends in Database Systems. – IEEE Trans. Knowledge and Data Eng., March 1989, 1(1), pp. 33-44.

[Stonebraker et al., 1988] M. Stonebraker, R. Katz, D. Patterson, and J. Ousterhout. The Design of XPRS. – Proc. 14th Int. Conf. on Very Large Data Bases, Los Angeles, September 1988, pp. 318-330.

[Swami and Gupta, 1988] A. Swami and A. Gupta. Optimization of Large Join Queries. – Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1988, pp. 8-17.

[Valduriez, 1993] P. Valduries. Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases, April 1993, 1(2), pp. 137-165.

[Weihl, 1989] W. Weihl. Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Prog. Lang. Syst., April 1989, 11(2), pp. 249-281.

Комментарии к списку литературы

Сейчас есть два учебника по распределенным и параллельным базам данных – это наша книга [Ezsu and Valduriez, 1991a] и еще [Bell and Grimson, 1992]. Первой серьезной книгой по этой теме была [Ceri and Pelagatti, 1984], в настоящее время уже устаревшая. В статье [Ozsu and Valduriez, 1991b], которая во многом перекликается с упомянутой выше нашей книгой, обсуждаются многие открытые на сегодня проблемы распределенных баз данных. Упомянем также две блестящие статьи о параллельных системах баз данных [DeWitt and Gray, 1992, Valduriez, 1993].

Среди работ по более специфическим проблемам отметим книгу [Freytag et al., 1993], посвященную обработке запросов, где дается обзор результатов последних исследований. В работе [Elmagarmid, 1992] описан ряд новых моделей транзакций. [Gray and Reuter, 1993] содержит прекрасный обзор по проектированию менеджеров транзакций. Еще одна классическая книга, посвященная обработке транзакций, – [Bernstein et al., 1987]. В этих книгах освещены также вопросы надежности и управления одновременным доступом.


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

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

Новости мира IT:

Архив новостей

Последние комментарии:

Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...