Содержание к диссертации
Введение
1. Анализ существующих методов построения параллельных субд и ис на их основе, анализ методов моделирования 13
1.1. Анализ существующих методов построения параллельных субд. особенности организации 13
1.1. L Модели данных 14
1.1.2. Схема данных и языки запросов 16
1.1.3. Архитектура ВС для СУБД 21
1.1.4. Методы размещения данных 24
1.1.5. Транзакциотtan обработка данных 27
1.1.6. Блокировка данных т 30
1.1.7. Методы организагщи параллельного выполнения запросов 32
1.1.8. Архитектура взаимодействия клиента и сервера СУБД. 39
1.2. Анализ методов моделирования производигельностиис 42
L2.1. Анализ математических методов моделирования 42
1.2.2. Применение методов моделирования для оценки характеристик производительности СУБД 72
1.2.3. Средства моделирования СУБДиИС 86
1.3. Анализ осу бд odb-jupiter как объекта исследования 88
1.3.1. ИПС «Обзор СМИ» 94
1.4. Выводы 96
2. Разработка метода моделирования производительности ис, использующей СУБД. 99
2.1. Расширение свойств алгеьрырера 99
2.1.1. Формальное определение алгебры прогщссов 99
2.2. Решение моделей 102
2.2.1. Генерация сокращенной марковской цепи 103
2.2.2. Генерация полной марковской цепа 104
2.3. Весовое расширение алгебры 105
2.3.1. Структурные и параметрические ограничители 108
2.3.2. Выбор факторов в векторе потребления ресурсов ПО
2.3.3. Анализ целесообразности введения операции взаимоисключения вРЕРА 130
2А Модели пюизводительности ис, использующей СУБД 133
2.4. 1. Модель выполнения запросов 133
2.4.2. Анализ обработки запросов в ОСУБД QDB-Jupiter и ИПС «Обзор СМИ» 135
2.4.3. У прощенная модель сервера СУБД 142
2.4.4. Модель запросов подсистемы поиска 143
2.4.5. Полная модель ИС 149
2.4.6. Модели пропускной способности подсистемы памяти 153
2.4.7. Модель дляоценки чиелаобработчиковпараллелизатора 159
2.5. ВЫВОДЫ 163
3. Улучшение характеристик производительности субд с использованием адаптивного планировщика параллельных запросов 164
3.1. Разработка параллелизатога запросов 167
3.1.1. Синхронное адаптивное управление 172
3.1.2. Асинхронное адаптивное управление 176
3.1.3. Выбор параллельного планировщика, .179
3.1.4. Оценка применимости выбранных параметров
планировщика для идентификации состояния системы 184
3.2. Реализация модуля параллелизатора 192
3.3. Выводы 197
4. Методики проектирования параллельных СУБД 198
4.1. Методика реорганизации субд в соответствии с заданными характеристиками 198
4.2. Методика нагрузочного тестирования сервера осубд В составе ис 199
4.3. Методика оценки характеристик производительности Ис на основе субд 201
4.4. Методика разбиения последовательного кода программы на независимые 202
4.5. Методика параметризации моделей для различных вс с различными методами доступа к озу 203
4.6. Метод использования параллелизатора в тексте программ 205
4.6.1. Пример применения метода 205
4.7. Применение методики нагрузочного тестирования сервера осубд в составе ис 207
4.7J. Выбор средства анализа программного кода. 207
4.7.2. Выбор метода измерения временных интервалов 208
4.7.3. Трассировка выполнения программы 209
4.7.4. Выбор способа организации синхронизации потоков 213
4.7.5. Организация нагрузочного тестированияИС. 215
4.7.6. Измерение показателей ИС 217
4.7.7. Съем данных с реальной системы 218
4,8. Выводы 219
5. Выполнение модельных и натурных экспериментов, анализ результатов 221
5.1.. Выполнение модельного эксперимента с разработанными моделями 221
5.1.1. Модель запросов подсистемы поиска по реквизитам 221
5.1.2. Модели пропускной способности подсистемы памяти 223
5.2. Анализ результатов моделирования 225
5.2.1. Эксперимент и моделирование подсистемы полнотекстового поиска ИС 225
5.3- Анализ экспериментальных данных 231
5.4. Выводы 236
6. Заключение 237
7. Общие выводы 238
8- Литература
- Методы организагщи параллельного выполнения запросов
- Генерация полной марковской цепа
- Асинхронное адаптивное управление
- Методика разбиения последовательного кода программы на независимые
Введение к работе
Актуальность темы
Интенсивное развитие вычислительной техники в последние годы, привело к массовому использованию многопроцессорных высокопроизводительных вычислительных систем (ВС) общего назначения. Тем не менее, применяемые ранее разработанные (унаследованные) СУБД, обычно неэффективно используют предоставляемые ресурсы ВС. Несмотря на то, что межзапросный параллелизм в СУБД используется часто, внутризапросные формы параллелизма в унаследованных СУБД практически не используются. Следствием этого является явное несоответствие возможностей ВС и производительности неоптимизи-ровашюй СУБД, не рассчитанной на параллельное выполнение одиночных запросов- В результате, при малой плотности запросов, СУБД может использовать лишь минимально необходимое количество ресурсов системы, так что, в конечном счеге, добавление новых процессоров или параллельных дисковых накопителей не приводнт к какому-либо улучшению её характеристик. Если же при выборе оборудования ориентироваться на пиковую нагрузку, то в среднем вычислительная система будет серьезно недогружена.
Другой проблемой использования СУБД является то, что монопольное использование вычислительной системы не всегда возможно. В большинстве малых и средних коммерческих организациях, на ВС, на которой работает СУБД, работают и другие программы, также требующие значительных ресурсов. При малой плотности запросов к СУБД, влияние других программ может быть незначительным, однако, например в случае использования СУБД в сочетании с Web-сервером, вполне возможна ситуация полной загрузки вычислительной системы. Операционная система, типа MS Windows на ВС с вытесняющей многозадачностью с архитектурой х8б, не способна оптимально разрешить ситуацию одновременного использования процессора или НЖМД при большом количестве одновременно работающих процессов/потоков. Таким образом, линейное увеличение количества параллельных процессов в различных программах приводит к нелинейному снижению производительности системы в целом, поскольку доля служебных операций по переключению потоков, вытеснению памяти, позиционированию головок НЖМД на нужный сектор занимает значительное время. К аналогичным последствиям приведет неограниченное параллельное выполнение запросов при большой их входной плотности [114].
В настоящее время широко распространены параллельные СУБД для вычислительных систем без общей памяти, однако, массовое использование архитектуры х86 не позволяет использовать классические параллельные СУБД в чистом виде. Кластер, построенный путем объединения отдельных х86-систем, можно рассматривать как единую систему, с несколькими независимыми узлами, не имеющими общей памяти. При этом каждый узел може г быть многопроцессорным, что требует реализации соответствующих алгоритмов, а кроме того, создание кластера на х86 требует организации быстродействующего межпроцессорного обмена данными, что также является проблемой.
Итак, оптимальной СУБД с точки зрения про изводи тел ьности и времени отклика будет СУБД, реализующая впутризапросный параллелизм, причем доступные в данный момент времени ресурсы ВС используются максимально, но с учетом того, что превышение некоторого предела загрузки ВС приведет к релейному падению производительности системы в целом.
Рассмотрим актуальность проблемы моделирования производительности СУБД и РІС на их основе. На рис. 1 приведена обобщенная схема анализа производительности СУБД.
Моделирование характеристик СУБД актуально в следующих случаях:
- Создание новой СУБД;
- Проверка допустимых режимов работы существующей СУБД;
- Выполнение оптимизации работы существующих приложений.
Архитектура СУБД наиболее существенно влияет на производительность будущих систем, построенных с применением данной СУБД. Поэтому целесообразно проводить моделирование работы СУБД и возможных последствий от введения каких-либо элементов архитектуры СУБД на ранних стадиях разработки. Кроме того, существует возможность оценить возможные области применения СУБД по предельно допустимым режимам работы.
В случае, когда СУБД уже разработана, необходимо знать ее допустимые режимы эксплуатации (типы приложений и наборы операций, которые не приведут к снижению производительности), а также иметь возможность оценивать требуемые параметры оборудования, такие как быстродействие процессоров, дисков, их количество, схему объединения в кластер и пр.
Если СУБД находится в эксплуатации, уже разработаны ее приложения, и выясняется, что имеющаяся ВС не обеспечивает необходимого уровня производительности, либо необходимую ВС невозможно реализовать на данном уровне развития техники, то либо требуется полное проектирование новой системы, либо проведение оптимизации характеристик существующей. Среди способов оптимизации производительности можно выделить использование специальных подсистем кэширования, которые обеспечивали бы не только хранение информации, полученной из медленных источников данных, по и хранение промежуточных результатов, а также изменение структуры индексов, в частности за счет введения не только одномерных индексов, но и создание многомерных индексов под конкретный набор операций [75]. В общем случае требуется существенная переработка архитектуры СУБД в целом и механизмов обработки запросов в частности.
Цели и основные задачи
Целью работы является разработка методов и моделей проектирования параллельных СУБД и их приложений с заданными характеристиками, а также оценка предельных характеристик СУБД и приложений. Для достижения поставленной цели в работе решаются следующие задачи:
- Анализ параллельных архитектур СУБД и методов повышения эффективности использования системных ресурсов. Выбор критериев производительности СУБД.
- Разработка алгебраической модели параллельной объектной СУБД. Метод оценки характеристик производительности систем на основе СУБД.
- Моделирование и исследование свойств модели.
- Разработка параллелизатора запросов для асинхронного выполнения операций в СУБД
- Разработка метода измерения производительности реальной системы.
- Создание инженерных методик реорганизации СУБД в соответствии с заданными характеристиками с использованием предложенных моделей. Исследование характеристик производительности систем на основе СУБД с использованием этих методик. Реализация методик для улучшения характеристик сервера ОСУБД.
Объект исследования
Обьектом исследования является класс систем, предназначенных для работы на многопроцессорных ВС общего назначения, включающих в себя объектные системы управления базами данных, в частности ОСУБД ODB-Jupiter и ИС на её основе.
Предмет исследования
Предметом исследования является анализ процессов обработки запросов в параллельных объектных системах управления базами данных и информационных систем на их основе.
Научная новизна
В работе получены следующие новые результаты:
На основе стохастической алгебры процессов "РЕРА" (англ.) разработан метод, позволяющий проводить расширенный анализ сложной информационной системы на основе алгебраических моделей, включая анализ по каждому параллельному процессу в отдельности, а также весовое расширение "PEPА", позволяющее анализировать модель с позиции потребления различных ресурсов системы, описываемых как многомерный вектор.
Разработана комплексная модель сервера ОСУБД ODB-Jupiter, а также модели отдельных подсистем с использованием алгебраического подхода.
Разработан метод параллельного выполнения внутренних операций с учетом доступных ресурсов ВС па момент начала обработки.
Методы организагщи параллельного выполнения запросов
Для непосредственного выполнения запроса необходимо построение физического плана, т.е последовательности конкретных операций над конкретными данными. СУБД транслирует оптимизированный (по времени выполнения или потреблению ресурсов) логический план в физический. На этапе построения физического плана выполнения выбираются точки синхронизации и передачи данных, обработчики, узлы обработки и пр. Формальное описание физического плана выполнения производится физической алгеброй запроса, отличием которой от логической является набор операторов (часто более короткий), однозначно соответствующих реальным действиям сервера БД [97, 61 ].
В соответствии с классификаций, приведенной в работе [123], существует два ортогональных метода параллельного выполнения сложных запросов в СУБД (на примере IBM DB2) - программный параллелизм и параллелизм данных.
- Программный параллелизм предполагает параллельное выполнение операций, таких как сканирование таблиц, слияние над неделимым пространством данных.
- Параллелизм данных предполагает возможность параллельного выполнения указанных выше операции за счет того, что пространство данных фрагмен-тировано, а операции могут выполняться независимо над каждым фрагментом данных.
В работе [61] представлена детальная классификация методов параллелизма, краткая иллюстрация которой приведена на рис 1.2.
Межтранзакционный параллелизм подразумевает выполнение отдельных транзакций в рамках одной БД. Данный вид параллелизма тесно связан с проблемой многопользовательской обработки запросов на однопроцессорных системах, поскольку предполагает только блокировку ресурсов СУБД. Является наиболее простым видом параллельной обработки и эффективен при большой плотности запросов.
Внутритранзакционный параллелизм подразумевает параллельное выполнение запросов в рамках одной транзакции. Эго приводит к снижению времени выполнения транзакции. Применение методов впутритраизакциопного распараллеливания целесообразно в тех случаях, когда необходимо либо минимизировать время отклика, либо обеспечить приоритетное выполнение запросов. Различают несколько форм внутритранзакционного параллелизма.
Межзапросный параллелизм подразумевает параллельное выполнение запросов в рамках одной транзакции. Его реализация в общем случае затруднительна, поскольку требуется явное указание зависимостей между запросами. Межзапросный параллелизм в коммерческих СУБД применяется редко.
Внутризапросный параллелизм подразумевает выполнение запроса посредством его разбиения на элементарные операции и их параллельное выполнение. Трансляция логического плана выполнения запроса в физический парал лельный план проводится в независимости от пользователя, сформировавшего запрос. Внутризапросный параллелизм может быть реализован как межоперационный (interoperator) или внутри операционный (intraoperator) параллелизм. В соответствие с [97] внутриоперационный параллелизм разделяют на вертикальный и горизонтальный.
Вертикальный паралеллкзм подразумевает создание конвейерного обработчика запросов, в котором операторы в порядке последовательного физического плана выполнения запроса обрабатывают данные порционно следующим образом. После того как порция данных обработана, результат передается следующему оператору, а текущий оператор продолжает обработку следующей порции.
Горизонтальный параллелизм предполагает, что исходный физический план может быть представлен как дерево независимых операций. Другое название данного метода -кустовой (bulk) параллелизм- Операторы в независимых поддеревьях могут выполняться параллельно.
Основной формой внутриоперациопиого параллелизма является фрагментарный параллелизм, сутью которого является разбиение массива данных на фрагменты и их независимое выполнение. Условно различают горизонтальный фрагментарный параллелизм - разделение по кортежам и вертикальный фрагментарный параллелизм - разделение по атрибутам.
На рис 1.3 приведена иллюстрация трансляции запроса в физический план и алгоритм выполнения с горизонтальным (получение списков ключей объектов si и s2) и фрагментарным (расщепление операции проекции элементов найденных объектов на 3 одинаковых интервала и их одновременная обработка) параллелизмом, применительно к объекту исследования данной работы.
Генерация полной марковской цепа
Расширим рассмотренный в [92] способ получения промежуточной марковской цепи. Обычным для алгебры процессов РЕРА является генерация марковской цепи, в которой переходы между двумя состояниями, вызванные одним типом действий, но разными процессами, заменяется одним переходом с суммарной интенсивностью. Однако наличие уравнения системы, в котором применяются только статические комбинаторы процессов при фактическом запрете на их использование в описании одного процесса, позволяет получить не только суммарную интенсивность, но и вклад каждого отдельного процесса в кооперирующей их системе. Это позволяет получить ряд дополнительных возможностей использования РЕРА, не предусмотренных в работах ее авторов. Среди них - возможность учета производительности для любого типа действия по любому процессу, а также возможность раздельного анализа каждого процесса.
Уравнение системы Sys есть функция кооперации по множеству динамических компонентов Р, каждый из которых представляет собой процесс:
Процесс есть последовательность компонентов !\ = {С ...С }, где СГА- элементарный компонент процесса /, определяющий действия для перехода к следующему компоненту, причем С/ є ds(Pk) .
Определим понятие условного множества активных действий компонента Лс/(С;(С «С}}) = Кроме того, действие асі есть некоторое действие номер qy принадлежащее к-му процессу. Таким образом, интенсивность перехода q(CirCj) между компонентами С, и С; определяется как д{С„С .) = 5] 5/j , где С и С; есть компоненты, соот ветствующие ft-му процессу.
Расширийі алгебру процессов РЕРА. В работах [79, 74] рассматриваются методы введения в алгебры процессов дополнительной информации, однако большинство таких расширений изменяет операционную семантику базовой алгебры. Разработанное здесь расширение не меняет аксиоматику и операционную семантику алгебры.
Естественным следствием анализа модели РЕРА по каждому процессу является ассоциация каждого перехода марковской модели с набором действий, которые становятся активными в этот момент. Поскольку в рамках марковской цепи, генерируемой по модели РЕРА, один переход между соседними состояниями может быть ассоциирован лишь с одним действием, другие процессы, комбинируемые в данном состоянии кооперацией, также имеют возможные переходы, ассоциированные со своими действиями. Причем, поскольку в алгебре РЕРА невозможен возврат процесса к предыдущему состоянию иначе как предписанным моделью циклом, получается, что статический комбинатор кооперации, сохраняя в любом состоянии фиксированный набор процессов и их взаимное положение, дает множество возможных комбинаций действий по всем процессам. Запишем формально данное положение.
Множество возможных комбинаций активных действий в любом состоянии системы 5 wr Г/ Г] есть декартово произведение условных множеств активных действий по компонентам всех процессов системы: xAct(cljk2\fa{cHh,c В общем случае CAct({Chi,,- )) = {RAct RAcJ RActJ, где RAciQCih элементарное множество действий по различным процессам уравнения системы.
Каждый столбец матриц определяет предельный условный объем некоторых ресурсов виртуальной вычислительной системы VMfo на которой выполняется конечное множество процессов (Ргосм, Ргосм—Ргосц}.
Действие характеризуется определенным типом и является неделимым, переводящим систему в другое состояние. Различают активные и пассивные действия. Каждый тип действия a-s характеризуется параметром вектором по требления ресурсов acia = г кг ! л , где rsn есть величина потребления j-ro ресур r uki са, t4 есть среднее время, за которое происходит потреблепие ресурса
Асинхронное адаптивное управление
Рассмотрим функциональную схему модуля асинхронного управления параллелизмом (рис. 3.9). Главное отличие асинхронного управления заключается в том, что коррекция критериев управления производится независимо от потока заявок. Преимуществом данного метода коррекции перед синхронным является меньшее использование ресурсов ВС на определение состояния системы и принятия управляющего решения, а также более простой алгоритм оценки возможности постановки на обработку. Недостатком является потенциально более низкая точность управления» поскольку таймер корректора обеспечивает проверку состояния ВС с многократно более низкой интенсивностью, чем поступают входные заявки. В данном случае, планировщик представляет собой модуль, обеспечивающий планирование на основе статических критериев, таких как вектор максимально допустимых ресурсов, а подстройку этих критериев производит модуль корректора. Решение об изменении числа параллельных обработчиков также принимается корректором.
Функциональная схема асинхронного адаптивного параллелизатора
Поскольку корректор сильно зависит ог используемой архитектуры RC и применяемого параллелизатора системы, данную функциональную схему еле дует рассматривать лишь как пример конкретной реализации возможного асинхронного управления, использованного в ОСУБД ODB-Jupiter,
Аналогично рассмотренным ранее схемам работы параллелизаторов с синхронным управлением, заявки поступают в соответствующие их типу входные очереди, откуда изымаются свободными обработчиками. Однако, момент постановки заявки на выполнение может быть задержан до момента появления требуемых ресурсов.
ВС представляется в планировщике двумя векторами - вектор Wcur - текущее использование ресурсов и вектор Wsy - вектор доступных ресурсов. Под ресурсом здесь понимается некоторая численная величина, которая, в общем случае, может и не иметь реальной физической интерпретации, такой как скорость обмена данными, процент использования и пр. Любая заявка для выполнения требует определенных ресурсов, описываемых вектором Wop. Частным критерием постановки заявки на выполнение является неравенство 0 + V/ (3.1), где і - номер элемента вектора (общий критерий будет рассмотрен позже). Следует отметить возможность рекурсивной постановки заявок из обработчиков, требующей ожидания окончания выполнения. Для исключения возможности мертвой блокировки детектор рекурсивного вызова планировщика в момент ожидания окончания обработки установленной заявки временно высвобождает ресурсы, выполняя операцию W =WLitr-w ii где w - вектор использования ресурсов временно приостановленного потока. После получения результата обработки, планировщик возобновляет работу потока и выполняет операцию " cvr іиг tip После завершения обработки заявки, обработчик сообщает планировщику о высвобождении ресурсов, связанных с этой заявкой и помещает результат обработки, если он есть, в выходную очередь.
Корректор в данной системе активируется по таймеру, проводя две независимые проверки. Первая- контроль достаточности количества параллельных обработчиков каждого типа. Вторая - оценка текущего состояния ВС по некоторым внешним характеристикам и сопоставление их с представленными в планировщике векторами состояний.
Количество параллельных каналов обработки каждого типа может быть жестко связано с ВС, на которой производится обработка или быть переменным числом, изменяемым в зависимости от текущей возможности ВС. Политика выбора количества каналов выбирается из требования ко всей параллельной СУБД. В данном случае, наличие планировщика, производящего контроль превышения ресурсов, позволяет держать избыточное количество каналов обработки, увеличивая их каждый раз, когда на момент проверки загруженности выявляется использование всех каналов при наличии заявок во входной очереди.
Проверка текущего состояния ВС производится на основании системных счетчиков производительности (в терминологии Microsoft) и проверки соответствия их значений векторам использования ресурсов. Следует отметить, что в общем случае, нет прямого соответствия между элементами векторов состояний и счетчиками производительности, однако такое допущение возможно для некоторых случаев.
Методика разбиения последовательного кода программы на независимые
При организации внутриоперационного параллелизма необходимо в рамках исходно последовательного алгоритма выполнения операции выявить взаи-монезависимые последовательности его выполнения с целью их дальнейшего выделения в отдельные параллельные обработчики. В соответствие с ранее сформулированным принципом параллельной обработки, необходимо обеспечить наиболее раннюю постановку заявок на выполнение выделенных функций и наиболее позднее получение результатов их выполнения. Таким образом, задача разбиения последовательного кода на взаимонезависимые фрагменты решается следующим образом: выявление продолжительных функций внутри фрагмента кода программы, параллельное выполнение которых может быть целесообразно. Формирование комбинаций возможных последовательностей выполнения этих функций;
2) определение потребляемых ресурсов в рамках каждой выделенной функции из числа совместно используемых ресурсов (дисковые накопители, каналы обмена ОЗУ, вычислительная нагрузка, взаимноисключагощие режимы блокировки);
3) создание алгебраической модели выполнения анализируемого участка кода программы с различными комбинациями группировки параллельного выполнения выделенных функций;
4) выбор модели оптимальной комбинации группировки функций с точки зрения достигнутой производительности в режиме совместного выполнения с другими фрагментами кода или множественного параллельного выполнения анализируемого участка кода,
Методика предназначена для выполнения преобразования моделей между различными ВС и ориентирована на подсистемы с параллельным режимом работы с интенсивным использованием ОЗУ.
При выполнении преобразования между ВС с различными архитектурами памяти, наиболее важным является корректное разделение составляющих времени, затраченного на работу процессора и на обмен данными с ОЗУ.
Во второй главе предлагалось проводить коррекцию интенсивностей марковской цепи степенной функцией с коэффициентом 3,, см. формула (2.6), причем %a.t! =1-% . Учитывая, что коэффициент А3, в начальный момент может быть подобран эмпирически, это позволяет оценить распределение долей вре мени работы ЦП и обмены ОЗУ. Из приведенного выражения можно определить, что
Учитывая, что известно суммарное время выполнения, а также пропускная способность памяти и производительность процессоров, это позволяет пересчитать времена выполнения анализируемых действий для предполагаемых систем.
Пересчет долей времени выполнения выполняем по формуле КП М %А Л, Thr Ч,ш „ = щ- "- "« , где ШКІШп Шикм „_ пропускные О/ ЛЯ ЛЇ П/ Thr Thr способности подсистем памяти существующей и новой системы, a Thrn,u и VPU №№м инД ксы производительности процессоров в соизмеримых величинах существующей и новой системы (Для процессоров одной серии применимы значения тактовых частот).
Таким образом, методика представляется следующим образом: 1) Параметризация функции коррекции интенсивпостей (коэффициент к\) в модели по известным результирующим характеристикам, полученным на основании экспериментальных или теоретических данных. 2) Определения долей времени работы процессора и обмена ОЗУ в действиях модели, 3) Пересчет долей времени выполнения для новой ВС с использованием значений деградаций пропускной способности ОЗУ (определены в следующей главе). 4) Пересчет коэффициента к11 для новой ВС с использованием значений деградаций пропускной способности ОЗУ.
