|
планировщик должен также специальным способом проверять согласованность шагов, создающих новые версии. Для этого в граф добавляются дополнительные дуги, которые фиксируют «позиции записи» в соответствующем последовательном расписании. Опишем общую схему работы предлагаемого MVSG-планировщика. Когда очередной шаг pi(x) поступает планировщику, он предпринимает следующие действия. 1. Если это первое действие транзакции ti, поступившее планировщику, то соответствующий узел добавляется к графу конфликтов. 2. Если это шаг ri(x), то выбирается подходящая версия xj, и в граф добавляется дуга (tj, ti) (поскольку, согласно нашим обозначениям, версию xj записала транзакция tj). Для всех других к, таких что yvk(xk) является шагом tk, в граф добавляется либо дуга (tk, tj), либо дуга (ti, tk). В этом и состоит выбор «позиции записи». 3. Если это шаг yvi(xi), то для каждой транзакции tk, которая прочитала, скажем, версию xj, нужно добавить либо дугу (ti, tj), либо дугу (tk, ti). То есть ti должна следовать либо до tj, либо после tk в соответствующем последовательном расписании. 4. Если граф остается ацикличным, то изменения в графе фиксируются, а действие добавляется к списку запланированных. Иначе транзакция откатывается. Следует обратить внимание на выборе подходящей версии для чтения. Версия xj не является подходящей в двух случаях: во-первых, если существует путь из ti в tj (tj следует после ti по порядку сериализации);J вовторых, если существует путь (tj, tk, ti), где tk пишет х — wk(xk). В этих случаях отсутствует способ выбора места для wk(xk) в эквивалентном моноверсионном последовательном расписании. Как уже отмечалось, выбор для добавления в граф дуги — «(ti, tj) либо (tk, ti)», по сути, является выбором «позиции записи». Выбирается порядок следования других транзакций, которые пишут х. В некоторых случаях будет 70 |
Этот граф ацикличен. Однако для S не существует эквивалентного моноверсионного последовательного расписания. Действительно, поскольку t3 читает версию х, записанную ll (r3[xl]), то (2, которая тоже пишет элемент х (w2fx2J), должна следовать в моноверсионном последовательном расписании либо после t3, либо перед t l . Но первый вариант невозможен изза шага r3[z2], а второй — из-за г2[у1]. Таким образом, многоверсионный планировщик должен также специальным способом проверять согласованность шагов, создающих новые версии. Для этого в граф добавляются дополнительные дуги, которые фиксируют «позиции записи» в соответствующем последовательном расписании. Опишем общую схему работы предлагаемого MVSG-планировщика. Когда очередной шаг pi(x) поступает планировщику, он предпринимает следующие действия. 1. Если это первое действие транзакции ti, поступившее планировщику, то соответствующий узел добавляется к графу конфликтов. 2. Если это шаг ri(x), то выбирается подходящая версия xj, и в граф добавляется дуга (tj, ti) (поскольку, согласно нашим обозначениям, версию xj записала транзакция tj). Для всех других к, таких что wk(xk) является шагом tk, в граф добавляется либо дуга (tk, tj), либо дуга (ti, Ik). В этом и состоит выбор «позиции записи». 3. Если это шаг wi(xi), то для каждой транзакции tk, которая прочитала, скажем, версию xj, нужно добавить либо дугу (ti, tj), либо дугу (tk, ti). То есть ti должна следовать либо до tj, либо после tk в соответствующем последовательном расписании. 4. Если граф остается ацикличным, то изменения в графе фиксируются, а действие добавляется к списку запланированных. Иначе транзакция откатывается. Следует обратить внимание на выборе подходящей версии для чтения. Версия xj не является подходящей в двух случаях: во-первых, если существует путь из ti в tj (tj следует после ti по порядку сериализации); во вторых, если существует путь (tj, tk, ti), где tk пишет .г — wk(xk). В этих случаях отсутствует способ выбора места для wk(xk) в эквивалентном моноверсионном последовательном расписании. Как уже отмечалось, выбор для добавления в граф дуги — «(ti, tj) либо (tk, ti)», по сути, является выбором «позиции записи». Выбирается порядок следования других транзакций, которые пишут х. В некоторых случаях будет иметься несколько альтернативных путей, а в некоторых уже существующие дуги не оставят возможности выбора. В рассмотренном примере в графе образуется цикл на последнем шаге — w2[x2]. Выполняя этот шаг, мы должны будем, согласно правилу 3 алгоритма, добавить одну из дуг — (t2, tl) или (t3, t2). Обе ведут к образованию цикла. 3.6 Проблемы реализации версионных алгоритмов Далеко не все разработанные и предложенные алгоритмы активно применяются на практике — при их реализации возникают проблемы двух типов. Во-первых, требуется так устроить физическую организацию данных, чтобы можно было обеспечить эффективное управление версиями. Здесь следует учесть и разрастание объема базы данных при добавлении версий. То есть в идеале при организации данных должны учитываться возможные ограничения на количество версий. Заметим, что на практике ограничение на число версий зачастую отсутствует — вместо этого система просто удаляет ненужные версии по мере завершения соответствующих транзакций. Таким образом, ответственность за поддержание умеренного количества версий ложится на пользователей СУБД, которые должны следить за тем, чтобы в системе не появлялись «длинные транзакции». В противном случае версии будут оставаться в базе данных, что приведет к нефункциональному увеличению ее объема. Вторая проблема, возникающая при добавлении версий в архитектуру СУБД, имеет логический характер. Помимо планировщика наличие версий |