Принципы реализации машин БД

и высокопараллельную МН МВД сложно.

Вторая основная проблема в создании высокопараллельных МН МБД, названная

«дисковым парадоксом», заключается в том, что скорость ввода-вывода

современных УМП (одноканальные и многоканальные НМД с перемещающимися

головками) является узким местом и ограничивает достижение высокого

параллелизма в обработке. В МН МБД для решения этой проблемы в качестве кэш-

диска применяется большая полупроводниковая буферная память.

Для решения этой проблемы некоторые авторы предлагают сетевые МБД в

которых распределенное хранение больших БД осуществляется на большем

количестве НМД.

Сетевые МВД (см. рис. 1,б) воплощают принципы однородности структуры,

сегментации данных в устройствах массовой памяти и распределения

процессоров обработки по УМП. Таким образом, основная идея сетевых MBД -

приближение дешевой обрабатывающей логики (в виде универсальных

микропроцессоров) к УМП и связывание таких «обрабатывающих хранилищ» в

сеть. Учитывая быстро снижающуюся стоимость процессоров oбработки и жестких

НМД и успехи в технике коммуникации процессоров, в ее составе такой сети

может быть сотни УМП, с каждым из которых соединен свой обрабатывающий

процессор. Примерами таких проектов являются МВО; GAMMA. В перспективе

развития сетевых MB.Д некоторые авторы видят создание МВД на основе

вычислительной систолической среды. Так, проект NODD, схема которого

изображена на рис. 5, реализован в виде регулярной решетки, в узлах которой

размещены процессорные элементы (ПЭ). С каждым ПЭ связаны своя локальная

память (ЛП) и устройство массовой памяти (УМП) в виде жесткого НМД.

[pic]

Предполагается также замена УМП энергонезависимой полупроводниковой

памятью соответствующей емкости («силиконовая» систолическая МВД).

Назначение ЛП в каждом узле-хранение программ обработки, копии управляющей

программы, буфера для обмена сообщениями и кэш-памяти для своего УМП (3%

каждого локального УМП находится в этой локальной кэш-памяти). Для целей

надежности пространство на каждом УМП разделено на части: одна часть для

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

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

выполнением транзакций в таких сетевых МВД полностью распределено, так что

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

Особый интерес приобретает создание систолических МВД в связи с

появлением серийных однокристальных транспьютеров, содержащих наряду с

процессором и памятью каналы (порты ввода-вывода). Например, промышленный

транспьютер фирмы INMOS IMS Т414 имеет следующие характеристики. В одном

кристалле реализован 32-разрядный процессор быстродействием до 10 млн.

опер./с, статическое ОЗУ на 2 Кбайт, четыре канала связи, 32-разрядный

интерфейс памяти и контроллер динамического ОЗУ. Конструктивно

транспьютерная матрица, являющаяся основным элементом систолических

транспьютерных МВД (см. рис. 5), может быть реализована посредством

серийных транспьютерных плат IMS ВОООЗ той же фирмы. Эта двойная европлата

содержит четыре транспьютера Т414, связанных между собой портами связи,

четыре устройства динамической памяти по 256 Кбайт каждое и четыре внешних

порта ввода-вывода. Возможно, в ближайшее время применение таких

транспьютерных плат переведет проекты систолических МВД из области

теоретических исследований в область практической реализации.

[pic]

Основной проблемой в распределенных (сетевых) МБД является оптимальная

кластеризация данных по локальным УМП и поддержка соответствующей

распределенной индексации. В GAMMA, например, предлагается кластеризация

каждого отношения по всем УМП (в соответствии с хешированием

значенийключевых атрибутов и созданием распределенного по УМП индекса этих

значений). В NODD предлагается равномерное распределение отношений по

узлам решетки. Между конкретными кортежами разных отношений, для которых

действуют семантические связи, существуют указатели, задающие расположение

связанных кортежей (номера узлов и их адреса в УМП). Таким образом, запрос

в БД возбуждает связи между кортежами в узлах решетки и порождает поток

данных между ними. Это позволяет реализовать в такой МВД потоковую

обработку сложных запросов на основе модели «активного графа»

К классу сетевых относится коммерческая МВД фирмы Teradata DBC 1012,

которая интенсивно распространяется и находит широкое применение в разлиных

информационных системах. На рис. 6 изображена конфигурация DBC 1012 с

восемью обрабатывающими процессорами ПМД (на базе i80386), каждый из

которых имеет НМД и подключается к коммуникационной сети типа двоичного

дерева (Y-сеть). В узлы этой сети встроены сетевые высокоскоростные

процессоры и программируемые логические матрицы, реализующие функции

управления сетью. Y-сеть позволяет осуществлять дуплексный обмены между

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

процессоры (ИЛ) для осуществления интерфейса с главной ЭВМ. Каждый

обрабатывающий процессор обеспечивает поддержку всех операций реляционной

алгебры, достаточных для выполнения операторов SQL, поддержку своей части

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

частью БД, в том числе защиту целостности, восстановления и т. д. Образцы

DBC 1012 включают до 128 процессоров и имеют распределенную по

обрабатывающим процессорам полупроводниковую память емкостью 412 Мбайт на

один процессор. Общая емкость массовой памяти составляет до 1000 Гбайт и

общее быстродействие - до 10^9 опер./с.

[pic]

Два свойства DBC 1012 характерны для всех сетевых МЕД:

обеспечение возможности увеличения мощности наращиванием числа

обрабатывающих процессоров, так что производительность при этом растет

линейно (показатель линейности роста производительности DBC 1012 от числа

процессоров составляет 97%);

обеспечение надежности функционирования за счет дублирования данных в

локальных УМП (т. е. обеспечивается работа без краха системы при выходе из

строя отдельных процессоров или УМП).

Третье направление исследований в области МБД заключается в создании

недорогих коммерческих устройств на серийных процессорных элементах с

шинным интерфейсом (топология таких МБД изображена на рис. 2,а). В качестве

примера рассмотрим МБД фирмы Britton Lee IDM 500, структурная схема которой

изображена на рис. 7. Хотя эти изделия не ориентированы на

высокопараллельную обработку и содержат ограниченное число функциональных

процессоров, они удовлетворяют сформулированным выше принципам МН МБД и

полностью реализуют все основные функции МБД. Структурная схема

коммерческих МБД является частным случаем МН МБД (см. рис. 2,a). Роль СБП

выполняет полупроводниковая память, к которой через общую шину подключаются

периферийные контроллеры НМД со встроенными микропроцессорами AMD 2901,

процессор обработки (процессор БД) на основе Z8002 и до 8 канальных

процессоров для подключения к главной ЭВМ (канал IBM 370, интерфейс с VAX

750) или подключения к локальной сети (Ethernet). Кроне того, к общей шине

может подключаться особый функциональный процессор (акселератор БД) для

выполнения тех операций, которые являются узким местом (например,

сортировка отношений). Старшая модель IDM SOO/XL с емкостью внешней памяти

более 1 Гбайт на жестких МД и 500 Мбайт на МЛ имеет производительность 1000

транзакций/мин и одновременно обслуживает до 400 пользователей.

Развитием этого направления в разработках фирмы Britton Lee явился

реляционный файлсервер (data/file server) RS310 - автономное устройство,

подключаемое к локальной сети Ethernet или непосредственно к главной ЭВМ по

интерфейсу RS232. Он включает:

собственно процессор базы данных (1 плата) на основе 28000 (10

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

одной плате;

два жестких диска типа винчестер (5 1/4 дюйма) по 80 Мбайт каждый с

соответствующим контроллером;

контроллер кассетной МЛ с 60 Мбайт на кассете (Streaming tape 1/4 дюйма);

до четырех интерфейсных плат двух типов (интерфейс RS232 с восемью

выходами или интерфейс локальной сети Ethernet).

Каждая интерфейсная плата содержит процессор 28000 и свою локальную

память. ,RS310 может быть использован или как автономная СУБД с выходным

языком SQL, поддерживая при этом все функции СУБД, за исключением первого

этапа трансляции с SQL (управление транзакциями, параллельное выполнение

запросов, откаты и восстановления, автоматическую оптимизацию запросов и т.

п.), или как интегрированная система управления файлами. При этом RS310

выступает для главной ЭВМ в качестве интеллектуального контроллера с

буферизацией и удовлетворяет интерфейсу SCSI (Small Computer System

Interface). RS310 обеспечивает одновременную работу до 50 пользователей и

выполняет одновременно до 10 запросов. Ближайшая перспектива развития RS310

- увеличение внешней памяти до восьми НМД емкостью 478 Мбайт и МЛ емкостью

300 Мбайт.

[pic]

Рис. 8. Специализированная машина для БД PYRAMID S 9810 (9820)

Дальнейшим развитием такого подхода к созданию коммерческих МБД является

их реализация на модульной параллельной мультимикропроцессорной системе

типа систем S27 и S81 фирмы Sequent и систем серии 9000 (9810, 9820) фирмы

Pyramid-Sybase. На рис. 8 изображена структурная схема нового изделия фирмы

Pyramid--система 9810(9820), являющаяся специализированной ЭВМ для БД. Эта

специализированная машина предназначена для автономной поддержки СУБД

Sybase с входным языком SQL, а также для поддержки прикладных

информационных систем на основе этой СУБД для автоматизации конторской

деятельности, разработки программного обеспечения и т. п. Система работает

как data computer в сети ЭВМ и имеет интерфейс не только с локальной сетью

Ethernet, но и Х25, telenet, darpa. Общая дисковая память достигает 15

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

плат до 4 и 16 Мбайт, может наращиваться до 128 Мбайт. В системе

поддерживается виртуальное адресное пространство 4 Гбайт со страницами в

2048 байт. В качестве процессоров обработки выступают один или два

спецпроцессора (CPU), реализованные в виде 32-разрядных процессоров с RISC-

архитектурой. CPU имеет следующие характеристики:

время цикла- 100 нс;

число 32-разрядных регистров - 528;

кэш-память инструкции- 16 Кбайт;

кэш-память - 64 Кбайт.

В RISC-процессорах реализован конвейерный режим выполнения инструкций.

Основой системы является собственная сверхбыстрая шина xtend

(40 Мбайт/с), работающая по принципу коммутации сообщений. Интеллектуальный

процессор ввода-вывода (ПВВ) реализован на базе микропроцессора AMD 29116 с

быстродействием 5 млн. опер./с и содержит 14 параллельных ОМА-контроллеров,

общая пропускная способность которых 11 Мбайт/с. ПЕВ обслуживает

периферийные устройства, контроллеры НМД (скорость передачи в которых до

2,5 Мбайт/с) и контроллеры локальной сети (КЛС).

К общей шине подключается до 16 портов с интерфейсом RS232 для

обслуживания интеллектуальных терминальных процессоров, с помощью которых к

системе могут подключаться терминальные пользователи. Подключение к шине

адаптера шины MULTIBUS открывает широкие возможности для подключения

вспомогательных внешних устройств, в которых реализован интерфейс этой

шины.

Управление системой осуществляется процессором поддержки системы, в

функции которого входят также диагностика всех устройств и системы в целом,

сервисная служба системы и т. п. В этом процессоре функционирует так

называемая двухпортовая многопроцессорная операционная система, которая

соединяет в себе две версии UNIX ОС: System V. AT&T и 4.0 Berkly.

Перспективы развития МБД

Создание высокопроизводительных МВД связывается с решением следующих

проблем, по которым ведутся интенсивные исследования.

1. Создание специализированных архитектур МВД, сочетающих достоинства

горизонтального параллелизма при выполнении одной операции с функциональным

параллелизмом при выполнении последовательности операций и транзакций.

Особую роль здесь играет реализация конвейерной потоковой обработки (data

flow) применительно к операциям реляционной алгебры.

[pic]

Рис. 5.9. Структура подсистемы потоковой обработки в МВД DFRU

Управление выполнением запросов при этом должно происходить собственно

потоками данных, что облегчает задачу программного контроля выполнением

операций, синхронизации их и т. п. Например, в проекте DFRU предпринята

попытка аппаратно реализовать потоковую обработку в регулярной структуре

обрабатывающих процессоров (рис. 9). Основным обрабатывающим элементом

является универсальный компаратор кортежей (К). В матрице компараторов

кортежей, соединяемых коммутирующими сетями, возможна динамическая

коммутация выходов процессоров обработки i-го уровня со входами процессоров

(i+1)-го уровня. В каждой строке матрицы по одному арифметическому

процессору (АП) для реализации агрегатных функций. Связи между процессорами

устанавливаются в соответствии с дугами дерева запроса (дерева реляционных

операций). Это позволяет отображать дерева запроса в дерево процессоров,

вырезаемых в данной матрице, так что каждой операции назначается один

процессор обработки. После этого исходные отношения в потоке читаются из

подсистемы массовой памяти и обрабатываются конвейерно в настроенном дереве

процессоров, так что кортежи, образованные в операции i-го уровня, через

коммутирующую сеть попадают в соответствующий процессор (i+l)-го уровня. На

рис. 10 проиллюстрирован этот процесс для следующего запроса: «Выдать имена

поставщиков, которые поставляют более 100 деталей типа I» применительно к

трем исходным отношениям:

(RI) ПОСТАВЩИК (КОД ПОСТАВЩИКА, имя);

(R2) ДЕТАЛЬ (КОД-ДЕТАЛИ, ТИП-ДЕТАЛИ, НАИМЕНОВАНИЕ);

(R3) ПОСТАВКА (КОД-ДЕТАЛИ, КОД-ПОСТАВЩИКА, КОЛИЧЕСТВО).

[pic]

Рис. 10. Реализация дерева операций в матрице процессоров

Появление на входе компаратора кортежа исходного отношения для операции

селекции (select) или двух исходных кортежей для операции соединения (join)

активизирует его, и после выполнения операции и выдачи результирующего

кортежа он переходит в состояние ожидания. Процессоры сортировки отношений

подключаются перед бинарными операциями или перед операцией удаления

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

если длина дерева запроса больше числа строк в обрабатывающей матрице, или

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

В матрице процессоров возможно одновременное выполнение нескольких

запросов, каждый из которых отображен в свое дерево процессоров.

Необходимость в сортировке объясняется тем, что реализация бинарных

операций реляционной алгебры (с нелинейной сложностью 0(n^2), где n-

кардинальность отношений) в потоковом режиме, когда единицей обмена между

операциями являются кортежи или страницы отношений, возможна, только если

отношения одинаково упорядочены. Поэтому операция сортировки в конвейерном

и потоковом режимах обработки является узким местом, и требуется ее

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

высокая скорость и близкая к линейной зависимость времени сортировки от

объема отношения;

один проход при реализации сортировки;

конвейерный режим обработки потока данных;

наличие внутренних буферов объемом не менее страницы отношения (64,

128, 256 Кбайт);

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

[pic]

рис. 11. Влияние задержки при сортировке на потоковый режим обработки

кортежей

Необходимо отметить, что даже применение аппаратных потоковых

сортировщиков не решает полностью проблему потокового выполнения бинарных

операций. Сортировщик может начать выдачу кортежей сортированного отношения

только после получения на входе последнего кортежа исходного отношения, да

и то с задержкой. Например, процессор сортировки в Delta имеет задержку

(2lm+N-1)t, где l-длина кортежа в байтах, t=ЗЗО нс-время пересылки байта

между сортирующими элементами, m-число сортируемых кортежей, N - число

сортирующих элементов. Таким образом, наличие даже аппаратной потоковой

сортировки прерывает и замедляет общий поток кортежей между реляционными

операциями. А любое замедление входного потока одного отношения-операнда

требует для другого операнда бинарной операции наличия промежуточного

буфера. Поэтому конвейер кортежей при потоковой обработке должен иметь вид

«растягиваемых рукавов» (рис. 11). Все это может свести к минимуму

преимущества потоковой обработки.

2. Создание ассоциативной памяти большой емкости для системного буфера

МВД. Как известно, использование ассоциативной памяти в качестве СБП

позволяет существенно повысить эффективность поисковых и некоторых других

операций в МВД на уровне вторичной обработки. Интерес представляет

гибридная ассоциативная память, которая имеет один порт-обычный для

подключения памяти к общей шине, а второй-ассоциативный для подключения к

соответствующему контроллеру.

Страницы: 1, 2, 3