Абстракт

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

1. ВВЕДЕНИЕ

Как следует из названия, LLT — это транзакция, выполнение которой занимает продолжительное время (возможно, часы или дни) даже когда её выполнение не прерывается другими транзакциями. Причиной длительного срока выполнения LLT по сравнению с большинством транзакций может быть необходимость доступа к множеству объектов базы данных, ресурсоёмкие вычисления, необходимость ожидать ввода данных пользователями или сочетание перечисленных факторов. В качестве примеров LLT можно привести транзакции, генерирующие ежемесячные выписки по банковскому счёту, транзакции по обработке страховых исков или транзакции по обработке статистики по целой базе данных [Gray81a].

Примечание редактора: список источников можно найти на страницах 258-259 в оригинале.

В большинстве случаев LLT существенно ухудшают производительность. Поскольку они являются транзакциями, система должна выполнять их как атомарные операции, чтобы сохранить согласованность базы данных [Date81a, Ullm82a]. Атомарность обычно обеспечивается тем, что система блокирует необходимые транзакции объекты до тех пор, пока не произойдёт фиксация, а она обычно выполняется в конце транзакции. Это существенно задерживает выполнение других транзакций, которым необходим доступ к объектам LLT. Если причиной долгого выполнения LLT является доступ ко многим объектам базы данных, это повышает вероятность других транзакций замедлиться из-за блокировок, их вероятность вступить в конфликт с LLT выше, чем с короткой транзацкцией. 

Кроме того, высокая продолжительность LLT вызывает увеличение доли неудавшихся транзакций. Как показывает [Gray81b], частота взаимоблокировок весьма чувствительна к «объему» транзакций, т. е. к числу объектов, доступ к которым получают транзакции. (Согласно [Gray81b], частота взаимоблокировок пропорциональна четвертой степени объема транзакции). Для LLT необходим доступ к большому числу объектов, а это означает высокую вероятность взаимоблокировок и, как следствие, неудавшихся транзакций. Из-за продолжительности LLT гораздо выше вероятность того, что во время их выполнения произойдет сбой системы, что приводит к еще большим задержкам и ошибкам в самих транзакциях. 

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

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

Рассмотрим в качестве примера приложение для бронирования авиабилетов. В базе данных (которая на самом деле является набором баз данных различных авиалиний) хранятся брони для авиабилетов. Предположим, транзакции T необходимо сделать несколько бронирований, и эта транзакция является LLT (скажем, ей требуется ввод данных от пользователя после каждого бронирования). В таком приложении вовсе нет необходимости в том, чтобы T блокировала все требуемые ей ресурсы на весь период своей работы. Например, по завершении бронирования сидения на рейс F₁ она может сразу же разрешить доступ к этому рейсу другим транзакциям. Иначе говоря, транзакцию T можно рассматривать как набор под-транзакций T₁, T₂, … T_n, каждая из которых бронирует одно место.

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

На этом примере видно, что был бы полезен механизм управления, который был бы менее жёстким, чем обычные атомарные транзакции, но при этом всё равно гарантировал бы выполнение компонентов LLT. Именно такой механизм мы и опишем в данной статье.

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

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

Если для саги T₁, T₂, … T_n определены отменяющие транзакции C₁, C₂, … C_n-1, система может гарантировать, что будет выполнена либо последовательность

T₁, T₂, … T_n

(что предпочтительно), либо последовательность

T₁, T₂, … T_j, C_j, … C₂, C₁,

где 0 ≤ j < n. (Обратите внимание, что другие другие транзакции могли заметить эффекты частичного исполнения саги. При исполнении компенсирующей транзакции C_j не предпринимаются никакие действия для уведомления или отмены транзакций, которые могли наблюдать результаты Tj до того, как они были скомпенсированы C_j).

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

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

Заметим, что у саг много общего с вложенными транзакциями [Mossa, Lync83a]. Однако есть два важных различия: 

(а) Саги допускают только два уровня вложенности: собственно сага и её транзакции.

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

