|
иметься несколько альтернативных путей, а в некоторых уже существующие дуги не оставят возможности выбора. В рассмотренном примере в графе образуется цикл на последнем шаге — ~w2[x2]. Выполняя этот шаг, мы должны будем, согласно правилу 3 алгоритма, добавить одну из дуг — (t2, tl) или (t3, t2). Обе ведут к образованию цикла. 2.6. Проблемы реализации версионных алгоритмов Далеко не все разработанные и предложенные алгоритмы активно применяются на практике — при их реализации возникают проблемы двух типов. Во-первых, требуется так устроить физическую организацию данных, чтобы можно было обеспечить эффективное управление версиями. Здесь следует учесть и разрастание объема базы данных при добавлении версий. То есть в идеале при организации данных должны учитываться возможные ограничения на количество версий. Заметим, что на практике ограничение на число версий зачастую отсутствует — вместо этого система просто удаляет ненужные версии по мере завершения соответствующих транзакций. Таким образом, ответственность за поддержание умеренного количества версий ложится на пользователей СУБД, которые должны следить за тем, чтобы в системе не появлялись «длинные транзакции». В противном случае версии будут оставаться в базе данных, что приведет к нефункциональному увеличению ее объема. Вторая проблема, возникающая при добавлении версий в архитектуру СУБД, имеет логический характер. Помимо планировщика наличие версий должно приниматься во внимание во многих компонентах СУБД. В связи с этим необходимо обеспечить корректное взаимодействие этих компонентов. Очевидным образом, с учетом версий должно происходить поддержание поисковых структур. С учетом версий должна строиться и журнализация. Более того, поскольку и журнал и версии содержат информацию о старом состоянии базы данных, возможно объединение этих сущностей. 71 |
вторых, если существует путь (tj, tk, ti), где tk пишет .г — wk(xk). В этих случаях отсутствует способ выбора места для wk(xk) в эквивалентном моноверсионном последовательном расписании. Как уже отмечалось, выбор для добавления в граф дуги — «(ti, tj) либо (tk, ti)», по сути, является выбором «позиции записи». Выбирается порядок следования других транзакций, которые пишут х. В некоторых случаях будет иметься несколько альтернативных путей, а в некоторых уже существующие дуги не оставят возможности выбора. В рассмотренном примере в графе образуется цикл на последнем шаге — w2[x2]. Выполняя этот шаг, мы должны будем, согласно правилу 3 алгоритма, добавить одну из дуг — (t2, tl) или (t3, t2). Обе ведут к образованию цикла. 3.6 Проблемы реализации версионных алгоритмов Далеко не все разработанные и предложенные алгоритмы активно применяются на практике — при их реализации возникают проблемы двух типов. Во-первых, требуется так устроить физическую организацию данных, чтобы можно было обеспечить эффективное управление версиями. Здесь следует учесть и разрастание объема базы данных при добавлении версий. То есть в идеале при организации данных должны учитываться возможные ограничения на количество версий. Заметим, что на практике ограничение на число версий зачастую отсутствует — вместо этого система просто удаляет ненужные версии по мере завершения соответствующих транзакций. Таким образом, ответственность за поддержание умеренного количества версий ложится на пользователей СУБД, которые должны следить за тем, чтобы в системе не появлялись «длинные транзакции». В противном случае версии будут оставаться в базе данных, что приведет к нефункциональному увеличению ее объема. Вторая проблема, возникающая при добавлении версий в архитектуру СУБД, имеет логический характер. Помимо планировщика наличие версий должно приниматься во внимание во многих компонентах СУБД. В связи с этим необходимо обеспечить корректное взаимодействие этих компонентов. Очевидным образом, с учетом версий должно происходить поддержание поисковых структур. С учетом версий должна строиться и журнализация. Более того, поскольку и журнал и версии содержат информацию о старом состоянии базы данных, возможно объединение этих сущностей. Еще одна подсистема СУБД, которая существенным образом меняется при добавлении версий, — это подсистема управления памятью. Поскольку много версий одного и того же элемента данных могут использоваться параллельно, необходимо эффективное размещение версий в основной памяти. Если заранее неизвестно максимальное число версий, допустимых для одного элемента данных, то это требование трудновыполнимо. Перечисленные трудности проявляются различным образом, в зависимости от выбора алгоритма, что объясняется тем, что алгоритмы фиксируют порядок создания и поддержания версий. Поэтому они влияют как на физическую сторону организации многоверсионной СУБД, так и на логическую. На практике предлагается используются протоколы ROMV и 2V2PL. С одной стороны, эти протоколы достаточно просты в реализации, а с другой — предоставляют пользователю большую часть выгод версионной СУБД. В случае протокола 2V2PL существенную роль также играет его сходство с обычным 2PL. Помимо этого, в 2V2PL решается проблема ограничения числа версий. Сложность решения этой проблемы в случае протокола MVTO, по-видимому, служит одной из причин его малой распространенности. Можно предположить, что та же причина объясняет небольшое количество реализаций, использующих MV2PL. 3.7 Выводы 1. Современные СУБД, являющиеся многопользовательскими системами, допускают параллельную одновременную работу большого количества пользователей, что в свою очередь порождает целый комплекс |