Е. Б. Замятина Распределенные системы и алгоритмы Курс лекций

Вид материала

Курс лекций

Содержание Лекция 11. Распределенное хранение информации Исполнители алгоритма Операции, выполняемые менеджерами Схемы владения данными в распределенной БД

Подобный материал:

• Века. Вопросы к семинарам и диспутам. Часть вторая е. И. Замятин. Роман-антиутопия, 78.14kb.
• С. В. Лапина Социология Курс лекций, 2085.17kb.
• Е. В. Беляева Этика Курс лекций, 693.52kb.
• С. В. Лапина Культурология Курс лекций, 3263kb.
• О. В. Свидерская Основы энергосбережения Курс лекций, 2953.76kb.
• С. М. Забелов > П. С. Забелов Административное право Курс лекций, 3268.19kb.
• И. М. Вашко Организация и охрана труда Курс лекций, 2301.17kb.
• И. М. Вашко Организация и охрана труда Курс лекций, 2301.24kb.
• Курс лекций для студентов заочного факультета самара, 1339.16kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.

Лекция 11. Распределенное хранение информации

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

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

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

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

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

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

Для управления распределенной базой данных создается программный комплекс – система управления распределенной базой данных (СУРБД).

C. J. Date в 1987 году сформулировал один основной принцип и двенадцать правил, которым, по его мнению, должны следовать распределенные базы данных.

Основной принцип заключается в «прозрачности распределенности». С точки зрения пользователя информации распределенная БД не должна отличаться от локальной БД. Здесь имеется в виду пользователь, формулирующий запросы к базе данных и получающий результаты на своем экране (или принтере). Технология его работы не должна зависеть от того, в какой конкретной базе (на каком сайте) находятся нужные ему данные: в его локальной базе, в удаленной базе, все необходимые данные в одной и той же базе или в различных базах данных.

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

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

Третье правило – непрерывность работы. Реконфигурация системы (добавление и удаление локальных сайтов) не должна требовать остановки работы распределенной БД.

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

Седьмое правило касается распределенных запросов. Если выполнение запроса данных требует поиска данных не в одной локальной БД, а в нескольких локальных БД, то к этому не должно быть никаких препятствий.

Восьмое правило. Система должна поддерживать выполнение транзакций с сохранением их основных свойств: атомарности, согласованности, изолированности и продолжительности.

Правила девять – двенадцать декларируют независимость работы распределенной БД от аппаратного обеспечения, операционной системы, сетевой архитектуры и от типов СУБД, управляющих локальными базами. Последнее подразумевает, что локальные БД могут быть построены на основе различных моделей данных и с использованием различных типов СУБД, а СУРБД должна работать «поверх» этих СУБД.

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

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

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

Фрагментация

Реляционные базы данных хранят отношения – таблицы, состоящие из строк и столбцов. Строка отношения называется кортежем и представляет собой запись (record в смысле языка программирования, например, Pascal) о какой-либо сущности предметной области.

Таб.№	Фамилия	Имя	Отчество	Год рождения
А5	Соловьев	Александр	Александрович	1980
Д16	Фомин	Василий	Иванович	1976
Е4	Зубова	Оксана	Петровна	1980
Б11	Булатов	Александр	Иванович	1984

Рис. 21. Пример отношения


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

Значения элементов в столбце принадлежат одной и той же области определения, называемой доменом. Например, домен для последнего столбца на рис. множество целых неотрицательных чисел. Если же иметь в виду, что в данное отношение включены работники некоторой организации, которым наверняка не более 100 лет, то домен можно определить как множество целых чисел из интервала [текущий год – 100, текущий год – 14]. Последнее число определяет то, что малолетние дети тоже не могут быть работниками. Каждому домену может быть присвоено имя (в программировании известны такие имена доменов как int, integer, real, float, char и др.).

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

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

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

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

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

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

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

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

Репликация

