Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

5.6. Распределенные транзакции 311

стоять из одной или более транзакций или, в свою очередь, делиться на дочерние

транзакции.

Вложенные транзакции поднимают перед нами небольшую, но важную про-

блему. Представьте себе, что транзакция запускает несколько параллельных

дочерних транзакций, и одна из них завершается, делая результат видимым для

родительской транзакции. В ходе дальнейших вычислений родительская транз-

акция прерывается, возвращая систему в то состояние, в котором она была до

запуска транзакции верхнего уровня. Вместе с другими промежуточными резуль-

татами теряются и результаты завершившейся дочерней транзакции. Таким об-

разом, долговечность, о которой мы говорили, применима только к транзакциям

верхнего уровня.

Поскольку глубина вложенности транзакций может быть произвольно глубо-

кой, для сохранения правильности необходимо серьезное администрирование.

Однако семантика ясна. Когда начинается любая транзакция или вложенная

транзакция, создается закрытая копия данных всей системы. Если транзакция

прерывается, ее внутренняя вселенная исчезает, как будто ее никогда и не было.

Если она завершается, ее внутренняя вселенная замещает родительскую. Таким

образом, если дочерняя транзакция завершается и начинается новая дочерняя

транзакция, вторая из них получает возможность работать с результатами, соз-

данными первой. Таким же образом, если прерывается объемлющая (верхнего

уровня) транзакция, все вложенные в нее дочерние транзакции также преры-

ваются.

Распределенные транзакции

Вложенные транзакции важны для распределенных систем, потому что OHPI пре-

доставляют естественный способ распределения транзакций по нескольким ма-

шинам. Однако вложенные транзакции обычно делят работу исходной транзак-

ции

логически.

Например, транзакция, в ходе которой следовало зарезервировать

билеты на три различных самолета (см. листинги 5.1 и 5.2), может быть логиче-

ски разделена на три вложенные транзакции. Каждая из этих вложенных транз-

акций может управляться отдельно, независимо от остальных двух.

Однако логическое разделение вложенных транзакций на вложенные транз-

акции не обязательно означает, что все распределение в этом и состоит. Так, вло-

женная транзакция резервирования места в самолете от Нью-Йорка до Найроби

может нуждаться в доступе к двум базам данных, по одной для каждого из этих

городов. В этом случае вложенная транзакция может разделяться дальше, на

меньшие вложенные транзакции, которые логически уже не существуют, посколь-

ку резервирование само по себе является неделимой операцией.

этом случае вложенные транзакции (плоские) работают с данными, распре-

деленными по нескольким машинам. Такие транзакции известны под названием

распределенных

транзакций {distributed transactions). Разница между вложен-

ными и распределенными транзакциями невелика, но существенна. Вложенные

транзакции

—

это транзакции, которые логически разделяются на иерархически

организованные дочерние транзакции. В противоположность им распределен-

ные транзакции логически представляют собой плоские, неделимые транзакции,

312 Глава 5. Синхронизация

которые работают с распределенными данными. Эту разницу иллюстрирует

рис.

5.17.

Вложенная транзакция Распределенная транзакция

Дочерняя Дочерняя Дочерняя Дочерняя

транзакция транзакция транзакция транзакция

Распределенная 1

база данных У

База данных \ / База данных

авиарейсов \ / отелей

Две различные (независимые) „ ^

базы данных Д^® физически разделенные части

одной базы данных

а б

Рис. 5.17. Вложенная транзакция (а), распределенная транзакция (б)

Основная проблема распределенных транзакций в том, что для блокировки

данных и подтверждения транзакции необходимы отдельные распределенные

алгоритмы. Распределенную блокировку данных мы рассмотрим ниже. Деталь-

ное рассмотрение распределенных протоколов подтверждения транзакции мы от-

ложим до главы 7, в которой рассмотрим отказоустойчивость и механизмы вос-

становления, к которым относится и протокол подтвержденрш.

5.6.3. Реализация

