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

Оценка математического ожидания времени чтения R реплик с учетом 
ожидания требованием на чтение окончания обновления W реплик. 
Математическое ожидание времени чтения R реплик с учетом ожидания 
требованием на чтение окончания обновления W реплик можно получить, 
дифференцируя (2.17) по s в нуле: 










R
1
i
(1)
i
Ω
Ξ
(0)
ψ
M
M
, 
(2.22) 
где M
Ω
определяется выражением (2.21), 

i
(s) определяется выражением 
(2.32). 
Для асинхронного режима выражение φ(s) = 



W
i
i
s
1
)
(
в (2.13) следует 
заменить на ПЛС функции распределения вероятностей случайной величины 
η=max(a
W+1
+b
W+1
, …, a
N
+b
N
) (см. рисунок 2.3). Если a
i
+b
i
имеют одинаковую 
функцию распределения вероятностей F(t), то [52]
P(ηN-W
(t). 
(2.23) 
2.1.4.
 
Преобразование Лапласа-Стилтьеса функции распределения 
вероятностей времени обновления i-й реплики 
Преобразование Лапласа-Стилтьеса (ПЛС) Ψ
i
(s) функции распределения 
вероятностей времени обновления i-ой реплики какой-либо записи было получено 
в [87, 91]. При выводе были использованы свойства ПЛС (2.2) ÷(2.5). 

---

56 
Представим время обновления как сумму двух составляющих: сетевой 
(передача данных между координатором и репликой) и локальной. Обозначим 
через Λ
i
(s,r,t) ПЛС сетевой составляющей времени обновления i-ой реплики, а 
через Θ
i
(s) – ПЛС локальной составляющей времени обновления i-ой реплики. 
Предполагая, что эти составляющие распределены по экспоненциальному закону, 
имеем 

 

t
nm
t
net
i
s
r
s
r
t
s




1
)
(
)
,
(
)
,
,
(


,
(2.24) 
s
v
k
r
v
k
r
r
s
net
net
net




)
/(
)
(
)
/(
)
(
)
,
(



,
ns
n
m
net
r
r







2
2
)
(
1
, 
(2.25) 
s
v
k
v
k
s
m
m
nm




)
/(
)
/(
)
(



. 
(2.26) 
где параметр t=1, если узел, содержащий i-ую реплику, не совпадает с 
координатором (передача данных по сети), 0 – иначе (передача данных в памяти 
узла). Параметр r=1, если узел, содержащий i-ую реплику, находится в подсети, не 
содержащий координатор (передача между сегментами сети), 0 – иначе (передача 
внутри одного сегмента сети).
φ
net
(s,r) – ПЛС времени передачи записи базы данных по сети. 
μ
m
– интенсивность чтения байтов данных из ОП (2/μ
m
- учитывает передачу 
данных из ОП в буфер сетевого адаптера (СА) до передачи по сети и передачу 
данных из буфера СА в буфер ОП после передачи по сети). 
μ
n
– интенсивность передачи байтов данных по локальной сети между 
станцией и коммутатором (2/μ
n
– предполагается, что коммутатор работает с 
буферизацией – это основной режим работы современных коммутаторов)). Будем 
считать, что подсети имеют одинаковую пропускную способность. 
μ
ns
– интенсивность передачи байтов данных по сети, соединяющей подсети. 
k – длина ключа записи (20-байтное число - RIAK, 16-байтное - Cassandra, 
Dynamo [31] (MD5)). 
v – длина поля «значение» записи. 

---

57 
ПЛС локальной составляющей:
)
(
)
(
kd
s
s
s
s
s
d
d
md
md
crc
crc
i















. 
(2.27) 
μ
crc
– интенсивность расчета контрольной суммы записи: 
)
1
4
)(
12
(
1
m







p
crc
v
k
, 
(2.28) 
где μ
p
– количество операций, выполняемых процессором в секунду, 
k+v+12 - длина структуры, для которой рассчитывается контрольная сумма; 
в нее входит 1) поле длиной k байтов, содержащее ключ записи, 2) поле длиной v 
байтов, содержащее значение записи, 3) поле длиной 4 байта, где хранится 
временная метка, 4) поле длиной 4 байта, где хранится длина ключа, и 5) поле 
длиной 4 байта, где хранится длина значения;
4 – учитывает, что для расчета контрольной суммы требуется 4 
процессорных операции на один байт данных [5348]. 
μ
md
– интенсивность передачи записи из ОП в буфер диска: 
m
md
v
k


1
)
16
(
1



, 
(2.29) 
(k+v+12)+4 - к предыдущей структуре добавляется поле длиной 4 байта, где 
хранится контрольная сумма. 
μ
d
– интенсивность чтения+записи блока на диск
1
1
1
d
d
wb



, 
(2.30) 
где μ
d1
– интенсивность чтения/записи байтов на диск, 
b – длина блока диска в байтах, 
w – учитывает время на чтение блока и время обязательной записи блока на 
диск после обновления записи (режим DW) (w=2). При чтении записи будем 
полагать, что w=1. 
φ
kd
(s) – ПЛС времени обновления хеш-таблицы (
keydir
) в ОП; не зависит от 
размера значения, т.к. хеш-таблица строится по ключу, значение которого 

---

58 
соответствует структуре <идентификатор файла, длина значения, смещение 
значения, временная метка>. Размер этой структуры - 20 байтов. 
s
s
k
k
s
p
p
m
kd






16
16
)
20
(
)
20
(
)
(
m





, 
(2.31) 
(20+K) – учитывает передачу описанной структуры в памяти и передачу 
ключа в кэш процессора для подсчета контрольной суммы. 
16 – учитывает, что количество процессорных операций, необходимых для 
подсчета хеша примерно равно 16. 
Таким образом, ПЛС времени обновления реплики можно определить, как: 
)
(
)
,
,
(
)
(
s
t
r
s
s
i
i
i





,
(2.32) 
где Λ
i
(s,r,t) и Θ
i
(s) определяются выражениями (2.24) и (2.27) 
соответственно.