.RU

7. Обеспечение надежности в распределенных системах


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

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

Отказоустойчивость тесно связана с понятием надежных систем {dependable systems). Надежность — это термин, охватывающий множество важных требований к распределенным системам, включая:


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

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

Система с высокой безотказностью — это система, которая, скорее всего, будет непрерывно работать в течение относительно долгого времени. Между безотказностью и доступностью имеется небольшая, но существенная разница. Если система отказывает на одну миллисекунду каждый час, она имеет доступность порядка 99,9999 %, но крайне низкую безотказность. С другой стороны, система. которая никогда не отказывает, но каждый август отключается на две недели, имеет высокую безотказность, но ее доступность составляет всего 96 %. Эти две характеристики — не одно и то же.

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

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

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

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

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

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

Случайные отказы (сбои) при повторении операции исчезают.

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

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

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

Отказы по характеру своего проявления подразделяются на «византийские» (система активна и может проявлять себя по-разному, даже злонамеренно) и «пропажа признаков жизни» (частичная или полная). Первые распознать гораздо сложнее, чем вторые. Свое название они получили по имени Византийской империи (330-1453 гг.), где расцветали конспирация, интриги и обман.

Разработаны различные схемы классификации отказов:

Поломка {crash failure) имеет место при внезапной остановке сервера, при этом до момента остановки он работает нормально. Важная особенность поломки состоит в том, что после остановки сервера никаких признаков его работы не наблюдается. Типичный пример поломки — полное зависание операционной системы, когда единственным решением проблемы является перезагрузка.

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

^ Ошибки сшрсронизации (timing failures) возникают при ожидании ответа дольше определенного временного интервала. Чаще, однако, сервер отвечает слишком поздно, в этом случае говорят, что произошла ошибка производительности (performance failure).

Еще один важный тип ошибок — ошибки отклика (response failures), при которых ответы сервера просто неверны. В случае ошибки значения (value failure) сервер дает неверный ответ на запрос. Так, например, эту ошибку демонстрирует поисковая машина, систематически возвращающая адреса web-страниц, не связанных с запросом пользователя.

Другой тип ошибок отклика — ошибки передачи состояния (state transition failures). Этот тип ошибок характеризуется реакцией на запрос, не соответствующей ожиданиям. Так, например, если сервер получает сообщение, которое он не в состоянии распознать, и никаких мер по обработке подобных сообщений не предусмотрено, возникает ошибка передачи состояния. В частности, сервер может неправомерно осуществить по умолчанию некие действия, производить которые в данном случае не следовало бы.

^ Произвольная ошибка – сервер отправляет случайные сообщения в случайные моменты времени.

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

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

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

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

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

Рассмотрим, например, схему, показанную на рис. На ней сигнал проходит последовательно через устройства А, В и С. Если одно из них неисправно, результат, вероятно, будет неверен.



На рис. б каждое из устройств присутствует в трех экземплярах. Переход к следующему участку схемы определяется тройным голосованием. Устройство голосования — это схема с тремя входами и одним выходом. Если два или три входных сигнала совпадают, выходной сигнал равен входному. Если все три входных сигнала различны, выходной сигнал не определен. Такая схема известна под названием тройного модульного резервирования (Triple Modular Redundancy, TMR).

Допустим, элемент А2 отказал. Каждое из устройств голосования, V1, V2 и V3, получает два правильных (идентичных) входных сигнала и один неправильный, и каждое из них передает на второй участок цепи правильное значение. В результате эффект отказа А2 оказывается полностью замаскированным, а значит, входные сигналы элементов В1, В2 VL ВЗ абсолютно такие же, как если бы никакого отказа не было.

Рассмотрим теперь, что будет, если в придачу к ^ А2 откажут также элементы ВЗ и С1. Эффект их отказа также будет замаскирован, и все три выходных сигнала окажутся правильными.

