Модели процессов согласования реплик в базах данных Nosql

2. ϕ=сумма(ξ)
Рисунок 2.10 – Модель ведения версий записи. 
На рисунке 2.10 приняты следующие обозначения: 
λ – параметр экспоненциального закона распределения вероятностей 
времени обдумывания клиентом (1…K) результатов работы с версиями записи,
τ
i
– момент поступления требования на чтение версий записи от i-го 
источника (клиента):
i
-й клиент читает W версий записей, φ
= 

W
1

- время 
обработки всех версий записи клиентом, ξ - случайное время обработки, 
связанное с одной версией записи, W – текущее число версий записи в базе 
данных NoSQL. 

---

68 
Массив обработки версий записи содержит один столбец. Значение Q
i 
– это 
число версий записи, которые необходимо удалить из базы данных в момент, 
когда i-й источник покидает фазу обработки.
Функцию распределения вероятностей числа версий записи, одновременно 
хранящихся в базе данных NoSQL, сложно представить в аналитическом виде. 
Поэтому предлагается имитационный подход к моделированию. В таблице 2.3 
приводится описание алгоритма работы модели. 
Таблица 2.3 – Алгоритм модели по варианту 1. 
№ 
Пункт алгоритма 
Примечание 
1 Положить W=1, массив обработки пуст. 
Новая запись включена в БД. 
2 j-ое требование поступает на обработку. Наступил момент времени τ
j
. 
3 Сохранить текущее число версий записи 
в j-ой строке массива: Q
j 
= W, 
определить φ, задержать транзакт 
(требование) на время φ (обработать 
записи). 
j-й клиент читает W версий записи из базы 
данных, φ
= 

W
1

, ξ - случайное время 
обработки, связанное с одной версией записи. 
4 Если 
очередное 
j-ое 
требование 
поступает на обработку, то перейти к 
пункту 3 алгоритма 
Наступило очередное время τ
j
5 Если 
требование покидает массив 
обработки (пусть это будет j-я строка 
массива), то выполнить следующие 
действия: 
а) W: = W - Q
j 
+ 1 
б) для всех строк массива обработки 
Q
i 
:= Q
i 
- Q
j
, 
если Q
i 
< 0, то положить Q
i 
= 0 
в) задержать клиента на время 
обдумывания результатов работы с 
версиями. 
Клиент j обработал прочитанные версии 
записи (затратив на это время φ
)
, сформировал 
вектор часов, удаляет из БД все старые версии 
записи (если их ранее не удалил другой 
клиент, т.е. если Q
j
≠0), добавляет в БД свою 
версию записи (+1, см. алгоритм 2 ведения 
версий записи в пункте 2.3.1). 
Учесть, что Q
j
, версий записи уже удалены из 
БД текущим j-м клиентом и их не надо удалять 
i-м клиентом (если Q
j
,≠0). Затем покидающее 
i-ое требование удалит ранее им считанные 
версии, которые остались не удаленными, и 
увеличит число версий записей W на единицу 
(см. пункт 5а – другие версии записей, 
поступившие позже чтения записей i-м 
клиентом, этот клиент удалить не может, т.к. 
они будут содержать в векторе часов новые 
номера версий других клиентов – это 
объясняет, почему только минус Q
j
в 5а). 
6 Перейти к пункту 4 алгоритма 

---

69 
Для реализации предложенного в таблице 2.3 алгоритма выбран язык GPSS 
[58]. GPSS является средством моделирования параллельных процессов. Система 
позволяет задавать различные функции распределения вероятностей для 
случайного времени пребывания в источнике (времени обдумывания) и времени 
обработки клиентом одной версии записи, а также имеет встроенные механизмы 
сбора статистики и построения гистограмм. В таблице 2.4 представлен текст 
модели на языке GPSS. 
Таблица 2.4 – Текст модели по варианту 1.
 
Метка 
Блок 
Комментарий 
LMBD EQU 5.5 
1 / 
λ = 5.5
NKL EQU 30 
Число клиентов = 30 
INITIAL X$VER_N,1 
W := 1 
MAS MATRIX ,30,1 
Массив обработки (1 столбец) 
STAT_VER 
TABLE X$VER_N,1.5,1,31 
Создание таблицы для сбора статистики по числу 
версий записи 
STAT_VRVZ 
TABLE X$VRVZ,10,10,20 
Создание таблицы для сбора статистики по 
времени обработки записей 
GENERATE ,,,NKL 
Генерация NKL транзактов (клиентов) 
ASSIGN 1,XN1 
k = номер транзакта (клиента) 
MET1 
ADVANCE (EXPONENTIAL(7,0,LMBD)) 
Задержать клиента на время обдумывания
MSAVEVALUE MAS,*1,1,X$VER_N 
Q[k] := W 
ASSIGN 2,X$VER_N 
Число итераций := W 
SAVEVALUE VRVZ,0 
Здесь будет накапливаться время обработки 
версий записи
MET2 
SAVEVALUE VRVZ+,FN$VRF 
VRF - имя функции вычисления времени 
обработки одной записи 
LOOP 2,MET2 
Цикл по количеству итераций 
TABULATE STAT_VRVZ 
Заполнить статистику по времени обработки 
записей
ADVANCE X$VRVZ 
Задержка клиента на время обработки записей 
SAVEVALUE VER_N-,MX$MAS(*1,1) 
W := W - Q[k] 
SAVEVALUE VER_N+,1 
W := W + 1 
TABULATE STAT_VER 
Заполнить статистику по количеству записей 
SAVEVALUE TODEL,MX$MAS(*1,1) 
Сохранить Q[k] в переменную 
ASSIGN 2,NKL 
Число итераций := число клиентов 
MET3 
MSAVEVALUE MAS-,*2,1,X$TODEL 
Q[i] := Q[i] - Q[k] 
TEST L MX$MAS(*2,1),0,MET4 
Если Q[i] < 0, то 
MSAVEVALUE MAS,*2,1,0 
Q[i] := 0 

---

70 
Продолжение таблицы 2.4 
Метка 
Блок 
Комментарий 
MET4 
LOOP 2,MET3 
Цикл по количеству итераций 
TRANSFER ,MET1 
Перейти к источнику