автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Построение адаптивной математической модели восстановления распределенных вычислительных систем

На правах рукописи

МИНОГИН Андрей Владимирович

ПОСТРОЕНИЕ АДАПТИВНОЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ВОССТАНОВЛЕНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13Л8 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

□ □3479 13Ь

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2009

003479135

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета).

Научный руководитель:

доктор физико-математических наук, профессор ПЕТРОВ Игорь Борисович

Официальные оппоненты:

доктор физико-математических наук, профессор ЖДАНОВ Александр Аркадьевич

кандидат физико-математических наук, доцент СОШНИКОВ Дмитрий Валерьевич

Ведущая организация:

Межведомственный суперкомпьютерный центр РАН

Защита состоится « /5Г » С^к^ч /гл-О 2009 года в // ^ час. на заседании диссертационного совета Д 21^.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер. д.9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).

Автореферат разослан «/^ » \sSy3Ji 2009 ]

Ученый секретарь

диссертационного совета ^—-—" 2__Федько О.С.

Общая характеристика работы Актуальность работы

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

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

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

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

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

Для многих современных работ в области возвратного восстановления характерны следующие недостатки:

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

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

В настоящей работе рассматривается построение модели возвратного восстановления с учетом следующих предположений относительно целевой системы и системы мониторинга:

1. возможность программных распространяющихся сбоев;

2. невозможность определения истинных причин сбоя;

3. возможность распределенного характера системы мониторинга;

4. максимальная прозрачность системы восстановления для разработчика и конечного пользователя.

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

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

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

Цели диссертационной работы

1. Построение адаптивной математической модели восстановления распределенной вычислительной системы в условиях распространяющихся ошибок.

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

3. Реализация модели восстановления распределенных систем на классе многоагентных систем с использованием многоагентной платформы JADE.

Методы исследования

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

комплекса программ, на основе которых проведён ряд вычислительных экспериментов.

Научная новизна работы

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

Практическая значимость работы

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

В работе приведено описание реализации предложенной модели на классе многоагентных систем в рамках многоагентной платформы JADE. Предложенная реализация может быть использована для создания отказоустойчивых многоагентных приложений.

Апробация и реализация результатов работы

По теме диссертации опубликовано 9 работ, в том числе одна [9] - в издании из списка, рекомендованного ВАК РФ.

Результаты работы докладывались на XLVIII научной конференция МФТИ (Долгопрудный-Москва, 2005 г.), международной научной конференции «Технологии Microsoft в теории и практике программирования» (Москва, 2006 г.), XVI международном научно-техническом семинаре «Современные технологии в

задачах управления, автоматики и обработки информации» (Алушта, 2007 г.), международной конференции AIS/CAD (Дивноморск, 2007 г.), международной конференции «Компьютерные науки и технологии» (Белгород, 2009 г).

Предложенная модель восстановления используется в программном комплексе автоматизированного абонентского обслуживания Mangoss.

Положения, выносимые на защиту

На защиту выносятся следующие основные положения:

1. Адаптивная математическая модель восстановления распределенной вычислительной системы в условиях распространяющихся сбоев.

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

3. Методика реализации адаптивной модели восстановления на классе многоагентных систем.

Структура и объем работы

Диссертация состоит из введения, трех глав, заключения, списка использованных источников и одного приложения. Работа изложена на 108 страницах, список использованных источников содержит 59 наименований.

Содержание работы

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

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

как ресурсоемких систем, которые плохо поддаются тестированию и отладке на малом количестве узлов сети.

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

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

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

восстановления. Оба метода требуют наличия в системе так называемого надежного хранилища (stable storage) для хранения точек восстановления и логов.

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

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

А А

(а) (б)

Рис. 1. Консистентное (а) и неконсистентное (б) множества состояний.

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

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

Большинство методик восстановления ограничиваются рассмотрением фатальных сбоев (stop-failure), то есть сбоев, приводящих к немедленной остановке процесса без распространения последствий ошибки. К фатальным сбоям относятся многие аппаратные сбои или сбои операционной системы, после которых дальнейшее выполнение программы невозможно. Для реальных систем существенную проблему представляет класс распространяющихся сбоев (propagation failures), рассматриваемых в параграфе 1.7, которые, как правило, происходят в результате программных ошибок. Данные сбои не обнаруживаются сразу, но вводят процесс в ошибочную ветку исполнения, которая, в итоге, приводит к некоторому детектируемому сбою. Главная опасность распространяющихся сбоев заключается в том, что процесс, находящийся в ошибочной ветке исполнения взаимодействует с другими процессами, изменяя их состояние некорректным образом. Характерный пример таких сбоев - ошибки синхронизации процессов.

Понятие прозрачности реализации модели разбирается в параграфе 1.8. Рассматривается влияние процесса восстановления на производительность системы и на сохранность данных пользователя, а также вопрос прозрачности реализации модели с точки зрения разработчика.

Глава 2 посвящена построению модели адаптивного восстановления распределенных систем.

В параграфе 2.1 указаны предпосылки для создания модели. Основной предпосылкой является существование распространяющихся сбоев.

Параграф 2.2 содержит формальное определение основных терминов и постановку задачи. В качестве модели целевой распределенной системы используется NCFSM - система <Q,q0,M,S> взаимодействующих

10

недетерминированных конечных автоматов, где С? - конечное непустое множество состояний, я0 - начальное состояние, М - множество неупорядоченных наборов сообщений вида < Е, п, С >, где Е - конечный алфавит набора, причем = 0, п - максимальный размер набора, С - неупорядоченный набор символов из Е. Функция 8 задает правила переходов, сопровождающихся чтением символа из некоторой очереди или записью символа в некоторую очередь. Возможны е -переходы - переходы без чтения символа.

Будем называть трассой последовательность Т=<1',12,...> мировых состояний, соединённых допустимыми последовательными переходами ЫСРБМ. Будем говорить, что я е ТА, если автомат А достигает состояния я хотя бы в

одном элементе Т. Если же автомат А достигает состояния я в элементе I1 трассы Т, то будем говорить, что я = ^.

Введем понятие консистентного состояния. Без ограничения общности можно считать, что все символы, отправляемые автоматами в рамках одной трассы, различны. Свяжем с каждым символом т, отправляемым автоматом А автомату В, индекс ¡дВ(ш)е 1Ч0. Пусть индекс символа ¡дВ(ш) равен числу символов, отправленных ранее автоматом А автомату В в трассе Т. Зафиксируем трассу Т. Пусть я е ТА. Обозначим множество индексов символов, отправленных

автоматом В и прочтённых автоматом А, через 11ди(я). Множество индексов символов, отправленных автоматом А автомату В, обозначим как 8дВ(ц).

01: Пусть Т - трасса. Состояния яе ТА и реТв автоматов А и В консистентны, если в данных состояниях совпадают множества индексов отправленных и прочитанных символов:

= И КТва(Р) = 81З(Ч)

02: Пусть Т - трасса. Состояния я, е ТА ,.--,Я„ е автоматов А,,...,АП консистентны, если все состояния попарно консистентны.

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

ИСРЗМ-система дополняется восстанавливающими переходами автомата А к одной из множества точек восстановления ^трассы Т. При этом я'д = 1д и М'А=0. Пусть < 1д,...,1д'^д,...,гд,1гЛ,{"'...> - трасса автомата А, прошедшего восстановление к состоянию в точке Г. Тогда <^,...,1:^',',...> -

восстановленная трасса автомата А. Если трасса не содержит точки восстановления, то восстановленной трассой называется сама трасса.

Будем называть вычислением некоторый конечный отрезок трассы автомата С=<1д,...,1д" >. Пусть автомат О моделирует внешний мир, то есть набор всех необратимых устройств системы. Отправка сообщения автомату О моделирует некоторое необратимое событие целевой системы. Пусть С -вычисление, тогда результатом У(С) вычисления С будем обозначать последовательность исходящих символов

У(С) =<V,.....Уп >,гдеV = ш(<^Л1 >): 1'ЛДд+| е С,уе 20

К системе предъявляется требование устойчивости к ошибкам: если >е Р, то >)€ 20

