Databases Reference
In-Depth Information
2Sy emMod l
We formalize a system for storing and accessing replicated data as a tuple
(
P,U,I,O,T,Q,D,lb
)where:
-
P
is a finite set (of process identifiers representing a set of real-world
pro-
cesses
, typically a set of network hosts).
-
U
is a set (representing possible
data values
).
-
I
is a set (of identifiers for logical data items).
-
O
U
) is a set of possible operations on items.
-
T
is a set (of transaction identifiers).
-
Q
is a set of transactions of the form (
t, p, O
t,p
,<
t,p
), where
t
⊆
(
{
read
}×
I
)
∪
(
{
write
}×
I
×
∈
T
is the
O
is
the set of operations executed by
t
on
p
and
<
t,p
is a partial order on
O
t,p
.
-
D
transaction identifier,
p
∈
P
is the process hosting transaction,
O
t,p
⊆
P
is a set (with (
i,u,p
) a replica of
i
with value
u
at
p
).
-
lb
is a function
lb
:
P
⊆
I
×
U
×
×
P
→
N
(denoting the lower bound on the message
transmission time from
p
to
p
).
The
read set
of a transaction (
t, p, O
t,p
,<
t,p
)istheset
RS
(
t
)=
{
i
∈
I
|
(
read,i
)
∈
O
t,p
}
,andthe
write set
of
t
is
WS
(
t
)=
{
i
∈
I
|
(
write,i
)
∈
O
t,p
}
.Apairof
transactions
t
,
t
are in
conflict
if
WS
(
t
)
∩
(
RS
(
t
)
∪ WS
(
t
))
=
∅
, or vice versa.
A
read-only transaction
is a transaction
t
where
WS
(
t
)=
∅
. Managing read-
only transactions is relatively easy. Therefore, by the term
transaction
we will
mean a transaction
t
with
WS
(
t
)
unless stated otherwise. The treatment of
read-only transactions is discussed in Section 3.4.
We assume that processes communicate by message passing, and that each
pair (
p,p
) of processes is connected by a link with minimum message transmis-
sion time
lb
(
p,p
). We also assume that the underlying infrastructure provides
the following operations for inter-process communication:
=
∅
-
unicast
(
m,p,p
), where
m
is some message,
p
is the sender and
p
is the
receiver. Unicast does not guarantee any upper bound on message delivery
times nor that messages are delivered in the order in which they were sent.
-
fifoUnicast
(
m,p,p
). Similar to unicast, but guarantees that messages be-
tween two processes are delivered in the order in which they were sent.
We use simple utility functions for multicast and broadcast built on unicast, and
do not assume access to sophisticated group communication middleware.
3 Overview of the FLACS Protocol
State-of-the-art database replication protocols, such as Postgres-R [10] or DBSM
[11], provide serializability through optimistic validation combined with
atomic
broadcast
to order all transactions before commit. FLACS is an optimistic pro-
tocol following a similar approach with one notable exception: FLACS does not
require a total order on all transactions before validation. Instead, a transaction
t
is executed as follows:
Search WWH ::
Custom Search