Саги также можно рассматривать как специальный тип транзакций, описанных в [Garc83a, Lync83a]. Благодаря ограничениям, которые мы добавляем к представленному там более общему механизму, саги значительно проще реализовать и использовать на практике (да и проще понять).

Наш подход требует, во-первых, СУБД, поддерживающую саги, и, во-вторых, LLT, разбитую на последовательности транзакций. В оставшейся части статьи мы разберем эти составляющие более подробно. В разделах 2-7 мы рассмотрим реализацию механизма обработки саги. Мы начнем с того, как саги могут быть определены разработчиком приложения, а затем опишем поддержку саг системой. В первых разделах мы предполагаем, что компенсирующие транзакции могут сталкиваться только с системными сбоями. В разделе 6 мы рассмотрим другие сбои (например, багов в программах) в компенсирующих транзакциях. В данной работе мы обсуждаем только саги в централизованных системах, однако очевидно, что их также можно реализовать в распределенных базах данных.

Наконец, в разделах 8 и 9 мы рассмотрим структуру LLT. Вначале мы покажем, что нашу модель последовательного выполнения саги можно обобщить, включив в нее параллельное выполнение транзакций, и, следовательно, более широкий круг LTT. Затем мы обсудим некоторые стратегии, которыми разработчики приложений могут пользоваться для написания саг.

2. ОСНОВНЫЕ СОСТАВЛЯЮЩИЕ

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

Рассмотрим его работу более подробно. При начале саги приложение отправляет системе команду begin-saga. За этим следует последовательность команд begin-transaction и end-transaction, определяющих границы каждой транзакции. В промежутках между этими командами приложение отправляет обычные команды доступа к базе данных. Кроме того, пользователь может инициировать завершение транзакции, находясь внутри неё, с помощью команды abort-transaction. В этом случае завершается текущая транзакция, но не сага. Существует также команда abort-saga, которая завершает вначале текущую программу, а затем всю сагу (с предварительным выполнением компенсирующих транзакций). Наконец, команда end-saga фиксирует выполняемую в данный момент транзакцию (если таковая имеется), а затем завершает сагу.

Для большинства из этих команд требуются некоторые параметры. Команда begin-saga может возвращать программе идентификатор саги. Этот идентификатор можно отправлять системе при последующих вызовах от саги. Для команды abort-saga в качестве параметра указан адрес, по которому будет продолжаться выполнение саги после перерыва в выполнении. Каждый вызов end-transaction принимает идентификатор компенсирующей транзакции, которую необходимо выполнить для отмены завершаемой транзакции. Этот идентификатор состоит из имени и точки вхождения компенсирующей программы, а также параметров, необходимых для компенсирующей транзакции. (Предполагается, что каждая компенсирующая программа включает вызовы begin-transaction и end-transaction. Команды abort-transaction и abort-saga внутри компенсирующей транзакции не допускаются.) Наконец, параметром команды abort-saga может быть идентификатор точки сохранения, о котором будет сказано ниже.

Важно, что параметры, которые могут в будущем понадобиться соответствующим компенсирующим транзакциям, можно хранить в самой базе данных. В этом случае системе не обязательно передавать параметры напрямую; компенсирующая транзакция может просто прочитать их из базы данных при начале работы. Следует также заметить, что в случае, когда команда end-saga завершает и последнюю транзакцию, и сагу, компенсирующая транзакция для последней транзакции не требуется. Если же выполняется отдельный вызов end-transaction, то для него требуется идентификатор компенсирующей транзакции.

В некоторых случаях допустимо иметь возможность указывать точки сохранения с помощью команды save-point. Эту команду можно вызывать между транзакциями. Она сообщает системе, что необходимо сохранить состояние выполняемого приложения, и возвращает идентификатор точки сохранения; в дальнейшем выполнение можно продолжить с этой точки. Такие точки сохранения позволяют сократить объём работы, который нужно проделать при сбое в саге или в системе. Вместо того, чтобы компенсировать все транзакции незавершенной саги, они позволяют компенсировать только транзакции, выполненные после последней точки сохранения, а затем перезапустить сагу.

