Databases Reference
In-Depth Information
http://folk.uio.no/jongr/flacs_model.html
.
In this paper, we describe the
protocol using pseudocode as a set of
rules
. The following message types are in-
volved in completing the execution of a transaction
t
:
-
informObserver:
Sent from
t
's initiator to
t
's observers to initiate
t
's ordering.
-
propagateOrder:
Propagate the order upwards in the validation hierarchy.
-
validateRequest:
Sent from
t
's initiator to its validator (see Section 3.3).
-
commit:
Sent from
t
's validator to all processes to signal commit.
-
abort:
Sent from a process which determines that
t
must abort.
The following variables represent the local state of each process
p
:
-
DATABASE
: A set of records (
i
,
value
,
seqnum
,
update-history
,
lock-reqs
)
representing
p
's version of the database, where
value
is the local value of item
i
;
seqnum
is the sequence number of the most recent update of
i
;
update-
history
is a list containing the transaction name of previous updaters of
i
;
and
lock-reqs
is a list of requests for either read lock or write lock on
i
.
-
LOCAL-ORDER
: A list of transaction ids representing the local order at
p
.
-
REMOTE-TRANS
: The set of currently executing remote transactions.
-
ORDER-GRAPH
: A graph of transactions awaiting to be
ordered
at
p
.
-
VALIDATE-REQ
: A list representing received validation requests.
RULE:
EXECUTE-TRANS(t
)
while
t has more operations
do
(optype,i)
= getNextOperation(
t
)
wait for lock on i
when
lock granted
do
executeOperation(
t, optype
)
when
aborted by high priority transaction
do
abortTransaction()
ops
t
= getExecutedOperations(
t
)
RS
(
t
) = getReadSet(
ops
t
)
RVe r
(
t
) = findReadVersions(
ops
t
,
DATABASE
)
WS
(
t
) = getWriteSet(
ops
t
)
writeobs
= getWriteObservers(
WS
(
t
))
validator
= findValidator(
RS
(
t
),
writeobs
)
multiCast
informObserver(
t
,
WS
(
t
))
from
p
to
writeobs
uniCast
validateRequest(
t
,
RS
(
t
),
WS
(
t
),
WVal
(
t
),
RVe r
(
t
))
from
p
to
validator
await
commit decision
if
commit granted
then
report success to client
else
report abort to client
releaseLocks(
t
,
DATABASE
)
Fig. 2.
Initial execution at initiator
4.1 Initial Execution
The execution of a transaction
t
at
t
's initiator is described in Fig. 2. The op-
erations in
t
are executed sequentially, and we assume local concurrency control
using locks.
When all operations of
t
have been executed,
t
is submitted for ordering and
validation. The list of executed operations is logged, and the read set and write
set (including written values) can be retrieved. The initiator determines the ob-
servers for
t
and initiates the ordering protocol by multicasting
informObservers
Search WWH ::
Custom Search