Параллелизм и репликация данных

Параллелизм

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

Стандартный метод разрешения таких проблем - метод блокировки. Блокировка не является единственным возможным подходом в решении проблемы управления параллелизмом, но она, несомненно, чаще других встречается на практике. Однако с внедрением метода блокировки возникают другие проблемы, среди них наиболее известна проблема тупиковых ситуаций. Формальный критерий правильности выполнения некоторого набора параллельных транзакций описан в концепции способности к упорядочению.

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

Транзакции

Транзакции - основной инструмент управления параллельными процессами в распределенных корпоративных приложениях. Слово "транзакция" часто приходит на ум в связи с коммерческими и банковскими операциями. Обращение к банкомату, ввод пароля и получение наличности - это транзакция.

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

ACID:свойства транзакций

Транзакции в программных системах часто описывают в терминах свойств, обозначаемых общей аббревиатурой ACID.

Ресурсы транзакций

Наиболее часто термин "транзакция" произносится применительно к СУБД. Однако это более широкое понятие, которое используется во многих других областях. Существует множество других объектов, управляемых с помощью механизмов поддержки транзакций, например, очереди сообщений или заданий на печать, банкоматы и т.д. Таким образом, термин "ресурсы транзакций" служит для обозначения всего, что может быть затребовано параллельно протекающими процессами, определяемыми с помощью модели транзакций. Наиболее распространенным ресурсом транзакций являются базы данных. Поэтому для наглядности и краткости упоминаются именно они, хотя все сказанное применимо и к другим видам ресурсов.

Для обеспечения высокого уровня пропускной способности современные системы управления транзакциями проектируются в расчете на максимально короткие транзакции. Обычно из практики исключаются транзакции, которые охватывают действия по обработке нескольких запросов; если же подобной ситуации избежать не удается, решения реализуются на основе схемы длинных транзакций. Чаще, однако, границы транзакции совпадают с моментами начала и завершения обработки одного запроса. Подобная транзакция запроса - весьма удачная модель, и многие среды поддерживают простой и естественный синтаксис ее описания.

Системные транзакции и бизнес-транзакции

Те транзакции, о которых до сих пор говорилось и которые упоминаются в большинстве случаев, называют системными.Именно такие транзакции поддерживаются СУБД и специализированными системами управления. Транзакция базы данных - это группа SQL -команд, обрамленная инструкциями начала и завершения транзакции. Если, скажем, четвертая от начала транзакции команда приводит к нарушению некоторого ограничения целостности, система должна аннулировать результаты выполнения первых трех команд и уведомить процесс-инициатор о неудачном завершении транзакции. Если все четыре команды обработаны успешно, их результаты становятся достоянием других процессов одновременно, а не каждый в отдельности. Технологии управления системными транзакциями в достаточной мере стандартизированы и доступны для разработчиков прикладных программ.

Однако смысл системных транзакций остается скрытым для пользователей бизнес-приложений. Например, с точки зрения посетителя банковского Web -портала, транзакция состоит из процедуры регистрации, выбора счета, задания суммы, определения вида операции и щелчка на кнопке "ОК". Подобная последовательность действий называется бизнес-транзакцией и должна обладать теми же свойствами ACID, что и аналогичная системная транзакция. Если пользователь прерывает выполнение сценария до нажатия кнопки "ОК", любые изменения в состоянии системы подлежат безусловной отмене; если транзакция завершается успешно, все ее промежуточные результаты фиксируются на уровне системы только после нажатия кнопки "ОК".

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

Если разрабатываемая система не предполагает функционирования многих параллельных процессов, без длинных транзакций можно обойтись. Длинные транзакции, кстати, не всегда являются таким уж большим злом, с их помощью часто удается избежать многих проблем, хотя их использование, как правило, приводит к меньшей масштабируемости системы. Дело в том, что процесс преобразования длинных транзакций в короткие часто оказывается крайне сложным и неоднозначным.

Тем не менее, во многих распределенных приложениях длинные транзакции стараются не применять. В таких случаях приходится принимать на себя ответственность за поддержку свойств ACID бизнес-транзакции, т.е. решать проблему обеспечения параллелизма в автономном режиме. Любое взаимодействие бизнес-транзакции с таким ресурсом транзакции, как база данных, выполняется внутри системной транзакции (тем самым обеспечивается целостность этого ресурса). Для правильной реализации бизнес-транзакций простого последовательного вызова системных транзакций недостаточно - программное приложение должно обеспечить надлежащие средства их "склеивания".