Транзакции кажутся отличной идеей, но как их реализовать? Этот вопрос мы

сейчас и рассмотрим. Чтобы упростить дело, мы ограничимся транзакциями в

файловой системе. Должно быть понятно, что если каждый процесс, выполняю-

щий транзакцию, просто обновляет файл там же, где файл используется, транзак-

ция не будет атомарной и при прерывании транзакции все изменения не исчезнут

волшебным образом. Понятно, что нужен другой метод. Обычно используются те

два метода, которые описаны ниже.

Закрытое рабочее пространство

Концептуально, когда процесс начинает транзакцию, он получает закрытое рабо-

чее пространство, содержащее все файлы, к которым он хочет получить доступ.

Пока транзакция не завершится или не прервется, все операции чтения и записи

будут происходить не в файловой системе, а в закрытом рабочем пространстве.

Это утверждение прямо приводит нас к первому методу реализации

—

созданию

для процесса, в момент начала транзакции, закрытого рабочего пространства.

Проблема этой методики состоит в том, что цена копирования всего подряд

в закрытое рабочее пространство такова, что равносильна запрету. Возможна, од-

нако,

различная оптимизация. Первый вариант оптимизации основан на том со-

ображении, что если процесс только читает файл, но не изменяет его в создании

5.6. Распределенные транзакции 313

закрытой копии нет необходимости. Он может использовать реальный объект

(если только тот не меняется в процессе транзакции). Соответственно, когда

процесс начинает транзакцию, он должен создать закрытое рабочее пространство,

котором ничего нет, за исключением указателя на рабочее пространство своего

родителя. Если это транзакция верхнего уровня, рабочим пространством родите-

ля будет файловая система. Когда процесс открывает файл на чтение, он следует

за указателямр!, пока файл не обнаружится в рабочем пространстве родителя

(или более дальнего предка).

Когда файл открывается на запись, он может быть найден таким же образом,

как и при чтении, за исключением того, что сначала он будет скопирован в за-

крытое рабочее пространство. Однако при втором варианте оптимизации удается

отказаться и от большей части копирования. Вместо копирования целого файла

в закрытое рабочее пространство можно копировать только индекс файла. Ин-

декс

—

это блок данных, ассоциированных с каждым файлом и хранящий ин-

формацию о том, где на диске расположены его блоки. В UNIX индекс

—

это ин-

дексный узел (inode). При использовании внутреннего индекса файл может

быть считан точно так же, поскольку диск, к которому происходит адресация,

—

это тот же самый диск с исходным расположением блоков. Однако когда блок

файла модифицируется, создается копия этого блока, и в индекс вставляется ад-

рес копии, как показано на рис. 5.18, а. После этого блок можно изменять, не

оказывая влияния на оригинал. Добавляемые блоки обрабатываются точно так

же.

Новые блоки иногда называют

теневыми блоками {shadow

blocks).

Индекс

Ш 0

П П П

)Ь^

Свободные блоки

Закрытое

рабочее

пространство

Исходный ^----

индекс

Рис. 5.18. Индекс файла и дисковые блоки для файла из трех блоков (а). Ситуация после того,

как транзакция модифицировала блок

и добавила блок 3 (б).

Ситуация после подтверждения транзакции {в)

Как молшо видеть на рис. 5.18, б, процесс, выполняющий транзакцию, видит

модифицированный файл, а все остальные процессы продолжают работать с ис-

314 Глава 5. Синхронизация

ходным файлом. В особенно сложных транзакциях закрытое рабочее простран-

ство может содержать не один, а большое количество файлов. Если транзакция

прерывается, закрытое рабочее пространство просто удаляется и все закрытые

блоки, которые оно содержало, возвращаются в список свободных. Если тран-

закция завершается, закрытые блоки в ходе атомарной операции перемещаются

в рабочее пространство родителя, как показано на рис. 5.18, в. Блоки, которые

больше не нужны, возвращаются в список свободных.

