|
2.1.2.
Разработка модели процесса согласования реплик в конечном
счете
Определим синхронный и асинхронный режимы распространения
обновлений записи БД по ее репликам. Синхронный режим означает, что после
получения запроса на обновление данных координатор последовательно
направляет обновление следующей реплике после завершения обновления
предыдущей (рисунок 2.1а).
N
W+2
W+1
K
Обновление реплик
...
W
K
t
N
W+2
W+1
Обновление реплик
...
W
а)
б)
Рисунок 2.1 – Варианты распространения изменений:
а) синхронный режим; б) асинхронный режим.
48
При асинхронном режиме координатор направляет обновление следующей
реплике, не ожидая завершения обновления предыдущей (рисунок 2.1б). Время
обновления реплик при асинхронном режиме меньше, чем при синхронном, т.к.
распространение изменений выполняется параллельно. На рисунке 2.1
обновляемые реплики обозначаются 1,2, …, N, буквой К обозначен координатор.
1.Синхронный режим.
На рисунке 2.2 представлена модель рассогласования данных для случая
согласованности в конечном счете (W+R
≤N
) [87, 96, 97, 101]. Входящий поток
требований на чтение из одной реплики принимается пуассоновским с
параметром λ, Ψ
i
(s) – преобразование Лапласа-Стилтьеса функции распределения
вероятностей времени обновления i-ой реплики (определяется выражением (2.32),
которое рассматривается далее). В каждый момент времени с суммарной
интенсивностью (W+i)λ поступают требования на чтение из уже обновленных
реплик и с интенсивностью (N-W-i)λ – из необновленных реплик. Задача состоит
в том, чтобы оценить вероятность P того, что за случайный интервал обновления
реплик поступит хотя бы одно требование и по нему будет прочитана устаревшая
запись в R репликах.
Ψ
1÷W
(s)
Ψ
W+i
(s)
Ψ
W+i+1
(s)
Ψ
N
(s)
Write(W)
Распространение изменений
Read
Обновленные реплики
Необновленные реплики
(W+i)λ
(N-W-i)λ
Рисунок 2.2 – Модель согласования реплик в конечном счете (W+R
≤N
,
синхронный режим).
Для решения поставленной задачи сначала предлагается получить
производящую функцию Q
W+i+1
(z) числа требований на чтение записи, которые
пришли за случайное время обновления (W+i+1)-й реплики этой записи и по ним
были прочитаны R записей из ее N-W-i необновленных реплик (i=0…N-W-1).
Ψ
W+i+1
(s) – преобразование Лапласа-Стилтьеса (ПЛС) функции распределения
вероятностей времени обновления (W+i+1)-ой реплики. Обозначим через g
49
вероятность того, что поступившее требование на чтение из необновленной
реплики получит R-1 необновленных записей из других реплик.
))
1
)(
(
(
)
(
1
1
z
i
W
N
g
z
Q
i
i
W
i
W
,
(2.6)
иначе
0,
R
i
-
W
-
N
если
,
1
1
1
1
R
N
R
i
W
N
i
C
C
g
(2.7)
Формула (2.6) следует из (2.4). Формула (2.7) доказывается, исходя из
классического определения вероятности - это отношение благоприятного числа
комбинаций к общему числу комбинаций. В данном случае благоприятное число
комбинаций – это число вариантов, при которых после поступления требования
на чтение записи из необновленной реплики будет считано из БД (R-1)
необновленных записей из оставшихся (N-W-i-1) необновленных реплик. Общее
число комбинаций - это число вариантов, при которых можно считать данные из
(R-1) реплик этой записи из ее оставшихся (N-1) реплик (обновленных и
необновленных реплик).
Из (2.5) получим: Q
W+i+1
(0) - это вероятность, что за время обновления
(W+i+1)-ой реплики не поступят требования, по которым будут прочитаны R
записей из N-W-i необновленных реплик, (1 - Q
W+i+1
(0)) – это вероятность, что за
время обновления (W+i+1)-ой реплики поступит хотя бы одно требование на
чтение и по нему будет прочитано R записей из (N-W-i) необновленных реплик.
Таким образом, вероятность, что за время обновления N-W реплик поступит хотя
бы одно требование на чтение пары <ключ/значение> и по нему будет прочитано
R записей из необновленных реплик, равна:
W
N
i
i
j
j
W
i
W
W
Q
Q
Q
P
2
1
1
1
)
0
(
))
0
(
1
(
))
0
(
1
(
.
(2.8)
Выражение (2.8) следует из формулы полной вероятности. Это и есть
вероятность, что клиент прочитает устаревшую запись за время распространения
обновлений записи по ее N-W репликам.
50
Синхронный режим обновления реплик поддерживает база данных NoSQL
Riak. Этот режим поддерживает и система Hadoop. Только здесь обновления
распространяются последовательно от предыдущей реплики к последующей.
Do'stlaringiz bilan baham: |