Прежде всего, непонятно, зачем на каждом этапе нужно использовать три устройства голосования. Вообще-то определить и донести до нас мнение большинства может и одно устройство голосования. Однако устройство голосования — это тоже компонент, который тоже может отказать. Рассмотрим, например, отказ У1 Входящий сигнал В1 в этом случае будет неверным, но до тех пор, пока все остальное работает, В2 и ВЗ будут давать одинаковые выходные сигналы, и устройства V4, V5 и V6 образуют правильный результат для третьего этапа.

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

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

Разумеется, TMR можно применять и рекурсивно. Например, можно повышать

надежность микросхем, встраивая в них механизмы TMR.

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


^ 7.1. Восстановление после отказа.

Восстановление может быть прямым (без возврата к прошлому состоянию) и возвратное.

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

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

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

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

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

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

(1) Потери производительности, вызванные запоминанием состояний, восстановлением запомненного состояния и повторением ранее выполненной работы, могут быть слишком высоки.

(2) Нет гарантии, что сбой снова не повторится после восстановления.

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

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

Для восстановления состояния в традиционных ЭВМ применяются два метода (и их комбинация), основанные на промежуточной фиксации состояния либо ведении журнала выполняемых операций. Они различаются объемом запоминаемой информацией и временем, требуемым для восстановления.

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

Устойчивые хранилища играют важную роль в восстановлении распределенных

систем. Здесь мы кратко обсудим этот вопрос.

Хранилища делятся на три категории. Первая — это стандартная оперативная память, стирающаяся при отключении питания или перезагрузках машины.

Следующая категория — дисковые хранилища, переживающие ошибки процессора,

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

И, наконец, существуют так называемые устойчивые хранилища {stable storage), разработанные для выживания в любых «передрягах», кроме катастроф вроде наводнений или землетрясений.

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

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




Применение подобных методов в распределенных системах наталкивается на следующие трудности.
7.1.1. Сообщения-сироты и эффект домино.


На рисунке показаны три процесса (X,Y,Z), взаимодействующие через сообщения. Вертикальные черточки показывают на временной оси моменты запоминания состояния процесса для восстановления в случае отказа. Стрелочки соответствуют сообщениям и показывают моменты их отправления и получения.

Если процесс X сломается, то он может быть восстановлен с состояния x3 без какого-либо воздействия на другие процессы.

Предположим, что процесс Y сломался после посылки сообщения m и был возвращен в состояние y2. В этом случае получение сообщения m зафиксировано в x3, а его посылка не отмечена в y2. Такая ситуация, возникшая из-за несогласованности глобального состояния, не должна допускаться (пример - сообщение содержит сумму, переводимую с одного счета на другой). Сообщение m в таком случае называется сообщением-сиротой. Процесс X должен быть возвращен в предыдущее состояние x2 и конфликт будет ликвидирован.

Предположим теперь, что процесс Z сломается и будет восстановлен в состояние z2. Это приведет к откату процесса Y в y1, а затем и процессов X и Z в начальные состояния x1 и y1. Этот эффект известен как эффект домино.
^ 7.1.2. Потеря сообщений.


Предположим, что контрольные точки x1 и y1 зафиксированы для восстановления процессов X и Y, соответственно.

Если процесс Y сломается после получения сообщения m, и оба процесса будут восстановлены (x1,y1), то сообщение m будет потеряно (его потеря будет неотличима от потери в канале).

  1. ^ Проблема бесконечного восстановления.




Процесс Y сломался до получения сообщения n1 от X. Когда Y

вернулся в состояние y1, в нем не оказалось записи о посылке сообщения m1. Поэтому X должен вернуться в состояние x1.



После отката Y посылает m2 и принимает n1 (сообщение-призрак). Процесс X после отката к x1 посылает n2 и принимает m2. Однако X после отката уже не имеет записи о посылке n1. Поэтому Y должен повторно откатиться к y1. Теперь X должен откатиться к x1, поскольку он принял m2, о посылке которого в Y нет записи. Эта ситуация будет повторяться бесконечно.
^ 7.1.4. Консистентное множество контрольных точек.
Описанные выше трудности показывают, что глобальная контрольная точка, состоящая из произвольной совокупности локальных контрольных точек, не обеспечивает восстановления взаимодействующих процессов.

Однако самый серьезный недостаток — это необходимость расчета границы восстановления.

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

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

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

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

^ 7.1.5. Синхронная фиксация контрольных точек и восстановление.

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

^ Алгоритм создания консистентного множества контрольных точек.

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

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

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

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

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

Алгоритм выполняется в две фазы.

1-ая фаза.

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

2-ая фаза.

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

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

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

Алгоритм отката (восстановления).

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

Выполняется в две фазы.

1-ая фаза.

Инициатор отката спрашивает остальных, готовы ли они откатываться. Когда все будут готовы к откату, то он принимает решение об откате.

2-ая фаза.

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

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

  1. Дополнительные служебные сообщения для реализации алгоритма.

  2. Синхронизационная задержка - нельзя посылать неслужебные сообщения во время работы алгоритма.


Если отказы редки, то указанные потери совсем не оправданы.

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

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

Для этого обозначим т-ю контрольную точку процесса ^ Р как CP[i](m).

Пусть INT[i](m) обозначает интервал между контрольными точками CP[i](m-1)

и CP[i](m).

Когда процесс Pi отправляет сообщение в интервале INT[i](т), он добавляет к нему пару (i,m), пересылая ее принимающему процессу. Когда процесс Pj получает сообщение в интервале INT[j](n) вместе с парой (i,m), он записывает зависимость

INT[i](m) -> INT[j](n). Таким образом, когда Pj создает контрольную точку CP[j](n), он дополнительно вместе с прочей информацией для восстановления, входящей в CP[j](n), записывает в локальное хранилище данных и эту зависимость.

Предположим теперь, что в некоторый момент процесс ^ Р1 необходимо откатить в контрольную точку CP[i](m-l). Для того чтобы гарантировать глобальную непротиворечивость, нам следует убедиться, что все процессы, получавшие от Р1 сообщения, посланные в интервале INT[i](m), откачены назад к состоянию, предшествующему получению этих сообщений. Так, например, процесс Pj в нашем примере следует откатить как минимум до контрольной точки CP[j](n-l). Если CP[j](n-1) не приведет систему в глобально непротиворечивое состояние, следует произвести дальнейший откат.

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


7.2. Отказоустойчивость.

Изложенные выше методы восстановления после отказов для некоторых систем непригодны (управляющие системы, транзакции в on-line режиме) из-за прерывания нормального функционирования.

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

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

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

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

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

  1. Использование режима «горячего резерва» (второй пилот, резервное ПО).

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

^ 7.2.2. Использование активного размножения.

Наглядный пример - тройное дублирование аппаратуры в бортовых компьютерах и голосование при принятии решения.

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


^ Алгоритмы голосования.

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

Файл может модифицироваться разными процессами только последовательно (при открытии файла на запись процесс-писатель будет ждать закрытия файла другим писателем или всеми читателями), а читаться всеми одновременно (протокол писателей-читателей). Все модификации файла нумеруются и каждая копия файла характеризуется номером версии – количеством ее модификаций. Каждой копии приписано некоторое количество голосов Vi. Пусть общее количество приписанных всем копиям голосов равно V. Определяется кворум записи Vw и кворум чтения Vr так, что

Vw +Vr > V

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

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

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

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


Протоколы принятия единого решения

Необходимо отметить, что в условиях отсутствия надежных коммуникаций (с ограниченным временем задержки) не может быть алгоритма достижения единого решения. Рассмотрим известную «проблему двух армий».

Армия зеленых численностью 5000 воинов располагается в долине.

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

Предположим, что командир 1-ой синей армии генерал Александр посылает (с посыльным) сообщение командиру 2-ой синей армии генералу Михаилу «Я имею план - давай атаковать завтра на рассвете». Посыльный возвращается к Александру с ответом Михаила - «Отличная идея, Саша. Увидимся завтра на рассвете». Александр приказывает воинам готовиться к атаке на рассвете.

