Стратегии хранения данных в РБД

Название стратегии	Суть стратегии	Достоинства	Недостатки	Рекомендации применения
Централизация (в том числе технология клиент/сервер)	Единственная копия БД в одном узле	Простота структуры	Скорость обработки ограничивается одним узлом. Долговременная память обеспечивает объем БД. Ограниченный доступ. Малая надежность.	Долговременная память ограничена по сравнению с объемом БД. Должна быть повышена эффективность функционирования при высокой степени централизации.
Локализация (расчленение)	Единственная копия, расчлененная по узлам (полная копия БД не допускается)	Объем БД определяется памятью сети. Снижение стоимости РБД. Время отклика при параллельной обработке уменьшается. Малая чувствительность к узким местам. Повышенная надежность при высокой локализации ссылок.	Запрос может быть не по всем узлам (затраты на связь больше при централизации). Доступ может быть хуже, чем при централизации
Дублирование	В каждой локальной БД - полная копия РБД	Выше надежность, доступность и эффективность выборки, простота восстановления. Локальная асинхронная обработка данных в узлах. Получение быстрых ответов	Объем БД ограничен долговременной памятью. Синхронизация многих копий. Дополнительная память. Слабая реализация параллельной обработки	Фактор уверенности превалирует. БД невелика. Интенсивность обновления невысока. Интенсивные запросы.
Смешанная	Несколько копий хранимого логического фрагмента в каждом узле	Любая степень надежности. Большая доступность. Меньше пересылок. Параллельная обработка.	Надо хранить словари. Рост стоимости согласованных копий. Разная частота обращения узла к различным частям БД. Потеря надежности из-за расчленения. Мала свободная долговременная память из-за

На ее основе может быть построен простейший алгоритм выбора стратегии, показанный на рис. 2.

Рис.2. Алгоритм выбора стратегии хранения: А - запрос локален

 

 

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

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

РБД состоит из трех основных частей: клиентов, модуля обработки транзакций и хранилища данных.

 

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

Рис. 3. Распределенные серверы

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

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

Дополнительными специфическими требованиями являются:

1) ЯОД в рамках схемы должен быть один для всех локальных БД;

2) доступ должен быть коллективным к любой области РБД с соответствующей защитой информации;

3) подсхемы должны быть определены в месте сосредоточения алгоритмов (приложений, процессов) пользователя;

4) степень централизации должна быть разумной;

5) необходимы сбор и обработка информации об эффективности функционирования РБД.

Состав и работа РБД

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

Рис.4. Схема РБД

 

Общий набор (система таблиц) данных, хранимых в РБД, показан в табл.2.

Таблица 2.

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

Не все данные глобального уровня доступны конкретному пользователю. Наиболее полные данные (пользовательский, внешний уровень) имеются в узле 1 головного предприятия. В узлах (участках) 2, 3 данные менее полные. Так, в узле 3 они имеют вид, показанный в табл.3.

 

Таблица 3

Пользовательский уровень состоит из фрагментов (например, строки A, B, C, 1, 2, 3 или столбцы табл. 12.1) глобального уровня, которые составляют фрагментарный, логический уровень.

Выделяют горизонтальную и вертикальную фрагментацию (расчленение).

Горизонтальное фрагментирование связано с делением данных по узлам. Горизонтальные фрагменты не перекрываются.

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

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

Так, например, локализация для примера в табл. 12.1. может иметь вид, показанный в табл. 4.

Таблица 4.

Локализация данных

Имя таблицы	Фрагменты	Распределение фрагментов по узлам
Служащие		11,21,3
Завод	aaa	1,2.31,2,31,2,3
Сырье	ABC

Очевидно, что для таблицы «Завод» осуществляется дублирование, а для таблицы «Сырье» - расчленение.

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

Физическую реализацию (логического) фрагмента называют хранимым фрагментом.

Иначе говоря, РБД можно представить в виде, показанном на рис. 5.

Сеть в РБД образуют сетевые операционные системы (например, Windows NT, Novell NetWare). В качестве СУБД, изначально предназначавшихся для использования в сети, следует назвать BTrieve, Oracle, Interbase, Sybase, Informix.

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

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

Рис. 5. Уровни представления данных в РБД

 

Естественно, что для работы в РБД необходимы администраторы РБД и локальных БД, рабочими инструментами которых являются перечисленные словари. Схема работы РБД показана на рис. 6.

