БАЗЫ ДАННЫХ И БАЗЫ ЗНАНИЙ —
УДК 519.687.1
МЕТОД АДАПТИВНОГО УПРАВЛЯЕМОГО ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ОПЕРАЦИЙ В ОБЪЕКТНЫХ СУБД
© 2008 г. Р. С. Самарев
Московский государственный технический университет им. Н.Э. Баумана 105005 Москва, ул. 2-я Бауманская, 5 E-mail: samarev@acm.org Поступила в редакцию 29.11.2006 г.
При разработке параллельных СУБД, как правило, подразумевают специализированные многопроцессорные вычислительные комплексы. Причем чаще всего предполагается монопольная работа СУБД. Однако в классе многопроцессорных вычислительных систем с архитектурой х86, ориентированных на массового потребителя, монопольность СУБД по отношению к другому программному обеспечению часто не обеспечивается. Кроме того, унаследованное программное обеспечение для данного класса вычислительных систем часто не предназначено для массового параллельного выполнения. Игнорирование требования немонопольной работы и неиспользование ресурсов ВС в режимах малой нагрузки СУБД являются причинами неэффективного использования ресурсов вычислительной системы в целом. В статье рассматривается метод программной организации управляемого параллелизма на уровне внутренних операций СУБД, обеспечивающий их контролируемое выполнение с учетом состояния вычислительной системы в целом. Разработанный метод позволил существенно снизить время отклика при малых плотностях поступления запросов в коммерческой объектной СУБД ODB-Jupiter, разработанной в НПЦ "ПНТЕЛТЕК ПЛЮС". Разработанный метод управляемого параллельного выполнения может применяться в широком классе программных систем.
1. ВВЕДЕНИЕ
Массовое использование недорогих многопроцессорных вычислительных систем с архитектурой х86 привело к тому, что задача параллельного выполнения программ стала актуальной не только для традиционных систем без общих ресурсов типа специальных многопроцессорных вычислительных комплексов (МВК) и кластерных систем, но и для этого растущего класса серверных систем. Однако применяемые унаследованные программные продукты (ПП) далеко не во всех случаях используют предоставляемые ресурсы системы. Следствием этого является явное несоответствие возможностей вычислительной системы и характеристик производительности неоптимизированных ПП, алгоритмы работы которых не были рассчитаны
на использование нескольких процессоров. Это же относится и к большинству СУБД, разработанных для ВС с архитектурой х86, не рассчитанных на параллельное выполнение одиночных запросов, в то время как ненасыщенный режим работы чаще всего является основным. Неэффективное использование ресурсов ВС приводит к тому, что обеспечение требуемого времени отклика СУБД в ненасыщенных режимах возможно только путем экстенсивного наращивания производительности отдельных процессоров, а их количество влияет только на производительность СУБД в режиме полной загрузки. В итоге получается, что в среднем вычислительная система будет серьезно недогружена. Другой проблемой при работе параллельных программ является то, что одновременное обраще-
Среда выполнения запроса (УМ1)
1) Трансляция запроса в план выполнения
2) Оптимизация и упорядочивание
3) Последовательная постановка микроопераций на выполнение и сбор результатов их обработки
4) Возврат результата
Инородные для СУБД программы с неизвестными характеристиками потребления системных ресурсов
Обработчик
Запрос 1
Обработчик
Диспетчер
Обработчик
Обработчик
Запрос N
УМ N
Г I
| Параллелизатор |
Тип N
Обработчик
Обработчик
Тип 1
Тип 2
Рис. 1. Обобщенная схема обработки запросов.
ние нескольких процессов к ряду системных ресурсов приводит к серьезному снижению производительности ВС в целом. К примеру, задача устранения проблемы нехватки ОЗУ при конкурирующем доступе нескольких потоков/процессов для операционных систем чаще всего решается путем вытеснения наиболее старых данных из ОЗУ в файл подкачки, вызывая непрерывный медленный файловый обмен и неконтролируемую деградацию производительности ВС. В то же время эта проблема может быть решена гораздо эффективнее путем приостановки обработки следующей порции данных в тот момент, когда предыдущие порции еще не обработаны, не вызывая нехватку ОЗУ. Таким образом, линейное увеличение количества параллельных процессов в различных программах приводит к нелинейному снижению производительности системы в целом. К аналогичным последствиям приведет неограниченное параллельное выполнение запросов СУБД при их высокой входной плотности. Решение проблемы монопольного использования систем с мас-
совым параллелизмом принято выполнять организационно, что рамках одной СУБД позволяет контролировать степень параллелизма самостоятельно. Для массовых серверов архитектуры х86 требование монопольного использования ВС часто не выполняется.
Следовательно, оптимальной СУБД с точки зрения производительности будет такая СУБД, которая способна максимально использовать доступные в данный момент ресурсы ВС с учетом того, что превышение некоторого предела загрузки приведет к релейному замедлению ВС в целом. На рис. 1 приводится схема обработки запросов в СУБД в немонопольном режиме.
Теоретические вопросы параллельного программирования в настоящее время хорошо проработаны для вычислительных систем специального назначения, а также для случая монопольного выполнения ПП на ВС [4], однако далеко не все методы могут быть применены для вычислительных систем общего назначения в условиях совместного использования ресурсов ВС несколькими ПП.
Традиционно в работах, посвященных параллельным вычислениям, рассматриваются идеальные случаи, когда выполняемая программа работает в монопольном режиме на некотором вычислительном комплексе. В ряде работ по анализу параллельных алгоритмов, например, в [3], рассматривается не просто режим работы, монопольный относительно программ прикладного уровня, но и монопольный по отношению к операционной системе. Т.е. в этом случае можно определить, какой процессор и в какой момент времени будет выполнять тот или иной оператор программы. Ясно, что в случае современного прикладного уровня программирования это потребовало бы замены планировщика ресурсов операционной системы для эффективного упорядочивания выполнения операций, а также требует выполнения анализа всего ПО, которое может быть запущено на выполнение на данной ВС.
Особый класс параллельных систем представляют собой вычислительные системы с массовым параллелизмом. В данное понятие можно условно объединить как многопроцессорные комплексы, в которых каждый процессорный модуль имеет собственный банк памяти, собственный контроллер диска и собственный жесткий диск, так и кластерные системы с узлами любой архитектуры [7, 10]. Поскольку к массовым потребителям такие архитектурные особенности в ближайшем будущем не придут, то методы параллельного программирования, применимые для них, следует рассматривать с осторожностью.
Следствием монопольного выполнения программы является то, что ресурсы системы предполагаются постоянными. В то же время, нет никаких гарантий того, что сторонняя программа не займет все доступные ресурсы ВС, при том, что для нашей программы такая ситуация не предусмотрена.
Таким образом, при решении задач прикладного программирования следует:
- использовать все доступные ресурсы вычислительной системы;
- учитывать, что состав доступных ресурсов ВС не постоянен, так как в любой момент времени может быть запущен или остано-
влен любой системный процесс, например, совместно с нашей СУБД поступил запрос WEB-серверу;
- иметь возможность предотвращения деградации производительности вычислительной системы.
Решение всех этих проблем в полной мере в настоящее время не обеспечивается ни операционными системами типа MS Windows/Linux, ни специализированными библиотеками для реализации параллельных программ типа MPI, Open MP [4].
Актуальность разработки нового метода параллельного выполнения обусловлена тем, что, несмотря на наличие большого количества работ в области параллельных баз данных, они, в основном, ориентированы на использование специализированных ВС [7, 8, 10]. Отличием данной работы от других является то, что разработанный метод параллельного выполнения предназначен для использования на ВС общего назначения, т.е. многопроцессорной системе с общими ресурсами в немонопольном режиме. В прикладном аспекте метод применен для объектной СУБД ODB-Jupiter [1, 2]. Следует заметить, что крупные компании, такие, как Oracle, IBM и Microsoft, также ведут разработки в области параллельных СУБД для систем общего назначения, однако открытой информации об их реализации нет. Необходимость решения задач параллельной обработки данных для таких систем обусловлена тем, что в последнее время в связи со значительным снижением стоимости оборудования многопроцессорные системы доминируют на рынке серверов, что требует от СУБД эффективного использования всех доступных ресурсов.
2. ВЫБОР СХЕМЫ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ
Формы параллелизма, используемые в СУБД, подробно рассмотрены в работах [6, 7, 9, 10]. Коротко следует отметить, что применяется как параллелизм между запросами при их последовательном внутреннем выполнении, так и различные виды внутризапросного параллелизма,
обеспечивающие как параллельное выполнение одной и той же микрооперации сервера БД над разными данными, так и параллельное выполнение разных микроопераций с разными данными. Кроме того, различают конвейерные и неконвейерные методы обработки.
В большинстве коммерческих параллельных СУБД для обработки больших объемов данных исторически применяется конвейерный принцип. С позиции способа параллельного выполнения, различают два основных принципа - скобочный (bracket model) и операторный (operator model) [6, 7]. Однако в отношении унаследованных последовательных СУБД часто применяются неконвейерные методы обработки, поскольку задача преобразования программ, реализующих последовательные алгоритмы в параллельные конвейерные, по сложности соизмерима, а часто превосходит разработку конвейерных алгоритмов с нуля. В то же время, неконвейерный параллелизм часто является достаточным для улучшения характери
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.