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

М. Тамер Оззу, ПатрикПатрик — мужское имя, может также быть фамилией. Происходит от лат.patrician — представитель знати, патриций. Валдуриз

Источник: журнал СистемыСистема (от др.-греч. — «сочетание»)— множество взаимосвязанных элементов, обособленное от среды и взаимодействующее с ней, как целое. УправленияУправление— воздействие субъекта, направленное на достижение абстрактной (неконкретной), но вынужденно-корректируемой цели (задачи, идеи) в уже сложившихся рамках правил, которые неизбежно-совершенствуются когда субъект непротиворечивее познаёт реальность, с которой сосуществует. Базами Данных # 4/1996, издательский дом «Открытые системы»
Новая редакция: СергейСергей— мужское имя, происходит от римского родового имени Sergius в святцах: высокий, высокочтимый. Кузнецов, 2009 г.

ОригиналОригинал(от лат. originalis - первоначальный) — первоначальный, подлинный.: M. Tamer Ozsu, PatrickПатрик — мужское имя, может также быть фамилией. Происходит от лат.patrician — представитель знати, патриций. Valduriez. Distributed and parallel database systems.

Содержание

Архитектурные проблемы
Обработка и оптимизация запросов
Управление одновременным доступом
Протоколы обеспечения надежности
Протоколы репликации

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

Введение

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

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

Параллельный компьютер, или мультипроцессор сам по себе является распределенной системой, составленной из узлов (процессоров, компонентов памяти), соединенных быстрой сетью внутри общего корпуса. Технология распределенных баз данных может быть естественным образом пересмотрена и распространена на параллельные системы баз данных, т. е. системы баз данных на параллельных компьютерах [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). Узлы данных обладают средствами для хранения данных, а узлы приема запросов – нет. В узлах приема запросов лишь выполняются программы, реализующие пользовательский интерфейс для доступа к данным, хранящимся в узлах данных. Вторая особенность состоит в том, что узлы логически представляют собой независимые компьютеры. Следовательно, у такого узла имеется собственная основная и внешняя память, установлена собственная операционная система (может быть, одна и та же на всех узлах, а возможно, и нет) и имеется возможность выполнять приложения. Узлы связаны компьютерной сетью, а не входят в мультипроцессорную конфигурацию. Важно подчеркнуть слабую связанностьСвязанность (англ.coupling)или зависимость (англ.dependency) — характеристика взаимосвязи модуля с другими модулями. Это степень, в которой каждый программный модуль полагается на другие модули. процессоров, которые обладают собственными операционными системами и функционирует независимо.

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

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

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

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