Пользовательский запрос, определяемый приложением, поступает в систему управления распределенной базы данных (СУРБД) и через сетевую и локальную операционные системы попадает в локальную СУБД. Если запрос связан с локализованными данными, СУБД осуществляет вызов данных из локальной БД, которые поступают пользователю. Если часть данных для выполнения приложения находится в другой локальной БД, локальная СУБД дополнительно через локальные и сетевые операционные системы осуществляет удаленный вызов процедуры (Remote Procedure Call - PRC), после выполнения, которой данные передаются пользователю.

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

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

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

2. Целесообразно использовать на сервере хранимые процедуры, совокупность которых можно инкапсулировать в виде пакета (модуля). В результате трафик уменьшится: клиент будет передавать только вызов процедуры и ее параметры, а сервер - результаты выполнения процедуры.

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

 

Рис. 6. Схема работы РБД

 

Контрольные вопросы

1. Каковы новые требования к БД?

2. Что такое «распределенная база данных - РБД»?

3. Что такое локальный и удаленный доступ?

4. Каковы сетевые уровни представления данных?

5. Перечислите стратегии хранения, их достоинства и недостатки, рекомендации по выбору стратегии. Что такое однородные и неоднородные РБД? Особенности интеграции локальных БД в РБД.

6. Задачи администратора системы.

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

Принципы построения РБД.

1. Минимизация интенсивности обмена данными (сетевого трафика)
2. Оптимальным размещением серверных и клиентских приложений в сети
3. Декомпозиция данных на часто и редко используемые сегменты (для правильной настройки репликации - размещение наиболее часто используемых данных на АРМ конечных пользователей)
4. Периодическое сохранение копий данных и выполнение действий по поддержке целостности распределенной информационной системы.
5. Максимум локализации данных и сокращение количества пересылаемых по кратчайшему пути данных: рекомендуется иметь до 90 процентов ее в локальной БД (ЛБД) узла и около 10 процентов - в ЛБД других узлов.
6. Локальность расположения данных следует определять по отношению к наибольшему числу приложений.

Критерии построения РБД.

1. Всесторонний анализ информационных потребностей предметной области с выявлением объемов хранимых данных их сложности, достоверности, взаимосвязанности.
2. Моделирование предполагаемого сетевого трафика при работе РБД с различными моделями репликации данных.
3. Кластеризация элементов данных и программ их обработки. Цель- добиться максимальной автономности и слабосвязанности кластеров.
4. Привязка кластеров данных к вероятным пользователям или АРМ.
5. Поддержка эталонной копии данных и ограничение репликационного механизма
6. Разработка и реализация правил приведения локальных и центральной БД в непротиворечивое состояние.
7. Минимум объема пересылаемых данных и сообщений.
8. Минимум стоимости трафика.
9. Минимум общего времени, необходимого для обслуживания запросов к БД.

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

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

В общем случае целостность данных может нарушаться по следующим основным причинам:

1) ошибки в создании структуры локальных БД и их заполнении;

2) просчеты в построении структуры РБД (процедуры фрагментации и локализации);

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

4) аварийная ситуация (неисправность технических средств) и восстановление РБД.

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

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

Рис. 7. Проблемы РБД

 

Использование РБД

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

Одновременный доступ

Особенностью РБД является многопользовательский распределенный доступ к данным.

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

Взаимодействие элементов в РБД осуществляется посредством транзакции, которая становится

распределенной (рис. 8) и, воздействуя на целостную БД, после своего завершения оставляет БД целостной. В транзакции выделяют две команды: читать (R) и писать-обновлять (W).

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

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

Последовательное РР (ПРР) - это РР, в котором каждая составляющая последовательна. Последовательностноподобное РР (ППРР) эквивалентно ПРР.

 

 

Рис. 8.. Распределенная модель транзакции: Ti (суб) транзакции

Существует несколько методов синхронизации.

I. Блокировка, которая может быть:

1) с главным узлом;

2) с заданием блокировки с помощью предикатов;

3) с главной копией.

II. Голосование по большинству.

III. Метод предварительного анализа конфликтов.

Восстановление РБД

Если РБД обеспечивает целостные, непротиворечивые данные, говорят об ее корректном состоянии (корректности).

Восстановление (управление восстановлением) связано с приведением системы в корректное состояние после (аппаратного) сбоя.

Любой конкретный метод восстановления реагирует на определенный отказ РБД.

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

Система восстановления решает две группы задач:

1) при незначительной неисправности - откат в выполнении текущей транзакции;

2) при существенных отказах - минимизация работы по восстановлению РБД.

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

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

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

Процедура восстановления проводится следующим образом.

1. Устраняется аппаратный сбой.

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

3. Запускается процесс восстановления:

а) с применением транзакций (применение к архивным копиям испорченных данных необходимых групп журнала транзакций);

