Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 88
Текст из файла (страница 88)
Рассмотрим 120 (5!) последовательностей, которые начинаются с х=1. В половине из них инструкция print(x,z) выполняется раньшеинструкции у=1, а потому нарушают порядок выполнения инструкций программы. Еще у половины инструкция prlnt(x.y) выполняется раньше инструкции z=lи также нарушают порядок выполнения инструкций программы. Только 1/4 из120 последовательностей являются допустимыми (всего 30).
Еще 30 допустимыхпоследовательностей могут начинаться с инструкции у=1 и еще 30 — с инструкции z=l, давая в сумме 90 допустимых последовательностей выполнения инструкций. Четыре из них приведены в табл. 6.2.Таблица 6.2. Четыре варианта допустимых последовательностейвыполнения процессовВариант1ИнструкцииПечатьСигнатурах=1;prlnt(y.z);У=1:prlnt(x.z):z=l;print(x.y):001011001011234х=1:y=l:z=l:print(x.y):print(x.z):x=l:prlnt(y.z);010111110101y=l:x=l:У=1:prlnt(x.z):prlnt(y.z):z=l;prlnt(x.y):101011101011z=l:prlnt(x.z):prlnt(y.z):prlnt(x.y):111111111111В варианте 1 три процесса запускаются в следующем порядке: сначала Р1, посленего Р2, затем РЗ.
В трех других вариантах демонстрируются различные, но также6.2. Модели непротиворечивости, ориентированные на данные341допустимые чередования выражений во времени. В каждом из этих трех процессов печатаются две переменные. Поскольку единственные значения, которые можетпринимать каждая из переменных, — это исходное значение (0) или присвоенноезначение (1), каждый процесс печатает строку из двух битов. Числа в графе «Печать» — тот результат, который появится на устройстве вывода.Если мы объединим результаты работы процессов РУ, Р2 и РЗ в таком порядке, мы получим строку из шести битов, характеризующую частичное чередование инструкций. Эта строка в таблице представлена в графе «Сигнатура».
Нижемы характеризуем каждый из вариантов по его сигнатуре, а не по результатампечати.Не все из 64 сигнатур допустимы. Тривиальный пример: сигнатура 000000 неразрешена, поскольку означает, что инструкции печати выполнены раньше, чеминструкции присваивания, что нарушает требования о выполнении инструкцийв порядке, предусмотренном программой. Более сложный пример — 001001. Первые два бита, 00, означают, что переменные у и z в момент их печати были равнынулю.
Такая ситуация может возникнуть только в том случае, если обе инструкции из процесса Р1 выполняются до начала выполнения процессов Р2 и РЗ. Следуюш;ие два бита, 10, означают, что Р2 выполняется после начала выполнения Р1,но до начала выполнения РЗ.
Последние два бита, 01, означают, что выполнениеРЗ должно закончиться до начала выполнения Р1, но мы уже видели, что процесс Р1 должен выполняться первым. Таким образом, сигнатура 001001 недопустима.Говоря коротко, 90 допустимых последовательностей выполнения инструкций порождают многообразие различных результатов работы программы (ихвсе-таки менее 64), допустимых по условиям последовательной непротиворечивости.
Соглашение между процессами и распределенным хранилищем данных,предназначенным для совместного доступа, состоит в том, что процессы воспринимают все эти результаты как правильные. Другими словами, процессы должнывоспринимать четыре результаты из табл. 6.2 и все остальные допустимые результаты в качестве правильных ответов и корректно работать в случае получения одного из них. Программа, которая работает с какими-то из этих результатов, а другие воспринимает как ошибочные, нарушает соглашение с хранилищемданных и является неправильной.Существуют различные способы формального выражения последовательнойнепротиворечивости (и других моделей). Общий подход изложен в [5, 298].
Каждый процесс Pi имеет ассоциированную с ним реализацию (execution) Ei, котораяпредставляет собой последовательность операций чтения и записи процессом Piзначений из хранилища данных 5. Эта последовательность соответствует порядку, заданному в программе, ассоциированной с процессом Pi,Так, например, реализация четырех процессов, представленных на рис. 6.6, а,может быть задана следующим образом:Е1: W1(x)aЕ2: W2{x)bЕЗ: R3(x)b, R3(x)aЕ4: R4(x)b, R4(x)a342Глава 6. Непротиворечивость и репликацияЧтобы получить относительный порядок, в котором должны исполнятьсяоперации, мы должны объединить строки операций в реализации Ei в единуюстроку Я так, чтобы каждая из операций, входящих в Ei, входила и в Я. Строка Яназывается историей (history).
Интуитивно понятно, что Я описывает очередность операций с точки зрения единого централизованного хранилища. Все допустимые значения Я обязаны следовать двум ограничениям:4^ должен сохраняться такой же порядок выполнения, как и в программе;4^ должно сохраняться соотношение между данными.Первое ограничение означает, что если операция записи или чтения 0Р1 в одной из строк реализации Ei следует перед другой операцией 0Р2, то 0Р1 должнаследовать перед 0Р2 и в истории Я. Если это ограничение для всех пар операцийсоблюдается, то получившаяся история Я не будет содержать операций, нарушающих порядок, заданный программой.Второе ограничение, которое мы будем называть связностью данных (datacoherence), означает, что чтение R(x) некоторого элемента данных х всегда должно возвращать самое недавнее из записанных значений х, то есть значение v, записанное последней перед R(x) операцией W(x)v.
Связность данных проверяется путем выделения каждого элемента данных и последовательности операций сним. Прочие данные при этом остаются без внимания. В противоположностьэтому, при проверке непротиворечивости внимание обращается на операции записи различных элементов данных и их порядок. Если мы рассматриваем совместно используемую память и локализацию в памяти, не обращая внимания наэлементы данных, такой случай связности данных называется связностью памяти (memory coherence).Возвращаясь к четырем процессам, представленным на рис. 6.6, а, допустимым значением истории Я для них может быть следующая строка:Я = W1(x)b,R3(x)b,R4(x)b,W2(x)a,R3(x)a,R4(x)a.С другой стороны, для исполнения четырех процессов, представленных нарис.
6.6, б, невозможно найти разрешенной истории, поскольку в последовательно непротиворечивой системе невозможно сделать так, чтобы процесс РЗ сначала выполнял операцию R3(x)b, а затем — операцию R3(x)a, в то время как процесс R4 считывает значения аи b в обратном порядке.Более сложным примером могут быть несколько допустимых значений Я.Поведение программы будет считаться правильным, если ее последовательностьопераций соответствует одному из разрешенных значений Я.Хотя последовательная непротиворечивость и дает удобную для программистов модель, она имеет серьезные проблемы с производительностью.
В [268]было доказано, что при времени чтения г, времени записи w и минимальном времени передачи пакета между узлами t всегда выполняется условие г + w>t. Другими словами, для всякого последовательно непротиворечивого хранилища изменение протокола для увеличения скорости чтения вызывает падение скоростизаписи, и наоборот.
По этой причине исследователи принялись за поиск новых,еще более слабых моделей. В следующем пункте мы рассмотрим некоторыеиз них.6.2. Модели непротиворечивости, ориентированные на данные3436.2.3. Причинная непротиворечивостьМодель причинной непротиворечивости {causal consistency) [208] представляетсобой ослабленный вариант последовательной непротиворечивости, при которойпроводится разделение между событиями, потенциально обладающими причинно-следственной связью, и событиями, ею не обладающими. Мы уже говорили опричинно-следственной связи в предыдущей главе, когда обсуждали векторныеотметки времени.
Если событие В вызвано предшествующим событием А или находится под его влиянием, то причинно-следственная связь требует, чтобы всеокружающие наблюдали сначала событие Л, а затем В.Рассмотрим пример с памятью. Предположим, что процесс Р1 записываетзначение переменной х. Таким образом, чтение х и запись у будут потенциальносвязаны с этим процессом причинно-следственной связью, поскольку вычисление у может зависеть от значения х, которое прочтет Р2 (то есть от значения, записанного процессом Р1). С другой стороны, если два процесса спонтанно и одновременно записывают значения двух различных переменных, они не могутиметь причинно-следственную связь.
Когда за записью следует чтение, эти двасобытия потенциально имеют причинно-следственную связь. И вообще, чтениесвязано с записью, которая предоставляет данные для этого чтения, причинноследственной связью. Операции, не имеющие причинно-следственной связи, называются параллельными {concurrent).Для того чтобы хранилище данных поддерживало причинную непротиворечивость, оно должно удовлетворять следующему условию: операции записи,которые потенциально связаны причинно-следственной связью, должны наблюдаться всеми процессами в одинаковом порядке, а параллельные операции записимогут наблюдаться на разных машинах в разном порядке.В качестве примера рассмотрим рис.
6.7. На нем представлена последовательность событий, возможная для хранилища с причинной непротиворечивостью,но запрещенная для хранилищ со строгой или последовательной непротиворечивостью. Стоит отметить, что W2{x)b и W1{x)c — параллельные операции, и поэтому их очередность для различных процессов не важна.Р1: W(x)aР2:РЗ:Р4:W(x)cR(x)aR(x)aR(x)aW(x)bR(x)cR(x)bR(x)bR(x)cРис. 6.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
