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

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

Основы современной информационной технологии составляют базы данных

(БД) и системы управления базами данных (СУБД), роль которых как единого

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

постоянно возрастает. При этом существенным является постоянное повышение

объемов информации, хранимой в БД, что влечет за собой требование

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

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

Это особенно проявляется при организации логической обработки информации в

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

системы.

Быстрое развитие потребностей применений БД выдвигает новые требования к

СУБД:

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

(включая фактографические, документальные, картинно-графические данные) ;

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

объектами предметных областей (например, пространственно-временных с

обеспечением визуализации данных);

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

обеспечение целостности БД в широком диапазоне разнообразных предметных

областей и операционных обстановок;

управление распределенными БД, интеграция неоднородных баз данных;

существенное повышение надежности функционирования БД. Вместе с тем

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

на ЭВМ общего назначения приводит к громоздким и непроизводительным

системам с недостаточно высокой надежностью. Тем более затруднительным

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

выше требования. Это обусловлено рядом причин:

фон-неймановская архитектура ЭВМ неадекватна требованиям СУБД, в частности

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

программным способом неэффективны как по производительности, так и по

стоимости;

многоуровневое и сложное программное обеспечение СУБД снижает эффективность

и надежность функционирования БД;

универсальная ЭВМ оказывается перегруженной функциями управлениями базами

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

систем;

централизация и интеграция данных в сетях персональных и профессиональных

ЭВМ нереализуема с приемлемой стоимостью без включения в состав сетей

специализированных ЭВМ для поддержки функции СУБД.

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

специализированных автономных информационных систем, ориентированных

исключительно на реализацию функций СУБД. Однако системы, реализованные на

обычной универсальной мини- или микроэвм, не способны полностью решить

указанные проблемы. Необходим поиск новых архитектурных и аппаратных

решений. Исследования в этом направлении привели к появлению-проектов и

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

назначением составляют также основу вычислительных систем 5-го поколения.

Машиной баз данных (МБД) принято называть аппаратно-программный

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

некоторых функций СУБД.

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

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

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

развитой теории реляционных баз данных и аппарата сведения к реляционной

других моделей данных обусловили разработку МБД, ориентированных в основном

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

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

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

операций реляционной алгебры.

Первые публикации по МВД появились в 1974 г., сейчас можно назвать более 50

проектов, некоторые уже реализованы в виде промышленных прототипов и

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

операций над базами данных проводятся и в нашей стране. Основными

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

функций СУБД и ожидаемое повышение производительности при их выполнении.

Это одинаково важно как для МБД, функционирующих совместно с главной ЭВМ в

составе единой вычислительной системы, так и для МБД, являющейся узлом

локальной сети (data computer). Во всех современных проектах и коммерческих

МБД реализован полный объем функций СУБД. Повысить производительность,

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

базы, можно только структурными методами (за счет структурного

распараллеливания). В силу этого МБД являются специализированными

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

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

настоящее время ведутся интенсивные исследования в этой области.

Основными техническими приемами, применяемыми в структурных методах

повышения производительности МВД, являются следующие:

использование многоканальных устройств массовой памяти (УМП) со встроенными

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

объемов перекачиваемых данных из УМП в обрабатывающие подсистемы;

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

и УМП, которая не только сглаживает разницу в скоростях обработки данных и

чтения их в УМП, но и уменьшает частоту обращения к УМП;

сегментация данных в УМП, которая увеличивает локальность доступа и

улучшает эффект двух предыдущих методов; с этой целью предполагается

развитие мультиатрибутной кластеризации и индексации данных в УМП и

аппаратная их поддержка;

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

алгоритмов обработки данных;

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

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

пространством данных;

реализация режимов параллельной интерпретации каждой операции над БД

(горизонтальный параллелизм типа SIMD) и режимов конвейерной и потоковой

обработки не только операций, но и транзакций в целом;

функциональная специализация процессоров обработки и их аппаратная

реализация в виде СБИС.

Основные направления развития структур МВД:

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

по структурным методам повышения производительности МВД: многопроцессорные

неоднородные (МН) и сетевые МВД. На рис. 1 приведены обобщенные