Если в приложении используются точки сохранения, то становится возможна, например, следующая последовательность выполняемых транзакций: T₁, T₂, C₂, T₂, T₃, T₄, T₅, C₅, C₄, T₄, T₅, T₆. (Т. е. система успешно выполнила T₂, после чего произошёл сбой. Перед T₂ была создана точка сохранения, но для того, чтобы к этой точке вернуться, система вначале отменила T₂, выполнив C₂. После этого выполнение саги возобновилось и T₂ была выполнена повторно. Второй сбой произошёл после выполнения T₅.) Если такая последовательность допускаетсся, то данное выше определение допустимых последовательностей выполнения необходимо дополнить. Если же последовательности с частичным откатом не допускаются, то либо система должна запрещать использование точек сохранения, либо точки сохранения должны создаваться автоматически в начале (или в конце) каждой транзакции.

Модель, которую мы описывали до сих пор, имеет довольно общий характер; в некоторых случаях предпочтительнее использовать более специальную модель. Её мы опишем в разделе 5.

3. НАДЁЖНОЕ ХРАНЕНИЕ КОДА

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

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

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

Такой подход допустим, если разработчикам саги можно доверять, и если обновления происходят не слишком часто. В противном случае следует хранить код саги как объект или несколько объектов базы данных. Тогда его восстановление происходит автоматически. Единственный недостаток этого подхода в том, что для него необходима СУБД, позволяющая работать с крупными объектами, т. е. с кодом. В некоторых системах это невозможно по разным причинам: модель данных может не допускать использование крупных «неструктурированных» объектов, диспетчер буфера может не допускать использование объектов крупнее одного буфера и т. д. 

Если у СУБД есть доступ к управлению кодом, то проблему надежного хранения кода саг решить довольно просто. В первой транзакции саги, T₁, в базу данных записываются все будущие транзакции (как компенсирующие, так и обычные), и сага готова к запуску. Компенсирующая транзакция для T₁, C₁, должна просто удалить эти объекты из базы данных. Транзакции можно также определять пошагово. Например, компенсирующую транзакцию C_i не обязательно вводить в базу данных до тех пор, пока не будет готова к фиксации соответствующая транзакция T_i. Такой подход несколько более сложен, но он позволяет избавиться от ненужных операций с базой данных.

4. ВОССТАНОВЛЕНИЕ С ВОЗВРАТОМ

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

Внутри СУБД за управление саг ответственен компонент выполнения саги (saga execution component, SEC). Этот компонент вызывает традиционный компонент выполнения транзакции (transaction execution component, TEC), который ответственен за выполнение отдельных транзакций. Принципы работы SEC и TEC похожие: SEC выполняет последовательность транзакций как единое целое, а TEC выполняет набор действий как единое (атомарное) целое. Кроме того, оба компонента записывают действия саг и транзакций в журнал. Для наших целей удобно объединить эти два журнала в один. Предположим также, что в интересах надежности этот журнал дублируется (duplexed). Следует заметить, что для SEC не требуется реализовывать управление параллелизмом, поскольку его транзакции могут чередоваться с другими транзакциями.

Все команды саг и действия с базой данных выполняются через SEC. Каждая команда саги (например, begin-saga) перед выполнением записывается в журнал. Все параметры команды (напр. идентификатор компенсирующей транзакции в команде end-transaction) также записываются в журнал. Команды begin-transaction и end-transaction, а также все действия с базой данных направляются в TEC, где обрабатываются обычным образом [Gray78a].

Когда SEC получает команду abort-saga, инициируется восстановление с возвратом. В качестве примера рассмотрим сагу, в которой выполнены транзакции T₁ и T₂, а во время выполнения транзакции T₃ в SEC отправляется команда abort-saga. Там эта команда записывается в журнал (на случай сбоя во время процедуры отката), а затем в TEC поступает инструкция отменить текущую транзакцию T₃. Отмена этой транзакции выполняется традиционными методами: например, сохранением в базу данных значений предшествующего состояния, которые хранятся в журнале. 