Под репликацией понимается создание копий некоторых фрагментов отношений и одновременное хранение нескольких копий на разных сайтах (в разных локальных БД). Репликация используется для того, чтобы «приблизить» данные с «чужого» сайта к месту их использования. Распределенные запросы позволяют пользователю, находящемуся на сайте i, выполнять приложения с данными, находящимися как на сайте i, так и на сайтах j, k, l, … Однако, каждый такой запрос удаленных данных требует очень большого (по сравнению с местным запросом) времени. Если предполагается выполнение большого количества удаленных запросов, то более выгодным оказывается предварительно переместить (скопировать) необходимые фрагменты локальных баз данных с сайтов j, k, l, … на сайт i. Подобное решение используется и при разработке архитектуры аппаратной части компьютеров. Там оно называется кэшированием.

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

Репликация приводит и к определенным трудностям. Локальные БД постоянно обновляются. В них поступают новые данные, старые данные могут исключаться. Это приводит к тому, что БД(t)  БД(t + t) через некоторый период времени t. Следовательно, копия БД(t) становится не актуальной, и ее использование может привести к ошибочным результатам запросов.

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

Применяются синхронные и асинхронные репликации.

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

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

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

Исполнители алгоритма:

1) Менеджер сайта – владельца исходной БД (обозначим его M).

2) Менеджеры сайтов – хранителей копий фрагментов БД, m_j . Множество этих менеджеров обозначим S.


Состояния исполнителей:

Множество состояний менеджера M имеет вид Q_M = {инициализация, ожидание, обновление, завершено}.

Множества состояний менеджеров m_j имеют одинаковый вид Q_m = {инициализация, готов, не готов, выполнено}. Но каждый менеджер имеет свой экземпляр этого множества.


Операции, выполняемые менеджерами.

Менеджер M выполняет следующий набор операций:

1) start – начать транзакцию;

2) send – послать сообщения менеджерам m_j ;

3) write – записать информацию в свой журнал;

Менеджеры m_j выполняют следующий набор операций:

1) send – послать сообщения менеджеру M;

2) write – записать информацию в свой журнал;

3) put – поместить результаты транзакции в свою копию БД.


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

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

routine M

initial

состояние сайта := “инициализация”

endi

event

if message.code = “включить данные в БД” then

begin

start; write(“начало транзакции”);

L := ;

out “приготовиться к изменениям”;

состояние сайта := “ожидание”;

schedule (TimeOut, T)

end

else if message.code = “готов” then

begin

Include(L, message.id);

if L = S then

begin

L := ; out “общее обновление”;

состояние сайта := “обновление”

end

end

else if message.code = “выполнено” then

begin

Include(L, message.id);

if L = S then

begin

write(“транзакция завершена”);

состояние сайта := “завершено”

end

end

else if message.code = “не готов” then

begin

write(“не готов менеджер копии”);

out “общий возврат”;

end

else if message.code = “не выполнено” then

begin

write(“не выполнил менеджер копии”);

out “общий возврат”;

end

else if message.code = “отказ принят” then

begin

Include(L, message.id);

if L = S then

begin

write(“отказы подтверждены”);

состояние сайта := “завершено”

end

end

endc

ende;

event TimeOut;

write(“время истекло”);

состояние сайта := “завершено”;

out “общий возврат”;

ende.


Менеджер сайта – владельца исходной базы данных получает сообщение “включить данные в БД” при необходимости корректировки копий. Менеджер заносит соответствующую запись “начало транзакции” в свой журнал, готовит структуру данных (L := ) для занесения в нее в будущем информации о готовности периферийных сайтов и рассылает всем сообщение “приготовиться к изменениям”. Кроме этого, менеджер устанавливает предельное время (T) для проведения всего процесса.

Менеджеры m_j сайтов начинают присылать сообщения о своей готовности. Идентификаторы этих сайтов заносятся в множество L. Если все сайты готовы, то при приходе последнего сообщения выполнится условие L = S, т.е. множество сайтов, сообщивших о своей готовности, совпадает с множеством всех сайтов.

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

