Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 104
Текст из файла (страница 104)
Точно так же WORK{i)[j] отражаетобщее число обновлений, присланных с Lj, которые должны быть выполнены,чтобы очередь записи стала пустой.Кроме этих двух векторов отметок времени каждый клиент отслеживает текущее состояние хранилища данных. Для этого клиент С поддержршает векторотметок времени LOCAL(C), где LOCAL(C)[i] устанавливается равным последнему значению состояния i/, которое видно из С.
(Отметим, что клиент, производя чтение или запись, каждый раз контактирует с разными репликами.) Каждый раз, когда клиент С пересылает запрос на чтение или запись 7?1У локальнойкопии, в качестве отметки времени DEP(RW) он выставляет LOCAL(C), чтобыпоказать, от чего зависит RW.Выполнение операций чтенияТеперь самое время описать, как происходят различные операции. Сначала мысосредоточимся на операции чтения, различные этапы которой иллюстрируетрис. 6.29. Очередность здесь следующая.1. Присваивание DEP(R):=LOCAL(C).2.
Проверка DEP(R)<VAL(i).3. Передача данных и значения VAL(i).4. Присваивание LOCAL(C):=max{LOCAL(C), VAL(i)}.Когда клиент С (в нашем случае, внешний интерфейс) хочет произвести операцию чтения 7?, отметка времени DEP(R) соответствующего запроса на чтениеустанавливается равной LOCAL(C). Эта отметка времени отражает тот факт, что6.6. Примеры397клиент постоянно знает о хранилище данных. После этого запрос передается одной из копий.Очередь3Реплика!Рис.
6.29. Выполнение операции чтения локальной копииВходящий запрос на чтение R к копии L всегда помещается в очередь на чтение этой копии. Отметка времени DEP(R) отражает глобальное состояние хранилища данных в тот момент времени, когда был послан запрос R. Для обработки Rнеобходимо, чтобы локальная копия Lf также была осведомлена об этом состоянии. Так, в частности, для каждого значения j справедливо DEP(R)[j] < VAL(i)lj].Как только операция чтения будет произведена, копия Li возвращает значение запрошенного элемента данных клиенту вместе с VAL(i), После этого клиентприводит в соответствие с ним свой собственный вектор LOCAL(C), устанавливая каждый из его элементов LOCAL(C)[j] в max{LOCAL(C)[j], VAL(i)[j]}.Выполнение операций записиВыполнение операций записи происходит более или менее аналогично операциям чтения, как показано на рис.
6.30. Очередность этапов выполнения здесь следующая.1. Присваивание D£'P(W^):=I0C4I(C).2. Присваивания WORK(i)[i]:-=WORK(i)[i]-^l, ts(W)[i]:=WORK(i)[i\и ts(W)[i]:-DEP(W)[Jl3. Передача отметки времени z^5(W).4. Присваивание LOCAL(C):=^max{LOCAL(C), ts(W)}.5. Проверка DEP(W) < VAL(i).Когда клиент С собирается выполнить операцию записи, он посылает запросна запись копии if, устанавливая отметку времени DEP(W) равной своему локальному вектору LOCAL(C)y как и в прошлый раз.Когда копия получает запрос на запись W от клиента, она увеличиваетWORK(i)[i], оставляя прочие элементы неизменными. Кроме того, в ответ на запрос на запись Li возвращает отметку времени ts(W), где /:5(W)[z] равноWORK(i)[i]y а другие элементы ts(W)[;] получили значения DEP(W)\j]. Эта отметка времени посылается клиенту как подтверждение, после чего клиент приводит в соответствие с ним собственный вектор LOCAL(C), устанавливая каждый k-й его элемент LOCAL(C)[k] в значение max{LOCAL(C)[k]i ts(W)[k]}.398Глава 6.
Непротиворечивость и репликацияКлиентРеплика iРис. 6.30. Выполнение операции записи локальной копииКак и в случае запроса на чтение, запрос на запись W выполняется, только если локальная копия Li произвела все обновления, от которых зависит W. Это тотслучай, когда для каждого элемента DEP(W)[j] < VAL(i)[j]. В этом случае операция производится и вектор VAL(i) настраивается путем присваивания каждомуj-uy элементу значения max{VAL(i)[j], ts(W){j]}. Поскольку вектор WORK{i)[i]увеличился на единицу, когда запрос 1^ был получен копией 1„ а затем получилзначение метки г^5(1У)[/], мы легко убедимся, что запрос W обрабатывается копией Li при выполнении следующих двух условий:ts(W)[i]-VAL(i)[t] + 1,^5(W^)[;] < VAL(i)[j] для всех; J^ iПервое условие гласит, что должны быть выполнены все операции, посланные напрямую копии if от других клиентов и предшествующие операции записи W.
Второе условие говорит о том, что все обновления, от которых зависит запись Wy также должны быть выполнены на Li. Отметим, что эти два условия полностью аналогичны условиям реализации причинной доставки сообщений, которая обсуждалась в предыдущей главе.Выполненные операции остаются в очереди, но никогда не выполняются снова.Они сохраняются в очереди потому, что может потребоваться распространить ихдля выполнения другим копиям. Это распространение обновлений обсуждаетсядалее.Распространение обновленийЧтобы закончить тему обработки операций, нам следует обсудить распространение операций обновления среди различных копий.
Распространение обновленийвыполняется при помощи антиэнтропийных методов, о которых мы упоминали,когда обсуждали эпидемические протоколы. Время от времени копия L^ связывается с другой копией Lj и обменивается с ней операциями, содержащимися в очередях на запись обеих копий.Если говорить более конкретно, когда копия Li связывается с другой копией Lj,она пересылает ей все сообщения, содержащиеся в ее очереди на запись. Крометого, копии Lj пересылается векторная отметка времени WORK(i). В свою очередь, Lj подстраивает свой собственный вектор WORK(j), устанавливая каждый6.7.
Итоги399к'И элемент равным max{WORK(i)[k], WORK(j)[k]}. Далее Lj включает операциизаписи, полученные от i,, в свою очередь на запись. Если операция 1^уже содержится в очереди Lj, она просто отбрасывается. В противном случае 1^ добавляется в очередь.После обмена обновлениями копия L/ просматривает, какие из полученныхею операций могут быть выполнены. Обозначим через U набор всех отложенныхопераций записи W, для которых для каждого ^-го элемента соблюдается условие DEP(W)[k] < VAL(i)[k].
Копия Z„ соответственно, выбирает операцию W\ независящую от любой другой операции записи в наборе U. Другими словами, в Uнет больше такой операции W, для которой для каждого k-то элемента выполняется условие DEP(W)[k] < DEP(W')[k]. После этого операция 1У удаляется из Uи выполняется. Затем в наборе U выбирается следующая операция.Существует еще множество нюансов, оставшихся «за кадром». Важно то, чтосогласно приведенному описанию, очереди записи могут разрастись бесконечно.Понятно, что операция должна удаляться из очереди сразу же, как только мы определили, что она выполнена всеми копиями.
Чтобы определить этот момент,необходимо дополнительное администрирование и обмен дополнительной информацией. Детали можно найти в [246].6.7. ИтогиСуществует два основных довода в пользу реплицирования данных — повышение надежности распределенных систем и увеличение их производительности.Репликация порождает проблему противоречивости: при обновлении одной изреплик она становится отличной от остальных. Для сохранения непротиворечивости реплик нам необходимо распространять обновления так, чтобы временнаяпротиворечивость оставалась незаметной.
К сожалению, это может значительноснизить производительность, особенно в крупных распределенных системах.Единственное решение этой проблемы — посмотреть, нельзя ли немного ослабить требования к непротиворечивости. В моделях строгой непротиворечивостинепротиворечивость определяется для отдельных операций чтения и записи совместно используемых данных. Можно провести разделение этих моделей настрогую непротиворечивость, последовательную непротиворечивость, линеаризуемость, причинную непротиворечивость и непротиворечивость FIFO.Строгая непротиворечивость предполагает, что операции чтения всегда возвращают последнее записанное значение. Из-за нереальности поддержки глобального времени в распределенных системах реализация строгой непротиворечивости невозможна.
Последовательная непротиворечивость и линеаризуемость,в сущности, имеют ту же семантику, которая используется программистами в параллельном программировании: все операции записи должны наблюдаться отовсюду в одинаковом порядке. Линеаризуемость — немного более строгая модель,она упорядочивает операции в соответствии с глобальными часами (с конечнойточностью).Причинная непротиворечивость отражает тот факт, что операции, потенциально зависящие друг от друга, происходят в порядке, определяемом этой зави-400Глава 6. Непротиворечивость и репликациясимостью. Непротиворечивость FIFO просто определяет, что операции одногопроцесса происходят в порядке, определяемом этим процессом.Модели слабой непротиворечивости относятся к последовательностям операций чтения и записи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