Далее в SEC происходит сверка с журналом и начинается выполнение компенсирующих транзакций C₂ и С₁. Если параметры для этих транзакций хранятся в журнале, они оттуда считываются и передаются в вызов. Далее эти транзакции выполняются обычным образом, а время начала и время фиксации записывается TEC в журнал. (Если во время выполнения происходит сбой системы, на основе этой информации мы сможешь определить, какую работу осталось проделать). После фиксации C₁ выполнение саги завершается. В журнал вносится запись, аналогичная той, которую генерирует команда end-saga.

Журнал также используется при восстановлении после сбоев. Когда происходит сбой, вначале вызывается TEC, чтобы обработать находящиеся в ожидании транзакции. После того, как все транзакции либо отменены, либо зафиксированы, в SEC анализируется состояние каждой саги. Если для саги в журнале есть соответствующие записи begin-saga и end-saga, это значит, что сага выполнена и дополнительных действий предпринимать не нужно. Если запись end-saga отсутствует, происходит отмена саги. Анализ журнала показывает SEC, какая именно транзакция была последней успешно выполненной и не компенсированной. Для этой транзакции и всех предшествующих выполняются компенсирующие транзакции.

5. ВОССТАНОВЛЕНИЕ БЕЗ ВОЗВРАТА

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

Чтобы лучше понять работу SEC в подобной ситуации, рассмотрим следующий сценарий. Некоторая сага выполнила транзакции T₁, T₂, команду создания точки сохранения и транзакцию T₃. Предположим, при выполнении транзакции T₄ происходит системный сбой. После сбоя вначале должно быть выполнено восстановление с возвратом до точки сохранения (т. е. отмена T₄ и выполнение C₃). Затем в SEC проверяется наличие кода для выполнения T₃, T₄, …, в журнал вносится запись о повторном запуске саги, после чего происходит собственно запуск. Такую последовательность событий мы называем смешанным восстановлением (backward/forward recovery).

Как уже говорилось во втором разделе, использование автоматических точек сохранения в начале каждой транзакции упрощает чистое восстановление без возврата. Если же запретить использование команд abort-saga, необходимость в восстановлении с возвратом отпадает полностью . (Команды abort-transaction при этом по-прежнему допускаются). Преимущество такого подхода в том, что для него не нужно писать компенсирующие транзакции — а их для некоторых приложений создать проблематично (см. Раздел 9). 

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

При таком подходе SEC становится простым персистентным средством выполнения транзакций, аналогичным персистентным механизмам передачи сообщений [Hamm80a]. После каждого сбоя SEC передает инструкцию в TEC отменить последнюю транзакцию в состоянии выполнения для каждой активной саги, а затем перезапускает сагу с точки, где началось выполнение транзакции. 

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

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

В терминологии операционных систем модель файла транзакций, которую мы только что описали — это простой EXEC или SCRIPT. С помощью такого персистентного SCRIPT-а в операционной системе можно обеспечить успешное выполнение команд (если каждая команда выполняется как транзакция). Обычная задача по обработке и распечатке текста состоит из нескольких шагов (в UNIX это обработка уравнений, troff, печать). Каждое действие генерирует один или несколько файлов, которые затем используются следующими шагами. Персистентный SCRIPT позволяет пользователю дать системе крупное задание и пойти заниматься своими делами, пока система его выполняет.

6. ПРОЧИЕ ОШИБКИ

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

Чтобы избежать таких ситуаций, можно использовать отказоустойчивые методики, например, блоки восстановления [Ande81a, Horn74a]. Блок восстановления — это дополнительный блок кода, существующий на случай, если в основном блоке обнаруживается ошибка. При обнаружении ошибки система восстанавливается к исходному состоянию и выполняется дополнительный блок. Этот вторичный блок выполняет ту же задачу, что и первичный, но другим способом, тем самым сокращая вероятность возникновения аналогичной ошибки.

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

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

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

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

7. РЕАЛИЗАЦИЯ САГ ПОВЕРХ СУЩЕСТВУЮЩЕЙ СУБД

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

