Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 100
Текст из файла (страница 100)
Позднее, когда он вновь подсоединится к сети, обновления распространятсяс первичного сервера на серверы резервного копирования, вновь приводя хранилище данных в непротиворечивое состояние. Мы вернемся к работе в отключенном от сети состоянии в главе 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) — произвольный набор любых NR ИЛИ более серверов. Соответственно, для модификации файла требуется кворум записи (write quorum),образованный как минимум Nw серверами.
Значения NR и Nw должны удовлетворять следующим двум условиям:NR + Nw> N,Nw>N/2.Первое ограничение используется для предотвращения конфликтов чтениязаписи, а второе — для предотвращения конфликтов двойной записи. Только после того как соответствующее число серверов даст согласие на операцию, файлможно будет прочитать или изменить.Чтобы рассмотреть, как работает алгоритм, взглянем на рис. 6.26, а, на которомNR = 3,3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
