Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

6.6. Примеры 391

биться легко, но если стек реплицируется на всех машинах, необходимо, как по-

казано ниже, затратить чуть больше усилий.

Огса объединяет синхронизацию и совместно используемые данные пример-

но так же, как при поэлементной непротиворечивости. Первый вид синхрониза-

ции

—

это синхронизация взаимного исключения, позволяющая не допустить

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

каждая из операций разделяемого объекта весьма напоминает критическую об-

ласть, поскольку система гарантирует, что итоговый результат будет таким же

самым, что и при поочередном (по одной за раз) обработке всех критических об-

ластей. В этом отношении объект Огса похож на распределенную форму монито-

ра, обсуждавшегося в главе 1.

Другим видом синхронизации является условная синхронизация, при ис-

пользовании которой процесс блокируется и ожидает выполнения некоторых

условий. В Огса условную синхронизацию обеспечивают стражи. В нашем при-

мере на листинге 6.2 процесс, пытающийся извлечь элемент из пустого списка,

будет приостановлен до того момента, когда стек перестанет быть пустым.

Управление совместно используемыми объектами в Огса

Управление объектами в Огса возложено на исполняющую систему. Оно поддер-

живается как в сетях с широковещательной (и групповой) рассылкой, так и в се-

тях со сквозной (от точки к точке) передачей. Исполняющая система выполняет

репликацию объектов, их пересылку, поддержание непротиворечивости и обра-

щения к операциям.

Каждый объект может быть в одном состоянии из двух

—

либо в виде единст-

венной копии, либо в виде реплики. Объект в состоянии единственной копии

имеется только на одной машине. Реплицированный объект представлен на всех

машинах, на которых имеются использующие его процессы. Не требуется, чтобы

все объекты находились в одном и том же состоянии, так что некоторые объек-

ты,

задействованные процессом, могут быть реплицированы, в то время как ос-

тальные представлять собой единственные копии. Объекты в ходе выполнения

могут менять свое состояние, переходя от единственной копии к реплицирован-

ному состоянию и обратно, что придает им большую гибкость.

Большое преимущество репликации объектов на всех машинах состоит в том,

что операции чтения могут выполняться локально, без поглощения сетевого тра-

фика и без задержек. Если объект не реплицирован, ему должны посылаться все

операции, а вызывающие его процессы — блокироваться в ожидании ответа.

Второе преимущество репликации состоит в том, что она повышает степень па-

раллельности: одновременно может происходить несколько операций чтения. При

использовании единственной копии одновременно может производиться только

одна операция, что замедляет выполнение. Принципиальный недостаток репли-

кации

—

затраты на поддержание непротиворечивости всех копий.

Когда программа выполняет операцию над объектом, компилятор вызывает

процедуру 1nvoke_op исполняющей системы, задающую объект, операцию, пара-

метры и флаг, уведомляющий, будет ли объект при этом модифицироваться (это

называется записью) или нет (это называется чтением). Действие, вызываемое

392 Глава 6. Непротиворечивость и репликация

исполнением процедуры 1nvoke_op, зависит от того, реплицирован ли объект,

имеется ли в наличии его локальная копия, должна ли производиться запись или

чтение, поддерживает ли платформа надежную, полностью упорядоченную широ-

ковещательную рассылку. Различают четыре варианта, как показано на рис. 6.27.

Единственная локальная копия

й>@

Единственная удаленная копия

Реплицированный объект,

выполняется чтение

Реплицированный объект,

выполняется запись

й>@

0 @

в г

Рис. 6.27. Четыре варианта процесса Р, выполняющего операцию над объектом О в Огса

На рис. 6.27, а процесс собирается выполнить операцию над нереплицирован-

ным объектом, который расположен на одной машине с процессом. Это требует

только блокирования объекта, вызова операции и разблокирования объекта.

Смысл блокировки в том, чтобы избежать любых удаленных обращений во вре-

мя выполнения локальной операции.

На рис. 6.27, б мы также имеем дело с единственной копией объекта, но име-

ется и кое-что еще. Исполняющая система, используя вызов RPC, просит уда-

ленную машину выполнить нужную операцию, возможно, с небольшой задерж-

кой, если объект в момент прихода запроса блокирован. Ни в одном из этих двух

случаев между чтением и записью разницы нет (исключая тот факт, что запись,

если изменит используемые стражами переменные, может активизировать бло-

кированные процессы).

Если объект реплицирован, как показано на рис. 6.27, в и г, в нашем распоря-