Для создания такой саги необходимо решить две задачи. Во-первых, команды саги в коде приложения должны быть вызовами подпрограмм (а не системными вызовами). (Подпрограммы загружаются вместе с кодом приложения.) Каждая подпрограмма должна хранить в базе данных всю информацию, которую SEC хранила бы в журнале. Например, при такой реализации подпрограмма begin-saga должна хранить идентификатор саги в таблице базы данных с активными сагами. Подпрограмма save-point должна вызывать сохранение состояния системы (или наиболее важную составляющую этого состояния) в аналогичной таблице базы данных. Подобным же образом подпрограмма end-transaction должна вводить в таблицу (или таблицы) базы данных идентификатор завершающей транзакции и компенсирующую транзакцию, а затем выполнять системный вызов end-transaction (который обрабатывается TEC).

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

Во-вторых, необходимо реализовать специальный процесс для реализации остальных функций SEC: демон саги (saga daemon, SD), постоянно работающую управляющую программу. После сбоя операционная система должна ее восстанавливать. Эта программа затем сканирует таблицы саг, чтобы определить состояние находящихся в ожидании саг. Такое сканирование реализуется через отправку транзакции в базу данных. TEC выполняет такую транзакцию только после завершения восстановления транзакций; благодаря этому полученные SD данные всегда согласованные. Как только SD получает информацию о состоянии находящихся в ожидании саг, запускаются необходимые компенсирующие или обычные транзакции — так же, как это делает SEC после восстановления системы. При этом необходимо избегать вмешательства в работу саг, запущенных непосредственно после сбоя но до отправки запроса SD в базу данных. 

Когда TEC завершает транзакцию (например, из-за взаимоблокировки или отмены пользователем), он может также завершить работу процесса, запустившего транзакцию. В обычной системе это не вызывает осложнений, но в случае с сагами сага оказывается незавершенной. Если у TEC нет возможности напрямую передать сообщение об этом в SD, то SD должен периодически сканировать таблицу саг и проверять, не возникла ли такая ситуация, чтобы иметь возможность сразу же ее исправить.

Кроме того, работающая сага может напрямую отправлять запросы в SD. Например, при выполнении подпрограммы abort-saga отправляется запрос в SD а затем (при необходимости) выполняется команда abort-transaction.

8. ПАРАЛЛЕЛЬНЫЕ САГИ

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

Условимся, что процесс саги (родительский) может создавать новые процессы (дочерние), выполняемые параллельно с ним. Запрос на создание таких процессов аналогичен запросу fork в UNIX. Условимся также, что система может предоставлять вызов join для объединения процессов в саге.

Для параллельных саг восстановление после сбоев с возвратом происходит так же, как и для последовательных саг. Внутри каждого процесса параллельной саги транзакции компенсируются (или отменяются) в обратном порядке, как и в последовательной саге. Кроме того, все компенсирующие транзакции дочернего процесса должны происходить до компенсирующих транзакций в родительском процессе, выполненных до создания (через fork) дочернего процесса. (Заметим, что ограничения на порядок компенсации накладываются только порядком выполнения транзакций внутри процесса, а также вызовами fork и join. Если T₁ и T₂ выполнялись в параллельных процессах, и в T₂ есть данные, записанные T₁, то компенсация T₁ не требует предварительной компенсации T₂.)

В отличие от восстановления с возвратом после системного сбоя, восстановление с возвратом после сбоя саги усложняется при использовании параллельных саг, поскольку саги могут состоять из нескольких процессов, каждый из которых необходимо завершить. Для облегчения этой задачи все операции fork и join для процессов удобнее всего выполнять через SEC, поскольку тогда в этом компоненте будут данные о структуре саги. Благодаря этому SEC сможет завершить все процессы саги, если один из процессов саги запросит операцию abort-saga, а также отменить все находящиеся в ожидании транзакции и компенсировать все зафиксированные транзакции.

Дополнительная сложность при восстановлении без возврата возникает из-за возможности существования «несогласованных» точек сохранения. Рассмотрим в качестве примера сагу на схеме 8.1. Здесь каждый прямоугольник представляет из себя отдельный процесс; внутри прямоугольника находится последовательность транзакций и точек сохранения, которую этот процесс выполняет. Нижний процесс был создан через fork после фиксации T₁. Предположим, что в данный момент выполняются транзакции T₃ и T₅, и что точки сохранения были выполнены перед T₁ и T₅. 