Эта схема работает также и для распределенных транзакций. В этом случае

аналогичный процесс начинается на каждой машине, содержащей файлы, к ко-

торым в ходе транзакции будет производиться доступ. Каждый процесс получа-

ет свое собственное закрытое рабочее пространство так, как описано выше. Если

транзакция прерывается, все процессы просто отказываются от своих закрытых

рабочих пространств. С другой стороны, при подтверждении транзакции произ-

водятся локальные обновления, после чего транзакции можно считать полно-

стью завершенными.

Журнал с упреждающей записью

Другой традиционный метод реализации транзакций

—

это

журнал

упреждаю-

щей записью

{write-ahead

log).

Согласно этому методу файлы действительно мо-

дифицируются там же, где находятся, но перед тем, как какой-либо блок действи-

тельно будет изменен, в журнал заносится запись со сведениями о том, какая

транзакция вносит изменения, какой файл и блок изменяются, каковы прежние и

новые значения. Только после успешной записи в журнал изменения вносятся в

файл.

Ниже описано, как работает этот метод. В листинге 5.3 представлена простая

транзакция, которая использует две общие переменные (или другие объекты), х

и у, инициализированные нулями.

Листинг 5.3. Транзакция

X = 0:

= 0:

BEGINJRANSACTION:

= X + 1:

= У + 2;

X = у * у:

ENDJRANSACTION;

Для каждой из трех инструкций тела транзакции до начала ее выполнения

создается запись в журнале, которая содержит прежнее и новое значения, разде-

ленные косой чертой:

содержимое журнала перед выполнением первой инструкции (х=х+1:):

[х=0/1]

4 содержимое журнала перед выполнением второй инструкции (у=у+2:):

[х=0/1]

[у=0/2]

5.6. Распределенные транзакции 315

> содержимое журнала перед выполнением третьей инструкции (х=у*у;):

[х=0/1]

[у=0/2]

[х=1/4]

Если транзакция успешна, она подтверждается и в журнал добавляется за-

пись о подтверждении, но структуры данных не изменяются, поскольку они

так изменены. Если транзакция прерывается, журнал используется для восста-

новления первоначального состояния. Начиная с конца и продвигаясь к началу,

из журнала считываются записи и описанные в них изменения отменяются. Это

действие называется

откатом {rollback)

транзакции.

Как и предыдущая, эта схема также может использоваться для работы с рас-

пределенными транзакциями. В этом случае каждая машина поддерживает соб-

ственный журнал изменений в локальной файловой системе. Откат в случае пре-

рывания транзакции каждая машина производит по отдельности, восстанавли-

вая свои исходные файлы.

5.6.4. Управление параллельным

выполнением транзакций

Итак, мы рассмотрели основные способы достижения атомарности транзакций.

Достижение атомарности (и долговечности) транзакций при наличии сбоев

—

это

важнейшая тема, к которой мы вернемся в главе 7, когда будем рассматривать не

только транзакции. Такие свойства, как непротиворечивость и изолированность,

основаны на возможности управления выполнением параллельных транзакций,

то есть транзакций, выполняющихся одновременно и над одним и тем же набо-

ром совместно используемых данных.

Цель управления параллельным выполнением транзакций состоит в том, что-

бы позволить нескольким транзакциям выполняться одновременно, но таким об-

разом, чтобы набор обрабатываемых элементов данных (например, файлов или

записей базы данных) оставался непротиворечивым. Непротиворечивость дости-

гается в результате того, что доступ транзакций к элементам данных организует-

ся в определенном порядке так, чтобы конечный результат был таким же, как

при выполнении всех транзакций последовательно.

Управление параллельным выполнением лучше всего можно понять в терми-

нах трех менеджеров, организованных по уровням, как это показано на рис. 5.19.

Нижний уровень предоставляет

менеджера

данных {data

manager),

который фи-

зически осуществляет операции чтения и записи данных. Менеджер данных ни-

чего не знает о том, какая транзакция выполняет чтение или запись. На самом

