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

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

5.5. Взаимное исключение

301

сам, концептуально включая самого себя. Посылка сообщения,

как

предполага-

ется, надежная, то есть

на

каждое письмо приходит подтверждение

получении.

Вместо отдельных сообщений может быть использована доступная надежная

групповая связь.

Когда процесс получает сообщение

запросом от другого процесса, действие,

которое оно производит, зависит

от

его связи

с той

критической областью,

имя

которой указано

сообщении. Можно выделить три варианта.

> Если получатель

не

находится

критической области

не собирается

ту-

да входить,

он

отсылает отправителю сообщение ОК,

-¥ Если получатель находится

критической области, он не отвечает,

поме-

щает запрос

очередь.

> Если получатель собирается войти

критическую область,

но

еще

не

сде-

лал этого,

он

сравнивает метку времени пришедшего сообщения

меткой

времени сообщения, которое

он

отослал. Выигрывает минимальное. Если

пришедшее сообщение имеет меньший номер, получатель отвечает посыл-

кой сообщения ОК. Если

его

собственное сообщение имеет меньшую

от-

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

очередь,

ни-

чего

не

посылая при этом.

После посылки сообщения-запроса на доступ

критическую область процесс

приостанавливается

ожидает,

что

кто-нибудь даст

ему

разрешение

на

доступ.

После того

как все

разрешения получены,

он

может войти

критическую

об-

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

то

отсылает сообщения ОК всем

процессам

их очереди

удаляет все сообщения подобного рода из своей очереди.

Попытаемся теперь понять, как работает алгоритм. Если конфликты отсутст-

вуют,

все

идет хорошо. Однако представим себе,

что два

процесса пытаются

одновременно войти

одну

и ту же

критическую область,

как

показано

на

рис.

5.14,

а.

Входит

в критическую

область

Входит

в критическую

область

Рис. 5.14. Два процесса одновременно хотят получить доступ в одну

ту же критическую

область (а). Процесс

имеет меньшую отметку времени

потому выигрывает (б). Когда

процесс

завершает работу

критической областью, он отправляет сообщение

ОК,

и теперь процесс

может войти

критическую область

(в)

Процесс О рассылает всем запрос

отметкой времени

8, и

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

с ним процесс

рассылает всем запрос

отметкой времени 12. Процесс 1

не

ин-

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

тересуется входом в критическую область и в ответ посылает сообщение ОК им

обоим. Процессы

и 2 замечают конфликт и сравнивают отметки времени. Про-

цесс 2 видит, что проиграл, и разрешает доступ процессу

О,

посылая ему сообще-

ние

ОК.

Процесс

ставит ответ от процесса 2 в очередь для дальнейшей обработ-

ки и входит в критическую секцию, как показано на рис. 5.14, б. Когда процесс

заканчивает работу в критической области, он удаляет ответ 2 из очереди сооб-

щений и отправляет процессу 2 сообщение ОК, разрешая ему войти в критиче-

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

чае конфликтов наименьшая отметка времени выигрывает, а с очередностью

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

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

если бы процесс 2 послал свое сообщение раньше, чем это сделал процесс

О,

и по-

лучил разрешение на доступ до создания своего ответа на сообщение от процесса 0.

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

критической области, просто поместил бы запрос от процесса

в очередь, не по-

сылая никакого ответа.

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

ленное взаимное исключение гарантировано от тупиков и зависаний. Число со-

общений, приходящихся на один процесс,

—

2(п-1), где п

—

общее число процес-

сов в системе. Больше нет единой точки, сбой в которой мог бы погубить всю

систему.

Однако, к сожалению, одна точка сбоя сменилась на п точек сбоев. Если ка-

кой-либо из процессов «рухнет», он не сможет ответить на запрос. Это молчание

будет воспринято (неправильно) как отказ в доступе и блокирует все последую-

щие попытки всех процессов войти в какую-либо из критических областей. По-

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

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

что заменили слабый алгоритм в п раз худшим и требующим более интенсивного

сетевого трафика.

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

ли ранее. Когда приходит запрос, его получатель посылает ответ всегда, разрешая

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

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

тель находится в нерабочем состоянии. После получения запрещения отправи-

тель ожидает последующего сообщения ОК.

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

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

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

ление процессов из группы и отслеживание сбоев. Метод наилучшим образом

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

не меняется.

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

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

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

решениях, касающихся входа в критические области. Если один из процессов

5.5. Взаимное исключение 303

оказывается неспособным справиться

такой нагрузкой, маловероятно,

что во-

зымеет успех попытка

их

всех сделать

то

же самое параллельно.

В этот алгоритм можно внести разнообразные дополнительные усовершенст-

вования. Например, получение каждым