Затем произошел системный сбой. После него необходимо перезапустить верхний процесс с точки перед T₁. Использовать точку сохранения второго процесса здесь не получится, поскольку этот процесс зависит от выполнения транзакции T₁, которую необходимо компенсировать.

Эта проблема называется каскадными откатами. Ее уже анализировали применительно к ситуации, где процессы передают информацию друг другу сообщениями [Rand78a]. Там удалось найти согласованное множество точек сохранения (в случаях, где таковое существует) посредством анализа зависимостей точек сохранения. Затем с помощью этого согласованного множества можно перезапустить процесс. В случае с параллельными сагами ситуация еще проще, поскольку зависимости между точками сохранения определяются только операциями fork и join и порядком транзакций и точек сохранения внутри процесса.

Для поиска согласованного множества точек сохранения SEC должен иметь доступ к информации об операциях fork и join. Эту информация хранится в журнале, а анализ ее происходит при восстановлении после сбоя. SEC выбирает последнюю точку сохранения внутри каждого процесса саги, такую, что ни одна транзакция до этой точки ещё не была компенсирована. (Транзакция считается предшествующей точке сохранения в том случае, если при замене точки сохранения другой транзакцией компенсация нашей транзакции происходит после компенсации этой новой транзакции). Если в процессе отсутствует такая точка сохранения, откатить необходимо весь процесс. Если точка сохранения в процессе есть, можно выполнить необходимые восстановления с возвратами и перезапустить процесс.

9. ПРОЕКТИРОВАНИЕ САГ

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

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

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

В общем случае проектирование компенсирующих транзакций для LLT — сложная проблема. (Например, если транзакция выстреливает ракету, компенсировать это действие невозможно.) Но в частных случаях вся сложность может сводится к написанию самих транзакций, и тогда всё зависит только от того, насколько сложны они. В [Gray81a] Грей отмечает, что для многих транзакций не нужно специально писать компенсирующие транзакции, так как они уже есть по умолчанию внутри самого приложения. В особенности часто это наблюдается, когда транзакция моделирует реальное действие, которое можно отменить — например, бронирование автомобиля или отправка грузового ордера. В этих случаях написание и компенсирующей, и обычной транзакции происходит похожим образом: разработчик должен написать код, выполняющий требуемое действие, и при этом соблюдающий ограничения целостности базы данных. 

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

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

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

Другой прием, с помощью которого можно преобразовать LLT в сагу — это хранение временных данных LLT в самой базе данных. Рассмотрим в качестве примера LLT L с тремя под-транзакциями T₁, T₂ и T₃. В T₁ выполняются некоторые действия и со счета в базе данных снимается некоторое количество денег. Значение суммы хранится во временной локальной переменной, и используется в T₃, где деньги переводятся на другой счет (или счета). После завершения T₁ база данных оказывается в несогласованном состоянии, поскольку снятая со счета сумма «отсутствует», ее нет ни на одном счете в базе данных. Поэтому L не может быть сагой. Если бы она была сагой, то в промежутке между T₁ и T₃ любая транзакция, которой нужен доступ ко всем средствам, недосчиталась бы снятой со счета суммы денег. Если же L выполняется как обычная транзакция, то между T₁ и T₃ никакие другие транзакции выполнены быть не могут. Это обеспечивает согласованность за счет более низкой производительности.

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

Записывать недостающие средства в базу данных может иметь смысл даже если в L нет транзакции T₂. Правда, в этом случае L снимает блокировку временного хранилища после T₁ и тут же снова ее запрашивает в T₃. Из-за этого издержки выполнения L возрастают, но зато транзакции, которым необходим доступ к временному хранилищу, можно будет выполнить раньше, сразу после T₁. Представьте, что кому-то нужно отксерокопировать огромный объем текста, а ксерокс только один; тогда этот человек будет периодически пропускать других людей с небольшими объемами, т. е. периодически открывать доступ к ограниченному ресурсу (ксероксу или информации в базе данных). 

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

10. ЗАКЛЮЧЕНИЕ

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

Перевод Михаила Ланкина