Замечания по поводу реализации свободной непротиворечивости

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

Задача получения новой непротиворечивой реплики

Рассматривается распределенное хранилище данных (РХД), состоящие из N узлов, каждый их которых содержит реплики данных. Стоит задача получения непротиворечивой реплики для нового N+1 узла.

Существует два различных подхода к решению этой задачи:

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

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

Алгоритм, иллюстрирующий 1-ый подход

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

Алгоритм получения глобального состояния системы

В [1] приводится алгоритм получения глобального состояния. Узел, инициирующий получение глобального состояния системы, выполняет локальное копирование и посылает всем остальным узлам запрос на проведение операции получения глобального состояния. Каждый узел, получив такой запрос, делает одно из двух:

1. Если запрос получен впервые, то он записывает свое локальное состояние и пересылает запрос всем остальным узлам. После этого он начинает протоколировать все входящие сообщения от всех узлов

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

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