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

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

архитектуры

А.Н. Скоба, Е.В.Состина Южно-Российский государственный политехнический университет (НПИ) им.

М. И. Платова, Новочеркасск

Аннотация: в данной статье с использованием аппарата замкнутых экспоненциальных сетей массового обслуживания (СеМО) разработана математическая модель решения задачи об оптимальном размещении распределённой базы данных (РБД) по узлам локальной вычислительной сети (ЛВС) на базе двухуровневой клиент-серверной архитектуры по критерию минимума среднего времени реакции системы на запросы пользователей. Приведены результаты численных экспериментов.

Ключевые слова: распределённая база данных, селективная выборка информации, SQL-запрос, распределённая информационная система, транзакция, пространство состояний системы, стационарная вероятность, переходная вероятность, интенсивность обслуживания, матрица объёмов информации, время реакции системы.

Отличительная особенность разрабатываемой модели от модели, представленной в работе [1] состоит в том, что на сервере производится селективная выборка информации, и по каналу связи передаётся не полная база данных, а некоторое количество кортежей базы данных, удовлетворяющих условию поиска SQL-запроса [2-4]. Дополнительно к введённым при разработке модели распределённой информационной системы на базе файл-серверной архитектуры, исходным данным [1]:

и=(и1,...,из,...,и„}; А=(А1,...,А3,...,АП}; Я={ЯЬ.Л={1Ъ...Х,...,ХП};

УВ={УВ1,...,УВ,...,УВП}; Ри={Ри1,...,Ри,...,Рип}; в; во; «о;

Q={Ql,.,Ql,.,Qq}; У={У1,.~,У,.~,У};

УУ={УУ1,...,УУ,...,УУп};

£(В) = |£.||, (/ = 1, q, . = 1, й), вводится матрица объёмов информации, получаемой после процессорной обработки: В = Ьд1к] ||, (/ = 1, q, ] = 1, й).

При этом, дополнительно к концептуальной модели информационной системы на базе файл-серверной архитектуры [1], для сборки ответов на элементарные транзакции вводятся буферные памяти пользователей: ВРА],...,ВРА8,...,ВРАп ёмкостью й и ключи: К],.,К8,.,Кп. Каждый из ключей может находиться в двух состояниях: разомкнутом и замкнутом. В первом состоянии он находится до тех пор, пока в ВРА3, = 1, п) не будет собран ответ на запрос пользователя А, т.е. будут получены ответы на все элементарные транзакции. После этого ключ К переходит в замкнутое состояние, и собранный ответ на весь запрос выводится на пользовательский терминал. Количество одновременно обслуживаемых в системе сообщений, с учётом "расщепления" запроса на элементарные транзакции, не может превосходить величины пй, а в период пиковых нагрузок точно совпадает с этой величиной. Концептуальная модель функционирования этой системы представлена на рис. 1.

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

«клиент-сервер»

По сравнению с моделью информационной системы на базе файл-серверной архитектуры [1], пространство состояний данной модели

модифицируется:

,12п+1,з,.,12п+1,ц), I = 1, Р}, где

{/0я, я = 1, п} описывают состояние буфера ВРАл при этом 0 - количество обслуженных транзакций я-го пользователя; {,я = 1,п} - описывают состояние я-го пользователя, причём

й, если я - й пользователь находится в активном состоянии (формирует запрос),

0 < ¡и < й, я - й пользователь находится в пассивном состоянии (ждёт ответа на запрос).

Ограничения имеют следующий вид:

2п+1 п

1) ЕЕ к = пй;

к=0 г=1

2п+1 _

2) Е кг = й, г=1 п;

к=0

^ =

3) уя = 1, п,0 < ¡0з < й ;0 < ¡ъ < й ;0 < /0 я + < й > 0, У к = 0,2п +1.

Расчёт стационарных вероятностей состояний сети Р () аналогичен расчёту данных величин для информационной системы на базе файл-серверной архитектуры [1] и производится на основе решения уравнения глобального баланса[5-9].

При расчёте величин ¡лгг, (я = 1,2п +1, г = 1, п) следует учитывать тот факт, что применение клиент-серверной архитектуры приводит к вариации содержания процедур обработки второй и третьей групп запросов, а обслуживание заявок первой группы не изменяется по отношению к модели информационной системы на базе файл-серверной архитектуры [1,10]. В частности, при выполнении заявок первой группы производится селективная выборка информации из баз данных, размещённых в ЦЦ-м узле, а затем её процессорная обработка. Обслуживание запросов второй группы в Ц-м узле

