Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

5.6. Распределенные транзакции 321

ку. После того как блокировка установлена, менеджер транзакций работает не-

посредственно с менеджерами данных. Отметим, что при такой схеме элементы

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

ния операции менеджер транзакций возвращает блокировку менеджеру блоки-

ровок.

При первичной двухфазной блокировке {primary two-phase locking) с каждого

элемента данных делается первичная копия. Блокировки устанавливает и сни-

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

вичная двухфазная блокировка работает практически так же, как и централи-

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

нескольким машинам.

И, наконец, при

распределенной

двухфазной

блокировке {distributed

two-phase

locking)

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

шинам. В противоположность первичной и централизованной двухфазной бло-

кировке планировщики каждой из машин отвечают не только за установку и сня-

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

этом смысле распределенная двухфазная блокировка значительно ближе к ба-

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

содержащих данные.

Классическое исследование двухфазной блокировки для систем баз данных

вообще управления параллельным выполнением можно найти в [47].

Пессимистическое упорядочение по отметкам времени

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

том,

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

времени ts{T). Используя алгоритм Лампорта, мы можем убедиться в уникально-

сти отметок времени, что в данном случае необходима. Каждая операция, являю-

щаяся частью транзакции Г, также получает отметку времени ts{T). Кроме того,

каждый элемент данных х в системе получает отметку времени чтения Z^SRD(X)

отметку времени записи

ts^^Y(i^)•

Отметка времени чтения соответствует отмет-

ке

времени транзакции, которая последней считывала

х,

а отметка времени запи-

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

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

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

шей отметкой.

Теперь представим себе, что планировщик получает от транзакции Т

отмет-

кой времени ts операцию read{T,x), причем ts<tSwR{x). Другими словами, он

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

выполнения Т. В этом случае транзакция Т просто прерывается. С другой сторо-

ны,

если ts

tswR{x),

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

образом. Кроме того, ^RD(^) устанавливается в значение

max{ts,

^5RD(^:)}.

Точно таким же образом обстоит дело и при получении планировщиком от

транзакции Г

отметкой времени ts операции записи write{T,x). Если ts< tSRD(x),

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

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

322 Глава 5. Синхронизация

С другой стороны, если ts

tSYcoipc),

то, поскольку никакая предыдущая транзак-

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

^WRW устанавливается в

max{ts,

^5WR(^)}.

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

смотрим следующий пример. Представим себе три транзакции, Ти Тг и Гз. Тран-

закция Т\ отработала уже давно и использовала все элементы данных, необходи-

мые транзакциям

Т2

и Гз, так что на всех этих элементах стоят отметки времени

чтения и записи ts{T\). Транзакции

Т2

и Гз начинаются параллельно с отметками

^5(Г2)<^(Гз).

Рассмотрим сначала чтение транзакцией Гг элемента данных х. Пока транзак-

ция Гз не подтверждена, обе отметки,

15л^к{х)

1зш^{х),

будут иметь значение

ts{T\),

которое меньше, чем ts(T2). На рис. 5.23, аи б мы видим, что ts(T2) боль-

ше,

чем tswR(x) и ^5RD(X), так что запись допустима и будет предварительно вы-

полнена (транзакция Гз еще не подтверждена). Она станет постоянной после за-

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

отметка времени транзакции Гг.

tSRD(x)

|(Ti)

tSwR(x)

1з(Т2)

|(Tl) |(Т2)

Время

tSwR(x)

|(Ti)

tSRD(x) 1з(Т2)

к) к)

Время'

'SWRM

|(Ti)

ts(T2)

|(Т2)

Пробная

запись

^ Время

tSwR(x)

tstent(x) ts(T2)

|(Ti)

|(Тз) |(Т2)

Время

•

ts(T2)

tSRD(x)

h) |(Тз)

Время

—I

ts(T2)

tSwR(x)

k) |(Тз)

Прерывание

Время

