|
Временные метки (Multiversion Timestamp Ordering, MVTO)
В [6] Бернштейн и Гудмен пишут, что наиболее ранний известный им алгоритм работы планировщика для версионной СУБД основан на временных метках. Этот планировщик обрабатывает операции таким образом, чтобы суммарный результат выполнения операций был эквивалентен последовательному выполнению транзакций. При этом их порядок задается порядком временных меток, которые получают транзакции во время старта. Временные метки также используются для идентификации версий данных при чтении и модификации – каждая версия получает временную метку той транзакции, которая ее записала. Планировщик не только следит за порядком выполнения действий транзакций, но также отвечает за трансформацию операций над данными в операции над версиями, т.е. каждая операция вида “прочитать элемент данных x”, должна быть преобразована планировщиком в операцию: “прочитать версию y элемента данных x”.
Для описания алгоритма введем ряд обозначений. Временную метку, полученную транзакцией ti в начале ее работы, будем обозначать как ts(ti). Операция чтения транзакцией ti элемента данных x будет обозначаться как ri(x). Для обозначения того, что транзакция ti читает версию элемента данных x, созданную транзакцией tk, будем писать ri(xk). Для обозначения того, что транзакция ti записывает версию элемента данных x, будем использовать запись wi(x).
Теперь опишем алгоритм работы MVTO-планировщика:
1. Планировщик преобразует операцию ri(x) в операцию ri(xk), где xk – это версия элемента x, помеченная наибольшей временной меткой ts(tk), такой что ts(tk) ≤ ts(ti).
2. Операция wi(x) обрабатывается планировщиком следующим образом.
Если планировщик уже обработал действие вида rj(xk), такое что ts(tk) < ts(ti) < ts(tj), то операция wi(x) отменяется, а ti откатывается.
В противном случае wi(x) преобразуется в wi(xi).
3.Завершение транзакции ti (commit) откладывается до того момента, когда завершатся все транзакции, записавшие версии данных, прочитанные ti.
Многоверсионный вариант двухфазного протокола синхронизации (Multiversion Two-Phase Locking Protocol, MV2PL)
В этом разделе мы рассмотрим вариант широко известного двухфазного протокола синхронизации транзакций (2PL), адаптированного для применения в версионной базе данных.
Рассматривая алгоритм работы MVTO-планировщика, мы использовали ряд терминов, которые теперь определим строго. Будем различать три типа версии элемента данных.
1.Завершенные версии (commited versions). Эти версии, созданные теми транзакциями, которые уже успешно закончили свою работу.
2.Текущая версия (current version). Это последняя из завершенных версий.
3.Незавершенные версии (uncommited versions). Это версии, созданные теми транзакциями, которые еще находятся в работе.
В MV2PL планировщик следит за тем, чтобы в каждый момент времени существовало не более одной незавершенной версии. В зависимости от того, позволяется ли мы транзакциям читать незавершенные версии данных, различаются два варианта этого алгоритма. Мы будем одновременно рассматривать оба варианта MV2PL (с чтением незавершенных данных и без него). Сначала рассмотрим схему работы MV2PL в предположении, что все версии элементов данных сохраняются в базе. Затем обсудим вариант этого алгоритма, в котором допускается одновременное существование не более двух версий одного и того же элемента данных.
Все операции, которые обрабатывает планировщик, разделяются на два класса: обычные операции и финальные операции. Под финальной операцией понимается последняя операция транзакции перед ее завершением или же сама операция завершения (commit). Обе интерпретации допустимы. При этом каждая отдельная операция транзакции обрабатывается следующим образом.
1.Если операция не является финальной, то:
операция r(x) выполняется незамедлительно; ей сопоставляется последняя из завершенных к данному моменту версий x (или последняя из незавершенных версий x во втором варианте алгоритма);
операция w(x) выполняется только после завершения транзакции, записавшей последнюю версию x.
2. Если операция является финальной для транзакции ti то она откладывается до тех пор, пока не завершатся следующие транзакции:
— все транзакции tj, прочитавшие текущую версию данных, которую должна заменить версия, записанная ti (таким образом устраняется возможность неповторяющегося чтения);
— все транзакции tj, которые записали версии, прочитанные ti (это требуется только во втором варианте алгоритма).
Как видно, этот алгоритм ничего не говорит о числе версий одного и того же элемента, которые могут одновременно существовать в базе данных. Это вызывает проблемы с хранением версий. Во-первых, они могут занимать слишком много места (легко вообразить себе ситуацию, когда объем старых версий становится в несколько раз больше, чем объем всей “текущей” базы данных). Во-вторых, возникают трудности с размещением этих “старых” данных. Учитывая, что количество версий заранее не известно, сложно придумать эффективную структуру их хранения, которая бы не вызывала заметных накладных расходов. И, наконец, такая система слишком сложна в реализации.
Вероятно, именно из-за этих проблем на практике чаще всего используется протокол 2V2PL, предложенный впервые в работе Байера и др.[3]. В этом протоколе возможно одновременное существование двух версий элемента данных: одной текущей версии данных и не более одной незавершенной. Такая организация версий выгодна, прежде всего, для транзакций, выполняющих операцию чтения.
В 2V2PL используются три типа блокировок. Каждая блокировка удерживается до конца транзакции.
— rl (read lock): эта блокировка устанавливается на текущую версию элемента данных x непосредственно перед ее прочтением;
— wl (write lock): блокировка устанавливается перед тем, как создать новую (незавершенную) версию элемента x;
— cl (commit lock): блокировка устанавливается перед выполнением последней операции транзакции (обычно перед операцией commit) по отношению к каждому элементу данных, который она записала. Эта блокировка играет роль монопольной блокировки для обычного протокола 2PL. Она необходима для корректной смены версий.
|
