• Concurrency control is the problem of synchronizing concurrent transactions (i.e., order the operations of concurrent transactions) such that the following two propertiesare achieved:

- the consistency of the DB is maintained

- the maximum degree of concurrency of operations is achieved

• Obviously, the serial execution of a set of transaction achieves consistency, if each single transaction is consistent

Conﬂicts

• Conﬂicting operations: Two operations Oij (x) and Okl(x) of transactions Ti and Tk

are in conﬂict iff at least one of the operations is a write, i.e.,

- Oij = read(x) and Okl = write(x)

- Oij = write(x) and Okl = read(x)

- Oij = write(x) and Okl = write(x)

• Intuitively, a conﬂict between two operations indicates that their order of execution is important.

• Read operations do not conﬂict with each other, hence the ordering of read operations does not matter.

• Example: Consider the following two transactions

T1: Read(x)

x ← x + 1

Write(x)

Commit

T2: Read(x)

x ← x + 1

Write(x)

Commit

- To preserve DB consistency, it is important that the read(x) of one transaction is not between read(x) and write(x) of the other transaction.

Schedules

• A schedule (history) speciﬁes a possibly interleaved order of execution of the operations O of a set of transactions T = {T1, T2, . . . , Tn}, where Ti is speciﬁed by a partial order (Σi , ≺i). A schedule can be speciﬁed as a partial order over O, where - ΣT =Sn i=1 Σi - ≺T ⊇ Sn i=1 ≺I - For any two conﬂicting operations Oij , Okl ∈ ΣT , either Oij ≺T Okl or Okl ≺T Oij

• A schedule is serial if all transactions in T are executed serially.

• Example: Consider the following two transactions

T1: Read(x)

x ← x + 1

Write(x)

Commit

T2: Read(x)

x ← x + 1

Write(x)

Commit

- The two serial schedules are S1 = {Σ1, ≺1} and S2 = {Σ2, ≺2}, where

Σ1 = Σ2 = {R1(x), W1(x), C1, R2(x), W2(x), C2}

≺1= {(R1, W1),(R1, C1),(W1, C1),(R2, W2),(R2, C2),(W2, C2),

(C1, R2), . . . }

≺2= {(R1, W1),(R1, C1),(W1, C1),(R2, W2),(R2, C2),(W2, C2),

(C2, R1), . . . }

• We will also use the following notation:

- {T1, T2} = {R1(x), W1(x), C1, R2(x), W2(x), C2}

- {T2, T1} = {R2(x), W2(x), C2, R1(x), W1(x), C1}

Serializability

• Two schedules are said to be equivalent if they have the same effect on the DB.

• Conﬂict equivalence: Two schedules S1 and S2 deﬁned over the same set of

transactions T = {T1, T2, . . . , Tn} are said to be conﬂict equivalent if for each pair

of conﬂicting operations Oij and Okl , whenever Oij <1 Okl then Oij <2 Okl.

- i.e., conﬂicting operations must be executed in the same order in both transactions.

• A concurrent schedule is said to be (conﬂict-)serializable iff it is conﬂict equivalent to a serial schedule

• A conﬂict-serializable schedule can be transformed into a serial schedule by swapping non-conﬂicting operations

• Example: Consider the following two schedules

T1: Read(x)

x ← x + 1

Write(x)

Write(z)

Commit

T2: Read(x)

x ← x + 1

Write(x)

Commit

- The schedule {R1(x), W1(x), R2(x), W2(x), W1(z), C2, C1} is

conﬂict-equivalent to {T1, T2} but not to {T2, T1}

Concurrency Control Algorithms

• Taxonomy of concurrency control algorithms

- Pessimistic methods assume that many transactions will conﬂict, thus the concurrent

execution of transactions is synchronized early in their execution life cycle

∗ Two-Phase Locking (2PL)

· Centralized (primary site) 2PL

· Primary copy 2PL · Distributed 2PL

∗ Timestamp Ordering (TO)

· Basic TO

· Multiversion TO

· Conservative TO

∗ Hybrid algorithms

- Optimistic methods assume that not too many transactions will conﬂict, thus delay

the synchronization of transactions until their termination

∗ Locking-based

∗ Timestamp ordering-based

DDB 2008/09 J. Gamper Page 10Locking Based Algorithms

• Locking-based concurrency algorithms ensure that data items shared by conﬂicting operations are accessed in a mutually exclusive way. This is accomplished by associating a "lock" with each such data item.

• Two types of locks (lock modes)

- read lock (rl) - also called shared lock

- write lock (wl) - also called exclusive lock

• Compatibility matrix of locks rli(x) wli(x) rlj (x) compatible not compatible

wlj (x) not compatible not compatible

• General locking algorithm

1. Before using a data item x, transaction requests lock for x from the lock manager

2. If x is already locked and the existing lock is incompatible with the requested lock, the transaction is delayed

3. Otherwise, the lock is granted Locking Based Algorithms

• Example: Consider the following two transactions

T1: Read(x)

x ← x + 1

Write(x)

Read(y)

y ← y − 1

Write(y)

T2: Read(x)

x ← x ∗ 2

Write(x)

Read(y)

y ← y ∗ 2

Write(y)

- The following schedule is a valid locking-based schedule (lri(x) indicates the

release of a lock on x):