из

процессов разрешения

на

вход

кри-

тическую область

—

это, по правде говоря, чересчур. Ведь нам необходимо толь-

ко предотвратить одновременный вход двух процессов

критическую область.

Алгоритм можно модифицировать так, чтобы разрешить процессу вход

крити-

ческую область после того,

как он

соберет разрешения простого большинства,

не

всех остальных процессов. Разумеется,

этом случае, после того как процесс

даст разрешение

на

вход

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

жет дать

то же

самое разрешение другому процессу

до тех

пор, пока первый

не

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

другие улучшения,

частно-

сти предложенные

[279],

но

они легко могут запутать алгоритм.

Несмотря

на все

возможные улучшения, этот алгоритм остается более мед-

ленным, более сложным, более затратным

менее устойчивым,

чем

исходный

централизованный алгоритм. Зачем тогда

его

вообще изучать?

Для

единствен-

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

Когда мы начинали рассмотрение, это не было очевидно. Кроме того, только об-

ратив внимание

на

недостатки,

мы

можем подвигнуть будущих теоретиков

на

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

И на-

конец, подобно питанию шпинатом

изучению латыни

средней школе, некото-

рые вещи выглядят очень хорошо, но только до тех пор, пока остаются теорией.

5.5.3. Алгоритм маркерного кольца

Абсолютно иной подход

реализации взаимных исключений

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

системах предлагает алгоритм

маркерного

кольца {Token Ring). Пусть

мы

имеем

магистральную сеть (например, Ethernet), но без внутреннего упорядочения про-

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

котором каждо-

му процессу назначается положение

кольце, как показано на рис. 5.15, б. Поло-

жение

кольце может быть назначено

по

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

или как-то иначе. Неважно,

как

именно задана упорядоченность. Главное

—

как

дать процессу знать, кто

кольце является следующим после него.

Рис. 5.15. Беспорядочная группа процессов в сети

(а).

Логическое кольцо, созданное программно

(б)

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

При инициализации кольца процесс О получает маркер, или токен {token).

Маркер циркулирует по кольцу. Он передается от процесса k процессу k+ \ (это

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

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

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

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

Входить в другую критическую область, используя тот же самый маркер, запре-

щено.

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

ческую область, он просто передает этот маркер дальше. Соответственно, если ни

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

лирует по кольцу с максимально возможной скоростью.

Легко видеть, что этот алгоритм корректен. Только один процесс в любой

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

диться в критической области. Поскольку маркер перемещается от процесса

к процессу в общеизвестном порядке, зависания не происходит. Когда процесс

решает войти в критическую область, в худшем случае ему придется ждать, пока

все остальные процессы последовательно не войдут в критическую область и не

выйдут из нее.

Обычно этот алгоритм также имеет проблемы. Если маркер однажды потеря-

ется, он должен быть восстановлен. На самом деле, понять, что он пропал, до-

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

ра в сети не ограничен. Тот факт, что маркера не было видно в течение часа,

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

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

справиться с этим проще, чем в других случаях. Если мы потребуем от процесса,

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

наружен при первой же попытке соседа передать ему маркер. В этот момент не-

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

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

ходимости следующему за ним. Разумеется, это требует поддержания текущей

конфигурации кольца.

5.5.4. Сравнение трех алгоритмов

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

ку оно поучительно. В табл. 5.1 мы перечислили алгоритмы и три их ключевых

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

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

лагается, что сообщения передаются по сети последовательно) и некоторые про-

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

Централизованный алгоритм наиболее прост и наиболее эффективен. На то,

чтобы войти в критическую область, ему достаточно всего трех сообщений

—

за-

прос,

разрешение на вход и сообщение о выходе. Распределенному алгоритму

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

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

для запроса п-

сообщений, по одному на каждый процесс, и дополнительно п- i

сообщений на разрешение, всего 2(п -1). В алгоритме маркерного кольца число

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

да

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

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

область понадобится одно сообщение. В другом крайнем случае маркер может

циркулировать по кольцу часами и им никто и не заинтересуется. В этом случае

число сообщений на вход в критическую область одного процесса не ограничено.

Таблица

5.1.

Сравнение трех алгоритмов взаимных исключений

Алгоритм

Число сообщений Задержка перед

на вход-выход входом

числе

сообщений

Возможные проблемы

Централизованный

Распределенный

Маркерного кольца

2(п-1)

От

до

сю

2(п~1)

ОтОдоп-1

Крах координатора

Сбой

одном

из процессов

Потеря маркера, сбой

в одном из процессов

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

ласть,

до момента входа для этих трех алгоритмов также различна. Если критичес-

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

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

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

таблице иллюстрируется первый случай. В случае централизованного алгорит-

