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

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

6.5. Протоколы непротиворечивости 381

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

упоминалась в главе 4.

Клиент

Текущий сервер

для элемента данных х

Новый сервер

для элемента данных х

Хранилище

данных

Рис. 6.22. Протокол локальной записи на базе первичной копии, в котором единственная

копия данных перемещается между процессами

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

токол первичного архивирования, в котором первичная копия перемещается ме-

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

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

после чего перемещает его туда, где находится сам, как это показано на рис. 6.23.

Здесь используются следующие обозначения:

—

запрос на запись;

—

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

—

подтверждение завершения записи;

—

сигнал на обновление резервных копий;

—

подтверждение обновления;

—

запрос на чтение;

Клиент Старый Новый ^

первичный первичный

сервер сервер

для элемента х Для элемента х

Клиент

Сервер резервного

копирования

Хранилище

данных

Рис. 6.23. Протокол первичного архивирования,

котором первичная копия перемещается

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

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

Основное преимущество этого подхода состоит в том, что многочисленные

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

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

Однако это улучшение может быть достигнуто только в том случае, если после

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

использованием описанного ранее неблокирующего протокола. Такой протокол

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

Упомянутый протокол первичного архивирования с локальной записью так-

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

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

ром для всех элементов данных, которые он собирается изменять. Будучи от-

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

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

ные.

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

с первичного сервера на серверы резервного копирования, вновь приводя храни-

лище данных в непротиворечивое состояние. Мы вернемся к работе в отключен-

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

файловые системы.

6.5.2. Протоколы реплицируемой записи

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

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

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

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

на большинстве голосов при голосовании.

Активная репликация

При активной репликации на каждой из реплик выполняется ассоциированный с

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

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

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

каждой реплике посылается операция записи. Однако, как было показано ранее,

можно также посылать и обновления.

С активной репликацией связана одна потенциальная проблема. Она состоит

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

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

рассылки. Подобную групповую рассылку, как показано в предыдущей главе,

можно реализовать на базе отметок времени Лампорта. К сожалению, подход с

использованием отметок времени Лампорта плохо масштабируется в больших

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

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

секвенсором

{sequencer).

Один из способов

—

просто передавать каждую опера-

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

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

6.5. Протоколы непротиворечивости 383

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

рассылки очень напоминает протоколы непротиворечивости

на

базе первичного

сервера.

Отметим,

что

использование секвенсора

не

решает проблем масштабируемо-

сти.

На

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

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

с использованием отметок времени Лампорта

секвенсоров. Подобное решение

описано

[384].

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

—

что делать

реплицированными

обращениями. Рассмотрим объект Л, обращаюш;ийся

другому объекту

В, как

показано на рис. 6.24. Объект

при этом обращается

третьему объекту

С.

Если

объект

реплицируется, каждая реплика

будет

принципе обращаться

объ-

екту С независимо

от

других. Проблема

том, что объект С получит множество

обращений вместо одного. Если вызываемый метод С призван выполнить пере-

вод $100 000 со счета на счет, очевидно, рано или поздно кто-нибудь пожалуется.

Клиент

реплицирует

обращение

Объект получает

одно

то

же

обращение трижды

Все реплики видят

одно

и то же

обращение

Реплицированный

объект

Рис. 6.24. Проблема репликации обращений

Репликация обращений

—

проблема не только объектов, но

некоторых сис-

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

ко-

торым он отправляет запросы, мы оказываемся

ситуации, когда запросы также

будут реплицированы, что может привести

нежелательным эффектам.

Немного существует общих решений проблемы репликации обращений. Одно

из решений, описанное в

[288],

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

лей поддержания непротиворечивости реплик. Другое решение является частью

системы GARF

[158].

Суть

его

состоит

создании осведомленного

репликах

коммуникационного уровня, поверх которого выполняются реплицируемые объ-

екты. Когда реплицированный объект

обращается

другому реплицированно-

му объекту

С,

первым делом

все

реплики объекта

присваивают этому обра-

щению один

и тот же

уникальный идентификатор. После этого координатор

реплик

передает обращение всем репликам объекта

С, в то

время

как

осталь-

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