топологические схемы таких МВД. Частным случаем МН МВД можно считать

коммерческие МВД IDM-500, RS-310, iDBP 86/440, топологическая схема которых

приведена на рис. 2.

[pic]

Рис. 1. Топология двух классов МВД:

а - многопроцессорные неоднородные МВД с несколькими уровнями обработки

б - сетевые МВД

К МН МВД можно отнести большинство современных проектов МВД, таких как

DELTA, GRACE, DSDBS, MPDC, SABRE и др. Основными особенностями МН МВД

являются следующие.

1. Наличие нескольких уровней обработки данных, в частности, трех основных:

селекция и первичная фильтрация данных непосредственно в контрольных

устройствах массовой памяти;

вторичная обработка, заключающаяся в реализации операций реляционной

алгебры над вспомогательными отношениями, полученными на первом этапе;

[pic]

/\ - универсальный обрабатывающий /__/ -коммуникационный

процессор

процессор (серийный микропроцессор)

- специализированный -

коммутирующее устройство (общая

обрабатывающий процессор шина,

переключательная матрица,

О - локальная полупроводниковая память кольцевая коммутирующая

шина,

коммутирующая сеть)

- буферная общедоступная память - Управляющий

процессор (подсистема)

- устройство массовой памяти

с контроллером (НМД с контроллером)

Рис. 2. Топология коммерческих МБД

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

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

кластеризация) .

2. Наличие системной буферной памяти (СБП) между первыми двумя уровнями

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

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

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

первичной обработки (стадирование). СБП при этом обязательно должна быть

двух или более портовой.

3. Наличие функционального параллелизма, при котором различные функции

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

аппаратуре. При этом часть функциональных устройств реализуется на

универсальных микропроцессорах, часть в виде спецаппаратуры (например,

заказных СБИС). Функциональный параллелизм позволяет реализовать

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

случаях для увеличения производительности допускается дублирование

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

В качестве наиболее типичных примеров таких МН МВД можно рассмотреть DELTA

и GRACE. Японский проект МВД (рис. 3) лежит в основе вычислительной системы

5-го поколения. Действующий в настоящее время прототип состоит из двух

подсистем:

[pic]

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

(РП), одного процессора управления (УП), одного коммуникационного

процессора (КП) и одного процессора технического обслуживания (НТО),

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

и т. п.;

подсистемы иерархической памяти (ИЛ), содержащей системную буферную

память (электронный кэш-диск емкостью 128 Мбайт), массовую память с восемью

НМД (с контроллером магнитного диска КМД) общей емкостью 20 Гбайт и

четырьмя НМЛ (с контроллером магнитной ленты - КМЛ) , а также универсальную

микроэвм в качестве управляющего процессора иерархической памяти (УПИП) и

процессора ввода-вывода (ПЕВ). Связь между подсистемами осуществляется

высокоскоростным каналом со стандартным интерфейсом со скоростью передачи

до 3 Мбайт/с. Все процессоры подсистемы вторичной обработки подключаются к

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

памяти (АИП).

Основным функциональным узлом МЕД DELTA является реляционный процессор (РП)

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

отношениями произвольного объема с высокой производительностью. Каждый из

четырех РП может выполнять отдельную операции:

процессора (КП) и одного процессора технического обслуживания (НТО),

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

и т. п.;

подсистемы иерархической памяти (ИЛ), содержащей системную буферную

память (электронный кэш-диск емкостью 128 Мбайт), массовую память

с восемью НМД (с контроллером магнитного диска КМД) общей емкостью

20 Гбайт и четырьмя НМЛ (с контроллером магнитной ленты - КМЛ) , а так

же универсальную микроэвм в качестве управляющего процессора иерархической

памяти (УДИЛ) и процессора ввода-вывода (НЕЕ). Связь между подсистемами

осуществляется высокоскоростным каналом со стандартным интерфейсом со

скоростью передачи до 3 Мбайт/с. Все процессоры подсистемы вторичной

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

адаптеры иерархической памяти (АИП).

Основным функциональным узлом МЕД DELTA является реляционный

