НАУКА и ОБРАЗОВАНИЕ

УДК 004.657

МГТУ им. Н.Э. Баумана

grigorev@iu5.bmstu.ru

В работах [11, 12] получено преобразование Лапласа-Стилтьеса (ПЛС) времени выполнения запроса к хранилищу данных, которое справедливо для каждого АМР параллельной системы баз данных:

,                                                       (1)

где

,                                                                     (2)

K – число измерений,

 - производящая функция числа записей i-го измерения в узле,

V_i –  общее число записей i-го измерения,

n – число AMP- узлов (AMP-процессоров),

p_i -  вероятность, что запись i-го измерения удовлетворяет условию поиска по этому измерению в запросе,

χ²(s) - ПЛС времени обработки записи блока листового уровня индекса (χ(s)) и записи таблицы измерения (χ(s)),

,                                                                          (3)

,                                    (4)

,                     (5)

,

,               (6)

,

 определяется следующими рекуррентными формулами:

,

,

                                                                                                                      (7)

, ,

p_j - это вероятность, что запись передаётся из данного узла в j-й узел при условии, что она не была передана в узлы n...j+1.

В табл. 1 [11, 12] приведены выражения для ПЛС φ_D(s), φ_M(s), φ_N(s), φ_PI(s),  φ_PJ(s),  φ_PA(s), φ_PS(s) – это ПЛС случайного времени обработки записи (исходной, промежуточной, результирующей) в ресурсе (диске, ОП, шине, процессоре).

Таблица 1

Здесь

1-p_D – вероятность, что запись находится в кэше (СУБД или диска),

λ_D, λ_M, λ_N – интенсивности запросов к разделяемому ресурсу (на чтение записей из RAID-массива, на запись/чтение записей таблиц из ОП, на передачу записей по соединительной шине),

μ_DB=1/t_БЧ – интенсивность чтения блоков чередования с диска RAID-массива, t_БЧ -  среднее время чтения блока чередования,

N_R – количество дисков в RAID-массиве (с учётом зеркальных),

μ_M  – интенсивность записи/чтения записей таблиц из ОП,

μ_N  – интенсивность передачи записей по соединительной шине,

μ_PI– интенсивность обработки записей в процессоре  при их поиске и чтении с помощью индекса,

μ_PJ– интенсивность построения записей декартова произведения в процессоре,

μ_PS– интенсивность сравнений записей БД в процессоре при их сортировке, 

μ_PA– интенсивность агрегации записей (значений фактов),

Q_PS – значение коэффициента при среднем значении _.  (см. ниже)_,

(n-1) в табл. 1 означает, что заявка не ждёт сама себя в очереди к ресурсу.

В дальнейшем будем считать, что запись результирующего декартова  произведения остаётся в данном узле или передаётся в другие узлы с одинаковой вероятностью. Т. е. p_j= 1/j в формулах (7). В этом случае в формуле (5)

.                                                                                    (8)

Продифференцируем выражение (1) в нуле и оценим математическое ожидание времени выполнения запроса к ROLAP в параллельной системе баз данных [11, 12]. При этом индекс i будем опускать в силу симметричности (8).

              (9)

где  и т.д. определяются следующим образом [4]:

- если соответствующий ресурс является "узким местом" (табл. 2), то это математическое ожидание времени пребывания в ресурсе, ПЛС которого представлено в табл. 1 (где фигурирует соответствующая интенсивность запросов к ресурсу -  λ_D и т.д.),

- в противном случае  и т.д. (для неразделяемого ресурса и для разделяемого ресурса, который не является "узким местом"),

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

Остальные переменные в формуле (9) определены выше. Формулы для оценки λ_D, λ_M, λ_N приведены в табл. 2 [11].

Таблица 2

В табл. 2 введено следующее обозначение:

                                                                 (10)

Помимо архитектур SE, SD и SN на практике применяют смешанные архитектурные решения. Например, узлы SMP (SE) соединяются по схеме "точка-точка" типа ByNet (SN). В этом случае формулу (9) можно переписать в следующем виде:

,          (11)

здесь предполагается, что в SMP-узле "узким местом" является диск,

n_AMP– число AMP-процессоров (узлов) в одном SMP-узле,

n= n_SMP×n_AMP  - общее число AMP-процессоров в системе,

n_SMP - число SMP-узлов,

Г(n) –  вектор (g₁(n), ..., g_K(n)),

 - среднее время передачи записи между AMP-процессорами SMP-узла (чтение из ОП – передача записи (сообщения) по системной шине – запись в ОП),

остальные обозначения такие же, как и в формуле (9).

Пример расчёта среднего времени выполнения запроса к хранилищу данных в параллельной системе баз данных

Расчёт математического ожидания (среднего) времени выполнения запроса к хранилищу данных в ПСБД был выполнен при следующих значениях характеристик ресурсов.