состоит в выполнении операций процессорной обработки над кортежами, которые были считаны в других узлах и переданы в из-й узел по каналу связи. Реализация запросов третьей группы включает селективную выборку информации из баз данных, размещённых в П8-м узле, и передачу кортежей отношений, удовлетворяющих условиям поиска, пользователям, прикреплённым к другим узлам. В соответствии с этим, интенсивности обслуживания запросов в узлах сети, по сравнению с [1] модифицируются следующим образом:

£ = 1,2« + 1, г = 1,п

д d _ Л

Е frl Е ьъхл

в0 + -

0 в

г = 1,п,г = 1,п,£ = 1 + г,г ф г;

д п d __^ 1

д d д d V / УУ/) Г

ЕЛЕ^х^ Е/„ ЕЕ]г1 ЕЕЬ1] *

а0 +

1=1 1=1

УК

+

1=1 1=1

ри„

+

к фе

г = 1, п, г = 1, п, £ = п + 1 + г, г = г;

д d д d \

Е /п Е д^Хзг Е /п Е д^Хл

ао +

1=1 1=1

УУ

+

1=1 1=1

ри

г = 1, п, г = 1, п, £ = п + 1 + г, г Ф г.

Элементы матрицы переходных вероятностей ||рк (я) для запросов £-го

пользователя (, к = 1,2п +1, £ = 1, п), по сравнению с моделью, представленной в [1], модифицируются следующим образом:

Р„

1 -Е

1=1

Е /А

I=1

у

д й

ЕЕ /Ач

I =1 у=1

>х. , / = 1, к = я +1;

Е

1=1

Е /Аи

1=1

д ^

ЕЕ /А*

1=1 *=1

>х. , / = 1, к = п + я +1;

1, если Е

у=1

Е /Аг

1=1

1*

д й

ЕЕ /Ац

1 =1 *=1

>х. ф 0 и г = 1,п,/ = г +1,1 ф я +1,к = 1;

г = 1,п,I = п +1 + г,г ф я,к = г +1 и г = я,к = 1;

Е

1=1

Е /А*

1=1

д й

ЕЕ /Ац

1=1 у=1

1-Е

1=1

Е /А

1=1

д й

ЕЕ /А

1=1 1=1

, если Е

1=1

Кх.

Е /^Аг

1=1

11

д й

ЕЕ /я1А11 1=11=1

>х ф 1,при / = я +1,г = 1,п,

к = п +1 + г, к ф п + я +1; 0, во всех остальных случаях.

Т =

Расчёт среднего времени реакции системы производится по формуле

г \ 1

Ех я

v «=1 у

ЕхТ,

я=1

где X2 (^ = 1, п) - интенсивность формирования запросов я-м пользователем; Тя (я = 1, п) - среднее время реакции системы на запрос я-го пользователя.

Величину Тз определим как Тз = , где Я*, (я = 1, п) - среднее количество

Хз

