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