Однако, чуть позже Александр вдруг осознает, что Михаил не знает о возвращении посыльного и поэтому может не отважиться на атаку. Тогда он отправляет посыльного к Михаилу чтобы подтвердить, что его (Михаила) сообщение получено Александром и атака должна состояться.

Посыльный прибыл к Михаилу, но теперь тот боится, что не зная о прибытии посыльного Александр может не решиться на атаку. И т.д. Ясно, что генералы никогда не достигнут согласия.

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

Теперь предположим, что коммуникации надежны, а процессоры нет.

Классический пример протокола принятия согласованных решений - задача «Византийских генералов».

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

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

Соответствующий рекурсивный алгоритм был предложен в 1982 г. (Lamport).

Проиллюстрируем его для случая n=4 и m=1. В этом случае алгоритм осуществляется в 4 шага.

1 шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал-1 указал 1 (одна тысяча воинов), генерал-2 указал 2, генерал-3 указал трем остальным генералам соответственно x,y,z, а генерал-4 указал 4.

2-ой шаг. Каждый формирует свой вектор из имеющейся информации.

Получается:

vect1 (1,2,x,4)

vect2 (1,2,y,4)

vect3 (1,2,3,4)

vect4 (1,2,z,4)

3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опять произвольные значения).

Генералы получают следующие вектора:

g1

g2

g3

g4

(1,2,y,4)

(1,2,x,4)

(1,2,x,4)

(1,2,x,4)

(a,b,c,d)

(e,f,g,h)

(1,2,y,4)

(1,2,y,4)

(1,2,z.4)

(1,2,z.4)

(1,2,z.4)

(i,j,k.l)



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

Все лояльные генералы получают один вектор (1,2,»неизвестен»,4) - согласие достигнуто.

Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто.

Lamport доказал, что в системе с m неверно работающими процессорами можно достичь согласия только при наличии 2m+1 верно работающих процессоров (более 2/3).

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

Применение алгоритма - надежная синхронизация часов.

^ Надежная групповая рассылка

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

^ Базовые схемы надежной

групповой рассылки

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

Рассмотрим случай, когда один передатчик должен сделать групповую рассылку

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

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

быть частично потеряны, а частично доставлены, но не всем потенциальным

потребителям.

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



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

^ Масштабируемость надежной групповой рассылки

Основная проблема описанной выше схемы групповой рассылки состоит в том, что она не в состоянии работать с большим количеством получателей. При наличии N получателей отправитель должен быть готов обрабатывать как минимум N подтверждений. Если получателей будет много, отправитель может быть просто погребен под ответами. Этот эффект известен под названием обратный удар (feedback implosion). Кроме того, мы должны прршимать во внимание и тот факт, что получатели могут быть разбросаны по всей глобальной сети.

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

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

^ Неиерархическое управление обратной связью

Ключевая задача при создании масштабируемых решений для надежной групповой рассылки — уменьшение числа откликов, получаемых отправителем от получателей. В некоторых глобальных приложениях используется популярная модель подавления откликов (feedback suppression), которая лежит в основе протокола масштабируемой надежной групповой рассылки (Scalable Reliable Multicasting, SRM), работающего следующим образом.

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

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

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



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

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

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

^ Иерархическое управление обратной связью

Описанный выше механизм подавления откликов в основе своей не является

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

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

метода организации групповой рассылки иллюстрирует рис.

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



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

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

Основная проблема в иерархическом подходе — построение дерева. Во многих случаях дерево должно строиться динамически.

^ Упорядочение сообщений

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

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

Процесс Р1

Процесс Р2

Процесс Р3

Отправка m1

Получение m1

Получение m2

Отправка m2

Получение m2

Получение m1

В случае надежной групповой рассылки в порядке FIFO (reliable FIFO-ordered multicast) коммуникационный уровень обязан доставлять входящие сообщения каждому из процессов в том же порядке, в котором они были отправлены.

Процесс Р1

Процесс Р2

Процесс Р3

Процесс Р4

Отправка m1

Получение m1

