Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 75
Текст из файла (страница 75)
Сообщение С от процесса 2 процессу 1 будет послано на отметке 60 и достигнет цели на отметке 56.Сообщение D от процесса 1 процессу О будет послано на отметке 64 и достигнетцели на отметке 54. Эти цифры абсолютно невозможны. Это та ситуация, которую мы должны предотвратить.Решение, найденное Лампортом, прямо вытекает из отношения «происходитраньше». Поскольку С посылается на отметке 60, оно должно достичь цели наотметке 61 или позднее. Поэтому каждое сообщение содержит время отправкипо часам отправителя.
Когда сообщение достигает цели, но часы получателя по-288Глава 5. Синхронизацияказывают время, более раннее чем время отправки, получатель быстро подводитсвои часы так, чтобы они показывали время на единицу большее времени отправки. На рис. 5.7, б мы видим, что теперь сообщение С приходит на отметке 61.Таким же образом сообщение D приходит теперь на отметке 70.С одним небольшим дополнением этот алгоритм удовлетворяет нашим требованиям по глобальному времени.
Это добавление состоит в том, что между любыми двумя событиями часы должны «протикать» как минимум один раз. Еслипроцесс посылает или принимает в коротком сеансе два сообщения, он долженсделать так, чтобы его часы успели протикать один раз (как минимум) в промежутке между сообщениями.В некоторых случаях желательно удовлетворять дополнительному требованию: никакие два сообщения не должны происходить одновременно. Чтобы выполнить это требование, мы можем добавить номер процесса, в котором происходятсобытия, справа от метки времени и отделить его от целой части десятичной точкой.
Таким образом, если в процессах 1 и 2 в момент времени 40 происходят события, то первый из них будет происходить в 40.1, а второй в 40.2.Используя этот способ, мы получаем возможность указания времени для всехсобытий в распределенной системе, подпадающих под перечисленные ниже условия.4 Если а происходит раньше b в одном и том же процессе, то С(а)<С(Ь),4- Если аи b представляют собой отправку и получение сообщения, соответственно С(а)<С(Ь),4^ Для всех различимых событий аиЬ выполняется соотношение С(а) ^ С(Ь).Этот алгоритм дает нам возможность полностью упорядочить все событияв системе.
В отличие от этого множество других распределенных алгоритмов дляустранения неясностей требуют упорядоченности, так что этот алгоритм широкоцитируется в литературе.Пример — полностью упорядоченная групповая рассылкав качестве области приложения алгоритма Лампорта рассмотрим ситуацию, когда необходима репликация базы данных на нескольких сайтах. Например, дляповышения производительности запросов банк может разместить копию базыданных по счетам в двух разных местах, скажем в Нью-Йорке и Сан-Франциско.Запросы всегда пересылаются к ближайшей копии.
Ценой быстрого ответа на запрос отчасти являются высокие затраты на обновление, поскольку каждая операция обновления должна быть передана каждой из реплик.На самом деле в отношении изменений существуют более точные требования.Предположим, клиент в Сан-Франциско хочет добавить $100 на свой счет, накотором в настоящее время лежит $1000.
В то же самое время сотрудник банка вНью-Йорке начинает обновлять счета пользователей, увеличивая сумму на нихна процент по вкладу — 1 %. Оба изменения должны быть внесены в обе копиибазы данных. Однако из-за задержек в базовой сети передачи данных обновления могут дойти в ином порядке (рис. 5.8).5.2. Л о г и ч е с к и е часыОбновление 1выполняется раньше,чем обновление 2Реплицированнаябаза данных289Обновление 2выполняется раньше,чем обновление 1Рис. 5.8.
Обновление реплицированной базы данных, после которогоона приходит в противоречивое состояниеПользовательская операция обновления будет выполнена в Сан-Францискораньше обновления для начисления процентов. В Нью-Йорке же наоборот, копия счета клиента будет обновлена после получения одного процента прибыли,а уж после этого по ней будет проведена операция с депозитом в $100. Соответственно, база данных в Сан-Франциско будет иметь общую сумму счета $1,111,а база данных в Нью-Йорке — $1,110.Проблема, с которой мы столкнулись, состоит в том, что две операции обновления должны быть выполнены в одинаковом порядке в каждой из копий. Хотяочередность обработки разная, с точки зрения непротиворечивости она абсолютно не важна. Важно, чтобы обе копии были абсолютно одинаковыми. Обычно такого рода ситуации требуют полностью упорядочетюй групповой рассылки{totally-ordered multicasting), то есть такой операции групповой рассылки, при которой все сообщения доставляются всем получателям с одинаковой очередностью.
Для реализации такой рассылки абсолютно распределенным методом могут использоваться отметки времени Лампорта.Рассмотрим группу процессов, посылающих друг другу сообщения путемгрупповой рассылки. Каждое из сообщений всегда имеет отметку времени с текущим временем (логическим) отправителя. Если сообщение передается путемгрупповой рассылки, оно по идее приходит также и отправителю. Кроме того,мы предполагаем, что сообщения каждого из отправителей принимаются в томпорядке, в котором они посылались, и что ни одно сообщение не теряется.Когда процесс принимает сообщение, оно попадает в локальную очередь в порядке, определяемом отметкой времени.
Получатель рассылает групповое подтверждение остальным процессам. Заметим, что если для корректировки локальных часов мы используем алгоритм Лампорта, отметка времени на полученномсообщении должна быть меньше, чем на подтверждении.Интересный аспект такого подхода состоит в том, что все процессы будутиметь одну и ту же копию локальной очереди. Каждое сообщение рассылаетсявсем процессам, включая подтверждения, а предполагает ответ от всех процессов. Напомним также, что мы решили, что сообщения принимаются в порядке ихотправки. Каждый процесс помещает полученное сообщение в свою локальнуюочередь в соответствии с отметкой времени на этом сообщении. Часы Лампортагарантируют, что никакие два сообщения не могут иметь одинаковую отметкувремени, а также то, что отметки времени отражают общий порядок сообщений.290Глава 5.
СинхронизацияПроцесс может доставить поставленное в очередь сообщение приложению, которое работает, только если это сообщение находится на вершине очереди и егополучение подтверждено всеми остальными процессами. В этот момент сообщение удаляется из очереди и обрабатывается приложением, а соответствующиеему подтверждения просто удаляются. Поскольку каждый процесс имеет такуюже копию очереди, все сообщения доставляются повсюду в одинаковом порядке.Другими словами, мы создали полностью упорядоченную групповую рассылку.5.2.2.
Векторные отметки времениОтметки времени Лампорта приводят к ситуации, когда все события в распределенной системе имеют единую последовательность, такую, что если событие апроисходит раньше события 6, то а оказывается перед /?, то есть С{а) < С(Ь).Однако при помощи отметок времени Лампорта ничего нельзя сказать о взаимосвязи между двумя сообщениями аи Ь, просто сравнивая их временные отметки,соответственно С(а) и С{Ь). Другими словами, если С(а) < С{Ь), это не обязательно означает, что события а действительно произошло раньше, чем Ь. Для этого необходимо что-то еще.Чтобы понять это, рассмотрим систему рассылки сообщений.
Один из наиболее популярных примеров подобной системы сообщений — это служба электронных досок сообщений в Интернете, сетевые новости (например, описанныев [110]). Пользователи, а следовательно, процессы, выбирают определенные дискуссионные группы. Послания в такую группу, будь то письма или реакция надругие письма, рассылаются групповой рассылкой всем членам группы. Чтобыгарантировать, что ответы присылаются после писем, на которые в них отвечали,мы можем попытаться использовать описанную выше схему полностью упорядоченной групповой рассылки.
Однако эта схема не означает, что если сообщение В пришло после сообщения Л, значит, В представляет собой отклик на то,что было послано в сообщении А. На самом деле они могут быть абсолютно независимыми друг от друга. Полностью упорядоченная групповая рассылка слишком строга для этого случая.Проблема состоит в том, что отметки времени Лампорта не в состоянии уловить причинно-следственную связь. В нашем примере получение письма из соображений причинно-следственной связи всегда предваряет отсылку ответа нанего. Соответственно, если в группе процессов поддерживаются отношения причинно-следственной связи, то получение ответа на письмо всегда должно следовать за получением этого письма.
Не более, но и не менее. Если два письма илиответы на них независимы друг от друга, порядок их получения обычно неважен.Причинно-следственная связь может быть соблюдена посредством векторныхотметок времени (vector timestamps). Векторная отметка времени VT{d) присвоенная событию а, имеет следующее свойство: если VT{d) < VT(b) для события 6,значит, событие а является причинно предшествующим событию Ь. Векторныеотметки времени создаются путем приписыванию каждому процессу Р, вектора Vuс перечисленными ниже свойствами.5.2.
Логические часы291^ V^[/] — это число событий, которые произошли с процессом Р, к настоящему времени.> Если Vi[j] = ky то процесс Р/ знает, что с процессом Р, произошло k событий.Первое свойство поддерживается путем увеличения У, [г] на единицу при каждом новом событии, происходящем в процессе Ру. Второе свойство поддерживается вложением векторов в посылаемые сообщения.
Так, когда процесс Р/ посылает сообщение т, он пересылает вместе с ним и его текущий вектор как отметкувремени vt.Таким образом, получатель оказывается информированным о номере сообщения, которое вызвало активность процесса Р/. Более важно, однако, что получатель уведомляется о том, сколько сообщений от других процессов должны прийти к нему до того момента, как процесс Р, послал ему сообщение т. Другимисловами, отметка времени vt в сообщении т говорит получателю, сколько событий в других процессах должны предварять т и с каким из них у сообщения тможет быть причинно-следственная связь.
Когда процесс Pj получает т, это побуждает его установить каждый элемент Vj[k] в собственном векторе в max{Vj[k], vt[k]}.Вектор теперь отражает число сообщений, которые должен получить процесс Р/и которые, как он видел, предшествовали посылке т. Затем элемент Vj[i] увеличивается на единицу, отражая факт получение сообщения ш, как следующего сообщения от процесса Р, [374].Векторная отметка времени может использоваться для доставки сообщенийтолько без нарушения причинно-следственной связи.
Рассмотрим далее примерс электронной доской объявлений. Когда процесс Р, отправляет письмо, он осуществляет множественную рассылку этого письма в виде сообщения а с пометкой времени vt(a), равной Vi. Когда другой процесс, Pj, получает а, он исправляетсвой собственный вектор, устанавливая Vj[i] > vt(a)[i].Допустим теперь, что Pj посылает ответ на это письмо. Он делает это посредством множественной рассылки сообщения г с отметкой времени vt(r)y равной Vj.Отметим, что vt(r)[i] >vt(a)[i].
Если считать связь надежной, оба эти сообщения — а, содержащее письмо, и г, содержащее ответ, — в конце концов достигнутдругого процесса, Pk. Поскольку мы не делали никаких предположений относительно очередности доставки сообщений, сообщение г может прийти процессу Pkраньше, чем сообщение а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
