Рассмотрим основные алгоритмы управления параллельными транзакциями, основанные на концепции версионности.

Первые работы, посвященные управлению параллельными транзакциями на основе многоверсионности (multiversion concurrency control, MVCC), появились еще в конце 70-х — начале 80-х годов. Исходные статьи были написаны Ридом и коллективом авторов во главе с Байером [1-3], идеи которых были развиты в работах Стернса и Розенкранца [10], а также Бернштейна и Гудмена [6]. Основная идея MVCC заключается в том, что в базе данных допускается существование нескольких «версий» одного и того же элемента данных, что позволяет улучшить ряд характеристик СУБД, наиболее важных для следующих категорий приложений.

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

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

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

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

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

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

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

Временные метки

В [6] Бернштейн и Гудмен пишут, что наиболее ранний известный им алгоритм работы планировщика для версионной СУБД основан на временных метках (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).

1) Операция wi(x) обрабатывается планировщиком следующим образом:

a) если планировщик уже обработал действие вида rj(xk), такое что ts(tk) < ts(ti) < ts(tj), то операция wi(x) отменяется, а ti откатывается;

b) в противном случае wi(x) преобразуется в wi(xi).

3) Завершение транзакции ti (commit) откладывается до того момента, когда завершатся все транзакции, записавшие версии данных, прочитанные ti.

Последний шаг нужен только в том случае, когда хотят предотвратить «грязное» чтение.

Рис. 1. Пример работы планировщика MVTO

На рис. 1 приведен пример работы планировщика MVTO. Взаимодействие транзакций t1 и t2 отличным образом иллюстрирует плюсы использования версий. В случае подобного плана выполнения транзакций при отсутствии версионности получился бы классический случай чтения несогласованных данных. Однако в нашем примере эта ситуация вполне приемлема из-за того, что первая транзакция читает «старую» версию элемента данных y. Транзакция t3 ожидает окончания работы t2 перед собственным завершением (пунктирная линия на рис. 1). Это происходит потому, что t3 прочитала незавершенную версию x2.

Транзакция t4 является примером «поздней» транзакции изменения. Она создает версию y4, в то время как транзакция t5 (стартовавшая позднее) уже прочитала более раннюю версию y2. То есть транзакция t5 «не видит» некоторых изменений, внесенных t4. Таким образом, сериализация транзакций в порядке получения ими временных меток невозможна — необходим откат (пункт 2a алгоритма).

Многоверсионный вариант двухфазного протокола синхронизации

Рассмотрим вариант широко известного двухфазного протокола синхронизации транзакций (multiversion two-phase locking protocol, MV2PL), адаптированного для применения в версионной базе данных. Будем различать три типа версии элемента данных:

  • завершенные (commited) — версии, созданные транзакциями, которые уже успешно закончили свою работу;
  • текущая версия (current) — последняя из завершенных версий;
  • незавершенные (uncommited) — версии, созданные транзакциями, которые еще находятся в работе.

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

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

  1. если операция не является финальной, то: a) операция r(x) выполняется незамедлительно; ей сопоставляется последняя из завершенных к данному моменту версий x (или последняя из незавершенных версий x во втором варианте алгоритма); b) операция w(x) выполняется только после завершения транзакции, записавшей последнюю версию x.
  2. если операция является финальной для транзакции ti, то она откладывается до тех пор, пока не завершатся: a) все транзакции tj, прочитавшие текущую версию данных, которую должна заменить версия, записанная ti (тем самым устраняется возможность неповторяющегося чтения); b) все транзакции tj, которые записали версии, прочитанные ti (это требуется только во втором варианте алгоритма).

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

Вероятно, именно из-за этих проблем на практике чаще всего используется протокол 2V2PL, предложенный впервые в [3]. В этом протоколе возможно одновременное существование двух версий элемента данных: одной текущей версии данных и не более одной незавершенной. Такая организация версий выгодна прежде всего для транзакций, выполняющих операцию чтения.

