程序代写 Transaction classification

Transaction classification
Progressively increasing complexity levels
• Remote requests
• Remote transactions

• Distributed transactions • Distributed requests

Remote requests
• Read-only transactions including an arbitrary number of SQL queries • All the queries are addressed to a single remote DBMS
• The remote DBMS can only be queried

Remote transactions
• Composed of an arbitrary number of SQL commands (select, insert, delete, update)
• All the commands are addressed to a single remote DBMS • Each transaction writes one DBMS only

Distributed transactions
• Composed of an arbitrary number of SQL commands (select, insert, delete, update) addressed to an arbitrary number of remote DBMSs
• Each SQL command refers to a single DBMS
• Each transaction can update different DBMSs • requires two-phase-commit protocol

Distributed requests
• Arbitrary transactions composed of an arbitrary number of SQL commands (select, insert, delete, update) addressed to an arbitrary number of remote DBMSs
• Each command can refer to any DBMS
• Requires a distributed query optimizer

Transaction: example (1)
CC(Num,Name,Balance)
• CC1: σNum≤1000(CC)
• CC2: σNum>1000(CC)
• assume allocation transparency
Distributed transaction
• Transfer 100 Euros from account 354 to account 1487
it is necessary to guarantee atomicity: either both updates are executed or none of them

Transaction: example (2)
begin transaction
update CC1
set Balance = Balance – 100 where CCNum = 􏰀354􏰂;
update CC2
set Balance = Balance + 100 where CCNum = 􏰀1487􏰂;
end transaction

Technology of distributed databases (1)
Data distribution does not affect
• consistency: integrity constraints describe only local properties
• it is a limit of current DBMS technology
• persistency: each system guarantees persistency to locally stored data
• local recovery (log, checkpoint, dump) mechanisms Data distribution affects
• isolation
• atomicity

Technology of distributed databases (2)
Data distribution requires to modify
• Query optimization • Concurrency control
• isolation
• Reliability control • atomicity

Distributed query optimizer (1)
Under the responsibility of the DBMS that receives the query
• Decides how to divide the query in sub-queries, each addressed to a
specific DBMS
• Defines a strategy (plan) for distributed execution:
• Coordinated execution of different programs at different DBMSs • Data exchange among DBMSs
• Guarantees global optimization

Distributed query optimizer (2)
In the computation of distributed queries cost, the amount of data transmitted over the network is particularly important
Ctot=CI/O ́nI/O +CCPU ́nCPU +Ctr ́ntr
• ntr : amount of data transmitted over the network • Ctr : transmission cost

Concurrency control
In a distributed system, a transaction ti can execute multiple sub- transactions at different nodes:
• tij execution of ti at node j
• t1 : r11(x) w11(x) r12(y) w12(y) • t2 : r22(y) w22(y) r21(x) w21(x)

Concurrency control: example
S1 : r11(x) w11(x) r21(x) w21(x) S2 : r22(y) w22(y) r12(y) w12(y)
• Locally serializable (serial) • Globally non serializable
• The conflict graph includes a cycle:
• on node 1, t1 precedes t2 and is in conflict with t2 • on node 2, t2 precedes t1 and is in conflict with t1

of distributed transactions can be compromised by failures/malfunctions
• node failure (software/hardware)
• message lost: the execution of a protocol is left in a bad state
• each message of the protocol (msg) is followed by an acknowledgement of receipt message (ack)
• the loss of a message leaves the sender not sure about its reception
• failure of connection links: may cause network partitioning
• a transaction can be active simultaneously in different sub-networks

Global serializability
Local serializability does not guarantee global serializability
S1 : r11(x) w11(x) r21(x) w21(x) S2 : r22(y) w22(y) r12(y) w12(y)
• Locally serializable (serial) • Globally non serializable
Global serializability requires the presence of a serial schedule S equivalent to all the local schedules Si resulting at each node
• The projection of S on node i must be equal to Si

Global serializability: properties
Conflict-serializable global schedule
• guaranteed if each scheduler uses strict 2PL and executes atomic commit when all the sub-transactions at the different nodes have all the resources
Serial global schedule
• guaranteed if each distributed transaction acquires a single timestamp and uses it in all its requests to all the schedulers that perform concurrency control based on timestamp
– requires the assignment of a global timestamp

Logical clocks
Need to assign timestamps that reflect precedence among events in a distributed system
• If two processes do not interact it is not necessary that they are synchronized
• No matter that all processes agree on what time it is, but on the order in which events occur
• Lamport clocks and vector clocks are based on these observations

Happened-before
• aàb means that all transactions agree that first a occurs and then b occurs
• a and b are in the same transaction and a occurs before b
• a is the event of sending a message and b is the event of receiving the
• The relationship is transitive
• Events in different transactions that do not exchange messages are concurrent
• it is a partial order relationship

Lamport clocks
• How do we maintain a global view on the system’s behavior that is consistent with the happened-before relationship?
• Attach a timestamp C(e) to each event e s.t.:
• If a and b are two events in the same transaction, and aàb, then C(a)j

