polimd/Data Bases 2/lesson_03.md

DB2 - lesson 03

Paraboschi

13 October 2015

Concurrency Control pt.II

Conflict Graph

It is used to test conflict-serializability

Structure:

• One node for each transaction $T_i$
• One arc from $T_i$ to $T_j$ if it exists at least one conflict between an action of $T_i$ and an action of $T_j$ such as $a_i$ precedes $a_j$.

A schedule is in CSR iff its conflict graph is acyclic.

Properties:

• if $S$'s graph is acyclic, then it has a
  • topological sort: An ordering of the nodes such that the graph only contains arcs (i,j) with i<j
• The serial schedule whose transactions are ordered according to the topological sort is conflict-equivalent to $S$, because for all conflicting pairs (i,j) it is always i<j
• In general there can be many topological sorts, i.e. serializations for the same acyclic graph

Concurrency control in practice

The conflict-graph technique would be efficient if we knew the graph from the beginning, but we don't.

A scheduler must work incrementally: decide for each operation to execute it or not.

It is not feasible to mantain the graph, update it, and verify its acyclicity at each operation request.

Locking

It's the most common method in commercial systems

A transaction is well-formed wrt locking if:

• read operations are preceded by r_lock (shared lock) and followed by unlock
• write operations are preceded by w_lock (exclusive lock) and followed by unlock

When a transaction first reads and then writes and object, it can:

• Use a w_lock
• Modify a r_lock into a w_lock (lock escalation)

Lock primitives

• r_lock: read lock
• w_lock: write lock

• unlock

  Possible states of an object

• free

• r_locked: locked by a reader

• w_locked: locked by a writer

Behaviour of the lock manager

The lock manager receives the primitives from the transactions and grants resources according to the conflict table

• When a lock request is granted, the resource is acquired
• When an unlock is executed, the resource becomes available.

Request	free	r_locked	w_locked
r_lock	OK - r_locked	OK - r_locked	NO - w_locked
w_lock	OK - w_locked	OK - r_locked	NO - w_locked
unlock	ERROR	OK - DEPENDS	OK - FREE

Two-Phase Locking

Requirements:

• A transaction cannot acquire any other lock after releasing a lock
• Locks on a transaction can be released only after commit/abort operations

A scheduler which:

• Uses well-formed transactions
• grants locks according to conflicts
• is Two-Phase Produces the schedule class called 2PL

Schedules is 2PL are serializable

2PL and CSR

Every 2PL schedule is also conflict-serializable, but the converse is not necessarily true.

Counter example

$r_1(x)w_1(x)r_2(x)w_2(x)r_3(y)w_1(y)$

• It violates 2PL
  

$r_1(x)w_1(x)$ |T1 rel $r_2(x)w_2(x)r_3(y)$ |T1 acq $w_1(y)$

• It is conflict-serializable
  T3 < T1 < T2

2PL implies CSR

$$2PL\subset CSR\subset VSR$$

• Consider for each transaction the moment in which it has all resources and is going to release the first one
• We sort the transactions by this temporal value and consider the corresponding serial schedule
• We want to prove that this schedule is conflict-equivalent to $S$
  • We then consider a conflict between an action from $t_i$ and an action from the $t_j's$ with $i<j$
  • Can they occur in the reverse order in $S$?
  • No, because then $t_j$ should have released the resource in question before $t_i$ has acquired it.

Strict 2PL

We were still using the hypotesis of commit-projection

To remove this hypotesis we need to add a constraint to 2PL, thus obtaining strict 2PL

Locks on a transaction can be released only after commit/rollback

This version of 2PL is used in commercial DBMSs

Implementation of 2-Phase Locking

Lock tables are in reality main memory data structures

• Resource state can be:
  • free
  • read-locked
  • write-locked
• Every resource has also a read counter
• Some late '90 systems only supported exclusive locks (binary info, no counter)

A transaction asking for a lock is either franted a lock or queued and suspended,
the queue is FIFO, there is danger of:

• Deadlock: endless wait
• Starvation: individual transaction waiting forever
  Starvation can occur for write transactions waiting for resources which are higly used for reading (e.g. index roots)