http://cmsshop.info/cms/3982 Фактографическая основа совместной реорганизации сложных информационных ресурсов © С.В. Знаменский Институт программных систем РАН имени А.К. Айламазяна svz@latex.pereslavl.ru Аннотация Информационные ресурсы, адресованные комплексным проблемам, непрерывно дорабатываются с привлечением широкого круга специалистов и организаций. Такая доработка часто нуждается в неожиданных коррекциях структуры ресурса, параллельной разработке и сопоставительном тестировании пользователями нескольких версий его составляющих, удалении лишнего и восстановлении ранее доступного. Обсуждается идея построить представление данных в такой системе на неизменяемых записях, адресуемых с учётом даты-времени и авторства их создания и обеспечивающей ускорение многопользовательской доработки за счёт (1) непосредственного доступа к прежним состояниям информации и существенным особенностям её изменения; (2) локализации ошибок исполнения во времени и информационном пространстве; (3) многослойного представления реорганизуемых данных (с разными комбинациями активных слоёв для разных пользователей) и многоуровневого тестирования. 1 Введение Последнее десятилетие в интернете наблюдается качественный и количественный рост -ресурсов открытых технических стандартов, включая библиографические классификаторы; -ресурсов открытых образовательных стандартов и систем дистанционного образования; -общедоступных ресурсов по биологии и другим наукам, склонным к пересмотру концепций и классификаций; -ресурсов открытого исходного кода больших программных систем; -государственных и корпоративных ресурсов законодательно-нормативной информации. Потребность в частой коррекции структуры такого ресурса обусловлена не столько неполнотой предпроектного обследования, сколько -наличием внутренних несогласованностей и требующих исправления противоречий, -рассогласованностью политик и приоритетов различных пользователей, создавших ресурс, -непредсказуемостью изменений в предметной области. Рост масштабов и сложности информационных систем актуализирует проблему совместной разработки. Для контента со слабыми внутренними взаимосвязями и неизменной структурой взаимодействие разработчиков полезно организовать в самой системе, как это делается в википедии и других системах управления контентом. Непрерывная интеграция [1] обещает удешевление и ускорение разработки сложного контента при одновременном повышении качества за счёт сочетания следующих шаблонов: - частое применение изменений (сборка) - упрощение и ускорение сборки - эащищённая система управления версиями - уровни сборки и тестирования (частная, групповая) - песочница(песочницы) для тестирования - скрипты ускоренного тестирования - запуск всех тестов на общем компьютере - оперативное адресное информирование разработчиков о изменениях в коде и об ошибках исполнения их кода в системе - скриптовое конфигурирование - упрощение возврата к старой версии Эффект непрерывной интеграции определяется качеством организации тестирования и связи разработчиков с пользователями. В [2,3] намечен подход к разработке контекстно-автономных информационных систем, базирующийся на целостности истории изменений в информации. Этот подход резко усиливает составляющие непрерывной интеграции, в корне изменяя привычные представления и ориентиры в разработке сложного контента: 1 Благодаря снятию конкурентности записи (старое значение не затирается новым), снимается требование изолированности модулей. 2 Модульность проявляется в выделении в общем информационном пространстве иерархии вложенных подпространств-контекстов данных, контроллируемых ответственными пользователями. 3 В текущем контексте доступны история изменений любого данного, наличие и критичность изменений за любой период. 4 Системных сообщений нет, есть авторизованное чтение последнего устойчивого состояния другого контекста с регистрацией попытки чтения. 5 Разные пользователи одновременно используют разные версии синхронно растущих структур данных (сервисного кода) с общими элементами, естественная миграция проходит без остановок сервиса. Это открывает новые возможности: Многоуровневое сопоставительное тестирование новых разработок в работающей системе производится в ходе их непосредственного использования без дополнительных затрат усилий, что резко сокращает затраты на широкое тестирование. Автоматическое управление версиями на основе кластеризации потребителей и их сопоставительных (явных и косвенных) оценок. Цикл "ошибка замечена пользователем - исправлена - проверена" может сокращаться до нескольких минут. 6 Прозрачный автоматический учёт авторских вкладов участников в код, данные и тестирование в каждом контексте. 7 Мониторинг ресурсов настраивается в рамках каждого автономного контекста с использованием явных и неявных оценок качества кластерами потребителей. 8 Резервное копирование и удаление неактуальной информации автоматически оптимизированы. 9 Распределённый сервис отзывчив, устойчив к разрывам связи и к потере любого ЦОДа (вопреки "CAP-3 теореме Браудера"). 10 Жизненный цикл приложения на новой основе состоит из выбора лучшего прототипа и бесконечной адаптации его к изменяющимся потребностям пользователя. Этот подход может рассматриваться и в качестве основы для системы неограниченно возрастающей сложности, долговременно устойчиво развивающейся (“perpetual еvolution”) на фоне технических, политических и юридических преображений. Новые исходные требования к такой системе лаконично сформулированы SEI (Software Engineering Institute) в [2,3] в виде ключевых особенностей широкомасштабируемых социотехнических систем будущего (ULS): - Децентрализация; - Противоречивые по своей сути, непознаваемые, и разнообразные требования к системе; - Непрерывное развитие и развёртывание; - Разнородные, рассогласованные и изменяющиеся элементы; - Стирание границы между людьми и системой; - Устойчивость к ошибкам в исходных данных и при их обработке; - Соревнование за системные ресурсы; - Наличие организаций и участников, ответственных за установление политик; - Наличие организаций и участников, ответственных за производство самой системы; - Локальные и глобальные показатели здоровья, которые будут подключать необходимые изменения в политиках и в поведении элемента и системы; - Дизайн и эволюция производственных отношений; - Оркестровка и управление; - Наблюдение и оценка. Сформулировав перечисленные требования, рабочая группа SEI дала им недвусмысленную оценку: “These characteristics undermine the assumptions we make in most current technical, management, and acquisition approaches.” “Today’s approaches are based on perspectives that fundamentally do not cope with the new characteristics arising from ultra-large scale. The mentality of looking backward doesn’t scale.” Такая оценка ориентирует на пересмотр стандартных подходов и, в частности, на поиск архитектуры СУБД ориентированной на разработку и беспрепятственное эволюционирование системы с указанными свойствами. Напрашивается гипотеза о том, что создание и развитие контекстно-автономных систем указывает значительно более простой, просматриваемый и экономный путь к ULS, чем предложенное SEI развитие сервер-ориентированной архитектуры. Подтвердить или опровергнуть эту гипотезу может только практическая работа. 2. План исследований Практическая работа по созданию контекстно-автономной системы разделяется на последовательное решение ряда новых трудных задач: 1. Разработка распределённой широкомасштабируемой B+tree СУБД, - имеющей логарифмическую сложность доступа к записи с лексикографически наибольшим ключом, меньшим или равным строке запроса, - гарантирующей неизменность первично сохранённого значения ключа, - обеспечивающей одновременный конкурентный доступ на чтение и запись данных с разными ключами, - не замедляющей чтение ранее записанных данных при многократных перегрузках или ухудшении коннективности. 2. Разработка теоретических принципов построения и создание "живого словаря" - подсистемы, ответственной за хранение информации. Подсистема должна эффективно обеспечивать - принципиально неограниченную масштабируемость, - доступ не чтение любого элемента хранимой информации с указанием времени запроса, - доступ к истории изменения любого элемента с авторством изменений, - индикацию наличия и критичности изменений любого элемента за любой период, - автоматический отбор для удаления из истории наименее значимой давно неактуальной информации с сохранением полной согласованности данных на любой запрашиваемый момент прошлого, - ретроспективную индексацию данных. - низкоуровневую навигацию по всему дереву данных, аналогичную панели файлового эксплорера. 3. Разработка подсистемы неограниченно масштабируемых многослойных структур данных. Базируясь на "живом словаре", эта подсистема должна обладать всеми качествами "живого словаря" и при этом обеспечивать - описания структур, изменяющееся синхронно с самими структурами; - аналог символических ссылок файловой системы с функциональностью команды "append" из msdos; - сосуществование нескольких версий хранимой информации (вариантов упорядочения массива, веток с по-разному привитыми подветками и т. д.) 4. Разработка подсистемы контекстно-автономного управления применением изменений. 5. Разработка персонально оптимизируемых пользовательских интерфейсов, ориентированных на работу с устоявшимися состояниями системы, её историей и её гладкую доработку. 6. Рефакторинг кода, расширение масштабов использования и сфер приложений в духе принципа персика. 3. Основные ориентиры 3.1 Принцип персика Система, удовлетворяющая требованиям децентрализации, непрерывного развития и развёртывания, содержащая разнородные, рассогласованные и изменяющиеся элементы и устойчивая к ошибкам в исходных данных и ошибках исполнения может, подобно персику, состоять из ядрышка, косточки и мякоти. Ядрышко — это защищённые данные системы, включая те, которые уже не актуальны, но ещё могут потребоваться для диагностики и исправления ошибок. Эти данные должны храниться с обеспечивающим надёжную сохранность дублированием распределённо, в разных ЦОДах, под управлением различных операционных систем, синхронизироваться и распределяться в вновь создаваемые хранилища. Ядрышко неограниченно количественно и качественно растёт в ходе жизнедеятельности системы, включая в себя все данные и логику функционирования приложений. Оно надёжно защищено от противоречий, рассогласованностей и ошибок жёстко определённой косточкой семантикой низкого уровня. Косточка — это жёсткий исполняемый код, обеспечивающий защищённый доступ к данным и гарантирующий их целостность на фоне штатных сбоев и поломок оборудования. Он базируется на прозрачно специфицированных протоколах и алгоритмах распределённого хранения и синхронизации изменений, выявления и удаления заведомо ненужной информации, регламентах аварийно-восстановительных работ. Этот код минимален и предельно прост, тщательно выверен и отлажен, устойчив к любым ошибкам в остальных частях и не требует коррекции при любых изменениях логики приложений. Мякоть — это прикладная логика системы, адекватно отражающая потребности пользователей. Как и эти потребности, она может быть локальна, непоследовательна, временами противоречива, по разному представляться разным группам и пользователям. Она вечно неограниченно эволюционирует, местами иногда возвращаясь к прежним состояниям. Эта логика выполняется в фоновом защищённом режиме и любые ошибки её задания или исполнения имеют жёстко ограниченные косточкой во времени и информационном пространстве последствия. 3.2 Контекстная автономность Децентрализация означает иерархию ответственности. По принципу единоначалия, один человек отвечает за систему в целом, но он делегирует управление и ответственность за некоторые или все подсистемы своим подчинённым, которые могут продолжить этот процесс. Таким образом, всё информационное пространство системы предстаёт иерархией автономно управляемых подпространств-контекстов данных. Смысл существования каждого такого контекста в специфическом информационном обслуживании, то есть в обеспечении клиентов качественно обработанной информацией. Хозяин контекста имеет полный доступ к информации своего автономного контекста, устанавливает внутри него политики и правила доступа, выбирает доступные способы обработки, разграничивает доступ и регулирует оркестровку и персонификацию, выбирает и использует средства мониторинга и оценки, делегирует эти функции подчинённым (или роботам), при необходимости отделяя для них дочерние автономные контексты, устанавливает роли, политики и правила вычисления относительных приоритетов очерёдности обработки данных. Любая часть выходной информация контекста может быть объявлена доступной для любого множества контекстов. Хозяину всегда доступна информация, сколько пользователей и насколько часто используют те или иные выходные интерфейсы напрямую или через какие контексты. Косточка регламентирует, где в ядрышке должна находиться информация о контекстах, делегировании, ролях, приоритетах и настройках ресурсов, как собирается статистика использования и организуется выполнение обработки информации и обеспечивает эти работы в точном соответствии с регламентом. 3.3 Фактографическая основа Основным средством защиты системы от ошибок в прикладных обработках становится обеспечение эффективного доступа к прошлой информации системы. Система не имеет состояния на текущий момент времени, настоящему, все запросы на чтение информации мгновенно возвращают установившееся в системе прошлое состояние и остаются воспроизводимы с тем же результатом. Если запрос к системе адресован к медленно обрабатываемым изменчивым данным, то система не заставит ждать окончания обработки, а немедленно выдаст последнюю готовую версию с индикацией момента времени актуальности и ставит запрос в очередь обработки. Сейчас это крайне непривычно, но такой порядок позволит значимо ускорить работу с системой, задержки в работе которой неустранимы по причине больших расстояний или сложных алгоритмов. Временная поломка обработчика оказывается эквивалентной задержке обработки данных. Если сопровождающий код программист оперативно извещается о поломке и в состоянии быстро её устранить, то поломка может проявиться и устраниться незаметно для пользователей. Требование устойчивости к ошибкам будет сохранять актуальность и по чисто технической причине [6], [7]: уменьшение размеров транзисторов и их энергопотребления при повышении быстродействия приводит к усилению эффектов квантовой механики, неотвратимо повышающих вероятность ошибки в конкретной ячейке памяти. Разумеется, ошибки в основном компенсируются использованием дублирования и особого кода, исправляющего ошибки, но требующего дополнительных ресурсов. Предлагаемая архитектура предъявляет высокие требования к хранению информации и исполнению регламентных процедур косточки. Обработки данных приложений в ряде случаев могут проводиться быстрее и с меньшей надёжностью, если выходные данные в контексте должны подвергаются независимому контролю и при необходимости перевычислению. 3.4 Жизненный цикл данных Хранение истории исходных данных, промежуточных и окончательных результатов обработки требует затрат, существенно зависящих от способа хранения и поэтому трудно поддающихся оценке. Ориентиром может служить достаточно экономный стандартный для темпоральных реляционных баз данных подход, связанный с добавлением столбцов времени в таблицы. Таблицы разрастаются менее чем в два раза по сравнению с тем, как если бы просто добавлялись новые строки данных без модификации старых. Однако при интенсивном обновлении данных даже здесь на практике неизбежно возникает проблема недостатка пространства для хранения данных. Хранение промежуточных и окончательных результатов обработки типовых запросов усугубляет ситуацию, вынуждая избавляться от старых никому не нужных данных. Чтобы удаление данных не нарушило целостность системы, предполагалось в далёком прошлом выделять короткие промежутки времени, так называемые «белые пятна истории», связанные с интенсивным изменением данных, и удалять версии данных, не актуальные вне этих промежутков. Поскольку выделение таких пятен при больших объёмах данных является непростой задачей, то предлагалось решать её в рамках отдельных автономных контекстов, что могло нарушить согласование данных между разными контекстами. Сейчас найдено существенно лучшее решение, позволяющее чистить ненужную часть истории без перерасхода ресурсов и угрозы рассогласования. Оно состоит в увеличении шага дискретизации для очень старых данных. Например, если шаг дискретизации для данных более чем десятилетней давности переустанавливается в одни сутки, то из всех изменений любого данного в течение таких давно прошедших суток оставляется последнее, актуальное на момент полуночи. Все изменения, актуальные на границе каких-либо суток, остаются в доступе, а все очень старые изменения, не дожившие до ближайшей полуночи, теряются безвозвратно. 4. Наброски решений 4.1 Модель данных Функциональность косточки должна быть предельно простой, но достаточной для обеспечения защищённости и целостности ядрышка. Поэтому модель данных ядрышка должна быть простейшей из обещающих требуемую функциональность. В докладе и материалах конференции предполагается затронуть описания модели данных и механизмов косточки, обеспечивающих динамическое распределение ресурсов с учётом приоритетов, синхронизацию информации в географически удалённых ЦОДах, механизмы альфа- и бета-тестирования дорабатываемых модулей в работающей системе и ретроспективное индексирование данных. Литература 1]by Paul M. Duvall. Continuous Integration: Improving Software Quality and Reducing Risk, Addison-Wesley, 2007. http://www.amazon.com/gp/product0321336380/?tag=integratecom-20 2 Знаменский С.В. Контекстно-автономная информационная система. // Четвёртая конференция «Свободное программное обеспечение в высшей школе». Переславль, 30 января — 1 февраля 2009 года. Тезисы докладов. М., ALT Linux, 2009, c. 32-37. 1. 3]С. В. Знаменский. Гибкая основа информационной системы для обучения. //Труды XII-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» RCDL-2010. Казань: Казанский университет. 2010, с. 451-460. 4]Знаменский С. В. Хорошо масштабируемое автономное администрирование доступа. Труды Международной конференции "Программные системы: теория и приложения", Переславль-Залесский, октябрь 2006,  Наука,-Физматлит, М. Т. 1, c. 155-169. ---. 2] Linda Northrop.The Impact of Scale: Carnegie Mellon University. December 17, 2009 http://www.sei.cmu.edu/library/assets/20091217webinar.pdf 3]Linda Northrop. Ultra-Large-Scale Systems. The Software Challenge of the Future. June 2006. Pittsburgh, PA 15213-3890 http://www.sei.cmu.edu/library/assets/ULS_Book20062.pdf http://skif.pereslavl.ru/psi-info/psi/psi-publications/e-book-2006/index.html Mart Roost, Karin Rava, and Tarmo Veskioja. 2007. Supporting self-development in service oriented information systems. In Proceedings of the 7th Conference on 7th WSEAS International Conference on Applied Informatics and Communications - Volume 7 (AIC'07), Minh Hung Le, Metin Demiralp, Valeri Mladenov, and Zoran Bojkovic (Eds.), Vol. 7. World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, Wisconsin, USA, 52-57. 6] J.C. Laprie, Dependability: Its Attributes, Impairments and Means. In Predictably Dependable Computing Systems, B. Randell, J.C. Laprie, H. Kopetz, and B. Littlewood (eds.), pp. 1-28, Springer-Verlag, 1995. 7]B. Bloom. Space/time Trade-Offs in Hash Coding with Allowable Errors. In Communications of ACM, volume 13(7), pages 422-426, 1970. . Factographic base for the complex collaborative information resources reorganization S.V. Znamenskij Some Information Resources, especially those addressed the complex issues are known to be continuously improved with a broad range of individuals and organizations. Such refinement is often needed in sudden corrections of the structure of the resource, parallel development and comparative testing of users of multiple versions of its components, removal of excess and restore previously available. The future system architecture is presented. Работа поддержана грантом РФФИ No 09-07-00407. Для контента со слабыми внутренними взаимосвязями и неизменной структурой взаимодействие разработчиков удобно организовать в самой системе, как это делается в википедии и других системах управления контентом. Непрерывная интеграция обещает [Continuous Integration: Improving Software Quality and Reducing Risk, by Paul M. Duvall (Addison-Wesley, 2007) - http://www.amazon.com/gp/product0321336380/?tag=integratecom-20] удешевление и ускорение разработки сложного контента при одновременном повышении качества. Естественные исходные требования к такой системе наиболее близки к описанным в [The characteristics of ULS systems undermine assumptions of traditional software and systems engineering practice. Linda Northrop. Ultra-Large-Scale Systems. The Software Challenge of the Future. June 2006 Unlimited distribution subject to the copyright. Pittsburgh, PA 15213-3890 ]The characteristics of ULS systems undermine assumptions of traditional software and systems engineering practice. 2] The Impact of Scale Linda Northrop: December 17, 2009 © 2009 Carnegie Mellon University http://www.sei.cmu.edu/library/assets/20091217webinar.pdf] требованиям к системам будущего, которые коротко сводятся к пяти ключевым качествам: 1. Децентрализация 2. Противоречивые по своей сути, непознаваемые, и разнообразные требования. 3. Непрерывное развитие и развертывание 4. Разнородные, рассогласованные и изменяющиеся элементы 5. Стирание границы между людьми и системой 6. Устойчивость к ошибкам в исходных данных и при их обработке дополняющим мышление в терминах социотехнической экосистемы, предполагающее: - соревнование за ресурсы - наличие организаций и участников, ответственных за установление политик - наличие организаций и участников, ответственных за производство самой системы - локальные и глобальные показатели здоровья, которые будут подключать необходимые изменения в политиках и в поведении элемента и системы. - дизайн и эволюцию производственных отношений - оркестровку и управление - наблюдение и оценку. Замечание в [2] по поводу этих требований • These characteristics undermine the assumptions we make in most current technical, management, and acquisition approaches. по сути означает необходимость комплексного пересмотра большинства стандартных технических, управленческих и приобретательских подходов. Требование устойчивости к ошибкам становится всё более актуальным и по причине неизбежного технического прогресса [Cristian Constantinescu, "Teraflops Supercomputer: Architecture and Validation of the Fault Tolerance Mechanisms," IEEE Transactions on Computers, pp. 886-894, September, 2000] [J.C. Laprie, ªDependabilityÐIts Attributes, Impairments and Means,º Predictably Dependable Computing Systems, B. Randell, J.C. Laprie, H. Kopetz, and B. Littlewood, eds., pp. 1-28, Springer-Verlag, 1995.]: уменьшение размеров транзисторов и их энергопотребления при повышении быстродействия приводит к усилению эффектов квантовой механики, неотвратимо повышающих вероятность ошибки. Эти аргументы оправдывают поиск архитектуры СУБД основе, ориентированной на разработку и беспрепятственное эволюционирование системы с указанными свойствами. По своей сути конфликта, непознаваемое, и разнообразные требования http://www.troyhunt.com/2011/02/unnecessary-evil-of-shared-development.html Указанный список причин подразумевает стандартную технологию разработки на реляционной основе. О нестандартных технологиях речь никто не ведёт, поскольку в сфере разработки информационных систем любой отход от стандартных технологий разработки связан с многократным удорожанием продукта из-за многократного роста объёмов требуемого кода. Refactoring Databases: Evolutionary Database Design by Scott W Ambler and Pramod Sadalage.: Addison-Wesley Professional (March 28, 2011) Рефакторинг баз данных: эволюционное проектирование. Addison-Wesley Signature Series Скотт В. Эмблер, Прамодкумар Дж. Садаладж Refactoring Databases: Evolutionary Database Design (Addison-Wesley Signature Series) Scott W. Ambler, Pramodkumar J. Sadalage 368 стр., с ил.; ISBN 978-5-8459-1157-5, 0-321-29353-3; формат 70x100/16; твердый переплетофсетная2007, 2 кв.; Вильямс. Идея совместить представление данных на неизменяемых записях, адресуемых с учётом даты-времени и авторства их создания, с динамически формируемыми на этой основе с учётом ролей и предпочтений пользовательскими интерфейсами соблазнительна принципиальными возможностями - видеть любое прежнее состояние в любом интерфейсе; - качественно расследовать критичную ситуацию; - "на лету" исправлять любые ошибки доработки и системного администрирования и ликвидировать последствия этих ошибок. Безусловно, современные коммерческие СУБД позволяют сохранять темпоральную информацию и выявлять попытки подделки Kyriacos E. Pavlou and Richard T. Snodgrass, "The Tiled Bitmap Forensic Analysis Algorithm," IEEE Transactions on Knowledge and Data Engineering 22(4):590–601, April 2010. (pdf) Oracle 10g1 supports transaction-time tables with its workspace manager [13].[13] Oracle Corporation, “Oracle Database 10g Workspace Manager Overview,” Oracle White Paper, May 2005. The Immortal DB project2 aims to provide transaction time database support built into Microsoft SQL Server [10].[10] D. Lomet, R. Barga, M. F. Mokbel, G. Shegalov, R. Wang, and Y. Zhu, “Immortal DB: transaction time support for SQL server,” in Proceedings of the International ACM Conference on Management of Data (SIGMOD), pp. 939–941, June 2005. 1http://www.oracle.com/technology/products/database/workspace_manager/index.html 2http://www.research.microsoft.com/research/db/immortaldb it requires an integrated solution for several problems, including (i) expressive temporal representations and data models, (ii) powerful languages for temporal queries and snapshot queries, (iii) indexing, clustering and query optimization techniques for managing temporal information efficiently, and (iv) architectures (a) XML to support temporally grouped (virtual) representations of the database history, (b) XQuery to express powerful temporal queries on such views, (c) temporal clustering and indexing techniques for managing the actual historical data in a relational database, and (d) SQL/XML for executing the queries on the XML views as equivalent queries on the relational database.. This approach achieves full-functionality transaction-time databases without requiring temporal extensions in XML or database standards, and provides critical support to emerging application areas such as RFID.Fusheng Wang, Carlo Zaniolo, and Xin Zhou. 2008. ArchIS: an XML-based approach to transaction-time temporal database systems. The VLDB Journal 17, 6 (November 2008), 1445-1463. DOI=10.1007/s00778-007-0086-6 http://dx.doi.org/10.1007/s00778-007-0086-6 Wang, F., X. Zhou and C. Zaniolo, 2006. Using XML to build efficient transaction-time temporal database systems on relational databases. Proceedings of the 22nd International Conference on Data Engineering, Apr. 3-7, IEEE Computer Society, Washington DC., USA., pp: 131. DOI: 10.1109/ICDE.2006.168 Novikov, B. and E. Gorshkova, 2008. Temporal databases: From theory to applications. Programm. Comput. Software, Г.Н. Сергеев SR*-дерево: метод индексирования исторических данных Информационные технологии и программирование: Сборник статей. Вып. 3/ Под ред. Е.А. Роганова. -- М.: МГИУ, 2002. -- 64 с. http://www.chair36.msiu.ru/articles/3/html/node54.html [35] G. Weikum and G. Vossen. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann Publishers Inc., 2001. Однако полноценная реализация этих идей предполагает поиск маршрута обхода серии "подводных скал", лежащих на этом пути. Первый и самый крупный из них это непригодность стандартных средств и общепринятых технологий разработки информационных систем и невозможность непосредственного использования готовых решений в области разработки информационных систем. Несмотря на то, что построению темпоральных и битемпоральных СУБД посвящена объёмная библиография в основном пятнадцатилетней давности, Jaymin Patel. Temporal Database System Individual Project Department of Computing, Imperial College, University of London 18 June 2003 1.5 Solutions in developing a Temporal Database The following approaches underline how a temporal database may be created: 1. Use the type date provided by a non-temporal (any commercial) DBMS. 2. Extend a non-temporal data model to a temporal data model by attaching time attributes to each data. 3. Develop a new temporal database system from scratch that provides a primitive data type time and handles the different states/time instances of data being stored. The first and second solution does not involve any changes to existing database technology and may be simple to form as we just build new methods for temporal support on top of the existing database system that will be used. The third solution involves developing a whole new database system with temporal support. This will be difficult as the underlying principles used by commercial DBMS to optimise operations must be reformed and a lot of theoretical work needs to be carried out to show that the new system is fully complete, all new and modified operations perform as required. The amount of time and manpower required for this approach is similar to that needed by commercial vendors to develop DBMS that we all are familiar with today. Thus, this project cannot consider the third solution when developing a temporal database, as this is out of reach in terms of time and manpower available Разумеется, существуют темпоральные СУБД, в которых работают стандартные средства разработки приложений и таблицы которых содержат метаданные, хранящие историю изменений таблицы. Однако индексирование http://yellowstone.cs.ucla.edu/schema-evolution/index.php/Prima schema evolution is transparent to the user: she writes queries against the current schema while retrieving the data from one or more schema versions. "Managing and querying transaction-time databases under schema evolution" Hyun J. Moon, Carlo A. Curino, Alin Deutsch, Chien-Yi Hou, and Carlo Zaniolo. Accepted for publication at Very Large Data Base VLDB, 2008 отказ от стандартных средств и технологий разработки - что делать (организация динамических контекстных уведомлений, напоминаний и быстрой навигации к важным делам и значимым изменениям информации) и 2. Поливалентность (многозначность) - возможность для авторитетных пользователей параллельно и независимо развивать общедоступные альтернативные варианты частей ресурса, интерпретации экспериментальных данных, ветви ПО, версии стандартов и т.п. 3. Контекстная автономность данных, обеспечивающая администрирование (включая системное) авторитетными заинтересованным объединениями пользователей. 4. Проработанность механизмов необременительного выявления и сведения мнений и предпочтений пользователей, ранжирующих версии и помогающих объективно оценивать вклад каждого пользователя. 5. Проработанность инструментов создания/модификации пользовательских интерфейсов, контекстно и индивидуально адаптирующихся к выявляющимся интересам пользователя и изменяющемуся состоянию ресурса. 6. Ограниченность во времени и пространстве данных и гарантированная обратимость последствий любых ошибок человека или исполняемого кода в администрировании, редактирования или обработки данных. Все перечисленные качества представляются существенно важными для любой из перечисленных во введении прикладных областей, а их совмещение несомненно является не менее сложной задачей, чем обеспечение функциональности, специфичной для прикладной области. Подходы к решению проблемы Все знают, что "удобный доступ к истории, возможность восстановления прежнего состояния в любом контексте данных" - это вики. Технология, создавшая крупнейшую энциклопедию мира. Однако во всех вики-системах администраторы скрывают и удаляют правки и целые страницы за неимением других средств снизить их доступность. Но более серьёзным недостатком является невозможность обратимого изменения структуры ресурса. Историчность ограничена рамками отдельной странички, действия над страничками и административные акты в истории не сохраняются и так просто не доступны. Вики не позволяют одновременно поддерживать несколько вариантов раздела с перекрывающимися данными. В них нет средств персонализации интерфейсов, а средства создания новых и улучшения старых интерфейсов если и присутствуют, то либо в виде отдельно разрабатываемых плагинов, либо в виде интерфейсов таких плагинов с сильно ограниченной функциональностью и крайне сомнительной дружелюбностью. Поэтому требуемое качество не может быть достигнуто на базе существующих вики-систем. Классическое средство работы с историей - системы управления версиями. Их общий недостаток в том, что они ориентированы на разработчиков, а не на потребителей. Например, статус каждого представленного файла фиксируется в момент представления. Это несовместимо с исходными требованиями, статус версии и статус ветки должны устанавливаться динамически по итогам тестирования и использования. Продукты категории Groopware ... Системы ERP, BPN ... Разделение указанной функциональности на независимые подсистемы, обменивающиеся сообщениями, крайне проблематично, поскольку оно резко усложняет и без того непростую логику системы и порождает многочисленные ошибки, связанные с отменами или невыполнимостью действий или потерями сообщений, не улавливаемые при отладке подсистем. Поэтому построение системы с указанной функциональностью является принципиально трудной задачей. Подобная задача решается в устойчиво развивающихся информационных системах, непрерывно требующих запредельно крупных вложений в разработку-сопровождение продукта. Описанный комплекс требований не зависит от прикладной области, в которой организуется совместная работа, и может быть реализован в виде универсальной основы, адаптация которой к каждой конкретной прикладной области будет осуществляться локально силами заинтересованного сообщества. Принципиальные особенности системы Особенности пользовательского интерфейса и API 1. Попытка любого изменения данных окончательно и неизменно фиксируется в системе с авторством и временем изменения. Система не предоставляет возможностей для удаления или какой бы то ни было модификации сохранённых данных ни разработчикам, ни системным администраторам. 2. Обычно на запросы пользователей система мгновенно выдаёт заранее заготовленный ответ, который не сможет измениться при повторении запроса в будущем с указанием текущего момента времени. Поэтому никакие ошибки администратора или сопровождающих программистов не лишат пользователя возможности видеть прежние состояния интерфейсов (ср. 1.6). Если запрос идёт на текущий момент, а обработка в данном контексте заметно задержалась (либо перегружен сервер, либо запрос требует длительной обработки), то пользователь мгновенно видит последнее обработанное состояние и время, на которое задерживается обработка. Время высвечивается и при потере связи с сервером. Пользователь может продолжать работать с системой, делать другие запросы, но как только этот обработается, то соответствующая страничка пользователя обновится, а на других появится иконка уведомления. 3. Работающий в системе пользователь видит происходящие в контексте его работы изменения и уведомляется о важных для него изменениях в других контекстах и особенно о коллизиях. Пользователь может работать одновременно в нескольких окнах на одном или разных компьютерах, и если поле формы есть в нескольких окнах, то заполнение поля в одном окне быстро окажется во всех остальных, уберегая пользователя от ошибки. Другие особенности 1. Коллизии могут возникать при изменении одним пользователем данных, изменённых другим пользователем, которых первый по роковому стечению обстоятельств (временная потеря связи, например) мог не увидеть. Для их разрешения необходимо участие человека, именно поэтому о коллизиях уведомляются оба. 2. Коллизии неизбежны например в случае, когда два равноправных центральных сервера системы расположены в различных ЦОДах и связь между ними временно прерывается (двухсерверная система свободна от коллизий при хорошей связи и обеспечивает сильные дополнительные гарантии целостности в случае пожаров, взрывов и прочих неожиданностей). 3. Обработка данных для ожидаемых запросов пользователя происходит в фоновом режиме с оптимизацией в порядке очереди (важные для администратора и массово востребованные результаты обработки обновляются чаще, а результаты, которых вероятно не увидит никто, встают в отдельную "последнюю очередь"). 4. Для учёта пользовательского интереса к различным контекстам данных, каждое чтение информации фиксируется без частого дублирования. Архитектура системы Базовая модель данных Любую слабоструктурированную информацию принято представлять деревом с фиксированным порядком узлов в ветке и поэтому вся информация системы образует единое упорядоченное дерево. Хранится оно в виде записей в базе B+tree или аналогичной. Ключ каждой записи образован путём к соответствующему листу (это логический ключ записи), дополненным строкой времён (момент актуальности исходных данных, результат обработки которых фиксирован записью и момент записи) и идентификатором персоны пользователя. Алгоритм чтения из базы B+tree обеспечивает логарифмическую сложность доступа к значению логического ключа на любой заданный момент времени. При одновременном наличии нескольких записей с общим логическим ключом естественно доминирует опирающаяся на более поздние исходные данные, а если их несколько, то более свежая запись. Такая структура позволяет полностью исключить потери данных из-за коллизий записи и упростить синхронизацию параллельно работающих серверов. Для обеспечения возможности изменения структур данных иерархическая структура данных должна быть дополняется возможностями перемещения веток и изменения порядка узлов ветки. Перемещение ветки не затрагивает имеющихся записей, а отражается в специальной системной ветке клонирования. Чтобы не ломать работающий код перемещение веток "на лету" производится в три этапа: 1. Создаётся живой клон. 2. Сохраняющий в ветке данные код переключается на сохранение в клоне ветки. 3. Клон замораживается и исходная ветка удаляется из логического дерева. Ветка клонирования содержит записи о ссылках, которые учитываются при чтении (но не при записи: запись всегда идёт точно по указанному адресу). Ключ каждой такой записи образован новым адресом, а её значение содержит адреса исходной ветки и фиксированные моменты времени, до которого используются данные и может содержать указание не использовать данных текущей ветки. Таким образом для содержимого ветки указывается алгоритм поиска значения: если в первой ветке на фиксированный момент времени записи нет, то используется вторая, и т.д. Алгоритм действует на всю ветку кроме подветок, для которых другими записями установлены другие алгоритмы. Для ускорения обработки создаётся индекс, ключи которого образованы границами промежутков, на которые полный список листов упорядоченного логического дерева разбивается разными линками. Таких промежутков может быть намного больше, чем ссылок, особенно если ссылки вложенные. Если исходная ветка содержала ссылки, то записи о них копируются при создании клона. Такое исключение рекурсивных обработок снимает угрозу зацикливания, хотя и усложняет алгоритм обновления индекса. Ссылки позволяют создавать новые версии веток без дублирования информации. За счёт ссылок логическое дерево данных может содержать многократно больше веток и узлов, чем физически хранится в базе и поливалентность обеспечивается минимальными затратами. Изменение порядка следования узлов осуществляется созданием указателей на следующий узел. Поскольку порядок следования узлов в клоне должен меняться независимо, от оригинала, то указатели на следующий элемент должны размещаться внутри ветки. Для этого резервируется особый суффикс логического ключа, добавление которого к логическому ключу записи создаёт логический ключ записи-указателя. Значением записи-указателя является идентификатор (=логический ключ) следующего узла ветки. Сами логические ключи-идентификаторы не затрагиваются изменением порядка следования. Необходимость учёта информации из ветки клонирования и индексной информации обеспечивает целостность истории при произвольном редактировании структур ценой трехкратного замедления чтения единичной записи. Контекстная организация В логическом дереве системы могут выделяться ветви с автономным управлением, называемые автономными контекстами данных. Пользователю при запросе доступен только запрошенный контекст. В рамках автономного контекста данных определяются категории пользователей (в отличие от групп, категории не пересекаются). Остальные пользователи включаются в категорию quest. Шаблоны страничек-ответов на запросы и их фрагментов определяются категорией, языком и значимостью для пользователя фрагмента. При обращении пользователя к данным контекста непосредственно или через ссылку-клон фиксируется интерес пользователя к контексту-источнику и формируется текущий показатель заинтересованности пользователей в контексте, который используется для определения приоритетов при обработке очередей фоновых задач. Контекст может использовать родительские пространство имён, шаблоны страничек и фоновые задания либо частично заменять своими. Computer languages, 07.05.Bx 15) Автоматизация проектирования и программирования; ISO 8601 Data elements and interchange formats — Information interchange — Representation of dates and times is an international standard covering the exchange of date and time-related data. It was issued by the International Organization for Standardization (ISO) and was first published in 1988. The purpose of this standard is to provide an unambiguous and well-defined method of representing dates and times, so as to avoid misinterpretation of numeric representations of dates and times, particularly when data is transferred between countries with different conventions for writing numeric dates and times. General principles * Date and time values are organized from the most to the least significant: year, month (or week), day, hour, minute, second, and fraction of second. The lexicographical order of the representation thus corresponds to chronological order, except for date representations involving negative years. This allows dates to be naturally sorted by, for example, file systems. Сортировка произвольных чисел Проблема сортировки отрицательных чисел часто обсуждается в интернет. Обычное решение - добавление большой положительной константы- не работает, когда границы диапазона используемых чисел не фиксированы. Предлагается новая система записи чисел, позволяющая записывать десятичные числа в неограниченном диапазоне значений и точности и обладающая лексикографической упорядоченностью. Решение даётся следующей таблицей. Диапазон изменения описание способа примеры The theory of ordering lexicographic entries: Principles, algorithms and computer implementation Andrzej Ziabicki Computers and the Humanities Volume 26, Number 2, 119-137, DOI: 10.1007/BF00116348 A Version Numbering Scheme with a Useful Lexicographical Order Arthur M. Kellery Je rey D. Ullmanz Stanford University Stanford University Computer Science Dept. Computer Science Dept. Stanford, CA 94305-2140 Stanford, CA 94305-2140 R. Katz, E. Chang and E. Bhateja, ‘‘Version Modeling Concepts for Computer-Aided Design Databases’’, Proc. ACM-SIGMOD 1986 Int’l Conf. on Management of Data, Washington D.C., May 1986. KELLER, A.M., ULLMAN, J.D. (2001): A Version Numbering Scheme with a Useful Lexicographical Order: Technical Report, Stanford University.