процессор (РП) баз данных, назначение которого-выполнение операций

реляционной алгебры над отношениями произвольного объема с высокой

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

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

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

РП имеет регулярную структуру (см. рис. 3) для облегчения его реализации в

виде СБИС. Кроме этого он в своем составе имеет центральный процессор (ЦП)

с памятью 512 Кбайт для реализации операций с обширной логикой (например,

агрегатных функций типа min, mах и т. п.). Для облегчения входного (ВП) и

выходного (ВЫП) потока данных РП содержит два адаптера иерархической памяти

(АИП), а также входной модуль для подготовки кортежей отношений (например,

перестановки значений атрибутов). Собственно операция реляционной алгебры

реализуется в РП. Процессор слияния (ПСЛ) сортированных сегментов отношений

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

реализуются операции естественного соединения двух отношений и селекции

отношения. Двенадцать процессоров сортировки (ПСО) предназначены для

реализации конвейерной однопроходовой сортировки сегмента отношения объемом

64 Кбайт. ПСО и ПСЛ реализованы полностью аппаратно.

Иерархическая память в DELTA является наиболее сложной подсистемой, в

функции которой входят:

управление СЕЛ и УМП;

стадирование данных (в виде сегментов отношений) из УМП в СБП в

соответствии с заявками РП;

селекция и вертикальная фильтрация отношений при помещении их в СБП с

привлечением специального (атрибутного) метода хранения отношений в УМП;

поддержка индексных структур, кластеризация отношений в УМП и организация с

их помощью быстрого поиска в УМП.

[pic]

Рис. 4. Структурная схема МВД GRACE

Вторым примером МН МВД является также японский проект GRACE, структурная

схема которого приведена на рис. 4. СБП реализована здесь набором

электронных дисков на цилиндрических магнитных доменах. В качестве УМП

использованы многоканальные НМД, в каждый канал которых встроены, кроме

устройств чтения-записи (Уч/з), процессоры первичной обработки, названные

фильтрами потока кортежей (ФПК). Каждый ФПК содержит:

процессор фильтрации (ПФ), осуществляющий в пределах дорожки МД

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

условию;

процессор проекции (ПП) и преобразования кортежей;

процессор хэширования (ПХ), реализующий динамическую сегментацию

кортежей читаемого отношения.

Фильтр потока кортежей работает в конвейерном режиме и позволяет

обрабатывать поступающие из УМП кортежи со скоростью их чтения (обработка

«в полете»).

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

обработки (ПВО) и ФПК. Назначение ФПК - выполнять описанную выше обработку

кортежей результирующих отношений, поступающих из ПВО в СЕЛ. ПВО содержит

наряду с процессором реляционной алгебры (ПРА), реализованным на основе

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

процессор сортировки отношений (ПСО) и процессор выдачи результата (ПВР) в

канал главной ЭВМ. ПСО осуществляет потоковую сортировку сегмента

отношения, поступающего из банка СЕЛ в процессор реляционной алгебры.

Двухпортовые банки СЕЛ подсоединяются к процессорам обработки обоих уровней

посредством специальных петлевых шин (СПШ). Эти многоканальные шины с

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

любого процессора обработки к любому банку памяти и одновременную обработку

нескольких банков памяти.

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

структурные решения.

1. Метод опережающей подкачки кортежей из УМП в СБП сочетает здесь не

только с первичной фильтрацией, но и со специальным распределением кортежей

по банкам СЕЛ. Эта так называемая динамическая хэш-сегментация позволяет

выполнять операции реляционной алгебры на уровне вторичной обработки

параллельно и без обменов несколькими ПPA, так что каждый ПРА реализует

бинарную операцию над парой соответствующих сегментов отношений-операндов.

Это является одним из источников повышения производительности МБД при

выполнении операций реляционной алгебры.

2. Включение в цикл вторичной обработки фильтров потока кортежей,

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

промежуточные отношения в СБП, так же как и исходные отношения БД,

единообразно интерпретировать последовательность операций реляционной

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

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

первичной и вторичной обработки.

3. Предварительная и параллельная фильтрация данных со скоростью их