деле он вообще ничего не знает о транзакциях.

Средний уровень представлен

планировщиком

{scheduler).

Он несет основную

ответственность за правильность управления параллельной работой, определяя,

какой транзакции и в какой момент разрешается передать операцию чтения или

записи менеджеру данных. Он также планирует отдельные операции чтения

записи с теми же гарантиями непротиворечивости и изолированности, что и для

316 Глава 5. Синхронизация

транзакций. Позже мы рассмотрим планирование, основанное на использовании

блокировок, и планирование, основанное на использовании отметок времени.

Транзакции

READ/WRITE

Менеджер

транзакций

Планировщик

Менеджер

данных

BEGIN_TRANSACTION

END_TRANSACTION

LOCK/RELEASE

или

операции

с отметками времени

Выполнение чтения/записи

Рис. 5.19. Обобщенная организация менеджеров

для управления транзакциями

На самом верхнем уровне находится

менеджер транзакций (transaction

mana-

ger),

который отвечает, прежде всего, за атомарность и долговечность. Он обра-

батывает примитивы транзакций, преобразуя их в запросы к планировщику.

Менеджер

транзакций

Планировщик

Менеджер

данных

Маш1 1наА

г-

Планировщик

<1 '

Менеджер

данных

Маш

лиг

Г''

Планировщик

Менеджер

данных

Машк

на С

Рис. 5.20. Обобщенная организация менеджеров для управления

распределенными транзакциями

Модель, приведенная на рис. 5.19, может быть адаптирована к использованию

в распределенных системах, как показано на рис. 5.20. Каждая машина в этом

случае имеет своих планировщика и менеджера данных, которые совместно обес-

5.6. Распределенные транзакции 317

печивают гарантии непротиворечивости локальных данных. Каждая транзакция

обрабатывается одним менеджером транзакций. Последний работает

планиров-

щиками отдельных машин.

зависимости

от

алгоритма управления параллель-

ным выполнением транзакций планировщик также может работать

удаленными

менеджерами данных.

Мы

вернемся

разговору

распределенном управлении

параллельным выполнением чуть ниже.

Изолированность

Основная задача алгоритмов управления параллельным выполнением

—

гаран-

тировать возможность одновременного выполнения многочисленных транзакций

до тех пор,

пока они изолированы друг от друга. Это значит, что итоговый резуль-

тат их выполнения будет таким же, как если бы эти транзакции выполнялись од-

на за другой

определенном порядке.

листинге 5.4 представлены три транзакции, которые выполняются одновре-

менно

трех отдельных процессах. Если бы они выполнялись последовательно,

итоговыми значениями переменной х были бы 1,

или 3,

зависимости

от

того,

какая

из

транзакций выполнялась

бы

последней

(х

может быть совместно

ис-

пользуемой переменной, файлом или сущностью другого типа).

Листинг

5.4.

Три транзакции Т^, Т2

''"з

BEGINJRANSACTION

= 0:

= X + 1;

ENDJRANSACTION

BEGINJRANSACTION

= 0:

= X + 2:

ENDJRANSACTION

BEGIN TRANSACTION

x"=

= X + 3;

ENDJRANSACTION

табл. 5.3 показаны различные способы упорядочивания, называемые плана-

ми

{schedules).

План 1 реально сериализован. Другими словами, транзакции

вы-

полняются строго последовательно, так что они

по

определению удовлетворяют

условию сериализуемости. План 2 не сериализован, но также допустим, поскольку

в результате его выполнения значение х, которое будет получено после отработ-

ки

транзакций, соответствует значению, полученному при строго последователь-

ном выполнении транзакций. Третий план недопустим, потому что

результате

его выполнения х становится равным

что при последовательном выполнении

транзакций невозможно. Системе необходимо убедиться,

что

отдельные опера-

ции перемелсаются правильно. Давая системе свободу выбора любой очередно-

сти операций

проверяя корректность получаемых результатов,

мы

