Файл: Учебнопрактическое пособие Владимир 2021.pdf

196 временным доступом, и глобальная сериализуемость обеспечивается достаточно легко. Соответствующие алгоритмы просты в реализации, но с ними связаны две проблемы. Во-первых, центральный узел мо- жет стать узким местом как из-за большого объема обработки дан- ных, так и из-за генерируемого вокруг него интенсивного сетевого трафика. Во-вторых, надежность такой системы ограничена, посколь- ку отказ или недоступность центрального узла приводит к выходу из строя всей системы.
Блокирование первичных копий (primary copy locking) – это ал- горитм управления одновременным доступом, применяемый для баз данных с репликациями, где копии одних и тех же данных могут хра- ниться в нескольких узлах. Одна из таких копий определяется как первичная копия, и для доступа к любому элементу данных необхо- димо установить блокировку на его первичную копию. Множество первичных копий элементов данных известно всем узлам распреде- ленной системы, и запросы транзакций на блокирование направляют- ся в узлы, где хранятся первичные копии. Если в распределенной базе данных репликации не используются, то данный алгоритм сводится к алгоритму распределенного блокирования. Алгоритм блокирования первичных копий был предложен для прототипа распределенной вер- сии Ingres.
Алгоритм распределенного (или децентрализованного) блоки- рования (distributed (decentralized) locking), предполагает распределе- ние обязанностей по управлению блокировками между всеми узлами системы. Для выполнения транзакции необходимо участие и взаим- ная координация менеджеров блокировок в нескольких узлах. Блоки- ровки устанавливаются во всех узлах, данные которых участвуют в транзакции. Алгоритмам распределенного блокирования не свой- ственны издержки механизма централизованного блокирования, свя- занные с перегруженностью центрального узла. Однако алгоритмы этого типа сложнее, а коммуникационные затраты, необходимые для установки всех требуемых блокировок, выше. Алгоритмы распреде- ленного блокирования применяются в системах System R* и NonStop
SQL.

197
Общий побочный эффект всех алгоритмов управления одновре- менным доступом посредством блокирования – возможность тупико- вых ситуаций (deadlock). Задача обнаружения и преодоления тупиков особенно сложна в распределенных системах. Тем не менее, благода- ря относительной простоте и эффективности алгоритмов блокирова- ния, они имеют значительно большую популярность, чем альтерна- тивные алгоритмы, основанные на временных метках (timestamp-
based algorithms), а также алгоритмы оптимистического управления одновременным доступом (optimistic concurrency control). Алгоритмы, основанные на временных метках, выполняют конфликтующие опе- рации транзакций в соответствии с временными метками, назначае- мыми транзакциям при их поступлении в систему. Алгоритмы опти- мистического управления одновременным доступом исходят из пред- положения о том, что конфликты между транзакциями редки, и дово- дят транзакцию до конца, а затем производят проверку корректности.
Если выясняется, что фиксация данной транзакции повлечет наруше- ние сериализуемости, то транзакция откатывается и запускается сно- ва.
Протоколы обеспечения надежности
Как отмечалось выше, распределенные СУБД потенциально бо- лее надежны в силу того, что системные компоненты в них дублиру- ются, и тем самым исключаются одиночные точки отказа. Для реали- зации этого потенциала необходима тщательная проработка структу- ры системы, а также соответствующие протоколы обработки систем- ных сбоев.
В распределенной СУБД различаются четыре типа сбоев: сбой транзакции (transaction failure), сбой узла (системы) (site (system)
failure), сбой носителя (диска) (media (disk) failure) и сбой коммуни- кационной линии (communication line failure).
Причин сбоев транзакции может быть несколько: ошибки, вы- званные неверными входными данными, обнаружение возникшего или возможного тупика. Обычный способ обработки таких сбоев за-

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

199
СУБД и должны учитываться в протоколах обеспечения надежности.
Если один узел ожидает сообщения от другого, а оно не поступает, то причин тому может быть несколько: (а) сообщение утрачено; (b) воз- никло повреждение на линии связи, соединяющей два эти узла; (c) узел, от которого ожидается сообщение, отказал. Таким образом, не всегда возможно отличить коммуникационный сбой от системного.
Ожидающий узел по истечении определенного промежутка времени просто решает, что узел-партнер стал недоступен. Протоколы распре- деленных СУБД должны уметь адекватно реагировать на подобные неопределенные ситуации. Серьезным последствием повреждений на линиях связи может стать разделение сети (network partitioning), когда множество узлов распадается на группы, внутри которых имеется связь, а коммуникации между группами невозможны. В такой ситуа- ции исключительно сложно обеспечить доступ пользователей к си- стеме, гарантируя при этом ее согласованность.
Протоколы обеспечения надежности поддерживают два свой- ства транзакций: атомарность (atomicity) и долговечность (durability).
Атомарность означает, что выполняются либо все действия транзак- ции, либо не выполняется ни одно из них (принцип "все или ничего").
Таким образом, множество операций, составляющих транзакцию, рассматривается как неделимая единица. Атомарность гарантируется даже в условиях возможных отказов. Долговечность означает, что ре- зультат успешно завершенной (зафиксированной) транзакции сохра- няется даже при последующих сбоях.
Для обеспечения атомарности и долговечности необходимы атомарные протоколы фиксации (atomic commitment protocol) и про- токолы распределенного восстановления (distributed recovery
protocol). Наиболее популярным протоколом атомарной фиксации яв- ляется протокол двухфазной фиксации транзакций (two-phase commit). Протоколы восстановления надстраиваются над протокола- ми локального восстановления, которые зависят от режима взаимо- действия СУБД с операционной системой.
Протокол двухфазной фиксации (2PC) – это простой и элегант- ный протокол, обеспечивающий атомарную фиксацию распределен-

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

201 вание, сообщение посылать не нужно, поскольку они сами способны принять решение, исходя из правил 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, если в период сбора голосов сбой происходит и на координирующем узле, и на одном из участников, оставшиеся узлы не способны решить между собой судьбу транзакции и вынуждены оставаться в заблокированном состоянии, пока не восстановится либо координатор, либо отказав- ший участник. В этот период невозможно снять установленные тран- закцией блокировки, что снижает доступность базы данных.

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

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

204 сти является критерий полной эквивалентности копий (one copy
equivalence), который требует, чтобы по завершении транзакции все копии логического элемента данных были идентичны.
Если поддерживается прозрачность реплицирования, то тран- закция будет выдавать операции чтения-записи, относящиеся к логи- ческому элементу данных x. Протокол управления репликами отвеча- ет за отображение операций над x в операции над физическими копи- ями x (x
1
, x
2
,..., x
n
). Типичный протокол управления репликами, сле- дующий критерию полной эквивалентности копий, известен под названием ROWA (Read-Once/Write-All – чтение из одной копии, за- пись во все копии). Протокол ROWA отображает чтение x [Read(x)] в операцию чтения какой-либо из физических копий x i
[Read(x i
). Из ка- кой именно копии будет производиться чтение, неважно – этот во- прос может решаться из соображений эффективности. Каждая опера- ция записи в логический элемент данных x отображается на множе- ство операций записи во все физические копии x.
Протокол ROWA прост и прямолинеен, но он требует доступно- сти всех копий элемента данных, чтобы транзакцию можно было тер- минировать. Сбой на одном из узлов приведет к блокированию тран- закции, что снижает доступность базы данных.
Было предложено несколько альтернативных алгоритмов, направленных на смягчение требования о том, что для завершения транзакции необходимо внести изменения в каждую копию элемента данных. Все они ослабляют ROWA, сопоставляя операцию записи с некоторым подмножеством физических копий.
Идея, согласно которой для завершения транзакции достаточно модифицировать некоторое подмножество копий, легла в основу ме- ханизма голосования на основе кворума, используемого в протоколах управления репликами. Алгоритм консенсуса большинства можно сформулировать немного с другой точки зрения: каждой копии дан- ных приписывается одно и то же число голосов, и транзакция, изме- няющая логический элемент данных, может успешно завершиться, если она наберет большинство голосов. На той же идее основан ран- ний алгоритм голосования на основе кворума (quorum-based voting

205
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].
Однако этот протокол исходит из совершенно нереалистичных пред- положений о свойствах коммуникационной системы. Базовые требо- вания состоят в том, что всем узлам немедленно становится известно об отказах, приводящих к изменениям в топологии сети, и каждый узел располагает представлением той части сети, где содержатся уз- лы, с которыми он взаимодействует. В общем случае невозможно га- рантировать выполнимость этих требований. Таким образом, прото- кол полной эквивалентности копий является ограничительным с точ- ки зрения доступности системы, а протоколы, основанные на голосо- вании, слишком сложны, и с ними связаны высокие накладные расхо- ды. Поэтому в современных промышленных распределенных СУБД ни один из этих методов не используется. Для практического приме- нения были исследованы некоторые более гибкие технологии репли- каций, где тип согласования копий находится под контролем пользо- вателя. На основе этого принципа уже создано или создается не- сколько разновидностей серверов репликации. К сожалению, в насто- ящее время не существует стройной теории, которая бы позволяла