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

ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОЙ ЧАСТОТЫ ОБНОВЛЕНИЯ ДАННЫХ В OLAP СИСТЕМАХ А.К. Дорожкин

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

Введение

Высокая эффективность OLAP систем в решении задач анализа данных в первую очередь обусловлена наличием в многомерной базе (МБД) всех данных, необходимых для выполнения анализа. Формат данных и структура МБД обеспечивают высокую скорость поиска и извлечения. Для согласования структуры МБД со структурами данных внешних информационных систем и поддержки актуальности данных необходимо периодически выполнять операцию загрузки (обновления). В рамках OLAP систем данный процесс состоит из трех основных этапов:

• извлечение новых данных из внешних источников,

• передача данных по сети,

• расчет агрегированных показателей.

Наиболее ресурсоемким этапом является расчет агрегированных показателей [5], так как он требует сканирования всех данных, хранящихся в МБД. Однако некоторые производители OLAP серверов (Microsoft, Cognos) используют инкрементальную агрегацию, когда значению существующих агрегированных показателей корректируется на основании загруженных значений. Полная агрегация (Oracle) позволяет разделить во времени процессы загрузки и агрегации данных, а также позволяет удалять данные из МБД. Но недостатком такого способа является слишком большие вычислительные затраты, так как требуется сканирование всех данных многомерного куба. Инкрементальная агрегация выполняется намного быстрее, так как происходит только добавление новых данных ко всем уровням иерархии. Но при этом процессы загрузки и агрегации данных следуют неразрывно во времени. Также в этом случае невозможно удалять данные из МБД.

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

Параметры метода

В рамках предлагаемого метода происходит определение частоты обновления данных (v). Именно изменение данного параметра определяет как актуальность хранимых данных, так и нагрузку на систему. Для того чтобы определить зависимость размера загружаемых данных от значения частоты обновления, необходимо ввести понятие скорости изменения данных (v), под которым будем понимать количество байт, изменяемых или добавляемых в таблицу в единицу времени.

Для определения временных характеристик необходимо использовать понятия производительности той или иной части системы. Так, для передачи данных по сети это будет ее пропускная способность p, а для извлечения и агрегации данных, соответст-

венно, Wext и Wagg, выражающие производительности соответствующего элемента сис-

темы.

C

В общем случае время выполнения операции определяется как t = w, где С —

объем обрабатываемых данных, а W - производительность. Для определения времени выполнения извлечения и передачи данных по сети всегда используется объем новых данных (Cinc), а время выполнения агрегации определяется в зависимости от ее типа. Так, инкрементальная агрегация затрагивает только новые данные (Cinc), а полная - все данные, хранящиеся в многомерном кубе (Ccube).

Наиболее сложный вопрос заключается в определении количественного выражения актуальности данных. Так как в OLAP системе широко используется предварительный расчет агрегатов, то изменение значения одной ячейки детальных данных влияет на множество ячеек многомерного куба, стоящих выше по иерархии во всех измерениях, по которым агрегируется данная ячейка. Поэтому простое сравнение количества загруженных ячеек с общим количеством ячеек многомерного куба не подходит,

