Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 93
Текст из файла (страница 93)
Позже он снова начал работать с базой данных, возможно,после перемещения в другое место или с другого устройства доступа. В этот момент пользователь может подсоединиться к другой нежели раньше реплике, чтои показано на рисунке. Однако если изменения, сделанные в базе данных раньше, еще не распространены на эту реплику, пользователь обнаружит противоре-358Глава 6. Непротиворечивость и репликациячивость данных в базе данных.
В частности, он будет ожидать увидеть сделанныераньше изменения, а вместо этого обнаружит, что ничего не изменилось.Этот пример типичен для потенциально непротиворечивых хранилищ данныхи вызван тем, что пользователь может иногда работать с различными репликами.Острота проблемы снижается путем введения пепротиворечивосши, ориентированной на клиента {client-centric consistency). По существу, непротиворечивость,ориентированная на клиента, предоставляет одному клиенту гарантии непротиворечивости при доступе к хранилищу данных. Относительно параллельногодоступа других клиентов никаких гарантий не предоставляется.Моделям непротиворечивости, ориентированным на клиента, дала начало работа над Bayou [453, 454] — системой управления базами данных, разработанной для мобильных вычислений.
В этой системе предполагается, что сетевыеподключения ненадежны и имеют различные проблемы с производительностью.В эту категорию попадают беспроводные сети и глобальные сети, такие как Интернет.В системе Bayou различают четыре основных модели непротиворечивости.Для рассмотрения этих моделей мы вновь обсудим хранилище данных, распределенное по нескольким машинам. Когда процесс получает доступ к хранилищуданных, он обычно связывается с локальной (или ближайшей) копией, хотя впринципе подойдет любая копия. Все операции чтения и записи осуществляются с локальной копией. Изменения постепенно распространяются и на другиекопии.
Для простоты примем, что элементы данных имеют ассоциированного сними владельца, которым является единственный процесс, имеющий право изменять их. Таким образом, мы избежим конфликтов двойного чтения.Модели непротиворечивости, ориентированные на клиента, описываются с использованием следующей нотации. Пусть Xi[t] означает версию элемента данных хна локальной копии 1, в момент времени t. Версия Xi[t\ — результат серии операций записи, произведенных в i, после инициализации.
Мы обозначим эту сериюкак W5(Xj[^]). Если операции из серии ^^^(^/[^i]) были также произведены в локальной копии Lj в более позднее время ^2, мы запишем это как W5(X,[^i];X/[^2])Если временная очередность операций будет ясна из контекста, мы будем опускать индекс у символа времени.6.3.2. Монотонное чтениеПервая из моделей непротиворечивости, ориентированная на клиента, — монотонное чтение. Хранилище данных обеспечивает непротиворечивость монотонногочтения (monotonic-read consistency)^ если удовлетворяет следующему условию:если процесс читает значение элемента данных х, любая последующая операциячтения х всегда возвращает то же самое или более позднее значение.Другими словами, непротиворечивость монотонного чтения гарантирует, чтоесли процесс в момент времени t видит некое значение х, то позже он никогда неувидит более старого значения х.В качестве примера применения монотонного чтения рассмотрим распределенную базу данных электронной почты.
В этой базе данных почтовый ящик каж-6.3. Модели непротиворечивости, ориентированные на клиента359дого пользователя может быть распределен по нескольким машинам и реплицирован. Корреспонденция добавляется в почтовые ящики всех реплик. Однакоизменения распространяются медленно (по запросу). Данные пересылаются копии базы только в том случае, когда эти данные нужны этой копии для поддержания непротиворечивости.
Представим себе, что пользователь читает свою почту в Сан-Франциско. Допустим, что чтение почты не оказывает воздействия напочтовый ящик, то есть сообщения не удаляются, не сохраняются во вложенныхкаталогах, не помечаются как прочитанные и т. п. Когда пользователь после этого улетает в Нью-Йорк и снова открывает свой почтовый ящик, непротиворечивость монотонного чтения гарантирует, что сообщения, которые он видел в своем почтовом ящике в Сан-Франциско, он увидит в своем почтовом ящике и вНью-Йорке.Если использовать нотацию, похожую на ту, которая применялась для описания непротиворечивости, ориентированной на данные, непротиворечивость монотонного чтения может быть графически представлена так, как показано на рис.
6.14.Вдоль вертикальной оси располагаются две различных локальных копии хранилища данных, Ы и L2. Вдоль горизонтальной оси откладывается время.L1: WS(Xi)L2:R(x^)WS(x^;x2)L1: \NS(x,)R(x^)aL2:R{x,)WS(X2)R(X2) WS(x^;x2)6Рис. 6.14. Операции чтения, осуществляемые одиночным процессом Р над двумя различнымикопиями одного хранилища данных. Хранилище с непротиворечивостью монотонногочтения (а). Хранилище без непротиворечивости монотонного чтения (б)На рис. 6.14, а процесс Р сначала выполняет операцию чтения х из копии L1,которая возвращает значение Xf (в этот момент). Это значение является результатом операции записи WS(x\), производимой с копией L1.
Позднее Р выполняетоперацию чтения х из хранилища 12, обозначаемую как R(x2). Чтобы гарантировать непротиворечивость монотонного чтения, все операции, сделанные в WS(x\),должны распространиться на L2 до момента второго чтения. Другими словами,мы должны точно знать, что операция WS(Xi) является частью операции WS(x2)и может быть выражена как WS(xuX2).В противоположность этому, на рис. 6.14, б показана ситуация, в которой непротиворечивость монотонного чтения не гарантируется.
После того как процесс Рсчитывает Х\ из Ы, он производит операцию R(x2) из L2. Однако в L2 была выполнена только операция записи WS(x2)y поэтому нет никаких гарантий, что в этомнаборе учтены также и операции, содержавшиеся в WS(xt).6.3.3. Монотонная записьВо многих ситуациях важно, чтобы по всем копиям хранилища данных в правильном порядке распространялись операции записи.
Это можно осуществить приусловии непротиворечивости монотонной записи {monotonic-xmite consistency). Еслхранилище обладает свойством непротиворечивости монотонной записи, для360Глава 6. Непротиворечивость и репликациянего соблюдается следующее условие: операция записи процесса в элемент данпых X завершается раньше любой из последующих операций записи этого процессав элемент х.Здесь завершение операции записи означает, что копия, над которой выполняется следующая операция, отражает эффект предыдущей операции записи,произведенной тем же процессом, и при этом не имеет значения, где эта операция была инициирована. Другими словами, операция записи в копию элементаданных X выполняется только в том случае, если эта копия соответствует результатам предыдущей операции записи, выполненных над другими копиями х.Отметим, что непротиворечивость монотонной записи напоминает одну измоделей непротиворечивости, ориентированной на данные, — непротиворечивость FIFO.
Сущность непротиворечивости FIFO состоит в том, что операциизаписи одного процесса всегда выполняются в правильной очередности. Такоеже ограничение на очередность применяется и при монотонной записи, за исключением того, что здесь мы говорим об одном процессе, а не о наборе параллельных процессов.Актуализация копии х не обязательна, если каждая операция записи полностью изменяет существующее значение х.
Однако операции записи часто выполняются только над частью элемента данных. Рассмотрим, например, библиотекуподпрограмм. Во многих случаях обновление библиотеки заключается в заменеодной или нескольких функций, а результатом этого является новая версия. Приусловии непротиворечивости монотонной записи даются гарантии того, что еслиизменения вносятся в одну из копий библиотеки, сначала будут внесены все предшествующие изменения. Получившаяся библиотека будет реально представлятьсобой самую последнюю версию и содержать все обновления, имевшиеся в предыдущей версии этой библиотеки.Непротиворечивость монотонной записи иллюстрирует рис. 6.15. Процесс Р осуществляет операцию записи W(xi) элемента х в локальную копию L1 (см.
рис. 6.15, а).Позднее Р выполняет еще одну операцию записи W(x2), на этот раз над L2, Длянепротиворечивости монотонной записи необходимо, чтобы предыдущая операция записи в L1 уже распространилась на L2, Это поясняет наличие операцииW(x\) в 12 и то, почему она помещена перед операцией W(x2).L1:L2:W(x,)L1:W(Xi)W(X2)L2:W(x^)W(X2)Рис, 6.15.
Операции записи, осуществляемые единичным процессом Р над двумяразличными копиями одного хранилища данных. Хранилище данныхс непротиворечивостью монотонной записи (а). Хранилищебез непротиворечивости монотонной записи (б)В противоположность этому, на рис.
6.15, б показана ситуация, в которой непротиворечивость монотонной записи не гарантирована. По сравнению с рис. 6.15, араспространение операции W(x\) на копию L2 отсутствует. Другими словами,нет никаких гарантий того, что копия элемента х, над которой производится вто-6.3. Модели непротиворечивости, ориентированные на клиента361рая операция записи, имеет то же самое или более позднее значение, чем полученное во время завершения операции W(x\) в 1 1Отметим, что по определению непротиворечивости монотонной записи операции записи одного процесса выполняются в том же порядке, в котором онибыли инициированы. В ослабленной форме непротиворечивости монотонногочтения эффект операций чтения наблюдается только в том случае, если все предшествующие операции чтения уже завершились, но не обязательно в том порядке, в котором они начинались.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
