Распределение баз данных по узлам сети с учетом репликаций

Необходимо определить вариант рационального размещения предметных баз данных в распределенной информационной системе для случая, когда каждая база данных может иметь произвольное число репликаций (копий), размещаемых на любых узлах (размещается только в одном узле сети главная репликация - мастер-репликация). Обрабатывающие процессы (приложения) не являются распределенными. При этом считать, что если некоторый процесс обращается за данными к базе, находящейся в другом узле, сетевые затраты на одно обращение составляют “t” секунд, независимо от местонахождения узла в сети и дисциплины обслуживания. Если процесс обращается к базе данных, находящейся в том же узле, где выполняется процесс, то считать, что “t = 0”.

На создание и поддержку репликаций средние приведенные затраты назначаем согласно следующей формуле:

где N - значение из таблицы П.51;

k - значение коэффициента из таблицы П5.2;

N₂ - исходное значение затрат на создание и поддержку репликаций БД, соответствующее варианту задания.

Рассчитанные значения N₂ приведены в таблице П5.8

Таблица П5.8

Исходные данные для варианта с репликациями

Узел	Проц.	Коэф К	Коэф	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10
У1	П5	0,3
П7	0,6	0,5
У2	П2	0,5	0,6
П6	0,7	0,429
П7		0,3
П8	1,1	0,272
У3	П5	0,8	0,375
П7	1,15	0,261
У4	П2	0,8	0,375
П7	0,9	0,333
П8	0,8	0,375
У6	П2	0,8	0,375
П6	1,6	0,188
П8	0,2	1,5
У7	П2	0,6	0,5
П5	1,2	0,25
П6	1,4	0,214
П8	0,7	0,428

Сгруппируем данные по процессам одного узлам, отнесенные к одной и той же БД так, чтобы в каждой клетке новой таблицы П5.9 было число, равное приведенным затратам на создание и поддержку репликации БД при помещении ее в этот узел

Таблица П5.9

Затраты на создание и поддержку репликации БД при помещении ее в соответствующий узел

Узел	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10
У1						-
У2						-
У3						-
У4						-
У6						-
У7						-

Таким образом, получены исходные данные для варианта с репликациями,

показывающие затраты на создание и поддержку репликации БД при помещении ее в соответствующий узел

Задача размещения репликаций баз данных в узлах сети решается при фиксированном размещении самих баз данных в сети. Эта задача оптимального размещения баз данных по узлам была решена ранее. Мы получили следующие два оптимальных варианта:

Вариант 1

(БД1/У5, БД2/У4, БД3/У4, БД4/У2, БД5/У7, БД7/У7, БД8/У6, БД9/У3, БД10/У2)

Вариант 2

(БД1/У5, БД2/У6, БД3/У4, БД4/У2, БД5/У7, БД7/У7, БД8/У6, БД9/У3, БД10/У2)

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

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

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

Таблица П5.10

Стоимость обращения к узлу , где БД при отсутствии реплик

Узел	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10
У1
У2
У3
У4
У6
У7

Таблица П5.11

Стоимость содержания реплики базы данных в узле

Узел	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10
У1						-
У2						-
У3						-
У4						-
У6						-
У7						-

После этого составим таблицу П5.12, элементы которой покажут для каких БД целесообразно создавать реплики и в каких узлах эти реплики следует размещать. Каждый элемент этой таблицы должен быть равен разности соответствующих элементов таблиц П5.10 и П5.11.

Реплики БД следует ставить в те узлы, которым соответствует положительное значение элемента таблицы П5.12

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

Таблица П5.12

Данные о целесообразности создания и размещения реплик БД

Узел	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10
У1					- 60		- 210		- 17
У2		- 40
У3
У4
У6			- 133	- 78	- 97
У7

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

Рассмотрим эти варианты.

Варианты оптимального размещения баз данных и их реплик в сети.

Считаем, что в исходном состоянии без использования репликаций, базы данных размещаются оптимально в соответствии с вариантом 1, приведенным в таблице П5.7

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

Вариант 1а - создаем только одну реплику для той БД, которая дает наибольший выигрыш в уменьшении суммарного количества обращений ко всем БД..

Вариант 1б - создаем три реплики для тех БД, которые дают наибольший выигрыш в уменьшения суммарного количества обращений ко всем БД в сети.

Вариант 1в - создаем только одну реплику для каждой БД

Вариант 1а

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

Таблица 6.13.

Вариант размещения БД и одной реплики по узлам сети

	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10	Оценка
БД	У3	У4	У4	У2	У7	-	У7	У6	У3	У2
Число обращений						-
Реплики								У7
Число обращений						-

Суммарное количество обращений к базам данных в сети снизилось на 7,35%

Вариант 1б

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

Таблица П5.14

