|
Оценка математического ожидания времени чтения 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)
соответственно.
Do'stlaringiz bilan baham: |
