Реализация транзакций.

Интерфейс транзакций

Интерфейс для системы, поддерживающей транзакции: begin-transaction, read, write и commit:

proc transfer (debit, credit, amount)

tid = begin-transaction();

d = read(debit, tid);

с = read(credit, tid);

nd = d - amount;

nc = с + amount;

write(nd, debit, tid);

write(nc, credit, tid);

commit (tid);

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

Хранение версии

В системах памяти, которые мы изучали до сих пор, новое значение элемента данных перезаписывало старое значение (например, в ОЗУ, на диске и т.п.). В терминах транзакции перезапись − commit: если система попадет в аварию после перезаписи, старое значение будет утеряно, и система не сможет вернуться назад. Кроме того, параллельная активность может наблюдать это изменение. Поэтому системы памяти, которые обеспечивают семантику перезаписи, не подходят для осуществления транзакций, так как мы хотим сделать много изменений и сохранить их все сразу или совсем не сохранять. Вместо этих систем нам необходима память, для которой можно только добавлять значения в конец. Мы называем это хранением версии.

Например: значение переменной − это не последнее записанное значение, а список всех значений; некоторые из них − старые значения, одно − текущее значение, а другие − предварительные значения.

При использовании хранения версии легко контролировать момент перезаписи:

1. Пометьте каждую транзакцию уникальным идентификатором (например, tid).

2. Для каждой транзакции создайте запись "подтверждения", в которой будет указано, завершена ли транзакция, прервана или находится на этапе подготовки.

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

Теперь операции чтения и записи внутри транзакции t работают следующим образом:

• Read возвращает самое последнее значение, которое подтверждено транзакцией, или самое последнее записанное значение, имеющее tid t.

• Write добавляет атомарным образом новое значение и tid = t к концу списка (например, используя стабильную память на диске).

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

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

read(address, tid) //перейти в конец списка "address"

//для каждой версии v

if v.tid = tid

then begin

temp = v.val; //просмотр "подтверждающей записи" для версии v;

if committed then return temp

end;

next;

write(address, val, tid) //перейти в конец списка "address"

//добавить новую версию v

v.val = val;

v.tid = tid;

Операция commit атомарным образом изменяет состояние записи "подтверждения" с "предварительная" на "подтвержденная".

Пример: transfer (А, В, 5). Счета А и В с историей значений; каждое значение помечено своим идентификатором транзакции tid, вместе с таблицей "подтверждающих" записей о состоянии каждой транзакции.

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

Пример: другой transfer (А, В, 5) с аварией до обновления В.

До сих пор эта схема работала только с восстановлением после отказа, и не учитывала параллелизм. Расширим эту схему, чтобы работать с параллелизмом, установив дополнительные правила относительно того, какие значения могут читаться какой из транзакций. Простая схема присваивает порядковый номер каждой транзакции (вместо простого уникального идентификатора), и предписывает, чтобы транзакция п+1 не начиналась, прежде чем не будет закончена транзакция п. Это правило гарантирует упорядочиваемость, так как все транзакции выполняются друг за другом; параллелизм отсутствует!

Но можно сделать лучше. Следующая схема упорядочивает транзакции, которые используют совместные переменные, а транзакции, которые не имеют совместных переменных, могут выполняться параллельно. Основная идея состоит в том, чтобы отметить версию переменной, от которой зависит транзакция: метка begin-transaction маркирует атомарным образом все переменные, которые могут измениться при создании незафиксированной записи в версии. Псевдокод для mark, read и write следующий:

read(address, tid) //перейти в конец списка "address"

//для каждой версии v

if (v.tid >= tid) //пропустить последующие транзакции

next;

if v.tid == tid and v.val == null //пропустить транзакции, в которых значение //переменной не установлено

next

else begin

temp = v.val; //просмотр "подтверждающей записи" для версии v;

if committed then return temp;

if uncommitted then block

end;

next;

mark(address, tid) //перейти в конец списка "address"