Свойства атомарности и устойчивости бизнес-транзакций поддерживать значительно легче, чем другие свойства ACID. Действительно, достаточно реализовать фазу фиксации бизнес-транзакции с помощью системной транзакции. Прежде чем предпринимать попытку фиксации всех внесенных изменений в наборе записей, бизнес-транзакция должна активизировать системную транзакцию. Только системная транзакция поможет гарантировать, что результаты всех модификаций будут зафиксированы цельно и надежно. Единственной потенциально сложной задачей в этом случае является поддержка точного набора измененных данных в течение всего жизненного цикла бизнес-транзакции.

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

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

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

В настоящий момент большинство разработчиков промежуточного программного обеспечения ( middleware ) включают сервис транзакций в свои системы.

Три проблемы

Каждый метод управления параллелизмом предназначен для решения некоторой конкретной задачи. Тем не менее, при обработке правильно составленных транзакций возникают ситуации, которые могут привести к получению неправильного результата из-за взаимных помех среди некоторых транзакций. Основные проблемы, возникающие при параллельной обработке транзакций, следующие:

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

Рассмотрим ситуацию, показанную в таблице 14.1.

Первая транзакция извлекает значение баланса, изменяет его и затем фиксирует. Проблема состоит в том, что вторая транзакция, которая также изменяет состояние баланса, делает это относительно "старого", еще не измененного первой транзакцией значения. Таким образом, при выполнении двух транзакций в указанном порядке изменения, выполненные первой транзакцией, будут просто утеряны.

Проблема незафиксированной зависимости

Проблема незафиксированной зависимости (таблица 14.2) появляется, если в некоторой транзакции осуществляется извлечение некоторых данных, которые в данный момент обновляются другой транзакцией, но это обновление еще не завершено. Таким образом, поскольку обновление еще не завершено, есть некоторая вероятность, что оно не будет завершено никогда (может быть выполнен откат транзакции, например). В таком случае в первой транзакции будут принимать участие данные, которых больше не существует.

В том случае, когда изменения, сделанные второй транзакцией, сразу становятся видны всем остальным (режим "грязного чтения" - см. ниже), первая транзакция читает "измененные" данные. Проведя вычисления, первая транзакция фиксирует результат. Вторая же транзакция производит откат изменений, т.е. фактически значения баланса, прочитанного первой транзакцией, никогда не существовало! Стоит отметить, что, несмотря на то, что вторая транзакция была отменена, результаты первой транзакции были уже зафиксированы и отменены не будут.

Проблема несовместимого анализа

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

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

Процедура подсчета идет "сверху вниз" по таблице счетов и суммирует их. Допустим, процедура была запущена в момент времени t1. Далее, в момент времени между t1 и t2 была запущена транзакция, которая состояла из двух действий - снять 100 рублей со счета Иванова и перечислить их на счет Яковлева (к этому моменту процедура суммирования уже учла сумму на счете Иванова, но до Яковлева еще не дошла). Транзакция была очень короткой. После того, как транзакция была успешно завершена, ее результаты стали "видны" первой процедуре. Таким образом, когда она дойдет до записи со счетом Яковлева, ей будет учтена сумма в 500 рублей. В результате сумма счетов в "банке" будет на 100 рублей завышена.

Блокировка

Описанные выше проблемы могут быть разрешены с помощью методики управления параллельным выполнением процессов под названием "блокировка".Ее основная идея очень проста: в случае, когда для выполнения некоторой транзакции необходимо, чтобы некоторый объект не изменялся непредсказуемо и без ведома этой транзакции (как это обычно бывает), такой объект блокируется.Таким образом, эффект блокировки состоит в том, чтобы заблокировать доступ к этому объекту со стороны других транзакций, а значит, предотвратить непредсказуемое изменение этого объекта. Следовательно, первая транзакция в состоянии выполнить всю необходимую обработку с учетом того, что обрабатываемый объект остается в стабильном состоянии настолько долго, насколько ей это нужно, и лишь затем снять блокировку.

