ALGORITHMS FOR MANAGING THE LOGICAL STRUCTURE OF THE DATABASE USING A PARAMETRIC MODEL OF COMPETITIVE ACCESS TO QUERIES BASED ON THE RANDOM FOREST METHOD

Full Text

Одним из важнейших вопросов информатизации обще- ства является необходимость эффективной обработки боль- ших объемов данных, как с точки зрениях оптимизации их размещения в узлах распределенных вычислительных си- стем, так и с точки зрения необходимости сокращения вре- мени доступа к хранимым данным. Особенно актуальным этот вопрос является для распределенных информационных систем, основанных на системах управления базами данных (СУБД) реляционного типа. Необходимость поддержки ин- фраструктурой подобных информационных систем горизон- тального масштабирования, допускающего распараллели- вание потока поступающих запросов требует решения ряда проблем, связанных с оптимизацией логической структуры базы данных относительно ее физическому представлению, размещаемому в иерархии памяти (в том числе в кэш-памя- ти различного уровня) ядра СУБД. Особенно ярко проблема горизонтального масштабиро- вания базы данных проявляется при увеличении доли после- довательно обрабатываемых вычислений, возникающих при согласовании совместного доступа к данным между двумя и более запросами, конкурирующими за эти данные. Реше- ние этой задачи может быть основано, как на механизмах согласования последовательности выполнения запросов, с учетом обеспечения требований к целостности и непро- тиворечивости данных и согласованной блокировки выпол- нения запросов на этапах их конкуренции над обрабатыва- емыми данными, так и на способах управления логической структурой базы данных, позволяющих оптимизировать ее физическое представление. Наиболее распространенные в настоящее время реляци- онные СУБД (Oracle, PostgreSQL, Microsoft SQL Server) содер- жат в своем составе средства оптимизации структуры базы данных относительно поступающих на вход СУБД запросов. 41 Однако математическое обеспечение подобных средств обычно ориентируется на использование стоимостных кри- териев, которые не коррелируют с, в первую очередь, вре- менными показателями потока обрабатываемых запросов. При этом рекомендации указанных средств оптимизации ориентированы на модификацию логической структуры базы данных, а ее сопоставление с физической схемой дан- ных возлагается экспертный аудит соответствия структуры базы данных имеющейся нагрузке, реализуемый в настоя- щее время вручную. Разрешением указанного противоречия является раз- работка математического (методы, модели и алгоритмы) и программного обеспечения, обеспечивающего поддержку автоматизированного решения задачи экспертного аудита соответствия структуры базы данных имеющейся нагрузке. П K e1 eaH t0 1 n c1e eaTe1bH ac eT e T e eaH K e1 na a11e1bH e c1eH e e1 4 HH СУ6A В работе [1] на основе теоретико-множественного под- хода выполнено формальное доказательство того, увеличе- ние времени обработки запроса некоторого запроса Q ведет к увеличению числа параллельно выполняемых запросов, что в свою очередь, влияет на рост вероятность появления запросов, конкурирующих за одни и те же данные. Следствием этого является рост времени на обработку последующего потока запросов, что ведет к лавинообразно- му снижению оперативности обработки суммарного потока запросов. Так как поток запросов Qt фактически является множеством пар (q, t), где q сам запрос, а t время его посту- пления, то время обработки всего потока запросов Qt может быть представлено, как: TF Qt   q, t QTq , t   (1)  q, t QTwrk (q)  q, t QZ (q , t , d) , где Z(q, t, d ) - некоторое приращение, связанное с решени- ем ядром СУБД задачи доступа к служебным объектам базы данных, обеспечивающим решение задачи оптимизации ее логической структуры. Это означает, что вариантом управляющего воздействия на логическую структуру базы данных за потока запросов Qt является выбор такого распределения служебных данных d (уменьшение приращения Z ), которое обеспечивает умень- шение значения времени TF. Поскольку изменяемым пара- метром является распределение данных d и выдвигается гипотеза о взаимосвязи целевого значения d с свойствами запроса Q разумным ожиданием будет установление через модель функциональной взаимосвязи между ними. Таким образом областью значений моделирования указанного про- цесса должно быть не суммарное время выполнения множе- ства запросов, а время выполнения отдельного запроса. Фактически, задача синтеза такой модели сводится к за- даче поиска функции эквивалентной некоторому отображе- нию f : { q( , t)} → T. В настоящее время одним из наиболее распространенных классов методов решения подобных за- дач является класс методов машинного обучения (machine learning) [2; 3]. В рамках этих методов подобная зависимость называется численной регрессией, а поиск решения - вос- становлением регрессии [3]. Поскольку отсутствуют априорные сведения о распреде- лении событий потока запросов Qt и свойствах моделируе- мой функции необходимо использовать, так называемые, сильные методы машинного обучения, которые способны восстанавливать зависимости произвольного рода. В рабо- тах [4-7] к таким методам относят: бустинг, бэггинг, случай- ный лес, нейронные сети и метод опорных векторов. На основании проведенного анализа функциональных возможностей указанных методов машинного обучения, был выбран метод случайного леса, как наиболее универ- сальный способ аппроксимации произвольных функций [8]. Метод был предложен в работе [9] и объединяет два под- хода к ансамблированию данных: рассмотренный выше бэг- гинг и метод случайных подпространств [10] используя в ка- честве базовых алгоритмов решающие деревья [11]. Использование в качестве базового алгоритма решающих деревьев полностью соответствует условиям представленной выше задачи. Рассмотрим обобщенную схему процесса обра- ботки потока запросов в реляционной СУБД (рис. 1). image Запрос Q, результат выполнения R и время выполнения Т Источники запросов Менеджер подключений Средства мониторинга и анализа производительности Средства управления СУБД Результат выполнения запроса R Запрос Q Парсер Представление запроса в виде абстрактного синтаскического дерева AST Администратор базы данных Управляющее воздействие через подкласс QC запросов Q QC Логическая схема организации данных Оптимизатор Ядро СУБД Хранимые данные План выполнения запроса Р Множество элементарных операций доступак памяти А Память вычислительной системы Р c. 1. Обобщенная схема процесса обработки потока запросов в реляционных СУБД Поскольку любой запрос q в проходит этап синтаксическо- го и лексического анализа, то на этапе его выполнения ядром СУБД, то есть при приращении величины Z, он будет представ- лен деревом AST, в узлах которого располагаются операции отображения. То есть, любой запрос q будет тождественен не- которому множеству координат в признаковом пространстве (q, t)  {x}  Xq . А1r T aH eaH na a eT e 3an c e n c a H e e eH e n 1HeH Для получения линейно упорядоченного множества объ- ектов базы данных по степени их значимости для времени выполнения запросов был разработан следующий обобщен- ный алгоритм. Узлы всех решающих деревьев объединяются lh  L Используемый в методе случайного леса подход с ан- самблированием множеств решающих деревьев позволяет обеспечить не только обобщающую способность, но и устой- чивость модели к частичным признакам и многообразию потенциально возможных запросов [12-14]. Предположим, что существуют некоторые пары (q1, t1), (q2, t2), (q3, t3), и как следствия соответствующие им предикаты в общее множество. Из полученного множества отсеиваются не связан- ные с объектами логической схемы данных элементы L lh L imagelh  xa ∪ xq . Рассчитывается арифметическое среднее сумм всех вершин обоих поддеревьев, формируемых каждым из узлов f (Ih′) → (SR ′, SL′), Ih′ ϵ L′. Для каждого из узлов выполняется обратный проход x1 ∪ x2 ∪ x3  Xq . и формируется подмножество признаков для которых Полагая запросы разнообразными можно допустить он определен X ′ : X ~ Ih′. На выбранном подмножестве признаков формирует- x1 ∪ x2  ; x1 ∩ x2  ся сумма затраченного на исходные запросы времени и аналогичным образом для иных пар. Подобные наборы можно назвать частичными признаками. По своему опреде- лению решающее дерево ℑ может быть построено над лю- бым подмножеством {x}  x1 ∪ x2 ∪ x3. и отношение к суммарному времени всех запросов к базе данных γ = τ (X ′)/τ (X). Пары величин (SR ′, SL′) корректируются: SR = γ SR ′, SL = γSL. Множество элементов L′ упорядочивается по критерию N Следовательно могут быть синтезированы деревья ℑ(x1), N1 imageSL  SR image. ℑ(x2), ℑ(x3), выражающие функциональные зависимости для каждого запроса в отдельности, без относительно иных за- просов. В равной степени допустимы деревья 1 Поясним шаги алгоритма. На ne e are внутреннее состояние модели представ- ляется через множество ее частичных состояний. Этот шаг x1 ∪ x2 ; x2 ∪ x3 ; x1 ∪ x3 , является преобразованием обратным представлению пре- аппроксимирующие совместную зависимость целевой функ- ции от нескольких запросов единовременно. Так же возмож- ны решающие деревья вида ∪x  x   x  Xq , где ψ - функция произвольной природы. Такая функция мо- жет устанавливать взаимосвязь между суперпозицией ансам- бля решающих деревьев и базовых алгоритмов удовлетворяя рассмотренному выше ограничению накладываемому на рас- смотренные ранее частичные функции hx . Из чего следует, что наличие частичных признаков не влияет на синтез алгоритма h. Финальная модель M FM  x    bm hx; am  m  1 представляет собой совокупность деревьев h (x; am), каждое из которых состоит из множества узлов Ih  L. Исходя из опре- дикатов запросов из исходной статистики в виде векторов обучающей выборки. Совокупности решающих правил всех деревьев пересекаются и образуют общее множество L. На eT are из полученного множества lh  L отби- раются те объекты, которые могут быть прямо связаны с ло- гической схемой данных. Поскольку в составе признакового пространства содержатся так же указания типов операций и отношений времен совместного выполнения, их можно от- бросить. Отброшенное множество узлов, аналогично остав- ленному может быть использовано выделения групп конку- рентных запросов и оценки их влияния. Однако, поскольку указанные узлы связанны, то как будет показано в дальней- шем их влияние будет учтено на последующих шагах. Т eT ar связан с формированием обобщения, обеспе- чивающего получение примерной оценки степени влияния выбранного узла на время выполнения запроса. Всякий эле- мент Ih′  L′ является частью как минимум одного решающего дерева в финальном алгоритме. С этого шага каждое из таких делениявекторовобучающейвыборкиxi = следует x(a{},{xq},{xc},{xm}), деревьев перебирается в цикле. У элемента Ih′ в заданном бинарном дереве имеются два дочерних поддерева. Каждое L  {xa} ∪ {xq} ∪ {xc} ∪ {xm} и соответственно значительная часть узлов прямо, через эле- менты множества {xa}, или транзитивно, через элементы мно- жества {xq} связана с объектами логической схемы данных. Следствием такой природы случайного леса является ограниченная способность к переобучению на рассматрива- емом наборе данных, что, согласно исследованиям, верно и для более общих случаев [15]. Таким образом, модель це- левой зависимости может строится полностью автоматиче- ски, без привлечения эксперта. из этих поддеревьев заканчивается листами с значением вре- мени выполнения запроса. Рассчитывая среднее арифметиче- ское указанных времен для обоих поддеревьев мы получаем f (Ih′) → (SR′, SL′) - усредненную оценку времени выполнения запроса в зависимости от истинности условия заданного уз- лом Ih′. При этой операции так же учитывается обобщенное влияние узлов, отсеянных на предшествующем шаге алгорит- ма, поскольку они являются частью поддеревьев. ЧeTee T ar заключается в поиске в обучающей выборке подмножества векторов X ′ : X ~ Ih′, к которым мо- жет быть применено заданное на прошлом шаге дерево. Поскольку частью каждого такого вектора является фактиче- ское время выполнения запроса, этот шаг является этапом перехода от усредненных оценок к фактическому времени, затраченному на обработку запросов ассоциированных с ус- ловием заданным узлом Ih′. На n T are рассчитывается величина вклада множе- ства ассоциированных с заданным решающим деревом за- просов к суммарному времени выполнения всех запросов. Коэффициент γ = τ(X′)/τ(X) в дальнейшем позволит нормали- зовать оценки времени задаваемыми разными деревьями. Начало Ввод статистики запроса за время Ti image image Р c. 2. Схема итеративного алгоритма автоматического распределения данных в реляционных СУБД Расчет модели Ti хранения данных Объединениес моделями за шаги Tn, Tn + 1, ..., Tj, j < 1, j - n < const, n > -1 Сортировка узлов (решающих правил) по выигрышу от нового состояния Есть узел для корректировки? Да Да Применить выбранные функции распределения Конец Узел окрашен? Нет Оценить «стоимость» распределения данных Значима сегментация? Нет Да Выбор функции изменения сегментации Значима конкуренция? Да Выбор функции изменения репликации Нет Преобладает чтение? Да Нет Выбор функции добавляемого индекса Выбор функции удаленного индекса Необходимо Применить выбранные функции распределения остановиться? Нет Ожидание спада нагрузки Да Окрасить связанные узлы Конец WecT ar заключается в переходе от условного вре- мени выполнения запроса в зависимости от условия задава- емого в узле Ih′ к абсолютной величине SR = γSR ′, SL = γSL. Заданное дерево определенно только на некотором подм- ножестве запросов, умножение усредненных времен на ко- эффициент рассчитанный на предшествующем шаге позво- ляет нормализовать пары (SR ′, SL′) разных деревьев для их сравнения. На ce b are совокупность условий Ih′ нормализует- ся по критерию N N1 imageSL  SR image. 1 Для каждого из заданного на третьем шаге алгоритма дерева рассчитывается разница во времени выполнения за- просов в зависимости от условия Ih′ (коэффициент |SL - SR|). И для всех сумм этого коэффициента находится среднее арифметическое. При этом для узлов Ih′, транзитивно связан- ных с элементами xa, подмножества пар (SL, SR) включаем в расчет критерия элемента xa. ИTe aT eH a1r T aeT aT ecK r acn e e1eH aHH После ранжирования объектов логической схемы дан- ных по степени их влияния на время выполнения запросов появляется возможность формирования управляющего воз- действия. Например, при существенном преобладании за- просов чтения над запросами записи можно формировать управляющее воздействие по добавлению индекса к целе- вому полю. Разработанный для этого итеративный алгоритм содер- жит три функциональных блока: Подготовка исходных данных. Формирование управляющего воздействия. Применение изменений к базе данных. Первый блок алгоритма включает в себя четыре шага, со- ответствующих приведенной блок-схеме: Сбор статистики обработки запросов за период времени. Расчет параметрической модели согласно разделу 2.3. Обобщение параметрических моделей за интервалы времени. Извлечение внутреннего состояния модели и примене- ние представленного выше алгоритма ранжирования. На ne e are получаются исходные данные. Ими яв- ляются тексты запросов и время их обработки. Они собира- ются за некоторый фиксированный промежуток времени Ti. В идеале величина временного промежутка должна совпадать с одним из внутренних циклов работы целевой систе- мы. Например, в качестве цикла можно рассматривать рабо- чий день организации. На eT are с применением метода случайного леса по собранным исходным данным формируется представлен- ная выше модель работы системы. В соответствии с [93; 98; 103] модель случайного леса может быть построена только для стационарного процесса, а значит и рассматриваемая система является квазистационарной. На T eTbe are полученная модель объединяется с моделями предшествующих итераций работы алгоритма. В силу особенностей внутренней структуры это может дости- гаться простым объединением лесов, с использованием по- нижающего коэффициента для деревьев, сформированных на предшествующих шагах. При этом объединяемые деревья проверяются на скользящем контроле, для отсечения уста- ревших данных. Объединение необходимо для обобщения временных промежутков, если работа системы между ними неравномерна. К примеру, для организации с пятидневной рабочей неделей и временным интервалом в одни сутки два временных интервалов будут описывать состояние системы существенно отличающееся от остальных пяти. Обобщение моделей за предшествующие времена позволяет минимизи- ровать подобные эффекты. На eTee T are выполняется представленный выше алгоритм ранжирования узлов дерева. Четвертый шаг по- зволяет перейти от аппроксимации целевой системы ли- нейно-непрерывными функциями к множеству объектов логической схемы данных, упорядоченному по их влиянию на время суммарное время выполнения запросов. Важ- ность данного шага состоит в сведении задачи многокри- териальной оптимизации к задаче оптимизации по одному критерию. Схема разработанного алгоритма представлена на рис. 2. 3aK1t0 eH e Процесс обработки потока запросов в современных СУБД реляционного типа представлен множеством этапов, которые оказывают влияние на суммарное время обработки запросов. В первую очередь это относится к запросам, конку- рирующим за доступ к одним и тем же данным, хранящимся в базе данных. Решение этой проблемы базируется на итеративном ана- лизе и синтезе логической структуры базы данных, учитыва- ющих динамику поступления конкурентных запросов. В статье рассматриваются разработанные в рамках ре- шения этой проблемы алгоритмы оптимизации логической структуры базы данных, обеспечивающие поддержку дея- тельности администратора СУБД.

About the authors

Dmitry Dmitrievich Gromey

Federal State Government Educational Institution of Higher Education "The Academy of Federal Security Guard Service of the Russian Federation"

Email: gromeydd@outlook.com
employee

References

Supplementary files