Решение, тем самым, заключается в применении широкомасштабного параллелизма, чтобы усилить мощность отдельных компонентов путем их интеграции в целостную систему на основе соответствующего программного обеспечения параллельных баз данных. Важное значение имеет применение стандартСтандарт (от англ.standard— норма, образец) в широком смысле слова— образец, эталон, модель, принимаемые за исходные для сопоставления с ними др. подобных объектов.ных аппаратных компонентов, для того чтобы иметь возможностьВозможность — направление развития, присутствующее в каждом явлении жизни; выступает и в качестве предстоящего, и вполне объяснимо рациональным путем: в каждой возможности присутствует вероятная невозможность, «возможность невозможного». Возможность не определяется познанием того, что может быть. Познание вероятностей, возможностей не всегда влияет на нашу возможность. На изучении возможности основывается, главным образом, исследование бытия и события. с минимальным отставанием использовать результаты постоянных технологических усовершенствований. В программном обеспечении базы данных могут быть предусмотрены три вида параллелизма, присущие приложениям интенсивной обработки данных. Межзапросный параллелизм предполагает одновременное выполнение множества запросов, относящихся к разным транзакциям. Под внутризапросным параллелизмом понимается одновременное выполнение сразу нескольких операций (например операций выборки), относящихся к одному и тому же запросу. И внутризапросный, и межзапросный параллелизм реализуется на основе разделения данных, аналогичного горизонтальному фрагментированию. Наконец, понятиеПонятие — отображённое в мышлении единство существенных свойств, связей и отношений предметов или явлений; мысль или система мыслей, выделяющая и обобщающая предметы некоторого класса по определённым общим и в совокупности специфическим для них признакам. Понятия суть «сокращения, в которых мы охватываем, сообразно их общим свойствам, множество различных чувственно воспринимаемых вещей» (Ф. Энгельс), а также нечувственных объектов, таких как другие понятия. Понятие не только выделяет общее, но и расчленяет предметы, их свойства и отношения, классифицируя последние в соответствии с их различиями. Так, понятие «человек» отражает и существенно общее (то, что свойственно всем людям), и отличие любого человека от всего прочего. внутриоперационного параллелизма означает параллельное выполнение одной операции в виде набора субопераций с применением, в дополнение к фрагментации данных, также и фрагментации функций. Языки баз данных, ориентированные на операции над множествами, обеспечивают много возможностей для использования внутриоперационного параллелизма.

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует множество альтернатив распределенной обработки. Наиболее популярна в настоящееНастоящее— часть линии времени, состоящая из событий, которые происходят в настоящий момент, то есть определенная область пространства-времени. время архитектура клиент-сервер [Orfali et al., 1994], когда множество машин-клиентов осуществляют доступ к одному серверу баз данных. В таких системах, которые можно определить как системы типа много-клиентов/один-сервер, проблемы управления базой данных решаются относительно просто, поскольку вся она хранится на одном сервере. Задачи, с которыми приходится здесь сталкиваться, – это управление буферами клиентов, кэшированиеКэш или кеш (англ.cache, от фр.cacher— «прятать»; произносится [k]— «кэш»)— промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше идёт быстрее, чем выборка исходных данных из оперативной (ОЗУ) и быстрее внешней (жёсткий диск или твердотельный накопитель) памяти, за счёт чего уменьшается среднее время доступа и увеличивается общая производительность компьютерной системы. Доступ к данным, хранящимся в кэше программным путем на процессорах линейки [x86] невозможен. данных и, возможно, блокировки. Управление данными реализуется централизованно на одном сервере.

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

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

