Транзакции. Свойства ACID транзакций. Управление параллельностью. Блокировки. Строгий протокол двухфазной блокировки.

 

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

 

Транзакции обладают (или должны обладать) четырьмя важными свойствами (ACID):

- Неразрывность (atomicity). Транзакции неразрывны (выполняются по принципу «все или ничего»).

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

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

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

 

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

 

Очевидно, что с точки зрения организации параллельной работы наибольший интерес представляют такие операции, как выборка информации из базы данных и обновление базы данных; иными словами, любая транзакция может рассматриваться как состоящая из последовательности только указанных операций. Если А и В — параллельно выполняемые транзакции, то проблемы могут возникнуть, если в ходе выполнения А и B требуется прочитать или записать один и тот же объект базы данных, например, кортеж t. При этом возникают четыре возможные конфликтные ситуации, которые описаны ниже.

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

- Конфликт типа RW. В транзакции А выполняется чтение кортежа t, а затем в транзакции В возникает необходимость записать кортеж t. Если транзакции В будет разрешено выполнить эту запись, то может возникнуть проблема анализа несовместимости, поэтому можно утверждать, что проблема анализа несовместимости вызвана конфликтами типа RW. Если транзакция В выполняет свою операцию записи, а затем транзакция А снова считывает значение t, то последняя обнаруживает значение, отличное от того, что было прочитано раньше; такое стечение обстоятельств принято обозначать как неповторяемое чтение.

- Конфликт типа WR. В транзакции А выполняется запись кортежа t, а затем в транзакции В возникает необходимость прочитать t. Если транзакции В будет разрешено выполнить эту операцию чтения, то (как показано на рисунке 5, с учетом того, что транзакции А и В поменялись ролями) может возникнуть проблема зависимости от незафиксированных обновлений. Чтение в транзакции В, если оно будет разрешено, называется грязным чтением (dirty read).

- Конфликт типа WW. В транзакции А выполняется запись кортежа t, а затем необходимость выполнить запись кортежа t возникает в транзакции В. Если транзакции В будет разрешено выполнить эту запись, то может возникнуть проблема потерянного обновления. Запись в транзакции В, если она будет разрешена, называется грязной записью (dirty write).

 

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

В его основе лежит простая идея — если для некоторой транзакции А требуется гарантия, чтобы определенный объект, в котором она заинтересована, не изменился каким-то образом без ее ведома, она приобретает блокировку на этот объект.

Принцип работы блокировок

1. Прежде всего, предположим, что в системе поддерживаются блокировки двух типов: исключительные блокировки (X — exclusive) и разделяемые блокировки (S — shared). Блокировки X и S иногда именуются, соответственно, блокировками записи и блокировками чтения.

2. Если транзакция А владеет исключительной блокировкой (X), то запрос от некоторой другой транзакции В на получение блокировки кортежа t любого типа не может быть немедленно удовлетворен.

3. Если транзакция А владеет разделяемой блокировкой (S) кортежа t, то выполняются следующие условия:

- запрос некоторой другой транзакции В на получение блокировки X кортежа t не может быть немедленно удовлетворен;

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

 

Данные правила можно успешно подытожить с помощью матрицы совместимости типов блокировок.

В этой матрице «N» указывает на конфликт (запрос транзакции В не может быть немедленно удовлетворен), а «Y» указывает на совместимость (запрос транзакции В может и должен быть немедленно удовлетворен). Очевидно, что эта матрица является симметричной.

Строгий протокол двухфазной блокировки

1) Транзакция, в которой требуется выполнить выборку кортежа, должна вначале приобрести блокировку S на этот кортеж.

2) Транзакция, в которой требуется выполнить обновление кортежа, должна вначале приобрести X блокировку на этот кортеж. В ином случае, если она уже владеет блокировкой S на этом кортеже, то эта транзакция должна расширить, или повысить уровень блокировки S до уровня X.

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

Система должна обеспечить, чтобы транзакция В не ожидала до бесконечности (такая ситуация называется активным тупиком — livelock, или истощением ресурсов — starvation).

4) Блокировки X освобождаются по завершении транзакции (COMMIT или ROLLBACK). Блокировки S также обычно освобождаются в это же время.

 

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

Для обнаружения взаимоблокировки необходимо определить наличие цикла в графе ожидания (Wait-For Graph). Так называется граф, который, неформально выражаясь, показывает «кто кого ожидает». Чтобы разорвать взаимоблокировку, необходимо выбрать одну из транзакций, участвующих во взаимоблокировке (т.е. одну из транзакций, которые входят в состав цикла в графе ожидания), в качестве «жертвы» и выполнить ее откат, что позволяет освободить ее блокировки и дать возможность другим транзакциям продолжить свою работу.

 

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

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

Краткое описание рассматриваемого подхода к предотвращению взаимоблокировок:

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

- Если транзакция А запрашивает блокировку на кортеже, который уже заблокирован транзакцией В, то выполняются описанные ниже действия в зависимости от применяемого варианта.

§ «Ожидание-отмена» (Wait-Die). Если выполнение транзакции А началось раньше, чем В, А переходит в состояние ожидания; в противном случае происходит ее отмена. Это означает, что осуществляется откат и перезапуск транзакции А.

§ «Отмена-ожидание» (Wound-Wait). Если выполнение транзакции А началось позже, чем В, она переходит в состояние ожидания; в противном случае, она отменяет В. Это означает, что происходит откат и перезапуск транзакции В.

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