Сформулируем задачу моделирования: построить модель процесса восстановления системы взаимодействующих конечных автоматов, удовлетворяющую следующим свойствам:

1. Корректность. Если Т - восстановленная трасса автомата А, то:

С(Т)=<^,...,СЧ >:Ук,0<к<п:<^+\^+к+| ><2 Р

2. Консистентность взаимодействия. Пусть автомат А восстановлен в состояние тогда: УВ* А,к1в(^) = 8;а(1;),81в0;,) = О1гв)

3. Наблюдаемая консистентность. Пусть С1 =< 1'А,> - вычисление автомата А до момента восстановления, С2 =< > - вычисление автомата А после восстановления, тогда:

ЗС: У(С) = У(С,) • У(С2)

С =<Эд>:\/к,0<к<Ь:<8дк,5д+к+' >ё Р

4. Результативность восстановления. Пусть < 1А,...,1д,...,1А,...> -вычисление автомата А, <1А,1А+1> - ошибочный переход, < > -восстанавливающие переходы, тогда:

Зк: к > Г + 1,т(< 1к, >)е £0 или < , 1к+1 >е ^ 1к * ^

Параграф 2.3 посвящен решению поставленной задачи. Для обеспечения корректности восстановления после любого ошибочного перехода должен осуществляться восстанавливающий переход. При этом для соблюдения наблюдаемой консистентности потребуем, чтобы восстанавливающий переход непосредственно следовал за ошибочным. Для обеспечения консистентности взаимодействия предлагается использовать следующую методику определения консистентных состояний. Пусть А = {А,,...,АП} - множество всех автоматов целевой ЫСРБМ-системы. Расширим целевую систему следующим образом. У А е А введем набор параметров, связанных с состоянием q автомата А:

5Ав(ч)^0,гАВ(Ч)бКДА(Ч)сК0,УВеА,ВМ (1)

К расширенной системе предъявляются следующие требования.

В начальном состоянии: зАВ(я0) = 0,гАВ(я0) = 0, \УАВ(я0) = 0 (2)

Пусть автомат А перешел из состояния я в состояние я' с отправкой сообщения ш, тогда сообщение т содержит значение зАВ(я) (3)

