Введение в системы БД (542480), страница 203
Текст из файла (страница 203)
Приведенная ниже подробная иллюстрация процесса выполнения запроса основана на примере, взятом из [20.13), который, в свою очередь, заимствован из ранней работы Ротни (Ко1)зп1е) и Гудмана (Оообшал) [20.33]. ° База данных поставщиков и деталей (упрощенная) Я ( Я)), С1ТХ ) 10 000 хранимых кортежей иа узле а Р ( Р)), СОЬОВ ) 100 000 хранимых кортежей иа узле Я ЯР ( Я)), Р() 1 000 000 храииммх кортежей иа узле А Предположим, что каждый хранимый кортеж имеет длину 25 байт (200 бит). ° Запрос (" Получить номера лондонских поставщиков красных деталей" ) ( ( Я 301Н ЯР 101Н Р ) ННЕВЕ С1ТУ = '1лпбоп' ВНЮ СОЕОВ = СОЕОВ ('Веб') ) ( Я)) ) ° Расчетные количества некоторых промежуточных результатов Количество красных деталей 1О Количество поставок, выполненных поставщиками из Лондона 100 000 ° Предполагаемые параметры линий передачи данных Скорость передачи данных 50 000 бит/с Задержка доступа О,1 с Теперь кратко рассмотрим шесть возможных стратегий выполнения этого запроса, и для каждой стратегии 1 рассчитаем общее время Т(1) передачи данных по следующей формуле.
( общая задержка доступа ) ь ( общий объем данных / скорость передачи данных ) В этом случае она сводится к следующей формуле (время в секундах). ( количество сообщений / 10 ) ь (количество битов / 50000 ) 781 Глава 20. Распределенные базы данных Метод В емя пе е ачи данных Ст атегия 6,67 мии 1,12 ч 6,06 ч Пересылка Р на А Пересылка 8 и ВР на Б Для каждой поставки из Лондона проверка красной детали Для каждой красной детали проверка по- ставщика из Лондона Пересылка поставок из Лондона на Б Пе есылка к асных деталей на А 2,00 с 6,67 мин 0,10 с самое малое Рис. 20.4, Возможные сгнратегии распределенной обработки запроса /сводка) Прокомментируем эти результаты.
° Каждая из шести стратегий представляет возможный подход к проблеме, но отклонения по времени передачи данных огромны. Наибольшее время в два миллиона раз больше, чем наименьшее. 782 Часть )г. дополнительные аспекты 1. Пересылка записей о деталях на узел А и обработка запроса на узле А. Т[1) = 0,1 + ( 100000 Я 200 ) / 50000 = 400 с (приблизительно 6,67 мин) 2. Пересылка записей о поставщиках и поставках на узел Б и обработка запроса на узле Б. Т[2] = 0,2 + ( ( 10000 + 1000000 ) * 200 ) / 50000 = 4040 с (приблизительно 1,12 ч) 3.
Соединение отношений поставщиков и поставок на узле А, выборка из результирующего отношения кортежей лля поставщиков из Лондона с последующей проверкой на узле Б для каждого выбранного поставщика соответствующих деталей, является ли деталь красной. Каждая из таких проверок включает два сообщения: запрос и ответ. Время передачи этих сообщений будет мало по сравнению с задержкой доступа. Т[3] = 20000 с (приблизительно 5,56 ч) 4. Выборка красных деталей на узле Б и проверка для каждой из выбранных деталей на узле А наличия поставок, связывающих эту деталь с поставщиком из Лондона. Каждая нз таких проверок включает два сообщения. Время передачи этих сообщений также будет мало по сравнению с задержкой доступа.
Т[4) = 2 с (приблизительно) 5. Соединение отношений поставщиков и поставок на узле А, выборка из результата кортежей лля поставщиков из Лондона, проекция этих кортежей по атрибутам 64 и Рб и пересылка результата на узел Б. Завершение обработки на узле Б. Т[5] = 0,1 + ( 100000 ' 200 ) / 50000 = 400 с (приблизительно 6,67 мин) б. Выборка красных деталей на узле Б и пересылка результата на узел А. Завершение обработки на узле А. Т[б] = 0,1 + ( 10 * 200 ) / 50000 = 0,1 с (приблизительно) На рис. 20.4 подведены итоги результатов обработки различных вариантов запроса.
° Скорость обмена данными и задержки доступа — важные факторы в выборе стратегии. ° Для плохих стратегий время вычислений и ввода-вывода ничтожно мало по сравнению со временем передачи данных. С другой стороны, для лучших стратегий это соотношение может зависеть от дополнительных обстоятельств (20.35). Такого большого расхождения может не быть в случае использования быстрых локальных сетей.
Кроме того, некоторые стратегии позволяют выполнять параллельную обработку на двух узлах, поэтому время ответа системы пользователю может быть даже меньше, чем в случае, когда окончательный результат запроса определяется на единственном узле. Управление каталогом В распределенной системе каталог включает не только обычные для каталога данные, соответствующие базовым переменным-отношениям, представлениям, полномочиям и т.д., но также всю необходимую управляюшую информацию, которая позволит системе обеспечить независимость от размешения, фрагментации н репликации. Возникает вопрос тде н как должен храниться сам каталог?".
Имеется несколько перечисленных ниже возможностей. !. Ценлгралиэовакное хранение. Единственный обший каталог хранится на отдельном центральном узле. 2. Полная репликачил. Общий каталог целиком хранится на каждом узле. 3. Частичное хранение. Каждый узел поддерживает собственный каталог для объектов, которые на нем хранятся. Общий каталог представляет собой объединение всех этих несвязанных локальных каталогов.
4. Сочетание подходов ! и 7. Каждый узел поддерживает свой локальный каталог, как предусмотрено при подходе 7. Кроме того, отдельный центральный узел сопровождает объединенную копию всех этих локальных каталогов, как предусмотрено при подходе 1. Каждый подход имеет свои недостатки. При подходе 1, очевидно, нарушается принцип "Отсутствие опоры на центральный узел". При подходе 2 в значительной мере утрачивается независимость узлов, поскольку всякое обновление каталога должно распространяться на каждый узел. При подходе 3 нелокальные операции становятся слишком затратными (для поиска удаленного объекта требуется доступ в среднем к половине всех узлов).
Подход 4 более эффективный по сравнению с подходом 3 (для поиска удаленного объекта требуется доступ лишь к одному удаленному каталогу), но в этом случае вновь нарушается принцип отсутствия центрального узла. Поэтому на практике системы обычно не используют ни один из этих подходов! В качестве примера рассмотрим подход, который применяется в версии К' системы К [20.391. Прежде чем описать структуру каталога системы й~, необходимо сказать несколько слов о механизме именования объектов в этой системе. Присвоение имен объектам— это вообше очень важный вопрос для распределенных систем. Поскольку два отдельных узла Х и Х могут иметь объект (скажем, базовую переменную-отношение) с именем А, требуется некоторый механизм (обычно — уточнение с помощью имени узла) для того, чтобы "устранить неоднозначность", т.е.
гарантировать уникальность расширенного системного имени. Однако, если уточненные имена, такие как Х.А и Х.А, будут предостав- Глава 20. Распределенные базы данных 783 ляться системой и пользователю, будет нарушено требование независимости от размешения. Поэтому необходимы средства отображения имен для пользователя в соответствующие системные имена. Теперь изложим подход к рассматриваемой проблеме, принятый в системе К*. В этой системе различаются печатные имена„с помощью которых пользователи обычно обрашаются к объектам (например, в предложении ЯЕЬЕСТ языка Б()Ь), и обшесистемные имена, которые представляют собой глобальные уникальные внутренние идентификаторы для этих же объектов. Расширенные системные имена имеют четыре следующих компонента. ° Идентификатор создателя, т.е.
идентификатор пользователя, который создал объект. ° Идентификатор узла создателя, т.е. идентификатор узла, на котором была введена соответствуюшая операция СМЕЕТЕ (создать). ° Локальное имя, т.е. не уточненное имя объекта. ° Идентификатор узла рождения, т.е, идентификатор узла, на котором объект хранился первоначально. Идентификаторы пользователя уникальны на узле, тогда как идентификаторы узла уникальны глобально. Рассмотрим, например, следующее расширенное системное имя. ИАЕ1ЬХМ $ ЫЕМХОЕК . ЯТАТБ 6 ЬОМООМ Оно обозначает обьект (возможно, базовую переменную-отношение) с локальным именем ЯТАТЯ, созданный пользователем ИАМ1ЬХМ на узле в Ньюыйорке и первоначально сохраненныйз на узле в Лондоне. Это имя гарантировано зашнщено от каких-либо изменений, даже если объект будет перемешен на другой узел (см, ниже).
Как уже указывалось, пользователи обычно ссылаются на объекты с помощью печатных имен. Печатное имя представляет собой простое, не уточненное имя — компонент "локальное имяп из расширенного системного имени (в примере это БТАТЯ) или синоним для соответствующего расширенного системного имени, который в системе Кв определяется с помошью специального оператора СЕЕАТЕ БХМОМХИ, как, например, показано ниже. сееАте яхмОмхм иятйтБ РОК МАЕ1ьхм 6 мемхОмк .