Архитектуры параллельных систем варьируются между двумя крайними точками, называемыми архитектура без разделяемых ресурсов (shared-nothing) и архитектура с разделяемой памятьПамять— одна из психических функций и видов умственной деятельности, предназначенная сохранять, накапливать и воспроизводить информацию. Способность длительно хранить информацию о событиях внешнего мира и реакциях организма и многократно использовать её в сфере сознания для организации последующей деятельности.ю (shared-memory). Промежуточную позицию занимает архитектураАрхитектура (лат.architectura от др.-греч. — старший, главный и др.-греч. — строитель, плотник) — искусство проектировать и строить здания и другие сооружения (также их комплексы), создающие материально организованную среду, необходимую людям для их жизни и деятельности, в соответствии с назначением, современными техническими возможностями и эстетическими воззрениями общества. с разделяемыми дисками (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«Encore» (рус. На бис)— пятый студийный альбом американского рэпера Эминема. Выход альбома был изначально запланирован на 16 ноября 2004года, но был перенесён на 12 ноября из-за утечки альбома в интернет. В первую неделю продаж было продано 711 тыс. экземпляров. На второй неделе альбом продался в 870 тыс. экземпляров. Альбом 2 недели продержался на 1-м месте «Billboard Top 200». К концу второй недели в США было продано уже 1,582,000 экземпляров. А в середине декабря стал 4 раза платиновым альбомом в США продано 5.2млн копий альбома. По всему миру тираж составляет 11 млн. экземпляров.. Две сильные стороны систем с разделяемой памятью – простота и хорошая балансировка нагрузки. Три наиболее существенные проблемы, связанные с этим подходом, – стоимость, ограниченная масштабируемость, невысокая надежность.

К системам параллельных баз данных с разделяемой памятью относятся XPRS [Stonebraker et al., 1988], DBS3 [Bergsten et al., 1991] и Volcano [Graefe, 1990], а также перенесенные на мультипроцессоры с разделяемой памятью наиболее известные промышленные СУБД. Первым примером такой системы была реализация СУБД DB2 на IBM3090 с шестью процессорами. Во всех известных на сегодняСегодня — наречие, указывающее (кроме телевизионных рекламных анонсов) на «текущий» 24-часовой отрезок времени (с 00 до 24 часов по местному времени). коммерческих продуктах (таких как Ingres и Oracle) используется только межзапросный (но не внутризапросный) параллелизм.

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

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

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

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

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

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

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

Исходной информацией для локализации данных служит исходное алгебраическое выражение, полученное на шаге декомпозиции запроса. В исходном алгебраическом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Основная роль локализации данных заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. На этом шаге выявляются фрагменты, реально участвующие в запросе, и запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Как отмечалось выше, правила фрагментации выражаются посредством реляционных операций (селекции для горизонтальной фрагментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации. Программа локализации для горизонтально (вертикально) фрагментированного отношения представляет собой объединение (union) (соединение (join)) соответствующих фрагментов. Таким образом, на шаге локализации данных каждое глобальное отношение запрос заменяется его программой локализации, а затем результирующий фрагментный запрос упрощается и реструктурируется с целью получения другого "хорошего" запроса. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и на шаге декомпозиции, окончательный запрос над фрагментами может быть еще далек от оптимального; данный процесс лишь исключает "плохие«Отбросы», также известен как «Неудачники» (англ.Misfits)— британский комедийно-фантастический телевизионный сериал. Премьера состоялась 12 ноября 2009 года на канале E4. В России первый сезон был показан 30 и 31 октября 2010 года (по 3 серии в день) на MTV под названием «Плохие». 29 октября 2011 года данный сериал показали на канале 2х2, приурочив показ сериала празднику Хэллоуин." алгебраические запросы.

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

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

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

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

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

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

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

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

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

Наряду с психическими процессами и свойствами личности состояния являются основными классами психических явлений, которые изучает наука психология. Психические состояния влияют на протекание психических процессов, а, повторяясь часто, приобретя устойчивость, могут включиться в структуру личности в качестве её специфического свойства. Так как в каждом психическом состоянии присутствуют психологические, физиологические и поведенческие компоненты, то в описаниях природы состояний можно встретить понятия разных наук (общей психологии, физиологии, медицины, психологии труда ит.д.), что создаёт дополнительные трудности для исследователей, занимающихся данной проблемой. В настоящее время не существует какой-либо единой точки зрения на проблему состояний, так как состояния личности можно рассматривать в двух аспектах. Они являются одновременно и срезами динамики личности, и интегральными реакциями личности, обусловленными её отношениями, поведенческими потребностями, целями активности и адаптивности в окружающей среде и ситуации. данных требуется синхронизовать доступ. Синхронизация достигается путем применения алгоритмов управления одновременным доступом (concurrency control algorithm), гарантирующих следование критериям корректности, таким как сериализуемость (serializability). Доступ пользователей к данным инкапсулируются в рамках транзакций [Gray, 1981], которые на нижнем уровне выглядят как последовательности операций чтения и записи данных. Алгоритмы управления одновременным доступом обеспечивают соблюдение свойстваСвойство (в философии, математике и логике)— атрибут предмета (объекта). Например, о красном предмете говорится, что он обладает свойством красноты. Свойство можно рассматривать как форму предмета самого по себе, притом, что он может обладать и другими свойствами. Свойства, следовательно, подпадают под действие парадокса Рассела и парадокса Греллинга-Нельсона. изолированности выполнения транзакций, которое заключается в том, что воздействия одной транзакции на базу данных не будут зависеть (т.е. будут изолированы) от других транзакций, пока эта первая транзакция не завершит свое выполнение.

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

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

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

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

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

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

Алгоритм распределенного (или децентрализованного) блокирования (distributed (decentralized) locking), предполагает распределение обязанностей по управлению блокировками между всеми узлами системы. Для выполнения транзакции необходимо участие и взаимная координация менеджеров блокировок в нескольких узлах. Блокировки устанавливаются во всех узлах, данные которых участвуют в транзакции. Алгоритмам распределенного блокирования не свойственны издержкиЗатраты— размер ресурсов (для упрощения измеренный в денежной форме), использованных в процессе хозяйственной деятельности за определённый временной этап. механизма централизованного блокирования, связанные с перегруженностью центрального узла. Однако алгоритмыАлгоритм, от имени учёного аль-Хорезми (перс. [al-Khwrazm])— точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система. этого типа сложнее, а коммуникационные затраты, необходимые для установки всех требуемых блокировок, выше. Алгоритмы распределенного блокирования применяются в системах 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), когда множество узлов распадается на группы, внутри которых имеется связь, а коммуникации между группами невозможны. В такой ситуации исключительно сложно обеспечить доступ пользователей к системе, гарантируя при этом ее согласованность.

ПротоколПротокол (от др.-греч. protos— «первый» и kolla— «клей»)— первый лист, приклеенный к свитку. На нем фиксировались титульная информация (например, дата написания, имя писателя) и краткое основное содержание свитка.ы обеспечения надежности поддерживают два свойства транзакций: атомарностьАтомарные операции— операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Атомарность операций имеет особое значение в многопроцессорных компьютерах (и многозадачных операционных системах), так как доступ к неразделяемым ресурсам должен быть обязательно атомарным. (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 ProcessingProcessing— открытый язык программирования, основанный на Java. Представляет собой лёгкий и быстрый инструментарий для людей, которые хотят программировать изображения, анимацию и интерфейсы. Используется студентами, художниками, дизайнерами, исследователями и любителями, для изучения, прототипирования и производства. Он создан для изучения основ компьютерного программирования в визуальном контексте и служит альбомным программным обеспечением (имеется в виду то, что каждый *.pde файл визуальной оболочки Processing’а представляет собой отдельное изображение или анимацию, ит.д.) и профессиональным производственным инструментом.).

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

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

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

Обратной стороной терминирования является восстановление. Какие действия должен предпринять восстанавливающийся после сбоя узел, чтобы привести базу данных в согласованное состояниеСостояние — абстрактный термин, обозначающий множество стабильных значений переменных параметров объекта.? Это относится к области компетенции протоколов распределенного восстановления. Рассмотрим данную процедуру для приведенного выше примераПримера Дивизион (исп.Primera Divisin) профессиональной футбольной лиги Испании (исп.Liga de Ftbol Profesional, LFP), известный также как Примера и Ла Лига (исп.La Liga), является профессиональным футбольным турниром клубов высшего уровня в системе футбольных лиг Испании. Ла Лига считается одной из лучших футбольных лиг в мире., когда координирующий узел возобновляет работу после сбоя, и протокол восстановления должен принять решение о том, как следует поступить с транзакцией, которую координировал узел. Возможны следующие случаи.

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

Протоколы репликации

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

Если поддерживается прозрачность реплицирования, то транзакция будет выдавать операции чтения-записи, относящиеся к логическому элементу данных x. Протокол управления репликами отвечает за отображениеФункция— математическое понятие, отражающее связь между элементами множеств. Можно сказать, что функция это «закон», по которому каждому элементу одного множества (называемому областью определения) ставится в соответствие некоторый элемент другого множества (называемого областью значений). операций над x в операции над физическими копиями x (x₁, x₂ ,..., x_n). Типичный протокол управления репликами, следующий критерию полной эквивалентности копий, известен под названием ROWA (Read-Once/Write-All – чтение из одной копии, запись во все копии). Протокол ROWA отображает чтение x [Read(x)] в операцию чтения какой-либо из физических копий x_i [Read(x_i). Из какой именно копии будет производиться чтение, неважно – этот вопрос может решаться из соображений эффективности. Каждая операция записи в логический элемент данных x отображается на множество операций записи во все физические копии x.

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

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

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

1. V_r + V_w > V (две транзакции не могут одновременно читать и модифицировать один и тот же элемент данных во избежание конфликта чтениеЧтение— один из важнейших видов речевой деятельности, тесно связанный как с произношением, так и с пониманием речи. Также «чтение»— это способность воспринимать, понимать информацию, записанную (передаваемую) тем или иным способом, воспроизводить техническими устройствами.-запись);

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

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

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

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

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

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

Полная декластеризация, когда каждое отношение разделяется по всем узлам системы, вызывает проблемы при работе с небольшими отношениями, а также в системах с очень большим числом узлов. Более удачен подход переменной декластеризации (variable declustering), при котором каждое отношение хранится в некотором числе узлов, которое является функцией от размера отношения и частотыЧастоты выражены в герцах, а также в кратных единицах: кГц = 1000 Гц, МГц = 1000 кГц = 1000000 Гц, ГГц = 1000 МГц = 10 Гц, ТГц = 1000 ГГц = 10 Гц. Для частот ниже 1 Гц будут приводиться численные значения обратной величины— периода, выраженного в секундах, минутах, часах, сутках и годах, что упростит соотнесение с бытовыми величинами времени. В верхней же части шкалы, помимо частот, приводятся приблизительные эквивалентные значения энергии (в электронвольтах), ибо энергия осциллятора в квантовой механике пропорциональна частоте: E = h, где h— постоянная Планка, Е— энергия, — частота. доступа к нему [Copeland et al., 1988]. Этот подход может сочетаться с совместной кластеризацией нескольких отношений, что позволяет избежать избыточных коммуникаций при выполнении бинарных операций.

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

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

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

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

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

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

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

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

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

Стоимостная модель – центральное звено глобальной оптимизации запросов, поскольку она предоставляет необходимую абстракцию среды выполнения распределенной СУБД в терминах методов доступа, а также абстракцию самой базы данных в терминах информации об ее физической схеме и соответствующей статистики. Стоимостная модельМодель (фр.modle, от лат.modulus— «мера, аналог, образец»)— некоторый материальный или мысленно представляемый объект или явление, являющийся упрощённой версией моделируемого объекта или явления (прототипа) и в достаточной степени повторяющий свойства, существенные для целей конкретного моделирования(опуская несущественные свойства, в которых он может отличаться от прототипа). используется для предсказанияПредсказание— это, по определению, сообщение о некотором событии, которое непременно произойдет в будущем.
В этом смысле данное понятие существенно отличается от понятий: гадание, ясновидение, пророчество, прогнозирование и других понятий, являющихся, по сути, попытками заглянуть в будущее с целью подтверждения благоприятного или неблагоприятного исхода некоторых, вполне определённых, действий.
затрат на выполнение альтернативных планов запроса. Со стоимостными моделями зачастую связан ряд серьезных ограничений, которые снижают эффективность оптимизации, направленной на улучшение общей пропускной способности системы. Полезными здесь могут быть работы по созданию расширенных алгоритмов оптимизации на основе параметризуемой стоимостной модели [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]. Подобные модели послужили бы достижению более высокой производительности и надежности, а также снижению конкуренции. По мере того как базы данных внедряются во все новые прикладные области, такие как инженерное проектирование, программные разработки, офисные информационные системы, видоизменяются и сама сущностьСущность (лат.Essentia) — то постоянное, что сохраняется в явлении при различных его вариациях, в том числе и временных, сердцевина бытия. Сущность обычно трактуется либо в метафизической, либо в логической плоскости. В метафизике, особенно в томистской, сущность (эссенция) есть источник или основание существования (экзистенции). Синонимами слова сущность часто являются слова идея, назначение, функция. В логике сущность (как существенный признак — лат.essentialia constitutiva) — это неотъемлемое качество, без которого предмет невозможно мыслить. Сущность предмета выражается в его определении. транзакций, и предъявляемые к их обработке требования. Это означает, что следует выработать более изощренные модели транзакций, а также критерии корректности, отличные от сериализуемости.

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

Атомарность (atomicAtomic Austria GmbH (произносится Атомик Австрия Гмбх)— австрийская компания, крупный производитель спортивного инвентаря. Штаб-квартира компании расположена в Альтенмаркте, федеральная земля Зальцбург (Австрия). По состоянию на 2011 год, принадлежит Amer Sports.ity). Свойство обработки транзакций, заключающееся в том, что либо выполняются все операции транзакцииТранзакция (англ.transaction)— в информатике, группа последовательных операций, которая представляет собой логическую единицу работы с данными. Транзакция может быть выполнена либо целиком и успешно, соблюдая целостность данных и независимо от параллельно идущих других транзакций, либо не выполнена вообще и тогда она не должна произвести никакого эффекта. Транзакции обрабатываются транзакционными системами, в процессе работы которых создаётся история транзакций., либо не выполняется ни одна (принципПринцип или начало (лат.principium, греч. )— в теоретической философии то, чем объединяются в мысли и в действительности известная совокупность фактов. "все или ничего").

Блокирование (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 processingProcessing— открытый язык программирования, основанный на Java. Представляет собой лёгкий и быстрый инструментарий для людей, которые хотят программировать изображения, анимацию и интерфейсы. Используется студентами, художниками, дизайнерами, исследователями и любителями, для изучения, прототипирования и производства. Он создан для изучения основ компьютерного программирования в визуальном контексте и служит альбомным программным обеспечением (имеется в виду то, что каждый *.pde файл визуальной оболочки 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). КритерийКритерий (гр. kriterion— признак для суждения)— признак, основание, мерило оценки чего-либо. Особо выделяют критерии истинности знания. Различают логические (формальные) и эмпирические (экспериментальные) критерии истинности. Формальным критерием истины служат логические законы: истинно всё, что не заключает в себе противоречия, логически правильно. Эмпирическими критериями истинности служит соответствие знаний экспериментальным данным. Вопросом о критериях истины, выставляемых разными философскими школами, занимается теория познания или гносеология. корректности для управления одновременным доступом, который требует, чтобы эффект множества одновременно выполняемых транзакций был эквивалентен эффекту от их последовательного выполнения при каком-либо упорядочении.

Стабильная база данных (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 RecoveryRecovery (рус. Восстановление) — седьмой студийный альбом американского рэпера Eminem.Самый продаваемый альбом 2010 года в США.'а. Выход Recovery был подтвержден во время пресс-релиза Eminem’а, состоявшегося 5 марта 2009, и альбом был первоначально назван Relapse 2. Все было намечено на выпуск альбома продолжения в 2009, после выпуска альбома Relapse, но релиз был перенесен на следующий 2010 год. Позже было опубликованно окончательное название альбома, Recovery; также была подтверждена дата выпуска альбома: 21 июня в Соединенном Королевстве, (в остальных странах Европы 18 июня) 21 июня в Соединенных Штатах. Альбом дебютировал на первой строчке Billboard 200, Top Ramp;B/Hip-Hop Albums и Rap Albums Chart. 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. Русский переводПеревод— деятельность по интерпретации смысла текста на одном языке (исходном языке [ИЯ]) и созданию нового, эквивалентного текста на другом языке (переводящем языке [ПЯ]).: Д. ДевиттБрайс Селигман Девитт (англ.Bryce Seligman DeWitt; 8 января 1923, Динуба, Калифорния, США— 23 сентября 2004, Остин, Техас, США)— американский физик-теоретик., Д. Грэй. Параллельные системы баз данных: будущее высоко эффективных систем баз данных. – СУБД N2, 1995.

[Dogac et al., 1994] A. Dogac, M.T. Ezsu, A. Biliris, and T. Sellis (eds.) Advances in Object-Oriented Database Systems. – BerlinБерлин (нем.Berlin [blin])— столица Германии, самый крупный и самый населённый город Германии. После Лондона Берлин— второй по населению и пятый по площади город Евросоюза. Берлин— одна из 16 земель в составе Федеративной Республики Германия. Город расположен на берегах рек Шпрее (с этим связано «прозвище» Берлина «Spree-Athen»— «Афины на Шпрее») и Хафель в центре федеральной земли Бранденбург, частью которой он не является (с 1920 года).: 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, PacificPacific Racing— команда Формулы-1 из Великобритании. Провела два полных сезона в Формуле-1 в 1994-м и 1995-м годах, стартовав в общей сложности в 33 гонках. 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. HallmarkHallmark— телевизионная кабельная сеть, транслирующаяся в США. Специализируется на трансляции классических сериалов и фильмов, ориентированных для семейного просмотра. Владельцем является Crown Media Holdings., 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Джордж Эдвардс (англ.George Edwards; 3апреля 1694(16940403)— 23 июля 1773)— британский натуралист и орнитолог, «отец британской орнитологии».. 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 IssuesIssues— четвёртый студийный альбом группы Korn, вышедший 16 ноября 1999. Продан общим тиражом свыше 11000000 копий по всему миру. Альбом имеет четыре различных обложки, каждая из которых разработана поклонниками группы в рамках конкурса на канале MTV (основная обложка альбома была создана Альфредо Карлосом, другая обложка для специального издания альбома представляла собой рисованное полукарикатурное изображение группы).. 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]. В этих книгах освещены также вопросы надежности и управления одновременным доступом.

¹⁾ Разница между оптимальным и "наилучшим" планом состоит в том, что для нахождения первого требуется исследованиеИсследование— буквально «следование изнутри», процесс научного изучения чего-либо. всех возможных планов, что на практике никогда не реализуется из-за трудноразрешимого характера задачи.

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