поступления из УМП позволяет снизить объем перемещаемых из УМП в СБП

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

МБД в целом. Этот механизм используется во многих (если не во всех)

проектах МН МБД и считается признанным решением.

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

эффективной, если большая часть ее работает под управлением операционной

системы общего назначения. Поэтому повышение эффективности МБД связано с

полной изоляцией СУБД в рамках МВД, т. е. реализацией функционално-полных

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

соответствующей операционной системы МБД, реализовать функционально полную

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

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

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

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

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

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

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

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

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

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

Сетевые МВД (см. рис. 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. Создание ассоциативной памяти большой емкости для системного буфера

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

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

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

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

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

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

Примером такой памяти является изделие фирмы Сименс, структурная схема

подключения которого к общей шине представлена на рис. 12.а., Наличие порта

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

память через общую шину из УМП. Ассоциативная память в этом изделии

содержит 64 параллельные линии обработки (шириной 8 разрядов каждая), так

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

побайтно (в виде столбца байтов длиной 256 К). Длина обрабатываемого слова

256К, общая емкость ассоциативной памяти 16 Мбайт. Модуль памяти,

обрабатываемой каждым процессорным элементом, 256 Кбайт. Каждый модуль

памяти имеет адрес на общей шине, и информация в него может записываться

автономно по первому порту. Кроме того, внутри столбца-своя адресация в

пределах 256К, доступная контроллеру ассоциативной памяти. Ассоциативный

поиск осуществляется синхронно всеми (или частично) процессорными

элементами.

Структура каждого процессорного элемента изображена на рис. 12.б. Каждый

процессорный элемент содержит АЛУ и тест-устройство, два входных регистра А

и В, регистр маски М и блок регистров С. Все эти устройства выходят на

внутреннюю шину памяти (М-шину). Процессорный элемент и модуль памяти

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

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

постоянно фиксирует текущий адрес в пределах 256К, с которым 8 данный

момент работают процессорные элементы. Факт нахождения релевантной

информации в каждом процессорном элементе фиксируется в контроллере Для

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

эффективно реализуется операция поиска вхождений по заданному образцу.

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

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

[pic]

Рис. 12. Гибридная двухпортовая ассоциативная память:

а - общая схема; б - схема процессорного элемента

3. Использование процессора потоковой сортировки отношений для слияния

отношений. Например, в проекте Delta он предназначен для потокового слияния

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

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

реализовано устройство соединения двух отношений (Delta).

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

алгебры на основе универсальных компараторных процессоров (компараторов).

Пример такого компаратора (проект DFRU) представлен на рис.13. Компаратор

(К) предназначен для реализации операций селекции, проекции, сужения и

соединения отношений и используется в процессорной матрице (рис. 9). Он

имеет два буфера объемом, достаточным для помещения одного кортежа, и

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

Компаратор может находиться в разных состояниях, управляемых тремя

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

кортежами. Режим работы микропрограммы определяется текущим состоянием

компаратора. Компаратор содержит три микропрограммных процессора (модуля);

ввода, сравнения и выхода, и набор внутренних регистров (Доп. Р, БР).

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

кортеж побайтно в буфер или/и в компаратор (в зависимости от своего

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

управляющих битов (флагов), таких как признак окончания отношения, который

оканчивает обработку. В центральном компараторе происходит сравнение

значений заданных атрибутов из входных кортежей (побайтно). В компаратор

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

входной модуль по своей микропрограмме, синхронизируясь по заданному

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

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

команду на вывод кортежей из соответствующих буферов. Вывод может

осуществляться:

на выходную шину, если сравнение было успешным;

в линию обратной связи (ЛОС), если, например, из входного модуля по

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

отношения то же значение атрибута соединения (для операции соединения) и

этот выводимый кортеж надо повторно с ним сравнить. При этом

соответствующая входная линия перекрывается и замыкается на ЛОС, пока на

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

соединения;

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

сравнении (выходная линия замыкается на «землю»). Для операции соединения в

выходном модуле может выполняться сцепление выходных кортежей. Режим

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

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

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

этом определенная микропрограмма выполняется, если модуль находится в

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

[pic]

Рис. 13. Универсальный компараторный процессор для реляционных операций:

БР-а-разрядныа буферный регистр; Доп. Р - дополнительный регистр; К -

компаратор;

ЛОС - линии обратной связи

При выполнении операции селекции в Буфер 2 загружается «псевдокортеж»,

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

реализовать селекцию по условию, не содержащему дизъюнкций.) Кортежи

отношения, поступающие на Вх.1, пропускаются через компаратор, а

«псевдокортеж» циркулирует по ЛОС2, Буфер 2 и компаратору. Входной модуль

синхронизирует этот процесс. При успешном сравнении в компараторе кортеж

отношения посылается на Вых.1, иначе на «землю». Аналогично рассмотренному

реализован реляционный процессор РП (см. рис. 3) в МБД Delta, но с большим

разнообразием выполняемых функций.

4. Аппаратная реализация потоковой фильтрации данных непосредственно в

каналах УМП. Такая фильтрация позволяет снизить объемы данных, передаваемых

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

повышения производительности МБД в целом. Потоковые процессоры фильтрации

(фильтры) должны удовлетворять следующим требованиям:

скорость обработки должна соответствовать скорости чтения НМД, чтобы

избежать холостых оборотов МД;

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

дорожку МД для обеспечения непрерывности чтения;

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

условию данные (горизонтальная фильтрация);

возможность формировать на выходе часть входной записи в соответствии с

заданным условием (вертикальная фильтрация);

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

элементарных поисковых условий или в виде поисковых образов;

объем поисковых условий допилен определяться допустимой скоростью

обработки.

Достаточно полный обзор существующих процессоров фильтрации.

5. Устранение препятствия в увеличении производительности

многопроцессорной МБД с двумя уровнями обработки и системной буферной

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

с СБП и между собой. Это определяется интенсивностью обмена данными между

процессорами и СБП и объемом этих данных, которые, как правило, являются

частями файлов (отношений БД). Кроме этого организация параллельной работы

процессоров требует интенсивного обмена сообщениями между процессорами.

Ориентировочные требования к системе коммутации в МБД с высокой степенью

параллельности:

скорость передачи данных - 10-80 Мбайт/с;

число подключаемых автономных банков памяти - 100;

число подключаемых процессоров обработки - 100;

отсутствие конфликтов.

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

высокоскоростных сетей коммутации (до 10^3 входов) и реализации на их

основе многопортовой системной буферной памяти для МВД.

Фильтры представляют собой технические или программные средства для

выделения данных, удовлетворяющих каким-либо условиям. В реляционной модели

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

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

выбрать текст, содержащий данное слово. Те же задачи выбора данных по

условию могут решаться и с помощью использования циклов или хэширования.

Фильтры, однако, позволяют проверять более сложные условия, чем «равно»

(для хэширования возможна только такая проверка), «не равно», «больше»,

«меньше». Фильтры не требуют предварительной структуризации данных. Вместе

с тем использование фильтров предполагает полный просмотр отношения (или,

если в базе хранятся инвертированные файлы, полный просмотр значений

атрибутов, участвующих в условии). Фильтры могут применяться и в комбинации

с индексированием и хэшированием.

Общая схема использования фильтров следующая. Процессор, анализирующий

запрос, выделяет условие селекции. Выделенное условие передается в

специальный процессор (или группу процессоров), который является

программируемым фильтром. Этот процессор может быть как специализированным,

так и процессором общего назначения.

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

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

Отобранные (релевантные) кортежи передаются другим процессорам для

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

фильтра.

В ряде проектов МЕД используются фильтры, которые моделируют для

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

условия практически не зависит от его сложности (если размер памяти

фильтра достаточен для моделирования конечного автомата, проверяющего

условие)

Бинарные операции (объединение, пересечение, соединение) над

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

фильтров.

Специализироьанный фильтр работает приблизительно в два раза быстрее,

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

фильтр может читать уже загруженную часть памяти. Кэш-память служит

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

Когда в качестве фильтрующего процессора используется процессор общего

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

входного файла поочередно в один из двух буферов. Загрузка ведется

непосредственно с диска, так как фильтрация идет приблизительно в три раза

медленнее чтения. Кэш-память в этом случае не нужна. Результат фильтрации

записывается в один из двух выходных буферов. По заполнении буфера его

содержимое сбрасывается на диск.

К недостаткам фильтров, моделирующих конечные автоматы, следует отнести

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

Другой способ проверки Условий осуществляется прямым фильтром, структура

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

фильтра являются компаратор, управляющее устройство и логическое

устройство. Компараторы проверяют истинность простых условий. Их число

ограничено и фиксировано в аппаратуре. Современная технология СБИС

позволяет строить прямые фильтры с числом компараторов порядка 100.

Управляющее устройство организует работу фильтра, логическое устройство

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

истинности сложного условия. На вход компаратора подается запись вида

или

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

является признак ИСТИНА или ЛОЖЬ.

Передаваемое в фильтр формализованное условие представлено в

дизъюнктивной или конъюнктивной нормальной форме. Для определенности будем

говорить далее о дизъюнктивной нормальной форме. В этом случае условие

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

условий. На каждом шаге компаратор проверяет очередное простое условие, и

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

условия.

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

очередное промежуточное значение окончательного результата по результату

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

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

компараторов и логических блоков.

Управляющее устройство выполняет следующие функции:

декодирование, вычисление длины операндов и подготовка данных к

вычислениям;

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

управление входным и выходным буферами. Входной буфер не является

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

основной памяти.

Операнды проще всего размещать во внешней памяти, общей для всех

компараторов. Время обращения к общей памяти налагает в этом случае

ограничения на число компараторов в фильтре. Если время ввода одной записи

100 не, а время работы компаратора 400 не, то нет смысла иметь более

четырех компараторов. Использование СБИС-технологии позволяет обеспечить

каждому компаратору достаточную внутреннюю память (порядка 256 байт).

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

МВД.

1. Повышение эффективности хранения данных в больших БД часто связывают

со сжатием данных, специальным кодированием данных и т. п. Но

псевдоассоциативный поиск и фильтрация данных непосредственно в УМП трудно

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

только в единственном проекте DS DBS предпринята попытка решить эту

проблему.

2. При разработке МЕД совсем не рассматривается проблема обеспечения

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

дисплея. Если терминалы работают под управлением МБД, то сложность ОС МБД

существенно возрастает, что может привести к деградации общей

производительности МБД. Если терминалы пользователя работают под

управлением главной ЭВМ, то растет объем данных, передаваемых от МБД в

главную ЭВМ и наоборот.

3. Повышение производительности МВД обычно связывается со скоростью

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

транзакций. При этом выдача данных терминальному пользователю начинает

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

последовательности операций, соответствующих запросу. Иногда для принятия

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

последовательности (дерева запроса). Увеличение реактивности МБД при выдаче

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

увеличению традиционной пропускной способности МВД. Решить эту проблему

можно только реализацией в МВД такого режима потоковой обработки отношений,

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

ожидая появления целиком сформированных отношений-операндов. Для ряда

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

отношений-операндов) реализация такого режима трудно разрешима, например

для операции сортировки отношений.

4. Обеспечение целостности БД при параллельных обновлениях в МВД с

высокой степенью внутреннего параллелизма, а также живучести таких систем и

их надежного функционирования-также серьезная проблема.

5. Разработка единой методологии проектирования МВД исходя из заданного

набора требований (объем и тип БД, типы и частота запросов, сфера

применения и т. п.). В настоящее время проектирование МВД основано на

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

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

Наличие указанных проблем в проектировании МВД заставляет некоторых

авторов на вопрос «Существует ли идеальная МБД?» ответить следующим

образом: «Идеальная МБД, если она существует, должна быть, очевидно,

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

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

Лучшей рекомендацией в данном случае является разработка семейства МВД,

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

применения. Например, мультипроцессорная машина псевдоассоциативного поиска

в больших файлах библиографических систем или многопроцессорные МВД для

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

логического вывода, или функционально полные МВД коммерческого типа для

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

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

ЭВМ.