В 2V2PL используются три типа блокировок, присем каждая блокировка удерживается до конца транзакции:

  • блокировка rl (read lock) устанавливается на текущую версию элемента данных x непосредственно перед ее прочтением;
  • блокировка wl (write lock) устанавливается перед тем, как создать новую (незавершенную) версию элемента x;
  • блокировка cl (commit lock) устанавливается перед выполнением последней операции транзакции (обычно перед операцией завершения) по отношению к каждому элементу данных, который она записала. Эта блокировка играет роль монопольной блокировки для обычного протокола 2PL. Она необходима для корректной смены версий.

Блокировки rl совместимы между собой, а также с блокировками wl. Поэтому использование блокировок rl и wl обеспечивает выполнение правил (1a) и (1b) алгоритма MV2PL (с учетом того, что одновременно позволяется поддерживать не более одной незавершенной версии). Блокировка cl, в свою очередь, обеспечивает выполнение правил (2a) и (2b).

Многоверсионный протокол для транзакций, не изменяющих данные

В работе многих приложений преобладают транзакции, не изменяющие данные (read-only). Такие приложения считывают и анализируют большие объемы данных. В случае наличия хотя бы небольшого числа параллельно выполняемых транзакций, производящих изменения, компонент, который отвечает за управление параллельными транзакциями, должен обеспечить согласованность прочитанных данных. В случае использования алгоритмов планирования без поддержки версий такие долговременные транзакции могут привести к чрезвычайному падению производительности. Например, при использовании 2PL крайне велика вероятность блокировки транзакций, производящих обновления данных. В результате у этих транзакций будет очень большое время отклика.

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

Протокол ROMV (Multiversion Protocol for Read-Only Transactions, ROMV) — гибридный, он основан на MVTO и 2PL. Он ориентирован на приложения, для которых наиболее важна скорость выполнения транзакций, не производящих изменений данных. (В литературе отсутствует согласие по поводу названий алгоритмов. Так, Пол Боббер и Майкл Кэри в [7] называют обсуждаемый протокол ROMV как MV2PL, мы же следуем терминологии, принятой в [4]).

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

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

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

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

MVSG-планировщики

Последний рассматриваемый класс многоверсионных алгоритмов планирования обобщает широко известную моноверсионную технику Serialization Graph Testing (SGT). Основанные на SGT планировщики поддерживают граф конфликтов, в котором вершины и дуги добавляются динамически в зависимости от операций, которые получает на вход планировщик. При этом конфликтующими называются любые две операции над одним и тем же элементом данных, если хотя бы одна из них является операцией модификации. Другими словами, для конфликтующих операций важен порядок их выполнения. Таким образом, планирование конфликтующих операций накладывает ограничение на порядок сериализации транзакций. Эти ограничения и выражает граф конфликтов. Рассмотрим, как происходит планирование очередной операции pi(x) с помощью SGT-планировщика.

  1. Если это первая операция транзакции ti, поступившая планировщику, то создается новый узел в графе сериализации.
  2. В граф добавляются дуги вида (tj, ti) для каждой запланированной ранее операции qj(x) (i _ j), конфликтующей с pi(x). Возможны два варианта: a) результирующий граф содержит циклы — транзакция ti откатывается; b) полученный граф ацикличен — действие добавляется к списку запланированных.

Что означает, что в графе появился цикл? Полученное расписание больше не будет сериализуемым. Это утверждение становится очевидным, если заметить, что дуга из ti в tj фиксирует порядок следования транзакций в эквивалентном последовательном расписании. Результат нашего расписания должен быть таким же, как и последовательное выполнения сначала всех действий транзакции ti, а затем tj. Поскольку транзакция не может следовать раньше самой себя, граф с циклами не будет иметь соответствующего последовательного расписания.

Теперь мы можем перейти к более общему многоверсионному случаю и будем рассматривать многоверсионный граф конфликтов MVSG. Покажем, что ограничения, которые мы накладывали на граф сериализации в моноверсионним случае, недостаточны. Рассмотрим следующий пример:

