авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 26 |

«Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции English Труды RCDL 2010 ...»

-- [ Страница 6 ] --

Переход от старой версии системы к новой тре- Ниже приводится набросок модели информаци бует внесения сложно согласованных изменений в онных процессов, не нуждающейся в изоляции про структуры данных. Модификация может потребо- цессов, допускающей ничем не ограниченную даль вать значительного времени. В промежуточном со- нейшая разработку работающей системы при под стоянии система не будет доступна пользователям. держке самой системы, ни на секунду не лишающей Перевод одной сложной внутренне согласованной пользователей доступа к прошлой информации и системы в сложную систему с другой онтологией возможностей сохранить изменения в ней даже при всегда является сложнейшей задачей, решение ко- единичных случаях гибели системных процессов, торой сопряжено с потерями второстепенного дос- ошибок разработчиков и администраторов. Все тупа. сформулированные проблемы могли бы решаться в При многократных обновлениях в результате ней вполне прозрачно и в комплексе. Это означало неизбежна утрата доступа к временно забытым дан- бы, что реляционная модель не всегда является аде ным. кватным средством и требует замены для практиче ски важного класса информационных систем.

2.3.3 Проблема системных сбоев и исправления Проверка этой гипотезы невозможна без приня последствий ошибок в коде и администрирова тия её за основу, проработки альтернативной моде нии ли и доведения её до полнофункционального со Полностью взять рутинную работу по полноцен- стояния.

ному воспроизведению ранее достигнутого доступа 3 Принципы асинхронной контекстно на себя, освободив разработчиков и администрато автономной модели управления данны ров для конструктивной деятельности, реляционная ми для сложных адаптивных систем система вряд ли сможет в принципе. Но именно это было бы крайне ценно не только для разработчиков Изложенные выводы иллюстрируют гипотетич и администраторов, но и для обычных пользовате ную бесперспективность реляционных СУБД в ре лей, страдающих от потери старого привычного шении сложных задач организации совместной дея доступа к давно не востребовавшейся информации тельности. Выглядит очевидной неадекватность рассматриваемому классу задач реляционной моде- У процесса есть хозяин – человек, который несёт ли, персональную ответственность за осуществление • этой цели.

опирающейся на неизменную в процессе Цель может разделяться на этапы, подзадачи, обработки запросов онтологию системы;

подцели и т. п., для реализации которых порожда • требующей поддержания сверхзатратного ются дочерние процессы. Поэтому каждый процесс для сложных систем согласованного состояния сис кроме универсального процесса общего функцио темы в целом;

нирования системы имеет единственного родителя, • обещающей недостижимую в реальности который иногда может измениться.

возможность глобальной обработки запросов про Дерево процессов может расширяться по уста извольной сложности посредством ACID транзак новленным сценариям. Каждый сценарий содер ций;

жится в данных процесса сопровождения этого сце • на практике эклектично разделяющей нария (мастер-процесса), которые в свою очередь сложные системы на взаимодействующие части.

могут строиться по сценарию, определённому чаще Отказ от реляционной модели в высшей степени в другом мастер-процессе. Указатель на корень болезнен и требует усилий, многократно превы сценария берётся в данных корня ветки растущего шающих затраты на создание системы сходной по сценарию процесса либо в данных ближайшего функциональности на традиционных технологиях, предка этого корня, где он прописан. Расширяемый поскольку именно на реляционную модель ориен по сценарию процесс обязательно имеет в данных тированы практически все существующие стандар строку, идентифицирующую статус, определяющий ты построения информационных систем, подсисте наследуемые из мастер-процесса код и данные.

мы и пользовательские интерфейсы, мощные сред Процесс может совпасть со своим мастер-процессом ства разработки и обширная учебная литература.

или мастер-процессом своего мастер-процесса.

Поэтому такой отказ должен опираться на альтер Процесс может не иметь собственных данных, опи нативную достаточно общую модель с глубоко раясь на данные родительских мастер-процессов.

проработанными основаниями, гарантированно бо Так изначально устроены многие подпроцессы, на лее адекватную в широкой прикладной области.

пример, подпроцесс сбора пожеланий по улучше В качестве такой области в статье рассмотрена нию, имеющийся в каждом процессе.

организация совместной целенаправленной дея Если наследуемого данного не прописано в дан тельности, а в основу модели заложены такие каче ных самого процесса и для заданной статусной ства, которые существенны для успешности органи строки в мастер-процессе, то это данное берётся из зации совместной деятельности и важность которых (пра-)родительского процесса.

общепризнанно подтверждена широкой практикой.

Все процессы подразделяются на самостоятель Такие общепринятые основы организации со ные (не наследующие данных из родительских про вместной деятельности отражены в стандартах до цессов) и подчинённые (не имеющие данных, кото кументооборота и управления качеством и в описа рые могли бы наследоваться). Любой подчинённый ниях корпоративных информационных систем. Хотя процесс легко делается самостоятельным. Возмож такие источники не содержат описания модели ность лишения самостоятельности потребует ус управления данными, но содержащиеся в них клю ложнения системы, которое сможет при необходи чевые рекомендации ниже интерпретированы как мости быть добавлено в ходе эксплуатации без при базовые принципы асинхронной контекстно остановки сервиса.

автономной модели управления данными и соответ Данные самостоятельного процесса и подчинён ствующей архитектуры ИС.

ных ему дочерних и (пра-)внучатых процессов об разуют общий автономный контекст данных этих 3.1 Процессный подход к управлению качеством процессов.

Базовым классом системы является информаци Процесс, выполнивший свою цель, засыпает, и онный процесс в широком понимании. Это могут система забывает о его существовании. Спящий быть процессы совместной подготовки и принятия процесс, данными которого интересуются, пробуж решения, поддержания в актуальном состоянии ин дается при наличии изменений в ранее использо формационного ресурса или его части, уточнения ванных им данных этого и других процессов и сво пользовательского профиля и настроек пользова бодных ресурсов системы. Оценка наличия свобод тельских интерфейсов, выполнения сложных расчё ных ресурсов учитывает приоритет процесса, уста тов или иной обработки информации. Сопровожде новленный разработчиком или администратором.

ние, переработка процесса и создание новых сцена риев осуществляются на языке высокого уровня в 3.2 Пользовательский контроль произошедших рамках самостоятельных процессов. изменений У процесса предполагаются данные, которые Заходя в систему, пользователь видит не только могут изменяться этим процессом и читаться им и текущее состояние, но персонализованную индика другими процессами и приведение которых в адек цию изменений, произошедших с окончания преды ватное текущей ситуации состояние является ос дущей сессии.

новной целью процесса.

• Элементы информации на экране пользователя пометку процессов с изменившимися вход снабжены иконками-индикаторами наличия и каче- ными данными и процессов, выходные данные ко ства изменений с возможностями просмотра исто- торых используются;

рии изменений и перехода на время любого из из- • выделение процессов, первоочерёдно тре менений или иное время. бующих обработки данных, и запуск обработки.

Два последних времени перехода образуют про- Появление, исчезновение и любое изменение межуток, наличие и характер изменений за который информации фиксируются в базе типа B+tree от показаны на экране. дельной записью, отражающей значение созданного Если одно из них текущее, то происходящие в или изменённого атрибута или функции. Ключ та системе изменения немедленно отражаются на эк- кой записи содержит по порядку:

ране. • идентификатор (возможно, составной) про цесса, характеристики (либо данного) процесса;

3.3 Эффективный доступ к истории изменений • идентификатор (возможно, составной) объ екта либо список аргументов функции в порядке Эффективность доступа к истории изменений убывания критичности обновлений;

базируется на том, что любое отображение инфор • мации на экране пользователя – это отображение идентификатор имени атрибута или функ сохранённой и впредь неизменной страницы исто- ции;

• рии изменения данных в системе. возможно дополнительно текстовая кон Для упрощения анализа изменений и снижения станта;

затрат на выдачу информации: • разделитель;

• информация хранится маленькими фраг- • список моментов времени, последним из ментами;

которых является время модификации записи;

вре • каждое изменение любого элемента или мя представляется в лексикографически монотон шаблона фрагмента фиксируется отдельной запи- ной кодировке, а моменты в типичном случае явля сью в базе;

ются концами промежутка времени, в котором про • при чтении значения шаблонов фрагментов изводились изменения;

• и данных на запрошенный пользователем момент разделитель;

времени рекурсивно подставляются;

• байт реальности данных, позволяющий вы • быстрый доступ к состоянию элементарно- делить ссылки на записи и отладочные данные;

го данного на момент времени и к истории измене- • идентификатор пользователя.

ний гарантируется хранением записей в глобальной Начало ключа записи до первого разделителя – базе В+tree [41, 42];

это логический ключ данного. Кроме логического • индексация данных для поиска организует- ключа, ключи записей должны содержать «дату и ся на тех же принципах, так что результаты поиска подписи», т. е. штамп времени и идентификатор ав всегда отражают состояние индексов на момент тора изменения.

