Database Reference
In-Depth Information
X
w
X
r
T
z
p
: Date of write
: Possible date of read
: Time to write the first replica
: To tal propagation time
X
r
X
w
Time
T
T
p
FIGURE 10.3
Situation that leads to a stale read.
stochastic variables
X
w
and
X
r
of a write time and read time follow an exponential
distribution of parameters
λ
−1
and λ
r
, respectively. The probability of the next read
being stale corresponding to the aforementioned situation is given by Equation 10.1,
with
N
being the replication factor in the system and
X
being the number of replicas
involved in the read operation, and
T
p
is the average time to propagate an update to
other replicas. Here
X
n
= 1 for the basic eventual consistency.
∞
=
NX
N
−=
<<++
(
1
)
(
)
+
X
=
1
(
)
i
i
i
i
Pr stale ead
(
_)
=
n
Pr
XXXTT
n
Pr
XXXT
w
<<+
w
r
w
p
r
w
N
(10.1)
i
0
After simplifying (more details can be found in [11]), the final value of the prob-
ability of next read to be stale, is given by
−
λ
T
=
−− +
(
N
11
)(
e
N
)(
1
λλ
)
rp
rw
Pr stale ead
(
_)
(10.2)
λλ
rw
10.6.3 h
armony
i
mPlementation
Harmony can be applied to different cloud storage systems that are featured with
flexible consistency rules. The current implementation of Harmony operates on
top of
Apache Cassandra
storage [52] and consists of two modules. The monitor-
ing module collects relevant metrics about data access in the storage system: read
rates and write rates, as well as network latencies. These data are further fed to
the adaptive consistency module. This module is the heart of the Harmony imple-
mentation where the estimation and the resulting consistency level computations are
performed: the Harmony estimation model, which is based on probabilistic compu-
tations, predicts the stale read rate in accordance to the statics fed by the monitoring
module. Accordingly, as shown in Algorithm 10.1, Harmony chooses whether to
select the basic consistency level ONE (involving only one replica) or else, computes
Search WWH ::
Custom Search