Вариант размещения БД и трех реплик по узлам сети

	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10	Оценка
БД	У3	У4	У4	У2	У7	-	У7	У6	У3	У2
Число обращений						-
Реплики		У6				-	У6	У7
Число обращений						-

Суммарное количество обращений к базам данных в сети снизилось на 16,1%

Вариант 1в

Для каждой БД создаем только одну реплику, которая дает наибольший выигрыш в уменьшения суммарного количества обращений ко всем БД.

Таблица П5.15

Вариант размещения БД и одной их реплики по узлам сети

	БД1	БД2	БД3	БД4	БД5	БД6	БД7	БД8	БД9	БД10	Оценка
БД	У3	У4	У4	У2	У7	-	У7	У6	У3	У2
Число обращений						-
Реплики	У2	У6	У3	У4	У2	-	У6	У7	У7	У6
Число обращений						-

Суммарное количество обращений к базам данных в сети снизилось на 25,4%

Приложение 6

Аналитическое моделирование рассматриваемой PCOD методом фонового потока

Формализованная схема и исходные данные рассматриваемой РСОД

Общая формализованная схема PCOD в виде сети массового обслуживания (СМО) приведена на рис.П6 1, а формализованная схема рассматриваемой PCOD в виде CMO приведена на рис П6.2

Рис. П6.1 . Формализованная схема PCOD, содержащая ПЭВМ, канал и сервер.

Рис.П6.2 . Формализованная схема рассматриваемой PCOD

В схеме используются следующие обозначения

- обслуживающий аппарат, имитирующий дообработку на i-той рабочей станции сети запроса от этой станции к серверу после обработки запроса на сервере

- обслуживающий аппарат, имитирующий формирование запроса от i-той рабочей станции к серверу; ( );

- буфер, имитирующий очередь запросов к каналу;

— обслуживающий аппарат, имитирующий задержку при передаче данных через канал;

- буфер, имитирующий очередь запросов к процессорам;

- обслуживающие аппараты, имитирующие работу процессоров.

- буфер, имитирующий очередь запросов к i-му диску;

- обслуживающий аппарат, имитирующий работу i-го диска.

Р - вероятность обращения запроса к ЦП после обработки на диске. Обслуживание заявок во всех ОА подчиняется экспоненциальному закону.

Исходными данными аналитической модели являются:

Обозначение	Описание
- N	- число рабочих станций сети
- Т0	- среднее значение времени дообработки на рабочей станции сети запроса от этой станции к базе данных на сервере
- Тр	- среднее значение времени формирования запроса от рабочей станции сети к базе данных на сервере
- tк	- среднее значение времени передачи запроса по каналу
- С	- число процессоров сервера
- tпр	- среднее значение времени обработки запроса в ЦП сервера
- tдi	- среднее значение времени обработки запроса в диске сервера
- Рi	- вероятность обращения запроса к i диску сервера после обработки запроса в процессоре

Выходными характеристиками аналитической модели являются:

Обозначение	Описание
- Треак	- среднее значение времени реакции системы
- rк	- коэффициент загрузки ОА, имитирующего работу канала передачи данных
- rпр	- коэффициент загрузки ОА, имитирующего работу процессора сервера
- rдi	- коэффициент загрузки ОА, имитирующего работу i–ого диска сервера

Введём следующие обозначения:

l_ф1 – среднее значение суммарной интенсивности фонового потока запросов, выходящих из ОА, имитирующих работу рабочих станций, в канал

l_ф1b – среднее значение интенсивности фонового потока запросов, проходящих через ОА, имитирующих работу сервера и дисков, где b=1/(1–р) ;

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

t_к – среднее значение времени обработки запроса в канале передачи данных;

t_к=0.5(t_к1+ t_к2 ).

Где t_к1 и t_к2 соответственно среднее время передачи запроса по каналу в прямом и обратном направлениях.

n – количество серверов, обслуживающих рабочие станции;

количество дисков в сервере, при условии, что все они одинаковые

- вероятность обращения к i-му диску сервера

Порядок расчета рассматриваемой системы методом фонового потока

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

1. Определяем начальное значение для l_ф1

lф1= К₁min

К₁ принимает значения в диапазоне 0.995…0.99995.

2. Определяем средние времена пребывания запроса в узлах системы: канале, процессоре, дисках:

.

3. Определяем интенсивность фонового потока после очередной итерации:

4. Сравниваем l_ф1 и l_ф .Если , то переход на пункт 6, иначе на пункту 5

5. Определяем новое приближённое значение для l_ф1:

К2 принимает значения в диапазоне 10…1000, .

Переход на пункт 2.

6. Определяем выходные результаты аналитической модели.

Определяем средние времена пребывания запроса в узлах системы: канале, процессоре и дисках.

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

где

где

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