Получение m3

Отправка m3

Отправка m2

Получение m2

Получение m1

Отправка m4




Получение m3

Получение m2







Получение m4

Получение m4




И, наконец, при надежной причинно упорядоченной групповой рассылке (reliable causally-ordered multicast) сообщения доставляются в порядке потенциальной причинной связи между ними. Другими словами, если сообщение m1 причинно предшествует сообщению т2, независимо от того, посылались они одним отправителем или разными, коммуникационный уровень каждого из получателей всегда будет доставлять т2 после того, как примет и доставит m1. Отметим, что причинно упорядоченная групповая рассылка может быть реализована с использованием обсуждавшихся ранее векторных отметок времени.

^ Полностью упорядоченная групповая рассылка (total-ordered multicast) означает, что независимо от того, как именно упорядочена доставка сообщений (причинно, по FIFO или не упорядочена вовсе), дополнительно требуется, чтобы сообщения доставлялись всем членам группы в одинаковом порядке.

Алгоритм надежных неделимых широковещательных рассылок сообщений.

1-ая фаза.

Процесс-отправитель посылает сообщение группе процессов (список их идентификаторов содержится в сообщении).

При получении этого сообщения процессы:

2-ая фаза.

При получении ответов от всех адресатов, отправитель:



Получив окончательный приоритет, получатель:

  1. Приписывает сообщению этот приоритет.

  2. Помечает сообщение как «доставленное».

  3. Упорядочивает все буферизованные сообщения по возрастанию их приписанных приоритетов.

  4. Если первое сообщение в очереди отмечено как «доставленное», то оно будет обрабатываться как окончательно полученное.


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

1. Опрашивает всех получателей о статусе этого сообщения.

Получатель может ответить одним из трех способов:



2. Получив все ответы координатор выполняет следующие действия:



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



^ Распределенное подтверждение

Задача атомарной групповой рассылки, которую мы обсуждали, — это пример более общей задачи, известной под названием распределенного подтверждения (distributed commit). Задача распределенного подтверждения включает в себя операции, производимые либо с каждым членом группы процессов, либо ни с одним из них. В случае надежной групповой рассылки операцией будет доставка сообщения. В случае распределенных транзакций операцией будет подтверждение транзакции на одном из caйтов, задействованных в транзакции.

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

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

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

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

^ Двухфазное подтверждение

Рассмотрим протокол двухфазного подтверждения (Two-phase Commit Protocol 2PC). Рассмотрим распределенную транзакцию, предполагающую участие множества процессов, каждый из которых работает на отдельной машине. Если предположить, что ошибки отсутствуют, протокол состоит из следующих двух фаз, каждая из которых включает в себя два шага.

1. Координатор рассылает всем участникам сообщение VOTE_REQUEST.

^ 2. После того как участник получит сообщение VOTE_REQUEST, он возвращает координатору либо сообщение VOTE_COMMIT, указывая, что он готов локально подтвердить свою часть транзакции, либо сообщение VOTE_ABORT в противном случае.

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

4. Каждый из участников, проголосовавших за подтверждение, ожидает итогового решения координатора. Если участник получает сообщение GLOBAL_COMMIT, он локально подтверждает транзакцию. В случае же получения сообщения GLOBAL_ABORT транзакция локально прерывается.

Первая фаза (фаза голосования) состоит из шагов 1 и 2, вторая (фаза решения) — из шагов 3 и 4. Эти четыре шага показаны на диаграмме конечного автомата:



Участник может быть блокирован в состоянии READY, ожидая глобального объявления результатов голосования, рассылаемого координатором.

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

Более правильным решением будет разрешить участнику ^ Р контакт с другим участником, Q, чтобы он мог по текущему состоянию Q решить, что же ему делать дальше. Так, например, пусть Q перешел в состояние COMMIT. Это возможно только в том случае, если координатор до поломки послал Q сообщение GLOBAL_COMMIT. Видимо, до Р это сообщение не дошло. Соответственно, Р теперь может прийти к выводу о необходимости локального подтверждения. Точно так же если Q находится в состоянии ABORT, Р может уверенно прерывать свою часть транзакции.