ма, для того чтобы войти в критическую область, требуется всего два сообщения.

случае распределенного алгоритма требуется 2(п - 1) сообщений, с учетом то-

го,

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

ется от

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

(маркер

был только что передан дальше по кольцу).

И, наконец, все три алгоритма тяжело реагируют на сбои. Чтобы сбой не при-

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

дополнительно усложнять алгоритм. Забавно, но распределенные алгоритмы бо-

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

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

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

Концепция транзакций тесно связана

концепцией взаимных исключений. Алго-

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

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

и т.

п. Транзакции, в общем, также защищают общие ресурсы от одновременного

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

другое. В частности, они превращают процессы доступа и модификации множе-

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

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

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

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

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

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

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

5.6.1.

Модель транзакций

Базовая модель транзакций пришла к нам из делового мира. Допустим, некой ме-

ждународной корпорации потребовалась партия каких-то штуковин. Они обра-

щаются к потенциальному поставидику, ООО «Штуковины», хорошо известному

во всем мире качеством своих штуковин, с заказом на 100 000 10-сантиметровых

пурпурных штуковин с поставкой в июне. ООО «Штуковины» предлагает

100 000 4-дюймовых розовых штуковин с поставкой в декабре. Некая междуна-

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

заказ в июле и настаивает на 10-сантиметровых штуковинах для своих зарубеж-

ных заказчиков. ООО «Штуковины» отвечают предложением 3 15/16-дюймовых

лавандовых штуковин в октябре. После дальнейших переговоров они сходятся,

наконец, на 3 959/1024-дюймовых фиолетовых штуковинах, которые будут по-

ставлены к 15 августа.

До этого самого момента обе стороны имели полную возможность прекратить

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

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

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

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

го бы не произошло, но в момент появления подписей они перешли ту черту, из-

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

Компьютерная модель выглядит очень похоже. Один процесс объявляет, что

хочет начать транзакцию с одним или несколькими другими процессами. После

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

сти,

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

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

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

сов отказываются (или до соглашения в них возникают сбои), ситуация возвра-

щается к тому состоянию, которое имело место до начала транзакции, со всеми

вытекающими отсюда последствиями для файлов, баз данных и т. д., все измене-

ния в которых волшебным образом исчезают. Такое свойство «все или ничего»

сильно упрощает работу программистам.

Использование транзакций в компьютерных системах берет начало в шести-

десятых годах. До этого дисков и сетевых баз данных не существовало, все дан-

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

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

начинал работу с двумя магнитными лентами. Первая из них содержала полные

сведения о товарах на момент открытия утром текущего дня, а вторая

—

список

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

изменений за

день:

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

ные поставщикам. Компьютер считывал информацию с обеих лент и создавал

новую основную ленту инвентаризации, как показано на рис. 5.16.

инвентаризация

Новая

инвентаризация

Исходные J ^Н I /"^N