S = {wl1(x), R1(x), W1(x), lr1(x)

wl2(x), R2(x), W2(x), lr2(x)

wl2(y), R2(y), W2(y), lr2(y)

wl1(y), R1(y), W1(y), lr1(y)}

- However, S is not serializable

∗ S cannot be transformed into a serial schedule by using only non-conﬂicting swaps

∗ The result is different from the result of any serial execution

Two-Phase Locking (2PL)

• Two-phase locking protocol

- Each transaction is executed in two phases

∗ Growing phase: the transaction obtains locks

∗ Shrinking phase: the transaction releases locks

- The lock point is the moment when transitioning from the growing phase to the

shrinking phase Two-Phase Locking (2PL) . . .

• Properties of the 2PL protocol

- Generates conﬂict-serializable schedules

- But schedules may cause cascading aborts

∗ If a transaction aborts after it releases a lock, it may cause other transactions that

have accessed the unlocked data item to abort as well

• Strict 2PL locking protocol

- Holds the locks till the end of the transaction

- Cascading aborts are avoided

DDB 2008/09 J. Gamper Page 14Two-Phase Locking (2PL) . . .

• Example: The schedule S of the previous example is not valid in the 2PL protocol:

S = {wl1(x), R1(x), W1(x), lr1(x)

wl2(x), R2(x), W2(x), lr2(x)

wl2(y), R2(y), W2(y), lr2(y)

wl1(y), R1(y), W1(y), lr1(y)}

- e.g., after lr1(x) (in line 1) transaction T1 cannot request the lock wl1(y) (in line 4).

- Valid schedule in the 2PL protocol

S = {wl1(x), R1(x), W1(x),

wl1(y), R1(y), W1(y), lr1(x), lr1(y)

wl2(x), R2(x), W2(x),

wl2(y), R2(y), W2(y), lr2(x), lr2(y)}

Timestamp Ordering . . .

• Basic timestamp ordering is "aggressive": It tries to execute an operation as soon as it receives it

• Conservative timestamp ordering delays each operation until there is an assurance that it will not be restarted, i.e., that no other transaction with a smaller timestamp can arrive

- For this, the operations of each transaction are buffered until an ordering can be established so that rejections are not possible

• If this condition can be guaranteed, the scheduler will never reject an operation

• However, this delay introduces the possibility for deadlocks

• Multiversion timestamp ordering

- Write operations do not modify the DB; instead, a new version of the data item is created: x1, x2, . . . , xn

- Ri(x) is always successful and is performed on the appropriate version of x, i.e., the version of x (say xv) such that wts(xv) is the largest timestamp less than ts(Ti)

- Wi(x) produces a new version xw with ts(xw) = ts(Ti) if the scheduler has not

yet processed any Rj (xr) on a version xr such that ts(Ti) < rts(xr)

i.e., the write is too late.

- Otherwise, the write is rejected.

• The previous concurrency control algorithms are pessimistic

• Optimistic concurrency control algorithms

- Delay the validation phase until just before the write phase

- Ti

run independently at each site on local copies of the DB (without updating the DB) - Validation test then checks whether the updates would maintain the DB consistent:

∗ If yes, all updates are performed ∗ If one fails, all Ti 's are rejected

• Potentially allow for a higher level of concurrency

Deadlock Management

• Deadlock: A set of transactions is in a deadlock situation if several transactions wait for each other. A deadlock requires an outside intervention to take place.

• Any locking-based concurrency control algorithm may result in a deadlock, since there is mutual exclusive access to data items and transactions may wait for a lock

• Some TO-based algorihtms that require the waiting of transactions may also cause deadlocks

• A Wait-for Graph (WFG) is a useful tool to identify deadlocks

- The nodes represent transactions

- An edge from Ti to Tj indicates that Ti is waiting for Tj

- If the WFG has a cycle, we have a deadlock situation

• Deadlock management in a DDBMS is more complicate, since lock management is not

centralized

• We might have global deadlock, which involves transactions running at different sites

• A Local Wait-for-Graph (LWFG) may not show the existence of global deadlocks

• A Global Wait-for Graph (GWFG), which is the union of all LWFGs, is needed

Deadlock Prevention

• Deadlock prevention: Guarantee that deadlocks never occur

- Check transaction when it is initiated, and start it only if all required resources are available.

- All resources which may be needed by a transaction must be predeclared

• Advantages

- No transaction rollback or restart is involved

- Requires no run-time support

• Disadvantages

- Reduced concurrency due to pre-allocation

- Evaluating whether an allocation is safe leads to added overhead

- Difﬁcult to determine in advance the required resources

Conclusion

• Concurrency orders the operations of transactions such that two properties are

achieved: (i) the database is always in a consistent state and (ii) the maximum

concurrency of operations is achieved

• A schedule is some order of the operations of the given transactions. If a set of

transactions is executed one after the other, we have a serial schedule.

• There are two main groups of serializable concurrency control algorithms: locking based and timestamp based

• A transaction is deadlocked if two or more transactions are waiting for each other. A Wait-for graph (WFG) is used to identify deadlocks

• Centralized, distributed, and hierarchical schemas can be used to identify deadlocks

Resources

Top Categories

Product

Company