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

2. Асинхронный режим. 
На рисунке 2.3 представлена модель согласования реплик для случая 
W+R
≤
N (асинхронный режим) [88, 96, 97, 101]. Входящий поток требований на 
чтение из одной реплики также принимается пуассоновским с параметром λ. 
...
λ
λ
λ
λ
a
W+1
a
a
a
W+2
W+3
N
b
b
b
b
N
W+1
W+2
W+3
...
ξ
ξ
ξ
ξ
W+1
W+2
w+3
N
t
t
t
t
t
0
Рисунок 2.3 – Модель согласования реплик в конечном счете (W+R
≤N
, 
асинхронный режим). 
На рисунке 2.3 введены следующие обозначения: a
i 
–
случайная
сетевая 
составляющая времени обновления i-ой реплики, b
i
– случайная локальная 
составляющая времени обновления i-ой реплики. В каждый момент времени с 
интенсивностью λ независимо друг от друга поступают требования на чтение 
записи БД из каждой реплики. Случайные промежутки времени между началом 
обновления t
0
и моментом поступления требования на чтение из i-ой реплики 
обозначим через ξ
i
. Задача состоит в том, чтобы оценить вероятность H, что за 
время обновления N-W реплик поступит хотя бы одно требование на чтение и по 
нему будет прочитана запись из ее необновленных реплик (R=1).
Чтение из i-ой реплики будет несогласованным, если ξ
i
.< a
i
. Вариант, когда 
требование на чтение поступает в промежуток времени b
i
(см. ξ
N
на рисунке 2.3) 

---

51 
не приводит к рассогласованию чтения, т.к. эта операция будет выполнена после 
обновления записи. Получим: 
)
(
1
)
:
(
1
)
:
(
i
i
i
i
i
i
a
i
P
a
i
P
a
i
P
H














(2.9) 
)
(
i
i
a
i
P



является вероятностью того, что не поступит ни одного 
требования на чтение из N-W реплик за время распространения обновления по 
сети. Пусть Λ
i
(s) – преобразование Лапласа-Стилтьеса функции распределения 
вероятностей F
i
(t) сетевой составляющей (a
i
) времени обновления i-ой реплики 
(выражение (2.24)). Тогда из (2.4) получим производящую функцию числа 
требований на чтение из i-ой реплики, поступивших за время a
i
: 
))
1
(
(
)
(
z
z
Q
i
a
i




(2.10) 
Вероятность того, что за сетевое время обновления i-ой реплики не 
поступит ни одного требования на чтение равно 
)
(
)
(

i
a
z
Q
i


. Т.к. требования на 
чтение из каждой реплики поступают независимо друг от друга, выражение (2.9) с 
учетом (2.10) можно переписать как: 






N
W
i
i
H
1
)
(
1

. 
(2.11) 
Это и есть вероятность, что клиент прочитает устаревшую запись за время 
распространения обновлений записи по ее N-W репликам (для асинхронного 
режима). 
Асинхронный режим обновления реплик поддерживает база данных NoSQL 
Amazon Dynamo, а также базы данных с типом репликации «master-slave» и 
«master-master».