избавляем

программистов

от

необходимости реализовывать собственные взаимные исклю-

чения, что упрощает

их

работу.

318 Глава 5. Синхронизация

Таблица 5.3. Возможные планы по очередности выполнения операций

Номер

плана

х=0;

х=0:

х=х+1:

х=0:

Очередность операций

х=0:

х=х+2:

х=0:

х=х+1:

х=х+2:

х=0:

х=х+1;

х=0:

х=х+2:

х=х+3:

Правильность

плана

Правильно

Неправильно

Для того чтобы разобраться

планах

управлении параллельным выполне-

нием, нет необходимости точно знать, как именно переменные будут вычислять-

ся.

Другими словами, неважно, будет

ли

значение

увеличено

на 2 или 3. Что

действительно важно,

так

это то, что значение х изменится. Соответственно, мы

можем описать транзакцию как наборы операций чтения

записи определенных

элементов данных. Так, например, каждая из трех транзакций,

Ть

Т2

Тз, приве-

денных

листинге 5.4, может быть представлена

виде последовательностей:

write(Tl.x); read(Ti.x); wr1te(Ti,x)

Основная идея управления параллельным выполнением состоит в том, чтобы

правильно спланировать конфликтующие операции {conflicting

operations).

Две

операции конфликтуют, если они работают с одним

тем же элементом данных,

и как минимум одна

из

них

—

это операция записи. В

конфликте чтения-записи

(read-write conflict) запись

—

это

одна

из

операций. Кроме того,

мы

имеем дело

и с

конфликтом двойной

записи

(write-write

conflict),

при этом не имеет значения,

принадлежат

ли

конфликтующие операции

одной транзакции

или к

разным.

Следует отметить, что две операции чтения никогда не конфликтуют между собой.

Алгоритмы управления параллельным выполнением обычно классифициру-

ются

по

способу синхронизации операций чтения

записи. Синхронизация мо-

жет производиться посредством механизма взаимного исключения совместно ис-

пользуемых данных (то есть блокировки) или явного упорядочивания операций

с помощью отметок времени.

Дальнейшее деление можно провести между оптимистическим

пессимисти-

ческим управлением параллельным выполнением. Для

пессимистических

подхо-

дов фундаментальным является закон Мерфи, согласно которому если что-ни-

будь можно сделать неправильно,

это

что-то будет сделано неправильно.

При

пессимистических подходах операции синхронизируются

до их

выполнения,

и, таким образом, конфликты разрешаются до того, как они проявятся. В проти-

воположность этому,

оптимистические

подходы основаны

на

идее

о том, что

обычно ничего плохого не случается. Поэтому операции без затей выполняются,

а синхронизация производится

конце транзакции. Если

этот момент обнару-

живается конфликт, одна или более транзакций прерываются. Далее мы рассмот-

рим два пессимистических

один оптимистический методы. Прекрасный обзор

различных подходов можно найти

[46].

Двухфазная блокировка

Самый старый

наиболее широко используемый алгоритм управления парал-

лельным выполнением транзакций

—

это

блокировка

{locking).

своей простей-

5.6. Распределенные транзакции 319

шей форме, когда процесс

ходе транзакции нуждается в чтении или записи эле-

мента данных, он просит планировщик заблокировать для него этот элемент дан-

ных. Точно так же, когда необходимость

этом элементе данных исчезает, плани-

ровщика просят снять блокировку. Задача планировщика состоит

том, чтобы

устанавливать

снимать блокировку таким образом, чтобы получать только до-

пустимые планы выполнения. Другими словами,

мы

нуждаемся

применении

алгоритма, предоставляющего нам только сериализуемые планы. Один

из

таких

алгоритмов

—

двухфазная блокировка.

При двухфазной

блокировке (Two-Phase

Locking,

2PL), которая продемонстри-

рована на рис. 5.21, планировщик сначала, на фазе

подъема

{growingphase), уста-

навливает все необходимые блокировки,

затем,