Identify distributed deadlock: example
DBMS1 DBMS2 DBMS3
t1 E2 t3 E3
E1 t1 E3 t2
•DBMS1 communicates to DBMS2 (E3®t3®t1®E2) DBMS2
E2 t2 E1 t3
E3 t3 t1 E3 t2
•DBMS2 communicates to DBMS3 (E3®t3®t2®E3)
E3 t2 E1 t3

Distributed commit protocols
Permits to a transaction to reach a correct commit or abort on all the nodes participating in the transaction
• Most widely used is two-phase commit

One-phase commit
• One process acts as a coordinator
• The coordinator tells all the other processes whether or not to locally
perform the operations
• There is no way to inform the coordinator if a participant cannot perform the operations

Two-phase commit (1)
• The commit/abort decision is taken by the parties and registered by a coordinator, distinguishing between:
• servers that participate in the decision: resource managers (RM) • coordinator process: transaction manager (TM)
• Works through the rapid exchange of messages (broadcast or serial) between TM and RM, and writing record logs
• TM and RM maintain logs to guarantee resistance to failures

Two-phase commit (2)
1. VotingPhase
1. TM sends VOTE_REQUEST to RMs
2. RMs replies with VOTE_COMMIT or VOTE_ABORT
2. Decisionphase
If all RMs vote commitàTM sends GLOBAL_COMMIT
if at least one RM voted abortàTM sends GLOBAL_ABORT
RMs who voted commit wait for a message from the TM: GLOBAL_COMMITàlocally commits its operations GLOBAL_ABORTàlocally aborts its operations

Two-phase commit (3)
Log: transaction manager
• Contains the identity of all the RM processes (node and process identifier)
• global commit or global abort
• Describes the global decision
• The decision by the TM is final when it is recorded in the log
• complete
• Records the end of the 2PC protocol

Two-phase commit (4)
Log: resource manager
• indicates the availability to participate in the 2PC protocol, and to contribute
to the final decision
• can be written only when the RM is in a reliable state, that is, when it has the lock on all the resources that need to be written
• reports the (node and process) identifier of the TM
• begin, insert, delete, and update • of the local transaction

Two-phase commit (5)
• When a RM declares that it is ready for a transaction, it loses its own autonomy and is subject to the decision of the TM
• uncertainty windows (should be minimized)
• the resources acquired by the transaction are blocked
• Before declaring the decision or declaring non-ready, RM can abort autonomously undoing its effects, without participating in the two-phase commit protocol

Protocol: first phase
• Writes prepare record in its log and sends a prepare message to all RM; sets
• If in a reliable state: writes a ready record in its log and sends a ready message to the TM, indicating its willingness to participate in the protocol
• If not in a reliable state: sends a non-ready message and terminates its participation in the protocol
• TM• Collects messages and writes in the log
§ global commit if all the RM answered ready
§ global abort if at least one RM answered non-ready or the timeout elapsed and not all messages have been received
the timeout • Each RM

Protocol: second phase
• Transmits the global decision (commit or abort) to all RM; sets the timeout
• Each RM in ready state
• Writes the decision record in the log and sends an acknowledgement (ack) to the
• Locally enforces the global decision
• Collects all the ack from the RM involved in the second phase
• If the timeout elapses, sets another timeout and resends the message to all RMs from which it did not get an ack
• When it received all the acks, writes complete record in its log

Two-phase commit protocol (1)
prepare msg
Global Decision
ready decision ack
msg Decision
Uncertainty window

Two-phase commit protocol (2)

Failure management and optimization
• An RM in ready state loses its autonomy waiting for the TM decision • Uncertainty window
• Possible failures can compromise the correct execution of the protocol
Þ protocols for failure recovery
Þ optimization to manage failures and of the uncertainty window

Two-phase commit protocol: failures (1)
TM and RMs are blocked waiting for incoming messages • What if they wait for a crashed process?
• Timeout mechanisms are used to avoid waiting forever

Two-phase commit protocol: failures (2)
RM in INIT state waits for VOTE_REQUEST
• If timeoutàlocally abort, send VOTE_ABORT to TM
TM in WAIT state waits for RMs’ votes
• If timeoutàvote for abort, send GLOBAL_ABORT to all RMs
RM in READY state waits for global decision by the TM If timeoutàblock until the TM recovers
If timeoutàcontact another RM Q
• Q reached the COMMIT state à commit
• Q reached the ABORT state à abort
• Q is in INIT state à the TM crashed while sending VOTE_REQUEST à P and Q abort
• Q is in READY stateàit turns out that all RMs are in ready state and can only wait for the recovery of the TM

Recovery protocols (1)
• A process can recover only if it saved its state to persistent storage
• RM in INIT stateàlocally decides to abort when it recovers
• RM in COMMIT or ABORT stateàknows that it should commit/abort when recovering
• RM in READY stateàneeds to contact another RM when it recovers