жении всегда имеется его локальная копия, однако теперь имеет значение, какую

операцию мы хотим осуществить

—

чтения или записи. Чтение можно проделать

локально, без использования сети и без дополнительных затрат.

Запись в реплицируемые объекты

—

более хитрое дело. Если базовая система

поддерживает надежные, полностью упорядоченные широковещательные рас-

сылки, исполняющая система рассылает имя объекта, операцию и ее параметры,

а затем блокируется до завершения широковещательной рассылки. Все машины,

включая данную, вычисляют новое значение.

Отметим, что примитивы широковещательной рассылки должны быть на-

дежны, то есть нижележащие уровни должны автоматически обнаруживать и ис-

правлять потерю сообщений. Система Amoeba, на основе которой разрабатыва-

6.6. Примеры 393

лась система Огса, имеет такие средства. Каждое сообщение, предназначенное

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

альному процессу под названием

секвенсор

(sequencer),

который присваивает ему

последовательный номер, а затем рассылает его, используя ненадежную аппарат-

ную широковещательную рассылку. Когда процесс обнаруживает пропуск в по-

следовательных номерах, он понимает, что потерял сообщение, и предпринимает

действия по его восстановлению.

Если система не поддерживает надежной широковещательной рассылки (или

не имеет вообще никаких средств рассылки), обновления вносятся при помощи

протокола на базе первичной копии. Каждый объект имеет первичную копию.

Процесс, выполняющий обновление, посылает сначала сообщение первичной

копии объекта, блокирует ее и изменяет. Затем первичная копия посылает инди-

видуальные сообщения всем остальным машинам, имеющим копии этого объек-

та, требуя блокировки этих копий. Когда все они подтвердят наличие блокиров-

ки,

начавший все это процесс переходит во вторую фазу и посылает другое

сообщение, предназначенное для того, чтобы провести операцию и разблокиро-

вать объект.

Взаимные блокировки при этом невозможны. Если два процесса одновремен-

но захотят изменить один и тот же объект, один из них первым заблокирует пер-

вичную копию, а второй будет дожидаться, пока объект снова не освободится.

Кроме того, отметим, что в ходе процесса обновления все копии объекта блоки-

руются, так что ни один из прочих процессов не может считать прежние значе-

ния. Эта блокировка гарантирует, что все операции будут выполняться в гло-

бально уникальном последовательном порядке.

Теперь кратко рассмотрим алгоритм, с помощью которого мы определяем,

в каком состоянии (единственной копии или реплицированном) находится объ-

ект. Изначально программа Огса состоит из одного процесса, владеющего всеми

объектами. Когда она разветвляется, все остальные машины уведомляются об

этом событии и получают текущие копии всех совместно используемых парамет-

ров дочерних процессов. Каждая исполняющая система подсчитывает стоимость

репликации этого объекта и сравнивает ее со стоимостью отказа от репликации.

Чтобы проделать эти вычисления, необходимо знать ожидаемое соотношение

операций чтения и записи. Компилятор оценивает это значение, исследуя про-

грамму и принимая во внимание, что вызовы из циклов стоят больше, а вызовы

из условных инструкций ~ меньше, чем обычные вызовы. Также в расчетах учи-

тываются затраты на взаимодействие. Например, объект с соотношением чте-

ние/запись 10 в сети с широковещательной рассылкой следует реплицировать,

объект с соотношением чтение/запись 1 в сети со сквозной (от точки к точке)

связью

—

хранить в состоянии единственной копии, причем эту копию следует

располагать на той машине, на которой выполняется большинство операций за-

писи. Более детальное описание этого процесса можно найти в [29].

Поскольку все исполняющие системы проделывают одни и те же вычисле-

ния, они приходят к одинаковому решению. Если объект постоянно находится

на одной машине, а нужен на всех, он становится распределенным. Если объект

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

394 Глава 6. Непротиворечивость

репликация

уничтожают его копии. Используя этот же механизм, объект может перемещать-

ся с машины на машину.

Давайте рассмотрим, как реализуется последовательная непротиворечивость.

Для объектов в состоянии единственной копии все операции реально сериализо-

ваны, так что последовательную непротиворечивость мы получаем «даром». Для

реплицируемых объектов операции записи полностью упорядочены в результате

использования либо надежной, полностью упорядоченной широковещательной

рассылки, либо алгоритма на базе первичной копии. В любом случае мы имеем

глобальное соглашение о порядке выполнения операций записи. Операции чте-