S = w1[x1]w1[y1]r2[y1]r3[x1]w2[z2]r3[z2]w2[x2]

Рис. 2. Граф сериализации для плана S, составленный по правилам SGT

Граф (рис. 2), составленный по правилам алгоритма SGT, будет содержать дуги (t1, t2), (t1, t3), (t2, t3).

Этот граф ацикличен. Однако для S не существует эквивалентного моноверсионного последовательного расписания. Действительно, поскольку t3 читает версию x, записанную t1 (r3[x1]), то t2, которая тоже пишет элемент x (w2[x2]), должна следовать в моноверсионном последовательном расписании либо после t3, либо перед t1. Но первый вариант невозможен из-за шага r3[z2], а второй — из-за r2[y1]. Таким образом, многоверсионный планировщик должен также специальным способом проверять согласованность шагов, создающих новые версии. Для этого в граф добавляются дополнительные дуги, которые фиксируют «позиции записи» в соответствующем последовательном расписании.

Опишем общую схему работы MVSG-планировщика. Когда очередной шаг pi(x) поступает планировщику, он предпринимает следующие действия.

  1. Если это первое действие транзакции ti, поступившее планировщику, то соответствующий узел добавляется к графу конфликтов.
  2. Если это шаг ri(x), то выбирается подходящая версия xj, и в граф добавляется дуга (tj, ti) (поскольку, согласно нашим обозначениям, версию xj записала транзакция tj). Для всех других k, таких что wk(xk) является шагом tk, в граф добавляется либо дуга (tk, tj), либо дуга (ti, tk). В этом и состоит выбор «позиции записи».
  3. Если это шаг wi(xi), то для каждой транзакции tk, которая прочитала, скажем, версию xj, нужно добавить либо дугу (ti, tj), либо дугу (tk, ti). То есть ti должна следовать либо до tj, либо после tk в соответствующем последовательном расписании.
  4. Если граф остается ацикличным, то изменения в графе фиксируются, а действие добавляется к списку запланированных. Иначе транзакция откатывается.

Следует обратить внимание на выборе подходящей версии для чтения. Версия xj не является подходящей в двух случаях: во-первых, если существует путь из ti в tj (tj следует после ti по порядку сериализации); во-вторых, если существует путь (tj, tk, ti), где tk пишет x — wk(xk). В этих случаях отсутствует способ выбора места для wk(xk) в эквивалентном моноверсионном последовательном расписании.

Как уже отмечалось, выбор для добавления в граф дуги — «(ti, tj) либо (tk, ti)», по сути, является выбором «позиции записи». Выбирается порядок следования других транзакций, которые пишут x. В некоторых случаях будет иметься несколько альтернативных путей, а в некоторых уже существующие дуги не оставят возможности выбора.

В рассмотренном примере в графе образуется цикл на последнем шаге — w2[x2]. Выполняя этот шаг, мы должны будем, согласно правилу 3 алгоритма, добавить одну из дуг — (t2, t1) или (t3, t2). Обе ведут к образованию цикла.

Это семейство алгоритмов описано в [11], [12] и в [4] под названием MVSGT.

Проблемы реализации версионных алгоритмов

Далеко не все рассмотренные алгоритмы активно применяются на практике — при их реализации возникают проблемы двух типов. Во-первых, требуется так устроить физическую организацию данных, чтобы можно было обеспечить эффективное управление версиями. Здесь следует учесть и разрастание объема базы данных при добавлении версий. То есть в идеале при организации данных должны учитываться возможные ограничения на количество версий. Заметим, что на практике ограничение на число версий зачастую отсутствует — вместо этого система просто удаляет ненужные версии по мере завершения соответствующих транзакций. Подобная ситуация наблюдается в СУБД MySQL (в конфигурации, при которой низкоуровневая работа с таблицами возлагается на подсистему InnoDB). В InnoDB используется одна из разновидностей протокола ROMV. Поскольку в этом протоколе все транзакции, вносящие изменения в базу данных, создают новые версии данных, то проблема ограничения числа версий стоит так же остро, как и в большинстве других версионных алгоритмов. В InnoDB удаление версий происходит в тот момент, когда они оказываются не нужными ни одной из активных транзакций. Таким образом, ответственность за поддержание умеренного количества версий ложится на пользователей СУБД, которые должны следить за тем, чтобы в системе не появлялись «длинные транзакции». В противном случае версии будут оставаться в базе данных, что приведет к нефункциональному увеличению ее объема.

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

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