•

ts(T2) tSwR(x)

b) |(Тз)

Время

—•

1з(Т2)

tstent(x)

b) |(Тз)

Время

Прерывание

Рис.

5.23. Управление параллельным выполнением транзакций

использованием отметок времени

На рис. 5.23, виг транзакции Г2 не везет. Транзакция Гз производит чтение

(рис.

5.23, в) или запись (рис. 5.23, г) хи подтверждается. Транзакция

Г2

преры-

вается. Однако она может получить новую отметку времени и стартовать снова.

Рассмотрим теперь чтение. На рис. 5.23, д конфликтов нет, и чтение может

быть произведено немедленно. На рис. 5.23, е в середину встревает какой-то без-

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

и поэтому

Г2

просто дожидается, пока тот завершится, после чего считывает но-

вый файл и продолжает работу.

5.6. Распределенные транзакции 323

На рис. 5.23, ж транзакция 7з изменяет значение х и вновь подтверждается.

транзакции Гг снова приходится прерываться. На рис. 5.23, з транзакция Гз на-

ходится в процессе изменения х до тех пор, пока не подтверждается. Транзакция

Т2

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

Свойства отметок времени и блокировки различны. Когда транзакция стал-

кивается с большими (устаревшими) отметками времени, она прерывается, бло-

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

немедленно. С другой стороны, при работе с отметками времени не бывает взаим-

ных блокировок, а это большой плюс.

Базовое упорядочение при помойки отметок времени существует в несколь-

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

говариантное упорядочение. Подробности можно найти в [177, 337].

Оптимистическое упорядочение

по отметкам времени

Третий подход к выполнению нескольких транзакций в одно и то же время

—

это

оптимистическое упорядочение по отметкам времени

[244].

Идея, лежащая в ос-

нове этого подхода, удивительно проста: идите вперед и делайте то, что вы хоти-

те,

не обращая внимания на то, что одновременно происходит что-то еще. Если

возникнут проблемы, волноваться об этом мы будем после (этот алгоритм ис-

пользуют также многие политики). На практике конфликты относительно редки,

так что большую часть времени все идет гладко.

Конфликты могут быть нечастыми, но они все же случаются, и нам необхо-

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

ния и записи элементов данных. В момент подтверждения транзакции проверя-

ется, не был ли с момента ее начала изменен какой-то элемент данных, нужный

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

ция подтверждается.

Оптимистическое управление параллельным выполнением транзакций отлич-

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

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

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

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

Большое преимущество оптимистического управления параллельным выпол-

нением транзакций состоит в том, что при его использовании достигается макси-

мальный параллелизм и не бывает взаимных блокировок, поскольку никакой

процесс никогда не ждет завершения блокировки. Недостаток такого управле-

ния в том, что временами оно дает сбой, и нам приходится начинать транзакцию

снова. В условиях высокой загрузки вероятность сбоев может существенно воз-

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

Как указывалось в

[337],

исследования оптимистического управления парал-

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

распределенных системах. Кроме того, создание коммерческих систем и прото-

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

другими.

324 Глава 5. Синхронизация

5.7- Итоги

с взаимодействием между процессами тесно связан вопрос синхронизации про-

цессов в распределенных системах. Синхронизация

—

это все то, что позволяет

нам делать правильные вещи в правильное время. Проблема распределенных сис-

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

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

личных машинах имеют свое собственное мнение о времени.

Существуют различные способы синхронизации часов в распределенных сис-

темах, но все они основаны на обмене показаниями часов, а это требует учиты-

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

хронизации в значительной мере определяют вариации в задержках доступа и

способы учета этих вариаций.

Во многих случаях знания абсолютного времени не требуется. Достаточно,

чтобы соответствующие события в различных процессах происходили в пра-

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

часов, можно заставить набор процессов соблюдать общее соглашение относи-

тельно правильной очередности событий. В сущности, каждое событие е, такое

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

кую отметку времени С{е), такую, что если событие а происходит раньше 6, то

С{а) <

С(Ь).

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

отметок времени: если С(а) <

С(Ь),

то мы всегда знаем, что событие а причинно

предшествует событию Ь.

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

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

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

низации всех процессов так, чтобы каждый из них определил и сохранил свое

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

Сама по себе синхронизация может быть выполнена без остановки процессов

и записи их состояния. Вместо этого в ходе работы распределенной системы

с нее можно сделать мгновенный слепок

—

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

Синхронизация между процессами часто требует, чтобы один из процессов

выступал в роли координатора. В этом случае если координатор не фиксирован,

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

торый из них будет координатором. Это решение принимается посредством ал-

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

сбое или отключении существовавшего координатора.

Важный класс алгоритмов синхронизации

—

распределенные взаимные ис-

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

доступ к совместно используемым ресурсам имеет максимум один процесс. Рас-

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

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

распределенные алгоритмы, но их минус

—

чересчур большая чувствительность

к сбоям процессов и связи.

5.7. Итоги 325

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

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

при этом вся транзакция целиком либо полностью выполняется, либо полностью

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

менно, при этом результат оказывается таким, как если бы эти транзакции вы-

полнялись в некоторой заданной очередности. И наконец, транзакции долговеч-

ны,

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

Вопросы и задания

Назовите как минимум три источника задержек между радиостанцией WWV,

которая рассылает сигналы точного времени, и процессором в распределен-

ной системе, устанавливающим свои внутренние часы.

Рассмотрим поведение двух машин в распределенной системе. Обе они име-

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

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

всего 990 раз в миллисекунду. Если поправки UTC приходят раз в минуту,

какое максимальное расхождение может возникнуть между часами?

Добавьте к рис. 5.7 новое сообш;ение одновременно с сообщением А так, что-

бы ни до сообщения Л, ни после него ничего не происходило.

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

полностью упорядоченной групповой рассылки с отметки времени по Лам-

порту?

Рассмотрим коммуникационный уровень, в котором сообщения доставляют-

ся в том же порядке, в котором они были отправлены. Приведите пример, ко-

гда даже такое упорядочение излишне строго.

6. Представьте себе, что два процесса одновременно обнаруживают передачу ко-

ординатора и решают провести голосование по алгоритму забияки. Что прои-

зойдет в этом случае?

На рис. 5.12 мы видим два одновременно курсирующих сообщения ГОЛО-

СОВАНИЕ.

Хотя мы не испытываем проблем с тем, что их два, было бы сим-

патичнее убрать одно из них. Придумайте алгоритм, который делал бы это, не

оказывая влияния на основной алгоритм голосования.

8. Многие распределенные алгоритмы требуют наличия координирующего про-

цесса. В какой степени такие алгоритмы могут считаться распределенными?

9. При централизованном подходе к взаимным исключениям (см. рис. 5.13) по-

сле получения сообщения от процесса о том, что он не нуждается больше

в исключительном доступе к критической области, которую использовал, ко-

ординатор обычно разрешает доступ первому процессу в очереди. Приведите

другой возможный алгоритм работы координатора.

10.

Рассмотрим снова рис. 5.13. Представьте себе, что координатор стал неактив-

ным. Обязательно ли это приведет к сбою системы? Если нет, при каких

326 Глава 5. Синхронизация

условиях это произойдет? Существует ли способ решить проблему и сделать

систему устойчивой к потере координатора?

И. Алгоритм, предложенный в

[380],

имеет недостаток. Если в процессе возни-

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

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

тупа. Мы предложили, чтобы ответ на все запросы приходил немедленно, да-

бы проще было обнаружить сбойные процессы. Существуют ли такие усло-

вия, при которых этот метод окажется неприемлемым?

12.

Как изменяться элементы в табл. 5.1, если мы предположим, что алгоритмы

реализуются в локальной сети, которая поддерживает аппаратную широкове-

щательную рассылку?

13.

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

областей. Представим себе, что процесс

хочет войти в критическую область А,

а процесс 1 хочет войти в критическую область В. Приведет ли использова-

ние алгоритма, предложенного в

[380],

к взаимной блокировке? Поясните свой

ответ.

14.

Рассматривая рис. 5.16, мы говорили об атомарном обновлении списка това-

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

на простоту эмуляции магнитных лент при помощи диска (в качестве файла),

этот способ все же не используется?

15.

В табл. 5.3 представлены три плана, два приемлемых и один неприемлемый.

Для этих же транзакций (см. листинг 5.4) создайте полный список значений х,

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

а какие нет.

16.

Когда для реализации транзакций над файлами используется закрытое рабо-

чее пространство, может случиться так, что в родительское рабочее простран-

ство придется копировать большое количество индексов файлов. Как это сде-

лать,

не вводя условий гонок?

17.

Приведите полный алгоритм попытки блокирования файла с успешным и не-

успешным результатами. Рассмотрите блокировку на чтение и на запись,

а также возможность файла быть в момент попытки неблокированным, забло-

кированным на чтение, заблокированным на запись.

18.

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

нением транзакций, обычно отличают блокировку на чтение от блокировки

на запись. Что произойдет, если процесс всегда устанавливал блокировку на

чтение, а теперь хочет заменить ее блокировкой на запись? Что произойдет

в случае замены блокировки на запись блокировкой на чтение?

19.

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

предположим, что операция записи wnte(Ti,x) может быть передана менеджеру

данных, поскольку единственная грозящая конфликтом операция wnte(T2,x)

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

повторно передать операцию write(Ti,x) менеджеру данных после заверше-

ния транзакции Гг?

5.7. Итоги 327

20.

Является ли оптимистическое управление параллельным выполнением тран-

закций более (или менее) строгим, чем использование отметок времени? По-

чему?

21.

Гарантирует ли использование отметок времени в управлении параллельным

выполнением транзакций сериализуемость процесса? Почему?

22.

Мы много раз говорили, что в случае прерывания транзакции мир возвраща-

ется в свое первоначальное состояние, как если бы никакой транзакции не

было.

Мы лгали. Приведите пример, когда вернуть мир в исходное состояние

невозможно.

Глава 6

Непротиворечивость

и репликация

6.1.

Обзор

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

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

на

клиента

6.4. Протоколы распределения

6.5. Протоколы непротиворечивости

6.6. Примеры

6.7. Итоги

Важным вопросом для распределенных систем является репликация данных. Дан-

ные обычно реплицируются для повышения надежности и увеличения произво-

дительности. Одна из основных проблем при этом

—

сохранение непротиворечи-

вости реплик. Говоря менее формально, это означает, что если в одну из копий

вносятся изменения, то нам необходимо обеспечить, чтобы эти изменения были

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

этой

главе мы детально рассмотрим, что в действительности означает непротиворечи-

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

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

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

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

в настоящее время растет.

Чтобы добиться высокой производительности в операциях с совместно ис-

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

шое внимание различным моделям непротиворечивости данных в распределенных

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

для различных типов распределенных систем, детально рассматриваются в этой

главе.

Реализация моделей непротиворечивости разделяемой памяти для крупно-

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

6.1.

Обзор 329

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

сложно реализовать. Один из конкретных классов подобных моделей

—

клиент-

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

с точки зрения одного (возможно, мобильного) клиента. Клиентские модели не-

противоречивости рассматриваются в отдельном разделе.

Непротиворечивость

—

это еще не все. Мы должны также обсудить, как эта

непротиворечивость реализуется на практике. В поддержании непротиворечиво-

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

них

—

это реальное распространение обновлений. Сюда входят вопросы разме-

щения реплик и того, как по ним расходятся обновления. Мы опишем и сравним

несколько протоколов распространения.

Второй аспект касается поддержания непротиворечивости реплик. В боль-

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

Говоря неформально, это означает, что обновления должны расходиться по реп-

ликам более или менее быстро. Существует несколько альтернативных реали-

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

разделе. Кроме того, внимание уделяется протоколам кэширования, представляю-

щими собой особую форму протоколов поддержания непротиворечивости.

Мы закончим эту главу двумя примерами приложений, в которых активно

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

области параллельного программирования и упомиршется также при обсужде-

нии распределенных систем на базе объектов в главе 9. Второй пример охваты-

вает вопросы причинной непротиворечивости и того, что называется медленной

репликацией.

6.1.

Обзор

Этот раздел мы начнем с разговора об основных доводах в пользу репликации

данных. Специальное внимание будет уделено реплицируемым объектам, к кото-

рым в современных распределенных системах проявляется все больший интерес.

И наконец, мы обсудим репликацию, как метод улучшения масштабируемости,

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

6.1.1.

Доводы в пользу репликации

в пользу репликации есть два основных довода ~ надежность и производитель-

ность. Во-первых, данные реплицируются для повышения надежности системы.

Если файловая система реплицирована, она может продолжать свою работу по-

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

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

себе,

что существует три копии некоего файла и операции чтения и записи произ-

водятся со всеми тремя. Мы можем защитить себя от единичной неудачной опе-

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

копии.

330 Глава 6. Непротиворечивость и репликация

Другой довод в пользу репликации данных

—

производительность. Реплика-

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

масштабировать на множество машин и географических зон. Масштабирование

на множество машин имеет место, например, когда возрастает число процессов,

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

производительность можно повысить путем репликации сервера с последующим

разделением общего объема работы между сервером и репликами. Мы уже при-

водили этот пример в главе 1, когда кратко рассматривали кластеры реплициро-

ванных web-серверов.

При масштабировании на увеличившуюся географическую зону мы также нуж-

даемся в репликации. Основная идея состоит в помещении копии данных побли-

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

В результате наблюдаемая производительность процесса возрастает. Этот при-

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

благодаря репликации, оценить не просто. Хотя в клиентском процессе может

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

временного обновления всех реплик потребуется увеличение пропускной спо-

собности сети. Мы вернемся к этой теме при обсуждении протоколов распро-

странения.

Если репликация помогает повысить надежность и производительность, что

нам может помешать? К сожалению, это цена, которую нам придется заплатить

за репликацию данных. Проблема репликации в том, что наличие множества ко-

пий может создать проблемы с непротиворечивостью данных. Каждый раз при

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

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

остальные копии. То, как и когда следует переносить эти изменения, и определя-

ет цену репликации.

Чтобы разобраться в проблеме, рассмотрим постоянно растущее время досту-

па к web-страницам. Если не предпринимать никаких специальных мер, загрузка

страницы с удаленного web-сервера может занимать до нескольких секунд. Для

повышения производительности web-браузеры часто локально сохраняют копии

загруженных ранее web-страниц (то есть

кэшируют

web-страницы). Если поль-

зователь снова запросит подобную страницу, браузер автоматически вернет ему

локальную копию. Скорость доступа, с точки зрения пользователя, будет потря-

сающая. Однако, если пользователь всегда хочет иметь последнюю версию стра-

ницы, его может постичь разочарование. Проблема состоит в том, что если в про-

межутке между обращениями страница будет модифицирована, модификации не

распространяться на копии в кэше, что сделает эти копии устаревшими.

Одно из решений проблемы возвращения пользователю актуальных копий

состоит в том, чтобы запретить браузеру хранить локальные копии, а задачу об-

новления полностью возложить на сервер. Однако это решение может приве-

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

Другое решение

—

позволить web-серверу объявлять кэшированные копии уста-

ревшими или обновлять их, но тогда серверу придется проверять все кэширован-

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