Распределенная СУБД - Контроль репликации

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

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

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

Управление синхронной репликацией
Управление асинхронной репликацией

Управление синхронной репликацией

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

Например, давайте рассмотрим таблицу данных PROJECT (PId, PName, PLocation). Нам нужно запустить транзакцию T1, которая обновляет PLocation до «Mumbai», если PLocation - «Bombay». Если репликаций нет, операции в транзакции T1 будут:

Begin T1: 
   Update PROJECT Set PLocation = 'Mumbai' 
   Where PLocation = 'Bombay'; 
End T1;

Если таблица данных имеет две реплики на сайте A и сайте B, T1 необходимо создать двух дочерних T1A и T1B, соответствующих этим двум сайтам. Расширенная транзакция T1 будет -

Begin T1: 
   Begin T1A : 
      Update PROJECT Set PLocation = 'Mumbai' 
      Where PLocation = 'Bombay'; 
   End T1A;  
	
   Begin T2A : 
      Update PROJECT Set PLocation = 'Mumbai'
      Where PLocation = 'Bombay'; 
   End T2A; 
	
End T1;

Управление асинхронной репликацией

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

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

Алгоритмы управления репликацией

Некоторые из алгоритмов управления репликацией -

Алгоритм управления репликацией ведущий-ведомый.
Алгоритм распределенного голосования.
Алгоритм консенсуса большинства.
Алгоритм обращения токенов.

Алгоритм управления репликацией Master-Slave

Есть один главный сайт и N подчиненных сайтов. Главный алгоритм запускается на главном сайте для обнаружения конфликтов. Копия подчиненного алгоритма работает на каждом подчиненном сайте. Общий алгоритм выполняется в следующих двух фазах -

Transaction acceptance/rejection phase- Когда транзакция попадает в монитор транзакций подчиненного сайта, подчиненный сайт отправляет запрос на главный сайт. Главный сайт проверяет наличие конфликтов. Если конфликтов нет, мастер отправляет сообщение «ACK +» на подчиненный сайт, который затем запускает фазу приложения транзакции. В противном случае мастер отправляет сообщение «ACK-» подчиненному, которое затем отклоняет транзакцию.
Transaction application phase- После входа в эту фазу подчиненный сайт, в который вошла транзакция, передает всем подчиненным запрос на выполнение транзакции. Получив запросы, одноранговые ведомые устройства выполняют транзакцию и по завершении отправляют «ACK» запрашивающему ведомому устройству. После того, как запрашивающее ведомое устройство получило сообщения «ACK» от всех своих партнеров, оно отправляет сообщение «DONE» на главный сайт. Мастер понимает, что транзакция завершена, и удаляет ее из очереди ожидания.

Распределенный алгоритм голосования

Он состоит из «N» одноранговых сайтов, каждый из которых должен «ОК» транзакции, прежде чем она начнет выполняться. Ниже приведены две фазы этого алгоритма:

Distributed transaction acceptance phase- Когда транзакция поступает в диспетчер транзакций сайта, она отправляет запрос транзакции всем другим сайтам. Получив запрос, одноранговый сайт разрешает конфликты, используя правила голосования на основе приоритета. Если все одноранговые сайты согласны с транзакцией, запрашивающий сайт начинает фазу приложения. Если какой-либо из одноранговых сайтов не «ОК» транзакции, запрашивающий сайт отклоняет транзакцию.
Distributed transaction application phase- После входа в эту фазу сайт, в который вошла транзакция, транслирует запрос на все подчиненные устройства для выполнения транзакции. При получении запросов одноранговые ведомые устройства выполняют транзакцию и по завершении отправляют сообщение «ACK» запрашивающему ведомому устройству. После того, как запрашивающее ведомое устройство получило сообщения «ACK» от всех своих партнеров, оно сообщает диспетчеру транзакций, что транзакция завершена.

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

Это разновидность алгоритма распределенного голосования, при котором транзакция может выполняться, когда большинство одноранговых узлов «одобряют» транзакцию. Это разделено на три этапа -

Voting phase- Когда транзакция поступает в диспетчер транзакций сайта, она отправляет запрос транзакции всем другим сайтам. Получив запрос, одноранговый сайт проверяет конфликты с помощью правил голосования и сохраняет конфликтующие транзакции, если таковые имеются, в очереди ожидания. Затем он отправляет сообщение «ОК» или «НЕ ОК».
Transaction acceptance/rejection phase- Если запрашивающий сайт получает большинство «ОК» по транзакции, он принимает транзакцию и транслирует «ПРИНЯТЬ» на все сайты. В противном случае он передает сообщение «REJECT» на все сайты и отклоняет транзакцию.
Transaction application phase- Когда одноранговый сайт получает сообщение «REJECT», он удаляет эту транзакцию из своего списка ожидания и пересматривает все отложенные транзакции. Когда одноранговый сайт получает сообщение «ПРИНЯТЬ», он применяет транзакцию и отклоняет все отложенные транзакции в очереди ожидания, которые конфликтуют с этой транзакцией. По завершении он отправляет «ACK» запрашивающему ведомому устройству.

Алгоритм обращения токенов

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

Transaction serialization phase- На этом этапе планируется запуск всех транзакций в порядке сериализации. Каждой транзакции на каждом сайте назначается уникальный билет из последовательной серии, указывающий порядок транзакции. После того, как транзакции был присвоен билет, он транслируется на все сайты.
Transaction application phase- Когда сайт получает транзакцию вместе со своим билетом, он помещает транзакцию для выполнения в соответствии со своим билетом. После завершения транзакции этот сайт передает соответствующее сообщение. Транзакция завершается, когда завершается выполнение на всех сайтах.