//добавить новую версию v

v.val = null;

v.tid = tid;

write(address, val, tid) //перейти в конец списка "address"

//найти версию v, такую что

v.tid = tid;

v.val = val;

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

Пример: авария при параллельном выполнении transfer (А, В, 5) и transfer (В, С, 5).

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

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

Журнал

Мало систем предлагает хранение версии. Фактически все системы, которые мы изучали до сих пор, имели семантику перезаписи (например, RAM и диски). Однако, мы можем создать хранение версии, используя журнал. Журнал − это структура данных, предназначенная для добавления только в конец. Каждая операция изменения (запись, создание, и т.д.) добавляет элемент в конец журнала. Добавленный элемент содержит достаточное количество информации для того, чтобы отменить операцию или сделать ее заново (например, имя переменной, tid, прежнее значение, новое значение и операцию). Журнал помнит все. Можно построить копию объекта, листая журнал и повторяя все действия. Мы можем рассматривать журнал, как особую реализацию версионного хранения. Он объединяет списки всех переменных. Для того, чтобы гарантировать стабильность и безошибочное заполнение журнала, требуется, чтобы он хранился, например, в стабильной памяти.

Если каждая операция read будет сканировать весь журнал, то производительность станет крайне низкой. Однако, объединяя журнал с перезаписью, можно сделать транзакции эффективными. Пусть вместо хранения журнала на одном диске, система имеет два диска: один для журнала (диск журнала) и один − для текущего состояния базы данных (диск базы данных, БД). Диск журнала содержит информацию по созданию, а диск БД − только кэш с последней информацией. Мы можем отбрасывать диск БД и восстанавливать его по содержанию диска журнала.

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

• Операции write сначала добавляют запись в журнал. Запись содержит tid, имя переменной, прежнее значение и новое значение. После успешного помещения этой записи в журнал, можно обновлять БД.

• При подтверждении транзакции внесите в журнал запись, регистрирующую, что транзакция tid подтверждена.

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

• При ошибке, на основе журнала восстановите состояние в момент ошибки. Затем вернитесь, и для каждого элемента без записи о подтверждении транзакции, отмените любые изменения, которые транзакция с ним сделала.

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

Мы можем сократить время, затрачиваемое на просмотр журнала в течение восстановления, регистрируя время от времени контрольную запись (checkpoint record) со списком всех активных транзакций. Мы можем дополнительно улучшить производительность во время выполнения, добавляя буферный кэш. Пример: System R.

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

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

Самый простой подход состоит в том, чтобы установить блокировки всех переменных перед использованием любой из них. Это − простое правило блокировок: транзакция должна просто установить блокировки всех объектов, которые должны читаться или записываться, перед любым выполнением операций чтения или записи. Простое правило блокировок четко гарантирует упорядочиваемость транзакций. Давайте примем, что у нас две транзакции, Т₁ и Т₂, разделяют две переменные, х и у. Одна из них, скажем, Т₁, первой устанавливает блокировку на х и у. Поэтому Т₂ не может выполняться до того момента, пока Т₁ еще не закончена. Из этого получается последовательный список: правило гарантирует упорядочиваемость.

Транзакции должны быть аккуратными по отношению к порядку, в соответствии с которым они запрашивают блокировки. Предположим, что Т₁ сначала устанавливает блокировку на х, а затем на у; если Т₂ запрашивает блокировки в противоположном порядке (сначала у, а затем х), то получится тупик. (Если Т₁ установит блокировку на х, а Т₂ − на у, то ни одна транзакция не может продолжаться.) Чтобы избежать тупика, операционная система может пронумеровать блокировки и предписывать транзакциям, чтобы они получали блокировки в порядке возрастания. (Существуют другие схемы предотвращения тупиков).

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

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

Это правило называется двухфазной блокировкой, потому что оно работает в два этапа: на первом этапе реализуются все полученные блокировки, а на втором этапе − все блокировки снимаются.