Руководитель проекта Соколинский  Леонид  Борисович

Краткая аннотация Разработаны принципы и методы моделирования иерархических кластерных архитектур виртуальных параллельных машин баз данных. На их основе начата реализация эмулятора виртуальных мультипроцессоров баз данных (ЭВМБД). ЭВМБД позволит моделировать практически любые архитектуры параллельных систем баз данных. Это даст возможность исследовать широкий спектр перспективных гибридных и иерархических кластерных архитектур без больших затрат на их аппаратную реализацию. Спроектирован, закодирован и отлажен прототип параллельной СУБД Омега для MPI – Omega-MPI. Данный прототип обладает высокой мобильностью и способен работать на широком классе мультипроцессорных платформ, поддерживающих компилятор Си и пакет MPI. Omega-MPI предполагается использовать для исследования новых методов и алгоритмов параллельной обработки запросов на кластерных архитектурах. Исходные тексты Omega-MPI свободно доступны в Интернет по адресу http://www.csu.ru/~sok/OmegaProject/Omega-MPI/. Разработана оригинальная архитектура менеджера буферного пула, базирующая на использовании избыточного индекса буферного пула DIR и методе статических и динамических рейтингов страниц. Избыточный индекс буферного пула DIR представляет собой хеш-таблицу, обеспечивающую быстрый поиск страниц в буферном пуле. Кроме этого, он включает в себя атрибуты, содержащие статистическую информации об использованных страницах. Отличительной особенностью метода статических и динамических рейтингов является то, что суммарный рейтинг страницы формируется из двух независимых рейтингов: статического и динамического. Статический рейтинг задается пользователем при открытии набора страниц и позволяет организовать избирательное вытеснение страниц. Динамический рейтинг страницы вычисляется системой на базе статистических атрибутов и правила вытеснения, ассоциированного с данной страницей. Динамический рейтинг позволяет реализовать комбинированную стратегию замещения страниц, в максимальной степени учитывающую специфику работы систем баз данных. Предложен новый метод автоматической параллелизации запросов для систем с кластерной архитектурой. В основе метода лежит использование специального оператора обмена, инкапсулирующего в себе все механизмы, необходимые для реализации внутриоперационного параллелизма. В течение 2003 года по тематике проекта исполнителями опубликовано 4 печатных работы (1 статья в научном сборнике, 1 статья в продолжающемся издании, 1 докторская диссертация, 1 автореферат докторской диссертации). Кроме этого, подготовлены и приняты к печати: статья в подолжающемся издании "Алгоритмы и программные средства параллельных вычислений" (ИММ УрО РАН); статья на английском языке в трудах международнрой конференции DASFAA-2004 (изд-во Springer). Еще одна статья в настоящее время проходит рецензирование в журнале "Программирование". Полные тексты опубликованных статей доступны по адресу http://www.csu.ru/~sok/grants/rfbr/2003/k_omega.html#papers. Результаты проекта докладывались на Всероссийской конференции "Научный сервис в сети Интернет-2003". По тематике проекта Л.Б.Соколинским защищена диссертация на соискание ученой степени доктора физ.-мат. наук [http://www.csu.ru/~sok/dissertation/index.html]. Обновлена и дополнена WWW страница, посвященная проекту создания параллельной СУБД Омега: http://www.csu.ru/~sok/OmegaProject. Обновлена и дополнена WWW страница на английском языке, посвященная проекту создания параллельной СУБД Омега: http://www.csu.ru/~sok/OmegaProject/eng. Создана WWW страница, посвященная данному гранту РФФИ: http://www.csu.ru/~sok/grants/rfbr/2003/k_omega.html.

