Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 76
Текст из файла (страница 76)
Получив г, Pk проверяет отметку времени vt(r) и решает отложить доставку до того момента, пока не будут приняты все сообщения,которые по соображениям причинности идут перед г. Если подробнее, сообщение г будет доставлено только в случае выполнения двух условий:> vt(r)U] = Vklj] + 1.> vt(r)[I] < Vk[i] для всех zVj.Первое условие означает, что г — следующее сообщение, получаемое Pk отпроцесса Pj. Второе условие означает, что Pk видит все те же сообщения, которыевидел процесс Pj, отправляя сообщение г. В частности, это означает, что процесс Pkуже получил сообщение а.292Глава 5.
СинхронизацияЗамечание по упорядоченной доставке сообщенийНекоторые системы промежуточного уровня, например ISIS и ее преемницаHorus [54], предоставляют поддержку полностью упорядоченной и упорядоченной в плане причинности (надежной) групповой рассылки. В свое время шлиспоры о том, должна ли эта поддержка быть реализована как часть уровня обменасообщениями или упорядочиванием должны заниматься приложения (см., к примеру, [59, 99].В том чтобы поручить выяснение очередности сообщений уровню обмена сообщениями, имеется две основные проблемы.
Во-первых, поскольку уровень обмена сообщениями не знает, что на самом деле содержится в сообщениях, возможен учет лишь потенциальной причинности. Так, например, два сообщения отодного отправителя, абсолютно независимые, на уровне обмена сообщениямивсегда будут считаться имеющими причинно-следственную связь. Подобный подход слишком ограничен и может привести к проблемам с эффективностью.Вторая проблема состоит в том, что не всякую причинно-следственную связьудается выявить. Рассмотрим еще раз службу новостей. Представим себе, чтоАлиса написала письмо. Если затем она позвонит Бобу и обсудит с ним написанное, Боб может написать ей в ответ другое письмо, не читая послания Алисыв группе новостей. Другими словами, между письмом Боба и письмом Алисы имеется причинно-следственная связь, обусловленная внешним взаимодействием.Такая причинно-следственная связь не выявляется системой сетевых новостей.В сущности, вопросы упорядочивания, как и множество других вопросов связи, относящихся к приложению, могут в достаточной мере быть решены путемрассмотрения приложений, с которыми осуществляется взаимодействие.
Это явление [393] известно в проектировании систем под названием сквозного аргумента{end-to-end argument). Оборотная сторона опоры исключительно на решенияприкладного уровня — в том, что разработчик вынужден сосредоточиваться навопросах, которые не относятся непосредственно к базовой функциональностиприложения. Так, например, упорядочение может не быть важнейшей проблемой при разработке системы сообщений, например, сетевых новостей. В этомслучае наличие базового уровня передачи данных, обслуживающего упорядоченность, может оказаться весьма кстати. Мы еще не раз вернемся к сквозным аргументам, в частности, при рассмотрении вопросов безопасности в распределенных системах.5.3.
Глобальное состояниеВо многих случаях полезно знать глобальное состоянию, в соответствии с которым распределенная система функционирует в данное время. Глобальное состояние {global state) распределенной системы включает в себя локальные состояниякаждого процесса вместе с находящимися в пути сообщениями (то есть посланными, но еще не доставленными). Что именно считать локальным состояниемпроцесса, зависит от того, что нас интересует [197]. В случае распределенной базы данных в него могут входить только те записи, из которых складывается часть2935.3. Глобальное состояниебазы данных, а временные записи, используемые для вычислений, можно исключить.
В нашем примере сборки мусора путем трассировки, который рассматривался в предыдущей главе, локальное состояние могло бы состоять из переменных, представляющих метки для тех заместителей, скелетонов и объектов,которые содержатся в адресном пространстве процесса.Знание глобального состояния распределенной системы может быть полезнопо многим причинам. Так, например, если известно, что локальные вычисленияпрекратились и ни одного сообщения в пути нет, ясно, что система перешла в состояние прекращения всяческой деятельности. Анализируя глобальное состояние, можно заключить, что мы либо зашли в тупик [71], либо распределенныевычисления были корректно завершены.
Пример такого анализа рассматривается ниже.В простом способе непосредственный записи глобального состояния распределенной системы, предложенном в [89], вводится понятие распределенногоснимка состояния {distributed snapshot), отражающего состояние, в котором находилась распределенная система. Важным его свойством является то, что он отражает непротиворечивое глобальное состояние. В частности, это означает следующее: если в снимке записано, что процесс Р получил сообщение от процесса Q, тотам также должно быть записано, что процесс Q послал это сообщение. В противном случае снимок состояния содержал бы записи о сообщениях, которые были приняты, но никогда никем не посылались.
Тем не менее допустима обратнаяситуация, когда процесс Q послал сообщение, а процесс Р его еще не получил.Противоречивый срезНепротиворечивый срезW\Р1m^/время 1\WР1тЗР2m1Р2/11\N.^-ч^рЗ/-^^^т2РЗ //УВремя-'--.-^^^^^^"-^2РЗ/Отправителя сообщения т 2по этому срезу определить невозможноабРис. 5.9. Непротиворечивый срез (а). Противоречивый срез (б)Понятие глобального состояния может быть представлено графически припомощи так называемого среза {cut). На рис. 5.9, а непротиворечивый срез, показанный пунктирной линией, пересекает оси времени трех процессов — Р1, Р2иРЗ. Срез отражает последнее записанное событие для каждого из процессов.В этом случае мы можем легко убедиться, что для всех записей о пришедших сообщениях зафиксированы соответствующие события их отправки.
В противоположность этому на рис. 5.9, б показан противоречивый срез. Приход сообщеният2 в процесс РЗ был записан, но в снимке состояния не зафиксировано соответствующего события его отправки.294Глава 5. СинхронизацияДля упрощения объяснения алгоритма создания распределенного снимка состояния мы предположим, что распределенную систему можно представить в виде набора процессов, соединенных друг с другом посредством однонаправленныхпрямых коммуникационных каналов. Так, например, процессы могут на первомэтапе взаимодействия устанавливать соединения TCP.Инициировать алгоритм может любой процесс. Инициировавший получениераспределенного снимка состояния процесс, скажем Р, начинает с записи собственного локального состояния.
Затем он посылает маркер по каждому из своихисходящих каналов, давая понять, что получатель этого сообщения должен принять участие в записи глобального состояния.Когда процесс Q получает из входящего канала С маркер, все зависит от того,записал он уже свое локальное состояние или нет. Если нет, он сначала записывает свое локальное состояние, а затем также рассылает маркеры по всем исходящимканалам. Если же Q уже записал свое состояние, маркер, пришедший из канала С, показывает, что Q должен записать состояние канала. Это состояние складывается из последовательности сообщений, которые были приняты процессом Qс момента записи им своего локального состояния и до прихода маркера. Записьэтого состояния иллюстрирует рис.
5.10.МаркерF ~ ~ ^ Локальная^'**-—^ файловаясистемаНТКЕНёН Q-DOQHЩШЦНЕЕLUEEEЗаписанноесостояниеРис. 5.10. Организация процесса и каналов в распределенном снимке состояния (а).Процесс О получает маркер впервые и записывает свое локальное состояние (б).Процесс О записывает все входящие сообщения {в).Процесс О получает маркер из входящего канала и заканчивает записьсостояния входящего канала (г)Процесс сообщает о том, что он закончил свою часть алгоритма, после получения и обработки маркера от каждого из своих входящих каналов. В этот момент записанное локальное состояние, а также состояние, записанное для каждого из входящих каналов, собираются вместе и посылаются, например, процессу,инициировавшему создание снимка состояния.
Последний может затем проана-5.3. Глобальное состояние295лизировать текущее состояние. Отметим, что тем временем распределенная система в целом продолжает работать обычным образом.Следует отметить, что поскольку алгоритм может быть инициирован любымпроцессом, одновременно может создаваться несколько снимков состояния. Поэтому маркер должен иметь идентификатор (а возможно, и номер версии) процесса, который инициировал алгоритм. Только после того, как процесс получитэтот маркер по всем входным каналам, он может закончить построение своейчасти ассоциированного с маркером снимка состояния.Пример — определение момента завершенияВыяснив, как приложение получает снимок состояния, рассмотрим, как определить момент завершения распределенных вычислений.
Если процесс Q получаетмаркер, запрашиваюгций снимок состояния, в первый раз, он рассматривает процесс, приславший этот маркер, как предшественника. Когда Q завершает созданиесвоей части снимка состояния, он посылает своему предшественнику сообщениеГОТОВО. Рекурсивным образом, когда инициатор создания распределенногоснимка состояния получает сообщения ГОТОВО от всех своих преемников, онзнает, что снимок состояния полностью готов.Однако снимок состояния может показать глобальное состояние, в которомсообщения еще находятся в пути.
В частности, представим себе записи процессао том, что он получил сообщение по одному из своих входящих каналов в периодмежду записью локального состояния и получением маркера из этого канала.Ясно, что мы не можем сделать заключения об окончании распределенных вычислений, поскольку это сообщение может породить новые сообщения, которыеуже не будут частью снимка состояния.Нам нужно получить снимок состояния со всеми пустыми каналами. Соответствующая несложная модификация алгоритма описывается ниже. Когда процесс Q заканчивает создание своей части снимка состояния, он посылает предшественнику либо сообщение ГОТОВО, либо сообщение ПРОДОЛЖИТЬ. СообщениеГОТОВО возвращается только в том случае, если выполнены условия:4 все предшественники Q вернули сообщение ГОТОВО;4^ между записью своего состояния и получением маркера процесс Q не принимал сообщений ни по одному из своих входящих каналов.Во всех прочих случаях процесс Q посылает предшественнику сообщениеПРОДОЛЖИТЬ.Существенно, что инициатор создания снимка состояния, скажем, процесс Р,может получать от каждого из своих преемников либо сообщение ПРОДОЛЖИТЬ,либо сообщение ГОТОВО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
