Meтки времени для глобальной идентификации версий ○ c С. В. Знаменский Институт программных систем имени А.К. Айламазяна РАН Переславль-Залесский svz@latex.pereslavl.ru Аннотация Децентрализованное управление ре- зервированием, локальными перезапус- ками и обновлением исполняемого в распределённой компьютерной системе кода придаёт системе такие качества интернета как высокая доступность и Рис. 1: Пример асинхронного сбоя (устаревшие катастрофоустойчивость. Система стано- данные помечены красным контуром) вится эклектичной, подверженной потере централизованного управления и непро- тиворечивости. автоматические обновления. Однако только эклектичные системы Децентрализация управления потоками дан- дают возможность опереться на де- ных создаёт проблему системных нарушений централизацию разработок для решения порядка событий. Рисунок 1 поясняет её на сложных междисциплинарных задач. примере простейшей сети из двух узлов, распо- Описана проблема обеспечения до- ложенных в удалении друг от друга, связанных ступности и согласованности данных в двумя каналами. эклектичных компьютерных системах, ре- Узел 𝐴 выдаёт по одному каналу текущий шаемая идентификацией версий данных час 0,1, ..., 23, 0, ..., а по другому - текущие временем изменения. минуты: 0... 59, 0,... Предлагаемая полиритмичная система Узел 𝐵 это часы, запрашивающие данные у автоматического версионирования объек- 𝐴 и выдающие время. тов разделяемой памяти включает в Мы будем считать, что все составляющие си- себя способ компактного единообразного стемы и каналы связи работают безупречно. Это представления меток времени с разным не отменяет возможных задержек изменчивой разрешением и способ обеспечения согла- продолжительности, неизбежных при передаче сованности информации на основе таких данных между узлами. Поэтому около полудня меток. возможны показания 12.59 или 11.00 с ошибкой на час. Пример иллюстрирует особый класс сбоев в Введение компьютерных системах, связанный с нарушени- ем синхронности процессов. Сбой такого рода Для повышения надёжности и качества об- способен разрушать связи родственных данных служивания мультипроцессорных компьютерных в сложных распределённых системах. В роли систем широко используется децентрализованное часов и минут могут оказаться любые син- администрирование. хронно изменяющиеся данные при возможности Без объявления технологических перерывов в распространения по разным путям. Под угрозой обслуживании во многих системах проводятся разрушения оказываются не только связи данных локальные перезапуски подсистем, переключе- наблюдений или их обработки, но и связи фраг- ния на резервные сервисы, автоматические ментов исполняемого кода, метаданных и(или) обновления исполняемого кода. Нередко исполь- исходного кода. зуются резервные копии данных и откатываются Возможность конфликтного сочетания неза- висимых изменений данных может ускользать Труды 15-й Всероссийской научной конференции от внимания разработчиков. Неразумно услож- «Электронные библиотеки: перспективные методы нять систему ради пренебрежимо маловероятной и технологии, электронные коллекции» — ситуации. RCDL-2013, Ярославль, Россия, 14-17 октября 2013 г. 117 1 Угроза асинхронного сбоя разделяющей дефекты технической системы на случайные, вероятность которых можно оце- Определение. Будем называть асинхронным нить с помощью теории и предварительных сбоем (аsynchroniс failure) негативные послед- испытаний, и систематические, выявляемые тща- ствия непредусмотренных задержек или схожих тельным тестированием компонент и системы дефектов синхронизации данных. в целом. Получается, что достаточно сложная Асинхронный сбой выражается в потерях: распределённая система, даже построенная по согласованности — когда информация различ- всем канонам теории надёжности на основе ных версий объекта смешивается; действующих стандартов, требует особых архи- тектурных решений чтобы не оказаться фатально порядка — когда задержки передачи или подверженной асинхронным сбоям [1]. локального восстановления непроизвольно сменяют новое значение старым; данных по тайм-ауту при передачах или слож- 2 Подходы ных расчётах. Теория и практика разработки информационных В результате система может потерять адекват- систем настоятельно рекомендуют базироваться ность, продуктивность или отзывчивость вплоть на стандартах [2], основанных на математической до непригодности. теории предикатов и надёжно проверенных широкой практикой создания систем вчерашнего 1.1 Факторы риска и сегодняшнего дня. Рациональный подход Пример вскрывает факторы асинхронного сбоя: к обеспечению качества информации имеет центральным стержнем 1. Неполнота онтологии системы, допускаю- щей неучтённую связь между данными. 1. Тщательную централизованную проработку логической модели системы. 2. Получение по разным каналам неявно связанных данных извне системы. 2. Чёткую организация разработки, точно следующей выверенной логической модели. 3. Разброс продолжительности прохождения информации обозначим 𝛿 . Тогда вероятность В каждый момент времени система имеет асинхронного сбоя равна 𝜏𝛿 , где 𝜏 это формально непротиворечивое в этой модели средняя продолжительность времени между состояние, которое моментально изменяется на связанными изменениями данных. новое столь же логически целостное состояние. Это означает, что любое событие непо- средственно порождает транзакцию, как бы 1.2 Характер угрозы мгновенно вносящую все сопутствующие из- Особое коварство асинхронных сбоев состоит в менения во все части системы. Параллельно их способности ускользать от тестирования и в могут выполняться только такие транзакции, невозможности воспроизведения. которые никак не взаимодействуют по данным. В отличие от случайных сбоев их вероятность Результат должен быть таким, как если бы все пренебрежимо мала. В штатном режиме задержки транзакции выполнялись последовательно, что малы и стабильны, поэтому статистические проблематично [3, 4]. Такая изоляция строгих оценки результатов тестирования асинхронных транзакций имеет целью создание для про- сбоев не замечают. В нештатных ситуациях граммиста иллюзии (view serializability), что он временные локальные перезагрузки, потери, работает с системой один, чтобы избавить его очереди, блокировки местами удлиняют задержки от сложностей конкурентного взаимодействия. обработки или передачи данных в многие Во многих практических задачах такая иллюзия тысячи раз, создавая практически неповторимые допустима и рациональный подход оказывается сочетания локальных задержек, приводящие к вне конкуренции. асинхронным сбоям. Диагностика и воспроизведение затруднены 2.1 Ограниченность рационального подхода отсутствием достаточно полных сведений о временных локальных перегрузках. Ряд востребованных в ближайшем будущем В результате, спроектированная и испытанная приложений страдает от принципиальных огра- по всем правилам система сбоит в нештатной ничений рационального подхода: ситуации так, что воспроизвести дефект в ∙ Единый лог транзакций [5] ограничивает лабораторных условиях оказывается практически масштабируемость. невозможным. ∙ Для системы, которая по сути долж- Такая скрытность асинхронных сбоев выводит на базироваться на неустойчивой сети их за рамки современной теории надёжности, (например, межпланетные или армейские 118 системы) централизованная обработка показывать. Если разница в задержках 𝛿 не данных неприемлема: временно теряюшие превысит ∆, то такой фильтр исключит ошибку. связь части очевидно должны продолжать Для полного подавления ошибок требуется функционировать корректно и по возможно- ∆ ≫ 𝛿 . При этом часы будут всегда отставать не сти эффективно. Распространённое мнение менее чем на ∆. Уменьшение ∆ повысит риск о том, что известная теорема САР Брюве- ошибки часов, увеличение усилит их отставание. ра [6] противоречит возможности создания Если же ускорение достигнуто оптимизацией таких систем, ошибочно [7, 8]. в штатных ситуациях, то оно вправе не ∙ Гибкость, адаптивность и другие полезные сработать в особом случае, задержка превысит свойства в полной мере реализуемы лишь гистерезисную и сбой произойдёт. многими сильными независимыми коман- Таким образом, гистерезисная фильтрация дами разработчиков при демократическом полезна лишь на входе системы. взаимодействии. Жёсткий упор на цен- Остаётся путь версионирования данных эк- трализацию разработки и сопровождения лектичной системы. резко ограничивает допустимую сложность системы одной головой генерального кон- 3 Эклектичность структора [9]. ∙ Неизменность модели данных не свой- Эклектичность модельного примера лишает ственна долгоживущим системам [10]. эффективности верифицированные протоколы ∙ Монополия централизованной разработ- обмена и обработки информации и строгих ки ограничивает пригодность систем к транзакций. независимой локальной модификации (ин- формационная система крупной корпора- 3.1 Апология эклектичности ции, межгосударственная система взаимной безопасности, интеллектуальная самовос- Популярная идея единой универсальной онтоло- станавливающаяся [11] или эволюциониру- гии, на которой базируются стандарты и теория ющая [12] системы). разработки информационных систем, проекты Semantic Web, Web 2.0 и Web 3.0, к сожа- Любое отклонение от рационального подхода лению принципиально не реализуема. Теорема обостряет проблему изучения и предупреждения Гёделя о неполноте подсказывает, что полная асинхронных сбоев. непротиворечивая онтология возможна лишь для примитивных систем. 2.2 Борьба с задержками Чтобы показать, что онтологии изменчивы в любой практически значимой области, рас- Последний фактор риска — неравномерность смотрим символ астрономической точности — задержек — уменьшается такими мерами как измерение времени. ∙ Использование новейших технологий уско- В сутках 24 часа. Однако в системе, учиты- рения обмена и обработки данных. вающей переход на летнее поясное время, всё ∙ Упреждающая балансировка ресурсов, сни- гораздо сложнее и количество часов в сутках жающая риски перегрузок [13]. иногда оказываться 23 или 25, что зависит от ∙ Поддержание запаса системных ресурсов, административного подчинения. С секундами в обеспечивающего устойчивость к перегруз- минуте сложнее. В последнюю минуту полуго- кам. дия иногда (но почти каждый год) по итогам Эти меры снижают риск возможно в сотни раз астрономических наблюдений вводится допол- кроме систем, которые (само)восстанавливаются нительная високосная 61-я секунда. Никто не или реконструируются в ходе эксплуатации: знает, будет ли последняя секунда следующего восстановление всегда означает существенную года високосной. Более того, Международный неискоренимую задержку. астрономический союз всерьёз обсуждает воз- Если возможно гарантировано ограничить можности отмены високосных секунд в частности время задержки малой величиной, то риск с заменой их високосными часами. асинхронных сбоев можно полностью исключён Даже в математике общеизвестные факты гистерезисной фильтрацией неустойчивых изме- уточняются с новых позиций. Пифагорейцы нений. Для этого результаты каждого запроса хранили в тайне иррациональность корня из двух должны сверяться с предыдущим показанием. поскольку это противоречило понятию числа как Если оно изменилось, то надо скажем каждую отношения. Ещё до рождения Христова было секунду или с другим периодом ∆ запрашивать известно, что сумма углов в треугольнике время снова и пока полученное значение не равна развёрнутому, а квадрат любого числа повторится, считать его неустойчивым и не положителен. Всё это неверно в геометриях 119 Лобачевского и Пуанкаре и алгебре комплексных 3.2 Модель эклектичной системы чисел. В учебниках по математическому анализу написано, что разрывные функции производных Эклектичные системы не похожи на конечные не имеют. Но теория обобщённых функций автоматы: их состояние меняется не мгновен- изучает их производные. но. Это ближе к реальности распределённых В предметных областях, отличных от ма- систем, в которых допускаются переключение тематики и астрономии, уточнение онтологии на резервный сервис, перезапуск локального ещё быстрее выводит на передний край науки сервиса, восстановление из резервной копии и научно-технической политики и становится и иные внезапные приостановки активности. зыбким и неустойчивым. В частности, это верно Для эклектичных систем (ЭС) более адекватной и для сетевых технологий [14]. представляется модель, основанная на идеях Безупречность онтологии оказывается жёстко контекстной автономности из [19] и [20]: ограниченной во времени и привязанной к ∙ ЭС может состоять из подсистем, являю- конкретной сфере приложений. щихся ЭС, и входить в другие ЭС. ∙ ЭС может считывать информацию датчиков, Правильное понимание недолговечно пользовательских интерфейсов и иных источников. Но именно правильное понимание является ∙ ЭС предоставляет доступ основой стандартов разработки компьютерных систем. Вывод парадоксален и неутешите- (1) к актуальной на указанный момент лен: императивные компьютерные системы в версии каждого выработанного ею обозримой перспективе обречены продолжать информационного объекта, разочаровывать пользователей [15]. (2) к описаниям белых пятен истории, т.е. Выход подсказывает общепризнанные прин- промежутков времени переходов к со- ципы разделения труда и разделения зон гласованным состояниям в указанном внимания (separation of concerns). Будущее контексте данных. за надёжными согласованно развивающимися взаимопроникающими системами, улучшаемыми Проблема распределения ресурсов между независимыми группами, компетентными в своих направлениями и темпами обновления и под- областях [16–18]. Такие системы правильно держкой функционирующих сервисов сложна и называть эклектичными. Интернет в целом — многопланова, но делится на очевидные части: это пример эклектичной системы. 1. Уточнение стратегии развития. Негативное отношение, закрепившееся за 2. Определение приоритетов внутренних про- термином и системами, исходит от наивной цессов. мечты об абсолютном знании и отсутствия теории, технологий и примеров согласованных 3. Организация обработки информации в соот- эклектичных систем. ветствии с установленными приоритетами. Не исключено, что технологии эклектичных Рассмотрение первых двух частей выходит за систем откроют путь к эффективной децен- рамки настоящей статьи. Её задача описать трализованной разработке на фоне постоянно систему приоретизированной обработки инфор- доступного качественного сервиса. мации, полностью исключающую асинхронные Подобно тому, как объединив творческие сбои. силы мира Википедия превзошла по ши- роте, полноте, доступности, актуальности и 3.3 Ретроспективность и обновления популярности все лучшие энциклопедии мира, совместное творчество независимых групп раз- Любые данные поступают в эклектичную систе- работчиков [21] способно привести к результату, му с указанием времени. Полезны протоколы превосходящему лучшие ожидания [22]. Речь своевременного получения информации об изме- идёт о качественно превосходной точности, на- нениях (сomet). дёжности и дружелюбности взаимодействующих Если в источнике есть информация о времени компьютерных систем, о самовосстанавливаю- актуальности данных, то она должна быть щихся, эволюционирующих и мультиагентных корректно использована. Иначе идентификаторы системах, о качественном скачке функциональ- версий могут быть сгенерированы на основе ности, надёжности и удобства пользовательских текущего времени. интерфейсов. Вывод данных из эклектической системы по запросу может в основном осуществляться двумя способами: 120 Проспективный означает ожидание когда по- ∙ При обмене информацией между узлами явится версия, актуальная на момент передаются фрагменты истории изменений, запроса или более поздний. а при обработке совместно обрабатываются Ретроспективный [19] означает немедленную или показываются данные, относящиеся выдачу последней на момент запроса версии только к одной версии. данных. На пути реализации этой идеи лежат Проспективный вариант привычно включает многочисленные подводные камни. ожидание завершения обработки всех внесённых на момент запроса данных. Ретроспективный 4 Трудности автоматического версио- непривычен тем, что исключает ожидания нирования обработки. Это напоминает чтение данных их кэша или реакцию поисковых серверов интернет. 4.1 Одновременность Механизм автоматического версионирования заменяет иллюзию изоляции необходимостью Первая проблема состоит в определении того, корректной идентификации версий объектов. какие данные считать одновременно актуальны- Происходившее в системе становится доступным ми, то есть относящимися к одному состоянию не через лог, а через машину времени, показыва- системы. ющую входные и выходные данные в динамике Классические исследования показали запре- обработки. Обработка может программироваться дельную техническую сложность синхронизации на любых языках программирования, а её всех изменений в распределённой компьютерной корректность диагностироваться и отлаживаться системе. Система рассматривалась при этом средствами этих языков. Требуется лишь чтобы как набор конечных автоматов, обменивающих- выходные данные правильно соответствовали ся сообщениями о событиях. Время в ней входным. трактовалось как вспомогательное средство для Гладкое обновление естественно будет проис- выстраивания всех событий в единый линейный ходить поэтапно: порядок. ∙ подготовка и отладка новой версии испол- В интересующей нас эклектичной модели няемого кода системы, время это показания локальных часов, то есть физическая величина, измеренная с некоторой ∙ запуск его в параллель с работающим с ав- точностью. томатическим извещениями о расхождениях Выделить актуальные в общий момент в выходных данных, времени данные далеко не просто по многим ∙ включение в качестве бета-версии с возмож- причинам. ностью мгновенного переключения между Во-первых, окончание актуальности данного версиями, 𝑋 может быть настолько близко к началу ∙ бета-тестирование потребителями, актуальности данного 𝑌 , что момент их ∙ получение статуса базовой версии, одновременной актуальности существует лишь с некоторой вероятностью. ∙ получение статуса резервной версии, Во-вторых, погрешность указания времени ∆ ∙ отключение по причине длительной невос- может варьироваться от наносекунд для данных требованности. быстро протекающих процессов до тысячелетий От программистов потребуется не только для археологических данных. тестирование своей системы, но и сравнитель- В-третьих, конкретная разница во времени ное тестирование версий систем-поставщиков событий может свидетельствовать об одновре- входной информации. менности или о неодновременности событий в Организация исполнения в эклектичных зависимости от постановки задачи. системах может основываться на следующей В-четвёртых, различаются актуальность в схеме: некоторый момент промежутка и актуальность в течение всего промежутка. ∙ Автоматическое версионирование заклады- В-пятых, проблематично корректно совме- вается на низшем уровне, а к нему стить данные, относящиеся к приближенно адаптируются структуры данных и интер- известной общей границе промежутков шкалы фейсы. времени с одним из этих промежутков. ∙ Использование штампа времени в качестве В-шестых, случается, что актуальная досто- метки версии обеспечивает синхронность верная информация недоступна и пользователям данных разной природы и происхождения. порой нужен доступ к новейшим неполным или непроверенным данным. В таких ситуациях 121 разумно предоставлять особый интерфейс к была классификация данных по городам России, неполной сводной информации. а понадобилось ввести административные округа Нужен прозрачный способ безупречно авто- и распределить данные городов по ним. матически выделять одновременно актуальные Сейчас такая структурная перестройка требу- версии данных. Идентификация моментами вре- ет удаления всех веток изменяющегося уровня мени должна и добавления их к добавленным узлам проме- ∙ быть достаточно универсальной, жуточного уровня. Эта операция нарушает связи между элементами структуры, портит предысто- ∙ отражать значение и погрешность проме- рию веток и тем самым делает невозможным жутка актуальности в широких диапазонах, гладкое (без перерывов в обслуживании) об- ∙ позволять быстро и просто собирать новление. Для представления данных, которые последние одновременные данные. должны быть непосредственно доступны с Организация исполнения должна до предела длительной историей структурных изменений, снижать вероятность ситуации, в которой необходима дальнейшая проработка универсаль- обработка задерживается из-за неспособности ных и эффективных гибких структур данных, системы выделить одновременно актуальные поддерживающих эволюцию, см., например, [25]. данные. 4.3 Продолжительные изменения и согласо- 4.2 Эффективность и алгоритмы ванность Работа эклектичной системы должна опираться Пока обработка использует версии данных, на эффективные алгоритмы решения принципи- актуальные на общий момент времени, результат ально новых, ранее не рассматривавшихся задач, однозначно определяется этими данными и таких как идентифицируется тем же временем, угрозы ∙ поддержание и сохранение истории датиро- рассогласования данных не возникнет. Поэтому ванных изменений, сколько бы ни длилась такая обработка, её результат относится к той же версии данных и ∙ обмен фрагментами истории изменений в должен быть помечен тем же временем, чтобы семантике глобальной разделяемой памяти, не нарушить логический порядок. ∙ отбор согласованных версий входных дан- Угроза рассогласование станет явной только ных для совместной выдачи или обработки, если обработка соединит данные, не актуальные ∙ эволюция структур данных во времени. на общий момент времени. Это может случиться В последнем пункте соединяются два направ- и для изменений, помеченных общим временем ления поиска. Во-первых, поддержка истории если одно из данных снова изменилось, а изменений структур традиционно ведётся без допустимое отставание локальных часов отнесло привязки ко времени. Обычная структура в это событие к следующему моменту. памяти либо не хранит историю изменений Если при алгоритмической обработке есть объекта, либо хранит фиксированное количество надежда избежать всего этого, то в пользова- последних изменений, либо (persistent data) тельских интерфейсах проблема остаётся. Как хранит полностью, но только порядок событий бы тщательно ни были отфильтрованы для без привязки ко времени. Последнее практиче- пользователя согласованные данные, привычное ски означает экспоненциальный рост требуемых использование дополнительных источников ак- ресурсов памяти. туальной информации может сделать результат Привязка ко времени позволила бы без дуб- неадекватным. лирования информации постоянно поддерживать Это придётся учитывать при создании поль- достаточное число снимков данных (snapshots), зовательских интерфейсов. Недостаточно просто синхронно забывая данные промежуточных из- принимать все меры к тому, чтобы инфор- менений [23]. мация в интерфейсе для пользователя была Например, можно сохранить все ежечас- предельно актуальной и полной. Важно правиль- ные снимки прошлого месяца, все ежедневные но идентифицировать результат. Идентификатор прошлого года, чтобы существенно сэконо- должен остаться прежним лишь в случае, когда мить ресурсы памяти, оставляя доступной для пользователь действовал по ранее установлен- разнообразной обработки (такой как машина ному алгоритму и не использовал сторонней времени [24, 26–28]) значимую часть истории. более поздней информации. Иначе при сохране- Во-вторых, это поддержка эволюции структур нии идентификатор должен корректно отразить данных. Для иерархической структуры (скажем, возникший разброс времени и вероятен кон- дерево XML-документа) это прежде всего появ- фликт для разрешения которого потребуются ление промежуточного уровня иерархии. Скажем, адекватные инструменты. 122 5 Система и перспективы мейства однозначно определяется своей середи- ной. Множество середин таких полусегментов 5.1 Способ кодирования времени совпадает с B Шкалой 𝑆 назовём разбиение числовой прямой Простота идентификации полусегментов би- на полусегменты равной длины, называемой нарного семейства делает их привлекательными шагом дискретизации. Шаг дискретизации опре- для использования в качестве идентификаторов деляется прикладными задачами и должен быть моментов событий с учётом погрешности опреде- практически несущественным. Например, для ления времени. Например, момент события, пред- полученных из веб-формы данных не имеет шествовавшего моменту 2 с точностью примерно практического значения, нажал ли пользователь 0.1%, идентифицируется как 1.11111111111(2) . кнопку отправки десятой долей секунды раньше Для ускорения поиска нужной версии в или позже. бинарном дереве важно чтобы идентификато- Правый конец в полусегмент не входит, ры были лексикографически упорядочены по этим из предыстории исключаются события, на актуальности. Несмотря на простоту и есте- обработку которых не было времени. Базовый ственность, порядок при таком представлении пример даёт разбиение на целочисленные не согласуется с желаемым лексикографическим: промежутки [𝑛, 𝑛 + 1), 𝑛 ∈ Z. правый конец полусегмента 𝑡 существенно более Мы будем использовать глобальные отметки значим, чем левый 𝑡 − 𝛿 . времени (Новый год, полночь и т.д.) как К сожалению, количество дней в году и разделители. Поскольку потребуется отчёт за другие соотношения мер времени не являются год, то каждое событие должно определённо степенями двойки (и, к тому же, не все являют- относится либо к прошлому году, либо к ся заранее фиксированными числами). Моменты будущему. Сложность с событием, произошедшим времени практически задаются конечными набо- в момент такого разделителя: допустимая рами 𝑡 = (𝑌, 𝑀, 𝐷, ℎ, 𝑚, 𝑠, 𝜇0 , 𝜇1 , ...) из указаний погрешность часов позволяет отнести его в одних года 𝑌 , месяца 𝑀 , дня 𝐷, часа ℎ, минут 𝑚, подсистемах к предшествующему разделителю секунд 𝑠, миллисекунд 𝜇0 , микросекунд 𝜇1 и т.д. полусегменту, а в других к последующему за Предложение 2. Функция разделителем. В таких случаях логически неправомерно 𝑥(𝑡) = 2−3 𝑌 + 2−7 (𝑀 − 1) + 2−12 (𝐷 − 1) производить обработку данных на момент конца + 2−18 ℎ + 2−24 𝑚 + 2−30 𝑠 года и нужно выбирать момент, на который ∑︁ + 2−30−10𝑘 𝜇𝑘 череда изменений приостановилась. Пользова- 𝑘>0 теля однако может интересовать состояние на конец года. По-видимому, лучшее, что может монотонно и однозначно представляет момен- сделать система в этой ситуации, это выдать ты времени двоичными дробями. корректный ответ на близкий момент времени. Замечание 1. Функция теоремы 2 переводит В ситуации продолжительной высокой интен- привычные шкалы времени (годы, месяцы, дни, сивности конфликтующих изменений входных недели, часы и т. д) в шкалы бинарного данных, в которой пользователя интересует не семейства. только (вероятно отдалённый) момент истины, но заведомо логически небезупречная оперативная Например, 13:35 30 июня 2014 года с се- оценка текущего состояния дел. кундной точностью идентифицируется двоичной Для получения такой оценки можно игнори- дробью ровать несущественные расхождения во времени, 𝑥 =2014 · 2−3 + 29 · 2−7 + 13 · 2−12 но при записи результата указать оценку дефек- та (времени рассогласованности) 𝜏 . Эта оценка + 35 · 2−18 + 0.5 · 2−24 + 2−31 должна быть использована при выдаче пользо- =11111011.110 0101 11101 01101 100010 111111 1(2) вателю предупреждения о размере возможной =211 − 100.001 1010 00010 10010 011101 000000 1(2) . некорректности данных. Одновременное использование многих шкал Следующее утверждение описывает ускоряю- нуждается в их согласованности, означающей щий сравнение переход от чисел произвольной что из двух пересекающихся полусегментов длины со знаком к битовым массивам (строкам один обязательно содержит другой. Обозначим произвольной длины). B = {𝑘 · 2𝑙 |𝑘, 𝑙 ∈ Z} множество всех двоичных Предложение 3. Кусочно-линейная функция дробей и назовём бинарным семейством такое (︂ )︂ семейство шкал, все сегменты которого имеют 1 sgn(𝑥) 3 1 + |𝑥| 𝐵(𝑥) = + 1 − 𝑘(𝑥)+1 − 2𝑘(𝑥) , где вид [𝑡 − 𝛿, 𝑡) = [𝑘 · 2𝑙 , (𝑘 + 1) · 2𝑙 ), где 𝑘, 𝑙 ∈ Z. 2 2 2 2 Предложение 1. Полусегмент бинарного се- 𝑘(𝑥) = ceil (log2 (1 + |𝑥|)) , 123 непрерывна, монотонна и взаимно-однозначно отображает множество B всех двоичных дробей на (0, 1) ∩ B. Для промежутка c 1984 по 2112 годы это выражение удобно масштабируется 𝐵(𝑥(𝑡) − 211 и упрощается до 𝐵(𝑥(𝑡) − 211 = 12 + 𝑥( 𝑡)2 потому что |𝑥 − 1| < 1. Для длительности 𝛿 удобнее суточный масштаб времени 2𝐵(−21 2𝑥(𝛿)) − 1, а Рис. 2: Устойчивость системы к асинхронным для дефекта 𝜏 минутный 2𝐵(−22 4𝑥(𝛿)) − 1. сбоям (устаревшие данные помечены контуром) Замечание 2. Обратная к 𝑦 = 𝐵(𝑥) функция вычисляется по формуле системные, обеспечивающие сопровождение со- гласования стратегии развития, планирования и 𝑥 =1 + sgn(2𝑦 − 1) 3𝛼 − 2𝛼2 |2𝑦 − 1| − 1 , где (︀ )︀ реализации обновлений, мониторинга состояния 𝛼(𝑦) = 2𝑘(𝑦)−1 , системы и уточнения приоритетов исполнения. ˜ Системная архитектура должна незаметно для 𝑘(𝑦) = − floor (log (1 − |2𝑦 − 1|)) . 2 прикладных программистов обеспечивать, что старый согласованный результат останется в Замечание 3. Количество значащих цифр действии и будет обновлён лишь когда пол- после запятой в двоичной записи 𝐵(𝑥) ностью соберётся требуемая для согласованного равно сумме |𝑘(𝑥)| и количества цифр в обновления информация, см. рисунок 2. записи двоичной дроби |𝑥| + 1, взятого без Процессу доступны упорядоченные списки заключительных нулей. версий каждого объекта входных данных для В частности, образ 𝐵(𝑥(𝑡) − 211 ) 34-значной обработки. Системный планировщик определяет двоичной дроби из последнего примера длиннее идентификатор версии объектов результата об- записи самой дроби на два знака поскольку для работки и обеспечивает обработчику быстрый неё 𝑘(𝑥) = 2. доступ к версиям объектов, которые долж- Для полусегментов [𝑡 − 𝛿, 𝑡) и дефектов 𝜏 ны быть включены в обработку. Прикладная требуется монотонно закодировать лексикографи- программа-обработчик (бинарный код или скрипт чески упорядоченные вектора из записи двоичных на любом языке программирования) обраба- дробей 𝐵(𝑥(𝑡)), 𝐵(212 𝑥(−𝛿))𝐵(224 𝑥(−𝜏 )), ). тывает пакет изменившихся входных данных. Пакетная обработка известна как средство Замечание 4. Можно монотонно закодиро- резкого ускорения обработки данных [30]. вать лексикографически упорядоченные вектора Запуск очередной обработки данных осу- из записи двоичных дробей (︁ 𝑥2 , 𝑥3 ) ∈ [0, 1] (𝑥1 , )︁ ществляется системным планировщиком в уста- ∑︀3 length(𝑥𝑖 ) строками из 𝑖=1 ceil 6 + 2 байт, новленном для процесса ритме (аналогично [29]). принимающих 65 различных значений. Если предыдущая обработка этого процесса не Для этого битовый массив разбивается на завершилась, то запуск отменяется. группы по 6 бит, последняя дополняется нулями, Результат может быть сохранён с версией каждая группа бит кодируется байтом (Base64) (𝑡, 𝛿, 𝜏 ) если версия любого использованного при и 𝑥𝑖 представляется строкой (в нашем примере обработке объекта 𝑜 удовлетворяет условию, длины 6 байт). Пусть «!» - байт с меньшим зависящему от положительности 𝜏 . кодом, чем использованные в Base64. Тогда 𝜏 > 0, 𝑡 − 𝛿 ≤ 𝑡𝑜 − 𝛿 < 𝑡𝑜 + 𝜏𝑜 ≤ 𝑡 + 𝜏 ; конкатенация 𝑥1 .«!».𝑥2 .«!».𝑥3 даёт эффективную 𝜏 = 0, 𝑡 − 𝛿 ≤ 𝑡𝑜 − 𝛿 < 𝑡𝑜 = 𝑡𝑜 + 𝜏𝑜 ≤ 𝑡 и некоторое кодировку для замечания 4. время после 𝑡𝑜 ; объект не менялся История изменений информационного объек- При запуске обработки правый конец отрезка- та предстаёт упорядоченным по актуальности идентификатора результата выбирается на шкале списком версий. Представление этого списка в с ритмом запуска обработки так, чтобы оказаться виде структуры 𝐵 + 𝑇 𝑟𝑒𝑒 [31, 32] обеспечивает на шкале с наибольшим шагом. Идентификатор быстрый доступ к актуальной на любой заданный всегда должен быть больше предыдущего момент версии. Версии с недостаточно высокими сохранения, но меньше текущего момента. значениями при этом быстро пропускаются. Длина полусегмента 𝛿 изначально берётся вдвое меньше, чем было в предыдущей со- 5.2 Способ организации исполнения хранённой версии результата этого процесса и 𝜏 = 0. Если для такого результата не хватает Функционирование эклектичной системы рас- актуальных входных данных, то 𝛿 увеличивается падается на процессы обработки данных. Это вдвое, если не помогает, то ещё вдвое, а если как прикладные сервисные процессы, так и и это не помогает и есть другие варианты 124 выбора для 𝑡, то проверяются они и если версия [6] S. Gilbert, N. A. Lynch. Perspectives on the не выбирается и есть давно необработанные CAP Theorem // IEEE Computer Society. – входные данные то появляется 𝜏 > 0, 2012.– P. 30–36. Последнее обеспечивает мягкую деградацию [7] K. P. Birman et al. Overcoming CAP with качества сервисов при перегрузках и аномальных consistent soft-state replication // Computer. задержках (передачи и исполнения) и незамедли- — 2012. – Т. 45. – № 2. — С. 50–58. тельное полное восстановление качества сервисов [8] С. В. Знаменский. Ретроспективная основа при исчезновении перегрузок и задержек. распределённой памяти для изменчивой вычислительной среды // Материалы VI 6 Выводы Международной конференции «Параллель- ные вычисления и задачи управления» 1. Эклектичные компьютерные системы обе- (PACO’2012). – М.: ИПУ РАН, 2012. – щают качественное превосходство по важ- Т. 2. – С. 259–272. нейшим показателям. [9] I. Sommerville, D. Cliff, R. Calinescu, 2. Конфликты версий неизбежны внутри J. Keen, T. Kelly, M. Kwiatkowska, J. Mc- сложных эклектичных систем. Dermid, R. Paige. Large-scale Complex IT 3. Автоматическое версионирование на ос- Systems // Communications of the ACM. – нове меток времени открывает путь к 2012. – V. 55, Issue 7. – P. 71–77. исключению таких конфликтов. [10] V. Andrikopoulos, S. Benbernou, 4. В начале этого пути теоретическая про- M. P. Papazoglou. On the evolution of работка и создание новых алгоритмов и services // IEEE Transactions on Software структур данных. Engineering. – 2012. – V. 38, Issue 3. – P. 609–628. 5. Описаны способ маркировки моментов событий и способ корректной организации [11] E. Hollnagel. From protection to resilience: исполнения в эклектичных системах. Changing views on how to achieve safety // 8th International Symposium of the Australian Aviation Psychology Association. Список литературы – Sydney, Australia, 2008. [1] M. Ghafari, P. Jamshidi, S. Shahbazi, [12] I. Fehérvári, W. Elmenreich. Evolutionary H. Haghighi. An architectural approach methods in self-organizing system design to ensure globally consistent dynamic // Proceedings of the 2009 International reconfiguration of component-based systems Conference on Genetic and Evolutionary // Proceedings of the 15th International Methods. — 2009. – P. 10–15. ACM SIGSOFT Symposium on Component- [13] T. Chalermarrewong, S. See, T. Achalakul. based Software Engineering (CBSE’2012). – Parameter Prediction in Fault Management Bertinoro, Italy, June 2012. Framework // Proceedings of The [2] J. Kasser, D. K. Hitchins. Unifying systems International Symposium on Grids and engineering: Seven principles for systems Clouds (ICGC 2012). – 26 February– engineered solution systems // The 20th 2 March 2012, Taipei, Taiwan. International Symposium of the INCOSE. – – http://pos.sissa.it/archive/conferences/153/ Denver, 2011. – P. 1–11. 005/ISGC%202012_005.pdf – 2012. — Т. 1. – P. 5. [3] H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, P. O’Neil. A Critique of ANSI [14] C. M. Kelty. Conceiving Open Systems // SQL Isolation Levels // Proc. of the Wash. UJL & Pol’y. – 2009. – Т. 30. – ACM SIGMOD International Conference on P. 139. Management of Data. – 1995. – P. 1–10. [15] Y. Merali, T. Papadopoulos, T. Nadkarni. [4] R. Normann, L. T. Østby. A theoretical study Information systems strategy: Past, present, of ’snapshot isolation’// ICDT. – 2010.– future? // J. Strateg. Inform. Syst. – 2012. – P. 44–49. http://dx.doi.org/10.1016/j.jsis.2012.04.002 [5] С. Д. Кузнецов. Транзакционные параллель- [16] P. Feiler, R. P. Gabriel, J. Goodenough, ные СУБД: новая волна // Труды Института R. Linger, T. Longstaff, R. Kazman, M. Klein, системного программирования РАН. – 2011. L. Northrop, D. Schmidt, K. Sullivan, — T. 20 – http://cyberleninka.ru/article/ K. Wallnau. Ultra-Large-Scale Systems: The n/tranzaktsionnye-parallelnye-subd-novaya- Software Challenge of the Future // Technical volna. Report. – Carnegie Mellon University Software Engineering Institute. – 2006. 125 [17] L. M. Northrop. Ultra-Large-Scale Systems: [27] Ragib Hasan. Trustworthy History and Scale Changes Everything // SMART Ultra- Provenance for Files and Databases // PhD Large-Scale Systems Forum. – March 6, thesis, University of Illinois at Urbana- 2008. Champaign. – Urbana, Illinois, October 2009. [18] C. Ncube. On the Engineering of Systems of [28] G. Fourny, D. Florescu, D. Kossmann. A Systems: key challenges for the requirements time machine for XML // Technical report engineering community // Requirements № 734. – ETH Zurich, Switzerland, 2011. Engineering for Systems, Services and [29] J. Wang, K. Y. Lam, S. Han, S. H. Son, Systems-of-Systems (RESS). – Aug. 2011. – A. K. Mok. On Co-Scheduling of Periodic P. 70–73. Update and Application Transactions with [19] С. В. Знаменский. Ретроспективная осно- Fixed Priority Assignment for Real- ва совместной реорганизации сложных Time Monitoring // Advanced Information информационных ресурсов // Электрон- Networking and Applications (AINA). – 2012 ные библиотеки: перспективные методы IEEE 26th International Conference. – 2012, и технологии, электронные коллекции». March. – P. 253–260. – RCDL-2011. – Воронеж, Воронежский [30] A. Thomson, T. Diamond, S. C. Weng, госуниверситет, 2011. – С. 93–101. – K. Ren, P. Shao, D. J. Abadi. Calvin: http://ceur-ws.org/Vol-803/paper10.pdf fast distributed transactions for partitioned [20] P. Helland, D. Haderle. Engagements: database systems // Proceedings of the 2012 Building Eventually ACiD Business international conference on Management of Transactions // 6th Biennial Conference Data. – 2012, May. – P. 1–12. on Innovative Data Systems Research (CIDR [31] Г. М. Адельсон-Вельский, Е. М. Ландис. ’13). – January 6–9, 2013. – 12 pp. Один алгоритм организации информации // [21] S. R. Jeffery, L. Sun, M. DeLand, N. Pendar, Доклады АН СССР. — 1962. — Т. 146, R. Barber, A. Galdi. Arnold: Declarative № 2. -– С. 263–266. Crowd-Machine Data Integration // 6th [32] L. Jiang, B. Salzberg, D. Lomet, M. Barrena. Biennial Conference on Innovative Data The BT-Tree: A Branched and Temporal Systems Research (CIDR ’13). – January 6-9, Access Method // VLDB’00 Proceedings. – 2013. – 8 pp. 2000. – P. 451–460. [22] W. Van Osch, M. Avital. Collective Generativity: The Emergence of IT- Induced Mass Innovation // Proceedings Timestamps for a global version of JAIS Theory Development Workshop. – identification http://sprouts.aisnet.org/9-54. Sergej Znamenskii [23] J. Stender, M. Hogqvist, B. Kolbeck. Loosely Decentralized management of data restore, local time-synchronized snapshots in object-based restarts and code updates for a distributed computer file systems // Performance Computing system gives the system some of such the Internet’s and Communications Conference (IPCCC). – qualities as high availability and disaster recovery. IEEE 29th International. – IEEE, 2010. — The system becomes eclectic, prone to loss of P. 188–197. centralized control and consistency. However, only the eclectic systems make [24] L. Shrira, C. van Ingen, R. Shaull. Time it possible to rely on the decentralization of travel in the virtualized past: Cheap fares development to solve complex interdisciplinary and first class seats // Haifa Systems and problems Storage Conference. – SYSTOR 2007. The article describes the problem of ensuring [25] Yu. Rogozov, A. Sviridov, S. Kucherov. the data consistency and availability in eclectic Meta-Database for the Information Systems computer systems to be solved with timestamp- Development Platform // 6th Spring/Summer based versioning. Young Researchers’ Colloquium on Software Proposed polyrythmic system of automatic Engineering (SYRCoSE 2012), – P. 164–171. versioning of shared memory objects includes short [26] P. Ta-Shma, G. Laden, M. Ben-Yehuda. uniform presentation of timestamps with different Factor: Virtual machine time travel using resolution and a timestamps-based way to ensure continuous data protection and checkpointing consistency. // Operating Systems Review. – 2008. – V. 42, Issue 1. – P. 127–134. 126