Databases Reference
In-Depth Information
RULE:
INIT-ORDER
when
receive message informObserver(t,WS
(
t
)
)fromp
init
to p
do
Wseq
(
t
) = createEmptySeqnumMap()
if
p =/= p
init
then
newRemoteSubtransaction(
t
,
WS
(
t
))
insert
(
t
,
WS
(
t
)
,Wseq
(
t
))
into
REMOTE-TRANS
addNodeToOrderGraph(
t
,
order-graph
)
RULE:
ORDERED
when
all order requests received for t at p
and
predecessors(t,order-graph
)==
∅
do
(WS
(
t
)
,Wseq
(
t
)
)
=getTrans(
t
,
REMOTE-TRANS
)
append
t
to
LOCAL-ORDER
foreach
i in WS
(
t
)
do
if
hasAllObserversInSubtree(i, p)
then
seqnum
i
= incrementLocalSeqnum(
i
)
append
(i
→
item-seqnum
)
to
Wseq
(
t
)
q
=getParent(
p
)
if
q
=
nil
then fifoUnicast
propagateOrder(
t
,
p
init
,
WS
(
t
),
Wseq
(
t
))
to
q
removeFromOrderGraph(
t
)
RULE:
RCV-ORDER
when
receive message propagateOrder(tid, p
init
,WS
(
t
)
,Wseq
(
t
)
)fromp
do
if
not t ∈ REMOTE-TRANS
then
addNodeToOrderGraph(
t
,
order-graph
)
newRemoteSubtransaction(
t
,
WS
(
t
)
)
addEdgeToOrderGraph(
t
,
p
,
order-graph
)
if
hasCycle(order-graph)
then broadCast
abort(
t
)
func
hasAllObserversInSubtree(i :itemid,p :processid)
return
true
iff
p
is the lowest process in the validation hierarchy where all observers for
i
are
in the subtree rooted by
p
;
func
newRemoteSubtransaction(t : transaction id, WS
(
t
)
)
applyRemoteUpdatesWithHighPriorityLocks(
t
,
WS
(
t
),
DATABASE
);
Fig. 3.
Ordering
5 Performance Evaluation
We have implemented a simulation model using the Real-Time Maude tool, and
compared FLACS to a “classical” approach where one master process acts as
the central validator. The latter approach was previously shown to outperform
protocols that use atomic broadcast in wide-area networks [12]. Since recent
research focuses on atomic broadcast-based replica control or weaker consistency
models, this comparison is relevant to evaluate the performance of FLACS.
5.1 Experiment Setup
Our experiment setup is an imaginary international travel agent, providing ho-
tel bookings in Paris, New York, London, and Los Angeles. Each city is served
by one process, and each process maintains a complete copy of the database.
Scenario A
is a setting with a master validating all transactions.
Scenario B
is our FLACS model, where we assign as observer for an item
i
the process
most likely to access
i
. We assume a validation hierarchy and network setup as
shown in Fig. 5. We model a network with stochastic delay with average values
Search WWH ::
Custom Search