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