так как каждая загруженная ячейка детальных данных меняет ^(// -1) ячеек [4], где

i=1

n

- количество измерений многомерного куба данных, а 1г - количество уровней /-ого измерения, подлежащих предварительной агрегации.

По аналогии с методом оценки актуальности данных, предложенного в [3], значение степени актуальности данных многомерного куба можно определить как отношение всех измененных ячеек, к общему числу ячеек многомерного куба:

1+1

* г =1_

Ф = Г-

т К^уУ

Сcube

С другой стороны, как уже было отмечено выше, при обновлении данных, наиболее длительной операцией является операция агрегации данных. Однако данная операция охватывает сканирование всех данных, имеющихся в многомерном кубе, поэтому для повышения эффективности процесса обновления данных необходимо установить некоторый баланс между временем извлечения и передачи новых (полезных) данных по сети, а также агрегированием всех имеющихся данных на OLAP сервере. Для этого введем степень полезной нагрузки (Р), равную отношению времени агрегации (tagg) и суммарному времени извлечения (text) и передачи данных по сети (tnet):

ß =

t

agg

с

cube

с

cube

t net + t,

ext

W

agg

v

v * p

v

W

ext

f

W

agg

1 p

+ -

W

ext

v

1

v

Критерии определения частоты обновления данных

Слишком маленький интервал обновления может иметь свои негативные последствия: после того, как данные загружены, необходимо пересчитать хранимые значения агрегатов, что обычно является достаточно длительной операцией, затрагивающей сканирование всех детальных данных, хранимых в МБД. Разумеется, интервал обновления не должен быть меньше или равен времени, необходимому для выполнения агрегации. В противном случае север МБД будет занят только тем, что будет обновлять данные. Отсюда возникает понятие «максимально возможная частота обновления», т.е. частота

обновления, при которой загрузка OLAP системы по выполнению задачи обновления данных близка к 100%:

1 1

t net + t agg + t I

' ext

<

=> V <

t + t + t net agg e

t net ' I ass ' I ext

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

Таким образом, используя выражение (3) и понятие производительности, значение максимально возможной частоты обновления данных для случай полной агрегации можно записать как

ff \\

Vm

<

1

V

V * p

V

с,

=>

W

vn

agg

cube

с

cube

1 - V

1

1

P Wext

V

Wext W,

JJ

agg

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

1 1 V <- => V < —-:-:- .

V

V

V

V * p

+-+ -

V *W t v *W

' ' ext ' ' a

1 p

+ -

1

1

Wext Wa

W agg y rr ext ГГ agg

Выражение (4) позволяет определить максимально возможную частоту обновления данных для случая полной агрегации, т.е. частоту данных, при которой система многомерного анализа данных занимается только тем, что обновляет свои данные. Очевидно, что такой подход не всегда является эффективным. Возникает вопрос, как определить эффективность процесса загрузки данных? Ответ на этот вопрос заключается в самом предназначении процесса загрузки данных - обновление данных, т.е. согласование внутренних данных системы многомерного анализа, с внешними источниками. При этом источники данных всегда содержат актуальные данные относительно OLAP системы (относительно реального мира эти данные тоже могут быть устаревшими, но данный вопрос выходит за рамки этой работы). Таким образом, эффективным является процесс загрузки, обеспечивающий определенную степень актуальности внутренних данных системы многомерного анализа.

Используя количественное выражение степени актуальности данных, представленное в (1), эффективная частота обновления определяется как f п , Л

V

V =

ф

1 +

V i=1

-1)

С

^еиЪе

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

Для равномерного распределения нагрузки по различным частям системы во время процесса обновления данных необходимо выбрать частоту обновления исходя из степени полезной нагрузки, определенной в выражении (2):

Г \

W

V =

agg *

с

ß *V*

cube

1

1

P Wext

*

На рис. 1 схематично представлены зависимости выражений (4) (утах), (6) (у(ф)) и (7) (у(Р)) от скорости изменения данных во внешнем источнике.

Рис. 1. Эффективное обновление данных

На рис. 1 утах обозначает максимально допустимую частоту обновления, выше которой система не будет справляться с обновлением данных. Область, отмеченная на рисунке как «Неэффективное обновление», обозначает случай, когда частота обновления данных не обеспечивает требуемую степень актуальности данных ф. Область, обозначенная как «Избыточное обновление», позволяет достичь требуемой степени актуальности, однако степень полезной нагрузки оказывается ниже заданного значения р. Поэтому эффективное обновление данных в случае, когда у(Р)<у(ф), при у(Р)<утах и у(ф)<утах, обеспечивается при V ^\у(Р); v(ф)], а оптимальное значение частоты обновления равно у(ф).

В случае, когда у(Р)>у(ф), при у(Р)<утах и у(ф)<утах, эффективное обновление невозможно, так как в этом случае возможно только либо избыточное, либо неэффективное обновление. Подобный случай изображен на рис. 2.

Рис. 2. Отсутствие эффективного обновления

В этом случае требуется увеличение вычислительных ресурсов. Так, для условий, представленных на рис. 2, требуется увеличение производительности OLAP сервера, потому что увеличение пропускной способности сети привет к уменьшению значения v(P).

При определении частоты обновления многомерного куба необходимо еще учитывать, что в процессе загрузки новых данных увеличивается размер куба, а, значит, и время, необходимое на выполнение агрегации. Поэтому частоту обновления данных необходимо выбирать с некоторым запасом, используя в качестве параметров прогнозируемый размер многомерного куба. При этом сам OLAP куб обычно не хранит в себе все имеющиеся во внешнем источнике данные, а только данные, например, за последние 5 лет. Таким образом, размер многомерного куба изменяется в определенных пределах, что позволяет достаточно точно определить эффективную частоту обновления. Но решение данной задачи выходит за рамки представленной работы.

Экспериментальная часть