Полученные за отчетный период важнейшие результаты Разработаны принципы и методы моделирования иерархических кластерных архитектур виртуальных параллельных машин баз данных. На их основе начата реализация эмулятора виртуальных мультипроцессоров баз данных (ЭВМБД). ЭВМБД позволит моделировать практически любые архитектуры параллельных систем баз данных. Это даст возможность исследовать широкий спектр перспективных гибридных и иерархических кластерных архитектур без больших затрат на их аппаратную реализацию. Спроектирован, закодирован и отлажен прототип параллельной СУБД Омега для MPI – Omega-MPI. Данный прототип обладает высокой мобильностью и способен работать на широком классе мультипроцессорных платформ, поддерживающих компилятор Си и пакет MPI. Omega-MPI предполагается использовать для исследования новых методов и алгоритмов параллельной обработки запросов на кластерных архитектурах. Исходные тексты Omega-MPI свободно доступны в Интернет по адресу http://www.csu.ru/~sok/OmegaProject/Omega-MPI/. Разработана оригинальная архитектура менеджера буферного пула, базирующая на использовании избыточного индекса буферного пула DIR и методе статических и динамических рейтингов страниц. Избыточный индекс буферного пула DIR представляет собой хеш-таблицу, обеспечивающую быстрый поиск страниц в буферном пуле. Кроме этого, он включает в себя атрибуты, содержащие статистическую информации об использованных страницах. Отличительной особенностью метода статических и динамических рейтингов является то, что суммарный рейтинг страницы формируется из двух независимых рейтингов: статического и динамического. Статический рейтинг задается пользователем при открытии набора страниц и позволяет организовать избирательное вытеснение страниц. Динамический рейтинг страницы вычисляется системой на базе статистических атрибутов и правила вытеснения, ассоциированного с данной страницей. Динамический рейтинг позволяет реализовать комбинированную стратегию замещения страниц, в максимальной степени учитывающую специфику работы систем баз данных. Предложен новый метод автоматической параллелизации запросов для систем с кластерной архитектурой. В основе метода лежит использование специального оператора обмена, инкапсулирующего в себе все механизмы, необходимые для реализации внутриоперационного параллелизма. За 2003 год по тематике проекта исполнителями опубликовано 4 печатных работы (1 статья в научном сборнике, 1 статья в продолжающемся издании, 1 докторская диссертация, 1 автореферат докторской диссертации). Кроме этого, подготовлены и приняты к печати: статья в подолжающемся издании "Алгоритмы и программные средства параллельных вычислений" (ИММ УрО РАН); статья на английском языке в трудах международнрой конференции DASFAA-2004 (изд-во Springer). По тематике проекта Л.Б.Соколинским защищена диссертация на соискание ученой степени доктора физ.-мат. наук [http://www.csu.ru/~sok/dissertation/index.html]. Обновлена и дополнена WWW страница, посвященная проекту создания параллельной СУБД Омега: http://www.csu.ru/~sok/OmegaProject. Обновлена и дополнена WWW страница на английском языке, посвященная проекту создания параллельной СУБД Омега: http://www.csu.ru/~sok/OmegaProject/eng. Создана WWW страница, посвященная данному гранту РФФИ: http://www.csu.ru/~sok/grants/rfbr/2003/k_omega.html.

