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

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

• Обработка запросов.
• Управление каталогом.
• Распространение обновлений.
• Управление восстановлением.
• Управление параллельностью.

 

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

Чтобы решить задачу минимизации использования сети, процесс оптимизации запросов должен быть распределенным, как и процесс выполнения запросов. Иначе говоря, в общем случае процесс оптимизации будет включать этап глобальной оптимизации, за которым последуют этапы локальной оптимизации на каждом участвующем узле. Например, предположим, что запрос 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 с (приблизительно)

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

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

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

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