запросов Б-го пользователя; , (з = 1, п) - средняя интенсивность формирования запросов з-м пользователем. Величины N и Х* определим как: N = 1 - Рз (<), Хз =ХзРз (<), где Рз(ф - вероятность того, что з-й пользователь находится в активном состоянии (формирует запрос). Расчёт величины Рз(<) аналогичен расчёту величины Р8(1) для информационной системы на базе файл-серверной архитектуры с простым типом запросов [1] . Аналогично работе [1], расчёт величины Т также по существу сводится к расчёту нормализующей константы 0(И1,...,Мп), для вычисления которой был использован рекуррентный метод Бузена [6,11].

Для решения задачи оптимального размещения РБД по узлам ЛВС был использован эвристический алгоритм, приведённый в работе [1].

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

Таблица№1

Результаты машинных экспериментов

Размерность задачи пх<хд Начальное значение --31 Число итераций МПП Значение Время решения задачи МПП, с Число итераций э> Значение Время решения задачи ЭА, с Д,%

3x4x5 7,1426 81 2,6875 8,8 2 2,8603 3,72 -6

6x8x10 2,1347 68 0,9712 223 5 1,1023 34,11 -14

8x13x15 3,1807 813 - - 9 2,1619 192,2 -

10x15x20 2,1845 1015 - - 14 0,1826 1332,5 -

Здесь МПП - метод полного перебора; ЭА - эвристический алгоритм; Т(г - среднее время реакции системы для оптимального размещения РБД,

полученного МПП; Г1Л| - среднее время реакции системы для оптимального размещения РБД, полученного ЭА; А - относительная погрешность, выраженная в % между оптимальным размещением, полученным МПП и оптимальным размещением, полученным с помощью ЭА.

Разработанная модель оптимального размещения РБД по узлам ЛВС на базе двухуровневой клиент-серверной архитектуры также может быть использована при внедрении интегрированных информационно-справочных систем на промышленных предприятиях.

Литература

1. Скоба А.Н., Состина Е.В. Математическая модель оптимального размещения распределённой базы данных по узлам ЛВС на базе файл-серверной архитектуры. // Инженерный вестник Дона. 2015. №2. URL:ivdon.ru/ru/magazine/archive/n2y2015/2881.

2. Богуславский Л.Б., Ляхов А.И. Оценка производительности распределённых информационно-вычислительных систем архитектуры «КЛИЕНТ-СЕРВЕР» // Автоматика и телемеханика.-1995.-С.160-175.

3. Воробьёв С.П., Горобец В.В. Исследование модели транзакционной системы с репликацией фрагментов базы данных, построенной по принципам облачной среды // Инженерный вестник Дона. 2012. №4. URL:ivdon.ru/ru/magazine/archive/n4y2012/1149.

4. Павлов С.В., Самойлов А. С. Проектирование структуры распределённой базы пространственных данных в сложно структурированных иерархических географических информационных системах // Инженерный вестник Дона. 2015. №1. URL:ivdon.ru/ru/magazine/archive/n1y2015/2755.

5. Вишневский В.М. Теоретические основы проектирования компьютерных сетей.- М.: Техносфера, 2003.- 512 с.

6. Жожикашвили В. А.,Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. - М.:Радио и связь, 1988.-192с.

7. Герасимов А.И. Теория и практическое применение стохастических сетей. М.:Радио и связь.,1994. 175с.

8. Antunes C.H. et al. A Multiple Objective Routing Algorithm for Integrated Communication Network // Proc. ITC-16.-1999.V.3b. pp.1291-1300.

9. Chakka R., Harrison P.G. A Markov modulated multi-server queue with negative customers -Ihe MM CPP/GE/c/LG-queue // Acta Informatika.2001. v.37. pp.785-799.

10. Черноморов Г.А. Теория принятия решений: Учебное пособие / Юж.-Рос.гос. техн.ун-т.-3-е изд.перераб. и доп.-Новочеркасск : Ред. журн. «Изв. Вузов. Электроомеханика», 2005. 448с.

11. Круглый З.Л. Алгоритмы расчёта моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины.-1980. №4. С.73-79.

References

1. Skoba A.N., Sostina E.V. Inzenernyj vestnik Dona (Rus), 2015. №2.URL:ivdon.ru/ru/ magazine/archive/n2y2015/2881.

2. Boguslavsky L. B., Lyakhov A. I. The performance evaluation of distributed information systems of the "Client-server» architecture. Automation and telemechanics.1995. pp. 160-175.

3. Vorobyov S. P., Gorobets V. V. Inzenernyj vestnik Dona (Rus), 2012. №. 4. URL: ivdon.ru/ru/magazine/archive/n4y2012/1149.

4. Pavlov S. V., Samoilov A. S. Inzenernyj vestnik Dona (Rus), 2015. №1.URL: ivdon.ru/ru/magazine/archive/nly2015/2755.

5. Vishnevskiy V.M. Teoreticheskie osnovy proektirovaniya komp'yuternykh setey [Theoretical foundations of computer network design].M: Tekhnosfera, 2003. 512p.

6. Zhozhikashvili V.A., Vishnevskiy V.M. Seti massovogo obsluzhivaniya. Teoriya i primenenie k setyam EVM [Queueing networks. Theory and its network application].M: Radio i svyaz', 1988. 192p.

7. Gerasimov A.I. Teoriya i prakticheskoe primenenie stokhasticheskikh setey [Theory and practical application of stochasticnetworks].M: Radio i svyaz', 1994. 175p.

8. Antunes C. H. et al. A Multiple Objective Routine Algorithm for Integrated Communication Network. Proc ITC-16.1999. V. 3b.pp. 1291-1300.

9. Chakka R., Harrison P. G. A Markov modulated multi-server queue with negative customers-The MM CPP/GE/c/L G-queue. Actalnformatica, 2001, V. 37.pp.785-799.

10. Chernomorov G.A. Teoriya prinyatiya resheniy[decision making theory]: Uchebnoe posobie. Yuzh.-Ros.gos. tekhn. un-t. 3-e izd. pererab. i dop. Novocherkassk: Red. zhurn."Izv.vuzov.Elektromekhanika", 2005.448p.

11. Kruglyy Z.L. Algoritmy rascheta modeley struktur vychislitel'nykh sistem s razlichnymi klassami zadaniy. Upravlyayushchie sistemy i mashiny.1980. №4.pp.73-79.