Теперь предположим, что Q пребывает в состоянии ^ INIT. Такая ситуация может

произойти, если координатор разошлет всем участникам сообщения VOTE_REQUEST и это сообщение дойдет до Р (который ответит на него посылкой сообщения VOTE_COMMIT), но не дойдет до Q. Другими словами, координатор может отказать во время рассылки сообщения VOTE_REQUEST. В этом случае правильно будет прервать транзакцию: и Р, и Q могут осуществить переход в состояние ABORT.

Наиболее сложную ситуацию мы получим, если Q также будет находиться в состоянии READY, ожидая ответа от координатора. Так, если окажется, что все участники находятся в состоянии READY, конкретное решение принять невозможно.

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

Таблица Действия, предпринимаемые участником Р в состоянии READY и контакте с участником Q

^ Состояние участника Q

Действие участника Р

COMMIT

Перейти в состояние COMMIT

ABORT

Перейти в состояние ABORT

INIT

Перейти в состояние ABORT

READY

Связаться с другим участником

Трехфазное подтверждение

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


5-analiz-ustojchivosti-linejnih-asu-konspekt-lekcij-chelyabinsk-2001-senigov-p-n-teoriya-avtomaticheskogo-upravleniya.html
5-antichnij-avtor-knigi-istoriya-nasishennoj-ogromnoj-geograficheskoj-informaciej-gerodot-braziliya.html
5-aprelya-v-1400-informacionnij-byulleten-administracii-sankt-peterburga-12-663-5-aprelya-2010-g.html
5-asinhronnij-format-peredachi-dannih-interfejsi-vichislitelnih-sistem-obshie-polozheniya-sposobi-podklyucheniya.html
5-avangard-i-organizator-parazitizma-v-rossionii-o-tekushem-momente-9-93-dekabr-2009goda-modernizaciya.html
5-avtomat-bezoposnost-instrukciya-po-ekspluatacii-avtokrana.html
  • uchenik.bystrickaya.ru/kuusinen-otto-vilgelmovich.html
  • gramota.bystrickaya.ru/zakonodatelnie-i-inie-normativnie-pravovie-akti-rossijskoj-federacii-prirodnie-resursi-i-okruzhayushaya-sreda-stranica-15.html
  • books.bystrickaya.ru/chast-5-igroki-na-mnogih-rinkah-tom-basso-redaktor-a-dzyura-shzz-shvager-dzh-d-novie-magi-rinka-besedi.html
  • exchangerate.bystrickaya.ru/1-otsutstvie-kakoj-libo-detali-risunka-diagnosticheskaya-programma-po-opredeleniyu-psihologicheskoj-gotovnosti-detej.html
  • school.bystrickaya.ru/242-vliyanie-opticheskih-izluchenij-na-otkormochnie-kachestva-fiziologicheskoe-obosnovanie-primeneniya-opticheskogo.html
  • nauka.bystrickaya.ru/uchebno-metodicheskij-kompleks-disciplini-gse-f-ekonomicheskaya-teoriya-makroekonomika-perehodnaya-ekonomika-kod-i-nazvanie-disciplini-po-uchebnomu-planu-specialnosti.html
  • upbringing.bystrickaya.ru/metodicheskie-rekomendacii-po-vipolneniyu-kursovoj-raboti-po-discipline-metrologiya-standartizaciya-i-sertifikaciya-dlya-studentov-specialnosti-220501-65-upravlenie-kachestvom.html
  • zadachi.bystrickaya.ru/osobennosti-ucheta-malocennih-i-bistroiznashivayushihsya-predmetov-i-ih-iznosa.html
  • occupation.bystrickaya.ru/mirovaya-sistema-standartizacii-obzor.html
  • education.bystrickaya.ru/33-uchenie-o-gosudarstve-i-prave-h-volfa-ne-lekciya-konspekt-kursa-istoriya-politicheskih-i-pravovih-uchenij.html
  • school.bystrickaya.ru/flesh-pamyat-tipi-i-principi.html
  • doklad.bystrickaya.ru/uprazhneniya-po-sisteme-obrabotki-zakazov-na-baze-knigi-uendi-boggs-majkl-boggs.html
  • thescience.bystrickaya.ru/ispanskij-yazik-xvi-xvi-vv-i-ispanskoe-yazikovoe-soznanie-vzaimosvyaz-i-vzaimodejstvie.html
  • ucheba.bystrickaya.ru/praktiki-stranica-15.html
  • writing.bystrickaya.ru/aleksandr-sergeevich-pushkin-2.html
  • pisat.bystrickaya.ru/spravochnoe-posobie-izdatelstvo-energiya-1978-izdatelstvo-radio-i-svyaz-1983-stranica-26.html
  • shpargalka.bystrickaya.ru/uroka-05-03-09-tema-uroka-tverdie-tela-amorfnie-kristalli.html
  • shpargalka.bystrickaya.ru/vakuum-i-subfizicheskaya-forma-materii.html
  • desk.bystrickaya.ru/otveti-na-voprosi-vebinara-1s-kolledzh-obzor-funkcionalnih-vozmozhnostej-redakcii-1-23-marta-2012-goda.html
  • turn.bystrickaya.ru/opredelenie-dlini-svetovoj-volni-s-pomoshyu-difrakcionnoj-reshetki-rukovodstvo-k-vipolneniyu.html
  • lesson.bystrickaya.ru/process-ekspedirovaniya-transportnoj-kompanii-ooo-avelena-logistik-chast-18.html
  • shpargalka.bystrickaya.ru/vi-organizaciya-uchebno-vospitatelnogo-rezhima-postanovlenie-ob-utverzhdenii-i-vnedrenii-gosudarstvennih-sanitarno-epidemiologicheskih.html
  • college.bystrickaya.ru/33-klassifikaciya-struktur-lekciya-2.html
  • znaniya.bystrickaya.ru/razvitie-na-infrastrukturata-i-opazvane-na-okolnata-sreda-obshinski-plan-za-razvitie-2007-2013-g.html
  • kolledzh.bystrickaya.ru/5-teoriya-centralnih-mest-51-obshaya-koncepciya-teorii-centralnih-mest-kurs-lekcij-dlya-zaochnogo-otdeleniya-chelyabinsk-2008.html
  • grade.bystrickaya.ru/obrazovatelnaya-programma-obedineniya-istoki-drevnosti.html
  • grade.bystrickaya.ru/mihail-veller-vse-o-zhizni-stranica-11.html
  • textbook.bystrickaya.ru/kalendar-znamenatelnih-dat-aprelya-2011-goda-informaciya-o-postuplenii-pechatnih-izdanij-v-dumu-astrahanskoj-oblasti.html
  • vospitanie.bystrickaya.ru/zakoni-razvitiya-yazika-stranica-3.html
  • lecture.bystrickaya.ru/6-zadaniya-dlya-samostoyatelnoj-raboti-studentov-uchebno-metodicheskij-kompleks-umk-d-specialnost-080105-finansi-i-kredit.html
  • paragraph.bystrickaya.ru/logicheskomu-razvitiyu-ekonomiki-rossii-ot-31-avgusta-2010-g.html
  • occupation.bystrickaya.ru/mezhdunarodnij-standart-finansovoj-otchetnosti-ias-21.html
  • laboratory.bystrickaya.ru/voennaya-politika-ssha-skvoz-prizmu-filosofii-i-personalij-chast-5.html
  • testyi.bystrickaya.ru/arhivovedenie-kompleksnaya-nauchnaya-disciplina-razrabativayushaya-i-izuchayushaya-teoreticheskie-metodicheskie-i-organizacionnie-voprosi-arhivnogo-dela-kurs-arhivove.html
  • otsenki.bystrickaya.ru/rod-nesklonyaemih-sushestvitelnih-i-metodika-ih-izucheniya.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.