Recovery protocols (2)
Guarantee correctness of the node status in case of failures during the execution of 2PC protocol
• RM failure
• TM failure
• Loss of messages
• Network partitioning

RM failure
Warm recovery, depends on the last record in the log
• abortor action: undo the transaction
• commit: redo the transaction
• ready: failure during the two-phase commit; need to ask to the TM
During warm recovery:
• The identifiers of the transactions in doubt are collected in the READY set
• For each of these transactions, the final decision must be requested to the TM

TM failure
Warm recovery, depends on the last record in the log
• prepare: some RM could be blocked; two alternatives
• write a global abort in the log, and execute the second phase of the protocol
• repeat the first phase
• global commit/abort: some RM could have been correctly informed, while others could be still blocked
• TM should repeat the second phase
• complete: does not have effects on the transaction

Loss of messages
• The TM cannot distinguish between the lost of a prepare message or of the following ready messages
• In both cases, the timeout elapses and a global abort decision is taken
• It is not possible to distinguish between the loss of a decision (commit/abort) or of an ack message
• In both cases the timeout of the second phase elapses and the second phase is repeated

Network partitioning
Does not cause further problems
• The transaction will be successful only if the TM and the RMs belong to the same partition

Optimization
The 2PC protocol is quite expensive, mainly because of synchronous write operations (force) required on each log
Systems usually adopt two optimizations • supposed abort
• read only

Supposed abort
A TM receiving a remote recovery request from an uncertain RM and does not have any information on the transaction, returns a global abort as default
• prevents the write (force) of prepare and global abort records (recover with their equivalent as default)
• complete record is not critical and can be omitted (in the worst case, repeat the second phase)

One of the participants that executed only read operations in the transaction can declare to be read-only and leave the protocol
• the TM ignores read-only participants in the second phase of the protocol

• Four phase commit
• the TM is replicated by a backup process at a different node
• at each phase of the protocol, the TM first informs the backup of its decision and then communicates it to the RMs
• the backup can substitute the TM in case of failure
• Three phase commit
• introduces a pre-commit phase
• if the TM fails, one of the participants can be elected as the new TM
• is not used in practice because it makes the uncertainty window longer

Three-phase commit protocol (1)
• 3PC avoids blocking processes
• Rarely used because much more complicated than 2PC and the blocking conditions of 2PC rarely occur

Three-phase commit protocol (2)
1. VotingPhase
1. TM sends VOTE_REQUEST to RMs
2. RM replies with VOTE_COMMIT or VOTE_ABORT
2. Decisionphase
all RMs vote commit à TM sends PREPARE_TO_COMMIT
if at least one RM voted abortàTM sends GLOBAL_ABORT
RM receives PREPARE_TO_COMMIT à send ACK to TM TM receives all ACKs à send GLOBAL_COMMIT
RMs receive:
GLOBAL_COMMITàlocally commits its operations GLOBAL_ABORTàlocally aborts its operations

Three-phase commit protocol: failures (1)
• RM in INIT state waits for VOTE_REQUEST
• If timeoutàlocally abort, send VOTE_ABORT to TM
• TM in WAIT state waits for RMs’ votes
• If timeoutàvote for abort, send GLOBAL_ABORT to all RMs
• TM in PRECOMMIT waits for ACKs
• If timeoutàa RM crashed but already voted commit, sends a GLOBAL_COMMIT

Three-phase commit protocol: failures (2)
• RM in READY state waits for global vote by the TM
If timeoutàblock until the TM recovers
If timeoutàcontact another RM Q
Q reached the COMMIT state à commit
Q reached the ABORT state à abort
Q is in INIT state à the TM crashed while sending VOTE_REQUEST à P and Q abort The majority of the RMs are in PRECOMMIT state à commit
The majority of the RMs are in READY state à abort

Why Replication?
• Replication is used to guarantee and improve
• reliability: if one replica crashes, we use the others
• performance: supports geographic scalability since placing a replica close to the destination reduces access times
• It introduces a new problem: consistency
• updates must be properly propagated to all the replicas

Scalability
• Replication and caching improve geographical scalability
• Keeping replicas consistent may itself cause scalability issues
• Propagate updates to all the replicas in an atomic fashion is desirable
• It may not always be possible, due to synchronization issues among replicas
• Solution: loosen consistency constraint, not requiring updates to be atomic (depends however on the application)

Consistency models
• Data-centric consistency: each process is assumed to have a local (nearby) copy of the whole data store on which it performs reads and writes
• Client-centric consistency: weaker consistency model, that hides inconsistencies to the clients and that can be used if there is no simultaneous updates

Data-centric consistency
• When tentative updates to replicas need to be committed, all the replicas must agree on the global ordering of operations
• Protocols:
• Sequential consistency • Causal consistency

Sequential consistency (1)
The result of any execution is the same as if
• the (read and write) operations by all processes on the data store
were executed in some sequential order and
• the operations of each individual process appear in the sequence in the order specified by its program

Sequential consistency (2)
• All the processes see the same interleaving of operations • Other processes write operations
• Their read operations

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts