Главная » SQL, Базы данных » ПРОБЛЕМЫ РАСПРЕДЕЛЕННЫХ СИСТЕМ

0

В этом разделе подробно рассматриваются проблемы, которые упоминались в разделе 21.3. Ключевая проблема распределенных систем состоит в том, что коммуникационные сети, по крайней мере, сети, которые охватывают большую  территорию, или глобальные сети, пока остаются медленными. Обычная  глобальная сеть чаще всего имеет среднюю скорость передачи данных от 5 до 10 тысяч байтов в секунду. Обычный же жесткий диск имеет скорость обмена данными около 5—10 миллионов байтов в секунду. (С другой стороны, некоторые локальные сети поддерживают скорость обмена данными того же порядка, что и  диски.) Поэтому основная задача распределенных систем (по меньшей мере, в случае глобальной сети, а также до некоторой степени и в случае локальной сети) — минимизировать использование сетей, т.е. минимизировать количество и объем передаваемых сообщений. Решение этой задачи, в свою очередь, затрудняется изза проблем в нескольких дополнительных областях. Ниже приведен список таких областей, хотя нельзя гарантировать, что он является полным.

■     Обработка запросов.

■     Управление каталогом.

■     Распространение обновлений.

■     Управление восстановлением.

■     Управление параллельностью.

Обработка запросов

Чтобы решить задачу минимизации использования сети, процесс  оптимизации  запросов должен быть распределенным, как и процесс выполнения запросов. Иначе говоря, в общем случае процесс оптимизации будет включать этап глобальной оптимизации, за которым последуют этапы локальной оптимизации на каждом участвующем узле. Например, предположим, что запрос Q передан на  выполнение на узел X, и предположим, что запрос Q требует соединения отношения Ry на узле Y, содержащего 10 тыс. кортежей, с отношением Rz на узле z, содержащим 10 млн. кортежей. Оптимизатор на узле х должен выбрать глобальную стратегию выполнения запроса Q. В данном случае очевидно, что было бы выгоднее переслать отношение Ry на узел Z, а не отношение Rz на узел Y (или, в зависимости от кардинальности результата соединения, может оказаться, что лучше переслать и отношение Ry, и отношение Rz на узел X). Предположим, что решено переслать данные отношения Ry на узел Z, поэтому реальная стратегия выполнения соединения на узле Z будет определяться локальным оптимизатором этого узла.

Приведенная ниже более подробная иллюстрация рассматриваемого подхода основана на примере, взятом из одной из ранних статей Ротни (Rothnie) и Гудмана (Goodman) [21.31].

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

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

■     База данных поставщиков и деталей (упрощенная)

, .,’. S { S#, CITY } 10 000 хранимых кортежей на узле  А  Р  {  Р#,  COLOR  }  100  000  хранимых кортежей на узле В SP { S#, Р# }                                          1 000 000 хранимых кортежей на узле А

Предположим, что каждый хранимый кортеж имеет длину 25 байт (200 бит).

■     Запрос ("Получить номера лондонских поставщиков деталей красного цвета")

( ( S JOIN SP JOIN P ) WHERE CITY = ‘London’ AND

COLOR = COLOR (‘Red’) ) { S# }

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

Количество деталей красного цвета                                                                                                                                                                                                                                                                                                                                   10

Количество поставок, выполненных поставщиками из Лондона 100 000

■     Предполагаемые параметры линий передачи данных

Скорость передачи данных                                                                                                                                                                                                                                                                                                                                50 000 бит/с Задержка доступа                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    0,1 с

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

( общая задержка доступа ) +

( общий объем данных / скорость передачи данных )

В этом случае она сводится к такой формуле (время в секундах):

( количество сообщений / 10 ) + (количество битов / 50000 )

Пересылка записей о деталях на узел А и обработка запроса на узле А.

Т[1] = 0,1 + ( 100000 * 200 ) / 50000

= 400 с (приблизительно 6,67 мин)

Пересылка записей о поставщиках и поставках на узел В и обработка запроса на узле В.

Т[2] = 0,2 + ( ( 10000 + 1000000 ) * 200 ) / 50000 = 4040 с (приблизительно 1,12 ч)

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

Т [ 3 ]  =  20000  с  (приблизительно  5, 5 6  ч)  Сокращение данных о  деталях на узле в для определения только тех деталей, которые имеют красный цвет, а затем для каждой из выбранных деталей проверка на узле А наличия поставок, связывающих эту деталь с поставщиком из Лондона. Каждая из таких проверок требует передачи двух сообщений. Время передачи этих сообщений также будет мало по сравнению с задержкой доступа.

Т [4]   =  2  с  (приблизительно) Соединение отношений поставщиков и поставок на узле А, сокращение результата для получения данных только о  поставщиках из Лондона, получение проекции этих результатов по атрибутам  s# и Р# и пересылка результата на узел в. Завершение обработки на узле в.

Т[5] = 0,1 + ( 100000 * 200 ) / 50000

= 400 с (приблизительно 6,67 мин)

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

Т[6] = 0,1 + ( 10 * 200 ) / 50000 = 0,1 с (приблизительно)

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

Ниже приведены комментарии к этим результатам.

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

■     Скорость обмена данными и задержки доступа — важные факторы в выборе стратегии.

■     Для плохих стратегий время вычислений и ввода—вывода ничтожно мало по срав нению со временем передачи данных.

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

838     Часть V. Дополнительные темы

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

Таблица 21.1. Возможные стратегии распределенной обработки запроса (сводка)

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

Управление каталогом

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

1.  Централизованное хранение. Единственный общий каталог хранится на отдельном центральном узле.

2.  Полная репликация. Общий каталог целиком хранится на каждом узле.

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

4.  Сочетание подходов 1 и 3. На каждом узле поддерживается свой локальный каталог, как предусмотрено в подходе 3. Кроме того, отдельный центральный узел сопро вождает объединенную копию всех этих локальных каталогов, как предусмотрено в подходе 1.

Каждый подход имеет свои недостатки. При подходе 1 очевидно нарушается принцип "отсутствия  зависимости от центрального узла". При подходе 2 в  значительной мере утрачивается независимость узлов, поскольку всякое  обновление каталога должно распространяться на каждый узел. При подходе 3 нелокальные операции становятся слишком дорогостоящими (для поиска удаленного объекта требуется доступ в среднем к половине всех узлов). Подход 4  более эффективен по сравнению с подходом 3 (для поиска удаленного объекта требуется доступ лишь к одному удаленному каталогу), но в этом случае вновь нарушается принцип отсутствия зависимости от центрального узла. Поэтому

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

В качестве примера рассмотрим подход, который применяется в системе R* [21.37].

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

это вообще очень важный вопрос для распределенных систем. Поскольку два отдельных узла X и У могут иметь объект (скажем, базовую переменную отношения) с одним и тем же именем, допустим, R, требуется некоторый механизм (обычно — уточнение с помощью имени узла) для того, чтобы устранить неоднозначность, т.е. гарантировать  уникальность имени в пределах всей системы. Но, если уточненные имена, такие как Х.R и

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

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

для этих же объектов. Общесистемные имена имеют четыре описанных ниже компонента.

■     Идентификатор создателя, т.е. идентификатор пользователя, который впервые вызвал на выполнению операцию CREATE для создания рассматриваемого объекта.

■     Идентификатор узла создателя, т.е. идентификатор узла, на котором была введена соответствующая операция CREATE.

■     Локальное имя, т.е. неуточненное имя объекта.

■     Идентификатор узла происхождения, т.е. идентификатор узла, на котором объект хранился первоначально.

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

MARILYN @ NEWYORK . STATS @ LONDON

Оно обозначает объект (для определенности будем считать, что это — базовая переменная отношения) с локальным именем STATS, созданный пользователем MARILYN на  узле  в  Нью-Йорке  и  первоначально  сохраненный  на  узле  в  Лондоне3.  Это  имя гарантированно защищено от каких-либо изменений, даже если объект в дальнейшем будет перемещен на другой узел (см. ниже).

Как уже указывалось, пользователи обычно ссылаются на объекты с помощью вводимых имен. Вводимое имя, как показано ниже, представляет собой простое, неуточненное имя — либо компонент "локальное имя" общесистемного имени (в приведенном выше примере — STATS), либо синоним для этого общесистемного имени, который в системе R* определяется с помощью специального оператора CREATE SYNONYM.

CREATE SYNONYM MSTATS FOR MARILYN @ NEWYORK . STATS @ LONDON ;

3  В системе R* базовые переменные отношения отображаются непосредственно на хранимые  переменные отношения. А фактически такой подход применяется почти во всех системах, известных автору. Некоторые критические замечания по поводу указанного состояния дел приведены в приложении А.

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

SELECT … FROM STATS … ; SELECT … FROM MSTATS … ;

В первом случае, т.е. при использовании локального имени, система будет исходить из того, что все компоненты общесистемного имени определяются по  умолчанию, а именно — что объект создан данным пользователем, создан на данном узле и сохранен на данном узле. Кстати, благодаря такому допущению по  умолчанию старые приложения системы System R могут выполняться без каких-либо исправлений в новой версии системы R* (т.е. после переопределения данных системы System R для системы R*).

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

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

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

2.          Запись каталога для каждого объекта, хранимого в настоящее время на данном узле.

Предположим теперь, что пользователь выдал запрос, содержащий ссылку на синоним MSTATS. Сначала система выполнит поиск соответствующего общесистемного имени в соответствующей таблице синонимов (исключительно локальный просмотр). После того как станет известен узел создания (в нашем примере это узел в Лондоне), можно будет опросить каталог узла в Лондоне (здесь мы для общности подразумеваем удаленный просмотр — первое удаленное обращение). Каталог узла из Лондона будет содержать запись для объекта в соответствии с п. 1. Если объект по-прежнему хранится на узле в Лондоне, он  будет найден. Однако, если объект перемещен, скажем, на узел в ЛосАнджелесе, запись каталога на узле в Лондоне будет содержать сведения об этом и система должна будет опросить каталог на узле в Лос-Анджелесе (второе удаленное обращение). Каталог на узле в Лос-Анджелесе будет содержать запись для искомого объекта согласно п. 2. Таким образом, для поиска объекта будет выполнено не больше двух удаленных обращений.

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

■     Вставка записи в каталог на узле в Сан-Франциско.

■     Удаление записи из каталога на узле в Лос-Анджелесе.

■     Обновление записи каталога на узле в Лондоне, который теперь будет указывать на узел в Сан-Франциско вместо узла в Лос-Анджелесе.

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

Отметим, что схема идентификации объектов, которая используется в распределенной СУБД DB2, хотя и подобна описанной выше, совпадает с ней не полностью.

Распространение обновлений

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

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

■     Одна копия для каждого реплицируемого объекта устанавливается как первичная

копия, а все оставшиеся копии — как вторичные.

■     Первичные копии различных объектов находятся на различных узлах (поэтому данная схема также является распределенной).

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

■     Примечание. Это последующее время, тем не менее, должно предшествовать опера ции завершения транзакции COMMIT, если должны гарантироваться свойства ACID распределенных транзакций (см. главы 15 и 16). Дополнительные замечания по этому вопросу будут приведены ниже.

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

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

отпечаток свойств этих продуктов, в результате чего, по крайней мере, на коммерческом рынке, под ним почти всегда подразумевается, что распространение обновлений откладывается до тех пор, пока соответствующая транзакция не  завершится (например, см. [21.1], [21.16] и [21.18]). Недостаток подобного подхода с задержкой распространения обновлений заключается, безусловно, в том, что база данных не может больше гарантировать согласованности всех ее данных в любой момент4. В действительности, пользователь даже может не знать, согласована ли база данных.

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

1.  Концепция репликации в системе с задержкой распространения обновлений мо жет рассматриваться как применение идеи снимков, речь о которых шла в главе 10. На самом деле, для обозначения такого вида репликации лучше было бы исполь зовать другой термин. Тогда можно было бы сохранить термин реплика для обо значения того, что понимается под ним в обычном смысле (а именно — точная копия). Но следует отметить, что снимки рассматриваются как предназначенные только для чтения (не считая их периодического обновления), тогда как некото рые системы позволяют пользователям обновлять такие реплики непосредственно (см. [21.18]). Безусловно, последний вариант представляет собой нарушение прин ципа независимости от репликации.

2.  Мы не утверждаем, что задержка распространения обновлений — плохая идея.

Это — очевидно самое лучшее, что можно было сделать при определенных обстоя тельствах, как мы убедимся, например, в главе 22. Суть в том, что задержка рас пространения подразумевает, что "реплики" — не настоящие реплики (поскольку возможно, что любое конкретное значение данных на логическом уровне будет представлено с помощью двух или большего количества хранимых значений на физическом уровне, более того, что эти хранимые значения будут разными!), а система — не настоящая распределенная система баз данных.

3.  Одна из причин (может быть, даже главная причина), по которой репликация в коммерческих продуктах реализована с задержкой распространения, заключает ся в следующем: альтернатива, т.е. обновление всех дубликатов перед выполне нием операции COMMIT, требует поддержки двухфазной фиксации транзакции (см. следующий подраздел), что может существенно повлиять на производитель ность системы. Именно по этой причине в компьютерных журналах иногда встре чаются статьи с озадачивающими названиями, такими как "Репликация или двух фазная фиксация?" (озадачивающими, поскольку в них фактически сравниваются характеристики двух принципиально различных подходов).

4  Безусловно, если все операции проверки целостности выполняются немедленно (см. главы 9 и 16), то такие ситуации становятся невозможными. И даже если такая проверка откладывается до этапа вызова оператора COMMIT (а такой подход рассматривается нами как логически  неправильный, но применяется во многих системах), подобные ситуации не могут возникнуть. Поэтому, в определенном смысле, отложенное распространение можно рассматривать как "еще  более логически неправильный подход", чем отложенную проверку (если только можно  рассуждать в терминах "более" или "менее" неправильного).

Управление восстановлением

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

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

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

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

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

Рассмотрим повторно процесс двухфазной фиксации транзакций, описанный ранее, в главе 15. Обратимся к рис. 21.4, на котором показано взаимодействие между координатором и обычным участником. Для общности предположим, что  координатор и участник находятся на разных узлах, кроме того, на данном рисунке ось времени направлена слева направо (но иногда временная последовательность нарушается!). К тому же для упрощения предположим, что в транзакции  затребовано выполнение операции COMMIT, а не ROLLBACK. После получения запроса на операцию COMMIT координатор организует следующий описанный ниже двухфазный процесс.

■   Каждому участнику координатор отдает распоряжение "приготовиться к фиксации или откату" транзакции. На рис. 21.4 показано сообщение  "приготовиться", отправленное в момент t1 и полученное участником в момент t2. Далее участник принудительно помещает запись в журнал  локального агента из своего физического журнала, а затем выдает  координатору подтверждение "ОК". Безусловно, если возникнет какая-либо ошибка (в частности, если произойдет сбой в работе локального агента), будет передано сообщение "Not OK". На рисунке это сообщение, которое для простоты обозначено как "ОК", отправлено в момент t3 и получено координатором в момент t4. Как уже отмечалось выше, участник теперь теряет автономность: он должен делать то, что ему будет предписывать координатор. Кроме того, любые ресурсы, которые заблокированы локальным агентом, должны оставаться заблокированными до тех пор, пока участник не получит и не выполнит распоряжение координатора.

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

■  Будем считать, что было принято решение о фиксации транзакции. В этом случае координатор отдаст распоряжение всем участникам "выполнить",  т.е. запустить обработку операции фиксации для локального агента. На рис. 21.4 показано сообщение "выполнить", отправленное в момент t6 и  полученное участником в момент t7. Участник выполняет операцию фиксации для локального агента и отправляет подтверждение  "выполнено"  координатору. На рисунке подтверждение отправлено координатору в момент t8 и получено координатором в момент t9.

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

Рис. 21.4. Двухфазная фиксация транзакции

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

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

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

■     Во-первых, как было отмечено в аннотации к [15.6], если агент на некотором кон кретном узле участника выполняет операции только чтения, такой участник при завершении первой фазы процесса может ответить "игнорируйте мое присутст вие" и координатор действительно может игнорировать такого участника во вто рой фазе процесса.

■     Во-вторых (и это указано в аннотации к [15.6]), если все участники в первой фазе процесса ответят "игнорируйте мое присутствие", вторая фаза может быть полно стью пропущена.

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

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

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

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

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

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

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

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

времени  написания  данной  книги  схема  предполагаемого  отката  стала  фактическим

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

Управление параллельностью

Как указано в разделе 21.3, управление параллельным доступом в большинстве распределенных систем строится на использовании механизма блокировки, т.е. точно так, как и в большинстве нераспределенных систем. Однако в распределенных системах запросы на проверку, установку и отмену блокировки становятся сообщениями (если считать, что рассматриваемый объект расположен на удаленном узле), а сообщения создают дополнительные издержки. Рассмотрим, например, транзакцию т обновления объекта, для которого существуют дубликаты на п удаленных узлах. Если каждый узел отвечает за блокировку объектов, которые  на нем хранятся (как предполагается в соответствии с принципом локальной независимости), то непосредственная реализация будет требовать по крайней мере 5л таких сообщений:

■     n запросов на блокировку;

■     n разрешений на блокировку;

■     n сообщений об обновлении;

■     n подтверждений;

■     n запросов на снятие блокировки.

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

Для решения проблемы обычно выбирается стратегия первичной копии,  описанная выше, в подразделе "Распространение обновлений". Для данного объекта А все операции

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

узлах). При использовании этой стратегии набор всех копий объекта с точки зрения блокировки можно рассматривать как единый объект, а общее количество сообщений будет сокращено  с 5л до 2л+3  (один запрос блокировки, одно  разрешение  блокировки,  л

обновлений, л подтверждений и один запрос на снятие блокировки). Но обратите внимание на то, что это решение влечет за собой серьезную потерю независимости — транзакция может теперь не завершиться, если первичная копия окажется недоступной, даже

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

есть нежелательный побочный эффект — снижение уровня производительности и  доступности как для выборки, так и для обновления.)

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

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

1.  Агент транзакции Т2 на узле х ожидает, пока агент транзакции Т1 на узле х осво бодит блокировку.

2.  Агент транзакции т1 на узле X ожидает, пока агент транзакции Т1 на узле Y завер шит транзакцию.

3.  Агент транзакции Т1 на узле Y ожидает, пока агент транзакции Т2 на узле У осво бодит блокировку.

4.  Агент транзакции Т2 на узле Y ожидает, пока агент транзакции Т2 на узле X завер шит транзакцию. Налицо явная взаимоблокировка!

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

Изящная (и распределенная) схема для определения состояния глобальной  блокировки описана в статьях о системе R* (например, [21.37]).

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

Рис. 21.5. Пример состояния глобальной взаимоблокировки

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии