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

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

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

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

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

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

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

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

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

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

исключающими конфликты чтение-запись, запись-чтение изапись-запись.

Согласно известной теореме, сериализуемость транзакций заведомо гарантируется, если блокировки, относящиеся к одновременно выполняемым транзакциям, удовлетворяют простому правилу: "Ни одна блокировка от имени какой-либо транзакции не должна устанавливаться после снятия хотя бы одной

ранее	установленной	блокировки".	Это	правило	известно	под
названием двухфазной		блокировки[Gray,	1979], поскольку транзакция

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

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

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

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

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

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

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

Алгоритм распределенного (или децентрализованного) блокирования (distributed

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

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

Алгоритмы, основанные на временных метках, выполняют конфликтующие

операции транзакций в соответствии с временными метками, назначаемыми транзакциям при их поступлении в систему. Алгоритмы оптимистического управления одновременным доступом исходят из предположения о том, что конфликты между транзакциями редки, и доводят транзакцию до конца, а затем производят проверку корректности. Если выясняется, что фиксация данной транзакции повлечет нарушение сериализуемости, то транзакция откатывается и запускается снова.

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

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

В распределенной СУБД различаются четыре типа сбоев: сбой транзакции

(transaction failure), сбой узла (системы) (site (system) failure), сбой носителя

(диска) (media (disk) failure) и сбой коммуникационной линии (communication line failure).

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

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

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

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

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

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

Протоколы обеспечения	надежности поддерживают	два свойства
транзакций: атомарность	(atomicity) идолговечность	(durability).

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

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

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

прежде чем зафиксировать транзакцию, подтверждает, что он готов сделать это.

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

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

2.Если все узлы голосуют за фиксацию транзакции, то она фиксируется во всех участвующих в ней узлах.

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

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

Processing).

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

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

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

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

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

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

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

3.Сбой произошел после того, как координатор сообщил участникам о глобальном решении и завершил транзакцию. В этом случае ничего делать не нужно.

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

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

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

соображений эффективности. Каждая операция записи в логический элемент данных x отображается на множество операций записи во все физические копии x.

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

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

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

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

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

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

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

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

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

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

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