1. Процессор – IntelXeon 5160. СУБД – Oracle 9i. В [9] для выбранного процессора приведено измеренное значение  числа процессорных циклов, выполняемых Oracle в секунду (CPUSPEED) – 1.5×10⁹.

Согласно [3, стр. 228-230] при поиске и чтении 400 записей с помощью обычного индекса (B-дерева) было потрачено  6×10⁵ процессорных циклов. Для интенсивности обработки записей в процессоре  при их поиске и чтении с помощью индекса имеем - μ_PI= 400/(6×10⁵/1.5×10⁹)= 10⁶.

В [3, стр. 347]  приведены результаты автотрассировки простого запроса соединения: число обработанных записей во внешней таблице– 320, число процессорных циклов - 7×10⁴. Поэтому для интенсивности построения записей декартова произведения в процессоре имеем – μ_PJ= 320/(7×10⁴/1.5×10⁹)= 7×10⁶.

Согласно [3, стр. 397, 400] на выполнение  2×10⁷  сравнений при сортировке записей БД в оперативной памяти было потрачено 6,21 секунд процессорного времени при скорости 3,5×10⁸ процессорных тактов в секунду (CPUSPEED). Поэтому для интенсивности сравнений записей БД в процессоре при их сортировке  имеем - μ_PS= 2×10⁷ × (1.5×10⁹/3,5×10⁸)/6,21 = 14×10⁶.

