Классика баз данных - статьи

Краткая история ARIES


В середине 80-х годов в исследовательском центре корпорации IBM Almaden начался проект под названием Starburst. Его целью было создание расширяемой реляционной СУБД. Именно тогда группа исследователей из числа разработчиков Starburst решила сосредоточить свое внимание на устройстве системы управления транзакциями. Они решили пересмотреть ряд предположений и выводов, к которым пришли разработчики знаменитой реляционной СУБД System R. Это желание привело к тому, что было потрачено много времени на изучение того, как работала система управления транзакциями в System R и некоторых других СУБД компании IBM. Исследования были настолько основательны, что был даже опубликован ряд статей, касающихся многих неизвестных до этого сторон работы System R. Вся эта деятельность позволила прийти к выводам о сильных и слабых местах в дизайне существовавших систем.

Например, выяснилось, что разработчики System R, хотя и убедились в том, что при восстановлении базы данных упреждающая журнализация (WAL - Write Ahead Log) работает лучше, чем механизм теневых страниц (Shadow Page Technique), не преуспели в разработке таких методов журнализации и восстановления, в которых поддерживались бы блокировки небольших объектов (например, блокировки кортежей) без потребности блокировки более крупного объекта (в то время, как блокируя кортеж, содержащийся в некоторой физической странице, мы хотели бы позволить системе беспрепятственно работать с другими кортежами этой страницы). Однако в некоторых существовавших продуктах IBM это свойство поддерживалось. Например, в иерархической СУБД IMS можно было производить блокировки самых различных объектов. Но при этом захват происходил не на логическом, а на физическом уровне (то есть блокировка закрывала доступ к конкретным сегментам памяти). Это приводило к тому, что реорганизация кортежей в странице должна была происходить в режиме, запрещающем операции над страницей.

Создатели ARIES решили объединить все лучшие разработки IBM в области управления транзакциями, журнализацией и восстановлением в единый алгоритм.
Эта цель была ими во многом достигнута. Работа над базовым алгоритмом ARIES была завершена к середине 80-х годов. Первые публикации появились в начале 90-х.

Однако, это лишь первый этап развития ARIES. Второй этап включает в себя внедрение ARIES в индустрию и разработку расширений алгоритма, наиболее интересном из которых, по-видимому, являлся алгоритм ARIES for Semi-Structured Data. Это расширение было выполнено под руководством Мохана в рамках проекта Dominotes. Целью этого проекта была разработка способа восстановления на основе журнализации для Lotus Domino/Notes. Выяснилось, что, несмотря на существенные особенности модели полуструктурированных данных, ARIES удалось сравнительно легко адаптировать и внедрить в уже существовавший продукт.

Алгоритм оказался столь удобен и прост, что его многочисленные варианты используются сейчас в большинстве систем, поддерживающих транзакции. Как уже отмечалось, ARIES используется в файловой системе NTFS, MS SQL Server, IBM DB2, O2 и многих других системах.

Разработкой алгоритма занималась группа исследователей, но главным вдохновителем и идеологом ARIES был Мохан (C. Mohan). Пусть читателя не удивляет столь необычное имя. Дело в том, что Мохан происходит из той части Индии, где нет такого понятия как фамилия. Поэтому все его работы подписаны именно так. Мохан является автором большинства статей про ARIES. В 1999 году за работу над ARIES он получил награду "10 Years Award" на самой крупной международной конференции, посвященной тематике СУБД, - VLDB (доклад, сделанный по этому поводу, был опубликован в виде статьи [3]). Эта награда вручается автору наиболее важного доклада из тех, что были сделаны на VLDB за последние 10 лет. Создание ARIES привело также к созданию нового структурного подразделения IBM - Института технологий баз данных (Data Base Technology Institute - DBTI). Эта организация позволила исследователям IBM более тесно сотрудничать с разработчиками и клиентами фирмы. Это, в свою очередь, привело к более четкому осознанию проблем, стоящих перед сообществом баз данных.

Сегодня ссылки на статьи по ARIES можно найти в самых известных учебниках по системам баз данных. Семейство алгоритмов изучают во многих университетах США, в некоторых из которых были разработаны специальные системы для демонстрации свойств ARIES (в качестве примера можно привести систему Mars, разработанную в университете Cornell). Так что ARIES смело можно назвать хрестоматийным алгоритмом.

Теперь обратимся к описанию самого алгоритма ARIES. Здесь мы будем рассматривать лишь основной алгоритм ARIES [4], на базе которого были созданы все расширения. Мы также будем говорить об ARIES в контексте баз данных, хотя область его применения не ограничивается СУБД.


Содержание раздела