ные реплики В воздерживаются от посылки своих копий обращения, как это по-

казано на рис. 6.25, а. В результате каждой реплике С посылается только одно

обращение.

Координатор

объекта В

Клиент реплицирует (

обращение •

Координатор

объекта С

Результат

Рис. 6.25. Передача обращения от реплицированного объекта другому реплицированному

объекту (а). Возвращение ответа одного реплицированного объекта другому (б)

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

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

Координатор реплик С уведомляется, что необходимо разобраться с реплициро-

ванными ответными сообщениями, созданными каждой из реплик С. Хотя эти

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

ликам объекта

В,

в то время как остальные реплики

воздерживаются от посыл-

ки своих копий ответного сообщения.

После того как реплика В в ответ на запрос, который она передавала объекту С

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

ординатором, возвращает результат реальному объекту А.

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

сылки, но одинаковые сообщения разными репликами не рассылаются. Таким

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

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

носящиеся к одному и тому же обращению, и передавала связанному с ней объ-

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

самостоятельного упражнения.

Протоколы кворума

Другой подход к поддержке реплицированных операций записи основан на ис-

пользовании

голосования

{voting).

Изначально он был представлен в [457] и обоб-

щен в

[167].

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

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

серверов.

6.5. Протоколы непротиворечивости 385

В качестве простого примера работы этого алгоритма рассмотрим распреде-

ленную файловую систему и предположим, что файл реплицирован на

Л^

серве-

ров.

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

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

одним (большинством) и попросить их согласия на обновление. Как только они

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

версии. Номер версии используется для идентификации версии файла и являет-

ся одинаковым для всех обновленных файлов.

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

виной серверов плюс еще одним и запросить у них номера версий, ассоцииро-

ванные с файлом. Если все номера версий согласованы, среди них должна быть и

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

рах, которым не был направлен запрос, невозможна,

—

они не составляют боль-

шинства.

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

них имеют файл версии 8, то не может быть, чтобы на остальных двух хранился

файл версии 9, поскольку любое обновление версии 8 на версию 9 требует разре-

шения как минимум трех, а не двух серверов.

Реальная схема более обобщенная, чем мы только что описали. Согласно этой

схеме для чтения файла, имеющего N реплик, клиент должен собрать кворум

чтения

(read

quorum) —

произвольный набор любых

ИЛИ

более серверов. Со-

ответственно, для модификации файла требуется кворум записи (write quorum),

образованный как минимум Nw серверами. Значения NR и Nw должны удовле-

творять следующим двум условиям:

NR + Nw> N,

Nw>N/2.

Первое ограничение используется для предотвращения конфликтов чтения-

записи, а второе

—

для предотвращения конфликтов двойной записи. Только по-

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

можно будет прочитать или изменить.

Чтобы рассмотреть, как работает алгоритм, взглянем на

рис.

6.26, а, на котором

3,3.

=10. Представим, что последний кворум записи состоял из 10 серве-

ров,

по I. Все они получили новую версию файла и новый номер версии. Все

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

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

обнаружит последнюю версию и воспользуется ей.

Рисунок 6.26, б иллюстрирует конфликт двойной записи, который может

произойти, поскольку Nw<N/2, Так, если один из клиентов выберет набор запи-

си

{A,B,C,E,F,G},

а другой

—

{D,HyIJ,K,L},

понятно, что мы столкнемся с пробле-

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

ми явно имеется конфликт.

Ситуация, представленная на рис. 6.26, в, особенно интересна, потому что

значение NR В этом случае равно единице, что делает чтение реплицируемого

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

Однако все имеет свою цену. За это мы платим тем, что для записи обновлений

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

нам необходимо согласие всех копий. Такая схема обычно называется ROWA

(Read-One, Write-All — читаем раз, пишем все). Имеются различные варианты

протоколов репликации по кворуму. Хороший обзор можно найти в

[213].

(А

В IC) D

IE F G H

II J К L 1

= 3.

NW=10

Кворум чтения

II J к LI

/ NR = 7, NW = 6

1 A В

E ©

1 J

NR=1.

С D '

G H

К L ^

Nw=12

Кворум записи

Рис. 6.26. Три примера алгоритма голосования. Правильный выбор наборов чтения

и записи (а). Выбор, который может привести к конфликтам двойной записи (б).

Правильный выбор, известный под названием ROWA (в)

6.5.3.

Протоколы согласования кэшей

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

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

согласования кэшей, которые отвечают за то, чтобы содержимое кэша соответст-

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

давшихся протоколов непротиворечивости.

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

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

Многие решения базируются на аппаратной поддержке, например, на предполо-

жении о возможности эффективной широковещательной рассылки или контро-

ля.

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

на базе операционных систем общего назначения, более интересны программные

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

используют два различных критерия [265, 296, 452].

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

стратегии

обнаружения согласованности (coherence detection

strategy),

то есть по тому,

когда

реально обнаруживается противоречивость. В статических решениях, как пред-

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

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

выми. Компилятор просто вставляет инструкции, позволяющие избежать проти-

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

меняются динамические решения. В них рассогласования обнаруживаются во

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

ляющим, модифицировались ли данные после кэширования.

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

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

6.5. Протоколы непротиворечивости 387

транзакции происходит обнаружение противоречивости. В [151] выделяют три

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

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

данных с той версией, которая хранится на сервере (возможно, реплицируемом).

Транзакция не может работать с кэшированной версией, пока непротиворечи-

вость последней не будет подтверждена.

Второй, оптимистический подход состоит в том, чтобы разрешить проведение

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

что кэшированные данные соответствуют действительности. Если позже окажет-

ся,

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

Третий подход заключается в том, чтобы проверять кэшированные данные

только перед самым подтверждением транзакции. Этот подход сравним со схе-

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

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

с кэшированными данными, надеясь на лучшее. После завершения всей обработ-

ки полученные данные проверяются на непротиворечивость. Если использова-

лись неактуальные данные, транзакция прерывается.

Другой аспект построения протоколов согласования кэша касается страте-

гии

установления

согласованности {coherence enforcement

strategy),

которая опре-

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

мое простое решение

—

вообще запретить кэширование общих данных, а хранить

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

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

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

Очевидно, что такое решение дает лишь незначительный выигрыш в производи-

тельности.

Если разрешить кэширование общих данных, можно предложить два подхо-

да, позволяющих добиться согласованности кэшей. В первом из них сервер при

модификации элемента данных рассылает всем кэшам сообщения о рассогласо-

вании. Второй состоит в простом распространении обновления. В большей части

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

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

сылкой сообщений о рассогласовании и распространением обновлений

[151].

И, наконец, нам следует рассмотреть, что происходит, когда процесс модргфи-

цирует кэшированные данные. Для кэшей, ориентированных только на чтение,

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

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

щих распространение обновлений на кэши. Нередко для этого применяют опи-

санный выше подход, основанный на извлечении данных. В этом случае, когда

клиент обнаруживает, что его кэш устарел, он запрашивает на сервере обновле-

ние.

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

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

Такой подход требует

кэшей сквозной

записи

{write-through

caches),

часто приме-

няемых в распределенных файловых системах. В действительности кэширова-

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

ние со сквозной записью похоже на протокол локальной записи на базе первич-

ной копии, в котором клиентский кэш выступает в роли временного первичного

сервера. Для гарантии непротиворечивости (последовательной) необходимо, что-

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

конфликты двойной записи.

Кэши сквозной записи потенциально дают максимальный выигрыш в произво-

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

ции выполняются локально. Еще одно усовершенствование, которое мы можем

сделать,

—

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

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

приведет нас к так называемому кэшу

обратной

записи (write-back cache), кото-

рый также широко применяется в распределенных файловых системах.

6.6. Примеры

Непротиворечивость и репликация находят применение во множестве распреде-

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

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

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

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

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

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

соким уровнем прозрачности.

Нашим вторым примером станет распределенная база данных, реплики кото-

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

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

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

висимо друг от друга. Во-вторых, он иллюстрирует эффективную реализацию

причинной непротиворечивости при помощи векторных отметок времени. В-треть-

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

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

мы будем рассматривать в следующей главе.

6.6.1.

Огса

—

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

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

мяти, содержащей защищенные объекты [28, 30]. Система Огса состоит из языка

программирования Огса, компилятора и исполняющей системы, которая собст-

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

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

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

другими языками [51, 53]. После знакомства с языком Огса мы .рассмотрим, как

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

гут быть физически разнесены по множеству машин.

6.6. Примеры 389

Язык программирования Огса

в некоторых отношениях Огса

—

это традиционный язык программирования, по-

следовательные инструкции которого несколько напоминают нам язык Modula-2.

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

массивов проверяются во время исполнения программы (кроме той проверки, ко-

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

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

ошибок программирования, таких как неопределенные области в памяти. Осо-

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

ты оптимизации.

Две черты Огса, важные для распределенного программирования,

—

это со-

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

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

операциями

{operations).

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

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

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

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

свойств других объектов, поэтому Огса считается языком на базе объектов, но не

объектно-ориентированным языком.

Каждая операция образует список пар (страж, блок инструкций). Страж

{guard)

—

это логическое выражение без каких-либо сторонних эффектов. Пус-

той страж означает то же самое, что и значение true. При вызове операции все

его стражи вычисляются в определенном порядке. Если все они равны значению

false,

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

стражей не получит значение true. Когда находится страж, вычисление которого

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

ге 6.2 показан объект stack (стек) с двумя операциями, push и pop.

Листинг 6.2. Упрощенный объект stack в Огса с внутренними данными

и двумя операциями

OBJECT IMPLEMENTATION stack;

top:

integer: # переменная, идентифицирующая вершину стека

stack: ARRAY [integer

0..N-1]

OF integer; # память для стека

# Эта функция ничего не возвращает

OPERATION pushCitem: integer);

BEGIN

GUARD top < N DO

stack[lop]:-

item; # поместить элемент в стек

top := top + 1: # инкремент указателя стека

0D;

END;

# Эта функция возвращает целое

OPERATION рорО: integer;

BEGIN

GUARD top > О DO # приостановиться, если стек пуст

top := top- 1: # декремент указателя стека

390

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

RETURN

stack[top];

# вернуть элемент с вершины стека

0D:

END:

BEGIN

top

:= 0: # инициализация

END:

После определения объекта stack могут быть созданы переменные этого типа:

t: stack:

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

top инициализируется нулем. Целая переменная

может быть помещена в стек s

с помощью следующей инструкции:

s$push(k):

Операция изъятия из стека имеет стража, который при попытке достать пере-

менную из пустого стека приостанавливает работу вызвавшего процедуру про-

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

число.

Для создания нового процесса на заданном пользователем процессоре в Огса

предусмотрена инструкция fork. Новый процесс запускает процедуру, имя кото-

рой указано в инструкции fork. В новый процесс можно передавать параметры,

включая объекты. Именно таким образом объекты распределяются по машинам.

Например, следующая инструкция создает по одному новому процессу foobar на

каждой из машин, от

по п:

FOR

1 IN 1 .. п DO FORK foobar(s) ON 1: OD:

Поскольку эти n процессов (включая родительский) выполняются парал-

лельно, все они могут добавлять элементы в общий стек s и извлекать их оттуда,

как если бы они работали на мультипроцессорной CPICTCMC С общей памятью.

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

не существует,

—

это работа исполняющей системы.

Операции над общими объектами атомарны и последовательно непротиворе-

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

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

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

строго последовательно (в некотором неопределенном порядке), при этом ни од-

на операция не начнется до завершения предыдущей.

Операции представляются для всех процессов в одном и тот же порядке. Так,

например, предположим, что мы добавим в объект stack из листинга 6.2 новую

операцию, реек, проверяющую элемент на вершине стека. Тогда в случае, если

два независимых процесса одновременно поместят в стек значения 3 и 4 и все

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

система гарантирует, что каждый из процессов увидит там либо 3, либо 4. Ситуа-

ция, когда часть процессов видит 3, а остальные

—

4, в мультипроцессорной сис-

теме с совместно используемой памятью невозможна. Точно так же невозможна

она и в Огса. Если поддерживается только одна копия стека, этого эффекта до-