Интенсивность агрегации записей (значений фактов) μ_PA= μ_PS= 14×10⁶ (т.к. многие операции агрегирования фактов требуют сортировки – orderby, groupby и др.

2. Оперативная память (ОП) – DDR3-1600 PC3- 12800. Расчёты показывают, что интенсивность записи/чтения записей таблиц из ОП равна μ_M= 10.4×10⁶ (она мало зависит от длины записи, т.к. данные читаются страницами из ОП).

3. Высокоскоростная системная шина:

для SE (SMP) – системная шина QuickPathInterconnect, её производительность достигает 25 Гбайт/с; при средней длине записи l_З= 100 байтов интенсивность передачи записей по шине равна μ_N= 250×10⁶; при такой скорости эта шина не будет "узким местом" в архитектуре SE,

для SD (кластерная архитектура) и SN (MPP) - в обоих случаях узлы соединены по схеме "точка-точка" типа ByNet (т.е. шина является неразделяемым ресурсом) и интенсивность передачи данных по этой шине равна 20 Мбайт/с на один узел.  Таким образом, при средней длине записи l_З= 100 байтов интенсивность передачи записей по соединительной шине равна μ_N= 0.2n×10⁶.

2. Внешняя память – RAID10 cN_R=30 дисками (с учётом зеркальных) 3.5'' SeagateCheetah 15K.6 ST3146356FC (объём диска 147 Гбайт); размер блока чередования (stripesize) – Q_БЧ=64 Kбайт; среднее время поиска и чтения блока чередования с диска – t_БЧ = t_{подвода} + t_{вращения}/2 + Q_БЧ/v_чтения = 4 + 4/2 + 64/200 = 6,3 мс. Следовательно, μ_DB=1/t_БЧ=1.6×10².

При расчётах использовались формула (11), а также формулы из табл. 1 и 2. Графики зависимостей математического ожидания (среднего) времени выполнения запроса к хранилищу данных (М) от общего числа процессоров 'n' в параллельной системе баз данных  приведены на рис. 1.

Рис. 1. Зависимости математического ожидания времени выполнения запроса к хранилищу данных (М) от числа процессоров (n).

Графики построены при следующих параметрах: среднее число записей таблиц измерений в запросе - V_ip_i= Vp= 20, число измерений - K=5 (число записей в декартовом произведении измерений равно 20⁵), вероятность, что запись находится в кэше (СУБД или диска) - 1-p_D= 0,99. Каждая зависимость соответствует конкретному числу AMP-процессоров в одном SMP-узле: n_AMP= 1 (SN), 2, 4 (см. легенду). При этом число SMP-узлов равно  n_SMP= n/n_AMP. 

Анализ зависимостей на рис. 1 позволяет сделать следующие выводы:

1. Перегрузка диска в SMP-узле наступает при n_AMP= 4, в этом случае среднее время обработки одной записи в дисковой подсистеме узла рассчитывалось по формуле

.                                                                          (12)

Уменьшение времени выполнения запроса при n_AMP= 4 с ростом общего числа AMP-процессоров объясняется уменьшением числа записей таблиц измерений и фактов, хранящихся в одном SMP-узле.

2.Дл случая n_AMP= 4 при n=16 (число SMP-узлов равно 4) время выполнения запроса (50 сек.) соизмеримо с временем выполнения запроса в SN(MPP)-системе (n_AMP= 1) при n=16 (13 сек.). Но такая смешанная SMP-система в несколько раз дешевле (примерно в 4 раза) соответствующей SN(MPP)-системы.

3. В рассматриваемом примере время выполнения запроса в "чистой" SMP-системе (n_SMP= 1) не зависит от 'n' и равно примерно 200 с. Это подтверждает тот факт, что при перегрузке "узкого места" (диска) не имеет смысла наращивать число AMP-процессоров в "чистой" SMP-системе.

 Графики зависимостей математического ожидания (среднего) времени выполнения запроса к хранилищу данных (М) от среднего числа записей таблиц измерений в запросе (V_ip_i= Vp) в параллельной системе баз данных  приведены на рис. 2.

Графики на рис. 2 построены при следующих параметрах: общее число AMP-процессоров – n= 16, число AMP-процессоров в узле – n_AMP= 1 (SN(MPP)-система, см. сплошные линии), вероятность, что запись находится в кэше (СУБД или диска) - 1-p_D= 0,99. Одна зависимость соответствует числу измерений в запросе: K= 3, 4, 5(см. легенду).

Анализ зависимостей на рис. 2 позволяет сделать следующие выводы:

1. Время выполнения запроса сильно зависит от числа записей в измерении (Vp) и числа измерений (K), указанных в запросе. MPP-системе с 16 AMP-процессорами потребуется 19 часов, чтобы обработать  записи 5-ти измерений по 110 записей в каждом измерении (количество записей в декартовом произведении равно 110⁵). Чтобы снизить это время до 19 минут потребуется MPP-система с 1000 AMP-процессорами.

2. Системе с 4-я SMP-узлами по 4-е AMP-процессора в каждом узле (см. пунктирную линию на рис. 2) потребуется 72 часа, чтобы обработать записи 5-ти измерений по 110 записей в каждом измерении.

Рис. 2. Зависимости математического ожидания времени выполнения запроса  к хранилищу данных (М) от среднего числа записей таблиц измерений в запросе (V_ip_i= Vp).

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

Приведено выражение для математического ожидания времени выполнения запроса. Рассмотрен практический пример расчёта и сделаны некоторые выводы. В частности, если "узкое место" (диск) системы не перегружено (его загрузка меньше 1), то среднее время выполнения запроса к хранилищу данных в системе с SMP-узлами соизмеримо с временем обработки этого запроса в MPP-системе с тем же количеством AMP-процессоров. Это позволяет существенно сэкономить денежные средства при приобретении аппаратного обеспечения параллельной системы баз данных.

ЛИТЕРАТУРА

1.     М. Тамер Оззу, Патрик Валдуриз. Распределенные и параллельные системы баз данных: [Электронный ресурс]. [http://citforum.ru/database/classics/distr_and_paral_sdb/]. Проверено 26.11.2010.

2.     Соколинский Л. Б., Цымблер М. Л. Лекции по курсу "Параллельные системы баз данных”: [Электронный ресурс]. [http://pdbs.susu.ru/CourseManual.html]. Проверено 04.12.2010.

3.     Дж. Льюис. Oracle. Основы стоимостной оптимизации. – СПб: Питер, 2007. – 528 с.

4.     Григорьев Ю.А., Плужников В.Л. Оценка времени соединения таблиц в параллельной системе баз данных// Информатика и системы управления. – 2011. - № 1. – С. 3-16.

5.     Лисянский К., Слободяников Д. СУБД Teradata® для ОС UNIX®: [Электронный ресурс]. [http://citforum.ru/database/kbd98/glava5.shtml]. Проверено  14.03.2011.

6.     КузнецовС. Essential Modelling Options: [Электронныйресурс].  [http://citforum.ru/database/digest/dig_1612.shtml]. Проверено  14.03.2011.

7.     Лев Левин. Teradata совершенствует хранилища данных: [Электронный ресурс]. [http://www.pcweek.ru/themes/detail.php?ID=71626]. Проверено  26.11.2010.

8.     Григорьев Ю.А., Плутенко А.Д. Теоретические основы анализа процессов доступа к распределённым базам данных. - Новосибирск: Наука, 2002. – 180 с.

9.     Форум/Использование СУБД/Oracle/CPUSPEED на IntelXeon 5500 (Nehalem): [Электронный ресурс]. [http://www.sql.ru]. Проверено 02.12.2010.

10.  Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы. Общий подход. – М.: БИНОМ. Лаборатория знаний, 2006. – 406 с.

11.  Григорьев Ю.А., Плужников В.Л. анализ времени обработки запросов к хранилищу данных в параллельной системе баз данных // Информатика и системы управления. – 2011. - № 2. – С. 94-106.

12.  Плужников В.Л. Преобразование Лапласа-Стилтьеса времени обработки запросов к хранилищу данных в параллельной системе баз данных: [Электронный ресурс]. [http://technomag.edu.ru/doc/270159.html]. Проверено 29.10.2011.