б) с отменой - отмена незавершенных транзакций, оставшихся после восстановления с применением транзакций.

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

Оптимизация запросов

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

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

Целями (целевыми функциями) оптимизации могут быть:

1) минимум времени передачи данных;

2) минимум времени обработки данных в узлах;

3) увеличение параллельности при обработке и передачах данных;

4) улучшение трафика и загрузки процессоров в сети;

5) минимум стоимости (задержки) только передачи данных (если имеются низкоскоростные каналы связи);

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

7) выравнивание нагрузки компьютеров.

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

Стоимость ТС обработки данных объема x, пересылаемой в узел i из узлов j и связанной с эксплуатацией физических каналов связи, составляет

,

где , - определяемые системой матрицы стоимости установления связи и передачи единицы информации ( = = 0).

Задержка TD(x) - время между началом и окончанием обработки запроса:

,

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

Примем такие предположения:

1) каналы связей однородны ();

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

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

1) глобальная оптимизация, которую далее будем называть просто оптимизацией;

2) локальная оптимизация,

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

Используем дерево запросов, в котором каждому из листов соответствует отношение, каждой вершине - операция РА. Конечной вершине соответствует узел РБД (локальная БД), а ответу на вопрос - корневая вершина.

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

В связи с этим используем эвристический подход к оптимизации.

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

В этой связи возможны следующие рекомендации.

1. Унарные операции необходимо выполнить как можно ранее (в узлах). Это иллюстрирует рис. 9.

Рис. 9. Использование унарных операций

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

Рис. 10. Выделение общих подвыражений: а - исходный; в - преображенный запрос

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

DF(T, S_NF (T))=S_F (T), NF=NOT F.

3. Использование полусоединения. Идея полусоединения иллюстрируется на рис. 11.

Рис. 11. Использование полусоединения

При традиционной схеме либо R надо пересылать в узел 2, либо S - в узел 1 (пунктирная линия). Можно пересылать лишь один раз S, сокращенную в помощью проекции, в узел 1 и затем осуществлять полусоединение.

Покажем сказанное на примере. Пусть даны следующие отношения:

Узел 1	Узел 2
r(A B)	s(B C D)	r'(B)	s'(B C D)
	4 13 16		4 13 16
	4 14 16		4 14 16
	7 13 17		7 13 17
	10 14 16
	10 15 17
	11 15 16
	11 15 16
	12 15 16

Имеются следующие возможности.

Переслать S из узла 2 в узел 1 (24 значения).

Вычислить r'=Р_в (r) в узле 1 и переслать его в узел 2, где вычислить s'=J(r', s) и отправить в узел 1. Там найти J(r, s) как J(r, s'), т.е. получить полусоединение. Передается уже 9 + 6 = 15 значений.

Напомним, что полусоединение r и s или SJ(r, s) есть Р_R (J(r, s)), Rеr. Если отношения r и s находятся в разных узлах, то вычисление полусоединения уменьшает объем передаваемых данных. Заметим, что для полусоединения справедливо J(SJ(r, s), s).

Иногда полусоединение может полностью заменить соединение.

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

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

Вводят понятие «профиль», который включает:

1) мощность (количество полей) отношения R;

2) «ширину» (число байтов) любого атрибута;

3) число различных значений атрибута в отношении R.

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

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

Таким образом, задача оптимизации запроса отличается неоднозначностью решения.

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

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

 

Контрольные вопросы

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

2. Что такое интеграция в РБД? однородная? неоднородная?

3. Какой математический аппарат можно использовать для анализа интеграции?

4. В чем отличие математического описания физической системы и системы локальных БД?

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

6. Как обеспечивается неоднородная интеграция?

1. Каковы группы методов синхронизации в РБД?
2. Суть блокировки с главным узлом и с использованием предикатов.
3. Блокировка с главной копией: достоинства и недостатки.
4. Достоинства и недостатки голосования по большинству.
5. Суть метод предварительного анализа конфликтов, его механизмы.
6. Какие критерии могут быть использованы для оптимизации запросов? Какой математический аппарат для этого применяется?
7. Каковы рекомендации по рационализации запросов?
8. Как используется операция полусоединения?
9. Что такое «восстановление» РБД?
10. Напишите процедуру восстановления.
11. Каковы возможности восстановления без дублирования, при частичном и полном дублировании данных?
12. Всегда ли нужен откат всей транзакции при откате какой-либо субтранзакции? Каков другой вариант?
13. Как можно использовать активные узлы?
14. Какие методы можно использовать при частичном дублировании? Можно ли при этом надежно устранить сбои в неуправляемых узлах?