В рамках эксперимента по определению эффективной частоты обновления данных были проведены эксперименты с помощью OLAP серверов Oracle Express и Microsoft Analysis Services. Целью данных экспериментов была демонстрация зависимостей частот обновления данных, построенных на различных критериях эффективности, от скорости изменения данных на реальных OLAP серверах. Был создан исходных набор детальных данных в реляционном источнике объемом 1 млн. записей. Исходный набор был полностью загружен в МБД и проагрегирован. В процессе проведения эксперимента в реляционный источник данных добавлялась некоторая порция данных, соответствующая определенной скорости изменения, которая после этого загружалась в МБД и также агрегировалась. При этом в Oracle Express применяется полное агрегирование [1], а в Microsoft Analysis Services - инкрементальное [2].

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

В табл. 1 представлены результаты измерения времени выполнения основных этапов процесса обновления данных и скорость изменения данных во внешнем источнике - как по двум измерениям, так и суммарная скорость изменения.

Скорость изменения Oracle Express Microsoft Analysis Services

Dim1

20 200 0.046 20 0.5 4 4

40 400 0.185 27 2 4 7

60 600 0.417 36 4 6 10

80 800 0.741 46 7 7 15

100 1000 1.157 56 11 7 23

120 1200 1.667 69 17 9 31

Таблица 1. Результаты эксперимента по загрузке данных

На основании полученных результатов были рассчитаны скорости агрегации и извлечения данных, а также максимально допустимая частота (выражение (4)), эффективная частота на основании степени актуальности данных (выражение (6)) и эффективная частота обновления для заданной степени полезной нагрузки (выражение (7)).

Результаты расчетов представлены в табл. 2. Все эти три критерия актуальны только для полного агрегирования, в то время как для инкрементальное агрегирования имеет смысл рассчитывать только эффективную частоту обновления на основании степени актуальности данных (в данном случае ее значение будет полностью совпадать для значения Oracle Express) и определить максимально возможную скорость изменения данных по выражению (5). Для расчетов использовалось значение степени актуальности данных 10-6, степень полезной нагрузки - 105, а размер данных в обоих МБД составлял 8 байт.

v (ячеек/ сек) Oracle Express Microsoft Analysis Services

W agg

0.046 1.53* 106 6.40* 104 0.050 1.51* 10-3 0.004 8.00* 103 8.00* 103 4.00* 103

0.185 1.51* 106 6.40* 104 0.037 4.55* 10-3 0.011 3.20* 104 1.83* 104 1.16* 104

0.417 1.45* 106 7.20* 104 0.028 8.00* 10-3 0.016 4.80* 104 2.88* 104 1.80* 104

0.741 1.41* 106 7.31* 104 0.022 1.14* 10-2 0.022 7.31* 104 3.41* 104 2.33* 104

1.157 1.41* 106 7.27* 104 0.018 1.46* 10-2 0.028 1.14* 105 3.48* 104 2.67* 104

1.667 1.37* 106 6.78* 104 0.014 1.76* 10-2 0.036 1.28* 105 3.72* 104 2.88* 104

Таблица 2. Результаты расчета эффективной частоты обновления

Для наглядности приведем небольшой расчет, иллюстрирующий представленные выше условия. Так, если во внешнем источнике данные изменяются со скоростью одна ячейка в секунду или 86400 ячеек в сутки, то для поддержания актуальности данных их необходимо обновлять примерно один раз в минуту. При этом степень актуальности данных составляет 10-6, что является очень жестким требованием при заданных условиях. Именно это значение соответствует эффективной частоте обновления данных в указанных условиях. Графики зависимостей рассчитанных частот обновления от скорости изменения данных представлены на рис. 3.

(ячеек'сек.^

Рис. 3. Зависимость частот обновления от скорости изменения данных

Как видно, характер зависимостей рассчитанных частот обновления, представленный на рис. 3, совпадает с характером зависимостей, полученных при теоретическом рассмотрении данных зависимостей (рис. 1).

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

Заключение

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

Литература

1. Архипенков С .Я., Голубев Д.В., Максименко О.Б., Хранилища данных. От концепции до внедрения / Под общ. ред. С.Я Архиипенкова. М: Диалог-МИФИ, 2002. 528 с.

2. Хоторн Р., Разработка баз данных Microsoft SQL Server 2000 на примерах. СПб: Вильямс, 2001. 464 стр.

3. Kiviniemi J., Wolski A., Lazy Aggregates for Real-Time OLAP // Proceedings of First International Conference on Data Warehousing and Knowledge Discovery. Florence, Italy: Springer-Verlag, 1999. Р. 165-172.

4. Shanmugasundaram J., Fayyad U., Bradley P. S., Compressed Data Cubes for OLAP Aggregate Query Approximation on Continuous Dimensions. // Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. NY: ACM Press, 1999. Р. 223-232

5. Thomsen E., OLAP Solutions: Building Multidimensional Information Systems. NY: John Wiley & Sons, 2002. 686 р.