Классика баз данных - статьи
Временные метки (Multiversion Timestamp Ordering, MVTO)
В [] Бернштейн и Гудмен пишут, что наиболее ранний известный им алгоритм работы планировщика для версионной СУБД основан на временных метках. Этот планировщик обрабатывает операции таким образом, чтобы суммарный результат выполнения операций был эквивалентен последовательному выполнению транзакций. При этом их порядок задается порядком временных меток, которые получают транзакции во время старта. Временные метки также используются для идентификации версий данных при чтении и модификации – каждая версия получает временную метку той транзакции, которая ее записала. Планировщик не только следит за порядком выполнения действий транзакций, но также отвечает за трансформацию операций над данными в операции над версиями, т.е. каждая операция вида “прочитать элемент данных x”, должна быть преобразована планировщиком в операцию: “прочитать версию y элемента данных x”.
Для описания алгоритма введем ряд обозначений. Временную метку, полученную транзакцией ti в начале ее работы, будем обозначать как ts(ti). Операция чтения транзакцией ti элемента данных x будет обозначаться как ri(x). Для обозначения того, что транзакция ti читает версию элемента данных x, созданную транзакцией tk, будем писать ri(xk). Для обозначения того, что транзакция ti записывает версию элемента данных x, будем использовать запись wi(x).
Теперь опишем алгоритм работы MVTO-планировщика:
- Планировщик преобразует операцию ri(x) в операцию ri(xk), где xk – это версия элемента x, помеченная наибольшей временной меткой ts(tk), такой что ts(tk) <= ts(ti).
- Операция wi(x) обрабатывается планировщиком следующим образом.
- Если планировщик уже обработал действие вида rj(xk), такое что ts(tk) < ts(ti) < ts(tj), то операция wi(x) отменяется, а ti откатывается.
- В противном случае wi(x) преобразуется в wi(xi).
- Завершение транзакции ti (commit) откладывается до того момента, когда завершатся все транзакции, записавшие версии данных, прочитанные ti.
Заметим, что последний шаг нужен только в том случае, когда мы хотим предотвратить “грязное” чтение.