ния локальны и могут случайным образом чередоваться с операциями записи, не

нарушая последовательной непротиворечивости.

Возможна различная оптимизация. Так, например, вместо синхронизации по-

сле операции ее можно производить в момент начала операции, как в случае по-

элементной непротиворечивости или слабой свободной непротиворечивости.

Преимущество такого нововведения в том, что если процесс выполняет опера-

цию над разделяемым объектом многократно (то есть в цикле), нам не понадо-

бится производить широковещательную рассылку до тех пор, пока какой-либо

другой процесс не проявит интерес к этому объекту.

Другая возможная оптимизация

—

не останавливать вызвавший процесс во

время широковещательной рассылки после операции записи, которая не должна

возвращать значения (например, как в примере с помещением в стек). Разумеет-

ся,

такая оптимизация должна быть прозрачна. Информация, предоставляемая

компилятором, делает возможными и другие варианты оптимизации.

Подведем итоги. Модель распределенной разделяемой памяти Огса сочетает

в себе хорошие традиции разработки программного обеспечения (инкапсулируе-

мые объекты), совместное использование данных, простую семантику и есте-

ственную синхронизацию. Кроме того, во многих случаях ее реализация так же

эффективна, как может быть разве что свободная непротиворечивость. Она пре-

красно работает, если базовое аппаратное обеспечение и операционная система

поддерживают эффективную надежную, полностью упорядоченную широкове-

щательную рассылку, а в обращениях приложений к совместно используемым

объектам отношение операций чтения к операциям записи изначально велико.

6.6.2. Слабая причинно непротиворечивая

репликация

в качестве следующего примера непротиворечивости и репликации, абсолютно

непохожего на предыдущий, обсудим схему репликации, реализующую потенци-

альную непротиворечивость и отслеживающую в то же время причинно-след-

ственные отношения между операциями. Эта схема, описанная в

[246],

исполь-

зуется в причинно непротиворечивых хранилищах данных, но использует для

распространения обновлений слабую форму непротиворечивости.

Модель системы

Для того чтобы понять, как работает слабая причинно непротиворечивая репли-

кация, мы адаптируем модель распределенного хранилища данных, которую не-

6.6. Примеры 395

давно использовали (см. рис. 6.4). Суть слабой причинно непротиворечивой реп-

ликации в том, что при помощи векторных отметок времени устанавливается

потенциальная причинно-следственная связь между операциями чтения и записи.

Векторные отметки времени мы обсуждали в предыдущей главе. Далее предполо-

жим, что хранилище данных является реплицируемым и распределенным по Л^сер-

верам. Как и ранее, мы считаем, что клиенты соединены с локальными (или бли-

жайшими доступными) серверами, хотя это ограничение не является строгим.

Клиенты могут связываться друг с другом, однако обмениваются информаци-

ей они при помощи операций с хранилищем данных. (Поэтому на практике на-

бор клиентов организуется в набор внешних интерфейсов хранилища данных,

которые обмениваются информацией, и «чистых» клиентов, которые остаются в

полном неведении о том, как именно в хранилище данных поддерживаются не-

противоречивость и репликации. Здесь мы не будем делать различия между ни-

ми.) Общая структура хранилища данных показана на рис. 6.28.

Клиенты

Очередь

на чтение

Ожидающий

запрос

Очередь

на запись

Локальный

сервер

Распределенное хранилище данных

Рис. 6.28. Обобщенная структура распределенного хранилища данных.

Предполагается, что клиенты также обслуживают взаимодействие,

связанное с поддержкой непротиворечивости

Как показано на рисунке, каждый сервер хранилища содержит локальную ба-

зу данных и две очереди операций. Локальная база данных содержит данные, ко-

торые должны постоянно храниться на сервере для поддержания глобальной мо-

дели непротиворечивости хранилища. Другими словами, она содержит именно

те данные, которые отождествляются с программным контрактом между клиен-

том и хранилищем данных, выраженные в форме модели непротиворечивости,

ориентированной на данные. В этом примере контракт побуждает свои локаль-

ные копии соответствовать причинной непротиворечивости.

Каждая копия поддерживает две очереди отложенных операций. Очередь на

чтение состоит из операций чтения, которые отложены до тех пор, пока локаль-

ная база данных не придет в состояние, соответствующее тому, на что рассчи-

тывает операция чтения. Так, например, если в операции чтения сказано, что

клиент, инициировавший операцию, обязательно должен увидеть результаты не-

396 Глава 6. Непротиворечивость и репликация

