Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 101
Текст из файла (страница 101)
NW =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].Кворум чтения(АВI C )D1AII EFGHIIJКL 1IINR = 3.NW=10II/JNR = 7,кNW = 6LIВСD'E©GH1JКL ^NR=1.Nw=12Кворум записиaРис. 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.Однако это язык с защитой типов, без указателей и без псевдонимов. Границымассивов проверяются во время исполнения программы (кроме той проверки, которая может производиться в ходе компиляции).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
