28.Перечислите основные принципы организации распределенных бд

При проектировании распределенных БД используются следующие принципы:

• отражение сложившейся организационной структуры системы;

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

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

• построение БД на основе типовых проектных решений;

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

• применение единой классификации данных;

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

• единство технологических процессов сбора, обработки и распространения данных;

• Надежность функционирования – обеспечение сохранности, защиты, безопасности информации;

• функциональная целостность – обеспечение функционирования распределенных БД как единого комплекса, позволяющего решать одну сложную задачу и множество справочных запросов;

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

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

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

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

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

29.Что представляет собой фрагментация данных?

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

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

OnLine XPS поддерживает несколько методов фрагментации: равномерная, интервальная, по выражению, хешированная.

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

Интервальная фрагментация. Этот тип фрагментации подразумевает распределение данных на основе диапазонов значений ключа. Например, таблица с данными о клиентах фирмы может быть фрагментирована по первой букве фамилий: от "А" до "Г" - узел 1, диск 1, от "Д" до "Й" - узел 1, диск 2 и т. д.

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

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

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

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

30.Перечислите проблемы распределенных систем.

Проблемы распределенных систем

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

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

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

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

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

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

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

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

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

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

• Скорость передачи данных - 50000 бит/с

• Задержка доступа - 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,56 ч) Сокращение данных о деталях на узле в для определения только тех деталей, которые имеют красный цвет, а затем для каждой из выбранных деталей проверка на узле А наличия поставок, связывающих эту деталь с поставщиком из Лондона. Каждая из таких проверок требует передачи двух сообщений. Время передачи этих сообщений также будет мало по сравнению с задержкой доступа. Т[4] = 2 с (приблизительно) Соединение отношений поставщиков и поставок на узле А, сокращение результата для получения данных только о поставщиках из Лондона, получение проекции этих результатов по атрибутам S# и Р# и пересылка результата на узел B. Завершение обработки на узле B. Т[5] = 0,1 + ( 100000 * 200 ) / 50000 = 400 с (приблизительно 6,67 мин) Сокращение данных о деталях на узле в для получения сведений только о тех деталях, которые имеют красный цвет, и пересылка результата на узел А. Завершение обработки на узле А. Т[6] = 0,1 + ( 10 * 200 ) / 50000 = 0,1 с (приблизительно)

Стратегия	Метод	Время передачи данным
1	Пересылка отношения Р на узел А	6,67 мин
2	Пересылке отношений S и SP на узел В	1,12 ч
3	Проверка деталей красного цвета для каждой поставки из Лондона	5,56 ч
4	Проверка поставщика из Лондона для каждой детали красного цвета	2,00 с
5	Пересылка данных о поставках из Лондона на узел 8	6,67 мин
6	Пересылка данных о деталях красного цвета на узел А	0,10 с (наилучший вариант)

Таблица 1. Возможные стратегии распределенной обработки запроса В табл. 1 подведены итоги по результатам обработки различных вариантов запроса. Ниже приведены комментарии к этим результатам:

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

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

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