времени, указанный в запросе. Дополнительное включение в состав ключа за писи байта реальности данных обеспечивает воз 4 Архитектура системы можность незаметного для обычных пользователей тестирования обновляемых частей системы. Перед В серверной части системы работают два неза- картиной реальных данных как бы встаёт невиди висимых базовых процесса, каждый из которых мый для обычных пользователей слой тестовых из поддерживается многими процессами ОС. менений в реальных данных, позволяющий полно Процесс взаимодействия с пользователями ценно выверить и отладить новый код и включить обеспечивает: его в работу с реальными данными без приостанов • выдачу любой предусмотренной информа- ки основного сервиса.

ции на любой заданный пользователем момент вре- Значением записи может быть произвольный мени;

текст, в котором может быть сериализована произ • индикацию изменений, произошедших за вольная структура. Для повышения эффективности истекший период;

хранения и обработки изменений большие структу • оперативное обновление отображаемой ин- ры и тексты должны разбиваться на отдельно хра формации;

нящиеся составляющие. Например, перестановка • сохранение полученных от клиентов дан- абзацев в тексте, совместно редактируемом пользо ных без обработки. вателями, должна сохраняться и показываться поль Процесс обработки информации обеспечивает: зователю как перестройки списка, а сами абзацы • контроль уровня загруженности системы;

должны показываться неизменными.

• Наравне с производственными процессами тре переработку полученных изменений ин буется информационно обеспечить процесс балан формации в оптимизированные для быстрого чте сировки обновлений системы, данными которого ния базы данных;

являются исполняемый код, информация об уровне текущей загруженности системы, востребованности • обработки различных контекстов в данный момент, момент последнего изменения использо наличии необработанных изменений и т. д. Для это- вавшихся в контексте данных других контекстов го в каждом автономном контексте поддержива- (модифицируется при записи любых данных).

ются: Такая основа принципиально позволяет на фоне • список пар (логический ключ данного, достаточно изолированных человеческих ошибок, идентификатор использовавшего его контекста) об- программных сбоев и поломок оборудования гаран новляется при чтении данных из других контекстов;

тировать:

• • функция проверки доступности пользовате- неизменность и быструю доступность (с лю данных контекста, возвращающая процедуру учётом авторизации) всей имеющейся информации;

• определения доступности данного по логическому высокую сохранность информации и пол ключу данного и категории пользователя и при не- ную воспроизводимость прежнего доступа;

обходимости расширяющая этот список;

• возможность организации наследования • функция определения категории пользова- данных, инкапсуляции изменений, каскадных сти теля (при изменении в ролях пользователя в авто- лей, политик и настроек;

номном контексте или иных влияющих на доступ • возможность безопасной организации от событиях его категория перевычисляется) и её те- ладки любых изменений кода в работающей систе кущие значения для пользователей с особыми пра- ме (например, миграции) без предоставления разра вами;

ботчикам доступа к секретным данным;

• момент последнего изменения данных кон- • возможность организации автоматического текста (модифицируется при записи любых дан- оптимального выделения и пометки для последую ных);

щего физического удаления наименее ценных давно устаревших записей.

Рис. 1. Схема потоков информации В случае большой базы вероятность конфлик та на уровне страниц памяти на порядки ниже ве 4 Производительность и проблема па роятности конфликта на уровне файла. Однако раллельной обработки такой подход сопряжён с высокой сложностью Узким местом масштабируемости СУБД явля- своевременной диагностики возможности возник ется эффективная параллельная обработка. На- новения конфликтов. Трудно предсказуемые кон глядным частным случаем является проблема фликты возникают при балансировке дерева и поддержания B+tree-базы данных. Проблем нет, асинхронной записи. В результате запрос на чте если чтение и запись разделены по времени, но ние может вернуть результат, отличный от того, такое разделение сопряжено с блокировками и за- который был перед началом записи и от того, ко держками. В документации к Berkeley DB 4 было торый стал после её окончания. О масштабах написано, что она поддерживает режим модифи- сложности проблемы говорит уже тот факт, что кации одним процессом одновременно с чтением фирма Oracle отказалась от поддержки такой другими. При этом блокировки доступа органи- функциональности в своей BerkeleyDB.

зуются на уровне страниц памяти, копии которых Сейчас новый вызов проблеме брошен в опи согласованно подготавливаются и периодически сании системы Kyoto Cabinet фирмой FAL Labs, синхронно пишутся на диск. производителем популярной СУБД Tokyo Cabinet.

Если он не окажется успешным, то масштабируе- for concurrent product development process// J.

мость описанной системы останется принципи- of Material Processing Technology. – 2003. – ально ограниченной предельной скоростью об- V. 139. – P. 619-623.

новления В+Tree-базы, имеющей сегодня порядок [9] Govindu R., Chinnam R. B. MASCF: a generic миллиона записей в секунду. process-centered methodological framework for Описанные принципы позволяют использовать analysis and design of multi-agent supply chain одновременно несколько В+Tree-баз, оптимизи- systems// Computers & Industrial Engineering. – рованных на чтение и неизменных в течение пе- 2007. – V. 53. – P. 584-609.

риодов различной продолжительности. Базы [10] Asproth V. Inter-organizational management and большего объёма меняются редко, самые малень- decision-making// Systemist. – 2006. – V. 28, кие базы обновляются несколько раз в секунду, No 2. – P. 4-12.

предоставляя доступ к последним изменениям [11] «Intel® Обучение для будущего». Официаль данных. ный сайт программы. – http://www.iteach.

Это позволяет обеспечить неразделяемую ин- ru/abo/.

формационную систему высоко реактивным поль- [12] Mukherjee I. The complexity paradigm: implica зовательским интерфейсом и гибко модифици- tions for information systems and their strategic руемой логикой обработок растущей сложности planning// J. of Computer Science. – 2008. – [41, 42]. V. 4, No 5. – P. 382-392.

[13] Mukherjee I. Understanding information system failures from the complexity perspective// J. of 5 Состояние реализации Social Sciences. – 2008. – V. 4, No 4. – P. 308 На текущий момент прорабатывается и коди- 319.

руется прототип системы, который будет исполь- [14] Tonchia S., Cozzi F. Industrial project manage зоваться для поддержки учебного процесса в УГП ment: planning, design, and construction. – имени А.К. Айламазяна. Springer, 2008. – 230 p.

[15] Choi J.K., Nies L.F., Ramani K. A framework Литература for the integration of environmental and business aspects toward sustainable product development// [1] Борисов Н.В., Чугунов А.В. Стратегия разви J. of Engineering Design. – 2008. – V. 19, No 5.

тия информационного общества и задачи под – P. 431-446.

готовки кадров в области информационно [16] Snbl A., Weber H., Padberg J. Evolutionary коммуникационных технологий // Труды XVI development of business process centered archi Всерос. науч.-метод. конф. Телематика'2009 – tectures using component technologies// J. of In 2009. – Т. 1, Секция A. – С. 171-172. – tegrated Design and Process Science. – 2001. – http://tm.ifmo.ru/tm2009/src/232a.pdf.

V. 5, No 3. – P. 13-24.

[2] Патаракин Е.Д., Ярмахов Б.Б. Веб 2.0 – [17] Wang X., Conboy K. Understanding agility in управление, изучение и копирование// Educa software development from a complex adaptive tional Technology & Society. – 2007. – Т. 10, № systems perspective// 17th European Conf. on In 2. – http://ifets.ieee.org/russian/depository/ formation Systems, 2009.

v10_i2/ html/2.htm.

[18] Meso P., Jain R. Agile software development:

[3] Патаракин Е.Д. Сеть детских конструкторов// adaptive systems principles and best practices// Большой московский семинар по методике Information Systems Management. – 2006. – раннего обучения информатике. Публикации V. 23, No 3. – P. 19-30.

семинара к 9 марта 2010 г. – [19] Yeh-Chun Juan, Chao Ou-Yang, Jiun-Shiung http://ito.edu.ru/sp/SP/SP-0-2010_03_09.html.

Lin. A process-oriented multi-agent system de [4] Weikum G., Vossen G. Transactional informa velopment approach to support the cooperation tion systems: theory, algorithms, and the practice activities of concurrent new product develop of concurrency control and recovery. – San Fran ment//Computers and Industrial Engineering. – cisco: Morgan Kaufmann Publishers, 2001.

2009. – V. 57, No 4.

[5] Fekete A. Allocating isolation levels to transac [20] Chih-Hsing Chu, Han-Chung Cheng. Business tions// Proc. of PODS. – 2005. – P. 206-215.

model innovation based on collaborative product [6] Saito Y., Shapiro M. Optimistic replication// development: a case study of Taiwan design ser ACM Computing Surveys. – 2005. – V. 37, No 1.

vices// Int. J. of Electronic Business Manage – P. 42-81.

ment. – 2005. – V. 3, No 4. – P. 257-269.

[7] Alrifai M., Dolog P., Balke W.-T., Nejdl W. Dis [21] Daneke G., Dooley K. From cycles to kaleido tributed management of concurrent web service scopes: mapping the nonlinear dynamics of tech transactions// IEEE Transactions on Services nology evolution// INFORMS Conf., Denver, Computing (TSC). – 2009. – V. 2, No 4. – 2004.