5ав(Я') = 5ЛВ(Ч) + 1 (4)

Пусть автомат А получил от автомата В сообщение т, содержащее звд(р), где р - соответствующее состояние автомата В, и перешел из состояния q в состояние q', тогда

если 8ВА(р)>гАВ(я), то гАВ^') = 8ВА(р) + 1; (5)

если яВА(р)>гАВ(Ч), то WA(q') = АУА(я)и{гАВ(ч),...,8ВА(р)-1} (6)

здесь «...» означает перечисление целых чисел;

если 8ва(р) < гАВ(Ч), то \УА(Ч') = \УА(ч) \ {8ва(р)}. (7)

Нами доказана следующая теорема: пусть Т - трасса. Набор состояний Я, е ТА ,...,яп е ТА автоматов А,,..., Ап, удовлетворяющих требованиям (1) - (7),

является консистентным тогда и только тогда, когда выполнен критерий: VI, р * j: WAтi (Ч|) = \\ГАТД) = 0,г^ (ч.^зЦ = (8)

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

Недетерминированным переходом трассы ТА будем называть переход, индуцированный входящим сообщением или е -переход из состояния, имеющего минимум два исходящих е -перехода.

Предлагается следующий алгоритм (1). Пусть автомат А на трассе Т совершил ошибочный переход < 1А,1;А 1 >.

1. Выбирается недетерминированный переход <1А,1А+1 >:е<Г. Ниже представлен алгоритм выбора этого перехода.

2. Сохраняется результат УА'Г вычисления < 1:А ,...,1:А >.

3. Выполняется восстанавливающий переход А к точке 1А.

4. С помощью методики определения консистентных состояний для каждого автомата В / А выбирается такая точка трассы гв, что:

^АВ(*а) = $ва(1В )>^АВОА) = )

5. Сохраняются результаты вычислений с^,...,^ >.

6. Проверяется следующее условие на восстановленной трассе Б:

Эп: У(< вд>) = V'-',УВ Ф А: У(< % >) = V*-' При этом отправка сообщений т(<8'А,5д' >),е<1<пи т(< 8'в ,8'в'' >),гп < 1 < п не производится.

При невозможности получения результата п.4 или при невыполнении п.6 работа системы прекращается. Прекращение работы системы фактически означает невозможность устранить ошибку в силу особенностей алгоритма или некорректного выбора недетерминированного перехода в п.1.

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

Предлагается следующий базовый эвристический алгоритм (2). Пусть автомат А совершил ошибочный переходс^,^*1 >. Положим Е[. =0,С\ =0,т' =0,пе N. Рассмотрим йо итерацию восстановления для данного ошибочного перехода.

1. Пусть >последовательность недетерминированных переходов, удовлетворяющая п.1 алгоритма (1).

2. Если Ср < п, то выбирается . При этом =С|. + 1,т'г+1 = т'г.

3. Если С^ >= п, то выбирается Ь^""1'"1, если существует. При этом С^+1=0,т;+1=т" +1.

Для различения повторов одного и того же ошибочного перехода на разных циклах исполнения используется дополнительный параметр ее N. Пусть < >,< 1дМд2+1 > - два ошибочных перехода, причем ^ = ^, тогда переходы

считаются различными в рамках алгоритма (2), если |Г2-Г,|>8. При невозможности выбора подходящего недетерминированного состояния работа системы прекращается. Отметим, что частые отказы или низкая эффективность системы могут быть связаны с неверным выбором параметра п. Заметим, что п.2 алгоритма (2) существенен для устранения фиксированных, в частности, аппаратных, сбоев. П.З алгоритма (2) необходим для устранения распространяющихся программных сбоев.

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

параграфе требованиям. Рис. 2 иллюстрирует основные элементы модели.

<1 /

/ 1

с2 у / С1, Сг-точки восстановления

Г - ошибочный переход е - недетерминированный переход V - наблюдаемый переход

<1 /

/

/

*-►

Рис. 2. Элементы модели восстановления.

Возможны другие эвристические модификации алгоритма (2), например, с использованием геометрической прогрессии.

В параграфе 2.4 рассматривается возможность применения адаптивных методов для повышения эффективности предлагаемой модели восстановления. Формализуем понятие эффективности системы восстановления. Пусть <^...^д""1,^,...,^,^,^1...,^ > - некоторое вычисление автомата А, прошедшего восстановление к состоянию 1д = ^ в точке {. Характеристикой эффективности процесса восстановления может служить следующая величина:

.Н1 16

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

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

Щ Потерянное время ->

Суммарное вычислительное время

Рис 3. Вычислительное время, потерянное в результате восстановления.

Мы предлагаем использовать адаптивную методику для более эффективного определения точки восстановления. В качестве адаптивно накапливаемых знаний автомата А рассматривается следующий объект: К=<Ьд,Ьд,п,ш>,п,те Ы,Ьд- ошибочный переход, Ьд — недетерминированный переход.

Предлагается следующий алгоритм (3) накопления и использования знаний в процессе восстановления: а,,а2,а3,а4,а5,а6 е Я,Ье [0,1] - параметры.

1. Пусть автомат А совершил ошибочный переходЬд =< 1д,1д+| >.

17

2. Выберем ближайший к точке сбоя недетерминированный переход hA , удовлетворяющий п.1 алгоритма (1). Если такого элемента нет, то завершим работу системы. Если в базе знаний нет элемента К:Ьд(К) = Ьд,Ьд(К) = Ьд, то добавим в базу знаний элемент:

K=<hfA,h;\l,l>

3. Выберем из базы знаний все элементы К: 3e':hA(K) = hA,eA(K) = e', е'- недетерминированный переход, удовлетворяющий п.1 алгоритма (1). Обозначим ек=тах(е'). Рассчитаем веса элементов:

wCe^^-^-.d^f-e,. a3mK Мк

Выберем ег с вероятностью рт -

2>(ек)

к

4. Пусть следующий достигнутый ошибочный переход Ь® =< 1А,1д+1 >

a. Если Ь* ^Ид, то п(Кг):=п(Кг) + 1.

b. Если Ьд = Ьд, то т(Кг):= т(Кг) + 1. Выбирается случайное число ре [0,1]

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

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

практической реализации модели возможна модификация алгоритма с использованием дополнительных знаний о целевой системе. Более подробно этот вопрос рассматривается в главе 3.

В параграфе 2.5 рассматривается модель системы восстановления в условиях вероятностного характера сведений о детектируемой ошибке. Такая ситуация возникает при использовании распределенной системы мониторинга. Мы исходим из следующей модели. Пусть Т=<1',.--Дг >- трасса. При детектировании сбоя в точке Г система мониторинга предоставляет сведения вида: {(^....сиДеМ, такие что ЗкЗ^-с^ >еБ

Основное отличие от случая точного детектирования ошибки заключается в невозможности прямого сравнения детектируемых сбоев. Для построения адаптивной модели восстановления необходимо построить критерий сравнения детектируемых множеств вида {с!,с!п}. Мы предлагаем использовать следующий критерий. Для множества {(1, ,...,(!„} :

1. Найдем к:(1к = шахс1г

2. Выберем недетерминированный переход < I ^, >: е < - с!к.

3. Подберем подходящие консистентные точки восстановления 1д. для автоматов А;Д*к (см. алгоритм 1).

4. Если ЗкС| — с!;,товыполнимп.2-4 для к = 1.

Для двух построенных консистентных глобальных состояний вычислим

меру удаленности:

г=1!1с1 п

Можно использовать следующий критерий равенства детектируемых множеств: |г - г1 < Я, где Я устанавливается эмпирически, исходя из особенностей системы. Далее алгоритм (3) последовательно применяется к системе автоматов

со следующим изменением: при построении новой точки восстановления на шаге (3) она должна соответствовать условию < tAk >: е < f - dk.

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

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

Параграф 3.2 посвящен описанию основных спецификаций многоагентных систем: MASIF и ИРА. Приводится описание многоагентной платформы JADE, которая используется для реализации системы восстановления.

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

20

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

Рис. 4. Сравнение эффективности эвристических и адаптивной моделей.

Реализация адаптивного алгоритма восстановления рассматривается в параграфе 3.4. Основные практические вопросы, решаемые в данном параграфе -реализация адаптивного алгоритма выбора логической контрольной точки восстановления, корректный откат зависимых агентов в процессе восстановления и проверка воспроизводимости наблюдаемых событий. Отдельный вопрос представляет описание детектируемой ошибки с целью построения критерия сравнения ошибок. Для описания контекста ошибки используются, в частности, следующие сведения: параметры исключения, идентификатор агента, текущее поведение агента (текущий цикл исполнения). Особое внимание уделяется ошибкам синхронизации и примерам их устранения. Показано, что обработка ошибок синхронизации упрощается путем включения в контекст ошибки дополнительных сведений о разделяемом объекте. На рис. 4 приводятся интегральные характеристики эффективности для трех типов моделей

21

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

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

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

В приложении приведены основные компоненты реализованного программного комплекса.

Основные результаты и выводы диссертации

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

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

3. Предложенные модели реализованы на классе многоагентных систем в рамках многоагентной платформы JADE.

Список публикаций по теме диссертации

1. Бородин М.В., Миногин A.B., Устюжанин А.Е. Верифицируемая многоагентная платформа // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVIII научной конференции - М. - Долгопрудный: МФТИ, 2005. - С. 6869.

2. Миногин A.B., Дубовик Г.А. Верифицируемая многоагентная платформа LiveNAP // Технологии Microsoft в теории и практике программирования: Труды Всероссийской конференции студентов, аспирантов и молодых ученых - М.: МГТУ им. Н.Э. Баумана, 2006. - С. 23-24.

3. Миногин A.B., Устюжанин А.Е. Реализация субъективного подхода к тестированию распределенных систем на примере многоагентной платформы LiveNAP // Процессы и методы обработки информации: Сборник научных трудов - М.: МФТИ, 2006. - С. 208-217.

4. Дубовик Г.А., Миногин A.B., Тодосьев В.В., Устюжанин А.Е. Использование контролирующих моделей для мониторинга распределенных многоагентных систем // Моделирование процессов обработки информации: Сборник научных трудов - М.: МФТИ, 2007. - С. 147-162.

5. Дубовик Г.А., Миногин A.B., Тодосьев В.В., Устюжанин А.Е. Разработка языка описания контролирующих моделей // Труды VII Международной научно-технической конференции «Интеллектуальные системы» и XXII Международной научно-технической конференции «Интеллектуальные САПР» - М.: Физматлит, 2007. - Т.З - С. 51-57.

6. Дубовик Г.А., Миногин A.B., Устюжанин А.Е. Методика мониторинга распределенных многоагентных систем // Современные технологии в задачах управления, автоматики и обработки информации: труды XVI Международного научно-технический семинара. - Тула: ТулГУ, 2007. - С. 17.

7. Миногин A.B. Методика возвратного восстановления высоко распределенной системы с ненадежными каналами коммуникации // Компьютерные науки и технологии: Труды Международной научно-технической конференции - Белгород: БелГУ, 2009. - С. 34-38.

8. Дубовик Г.А., Миногин A.B., Устюжанин А.Е. Устранение аномалий взаимодействия автоматов в системах с перестановкой символов. // Модели и методы обработки информации: Сборник статей. - М.: МФТИ, 2009.-С. 223-230.

9. Миногин A.B. Методика определения консистентного состояния в высоко распределенных системах с перестановкой, задержкой и потерей сообщений // Системы управления и информационные технологии - 2009 -№2.1(36) -С. 162-166.

В работах с соавторами лично соискателем выполнено следующее: [1], [2], [3] -

разработка адаптивной математической модели восстановления распределенной вычислительной системы и построение методики определения консистентного состояния, [4], [5], [6], [8] - построение модели восстановления в условиях вероятностного характера сведений об ошибках и ее практическая реализация.

МИНОГИН Андрей Владимирович

ПОСТРОЕНИЕ АДАПТИВНОЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ВОССТАНОВЛЕНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Автореферат

Подписано в печать 07.09.2009. Формат 60x90 1/16. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 40112

Типография П-Центр

129515, г.Москва, улица Академика Королева, дом 13, подъезд 5, этаж 9, офис 902 тел.: (495) 956-2195, факс (495) 616-6797

Введение.

Глава 1. Современное состояние предметной области.

1.1. Распределенные вычислительные системы.

1.2. Надежность распределенных вычислительных систем.

1.3. Отказоустойчивые системы. Репликация и восстановление.

1.4. Возвратное восстановление.

1.5. Метод фиксации контрольных точек.

1.6. Метод журналирования событий.

1.7. Фатальные сбои и распространяющиеся сбои.

1.8. Прозрачность методик восстановления.

Глава 2. Адаптивная математическая модель восстановления распределенной системы.

2.1. Предпосылки создания адаптивной модели.

2.2. Формальная постановка задачи.

2.3. Построение математической модели.

2.4. Применение адаптивных методов для повышения эффективности модели.

2.5. Построение модели в условиях вероятностного характера сведений об ошибках.

Глава 3. Методика реализации модели на классе многоагентных систем

3.1. Многоагентные системы.

3.2. Спецификации многоагентных систем.

3.3. Недетерминированные события.

3.4. Реализация модели восстановления.

3.5. Дополнительные технические вопросы.

Актуальность работы

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

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

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

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

Для многих современных работ в области возвратного восстановления характерны следующие недостатки:

1. Сильные предположения относительно характера возможных сбоев. В частности, в большинстве работ рассматриваются только фатальные (например, аппаратные) сбои, приводящие к немедленной остановке процессов, хотя для многих реальных систем более характерны распространяющиеся программные сбои [10].

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

В настоящей работе рассматривается построение модели возвратного восстановления с учетом следующих предположений относительно целевой системы и системы мониторинга:

1. возможность программных распространяющихся сбоев;

2. невозможность определения истинных причин сбоя;

3. возможность распределенного характера системы мониторинга;

4. максимальная прозрачность системы восстановления для разработчика и конечного пользователя.

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

Для практической реализации построенной модели и исследования особенностей ее поведения был выбран класс многоагентных систем. Направление многоагентных систем является актуальным и быстро развивающимся, так как парадигма агентного программирования предлагает новые возможности для построения распределенных программных комплексов и интернет-ориентированных приложений [44]. Основная идея парадигмы многоагентного программирования - использование автономных мобильных программных объектов, называемых агенты. Агенты взаимодействуют между собой и с внешней средой посредством отправки сообщений. Система взаимодействующих агентов хорошо моделирует систему взаимодействующих конечных автоматов и, следовательно, удобна для реализации модели восстановления распределенной системы.

Цели диссертационной работы

1. Построение адаптивной математической модели восстановления распределенной вычислительной системы в условиях распространяющихся ошибок.

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

3. Реализация модели восстановления распределенных систем на классе многоагентных систем с использованием многоагентной платформы JADE. Методы исследования

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

Научная новизна работы

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

Практическая значимость работы

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

В работе приведено описание реализации предложенной модели на классе многоагентных систем в рамках многоагентной платформы JADE. Предложенная реализация может быть использована для создания отказоустойчивых многоагентных приложений.

Апробация работы и публикации

По теме диссертации опубликовано 9 работ, в том числе одна [9] — в издании из списка, рекомендованного ВАК РФ.

Результаты работы докладывались на XLVIII научной конференция МФТИ (Долгопрудный-Москва, 2005 г.), международной научной конференции «Технологии Microsoft в теории и практике программирования» (Москва, 2006 г.), XVI международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2007 г.), международной конференции AIS/CAD (Дивноморск, 2007 г.), международной конференции «Компьютерные науки и технологии» (Белгород, 2009 г).

Предложенная модель восстановления используется в программном комплексе автоматизированного абонентского обслуживания Mangoss.

Положения, выносимые на защиту

На защиту выносятся следующие основные положения:

1. Адаптивная математическая модель восстановления распределенной вычислительной системы в условиях распространяющихся сбоев.

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

3. Методика реализации адаптивной модели восстановления на классе многоагентных систем.

Структура и объем работы

Диссертация состоит из введения, трех глав, заключения, списка использованных источников и одного приложения. Работа изложена на 108 страницах, список использованных источников содержит 59 наименований.

Заключение

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

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

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

3. Предложенные модели реализованы на классе многоагентных систем в рамках многоагентной платформы JADE.

1. Миногин А.В., Дубовик Г.А. Верифицируемая многоагентная платформа LiveNAP // Технологии Microsoft в теории и практике программирования: Труды Всероссийской конференции студентов, аспирантов и молодых ученых / МГТУ им. Н.Э. Баумана М., 2006. - С. 23-24.

2. Миногин А.В. Методика возвратного восстановления высоко распределенной системы с ненадежными каналами коммуникации // Компьютерные науки и технологии: Труды Международной научно-технической конференции — Белгород: БелГУ, 2009. С. 34-38.

3. Дубовик Г.А., Миногин А.В., Устюжанин А.Е. Устранение аномалий взаимодействия автоматов в системах с перестановкой символов. // Модели и методы обработки информации: Сборник статей. М.: МФТИ, 2009. - С. 223-230.

4. Миногин А.В. Методика определения консистентного состояния в высоко распределенных системах с перестановкой, задержкой и потерей сообщений // Системы управления и информационные технологии Воронеж: Научная книга, 2009. - №2.1 (36) - С. 162-166.

5. David Е. Lowell, Subhachandra Chandra, Peter M. Chen. Exploring failure transparency and the limits of gencric recovery // Proceedings of the 4th USENIX OSDI Symposium 2000 - P. 289-304.

6. M Wiesmann, F. Pedone, A. Schiper, B. Kemme, G. Alonso. Understanding Replication in Databases and Distributed Systems. // 20th IEEE International Conference on Distributed Computing Systems (ICDCS'00) 2000. - P. 264-274.

7. Г. Tannenbaum and M. Litzkow. The Condor Distributed Processing System. // Dr. Dobb's Journal 1995 - P. 40-48.

8. Yi-Min Wang, Yennun Huang, Kiem-Phong Vo, Pi-Yu Chung, and Chandra Kintala. Checkpointing and Its Applications. // Proceedings of the 1995 International Symposium on Fault-Tolerant Computing (FTCS). 1995. - P. 2231.

9. D. E. Lowell and P. M. Chen. Discount Checking: Transparent, Low-Overheadi

10. Recovery for General Applications. University of Michigan CSETR-410-99, 1998.

11. Fred B. Schneider. Byzantine Generals in Action: Implementing Fail-Stop Processors. // ACM Transactions on Computer Systems. 1984 - N 2. - P. 145154.

12. Schlichting R.D., Schneider F.B. Failstop processors: An approach to designing fault-tolerant computing systems. // ACM Transactions on Computing Systems. -1983 -V.1,N3.-P. 222-238.

13. Cao J. Efficient synchronous checkpointing in distributed systems. // Proceedings of the 15th Australia Computer Science Conference. 1992 - P. 165-179.

14. Cao J., Wang K.C. Efficient synchronous checkpointing in distributed systems. // Technical Report 91/6. James Cook University of North Queensland, Department of Computer Science. - 1991.

15. G. Jiang. Infrastructure Web: Distributed monitoring and managing critical infrastructures. // Proc. of. SPIE. 2001 - V.4232.

16. И. Б. Бурдонов, А. С. Косачев, В. H. Пономаренко, В. 3. Шнитман. Обзор подходов к верификации распределенных систем. // Технический отчёт М.: ИСП РАН, 2003.-52 с.

17. D. Brand, P. Zafiropulo. On Communicating Finite-State Machines // Journal of the Association for Computing Machinery. 1983 - V.30, N 2. - P. 323-342.3e.Gerard J. Holzmann. Design and Validation of Computer Protocols. Prentice Hall, 1990.-554 p.

18. F.B. Schneider. Replication Management using the State-Machine Approach. // Distributed Systems. 1993 - P. 169-197.

19. N. Vlassis. A Concise Introduction to Multiagent Systems and Distributed AI. -University of Amsterdam. 2003. 76 p.

20. Michael Wooldridge. An Introduction to MultiAgent Systems. John Wiley & Sons Ltd. 2002.

21. Carl Hewitt and Jeff Inman. DAI Betwixt and Between: From «Intelligent Agents» to Open Systems Science. // IEEE Transactions on Systems, Man, and Cybernetics. 1991 - P. 1409-1418.

22. D. Milojicic. MASIF: The OMG mobile agent system interoperability facility. // Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag. 1998 -P. 50.

23. P. D. О'Brian, R. C. Nicol. FIPA—toward a standard for software agents. 11 ВТ Technol. J. 1998 - V.16, N 3.

24. F. Bellifemine, A. Poggi, G.Giovanni Rimassa. JADE—A FIPAcompliant agent framework. // Proc. PAAM, London, U.K. 1999 - P. 97-108.

25. Проект JavaFlow Электронный ресурс. — режим. дост.: http://commons.apache.org/sandbox/javaflow/

26. Geert Bevin. Continuations in Java HTML. (http://www.artima.com/leiava/articles/continuations.html').

27. Elnozahy E.N. Manetho. Fault tolerance in distributed systems using rollback-recovery and process replication: Ph.D. Thesis. Rice University, Department of Computer Science, 1993.

28. Goldberg A., Gopal A., Li K., Strom R., Bacon D. Transparent recovery of Mach applications. // Usenix Mach Workshop Proceedings 1990 - P. 169-184.

29. Bartlett J.F. A Non Stop Kernel. // Proceedings of the Eighth ACM Symposium on Operating Systems Principles 1981 - P. 22-29.

30. Johnson D.B., Zwaenepoel W. Senderbased message logging. // Digest of Papers FTCS-17, The Seventeenth Annual International Symposium on Fault-Tolerant Computing 1987-P. 14-19.

31. David E. Lowell. Theory and Practice of Failure Transparency: PhD thesis -University of Michigan, 1999.

32. David E. Lowell, Peter M. Chen. Free Transactions with Rio Vista. // Proceedings of the 1997 Symposium on Operating Systems Principles. 1997 - P. 143-146.