Классика баз данных - статьи

       

Алгоритм консенсуса большинства можно сформулировать


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


Содержание  Назад  Вперед