Номер эксперимента
Исходные данные
Количество рабочих станций
Среднее время дообработки запроса на РС
Среднее время формирования запроса на РС
Среднее время передачи через канал в прямом направлении
Среднее время передачи через канал в обратном направлении
Количество процессоров
Среднее время обработки запроса на процессоре
Количество дисков
Среднее время обработки запроса на диске
Вероятность обращения запроса к диску сервера после обработки запроса в процессоре	0,5	0,5	0,5	0,5	0,5
Вероятность обращения запроса к ЦП после обработки на диске
Результаты моделирования.
Загрузка рабочей станции	0,84	0,92	0,74	0,74	0,70
Загрузка пользователя рабочей станции	0,42	0,46	0,37	0,37	0,32
Среднее количество работающих РС	14,10	15,80	12,75	12,75	11,90
Среднее количество РС формирующих запрос	7,14	7,80	6,29	6,29	5,95
Загрузка канала	0,42	0,23	0,74	0,37	0,32
Загрузка процессора	0,42	0,23	0,37	0,75	0,32
Загрузка диска 1	0,42	0,23	0,37	0,37	0,64
Загрузка диска 2	0,42	0,23	0,37	0,37	0,64
Среднее время цикла системы
Среднее время реакции системы

Примечание.

1. Количество рабочих станций должно соответствовать номеру варианта задания, за исключением следующих пяти случаев: для первого варианта N=31, для второго N=32, для третьего N=33, для четвертого N=34, для пятого N=35.

2. При проведении экспериментов среднее значение времени дообработки запроса на рабочей станции должно принимать следующие значения Т₀ = 10*N , Т₀ = 20*N ,

Т₀ = 30*N

3. При проведении экспериментов среднее значение времени формирования запроса на рабочей станции сети к базе данных на сервере должно принимать следующие значения Т₀ = 10*N , Т₀ = 20*N , Т₀ = 30*N.

4. При проведении экспериментов среднее значение времени передачи запроса по каналу, если канал медленный, должно принимать значение t_к=-5

5. При проведении экспериментов средние значения времени обработки запроса в ЦП сервера и на диске сервера должны принимать следующие значения t_цп =10 или t_цп =20,

t_д = 10 или t_д = 20.

Приложение 7

Имитационное моделирование рассматриваемой PCOD на GPSS

Формализованная схема моделируемой PCOD приведена на рис.П7.1

Рис П7.1 . Формализованная схема моделируемой PCOD

Укрупненная структура программы моделируемой РСОД на языке GPSS

Структура программы имеет следующий вид

Блоки и метки	Пояснение
INITIAL	Задание количественных и временных параметров исходных данных моделируемой системы
STORAGE	Задание многоканальных узлов системы
FUNCTION	Задание функции распределения запросов по узлам и времени выполнения запросов в узлах
GENERATE	Генерация количества задач, циркулирующих в системе
Метка WOSF	Объединяет набор блоков, описывающих формирование запроса на рабочей станции
Метка CAN	Объединяет набор блоков, описывающих обработку эапроса в канале
Метка SVR	Объединяет набор блоков, описывающих обработку эапроса в процессоре
Метка REP	Объединяет набор блоков, описывающих правило перехода запроса после обработки на диске в канал
Метка WOSD	Объединяет набор блоков, описывающих дообработку запроса на рабочей станции

Текст программы на языке GPSS

INITIAL X$STATION_N,17

INITIAL X$STATION_TD,170

INITIAL X$STATION_TF,170

INITIAL X$CANAL_T,5

INITIAL X$SERVER_T,10

INITIAL X$DISK_N,2

INITIAL X$DISK_T,20

WORKSTATION_D STORAGE 10

WORKSTATION_F STORAGE 10

SERVER STORAGE 1

DISK_N FUNCTION RN1,D2

0.5,1/1,2

EXPON FUNCTION RN1,C23

0,0/.1,.104/.2,.222/.3,.355/.4,.510/.5,.69/.6,.915/.7,1.2/

.75,1.37/.8,1.5/.84,1.83/.88,2.12/.9,2.3/.92,2.52/.94,2.82/

.95,2.98/.96,3.2/.97,3.5/.98,3.9/.995,5.3/.998,6.2/.9995,7/1,8

GENERATE ,,,X$STATION_N

WOSF QUEUE QSYSTEM

ENTER WORKSTATION_F,1

ADVANCE X$STATION_TF,FN$EXPON

LEAVE WORKSTATION_F,1

ASSIGN 3,SVR

CAN QUEUE QCANAL

SEIZE CANAL

DEPART QCANAL

ADVANCE X$CANAL_T,FN$EXPON

RELEASE CANAL

TRANSFER ,P3

SVR ENTER SERVER,1

ADVANCE X$SERVER_T,FN$EXPON

LEAVE SERVER,1

ASSIGN 5,FN$DISK_N

QUEUE P5

SEIZE P5

DEPART P5

ADVANCE X$DISK_T,FN$EXPON

RELEASE P5

TRANSFER 0.0, PER,SVR

PER ASSIGN 3,WOSD

TRANSFER ,CAN

WOSD ENTER WORKSTATION_D,1

ADVANCE X$STATION_TD,FN$EXPON

LEAVE WORKSTATION_D,1

DEPART QSYSTEM

TRANSFER ,WOSF

GENERATE 100000

TERMINATE 1

START 1

Листинг программы имитационного моделирования

GPSS World Simulation Report - Untitled Model 1.1.1

Wednesday, April 04, 2008 00:12:25

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 100000.000 31 3 3

NAME VALUE

CAN 7.000

CANAL 10013.000

CANAL_T 10003.000

DISK_N 10005.000

DISK_T 10006.000

EXPON 10010.000

PER 23.000

QCANAL 10012.000

QSYSTEM 10011.000

SERVER 10009.000

SERVER_T 10004.000

STATION_N 10000.000

STATION_TD 10001.000

STATION_TF 10002.000

SVR 13.000

WORKSTATION_D 10007.000

WORKSTATION_F 10008.000

WOSD 25.000

WOSF 2.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 17 0 0

WOSF 2 QUEUE 4187 0 0

3 ENTER 4187 0 0

4 ADVANCE 4187 8 0

5 LEAVE 4179 0 0

6 ASSIGN 4179 0 0

CAN 7 QUEUE 8357 0 0

8 SEIZE 8357 0 0

9 DEPART 8357 0 0

10 ADVANCE 8357 1 0

11 RELEASE 8356 0 0

12 TRANSFER 8356 0 0

SVR 13 ENTER 4178 0 0

14 ADVANCE 4178 0 0

15 LEAVE 4178 0 0

16 ASSIGN 4178 0 0

17 QUEUE 4178 0 0

18 SEIZE 4178 0 0

19 DEPART 4178 0 0

20 ADVANCE 4178 0 0

21 RELEASE 4178 0 0

22 TRANSFER 4178 0 0

PER 23 ASSIGN 4178 0 0

24 TRANSFER 4178 0 0

WOSD 25 ENTER 4178 0 0

26 ADVANCE 4178 8 0

27 LEAVE 4170 0 0

28 DEPART 4170 0 0

29 TRANSFER 4170 0 0

30 GENERATE 1 0 0

31 TERMINATE 1 0 0

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

1 2128 0.423 19.866 1 0 0 0 0 0

2 2050 0.417 20.345 1 0 0 0 0 0

CANAL 8357 0.424 5.075 1 12 0 0 0 0

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

1 6 0 2128 1269 0.292 13.707 33.957 0

2 6 0 2050 1252 0.256 12.482 32.066 0

QSYSTEM 17 17 4187 0 17.000 406.019 406.019 0

QCANAL 7 0 8357 5032 0.277 3.309 8.317 0

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

WORKSTATION_D 10 2 0 10 4178 1 7.067 0.707 0 0

WORKSTATION_F 10 2 0 10 4187 1 6.985 0.698 0 0

SERVER 1 1 0 1 4178 1 0.406 0.406 0 0

SAVEVALUE RETRY VALUE

STATION_N 0 17.000

STATION_TD 0 170.000

STATION_TF 0 170.000

CANAL_T 0 5.000

SERVER_T 0 10.000

DISK_N 0 2.000

DISK_T 0 20.000

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

12 0 100002.177 12 10 11 3 13.000

5 2.000

13 0 100026.258 13 4 5 3 25.000

5 1.000

15 0 100026.997 15 26 27 3 25.000

5 1.000

18 0 100038.085 18 26 27 3 25.000

5 2.000

7 0 100059.127 7 26 27 3 25.000

5 1.000

3 0 100074.650 3 4 5 3 25.000

5 2.000

17 0 100103.267 17 4 5 3 25.000

5 1.000

1 0 100121.893 1 4 5 3 25.000

5 1.000

4 0 100124.859 4 26 27 3 25.000

5 1.000

9 0 100135.172 9 4 5 3 25.000

5 1.000

14 0 100168.711 14 26 27 3 25.000

5 2.000

6 0 100239.274 6 4 5 3 25.000

5 1.000

11 0 100275.227 11 4 5 3 25.000

5 1.000

16 0 100307.748 16 4 5 3 25.000

5 2.000

10 0 100327.341 10 26 27 3 25.000

5 2.000

8 0 100341.005 8 26 27 3 25.000

5 2.000

5 0 100586.390 5 26 27 3 25.000

5 2.000

19 0 200000.000 19 0 30