ленты ) ^^ ^ Компьютер [—•(^ ) Лента с результатом

Сегодняшние

изменения

Рис. 5.16. Внесение изменений

основную ленту защищено от сбоев

Основное преимущество этой схемы (несмотря на то, что люди, вынужден-

ные этим заниматься, тогда часто не могли этого оценить) состояло в том, что

при любых сбоях все ленты можно было перемотать на начало и начать работу

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

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

—

«все или ничего».

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

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

модемом, намереваясь снять деньги с одного счета и положить их на другой.

Операция осуществляется в два приема.

Снять сумму а со счета 1.

Положить сумму а на счет 2.

В том случае, если модемное соединение после выполнения первого этапа, но

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

второй не перечислены. Деньги просто растворятся в воздухе.

Проблему решает объединение этих операций в одну транзакцию. Либо обе

они будут выполнены, либо не будет выполнена ни одна. Ключевой, следова-

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

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

—

так это способ «от-

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

возможность дает нам транзакция.

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

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

так и исполняющей системой языка программирования. Типичные примеры при-

водятся в табл. 5.2. Полный список примитивов зависит от того, какие объекты

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

правление, прием и пересылка почты. В банковских системах примитивы могут

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

READ

WRITE.

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

внутрь транзакций.

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

Таблица 5.2. Некоторые примитивы, используемые в транзакциях

Примитив Описание

BEGINTRANSACTION Пометить начало транзакции

ENDTRANSACTION Прекратить транзакцию

попытаться завершить

ее

ABORT_TRANSACTION Прервать транзакцию

восстановить прежние значения

READ

Считать данные

из

файла, таблицы или другого источника

WRITE Записать данные

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

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

BEGIN_TRANSACTION и

END_TRANSACTION.

Операции, расположенные между ними, фор-

мируют тело транзакции. Все эти операции либо выполняются, либо не выпол-

няются. Это могут быть системные вызовы, библиотечные процедуры или инст-

рукции на языке реализации.

Рассмотрим в качестве примера процесс резервирования посадочных мест от

Белых равнин, штат Нью-Йорк, до Малинди, Кения, в авиационной системе ре-

зервирования мест. Один из возможных маршрутов: из Белых равнин в аэропорт

им.

Джона Кеннеди, из аэропорта им. Джона Кеннеди в Найроби, из Найроби

в Малинди. На листинге 5.1 мы видим, что резервирование билетов на эти три

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

Листинг 5.1. Подтверждение транзакции резервирования билетов

на три авиарейса

BEGIN_TRANSACTION

зарезервировать WP -> JFK:

зарезервировать JFK -> Nairobi:

зарезервировать Nairobi -> Malindi;

END_TRANSACTION

Теперь представим, что билеты на первые два рейса зарезервированы, а тре-

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

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

—

база данных по биле-

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

транзакции (листинг 5.2). Все выглядит так, будто нршего не происходило.

Листинг 5.2. Транзакция прервана по причине невозможности заказа билета

на третий самолет

BEGIN_TRANSACTION

зарезервировать WP -> JFK;

зарезервировать JFK -> Nairobi;

Nairobi -> Malindi переполнен =>

ABORTJRANSACTION

Свойство транзакций «все или ничего» — это лишь одно из характерных

свойств транзакции. Говоря более конкретно, транзакции:

> атомарны {atomic)

—

для окружающего мира транзакция неделима;

непротиворечивы {consistent)

—

транзакция не нарушает инвариантов сис-

темы;

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

изолированы

(isolated)

—

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

ют друг на друга;

"¥

долговечны

{durable)

—

после завершения транзакции внесенные ею изме-

нения становятся постоянными.

На эти свойства часто ссылаются по их первым буквам

—

ACID.

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

—

ато-

марность.

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

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

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

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

ны они сами в транзакцию или нет) не могут наблюдать каких-либо промежу-

точных состояний.

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

данные в некий файл с начальной длиной 10 байт. Если этот файл в ходе тран-

закции пожелает прочитать другой процесс, он увидит только исходные 10 байт

независимо от того, сколько байт было добавлено в файл в ходе транзакции. Ес-

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

ра, размера на момент завершения без промежуточных состояний независимо от

того,

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

Второе свойство, о котором мы говорим, это

непротиворечивость.

Это значит,

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

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

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

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

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

мент в ходе транзакции этот инвариант и может нарушаться, но такое нарушение

не будет заметно извне.

Третье свойство, о котором мы говорили,

—

это

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

или сериа-

лизуемость.

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

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

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

(зависящем от системы) порядке. Ниже мы еще вернемся к этому свойству.

Четвертое свойство гласит, что транзакции

долговечны.

Это свойство отражает

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

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

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

ции или их потере. Долговечность подробно обсуждается в главе 7.

5.6.2. Классификация транзакций

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

ACID.

Этот тип транзакции именуется также плоской транзакцией {flat trans-

action).

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

—

это наиболее простой и наиболее часто используе-

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

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

НИИ,

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

мы обсудим два важных класса транзакций

—

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

ленные транзакции. Другие классы широко рассмотрены в

[177].

Ограничения плоских транзакций

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

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

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

стью.

Рассмотрим снова полет из Нью-Йорка в Кению, проиллюстрированный лис-

тингами 5.1 и 5.2. Предположим, что билеты на всю поездку продавались в виде

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

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

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

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

лет на самолет из аэропорта Кеннеди в Найроби уже невозможно. Прерывание

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

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

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

цию.

Плоская транзакция не позволит нам этого сделать.

В качестве другого примера рассмотрим web-сайт, гиперссылка в котором

двунаправленная. Другими словами, если web-страница W\ содержит URL стра-

ницы

W2J

ТО

Wi знает, что

ссылается на нее

[224].

Теперь представим себе, что

страница W перенесена в другое место или заменена другой страницей. В этом

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

ной атомарной операцией, в противном случае мы можем получить (временно)

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

транзакцию. Транзакция состоит из внесения изменений в W и серии опера-

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

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

для выполнения нескольких часов. Страницы, ссылающиеся на W, могут быть

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

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

потому что в этом случае некоторые web-страницы будут содержать правильные

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

ние изменений с сохранением старой ссылки на 1^ для тех страниц, ссылки на

которые еще не изменились.

Вложенные транзакции

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

при использовании вложенных транзакций (nested transactions). Транзакция

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

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

щения программирования. Каждая из этих дочерних транзакций также может со-