Если какой-либо из сайтов не готов или не выполнил обновление, то менеджер M дает команду “общий возврат”, отменяющую транзакцию. После отмены он ожидает подтверждений о принятии отмены от менеджеров копий базы данных.

Рутины менеджеров копий:

routine m

initial

состояние сайта := “готов”

endi

event

case message = “приготовиться к изменениям”:

if test(состояние сайта) = “готов” then

begin

write(“начинается обновление”);

блокировка доступа к копии БД;

out(“готов”);

schedule (TimeOut, T)

end

else

begin

write(“не готов”); out(“не готов”); откат транзакции

end

message = “общее обновление”:

if test(состояние сайта) = “готов” then

begin

write(“произведено обновление”); put; out(“выполнено”);

end

else

begin

write(“не готов”); out(“не выполнено”); откат транзакции

end


message = “общий возврат”:

begin

write(“отказ инициатора обновления”); откат транзакции; out(“отказ принят”);

состояние сайта := “готов”

end

endc

ende;

event TimeOut;

состояние сайта := “не готов”; снятие блокировки доступа к копии БД

ende.


Переменная «состояние сайта» является на каждом сайте разделяемой между менеджером копии и другими управляющими программами. Первоначально менеджер копии m_j устанавливает ее значение как “готов”. Впоследствии другие управляющие программы могут присваивать ей как значение “готов”, так и значение “не готов”.

Таким образом, при получении пакета изменяемых данных и сообщения (message) “приготовиться к изменениям” от менеджера M состояния сайтов с копиями могут быть различными.

В случае готовности менеджер сайта с копией БД заносит в свой журнал запись “начинается обновление”, блокирует доступ пользователей к копии БД, сообщает менеджеру M о своей готовности и включает «часы» для ожидания в течение времени T. Если транзакция не завершается почему-либо в течение этого времени, то состояние сайта меняется на “не готов” и блокировка доступа к копии БД для пользователей снимается. В дальнейшем готовность может быть вновь установлена, но в данном протоколе это действие не отражено.

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

Схемы владения данными в распределенной БД

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

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

В литературе рассматриваются несколько схем владения данными:

1) ведущий/ведомый;

2) рабочий поток;

3) симметричная репликация.


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

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

В схеме «рабочий поток» у любых данных, также как и в схеме «ведущий/ведомый», имеется единственный владелец. Однако в схеме «ведущий/ведомый» – это постоянное владение, а в схеме «рабочий поток» – временное владение, со сменой владельца. Но там и там в любой момент времени только один сайт имеет право менять конкретные данные, остальные могут только читать эти данные.

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

С точки зрения реализации схема «симметричной репликации» наиболее сложна. Она требует механизма выявления и разрешения конфликтов. Конфликты возникают при асинхронной репликации, если между двумя соседними моментами времени t_i и t_i+1 синхронизации копий БД пользователи, по крайней мере, на двух сайтах произвели изменения одних и тех же данных. Если, конечно, они произвели одинаковые изменения и знают об этом, то проблем нет. Но чаще изменения неодинаковы и/или без взаимного информирования (по какому-либо каналу передачи данных, не входящему в систему).

Примеры конфликтов.

1. На двух сайтах внесли различные записи под одним и тем же номером в структуру данных FIFO – очередь («лист ожидания»). Кто «стоит в очереди» раньше?

2. В некоторое поле, предназначенное для накопления суммы, и имевшее после синхронизации значение  на двух сайтах добавили слагаемые ₁ и ₂ , соответственно. Как провести обновление данных при очередной синхронизации копий? А если преобразование было более сложным, чем суммирование?

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


Применяются следующие механизмы разрешения:

1. Установление для каждого сайта приоритета. При конфликте принимаются во внимание изменения, произведенные сайтом с наиболее высоким приоритетом.

2. Пересчет изменений в базах. В приведенном выше примере на сайтах появились значения ( + ₁) и ( + ₂). При очередной синхронизации можно вычислить новое значение поля как сумму старого значения и всех приращений в копиях:  + (( + ₁) – ) + (( + ₂) – ).

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

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


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