Опишем функционирование блокировки более подробно.

Эти правила можно наглядно представить в виде матрицы совместимости (таблица 14.4) и интерпретировать ее следующим образом.

Рассмотрим некоторый объект р и предположим, что транзакция А блокирует объект р различными типами блокировки. Предположим также, что некоторая транзакция В запрашивает блокировку объекта р, что обозначено в первом слева столбце матрицы. Символ N обозначает конфликтную ситуацию (запрос со стороны транзакции В не может быть удовлетворен, и сама эта транзакция переходит в состояние ожидания), а Y - полную совместимость (запрос со стороны транзакции В удовлетворен). Очевидно, что эта матрица является симметричной.

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

Решение проблем параллелизма

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

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

Для нашего примера, поскольку мы собираемся изменять состояние объекта "Иванов", мы сначала должны наложить на него Х-блокировку. Соответственно, попытка наложения Х-блокировки другой транзакцией завершится успехом только после того, как первая транзакция блокировку снимет, а она это сделает только по завершении действия изменения. Таким образом, описанной проблемы просто не возникнет.

Следует отметить, что, хотя в таком случае результаты любых обновлений не будут утрачены, решение этой проблемы с помощью блокировки может привести к возникновению другой проблемы. Эта новая проблема называется тупиком,она рассматривается ниже в этом разделе.

Проблема незафиксированной зависимости

Проблема решается блокировкой объекта (аналогично предыдущему случаю).

Проблема несовместимого анализа

Проблема решается наложением S -блокировки на считываемые данные (в нашем случае это ВСЕ данные) и наложением Х -блокировок на два объекта, между которыми перемещаются средства. Проблема в этом случае только в том, что если транзакция по подсчету средств началась раньше, до ее завершения ни одна транзакция по переводу средств не сможет начаться (потому что ей придется наложить Х -блокировку на объекты, на которые уже наложена S -блокировка).

Тупиковая ситуация

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

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

В случае двух транзакций она может быть проиллюстрирована следующим образом: первая транзакция заблокировала ресурс R1 и пытается наложить блокировку на ресурс R2. В то же время вторая транзакция заблокировала ресурс R2 и пытается наложить блокировку на R1. Очевидно, что ни одна из таких транзакций успешно завершена быть уже не может. Возможны и более сложные случаи тупиков, при использовании большего числа ресурсов и при участии в процессе блокировки большего числа транзакций. При анализе тупиков часто используют модель в виде графа, называемую графом состояния ожидания ресурсов. Такой граф содержит вершины двух типов - потоки и запрашиваемые ими ресурсы и дуги двух типов - захват потоком ресурса и ожидание потоком ресурса. Для нашего примера граф состояния ожидания будет иметь следующий вид (рис. 14.1).

Желательно, чтобы при возникновении тупиковой ситуации система могла обнаружить ее и найти из нее выход. Для обнаружения тупиковой ситуации следует обнаружить цикл в диаграмме состояний ожидания,т.е. в перечне транзакций, которые ожидают окончания выполнения других операций. Поиск выхода из тупиковой ситуации состоит в выборе одной из заблокированных транзакций в качестве жертвы и отмене ее выполнения. Таким образом, блокировка снимается, а выполнение другой транзакции может быть возобновлено.

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

Обратите внимание, что транзакция-жертва признается некорректной и отменяется не из-за собственной некорректности. В некоторых системах предусмотрен автоматический перезапуск транзакции с самого начала при условии, что обстоятельства, которые привели к тупиковой ситуации, не повторятся вновь. А в других системах в программу, связанную с данной транзакцией, просто посылается сообщение о вызвавшей тупиковую ситуацию транзакции-жертве для обработки этой ситуации в самой программе. С точки зрения программирования приложений предпочтительнее первый из этих подходов. Но, несмотря на это, всегда рекомендуется решать данную проблему с точки зрения пользователя.

Способность к упорядочению

В предыдущих разделах были описаны некоторые основы, необходимые для введения ключевого понятия "способность к упорядочению",которое является общепринятым критерием правильности управления параллельной обработкой данных. Точнее говоря, чередующееся выполнение заданного множества транзакций будет верным, если оно упорядочено, т.е. при его выполнении будет получен такой же результат, как и при последовательном выполнении тех же транзакций.

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

Уровни изоляции

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

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

Уровней изоляции может быть несколько, например, в стандарте языка SQL - четыре, а в системе DB2 фирмы IBM поддерживается два уровня. Если вас в первую очередь беспокоит проблема достоверности информации, следует применять максимальный уровень изоляции. Следует, однако, иметь в виду, что это приведет к резкому снижению степени параллелизма операций и пропускной способности системы в целом. Поэтому лучше попытаться отыскать разумный компромисс. Кроме того, никто не заставляет использовать одинаковые уровни изоляции для всех транзакций - следует выбирать те, которые в наибольшей мере отвечают имеющимся потребностям.

Далее мы рассмотрим уровни изоляции транзакций, и для того, чтобы это сделать, приведем неформальное описание эффектов, возникающих при параллельной обработке, и установим соответствие между уровнями изоляции и возможностью возникновения этих эффектов.

Далее приведена таблица возможных нарушений для разных уровней изоляции (таблица 14.5).

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

Восстановление после сбоев. Откат транзакции

Важнейшая задача транзакционной обработки - атомарность - предполагает возможность отката сделанных изменений в случае если какое то из действий, составляющих транзакцию, закончилось неудачей. Другой важной характеристикой транзакции является долговечность, т.е. сохранение результатов транзакции после ее фиксации. Часто выполнение этих двух (вообще говоря, различных) задач объединяют в одном компоненте, называемом менеджером восстановления. Рассмотрим, однако, сначала первую задачу, а именно откат незавершенной транзакции. Первый из способов реализации этого механизма состоит в том, что изменения, которые делает транзакция в процессе работы, записываются не в долговременную память, а во временную. При этом в случае фиксации транзакции происходит перенос данных из временной памяти в основную, а в случае отката временная память просто очищается.

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

Другой проблемой является то, что если произошла необнаруженная (или обнаруженная) ошибка диска, данные завершенной транзакции могут быть потеряны. Поэтому часто применяют другой метод (иногда - совместно с первым), который состоит в журналировании операций, выполняемых транзакцией. При таком подходе все изменения, которые производит транзакция, вместо того чтобы записываться в долговременную память, записываются в журнал операций. В случае отката транзакций часть журнала, относящегося к прерванной транзакции, может быть просто уничтожена (часто в этом случае в журнал операций записывается специальная операция отката транзакции), а в случае фиксации транзакции операции из журнала должны быть "проиграны" на основной долговременной памяти.

Первое преимущество здесь состоит в том, что после фиксации транзакции не нужно сразу же переносить данные в долговременную память - это может делаться для нескольких завершенных транзакций сразу (причем операции в журнале при этом могут быть переупорядочены для увеличения быстродействия). Появляется еще одна полезная возможность - в случае повреждения по той или иной причине части данных в основном долговременном хранилище они могут быть восстановлены по журналу операций, вот почему говорилось о связи восстановления после сбоев и отката транзакции. Существенным минусом такого подхода является то, что появляется время, в течение которого данные, измененные зафиксированными транзакциями в основном долговременном хранилище, оказываются "старыми", неизмененными. Эта проблема может быть решена, например, блокировкой всех измененных, но не сброшенных из журнала операций данных.

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

До сих пор мы рассматривали транзакции, имеющие простую структуру, а именно состоящие просто из последовательности операций. Можно, однако, поговорить о возможности создания так называемых вложенных транзакций. Т.е. транзакции могут содержать другие транзакции - в таком случае транзакции образуют дерево. Это может быть удобным для решения ряда практических задач. В таком случае операции работы с транзакциями несколько видоизменяются - можно, например, откатить или зафиксировать не всю общую транзакцию, а лишь какую-то часть поддерева. Следует отметить, что, если речь идет о распределенной системе, большая часть проходящей в ней транзакций так или иначе будет содержать вложенные транзакции. Рассмотрим в качестве примера информационную систему, обеспечивающую заказ туристических туров. Последовательность действий при бронировании тура может быть, например, следующей:

Все вышеперечисленные действия представляют собой транзакцию с точки зрения нашей информационной системы - в самом деле, невыполнение любого из этих пунктов (кроме, может быть, оплаты) приводит к тому, что клиент от тура просто отказывается и все предварительно выполненные действия по другим пунктам должны быть отменены. С другой стороны, если не прошла оплата услуг, турагентство, опять же, должно отменить все другие действия. Но на самом деле каждое из описанных действий, в свою очередь, имеет сложную структуру. Так, например, если клиент и турагентство используют разные банки, должна пройти межбанковская транзакция по переводу денег. Таким образом, для распределенных систем необходим некий механизм для управления распределенными транзакциями. В качестве такого механизма часто используют так называемый протокол двухфазной фиксации транзакций.

Двухфазный протокол фиксации транзакций (2PC)

Суть его состоит в следующем.

Ниже приведен пример протокола работы координатора при фиксации транзакции.

Репликация данных

Задача репликации данных (под репликацией понимают управление копиями одних и тех же данных на нескольких узлах) при проектировании распределенных систем возникает достаточно часто. Происходи это по двум причинам. Первая причина - требование повышения производительности. Если между узлом, на котором хранятся данные, и узлом, который их обрабатывает, медленный (или ненадежный) канал, это может приводить к чрезмерно длительному времени работы системы. Если потребность в такого рода операциях возникает часто, то нужно задуматься либо о переносе данных "ближе" к узлам, в них нуждающимся, либо о создании локальных копий данных, т.е. их репликации. Другая причина, по которой часто используют репликацию, состоит в требовании повышения надежности системы путем резервного копирования части критичных данных.

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

Основные требования, которые предъявляются к системе репликации, обычно состоят в следующем: репликация должна быть прозрачной (обращение клиента к сервису не должно отличаться в случае использования сервисом данных реплики) и реплицированные данные должны быть целостными (пользуясь тем, что нам знакомо понятие транзакции, можно сказать, что реплицироваться должны только изменения для зафиксированных транзакций, т.е. только финальные, непротиворечивые состояния объектов).

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

Пассивная (primary-backup) репликация

Это простейший случай (тем не менее, широко распространенный), при котором изменение данных допускается только на одном узле (данные, размещенные на этом узле, называются мастер-копией), а на всех других узлах данные доступны только для чтения. Может использоваться как для резервного копирования данных, так и в большинстве информационных систем, в которых операции изменения данных сравнительно редки по отношению к операциям извлечения данных (при этом извлекаются данные большого объема) и могут быть сведены к операциям над мастер-копией.

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

Первый подход,и простейший, состоит в том, что (предполагается, что данных немного) весь массив данных по некоторому регламенту копируется на удаленные узлы. При этом подходе предполагается, что данные изменяются нечасто и на удаленных узлах не важна их высокая актуальность.

Второй подход называется репликацией на временных метках ( times-tamp-replication ). Он состоит в том, что любая транзакция, изменяющая данные, изменяет также и временную метку ( timestamp ) этих данных. Таким образом, у данных, которые изменялись позднее, будет большая временная метка, чем у данных, которые изменялись раньше. Зная время последнего удачного обмена данными, менеджер репликаций "снимает" все данные, измененные позднее, и передает на удаленный узел только их. Здесь нужно сделать два замечания.

Замечание первое:поскольку мы "видим" только данные, которые изменены зафиксированными транзакциями, кажется, что не будет нарушено условие консистентности реплики, однако это не так (вспомним пример с подсчетом баланса во время проведения платежа). Поэтому процесс, "снимающий" измененные данные, должен работать на уровне изоляции Serializable.

Замечание второе:представьте себе, что передача измененных данных осуществляется каждый час. В системе есть транзакция, работающая три часа (рис. 14.2). Поскольку данные, измененные долгой транзакцией, репликация увидит только в момент t3, а к тому времени передача данных уже закончена (и не раз!), есть шанс, что изменения, сделанные до t2, никогда не будут переданы на другие узлы. Выходов здесь может быть несколько - либо при завершении транзакции изменять все временные метки на время завершения транзакции, либо в момент начала репликации отслеживать все незавершенные транзакции (и время их начала), чтобы затем делать отступ назад по времени.

Третий подход состоит в передаче не данных, а журнала операций над этими данными (про журнал операций говорилось в разделе, посвященном восстановлению после сбоев). При этом подходе, опять же, каждой операции сопоставляется временная метка. Все операции, совершенные позднее последнего сеанса обмена, должны быть переданы и "проиграны" на других узлах. Поскольку операции пишутся в журнал линейно, в том числе и для незавершенных транзакций, подобного эффекта с потерей части изменений не возникает.