Перечисленные трудности проявляются различным образом, в зависимости от выбора алгоритма, что объясняется тем, что алгоритмы фиксируют порядок создания и поддержания версий. Поэтому они влияют как на физическую сторону организации многоверсионной СУБД, так и на логическую. На практике наиболее часто используются протоколы ROMV и 2V2PL. С одной стороны, эти протоколы достаточно просты в реализации, а с другой — предоставляют пользователю большую часть выгод версионной СУБД. В случае протокола 2V2PL существенную роль также играет его сходство с обычным 2PL. Помимо этого, в 2V2PL решается проблема ограничения числа версий. Сложность решения этой проблемы в случае протокола MVTO, по-видимому, служит одной из причин его малой распространенности. Можно предположить, что та же причина объясняет небольшое количество реализаций, использующих MV2PL. Автору также не известно о реализациях, применяющих MVSG-планировщики.

***

В статье сделан обзор наиболее известных версионных алгоритмов, применяемых для организации управления параллельными заданиями. Также рассмотрены основные проблемы, возникающие при их реализации. Обзор подготовлен в процессе поиска возможного пути организации версий в XML СУБД Sedna, разрабатываемой в ИСП РАН группой MODIS.

Литература
  1. D. Reed, Naming and Synchronization in a Decentralized Computer System, Ph.D. Thesis, MIT, September 1978.
  2. D. Reed, Implementing atomic actions on decentralized data. ACM Trans. Comp. Syst. 1, 1, Feb. 1983.
  3. R. Bayer, H. Heller, A. Reiser, Parallelism and recovery in database systems. ACM Trans. Database Syst. 5, 2, June 1980.
  4. G. Weikum, G. Vossen, Transactional information systems. Morgan Kaufmann, 2002.
  5. R. Unland, Optimistic Concurrency Control Revisited. Arbeitsberichte des Instituts f r Wirtschaftsinformatik, 1994.
  6. P. Bernstein, N. Goodman, Multiversion concurrency control — theory and algorithms. ACM Transactions on Database Systems, Vol. 8, No. 4, December 1983.
  7. P. Bober, M. Carey, Multiversion Query Locking. Proceedings of the 18th VLDB Conference Vancouver, British Columbia, Canada, 1992.
  8. O. Proskurnin, Concurrent Video: Versioning Concepts. Proceedings of the Spring Young Researcher?s Colloquium on Database and Information Systems SYRCoDIS, St.-Petersburg, Russia, 2004.
  9. A. Yakovlev, A Multi-Version Concurrency Control Model for Distributed Mobile Databases. Proceedings of the Spring Young Researcher?s Colloquium on Database and Information Systems SYRCoDIS, St.-Petersburg, Russia, 2004.
  10. R. Stearns, D. Rosenkrantz, Distributed database concurrency control using before-values. In Proc. 1981 ACM SIGMOD Conf. Management of Data, ACM, New York, 1981.
  11. C. Papadimitriou, The theory of database concurrency control. Computer Science Press, 1986.
  12. T. Hadzliacos, Serialization graph algorithms for multiversion concurrency control. Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1988.

Петр Чардин (cps@rc.ru) — студент ВМиК МГУ. Автор признателен Готфриду Воссену за предоставленные материалы и Сергею Кузнецову за многочисленные советы и замечания.