16. Модели непротиворечивости, ориентированные на данные

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

Строгая непротиворечивость

Наиболее жесткая модель непротиворечивости называется строгой непротиворечивостью (strict consistency). Она определяется следующим условием: всякое чтение элемента данных х возвращает значение, соответствующее результату последней записи X. Это определение естественно и очевидно, хотя косвенным образом подразумевает существование абсолютного глобального времени (как в классической физике), в котором определение «последней» однозначно. Однопроцессорные системы традиционно соблюдают строгую непротиворечивость, и программисты таких систем склонны рассматривать такое поведение, как естественное.

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

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

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

17. Понятия отказоустойчивость и надёжная связь

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

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

включая: доступность (availability); безотказность (reliability); безопасность (safety); ремонтопригодность (maintainability).

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

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

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

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

Говорят, что система отказывает (fail), если она не в состоянии выполнять свою работу. Построение надежных систем тесно связано с управлением отказами. Управление в данном случае означает нечто среднее между предотвращением, исправлением и предсказанием отказов. Для нашей цели наиболее важным вопросом является отказоустойчивость (fault tolerance),

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

Отказы обычно подразделяются на проходные, перемежающиеся и постоянные. Проходные отказы (transient faults) происходят однократно и больше не повторяются. Перемежающиеся отказы (intermittent faults) появляются и пропадают, «когда захотят», а потом появляются снова и т. д. Постоянные отказы (permanent faults) —это отказы, которые продолжают свое существование до тех пор, пока отказавший компонент не будет заменен.

Надежная связь

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

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

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

Восстановление

Основа отказоустойчивости исправление после ошибок. Основная идея механизма исправления ошибок состоит в замене ошибочного состояния безошибочным. Существует два основных способа восстановления после ошибок. При обратном исправлении (backward recovery) основная задача состоит в возвращении системы из текущего ошибочного состояния к предыдущему безошибочному состоянию. Чтобы сделать это, необходимо время от времени записывать состояние системы и восстанавливать ее в предыдущем состоянии, еслид ело пойдет плохо. При каждой записи текущего состояния системы (или его части) говорят, что создается контрольная точка (checkpoint). Другой вариант исправления ошибок —прямое исправление (fonoard recovery). В этом случае при входе системы в ошибочное состояние вместо отката назад, к предыдущей контрольной точке, делается попытка перевести систему в новое корректное состояние, в котором она могла бы продолжать работатьОбщие вопросы защиты в распределённых системах

18. Контроль доступа в распределённых системах