Transcript Document

Pusan National University
em
Spatiotemporal Database Laboratory
File Processing : Concurrency Control
2004, Spring
Pusan National University
Ki-Joune Li
Pusan National University
em
Serializability

For given transactions T1, T2,.., Tn,

Spatiotemporal Database Laboratory


Schedule (History) S is serializable if
Result(S)  Result(Sk) where Sk is a serial excution schedule.
Note that Result(Si ) may be different from Result(Sj ) (i  j )
How to detect whether S is serializable

Conflict Graph
Pusan National University
em
Conflict Graph
S1
T1
r(b)
r(a)
Res(S1)  Res( (T1, T2) )
Spatiotemporal Database Laboratory
affects
T2
w(a)
w(b)
S2
T1
r(a)
r(b)
Res(S1)  Res( (T1, T2) )
affects
Res(S1)  Res( (T2, T1) )
T2
w(a)
w(b)
Pusan National University
em
Detect Cycle in Conflict Graph
T1
r(a)
r(b)
T1
affects
Spatiotemporal Database Laboratory
T2

w(a)
w(b)
If  Cycle in Conflict Graph


Then Not Serializable
Otherwise Serializable
T2
Pusan National University
em
How to make it serializable

How to make it serializable


Timestamping
Spatiotemporal Database Laboratory


Control the order of execution of operations in concurrent transactions.
Ordering by timestamp on each transaction and each operation
Two Phase Locking Protocol

Locking on each operation
Pusan National University
em
Lock-Based Protocols

A lock


Data items can be locked in two modes :

Spatiotemporal Database Laboratory
mechanism to control concurrent access to a data item

Exclusive (X) mode : Data item can be both read as well as
written. X-lock is requested using lock-X instruction.
Shared (S) mode : Data item can only be read. S-lock is
requested using lock-S instruction.

Lock requests are made to concurrency-control manager.

Transaction can proceed only after request is granted.
Pusan National University
Spatiotemporal Database Laboratory
em
Lock-Based Protocols (Cont.)

Lock-compatibility matrix

A transaction may be granted a lock on an item



if the requested lock is compatible with locks already held
Any number of transactions can hold shared locks
If a lock cannot be granted,



the requesting transaction is made to wait
till all incompatible locks held have been released.
the lock is then granted.
Pusan National University
Spatiotemporal Database Laboratory
em
Lock-Based Protocols

Example of a transaction performing locking:
T2: lock-S(A);
read (A);
unlock(A);
lock-S(B);
read (B);
unlock(B);
Pusan National University
em
The Two-Phase Locking Protocol

This is a protocol which ensures conflict-serializable schedules.

Phase 1: Growing Phase


Spatiotemporal Database Laboratory

Phase 2: Shrinking Phase



transaction may obtain locks
transaction may not release locks
transaction may release locks
transaction may not obtain locks
The protocol assures serializability
Pusan National University
em
Lock Conversions

Two-phase locking with lock conversions:

First Phase:


Spatiotemporal Database Laboratory


Second Phase:




can acquire a lock-S on item
can acquire a lock-X on item
can convert a lock-S to a lock-X (upgrade)
can release a lock-S
can release a lock-X
can convert a lock-X to a lock-S (downgrade)
This protocol assures serializability
Pusan National University
Spatiotemporal Database Laboratory
em
Where to insert Lock related operations ?


A transaction Ti

issues the standard read/write instruction,

without explicit locking calls.
Automatic Acquitistion of Locks

The operation read(D) is processed as:
if Ti has a lock on D
then read(D)
else
begin
wait until no other transaction has a lock-X on D
grant Ti a lock-S on D;
read(D)
end
Pusan National University
Spatiotemporal Database Laboratory
em
Automatic Acquisition of Locks

write(D) is processed as:
if Ti has a lock-X on D
then write(D)
else
begin
if necessary wait until no other trans. has any lock on D,
if Ti has a lock-S on D
then upgrade lock on D to lock-X
else grant Ti a lock-X on D
write(D)
end;

All locks are released after commit or abort
Pusan National University
em
Lock Manager

Transaction

Spatiotemporal Database Laboratory


Transaction sends lock request to
Lock Manager
Lock Manager determines whether to
allow or not
Lock Table


Keeps granted locks and pending
locks for each item
In-memory Hash Table
Pusan National University
em
Problem of Two Phase Locking Protocol

Deadlock

Growing Phase and Shrinking Phase

Spatiotemporal Database Laboratory


Prevention and Avoidence : Impossible
Only Detetion may be possible
When a deadlock occurs


Detection of Deadlock : Wait-For-Graph
Abort a transaction

How to choose a transaction to kill ?
Pusan National University
em
Tree Lock : A Special Locking Mechanism

Only exclusive locks are allowed.

Spatiotemporal Database Laboratory


The first lock by T may be on any
data item.
Subsequently, a data Q can be
locked by T
only if the parent of Q is currently
locked by T.
Pairwise lock
Data items may be unlocked at any
time.
Not Allowed
Pusan National University
em
Timestamp-Based Protocols

Each transaction is issued a timestamp when

TS(Ti) <TS(Tj) :

Spatiotemporal Database Laboratory

old transaction Ti and new transaction Tj
Each data Q, two timestamp :

W-timestamp(Q) : largest time-stamp for sucessful write(Q)

R-timestamp(Q) : largest time-stamp for sucessful read(Q)
Pusan National University
em
Timestamp-Based Protocols : Read

Transaction Ti issues a read(Q)

If TS(Ti)  W-timestamp(Q),


Spatiotemporal Database Laboratory

then Ti needs to read a value of Q that was already overwritten.
Hence, the read operation is rejected, and Ti is rolled back.
If TS(Ti)  W-timestamp(Q),


then the read operation is executed, and
R-timestamp(Q) is set set
Pusan National University
em
Timestamp-Based Protocols : Write

Transaction Ti issues write(Q).

If TS(Ti) < R-timestamp(Q),


Spatiotemporal Database Laboratory


If TS(Ti) < W-timestamp(Q),



then the value of Q that Ti is producing was needed previously,
and the system assumed that that value would never be produced.
Hence, the write operation is rejected, and Ti is rolled back.
then Ti is attempting to write an obsolete value of Q.
Hence, this write operation is rejected, and Ti is rolled back.
Otherwise,


the write operation is executed,
and W-timestamp(Q) is reset
Pusan National University
Spatiotemporal Database Laboratory
em
Correctness of Timestamp-Ordering Protocol

The timestamp-ordering protocol guarantees serializability
since all the arcs in the precedence graph are of the form:
transaction
with smaller
timestamp

transaction
with larger
timestamp
Thus, there will be no cycles in the conflict graph
Timestamp protocol : free from deadlock
Pusan National University
em
Problem of Timestamping Protocol

Cascade Rollback

Spatiotemporal Database Laboratory

Thomas Rule
Rollback and Restarting Overhead

Instead of Deadlock Detection
Pusan National University
em
Long Duration Transaction

Transaction

Spatiotemporal Database Laboratory


Problem



of Long Duration
with large number of operations
Expensive rollback and restart
Degradation of concurrency
Approach


Nest Transaction
Semantic Consistency rather than Serializability