P. 289-302.

[22] Daneke G., Dooley K. The life-cycle revisited:

[8] Zhao H., Zhang Y., Wang Z., Lee S.F., Kwong stage transitions and the failure of the Iridium W.C. Research on group decision support system project// PICMET Conf., Portland, 2007.

[23] Razek M.A., Frasson C., Kaltenbach M.A. Con- [38] Tappolet J., Bernstein A. Applied temporal RDF:

text-based information agent for supporting edu- efficient temporal querying of RDF data with cation on the Web. V. Kumar et al. (Eds.). SPARQL// Proc. of ESWC Conf. – Springer ICCSA 2003, LNCS 2667, 2003. – P. 170-179. Verlag, 2009. – P. 302-322.

[24] Analyti A., Theodorakis M., Spyratos N., Con- [39] Noh Seo-Young, Gadia Sh.K. Benchmarking stantopoulos P. Contextualization as an inde- temporal database models with interval-based pendent abstraction mechanism for conceptual and temporal element-based timestamping// J. of modeling// Information Systems. – 2007. – V. 32, Systems and Software. – 2008. – V. 81, No 11. – No 1. – P. 24-60. P. 1931-1943.

[25] Franklin M., Halevy A., Maier D. From data- [40] Moon H.J., Curino C.A., Deutsch A., Hou C.-Y., bases to dataspaces: a new abstraction for infor- Zaniolo C. Managing and querying transaction mation management// SIGMOD Record. – 2005. time databases under schema evolution// Very – V. 34, No 4. Large Data Base VLDB, 2008.

[26] Choi J.-K., Nies L.F., Ramani K. A framework [41] Знаменский С.В. Контекстно-автономная ин for the integration of environmental and business формационная система. Четвёртая конферен aspects toward sustainable product development// ция «Свободное программное обеспечение в J. of Engineering Design. – 2008. – V. 19, No 5. высшей школе». Переславль, 30 января – – P. 431-460. февраля 2009 года. Тез. докл. – М.: ALT [27] Yeh-Chun Juan, Jiun-Shiung Lin, Chao Ou- Linux, 2009. – С. 32-37.

Yang. A process-driven approach to develop [42] Абрамов С.М, Знаменский С.В., Живчико multi-agent system for cooperation in concurrent ва Н.С., Котомин А.В., Титова Е.В. Информа new product development// CSIE '09: Proc. of the ционная система для разработки технологий 2009 WRI World Congress on Computer Science организации сложной совместной деятельно and Information Engineering. – IEEE Computer сти// Труды XI-й Всерос. науч. конф. «Элек Society, 2009. – V. 4. тронные библиотеки: перспективные методы [28] Bernstein P., Hadzilacos V., Goodman N. Con- и технологии, электронные коллекции»

currency control and recovery in database sys- RCDL-2009. – Петрозаводск: КарНЦ РАН, tems. – Addison-Wesley, 1987. 2009.

[29] Stonebeker M. Errors in database systems, even tual consistency, and the CAP theorem. Information system for education BLOG@CACM, April 5, 2010. – перевод на S.V. Znamenskij русский С. Кузнецова с комментарием 19 мая 2010 г. – http://citforum.ru/gazeta/154/.

Review the objectives and content of education in the [30] Brewer E.A. Towards robust distributed sys context of "one student – one computer" should be tems// Principles of Distributed Computing. Port supported by highly reliable information system. It land, Oregon, July 2000, Invited Talk.

should provide a flexible, efficient and versatile or [31] Herlihy M.P., Wing J.M. Linearizability: a cor ganization of a variety of creative collaborative work, rectness condition for concurrent objects// ACM based on digital libraries.

Transactions on Programming Languages and The report focuses on the problem of creating an Systems. – 1990. – V. 12, No 3. – P. 463-492.

information system with the required qualities. Ex [32] Lamport L. On interprocess communication. I;

plained why relational databases have no perspectives II// Distributed Computing. – 1986. – V. 1, No 2.

in future. Alternative approach description is pro – P. 77-101.

vided.

[33] Risson J., Moors T. Survey of research towards robust peer-to-peer networks: search methods// Работа выполнена при финансовой поддержке РФФИ Computer Networks. – 2006. V. 50, No 17. – (проект 09-07-00407) P. 3485-3521.

[34] Snodgrass R.T. Developing time-oriented data base applications in SQL// Morgan Kaufmann Series in Data Management Systems. – Morgan Kaufmann, 1997. – 504 p.

[35] Ali K.A., Pokorny J. A comparison of XML based temporal models// Advanced Internet Based Systems and Applications. Lecture Notes in Computer Science, 2009. – P. 339-350.

[36] Grandi F. Multi-temporal RDF ontology ver sioning// Int. Workshop on Ontology Dynamics IWOD, 2009.

[37] Pugliese A., Udrea O., Subrahmanian V.S. Scal ing RDF with time// Proc. of WWW Conf. – ACM Press, 2008. – P. 605-614.

Проектирование распределённых систем обработки объектных структур данных © А.А. Демидов Исследовательский центр искусственного интеллекта ИПС РАН alex@dem.botik.ru такой простой системы останется непротиворечи Аннотация вым, поскольку байты независимы друг от друга, а Статья посвящена проблеме обеспечения каждый байт записывается атомарно (Atomic), то устойчивости к отказам и согласованности есть неделимым на отдельные шаги образом.

изменений сложно структурированных Теперь усложним систему – пусть элементами данных при конкурирующем доступе к ним информации в ней будут непересекающиеся после транзакций распределённой системы. Неко- довательности байт. При конкурирующем доступе торые распространённые принципы проек- здесь возможны конфликты совместного доступа к тирования распределённых хранилищ дан- данным. Они вызваны потерей атомарности опера ных формализуются заново с целью анализа ций с объектом – элементом данных сложной необходимости их применения в тех или структуры, атомарность операций с которым не иных случаях, обусловленных требования- обеспечивается средствами системы нижнего уров ми предметной области реальных задач. ня (например, операционной системы или СУБД).

Особое внимание уделено проблеме выбора Если один процесс начал запись объекта в тот мо оптимальной стратегии обеспечения непро- мент, когда другой процесс не закончил чтение дан тиворечивости данных. ного объекта, то происходит конфликт «чтение – запись» – второй процесс получит противоречи 1 Введение вую (Non-Consistent) копию объекта, реально со держащую части разных объектов – до записи и Распределённые системы обработки и хранения после. Так же, если два процесса начнут запись од данных позволяют оптимальным образом решать ного объекта в одно и то же время, то возникает задачи объединения территориально разобщённых конфликт «запись – запись» – информация в сис узлов в единый информационно-вычислительный теме в таком случае будет необратимо испорчена.

комплекс. Технологии, лежащие в основе таких ре Между тем, реальные объекты в настоящей сис шений, как правило, довольно сложны. Причиной теме редко бывают независимы друг от друга – как тому являются физические ограничения среды правило, они имеют связи или же логические взаи функционирования распределённой системы: ко мозависимости своих данных. Поэтому модель ус нечная надёжность и пропускная способность как ложняется ещё более – объектами в ней являются самих узлов, так и каналов передачи данных, что уже пересекающиеся последовательности байт. Об делает необходимым применение алгоритмов кор ласть записи и область чтения объекта в такой мо рекции аппаратных сбоев, репликации и восстанов дели уже не всегда совпадают, область чтения одно ления данных, синхронизации процессов доступа к го объекта может являться областью записи друго ресурсам, балансировки нагрузки и организации го, объекты могут пересекаться только по чтению управления системой [1, 7].

или только по записи – всё это допустимые вариан Рассмотрим элементарную распределённую сис ты организации данных. Конфликты «запись – тему: сеть пронумерованных узлов, хранящих про запись» в таком случае можно подразделить на стые байты данных;

пусть каждый байт в такой сис физические, или низкоуровневые, связанные с раз теме уникально адресуется номером узла и смеще рушением данных в общей области записи объек нием элемента данных в его в памяти. Если надёж тов, и логические, высокоуровневые, вызванные ность и пропускная способность компонентов такой несогласованной модификацией данных в области системы не ограничены, то никаких дополнитель чтения другого объекта [3].

ных алгоритмов здесь не требуется – можно сво При произвольном изменении объекта пересе бодно читать и писать отдельные байты, состояние кающиеся с ним объекты пострадают, однако если пишущему процессу известно состояние всех пере секающихся объектов, то противоречивости при Труды 12й Всероссийской научной конференции записи можно избежать, если изменить объект со «Электронные библиотеки: перспективные методы и гласованно на основе совокупной информации. Это технологии, электронные коллекции» – RCDL’2010, Казань, Россия, 2010 возможно только в случае обеспечения взаимной изоляции (Isolation) процессов при работе с дан- Дальнейший анализ предполагает, что сущности ными – они не должны мешать друг другу при рабо- предметной области соответствуют одному из двух те с пересекающимися объектами. типов введённых выше объектов или, по крайней Наряду с ещё одним техническим требованием мере, заключены внутри них.

долговечности (Durability) произведённых изме нений, отсутствия потери данных после фиксации, 3 Постановка проблемы первые три условия формируют принципы ACID Поскольку реальные вычислительные узлы не транзакционной модели доступа к данным в конку идеальны в смысле надёжности и пропускной спо рирующих транзакциях: Atomic, Consistent, Isolated, собности, в реальных распределённых системах Durable. Дальнейшее изложение не предполагает предусматриваются механизмы балансировки на какой-либо одной частной архитектуры вычисли грузки, тиражирования и восстановления данных, тельной системы, наличия СУБД и подобных вещей управления и безопасности. К системам обработки – более удачной является введённая выше абстрак данных, как правило, предъявляется ряд требований ция с байтами, которая будет широко использовать по обеспечению устойчивости к отказам компонент, ся и далее. Однако понятия и подходы, разработан постоянной готовности сервиса и синхронности ные в рамках теории управления конкурирующими изменений состояния данных.

транзакциями, будут привлекаться при дальнейшем Все три характеристики являются важными для анализе. Главной целью данной работы является бесперебойной работы системы, однако оказывается поиск путей ослабления необходимости в синхро практически невозможным удовлетворить всем низации конкурирующих процессов.

трём требованиям в полном объёме. Так, хорошо известно, что требования сильной синхронизации и 2 О понятии объекта высокой степени параллельности с конкурирующим Чтобы дальнейшее изложение носило более доступом являются антагонистами. Сочетать свой предметный характер, необходимо остановиться на ства постоянной доступности и толерантности к понятии объекта более детально. Рассмотрим об- потерям сообщений внутри системы не менее слож ласть памяти системы как некоторое пространство но. Эти проблемы являются широко дискутируемы байт. Если содержимое одного байта обуславливает ми в рамках классификации задач, предложенной правомерность другого, то имеется направленная Брюэром в его CAP-тезисе [4, 5], по которой выде зависимость между этими двумя байтами (чаще она ляют требования: согласованности различных вер сий Consistency 1, высокой степени доступности является обоюдной). Если теперь адекватность 3-го сервиса Availability и устойчивости к разделению байта зависит от содержимого 2-го байта, но не за на части Partition tolerance. Тезис гласит, что толь висит напрямую от содержимого 1-го байта, то име ко две из трёх характеристик могут быть обеспече ется также и нетранзитивная зависимость 3-го ны проектом, поэтому при абсолютизации требова байта от 1-го. Если же содержимое 3-го байта спо ний получаются системы только трёх типов: недос собно потерять адекватность при изменении 1-го таточно устойчивые к разрывам коммуникаций – равно как и 2-го, то эта зависимость будет транзи CA, с возможными отказами обслуживания – CP тивной. Наконец, если есть ещё зависимость 1-го или без синхронного изменения распределённых байта от 3-го, то имеет место циклическая зависи данных – AP.

мость 1-го, 2-го и 3-го байт.

Применительно к системам обработки данных Более сильные транзитивные и компактные цик это означает существование трёх крайних вариантов лические зависимости часто естественным образом систем:

соответствуют сущностям предметной области, взя • CA (неделимая система) – это подход с фраг тым вместе с их непосредственными связями с бли жайшими соседями, а протяжённые области нетран- ментацией данных, строгой ACID непротиворе зитивно зависимых данных дополнительно вклю- чивостью и принципом синхронных изменений чают все опосредованные межобъектные зависимо- с применением двухфазного протокола фикса сти. Область транзитивной зависимости назовём ции транзакций;

классическим объектом (со связями), а объемлю- • CP (отказы обслуживания) – это подход с нали щую область нетранзитивной зависимости – неклас- чием дублирования, строгой ACID непротиво сическим объектом-замыканием или замкнутым речивостью и синхронной репликацией измене объектом;

если тип зависимости не будет иметь ний с применением метода пессимистических значения, будем говорить просто об объекте. Связи блокировок;

не могут принадлежать одному объекту;

вместо это- • AP (возможна рассогласованность) – это также го они разделяются между несколькими объектами, подход с дублированием, но со слабой, BASE, а сами объекты становятся пересекающимися окре- непротиворечивостью (Eventual consistency) и стностями в рассматриваемом пространстве байт. асинхронной репликацией изменений [1, 8].

Формализацию подобного выделения объектов Удачно выбранная архитектура распределённой можно найти в [6]. Если в системе существует мно- системы обработки данных обычно представляет жество версий объекта, все они логически рассмат- собой баланс между крайностями, найденный с учё риваются входящими в одну окрестность. том требований конкретной задачи.

минимизировано выбором более надёжного обору 4 Обеспечение устойчивости к отказам дования опорных узлов. Таким образом, ослабив Отказоустойчивость является одной из главных одно из условий теоремы, можно получить сущест особенностей распределённых систем, и имеется венный прирост эффективности распределённой большое количество трудов, посвящённых этой те- системы в целом.

ме [1, 7]. Формат статьи не позволяет раскрыть во- Следующим логичным шагом в этом направле прос вполне, но затронуть его нам необходимо. нии является поиск компромисса между типами CP Можно выделить два крайних подхода к по- и AP. К сожалению, это не менее многогранная строению систем распределённой обработки и хра- проблема, и здесь очень многое зависит от типа ре нения информации, хотя и допускающих промежу- шаемых задач – насколько свободно они позволяют точные варианты. Это: обрабатывать данные в конкурентном режиме. Спо • фрагментация, или секционирование данных – собам достижения баланса архитектурного решения распределение частей общей базы данных по между типами CP и AP посвящён следующий раз узлам сети без дублирования информации;

дел.

• дублирование, или тиражирование данных – Мы начнём со схемы асинхронной репликации в создание тождественных полных копий общей среде с частичным дублированием, а затем посмот базы данных на каждом узле сети. рим, какие дополнительные условия синхронизации Первый подход позволяет минимизировать объ- в какой ситуации нужно на неё наложить, чтобы ём хранимых данных, но предъявляет жёсткие тре- приблизить её к синхронной схеме репликации.

бования к надёжности оборудования и быстродей ствию каналов передачи информации при выборках. 5 Обеспечение непротиворечивости Второй подход позволяет повысить надёжность В распределённых системах критичной является системы и скорость выборок, но в свою очередь операция записи данных, когда два процесса меня требует больших объёмов дисковой и оперативной ют взаимозависимые данные или когда один про памяти для хранения и обработки, а также широких цесс меняет некоторую часть объекта, в то время каналов для репликации обновлений между узлами как второй процесс уже прочитал другую его часть при изменении данных.

и собирается прочесть изменённую. Такие ситуации Решения типа CA основываются на первом под называют низкоуровневыми конфликтами совмест ходе – непересекающемся распределении информа ного доступа к данным, и они находят более или ции по узлам распределённой системы. Именно по менее удовлетворительное разрешение в рамках этой причине данный тип решений столь чувствите подходов по управлению конкурирующими тран лен к разрыву коммуникаций. В то же время два закциями [2, 3].

других решения типа P основываются на дублиро Кроме низкоуровневых конфликтов совместной вании с дальнейшим синхронным (тип CP) или записи данных в объектных средах с зависимостями асинхронным (тип AP) обновлением информации могут отдельно возникать логические конфликты, между узлами системы.

вызванные некоммутативностью операций, выпол В качестве компромиссного решения, позво няемых в конкурирующих процессах. Такие кон ляющего оптимизировать требования к производи фликты необходимо выявлять и анализировать от тельности и надёжности системы, здесь выгодно дельно, причём при определённой организации дан применить стратегию размещения данных ближе к ных может оказаться возможным использовать низ потребителю. Эта стратегия сочетает в себе пре коуровневые коллизии для выявления конфликтов имущества двух подходов – фрагментации и дуб высокого уровня, а высокоуровневую логику – для лирования информации: часто используемые дан разрешения ряда конфликтов низкого уровня. На ные тиражируются и перемещаются ближе к запра пример, для изменения значения поля x = 0 часто шивающим их узлам, что позволяет повысить опе можно использовать коммутативные операции:

ративность запросов на выборку, а редко исполь x = x + 1, x = x + 2, результат которых не зависит от зуемые имеются в единственном экземпляре, что порядка выполнения, вместо аналогичных некомму позволяет снизить затраты на хранение и синхрони тативных операций: x = 1, x = 3.

зацию информации при изменениях. В такой среде В каждой задаче, допускающей параллельность, будут происходить постоянные перемещения дан можно обнаружить области данных, логически не ных между узлами (data movement) с целью оптими связанные между собой. Эти области данных могут зации производительности системы в целом, реали меняться независимо, по крайней мере, на каком-то зуя, таким образом, вариант подсистемы динамиче этапе выполнения задачи, что в точности означает, ской балансировки нагрузки (load balancing).

что операции изменения этих областей данных Как можно заметить, данная стратегия затраги коммутируют между собой, и здесь степень синхро вает третье условие CAP-тезиса – устойчивость сис низации может быть уменьшена. Логику объектов темы к разделению на части при отказах узлов или высокого уровня можно использовать для ослабле каналов связи, смещая архитектуры CP и AP типов ния требований к синхронизации при сохранении в сторону типа CA. Однако уменьшение надёжно непротиворечивости информации, что позволяет сти нивелируется ранжированием информации по применить для распространения изменений прин частоте использования, к тому же оно может быть ципы BASE непротиворечивости с асинхронной ными допустимыми операциями являются добавле репликацией, возможно лишь с некоторыми эле- ние новых или пометка удаляемых записей, никаких ментами синхронизации. Мы рассмотрим эти шаги реальных операций удаления или модификации за более детально с использованием транзакционной писей БД производиться не должно.

модели, но сначала хотелось бы предложить одну реальную распределённую систему, созданную на основе принципов BASE, – это наше обычное ин формационное общество.

Отдельный человек с технической точки зрения является автономным узлом потребления и произ водства информации, а средства массовой инфор мации, книги и пресса привносят элементы синхро низации. Каждый индивид не имеет чёткого регла мента работы с информацией, он может смотреть телепередачи или нет, быть начитанным или же глубоко невежественным человеком, может быть в курсе событий или не интересоваться новостями – всё это оказывается неважным для прогресса обще ства в целом. Информация в нём постоянно накап ливается и, в общем, не становится противоречивой, хотя каждый отдельный человек обладает только частью всей информации, и она часто бывает не точной или даже искаженной. Здесь можно отме тить как значительное дублирование информации:

каждый узел имеет в своём личном владении почти все необходимые ему данные, так и наличие систе мы асинхронной репликации (личное общение, поч Рис. 1. Виды пересечения транзакций по данным и та, посещение библиотеки, интернет). Кроме того, по времени. Обозначения: R1, R2 – область чтения, имеются элементы синхронной репликации, но без W1, W2 – область записи 1-й и 2-й транзакций;

гарантии получения сообщений конечным узлом A, B – варианты пересечения по времени (средства массовой информации). Имея данную мо дель перед глазами, будет проще сделать ряд обос При уровне изоляции Guaranteed view области нованных предположений в дальнейшем.

чтения можно не рассматривать в низкоуровневой 5.1 Многоверсионная транзакционная модель модели, поскольку после своего старта транзакция не видит никаких изменений данных, даже под Методы анализа, разработанные в рамках подхо- тверждённых другими транзакциями. На физиче дов к управлению конкурирующими транзакциями, ском уровне достаточно рассмотреть состояние в могут быть с успехом применены и при проектиро- области пересечения по данным W1 * W2 и време вании системы репликации данных, если считать ни A или B, то есть всего два варианта конфликтов:

началом транзакции момент актуализации узла дан- W1 * W2 * A и W1 * W2 * B. Обе эти ситуации рас ными других серверов, а её завершением – момент сматриваются как конфликты записи, при этом одна обновления серверов данными текущего узла. Все из транзакций откатывается, иначе может возник данные, используемые транзакцией, должны быть нуть противоречивость данных, поскольку данные согласованы между собой – в случае наличия час- области W1 * W2 могут быть взаимозависимы с тичных изменений в пределах системы эти данные данными как области W1, так и области W2, и по узла необходимо обновить. При таком соответствии сле изменений первой транзакции результаты вто синхронизация в распределённой системе может рой транзакции могут потерять согласованность с быть точно описана транзакционной моделью со остальной частью БД.

вместного доступа к данным.

Ситуация существенно усложняется при нали Рассмотрим две транзакции, которые читают и чии высокоуровневых логических конфликтов. Рас пишут некоторые данные. Возможны следующие смотрим область пересечения по данным пересечения этих транзакций по данным и по вре R1 * R2 * W1 \ W2, менять которую может только мени (рис. 1).

транзакция tr1. Здесь никакого конфликта в тран Для устранения конфликтов «чтение-запись»

закционной модели не возникает, и, тем не менее, можно применить режим изоляции Guaranteed view результаты транзакции tr2 могут оказаться проти (гарантированное представление), когда читающая воречивыми, поскольку она частично использует транзакция видит моментальный снимок – состоя устаревшие данные из области записи W1 транзак ние БД на момент своего старта. Для минимизации ции tr1. Использование режима изоляции транзак более серьёзных конфликтов «запись-запись» мож ций Read Committed (видимость подтверждённых но основать систему репликации на принципах мно изменений) не способно улучшить ситуацию, по говерсионности баз данных. При этом единствен скольку транзакции tr2 пришлось бы постоянно менения. По этой причине необходимо рассмотреть контролировать неизменность уже прочитанных ею варианты пересечения транзакций по данным и по данных. времени более тщательно.

Кроме того, уже реализация режима изоляции Прежде всего, следует обеспечить атомарность Guaranteed view, обеспечивающего временной срез объектов, которая гарантирует, что никакой объект данных для устранения конфликтов «чтение- не будет зафиксирован в системе лишь частично.

запись», в распределённой системе сама по себе При сложной организации объекты могут храниться является непростой задачей, требующей синхрони- в нескольких местах БД, поэтому в отсутствие кон зации изменений версий объекта. троля физических конфликтов гарантии атомарно сти необходимо предусматривать дополнительно.

5.2 Тотальный контроль непротиворечивости Этого можно добиться двумя разными способами:

либо предусмотрев элементы синхронизации, за Для решения данных проблем можно было бы прещая изменение всех данных объекта конфлик применить оптимистические методы управления тующей транзакцией, либо полностью перезаписы транзакциями с обратной валидацией, выполняя вая в каждой транзакции всю область данных объ пост-проверку того, что результат транзакции со- екта (и всех пересекающихся с ним – в случае клас гласуется с результатами других транзакций, зафик- сических объектов), тогда эту область можно будет сированных после её начала. Такую проверку мож- рассматривать как некую атомарную логическую но сделать либо на логическом уровне, контролируя запись базы данных. К сожалению, этот последний непротиворечивость сохраняемых объектов, либо на вариант неприемлем для сильно связанных данных физическом уровне, контролируя неизменность всех – в таком случае может оказаться невозможным данных, использованных транзакцией tr2 в своей выделение замкнутой окрестности без пересечений работе.

с другими объектами.

Первый вариант очень интересен, поскольку практически не требует синхронизации процессов 5.4 Отказ от контроля логических конфликтов при записи, но, к сожалению, трудно реализуем – он требует развитой логики процедур проверки, кото Проанализируем теперь коллизии «чтение рым необходимо иметь априорную информацию запись» и «запись-запись» – последние целиком обо всех ограничениях предметной области. перенеслись с низкого на высокий уровень из-за В свою очередь, при втором варианте возникают отказа от контроля конфликтов на физическом общие сложности синхронизации изменений во уровне. Оба типа коллизий можно рассматривать всей распределённой структуре, а также проблема единообразно, поскольку они имеют одинаковую учёта новых записей, созданных транзакцией tr1 за причину: результат транзакции основывается на время работы tr2. Такие записи не были учтены данных, полностью или частично потерявших акту транзакцией tr2, хотя могли бы повлиять на резуль- альность за время выполнения этой транзакции.

тат. В общем случае для оценки, какие из новых Такие коллизии не приводят к проблемам, если ре записей могли оказать такое влияние, придётся по- зультат транзакции также оказывается устаревшим и полностью перекрывается более свежими версия вторить выполнение транзакции tr2 с самого начала ми объектов, или даже если устаревший результат при любом добавлении записей в БД, что приводит полностью перекрывает все зависимые более све к запрету всякого параллелизма вообще.

жие данные – тогда состояние данных просто отка 5.3 Отказ от контроля физических конфликтов тится немного назад.

В противном случае, когда последняя версия В качестве альтернативы тотальному контролю данных будет содержать в какой-то своей части не непротиворечивости можно предложить вариант без актуальные результаты, информация может стать отслеживания физических конфликтов вообще. По- противоречивой. Хотя это необязательно, поскольку скольку мы не в состоянии обеспечить непротиво- частный результат может оказаться совместимым с речивость данных во всех случаях, не имеет особого произведёнными другой транзакцией изменениями смысла заботиться о ней и в некоторых из них. Вме- данных в области зависимости. Кроме того, само по сто этого необходимо спроектировать высокоуров- себе смешение результатов различной актуальности невую обработку информации таким образом, что- – несогласованность – ещё не обязательно приводит бы она была невосприимчивой к возникающей час- к противоречивости информации, поскольку даже тичной рассогласованности данных или на логиче- сама входящая в систему информация практически ском уровне не допускала её вовсе. никогда не синхронизирована по времени и допус Такой подход отклоняется от транзакционной кает различный порядок следования событий! При модели, здесь не будет валидации на физическом этом некоммутативность операций с данными ста уровне – транзакции всегда будут завершаться. Ме новится несущественной, поскольку полностью ханизмы многоверсионности обеспечат возмож вуалируется естественной неупорядоченностью ность хранения любых взаимоисключающих изме этих операций.

нений: одна транзакция сможет удалить (пометить к Обратимся опять к рис. 1. Пусть первая транзак удалению) запись, в то время как другая будет её ция tr1 работает со своим неклассическим объек менять, и обе потом успешно подтвердят свои из том-замыканием R1 + W1, а вторая tr2 – со своим R2 + W2.


Хотя неклассические объекты пересека- нения областей данных как классических объектов, ются, каждый из них меняется непротиворечиво для без учёта окружения. Заметим, что если бы рас себя и для других на основании только тех данных, смотренным сущностям соответствовали некласси которые находятся в принадлежащих ему областях ческие объекты, то никаких вопросов к непротиво (например, для первого объекта это R1 + W1) – в речивости не возникло. Проблема в том, что таких противном случае границы областей, занимаемых отдельных объектов-замыканий может не сущест объектами-замыканиями были бы другими. По- вовать из-за взаимных зависимостей данных, тогда скольку входящая информация неупорядочена, а пример сведётся к тривиальному случаю: X = Y = транзакции запускаются на основе каких-то внеш- A + B + C. В классическом случае второй транзак них событий, то нет никаких гарантий того, что ции нельзя было завершаться, поскольку её данные транзакция tr1 будет использовать свой объект до уже были изменены другой транзакцией.

изменения части области данных W1 * W2 транзак- Для синхронизации в данном случае можно цией tr2 и наоборот. Поэтому состояние этой облас- применить архитектуру «доска объявлений». По ти может быть тем или другим или даже измениться узлам системы распределяются доски объявлений, за время выполнения транзакции – всё это никак не на которых помещаются списки классических объ может привести к противоречивости информации в ектов, включая их непосредственные связи (область БД, хотя в ней и могут оказаться не самые послед- X = A + C транзитивной зависимости в примере, ние данные, если последняя из завершившихся рассмотренном выше). Каждый объект имеет свой транзакций выполнялась длительное время. домашний узел или группу узлов приписки, так что Таким образом, отличие технической несогласо- системе всегда известно, где искать соответствую ванности, вызванной параллельностью обработки, щую доску. В процессе запроса данных для предот от естественной, вызванной отсутствием предопре- вращения конфликтов «чтение – запись» проверяет делённого порядка входящих событий, состоит ся согласованность версий пересекающихся облас только в том, что в первом случае итоговое состоя- тей данных, а при записи контролируется их неиз ние объекта-замыкания может представлять собой менность другими транзакциями, предотвращая некоторую комбинацию различных состояний, ло- порчу данных при конфликтах «запись – запись» – в гически несовместимых между собой (если их до- этих случаях транзакция откатывается, либо произ пускает структура хранения данных). Это последст- водятся иные действия по акцепту изменений.

вия нарушения атомарности, и если средства её Такая архитектура обеспечивает строгую ACID поддержки были предусмотрены, то техническая и непротиворечивость при наличии множества рас естественная несогласованности абсолютно не- пределённых копий данных, но за это требует про различимы, и никакой дополнительной синхрониза- верки каждого читаемого объекта по доске объявле ции не требуется. ний. Если задача допускает использование не самых актуальных версий, то быстродействие системы 5.5 Добавление элементов синхронизации может быть существенно увеличено с переходом на принципы BASE – тогда обращений к доскам при К сожалению, в отличие от неклассических объ- чтении не требуется. Действительно, пусть транзак ектов, гарантия атомарности на уровне классических ция желает основываться на данных годичной дав объектов не является достаточным условием обес- ности, тогда, очевидно, она может смело запраши печения непротиворечивости БД. Случай опосредо- вать срез данных того периода, не опасаясь, что ка ванно, нетранзитивно зависимых по некоммутатив- кие-то объекты прочитаются неатомарно – ведь все ным операциям областей данных не позволяет в транзакции, начатые в прошлом году, уже давно полной мере обеспечить атомарность на этом уров завершены, и те версии данных уже никем не могут не – нетранзитивные зависимости представляют быть изменены. Ввод не такой большой, но разум собой межобъектные логические зависимости и не ной толерантности к актуальности информации в охватываются классической объектной моделью.

запросах данных позволяет реализовать BASE Например, пусть имеются две области данных, принципы без какой-либо существенной перестрой представляющие непересекающееся сущности ки системы. Задержка определяется характерным предметной области: Xp = A + D и Yp = B + E, где временем асинхронной репликации данных между C = D + E является объединением сфер взаимного узлами системы.

влияния, сфер действия связей. Этим сущностям Толерантные к актуальности данных задачи не будут соответствовать пересекающиеся классиче редки – это все темы, не относящиеся к задачам ре ские объекты со связями X = A + C и Y = B + C.

ального времени. Естественная задержка поступле Допустим, с небольшим интервалом над X стар ния новой информации в систему маскирует техни товали две транзакции, одна из которых заверши ческую дельту времени в запросах точно так же, как лась и перевела объект в состояние X1 = A1 + C1.

отсутствие предустановленного порядка событий Затем стартовала третья транзакция над объектом вуалирует некоммутативность операций с данными!

Y1 = B + C1 и перевела его в состояние Это значит, что здесь мы получаем такой же значи Y3 = B3 + C3. Потом завершилась вторая транзак мый выигрыш: кроме асинхронной репликации для ция, перекрыв результаты первой: X2 = A2 + C2. В обеспечения атомарности чтения никакой допол итоге объект Y3 оказался в состоянии Y3 = B3 + C2, нительной синхронизации не требуется.

что является потенциально опасным в случае изме 5.6 Дальнейшие шаги по оптимизации Литература [1] Таненбаум Э., ван Стеен М. Распределённые Если сущности предметной области можно рас системы. Принципы и парадигмы. – СПб.: Пи сматривать как слабо связанные объекты, то подход тер, 2003. – ISBN: 5-272-00053-6.

без контроля конфликтов будет работать и без гло [2] Чардин П. Многоверсионность данных и управ бальной синхронизации записи. Но даже при нали ление параллельными транзакциями// «Откры чии нетранзитивных зависимостей имеются задачи, тые системы». – 2005. – № 1. – С. 64-69.

не чувствительные к наличию некоторого объёма [3] Bretl R. Achieving high concurrency in object ori противоречий в данных;

главное – чтобы он не на растал со временем. Такого поведения можно ожи- ented databases. – ODBMS.ORG, 2006. – дать от моделей, обладающих чертами эргодиче- http://citforum.ru/database/articles/bretl.

ских цепей Маркова, когда поведение случайного [4] Brewer E.A. Towards robust distributed systems процесса перестаёт определяться его начальным (abstract)//Proc. of the 19th Annual ACM Sympo состоянием. В этот ряд попадают также задачи по sium on Principles of Distributed Computing, Port интенсивной обработке информации, содержащей land, Oregon, United States, 2000, July 16 – 19. – большое количество зависимостей с обратными свя- P. 7.

зями. Для реализации данного подхода в распреде- [5] Gilbert S., Lynch N.A. Brewer's conjecture and the лённой системе нужно лишь убрать все обращения feasibility of consistent, available, partition-tolerant к доскам объявлений;

несмотря на утрату атомарно- web services// SIGACT News. – 2002. – V. 33, сти записи (а возможно – и чтения) объекта как со No 2. – P. 51-59.

вокупности версий, в данном случае необходимо [6] Largeron C., Bonnevay S. A pretopological ap ставить вопрос о сохранении атомарности записи и proach for structural analysis// Information Sci чтения каждой отдельной его копии.

ences. – 2002. – V. 144, July. – P. 169-185.

В пространстве байт можно ввести ещё одно по [7] Lynch N.A. Distributed algorithms. – Morgan ле – продукций, если мы имеем возможность разде Kaufmann Publishers, Inc., San Mateo, CA, 1996. – лить по времени процессы обновления различных ISBN 1-55860-348-4.

областей. В отличие от статического поля зависи [8] Vogels W. Eventually consistent// ACM Queue. – мостей, использованного для выделения объектов, 2008. – V. 6, No 6. – P. 14-19.

поле продукций является динамическим. Все облас ти будут упорядочены векторным полем потоков Design of distributed systems of processing данных, возможно, содержащем циклы. Тогда базу object data structures данных можно рассматривать как самоорганизую щуюся нелинейную динамическую систему, в кото A.A. Demidov рой потоки данных, в ходе эволюции стремясь к аттрактору, постепенно затирают ошибочные дан This paper is devoted to the problem of reliability and ные. Насколько реальным будет такой эффект – ин consistency of data in concurrent transactions in distrib тересный вопрос, также зависящий от задачи, но uted system. Some of well-known principles of distrib само существование нашего общества индивидов uted system architecture design are reinvestigated to доказывает, что в принципе это возможно.

discover advantages of their usage in order of resolving problems of given specific tasks. Emphasis is made on Заключение the problem of choice the optimal strategy of providing consistency.

Представленные в работе понятия и методы, ка сающиеся выбора оптимальной стратегии обеспече- Работа выполнена по программе фундаментальных ис ния непротиворечивости данных, могут найти своё следований Президиума РАН №3, проект «Высокопроиз применение при проектировании распределённых водительные масштабируемые средства работы с факто систем различного назначения. Особый интерес для графическими базами большого объёма»


упрощения анализа, как представляется, имеет кон- Это другая Consistency: «согласованность» в отличие от цепция «пересекающихся объектов» – окрестностей «непротиворечивости» в ACID, хотя эти понятия связаны:

в пространстве байт, включающих области зависи- при различии версий обеспечить непротиворечивость в мостей данных. Такой «топологический» подход к рамках полной системы становится проблематично анализу хранилищ данных в совокупности с мето дами упомянутой теории динамических систем, ве роятно, способен привести к новым интересным результатам в дальнейшем: предтопологические пространства уже сейчас используются в работах, связанных с анализом сложных структур [6].

Разработанные методы и архитектура на базе «доски объявлений» используются в работе над проектом глобального ресурса знаний в системе извлечения информации из текстов ИСИДА-Т.

Приближенное индексирование многомерных объектов © Е.Г. Михайлова, Б.А. Новиков Санкт-Петербургский государственный университет egmichailova@mail.ru, borisnov@acm.org водит к необходимости решать задачу поиска в Аннотация многомерном пространстве. Из многочисленных Задачи поиска ближайших соседей в мно- многомерных индексных структур, предложенных в гомерном пространстве возникают во мно- 1980-е гг., проверку временем выдержали только R гих задачах информационного поиска, об- деверья [1], широко применяемые в различных при работки текстов на естественном языке, в ложениях и реализованные в промышленных СУБД.

логическом анализе данных. Эффективное Задачи многомерного поиска связаны, в первую решение этой задачи возможно только с очередь, с обработкой пространственных и про помощью специализированных индексных странственно-временных данных. Другим источни структур, однако точные методы неприме- ком многомерных данных является широкий класс нимы для пространств большой размерно- приложений, в которых объекты моделируются век сти. В работе предлагается и анализируется торами, составленными из значений некоторых вы индексная структура для приближенного числяемых признаков или характеристик объекта. К решения задачи поиска K ближайших сосе- этому классу приложений относятся системы, осно дей, основанная на использовании класте- ванные на различных вариантах векторной модели ризации для построения индексного дерева. текстового информационного поиска, поиск изо Реализация построена над высокопроизво- бражений по содержанию, некоторые методы логи дительной реляционной СУБД. ческого анализа данных и многие другие. Данные, полученные из приложений этого класса, обычно 1 Введение характеризуются большой размерностью.

Как правило, при обработке многомерных дан Любая система, для функционирования которой ных требуется поиск по признаку близости или по требуются хранение и обработка больших объемов добия, а не на точное совпадение каких-либо атри информации, по необходимости должна так или бутов. Наиболее часто упоминаются задачи поиска иначе решать задачу поиска. Как правило, для вы K ближайших соседей, поисков заданной окрестно полнения отдельных функций требуется относи сти и операция соединения на основе подобия.

тельно небольшая часть информации, хранимой в системе, и поэтому эффективная работа системы 2 Обзор родственных работ обеспечивается с помощью индексных структур.

Любой рассматриваемый процесс или объект, ин 2.1 Размер страницы формация о котором хранится, может быть характе В исследовательской литературе предложено ризован набором признаков, которые обычно назы большое количество индексных структур для мно ваются атрибутами. Назначение любого индекса – гомерных данных, в том числе R-деревья [8], X быстрое получение доступа к объекту по значениям деревья [2], AV-файлы и многие другие [3]. В по некоторых из его атрибутов. Иначе говоря, индексы следнее десятилетие большое внимание привлекает обеспечивают эффективное выполнение ассоциа схема пространственно-чувствительного хеширова тивного поиска.

ния (LSH – locality sensitive hashing). Рассматрива Если значения атрибута принадлежат некоторо лись также M-деревья [4], предназначенные для ин му линейно упорядоченному множеству, то задачи дексирования точек метрического пространства.

поиска решаются с помощью одномерных индексов.

Для пространственных данных малой размерно Одномерные индексные структуры (такие, как B сти хорошо работают индексы на основе R-деревьев деревья и hash-файлы) хорошо исследованы в [8]. Задача многомерного поиска чрезвычайно 1970 – 1980 гг. Во многих приложениях, однако, сложна при большом размере векторов. Можно да требуется поиск по значениям нескольких атрибу же утверждать, что построение универсальных ин тов или по атрибутам, которые не могут быть есте дексных структур для данных большой размерности ственным образом линейно упорядочены, что при невозможно. Этот факт, известный под названием «проклятие размерности», определяется топологией Труды 12й Всероссийской научной конференции многомерного пространства и не зависит от метода «Электронные библиотеки: перспективные методы и построения индекса. Практическое следствие состо технологии, электронные коллекции» – RCDL’2010, Казань, Россия, 2010 ит в том, что любая индексная структура, начиная с некоторой размерности, становится по производи- троидов образует верхний уровень индексного де тельности хуже, чем полный просмотр. Остроту рева.

этой проблемы можно несколько снизить, рассмат- Кластеризация ранее использовалась для опти ривая структуры индексов и алгоритмы, дающие мальной реорганизации R-дерева [7].

приближенный результат. Как правило, векторы Для решения задачи поиска ближайших соседей только приблизительно отражают близость исход- необходимо вычислить расстояния от центра, за ных объектов приложения (например, векторы в данного поисковым запросом, до всех точек верхне задачах информационного поиска не могут точно го уровня и выбрать из них несколько ближайших.

выражать смысл документов), поэтому использова- Далее с помощью предварительно построенной ние приближенных методов поиска допустимо. Так, матрицы расстояний можно выбрать точки следую например, LSH [6] дает только вероятностные га- щего уровня, ближайшие к выбранным, возможно, рантии решения задачи K-nn – поиска ближайших сократить это множество и перейти на следующий соседей [9, 5]. уровень.

Во многих случаях вычислительно трудоемкими Чтобы облегчить задачу многомерного поиска, оказываются не только поиск и подготовка векторов необходимо использовать алгоритмы кластериза (например, извлечение признаков изображений), но ции, или деления на классы. Известные методы от даже вычисление функции подобия (или расстояния носят к одному классу объекты, многомерные век между векторами). Поиск мог бы быть существенно торы которых в пространстве признаков являются ускорен, если бы можно было хранить матрицу по- соседними.

парных расстояний между объектами. К сожалению, такое решение не является масштабируемым, по- 3 Структуры данных и алгоритмы скольку размер индекса в этом случае квадратично зависел бы от количества объектов. 3.1 Структура данных Цель данной работы – построение субоптималь Для представления объектов будем использовать ной индексной структуры для приближенного поис реляционную модель. Рассматриваем объекты как ка многомерных объектов на основе функции подо многомерные векторы. Координаты многомерного бия (или функции расстояния), которая бы обеспе вектора являются различными характеристиками чивала приемлемое время ответа в практических изображений. Предполагается, что похожие изо важных диапазонах различных параметров. Для бражения будут характеризоваться близкими векто того чтобы оценить характеристики и качество этой рами.

структуры, мы реализовали ее модель над структу Для хранения будем использовать таблицы Ко рами данных, предоставляемыми промышленной ординат, Векторов, Расстояний и Компонент.

реляционной СУБД. Возможно, такое решение от В таблице Координат хранится информация о рицательно сказывается на эффективности, но обес значениях каждой координаты вектора. Чтобы печивает быструю реализацию, пригодную для ис структура таблицы не зависела от размерности век пользования в прототипах, например, в эксперимен торов, каждый вектор представляется в таблице на тальной системе поиска изображений по содержа бором строк – по одной строке для каждой коорди нию, т. е. разработанная система позволяет нахо наты вектора.

дить изображения по ряду характеристик, близких к Каждая строка таблицы имеет следующую искомому.

структуру: номер вектора;

номер координаты векто В предположении, что имеется доступная мат ра;

численное значение координаты вектора.

рица попарных расстояний, задачу поиска K бли Между всеми парами векторов необходимо вы жайших соседей можно решать просмотром одно числить расстояние. В разных приложениях можно мерного индекса по диапазону. Эта операция эф использовать для этого разные функции. В данном фективно реализована в любой реляционной СУБД.

случае расстояние вычисляется с помощью метрики Для того чтобы ограничить размер такого индекса, L1, но для метода это не принципиально.

мы будем хранить не все попарные расстояния, а Из полученных расстояний строится таблица только расстояния до K ближайших точек. Как пра Расстояний, в каждой строке которой хранится рас вило, в поисковых системах необходимо решать стояние между двумя векторами.

задачу K-nn только при небольших значениях K.

Итак, получилась таблица с атрибутами:

Для того чтобы обеспечить поиск ближайших 1. Номер вектора_1, соседей для произвольной точки в многомерном 2. Номер вектора_2, пространстве, мы строим древовидную структуру 3. Расстояние между векторами, следующим образом: имеющийся набор векторов 4. Номер компоненты связности, которой кластеризуется и выбираются центроиды каждого принадлежат оба вектора, если вектор является ча кластера. Эти центроиды образуют множество век стью остовного дерева для этой компоненты.