Следует отметить, что рассмотренный случай (пассивная репликация) имеет два более сложных варианта. Первый - когда каждый из узлов владеет собственной порцией данных, непересекающихся с другими, для которой узел владеет мастер-копией и реплицирует эту копию всем остальным узлам. В качестве примера можно рассмотреть информационную систему "офис-магазин". В офисе ведутся справочник товаров и прайс-лист, которые реплицируются в магазин в виде доступных только для чтения объектов; в свою очередь, магазин реплицирует в офис чековую ленту, которую офис может только просматривать и не может изменить. Второй вариант еще чуть более сложный. Он снова предполагает явное разделение прав владения между узлами, но уже на уровне одного класса сущностей. В качестве примера можно предложить информационную систему для регистрации на конференцию, причем построенную таким образом, что на каждом из терминалов системы могут зарегистрироваться участники, фамилии которых начинаются на определенную букву, скажем на первом терминале регистрируются участники с фамилиями, начинающимися с букв A, Б, В, на втором - Г, Д, Е и т.д. В любом случае, пассивная репликация предполагает выполнение одного очень важного правила: каждый из узлов может, не взаимодействуя с другими узлами, точно определить, может он редактировать данную сущность или нет. Причем, правами на редактирование каждой сущности может обладать только один из узлов системы. Это распределение прав не изменяется с течением времени. Очевидно, что рассмотренные варианты пассивной репликации годятся и для этих чуть более сложных случаев.

Активная репликация с блокировкой

Главное отличие от пассивной репликации состоит в том, что более чем один узел системы может претендовать на то, чтобы изменить объект. При репликации с блокировкой предполагается, что прежде чем изменять объект, узел запрашивает разрешение на это у центрального координатора (фактически, это является блокировкой объекта, поскольку как только такое разрешение получено, остальные запросы на этот же объект координатором будут отвергаться). После того, как объект изменен, это изменение реплицируется на все узлы, которые потенциально могут изменять этот объект, и только после этого блокировка объекта снимается. Делается это (репликация изменений) для того, чтобы исключить возможность возникновения проблемы "потерянного обновления". Например, узел А, предварительно заблокировав объект, изменил его, затем снял блокировку, не разослав изменений. Затем узел В, ничего не зная об изменениях, сделанных на А, изменил тот же самый объект - таким образом, изменения А оказались потерянными. Для реализации активной репликации с блокировкой необходим механизм блокировки объекта и механизм транзакций - репликация изменений на другие узлы должна объявляться транзакцией, только после ее выполнения блокировка объекта будет сниматься. Реализация репликации может быть такой же, как и в предыдущем случае.

Активная репликация без блокировки

В этом случае рассматривается система, в которой несколько узлов могут одновременно выполнять операции над одним и тем же объектом, не блокируя его и не дожидаясь репликаций о других изменениях. При применении такого метода возможны разнообразные эффекты типа "потерянного обновления" и т.д. Возможен эффект невозможности приема репликаций - например, мы разрешаем ведение справочника покупателей на двух разных узлах, при этом накладываем ограничение, что название покупателя должно быть уникально в пределах справочника. Достаточно независимо занести двух покупателей с одинаковыми именами (но, может быть, с различающимися остальными атрибутами!) на разных узлах, чтобы репликация между этими узлами оказалась невозможной из-за нарушения ограничения уникальностиТакого рода ситуации называются коллизиями. Существуют специальные методы их разрешения, но в общем случае задача, очевидно, неразрешима, потому что мы в любом случае должны оставить какое-то одно из введенных значений, потеряв второе (либо внести в них искусственные изменения) .

Несмотря на такие, казалось бы, фатальные проблемы, эта модель репликации тоже очень часто используется. Тонкость состоит в том, что в ряде случаев совсем не нужно редактировать сущности, достаточно их добавлять. По этой модели, например, устроено множество банковских платежных систем (практически все системы, не требующие online -соединения с процессинговым центром). В этом случае оконечные узлы формируют операции (выдачу и прием сумм), которые затем асинхронно пересылаются и обрабатываются банком или любым другим оператором.