на

фазе спада

{shrinking

phase),

снимает их. Говоря конкретнее, выполняются три правила, описанные

[47].

4 Когда планировщик получает операцию орег{Т,х)

от

менеджера транзак-

ций,

он

проверяет,

не

конфликтует

ли эта

операция

другими операция-

ми,

уже

получившими блокировку. Если

наличии конфликт, операция

орег{Т,х) откладывается

(и

транзакция Г вместе

ней). Если конфликта

нет, планировщик производит блокировку для элемента данных

х и

пере-

дает операцию менеджеру данных.

'f Планировщик никогда

не

снимает блокировку

элемента данных

х,

если

менеджер данных уведомляет его, что

он

осуществляет операцию,

кото-

рой участвует этот элемент данных.

"¥ После того

как

планировщик снимает

данных блокировку, установлен-

ную

по

требованию транзакции

Г, он

никогда

не

делает

по

требованию

этой транзакции другую блокировку, при этом неважно,

на

какой элемент

данных транзакция

требует установить блокировку. Любые попытки

потребовать новой блокировки являются ошибкой профаммирования и при-

водят

прерыванию транзакции

Т.

Фаза подъема

Г"

Точка

бг

окировки

Фаза спада

Время

—•

Рис. 5.21. Двухфазная блокировка

Можно доказать

[139],

что если все транзакции используют двухфазную бло-

кировку, любой план, сформированный путем перекрытия этих транзакций,

се-

риализуем.

этом причина популярности двухфазной блокировки.

320 Глава 5. Синхронизация

Во многих системах фаза спада не начинается до тех пор, пока транзакция не

окончится подтверждением или прерыванием, что и приведет к снятию блокиро-

вок, как показано на рис. 5.22. Такой режим, именуемый

строгой двухфазной

бло-

кировкой {strict two-phase

locking),

имеет два серьезных преимущества. Во-первых,

транзакция всегда считывает значения, записанные подтвержденной транзакци-

ей,

поэтому невозможно прерывание транзакции из-за того, что ее вычисления

базируются на недоступных данных. Во-вторых, любые наложения и снятия бло-

кировок могут выполняться системой без использования транзакций: любые бло-

кировки устанавливаются при доступе к элементу данных и снимаются по окон-

чании транзакции. При таком поведении устраняются каскадные прерывания

{cascaded

aborts):

отмена подтвержденной транзакции по той причине, что она

получает элемент данных, который получать не должна.

•у

Фаза подъема

v^~^

Г^

Точка бг

окировки

Фаза спада

Все блокировки

снимаются

одновременно ^

Время —•

Рис. 5.22. Строгая двухфазная блокировка

Как двухфазная блокировка, так и строгая двухфазная блокировка могут при-

вести к тупикам. Если два процесса пытаются заблокировать одну и ту же пару

блоков, но в разном порядке, результатом будет взаимная

блокировка,

или тупик

{deadlock).

В этом случае используются традиционные технологии предотвраще-

ния тупиков, такие как выполнение блокировок в некотором строго заданном

порядке. Также возможно обнаружение взаимных блокировок путем составле-

ния полного графа транзакций, показывающего, какой процесс какую блокиров-

ку создал и какую хочет создать, с последующей проверкой этого графа на цик-

лы.

И наконец, когда заранее известно, что никакая блокировка не может при

нормальной работе длиться более t секунд, можно использовать схему с тайм-ау-

том: если блокировка непрерывно принадлежит процессу более t секунд, это мо-

жет происходить из-за взаимной блокировки.

Существует несколько способов реализации двухфазной блокировки в рас-

пределенных системах. Допустим, что данные, с которыми мы работаем, разбро-

саны по нескольким машинам. При централизованной двухфазной блокировке

{centralized two-phase locking) за установку и снятие блокировок отвечает одна

машина. Все менеджеры транзакций взаимодействуют с одним централизован-

ным менеджером блокировок, который принимает от них запросы на блокиров-