торов меньшего размера, чем исходной, и образуют Если вектора относятся к разным компонентам второй уровень нашей структуры. Далее кластери связности, то номер компоненты в соответствую зация и выделение центроидов повторяются до тех щей строке будет равен нулю.

пор, пока количество выделенных центроидов не Эта таблица будет очень большой. Она необхо окажется достаточно малым. Множество этих цен дима только на этапе построения индекса. В даль нейшем можно хранить не все попарные расстояния бираем вектора остовного дерева, пока не удастся между векторами, а только несколько ближайших разбить компоненту связности на две части. Затем векторов к каждому и расстояние до него. разбиваем каждую новую часть, пока размер ком Таблица Векторов имеет следующую структуру: понент не окажется между Nmin до Nmax.

1. номер вектора, В каждой компоненте связности находим цен 2. номер компоненты связности, которой этот троиды. Для нахождения i-ой компоненты центрои вектор принадлежит, да находим усредненного значение i-х компонент 3. количество векторов нижнего уровня, для векторов, входящих в заданную компоненту связно которых данный вектор является центром компо- сти.

ненты связности, Далее рассматриваем найденные центроиды в 4. расстояние до центра связности текущего качестве многомерных векторов.

уровня. Далее повторяем наш алгоритм: вычисляем по Структура таблицы Компонент: парные расстояния между векторами, строим остов 1. номер компоненты связности, ное дерево, вновь разбиваем его на компоненты 2. уровень, связности. Со второй итерации при нахождении 3. количество векторов, относящихся к этой центроидов новых компонент связности учитываем компоненте, «вес» центроидов предыдущего уровня – количест 4. номер вектора-центра этой компоненты. во векторов следующего уровня, объединенных этим центроидом.

3.2 Построение индексной структуры Так мы повторяем все шаги алгоритма, на каж дой итерации выбирая в качестве новых векторов Чтобы при поиске избежать необходимости пол центры полученных компонент связности, пока ко ного просмотра, необходимо построить иерархиче личество этих компонент не станет равным или скую поисковую структуру. Для построения этой меньшим заданного M. В результате получается древовидной структуры будем использовать метод некая многоуровневая иерархическая структура, кластеризации. Для кластеризации был реализован которую можно использовать для поиска n векто метод, основанный на построении остовного дерева ров, ближайших к искомому вектору v1.

минимальной длины.

Для построения остовного дерева используется 3.3 Поиск следующий алгоритм:

Для организации поиска надо начать с верхнего 1. полагаем многомерные вектора вершинами уровня, определить вектор v2, ближайший к иско дерева, а расстояние между векторами – дугами;

мому v1. Затем рассмотреть компоненту связности, 2. на нижнем уровне полагаем каждую вер для которой вектор v2 является центром. Если коли шину отдельной компонентой связности;

чество векторов в этой компоненте связности боль 3. находим две компоненты связности, рас ше искомого n, то можно рассматривать только эту стояние между которыми минимально;

за расстоя компоненту, если меньше n, то ищем следующую ние между компонентами связности полагаем ми ближайшую компоненту связности. От центра спус нимальное расстояние между вершинами, принад каемся к векторам данной компоненты следующего лежащим соответствующим компонентам;

уровня и так далее, пока не доходим до нижнего 4. добавляем в остовное дерево дугу между уровня.

этими двумя вершинами;

При вставке нового вектора сначала производит 5. соединяем эти компоненты связности в од ся поиск одного ближайшего, затем новый вектор ну;

добавляют в ту же компоненту, где находится бли 6. продолжаем п.2 – п.4 до тех пор, пока все жайший вектор. Если количество векторов в этой вершины не войдут в одну компоненту связности.

компоненте связности окажется больше максималь При построении дерева для наибольшей равно но допустимого, то компонента делится на две. Так мерности вводилось ограничение на число входя же для каждого следующего уровня.

щих дуг для каждой вершины – не больше Nin.

Далее разбиваем построенное остовное дере во на несколько компонент связности. В каждой 4 Эксперимент и анализ результатов компоненте связности должно быть от Nmin до Nmax Описанная модель была реализована на векто вершин. Количество компонент зависит от количе рах, координаты которых описывают различные ства векторов, хранящихся в таблице, и определяет характеристики изображений: яркость, контраст ся.

ность, насыщенность, и т. д.

При разбиении остовного дерева на компонен Ставилась задача быстрого поиска векторов, ты связности из дуг, входящих в остовное дерево, наиболее близких к искомому вектору.

выбираем дугу, имеющую максимальную длину.

Задачей экспериментального исследования было Эту дугу исключаем из остовного дерева, при этом также определение параметров, при которых дан образуются 2 компонент связности. Проверяем, что ный метод может давать наилучшие результаты.

количество векторов в образовавшихся компонен Параметрами данного метода, которые можно изме тах больше Nmin. Если нет, то возвращаем удален нять, являются:

ную дугу обратно, пометив ее. Таким образом пере – максимальное количество векторов, входящих в каждую вершину остовного дерева;

– минимальное и максимальное количество век торов, входящих в каждую компоненту связности, на которые на каждом шаге построения иерархиче ской структуры делится остовное дерево;

– количество найденных векторов, ближайших к искомому, которые мы ищем;

– количество компонент, центры которых наи более близки к искомому вектору, которые про сматриваются на каждом шаге.

Индексная структура была построена и протес тирована над несколькими тысячами векторов, ха рактеризующих изображения. Вектора имеют координату.

Скорость поиска даже при таком небольшом ко личестве векторов оказалась в десятки раз меньше, чем при линейном просмотре.

При разбиении дерева на компоненты связности максимальное количество векторов подбиралось так, чтобы оно превосходило минимальное количе ство векторов в компоненте в 3 – 4 раза. А мини мальное количество векторов в компоненте, долж но, в свою очередь, как минимум в 2 раза превосхо дить максимальное количество дуг, входящих в ка ждую вершину остовного дерева.

Следующие графики показывают полученную точность результатов приближенного поиска в за висимости от количества компонент связности, про сматриваемых на каждом шаге.

Приведенные гистограммы показывают, что оп тимально на каждом шаге просматривать 3 – 4 ком поненты.

Скорость поиска с помощью построенной ин дексной структуры в десятки раз превышала ско рость линейного поиска.

5 Заключение Индексирование многомерных объектов являет ся трудной задачей, которая привлекает внимание исследователей на протяжении нескольких десяти летий.

В этой работы мы предлагаем практическую реализацию индексной структуры для многомерных объектов в решении задачи поиска k ближайших соседей. Мы предлагаем критерии оценки эффек тивности и предлагаем параметры, от которых мо жет зависеть производительность предложенной индексной структуры.

Литература [1] Arge L., de Berg M., Haverkort H.J., Yi Ke. The priority RTree: a practically efficient and WorstCase optimal RTree.

[2] Berchtold S., Keim D.A., Kriegei H.-P. The X-tree:

an index structure for high-dimensional data// Proc.

of the 22nd Int. Conf. on Very Large Databases, 1996. – P. 28-39.

[3] Bremner D., Demaine E., Erickson J., Iacono J., Langerman S., Morin P., Toussaint G. Output sensitive algorithms for computing nearest neighbor decision boundaries// Discrete and Com putational Geometry. – 2005. – V. 33, No 4. – P. 593-604.

[4] Ciaccia et al. M-tree: an efficient access method for similarity search in metric spaces// VLDB-1997, 1997.

[5] Cover Th.M., Hart P.E. Nearest neighbor pattern classification// IEEE Transactions on Information Theory. – 1967. – V. 13, No 1. – P. 21-27.

[6] Gionis A., Indyk P., Motwani R. Similarity search in high dimensions via hashing// Proc. of the 25th Very Large Database (VLDB) Conf., 1999.

[7] Guttman A. R-Trees: a dynamic index structure for spatial searching// SIGMOD Conference, 1984. – P. 47-57.

[8] Manolopoulos Y., Nanopoulos A., Papadopou los A.N., Theodoridis Y. R-Trees: theory and appli cations. – Springer, 2005.

[9] Nigsch F.A., Bender A., van Buuren B., Tissen J., Nigsch E., Mitchell J.B.O. Melting point prediction employing k-nearest neighbor algorithms and ge netic parameter optimization// J. of Chemical In formation and Modeling. – 2006. – V. 46, No 6. – P. 2412–2422. – doi:10.1021/ci060149f.

Approximate indexing for multidimensional objects E. Mikhaylova, B. Nivikov The multidimensional k nearest neighbor problem is essential for several application areas, including infor mation retrieval, natural language processing, and data mining. To solve this problem efficiently, one needs an index structure supporting this kind of search. However, exact solution is hardly feasible in multidimensional space.

In this paper we describe and analyze an indexing technique for approximate solution of the k-nn problem.

The construction of the index tree is based on cluster ing. The index is implemented on top of high performance industrial DBMS.



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 26 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.