Методы и подходы, использованные в ходе выполнения проекта АРХИТЕКТУРА ЭМУЛЯТОРА ВИРТУАЛЬНЫХ МУЛЬТИПРОЦЕССОРОВ БАЗ ДАННЫХ (ЭВМБД) базируется на разработанной нами концепции виртуальных параллельных машин баз данных. Виртуальная параллельная машина баз данных строится из следующих виртуальных устройств: виртуальные процессоры, виртуальные модули памяти, виртуальные диски, виртуальная соединительная сеть. Виртуальный процессор - это виртуальное устройство, используемое для выполнения отдельной задачи, определяемой как процесс базы данных. Типичным примером процесса базы данных является запрос или агент запроса (при использовании фрагментного параллелизма). В реальной системе виртуальный процессор может быть представлен микропроцессором или процессорным модулем. Виртуальный модуль памяти - это виртуальное устройство, используемое для буферизации объектов базы данных. Типичным примером объекта реляционной базы данных является отношение или его фрагмент (при использовании фрагментного параллелизма). Виртуальный процессор не может получить доступ к объекту базы данных иначе, чем через его образ, загруженный в некоторый доступный ему виртуальный модуль памяти. В соответствие с этим количество виртуальных модулей памяти в виртуальной параллельной машине баз данных не может превосходить количество виртуальных процессоров. В реальной системе виртуальный модуль памяти обычно реализуется в виде физических модулей оперативной памяти. Виртуальный диск - это виртуальное устройство, используемое для хранения объектов базы данных. В реальной системе виртуальный диск обычно реализуется в виде физического дискового устройства или дискового массива. Виртуальная соединительная сеть - это виртуальное устройство, обеспечивающее передачу данных из одного виртуального модуля памяти в другой. Передача может осуществляться только посредством коммуникативных действий соответствующих виртуальных процессоров. Без существенного ограничения общности мы можем полагать, что в виртуальной параллельной машине баз данных может существовать не более одной виртуальной соединительной сети. При этом следует отметить, если в виртуальной машине имеется только один модуль памяти, то виртуальная сеть должна отсутствовать. Виртуальную параллельную машину баз данных мы можем теперь определить как связный граф, узлы которого соответствуют различным виртуальным устройствам, а ребра соответствуют потокам данных. Детальный технический отчет, посвященный принципам и методам разработки эмулятора виртуальных мультипроцессоров баз данных доступен по адресу http://www.csu.ru/~sok/papers/omega_rep/11.html. УПРАВЛЕНИЕ БУФЕРНЫМ ПУЛОМ. В основе реализации менеджера буферного пула лежат следующие основные структуры, функции и алгоритмы: - избыточный индекс буферного пула DIR; - функция вычисления динамического рейтинга; - функция вычисления рейтинга; - набор правил вытеснения; - алгоритм работы диспетчера страниц. Избыточный индекс буферного пула DIR представляет собой таблицу, хранимую в оперативной памяти, и не обладающую свойством персистентности. DIR используется менеджером буферного пула для выполнения следующих двух функций: 1) поиск страниц в буферном пуле; 2) хранение статистической информации об использованных страницах. В соответствие с этим DIR имеет двойственную природу. С одной стороны, DIR представляет собой обычную хеш-таблицу, индексирующую страницы, хранящиеся в буферном пуле. При обращении к очередной странице диска менеджер буферного пула проверяет наличие ее индекса в DIR. Если индекс указанной страницы в DIR отсутствует, то происходит добавление нового индекса в DIR. Если при этом оказывается, что DIR переполнен, происходит предварительное вытеснение некоторого индекса из DIR. Поиск жертвы осуществляется только среди индексов DIR, соответствующих незагруженным в данный момент в буфер страницам. При этом используются те же рейтинги, что и для буферизованных страниц. С другой стороны, DIR представляет собой информационную таблицу с атрибутами, содержащими различную статистическую информацию об использованных страницах. Примерами подобной статистической информации являются время помещения страницы в буфер, время последнего обращения к странице, общее количество обращений к странице в течение некоторого интервала времени и др. Конкретный набор статистических атрибутов зависит от набора правил вытеснения, встраиваемых в менеджер буферного пула. Избыточность DIR подразумевает, что он может хранить информацию не только о тех страницах, которые в данный момент присутствуют в буферном пуле, но так же и о страницах, которые присутствовали там ранее и были впоследствии из него вытеснены. Оптимальной является ситуация, при которой DIR содержит информацию о всех страницах базы данных, размещенных на данном процессорном узле. Однако и при меньших размерах DIR использование избыточного индекса буферного пула может значительно повысить эффективность работы менеджера буферного пула. Как показали проведенные нами эксперименты, использование DIR, содержащего информацию о 20-40% страниц базы данных, позволяет увеличить производительность алгоритма замещения страниц на 8-10% при стационарном распределении вероятностей обращения. Алгоритм работы диспетчера страниц базируется на использовании рейтингового вытеснения. Рейтинг страницы задается неотрицательным вещественным числом, получаемым в результате вычисления рейтинговой функции. В основе алгоритма вычисления рейтинговой функции в системе Омега лежит оригинальный метод статических и динамических рейтингов. В соответствие с этим методом суммарный рейтинг страницы является неотрицательным вещественным числом из интервала [0;21[ и получается как сумма статического и динамического рейтингов: <Суммарный рейтинг> = <Статический рейтинг> + <Динамический рейтинг>. Статический рейтинг - это целое число из интервала [0;20]. Статический рейтинг является атрибутом открытого набора страниц. Он может задаваться явно при выполнении операции открытия набора страниц (файла). По умолчанию открытому набору назначается рейтинг, равный 10. Статический рейтинг страницы всегда совпадает с рейтингом набора, которому она принадлежит. Данный рейтинг не меняется на протяжении всего времени работы с открытым набором. Динамический рейтинг - это вещественное неотрицательное число из интервала [0;1[. Динамический рейтинг является атрибутом страницы и сохраняется в ее индексе в DIR. Динамический рейтинг всегда задается менеджером буферного пула неявно путем вычисления функции динамического рейтинга. Непосредственно из определений статического и динамического рейтингов вытекает следующее важное правило идемпотентности статического рейтинга. Если статический рейтинг страницы A больше статического рейтинга страницы В, то суммарный рейтинг страницы А будет всегда больше суммарного рейтинга страницы В вне зависимости от того, какие значения принимают динамические рейтинги этих страниц. Механизм статического рейтинга позволяет реализовать избирательное вытеснение страниц. Рассмотрим использование статического рейтинга на примере задачи корректного восстановления после сбоя. Страницы, содержащие флаги фиксации, и страницы, на которых записываются планируемые изменения, необходимо разделить в разные наборы. При открытии набора с данными ему присваивается некоторый статический рейтинг. Пусть для определенности значение этого рейтинга будет равным 10. Тогда набору с флагами при открытии необходимо присвоить статический рейтинг, равный 9 (на единицу меньше, чем у набора с данными). А набору, содержащему журнал изменений, необходимо присвоить статический рейтинг, равный 8 (на единицу меньше, чем у набора с флагами). В этом случае, вне зависимости от поведения динамического рейтинга, мы будем иметь следующий порядок вытеснения страниц на диск (следует из правила идемпотентности статического рейтинга): 1) вытеснение страниц журнала изменений; 2) вытеснение страниц с флагами; 3) вытеснение страниц с данными. Данный порядок шагов 1, 2 и 3 диктуется требованием корректности работы процедуры восстановления после сбоя. При возникновении сбоя на шаге 1 или 2 утилита восстановления удаляет из журнала изменений все записи, для которых не установлен флаг фиксации. При возникновении сбоя на шаге 3 утилита восстановления автоматически повторяет выполнение всех шагов прерванной транзакции, зафиксированных в журнале изменений. Динамический рейтинг отражает политику вытеснения, проводимую менеджером буферного пула по отношению к данной странице. Политика вытеснения определяется следующими двумя факторами: - правило вытеснения, ассоциированное с данной страницей; - значения статистических атрибутов страницы, на которые ссылается правило вытеснения. При этом первый фактор является основным, а второй - вспомогательным. В реализации менеджера буферного пула динамический рейтинг получается путем вычисления функции динамического рейтинга. Рассмотрим алгоритм вычисления функции динамического рейтинга на следующем примере. Пусть имеется три набора страниц, задействованных в выполнении запроса: A, B и C. Предположим, что страницы набора A просматриваются один раз без повторения. Предположим, что страницы набора B просматриваются в цикле, причем весь цикл можно поместить в буферный пул. Предположим, что страницы набора C просматриваются в соответствии с некоторым статическим распределением вероятностей, например, по правилу "80-20". Пусть DIR содержит следующие статистические атрибуты: - FoR (Force Out Rule) - правило вытеснения; - FC (Frequency Counter) - количество обращений к странице. Определим FCmax как максимальное значение атрибута FC в таблице DIR. Предположим, что в нашем менеджере буферного пула по умолчанию используется правило вытеснения, определяемое стратегией LFU, в соответствии с которой из буфера вытесняются страницы с наименьшим значением атрибута FC. Назначим наборам страниц следующие правила вытеснения: A - Немедленное вытеснение B - Удержание C - По умолчанию В данном контексте алгоритм вычисления функции динамического рейтинга может иметь следующий вид. /* Функция, возвращающая значение динамического рейтинга для страницы r */ if DIR[r].FoR = "По умолчанию" then return DIR[r].FC/(FCmax+2) else if DIR[r].FoR = "Немедленное вытеснение" then return 0 else if DIR[r].FoR = "Удержание" then return (FCmax+1)/(FCmax+2) else ошибка: "Неопределенный тип правила вытеснения" end if Безусловно, этот алгоритм нуждается в некоторых доработках для того, чтобы его можно было использовать на практике. Во-первых, это касается выбора правила вытеснения, используемого по умолчанию. В примере выше мы использовали правило, определяемое стратегией LFU. Однако данная стратегия имеет существенный недостаток, заключающийся в том, что в буфере достаточно долго будут оставаться неиспользуемые страницы, которые "накопили" достаточно большое значение атрибута FC во время предшествующих обращений. Выбор стратегии вытеснения, используемой по умолчанию, является критическим для эффективной буферизации. В СУБД Омега мы используем разработанную нами новую стратегию замещения LFU-K. Во-вторых, в приведенном выше алгоритме мы предположили, что правило вытеснения, ассоциированное с данной страницей, хранится в DIR (атрибут FoR). На самом деле правило вытеснения хранится в виде значения соответствующего атрибута таблицы открытых наборов. Это обеспечивает возможность задания для страницы более одного правила вытеснения, так как один и тот же набор может быть открыт одновременно двумя и более транзакциями. Для разрешения коллизий мы используем механизм приоритетов. Детальное описание принципов организации менеджера буферного пула можно найти в http://www.csu.ru/~sok/dissertation/dissert.pdf (Глава 3). АВТОМАТИЧЕСКАЯ ПАРАЛЛЕЛИЗАЦИЯ ЗАПРОСОВ. Запрос на языке SQL передается пользователем на host-машину. Там он транслируется в некоторый последовательный физический план. Данный последовательный физический план преобразуется в параллельный план 1-го уровня, представляющий собой совокупность агентов 1-го уровня. Каждый агент 1-го уровня, кроме реляционных операций, может содержать специальные параллельные операции psplit (расщепление) и pmerge (слияние). Параллельный план 1-го уровня задает распараллеливание запроса с точностью до Омега-кластера. На следующем этапе параллельный план 1-го уровня преобразуется в параллельный план 2-го уровня. При этом каждый агент 1-го уровня отображается в n агентов 2-го уровня. Здесь n обозначает количество процессорных модулей в Омега-кластере. Это достигается путем вставки оператора обмена exchange в соответствующие места дерева запроса. Параллельный план 2-го уровня задает распараллеливание запроса с точностью до процессорного модуля. На завершающем этапе агенты 2-го уровня пересылаются с host-машины на соответствующие узлы многопроцессорной системы, где интерпретируются исполнителем запросов. Результаты выполнения агентов в пределах одного Омега-кластера объединяются корневым оператором exchange на нулевом процессорном модуле. Если запрос выполнялся на нескольких Омега-кластерах, то суммарный результат получается путем выполнения операции pmerge на нулевом узле одного из Омега-кластеров, откуда передается на host-машину. Детальное описание методов и принципов параллелизации запросов можно найти в http://www.csu.ru/~sok/dissertation/dissert.pdf (Глава 5).

Адреса (полностью) ресурсов в Internet, подготовленных авторами по данному проекту http://www.csu.ru/~sok/OmegaProject http://www.csu.ru/~sok/grants/rfbr/2003/k_omega.html http://www.csu.ru/~sok/OmegaProject/eng