которых операций записи, локальная база данных должна быть обновлена этими

операциями до проведения операций чтения. Это требование очень близко к об-

суждавшейся ранее модели непротиворечивости, ориентированной на клиента.

Что такое на самом деле локальная непротиворечивость, мы обсудим ниже.

Точно так же очередь на запись содержит операции записи, которые отложе-

ны до тех пор, пока локальная база данных не придет в состояние, соответствую-

щее тому, на что рассчитывает операция записи. В частности, операция записи

может быть произведена только в том случае, если локальная база данных была

обновлена всеми предшествующими операциями, от которых причинно зависи-

ма эта операция записи. Детали мы также изложим ниже.

Для представления цельного состояния локальной базы данных и точного оп-

ределения того, какие операции в каком состоянии нуждаются, используются

векторные отметки времени. Прежде всего, каждая локальная копия Li поддер-

живает два вектора отметок времени. Вектор VAL{i) соответствует текущему со-

стоянию копии

Li.

VAL{i)[i\

—

это общее число запросов на запись, поступивших

напрямую от клиента копии Li и выполненных на этой копии. Кроме того, I, от-

слеживает, сколько операций обновления было ею принято (и обработано) от

копии

Lj.

Это число записывается в VAL{i)[j].

Второй вектор отметок времени, WORK{i), отражает, что должно быть сдела-

но копией

Li.

В частности, WORK{i)[i\

—

это общее число операций записи, при-

шедших от клиента, которые должны быть выполнены (включая уже выполняю-

щиеся), чтобы очередь записи стала пустой. Точно так же WORK{i)[j] отражает

общее число обновлений, присланных с Lj, которые должны быть выполнены,

чтобы очередь записи стала пустой.

Кроме этих двух векторов отметок времени каждый клиент отслеживает те-

кущее состояние хранилища данных. Для этого клиент С поддержршает вектор

отметок времени LOCAL(C), где LOCAL(C)[i] устанавливается равным послед-

нему значению состояния i/, которое видно из С. (Отметим, что клиент, произ-

водя чтение или запись, каждый раз контактирует с разными репликами.) Каж-

дый раз, когда клиент С пересылает запрос на чтение или запись

7?1У

локальной

копии, в качестве отметки времени DEP(RW) он выставляет LOCAL(C), чтобы

показать, от чего зависит RW.

Выполнение операций чтения

Теперь самое время описать, как происходят различные операции. Сначала мы

сосредоточимся на операции чтения, различные этапы которой иллюстрирует

рис.

6.29. Очередность здесь следующая.

Присваивание DEP(R):=LOCAL(C).

Проверка DEP(R)<VAL(i).

Передача данных и значения VAL(i).

Присваивание LOCAL(C):=max{LOCAL(C), VAL(i)}.

Когда клиент С (в нашем случае, внешний интерфейс) хочет произвести опе-

рацию чтения 7?, отметка времени DEP(R) соответствующего запроса на чтение

устанавливается равной LOCAL(C). Эта отметка времени отражает тот факт, что

6.6. Примеры 397

клиент постоянно знает о хранилище данных. После этого запрос передается од-

ной из копий.

Очередь

3 Реплика!

Рис. 6.29. Выполнение операции чтения локальной копии

Входящий запрос на чтение R к копии L всегда помещается в очередь на чте-

ние этой копии. Отметка времени DEP(R) отражает глобальное состояние хранили-

ща данных в тот момент времени, когда был послан запрос R. Для обработки R

необходимо, чтобы локальная копия Lf также была осведомлена об этом состоя-

нии. Так, в частности, для каждого значения j справедливо DEP(R)[j]

VAL(i)lj].

Как только операция чтения будет произведена, копия Li возвращает значе-

ние запрошенного элемента данных клиенту вместе с VAL(i), После этого клиент

приводит в соответствие с ним свой собственный вектор LOCAL(C), устанавли-

вая каждый из его элементов LOCAL(C)[j] в max{LOCAL(C)[j], VAL(i)[j]}.

Выполнение операций записи

Выполнение операций записи происходит более или менее аналогично операци-

ям чтения, как показано на рис. 6.30. Очередность этапов выполнения здесь сле-

дующая.

Присваивание D£'P(W^):=I0C4I(C).

Присваивания

WORK(i)[i]:-=WORK(i)[i]-^l,

ts(W)[i]:=WORK(i)[i\

и ts(W)[i]:-DEP(W)[Jl

Передача отметки времени z^5(W).

Присваивание

LOCAL(C):=^max{LOCAL(C),

ts(W)}.

Проверка DEP(W)

VAL(i).

Когда клиент С собирается выполнить операцию записи, он посылает запрос

на запись копии if, устанавливая отметку времени DEP(W) равной своему ло-

кальному вектору

LOCAL(C)y

как и в прошлый раз.

Когда копия получает запрос на запись W от клиента, она увеличивает

WORK(i)[i],

оставляя прочие элементы неизменными. Кроме того, в ответ на за-

прос на запись Li возвращает отметку времени ts(W), где /:5(W)[z] равно

WORK(i)[i]y

а другие элементы ts(W)[;] получили значения DEP(W)\j]. Эта от-

метка времени посылается клиенту как подтверждение, после чего клиент при-

водит в соответствие с ним собственный вектор LOCAL(C), устанавливая каж-

дый k-й его элемент LOCAL(C)[k] в значение

max{LOCAL(C)[k]i

ts(W)[k]}.

398 Глава 6. Непротиворечивость и репликация

Клиент

Реплика

Рис. 6.30. Выполнение операции записи локальной копии

Как

и в

случае запроса на чтение, запрос на запись

выполняется, только ес-

ли локальная копия

произвела все обновления, от которых зависит W. Это тот

случай, когда для каждого элемента DEP(W)[j]

VAL(i)[j]. В этом случае опера-

ция производится

вектор VAL(i) настраивается путем присваивания каждому

j-uy

элементу значения max{VAL(i)[j], ts(W){j]}. Поскольку вектор WORK{i)[i]

увеличился

на

единицу, когда запрос

был получен копией 1„

затем получил

значение метки

г^5(1У)[/],

мы легко убедимся, что запрос

обрабатывается копи-

ей Li при выполнении следующих двух условий:

ts(W)[i]-VAL(i)[t]

+ 1,

^5(W^)[;]

VAL(i)[j] для всех;

Первое условие гласит,

что

должны быть выполнены

все

операции, послан-

ные напрямую копии

if от

других клиентов

предшествующие операции запи-

си

Второе условие говорит

том, что все обновления,

от

которых зависит за-

пись

также должны быть выполнены на

Li.

Отметим, что эти два условия пол-

ностью аналогичны условиям реализации причинной доставки сообщений, кото-

рая обсуждалась

предыдущей главе.

Выполненные операции остаются

очереди, но никогда не выполняются снова.

Они сохраняются

очереди потому, что может потребоваться распространить их

для выполнения другим копиям. Это распространение обновлений обсуждается

далее.

Распространение обновлений

Чтобы закончить тему обработки операций, нам следует обсудить распростране-

ние операций обновления среди различных копий. Распространение обновлений

выполняется при помощи антиэнтропийных методов,

которых мы упоминали,

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

связыва-

ется с другой копией

и обменивается с ней операциями, содержащимися

оче-

редях

на

запись обеих копий.

Если говорить более конкретно, когда копия

связывается с другой копией

Lj,

она пересылает

ей все

сообщения, содержащиеся

в ее

очереди

на

запись. Кроме

того,

копии Lj пересылается векторная отметка времени WORK(i).

свою оче-

редь,

Lj подстраивает свой собственный вектор WORK(j), устанавливая каждый

6.7. Итоги 399

к'И

элемент равным max{WORK(i)[k], WORK(j)[k]}. Далее Lj включает операции

записи, полученные от i,, в свою очередь на запись. Если операция 1^уже содер-

жится в очереди

Lj,

она просто отбрасывается. В противном случае

добавляет-

ся в очередь.

После обмена обновлениями копия L/ просматривает, какие из полученных

ею операций могут быть выполнены. Обозначим через

набор всех отложенных

операций записи W, для которых для каждого ^-го элемента соблюдается усло-

вие DEP(W)[k]

VAL(i)[k]. Копия Z„ соответственно, выбирает операцию W\ не

зависящую от любой другой операции записи в наборе

Другими словами, в U

нет больше такой операции

для которой для каждого

k-то

элемента выполня-

ется условие DEP(W)[k]

DEP(W')[k]. После этого операция

1У

удаляется из U

и выполняется. Затем в наборе

выбирается следующая операция.

Существует еще множество нюансов, оставшихся «за кадром». Важно то, что

согласно приведенному описанию, очереди записи могут разрастись бесконечно.

Понятно, что операция должна удаляться из очереди сразу же, как только мы оп-

ределили, что она выполнена всеми копиями. Чтобы определить этот момент,

необходимо дополнительное администрирование и обмен дополнительной ин-

формацией. Детали можно найти в

[246].

6.7. Итоги

Существует два основных довода в пользу реплицирования данных

—

повыше-

ние надежности распределенных систем и увеличение их производительности.

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

реплик она становится отличной от остальных. Для сохранения непротиворечи-

вости реплик нам необходимо распространять обновления так, чтобы временная

противоречивость оставалась незаметной. К сожалению, это может значительно

снизить производительность, особенно в крупных распределенных системах.

Единственное решение этой проблемы

—

посмотреть, нельзя ли немного осла-

бить требования к непротиворечивости. В моделях строгой непротиворечивости

непротиворечивость определяется для отдельных операций чтения и записи со-

вместно используемых данных. Можно провести разделение этих моделей на

строгую непротиворечивость, последовательную непротиворечивость, линеари-

зуемость, причинную непротиворечивость и непротиворечивость FIFO.

Строгая непротиворечивость предполагает, что операции чтения всегда воз-

вращают последнее записанное значение. Из-за нереальности поддержки гло-

бального времени в распределенных системах реализация строгой непротиворе-

чивости невозможна. Последовательная непротиворечивость и линеаризуемость,

сущности, имеют ту же семантику, которая используется программистами в па-

раллельном программировании: все операции записи должны наблюдаться ото-

всюду в одинаковом порядке. Линеаризуемость

—

немного более строгая модель,

она упорядочивает операции в соответствии с глобальными часами (с конечной

точностью).

Причинная непротиворечивость отражает тот факт, что операции, потенци-

ально зависящие друг от друга, происходят в порядке, определяемом этой зави-

400 Глава 6. Непротиворечивость и репликация

симостью. Непротиворечивость FIFO просто определяет, что операции одного

процесса происходят в порядке, определяемом этим процессом.

Модели слабой непротиворечивости относятся к последовательностям опера-

ций чтения и записи. В частности, они предполагают, что каждая последователь-

ность сопровождается сопутствующими операциями с переменными синхрони-

зации, такими, как блокировки. Хотя это требует дополнительных усилий со

стороны программистов, эффективно реализовать модели слабой непротиворе-

чивости обычно проще, чем строгой.

В противовес этим моделям, ориентированным на данных, исследователи рас-

пределенных баз данных, предназначенных для мобильных пользователей, предло-

жили множество моделей непротиворечивости, ориентированных на клиента.

В этих моделях игнорируется тот факт, что данные могут совместно использо-

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

на уровне непротиворечивости, необходимом отдельному клиенту.

основу этих

моделей легло соображение о том, что клиент время от времени может подсоеди-

няться к различным репликам, при этом различия между ними должны быть не-

заметны. В сущности, модели непротиворечивости, ориентированные на клиен-

та, обеспечивают такое поведение системы, что при соединении клиента с новой

репликой эта реплика быстро приводится в соответствие с данными, с которыми

этот клиент работал раньше и которые могут находиться в других репликах.

Для распространения обновлений применяются различные технологии. Раз-

деление можно провести по тому,

что

на самом деле распространяется, куда рас-

пространяются обновления и кто инициирует распространение. Мы можем рас-

смотреть распространение уведомлений, операций или состояния. Кроме того,

не все реплики следует всегда обновлять немедленно. Какая реплика и в какой

момент будет обновлена, зависит от протокола распределения. И наконец, следу-

ет решить, могут ли обновления продвигаться другим репликам или каждая реп-

лика сама должна извлекать обновление у других реплик.

Протоколы непротиворечивости описывают конкретные реализации моделей

непротиворечивости. Для последовательной непротиворечивости и ее вариантов

выбор лежит между протоколами первичной копии и реплицируемой записи.

В протоколах первичной копии все операции обновления передаются первичной

копии, которая затем убеждается, что обновления правильно упорядочены и пе-

реданы. В протоколах реплицируемой записи обновление одновременно переда-

ется нескольким репликам. В этом случае правильное упорядочение операций

часто затруднено.

Вопросы и задания

Доступ к совместно используемым объектам в Java можно сериализовать,

объявив их методы синхронизуемыми. Достаточно ли этого, чтобы гаранти-

ровать сериализацию при репликации этих объектов?

Рассмотрим монитор, описанный в главе 1. Если потоки выполнения в репли-

цированном мониторе можно блокировать, что нам нужно сделать для гаран-

тии правильного срабатывания условной переменной?