Databases Reference
In-Depth Information
is granted commit if and only if, for each member
i
of
RS
(
t
),
Rver
(
t
) contains
the most recent version of
i
according to
≺
p
.
The correctness argument is the following: To perform this test at the val-
idating process
p
is equivalent to performing it at the root of the validation
hierarchy, where the ordering is global. Since all observers for
t
are contained
within the subtree rooted at
p
,
t
's ordering at
p
is consistent. Additionally, due
to the ordering being propagated upwards in the validation hierarchy, we know
that any preceding transaction in conflict with
t
will be known at
p
upon
t
's
validation. Therefore, the validation test for
t
at
p
is equivalent to testing at
the root of the validation hierarchy and FLACS guarantees serializability (and
consequently, strong consistency).
If
t
fails the validation test, a message
abort
(
t
) is broadcast. Otherwise, a
commit message for
t
is sent to all processes replicating items updated by
t
.
This may include processes that are neither the initiator, observers or part of
the validation hierarchy for
t
. Since transactions updating the same items may
be validated by different processes, commit messages can arrive out of order. To
handle this, we introduce
sequence numbers
. For an item
i
, the lowest process
p
where all
q
obs
(
i
) are in the subtree rooted at
p
, is responsible for the sequence
number of
i
. Whenever
p
orders a transaction
t
updating
i
, the sequence number
of
i
is incremented and propagated upwards in the validation hierarchy together
with the proposed ordering for
t
.Consequently,
t
's validator will have a complete
set of sequence numbers for items in
WS
(
t
). We denote this set
Wseq
(
t
).
Upon receiving a commit message
commit
(
t,
WS
(
t
)
,
Wval
(
t
)
,
Wseq
(
t
)), each
process
p
replicating items in
WS
(
t
) initiates a local transaction containing
t
's
write operations. For each item
i
, the sequence number of the most recent version
is stored at
p
. We refer to this value as
curseq
(
i,p
). We then apply Thomas'
Write Rule: Let
seq
i
t
represent the sequence number of
i
created by
t
.Fora
replicated item
i
at process
p
, we apply
t
's write operation at
p
if and only if
curseq
(
i,p
)
<seq
i
t
.
∈
3.4 Fault Tolerance and Read-Only Transactions
For fault tolerance, our ordering protocol represents the first phase of a two-
phase commit. If we assign more than one observer to an item, and then require
the validator to synchronize with observers before commit, this item will be
accessible as long as a majority of observers are available. In future work, we
will combine FLACS with Paxos to provide more sophisticated fault tolerance.
To ensure a consistent read set, a read-only transaction
t
r
must be executed
at, or validated by, a process
p
u
where, for every item
i
in
RS
(
t
r
), there is at least
one observer for
i
in the subtree rooted by
p
u
. Read-only transactions requiring
“fresh” data follow the same validation procedure as update transactions.
4TheFLACSProtocol
This section presents the FLACS protocol in more detail. The complete for-
mal, executable Real-Time Maude specification of FLACS is available at
Search WWH ::
Custom Search