Advanced Database systems

Chapter 4: Concurrency Control Techniques

 Outline
 What is Concurrency Control?
 Purpose of Concurrency Control
 Concurrency Control Protocols
̶ Locking Techniques for Concurrency Control
̶ Concurrency Control Based on Timestamp Protocol
̶ Multi-version Concurrency Control Techniques
̶ Validation (Optimistic) Concurrency Control Technique
̶ Granularity of Data Items and Multiple Granularity Locking
̶ Using Locks for Concurrency Control in Indexes

2
 What is Concurrency control?
 Concurrency control is the procedure in DBMS for
managing simultaneous operations without conflicting with
each another.
 Concurrent access is quite easy if all users are just
reading data.
 There is no way they can interfere with one another.

 Though for any practical database, would have a mix of

reading and WRITE operations and hence the concurrency
is a challenge.

3
 Purpose of Concurrency Control
 Reasons for using Concurrency control method in a DBMS is:

̶ To enforce Isolation (through mutual exclusion) among

conflicting transactions.

̶ To preserve database consistency through consistency

preserving execution of transactions.

̶ To resolve read-write and write-write conflicts.

̶ The system needs to control the interaction among the concurrent

transactions. This control is achieved using concurrent-control
schemes.

̶ Concurrency control helps to ensure serializability

4
 Concurrency Control Protocols
 Different concurrency control protocols offer different benefits
between the amount of concurrency they allow and the amount
of overhead that they impose.
 Types of concurrency control protocols:
̶ Locking Techniques for Concurrency Control
 The Two-Phase Locking Protocol (2PLP)
̶ Concurrency Control Based on Timestamp Protocol
̶ Validation (Optimistic) Concurrency Control Technique
̶ Granularity of Data Items and Multiple Granularity Locking
̶ Multi version Concurrency Control Techniques
̶ Using Locks for Concurrency Control in Indexes
5
 Locking Techniques for Concurrency Control
 Lock:
̶ is a Variable associated with a data item describing status for
operations that can be applied
̶ One lock for each item in the database
 Lock Manager: Managing locks on data items.
 Lock table:
̶ Lock manager uses it to store the identify of transaction locking a data
item, the data item, lock mode and pointer to the next data item
locked. One simple way to implement a lock table is through linked list.
 Binary locks:
̶ Two states (values)
 Locked (1): Item cannot be accessed
6  Unlocked (0): Item can be accessed when requested
 Cont.…
 A locking protocol is a set of rules that state when a transaction may
lock or unlock each of the data items in the database.
 Locking is an operation which secures

A. (a) permission to Read

B. (b) permission to Write a data item for a transaction.

 Example:

̶ Lock (X): Data item X is locked in behalf of the requesting

transaction.
 Unlocking is an operation which removes these permissions from the
data item.
 Example:

̶ Unlock (X): Data item X is made available to all other transactions.

7
 Cont.…
Transaction requests access by issuing a lock_item(X) operation

8
Figure: Lock and unlock operations for binary locks
 Cont.…
 Data items can be locked in two modes :
1. Shared Mode (read-locked item ) :
 If a transaction Ti has obtained a shared mode lock on data item (A),
then Ti can read, but cannot write A.
 A read-locked item is also called share-locked because other
transactions are allowed to read the item.
2. Exclusive-Mode (write-locked item) :
 If a transaction Ti has obtained an exclusive-mode lock on data item
(A), then Ti can both read & write A.
 A write-locked item is called exclusive-locked because a single
transaction exclusively holds the lock on the item.

9
 Cont.…
 Lock requests are made to the concurrency-control manager by
the programmer.
 Transaction can proceed only after request is granted.

 Generally, using binary locks or read/write locks in

transactions does not guarantee serializability of schedules on
its own.
 There are two possible major problems may occur

I. The resulting transaction schedule may not be serializable

II. The schedule may create deadlocks

10
 Two-Phase Locking (2PL) Techniques
 In two-phase locking protocol, all locking operations precede
the first unlock operation in the transaction
 Three locking operations
̶ read_lock(X)
̶ write_lock(X)
̶ unlock(X)
 Phases:
̶ Expanding (growing) phase
 New locks can be acquired but none can be released
 Lock conversion upgrades must be done during this phase

̶ Shrinking phase
 Existing locks can be released but none can be acquired
 Downgrades must be done during this phase
11
 Cont.…
 Lock conversion:
̶ Transaction that already holds a lock allowed to convert
the lock from one state to another

 Upgrading
̶ Issue a read_lock operation then a write_lock operation

 Downgrading
̶ Issue a read_lock operation after a write_lock operation

12
 Cont.…
Variations of Two-Phase Locking Techniques:
 Dynamic 2-phase locking

 Static (Conservative) two-phase locking

 Strict two-phase locking

 The Rigorous 2 P Locking

13
 Cont.…
Dynamic 2-phase locking:
 A transaction locks a data item immediately before any
operation is applied on the data item.
 After finishing all the operations on all data item, it release all
the locks.

14
 Cont.…
Static (Conservative) two-phase locking:
 In this scheme, all the data item are locked before any
operation on them and are released any alter the last
operation performed on any transaction.

 Predeclare read-set and write-set

15
 Cont.…
Strict two-phase locking:
 It is a locking method used in concurrent system.

 The two rules of strict 2PL are:

I. If transaction T wants to read/write an object, it must request a
shared/exclusive lock on the object.
II. All exclusive lock held by transaction T are released when T
commits or aborts (& not before).
 Note:
 Strict 2PL prevents transactions reading uncommitted data,
overwriting uncommitted data and unrepeatable reads.
 Thus it prevent cascading roll backs since exclusive lock must
be held until a transaction commits.
16
 Cont.…
Example:

17
 Cont.…
The Rigorous 2P Locking:
 It requires all locks be held until the transaction commits.

 In Rigorous two-phase locking, a transaction can be

serialized in the order in which they commit.

18
 Cont.…
Deadlock:
̶ Occurs when each transaction T in a set is waiting for
some item locked by some other transaction T’ Both
transactions stuck in a waiting queue

19
 Cont.…
 Deadlock prevention protocols
̶ Every transaction locks all items it needs in advance
̶ Ordering all items in the database
 Transaction that needs several items will lock them in that order

 Protocols based on a timestamp

̶ Wait-die: If TS(Ti) < TS(Tj), then (Ti older than Tj) Ti is allowed to wait; otherwise
(Ti younger than Tj) abort Ti (Ti dies) and restart it later
̶ Wound-wait: If TS(Ti) < TS(Tj), then (Ti older than Tj) abort Tj (Ti wounds Tj) and
restart it later with the same timestamp; otherwise (Ti younger than Tj) Ti is
allowed to wait.
 No waiting algorithm
̶ If transaction unable to obtain a lock, immediately aborted and restarted later
 Cautious waiting algorithm: If Tj is not blocked (not waiting for some other
locked item), then Ti is blocked and allowed to wait; otherwise abort Ti.
̶ Deadlock-free
20
 Cont.…
 Deadlock detection
̶ System checks to see if a state of deadlock exists
̶ Wait-for graph

 Victim selection
̶ Deciding which transaction to abort in case of deadlock

 Timeouts
̶ If system waits longer than a predefined time, it aborts the
transaction
 Starvation
̶ Occurs if a transaction cannot proceed for an indefinite period
of time while other transactions continue normally
̶ Solution: first-come-first-served queue
21
Concurrency Control Based on Timestamp Protocol

 The serializable schedules produced by 2PL have their equivalent

serial schedules based on the order in which executing
transactions lock the items they acquire.

 If a transaction needs an item that is already locked, it may be

forced to wait until the item is released.

 Some transactions may be aborted and restarted because of the

deadlock problem.

 A different approach that guarantees serializability involves using

transaction timestamps to order transaction execution for an
equivalent serial schedule.

 2PL protocol guarantees serializability, but it does not prevent

deadlocks.
22
 Cont.…
Time stamps:
 Timestamp is a unique identifier created by the DBMS to identify
a transaction.

 Timestamp values are assigned in the order in which the

transactions are submitted to the system, so a timestamp can be
though as the start time.

 A DBMS Assigns a global unique time stamp to each

transaction.

 All database operations within the same transaction must have

the same timestamp.

 Concurrency control techniques based on timestamp

ordering do not use locks; hence, deadlocks cannot occur.
23
 Cont.…
 Timestamp is a monotonically increasing variable (integer)
indicating the age of an operation or a transaction.
 A larger timestamp value indicates a more recent event or
operation.
 Timestamp based algorithm uses timestamp to serialize the
execution of concurrent transactions.

24
 Cont.…
Basic Timestamp Ordering(TO) algorithm:
1. Transaction T issues a write_item(X) operation:
A. If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an younger
transaction has already read the data item so abort and roll-back T
and reject the operation.

B. If the condition in part (a) does not exist, then execute

write_item(X) of T and set write_TS(X) to TS(T).

2. Transaction T issues a read_item(X) operation:

A. If write_TS(X) > TS(T), then an younger transaction has already
written to the data item so abort and roll-back T and reject the
operation.

B. If write_TS(X)  TS(T), then execute read_item(X) of T and set

read_TS(X) to the larger of TS(T) and the current read_TS(X).
25
 Cont.…
Strict Timestamp Ordering algorithm:
1. Transaction T issues a write_item(X) operation:

 If TS(T) > read_TS(X), then delay T until the transaction T’

that wrote or read X has terminated (committed or
aborted).

2. Transaction T issues a read_item(X) operation:

 If TS(T) > write_TS(X), then delay T until the transaction T’

that wrote or read X has terminated (committed or
aborted).

26
 Cont.…
Thomas’s Write Rule:
A. If read_TS(X) > TS(T) then abort and roll-back T and reject
the operation.
B. If write_TS(X) > TS(T), then just ignore the write operation
and continue execution. This is because the most recent
writes counts in case of two consecutive writes.
C. If the conditions given in 1 and 2 above do not occur, then
execute write_item(X) of T and set write_TS(X) to TS(T).

27
 Cont.…
 Advantages of timestamp protocol:
̶ Deadlock free because no transaction even waits.
̶ Avoids control lock manager.
̶ Attractive in distributed database system.

 Disadvantages of timestamp protocol:

̶ T abort/restart can degree performance under high contention.
̶ Storage overhead per data item for timestamps.
̶ Update overhead to maintain timestamp.
̶ Potentially update during each read/write to a data item

 Note: The timestamp-ordering protocol ensure conflict

serializability, because operations are processed in
28
timestamp order.
 Multiversion Concurrency Control Techniques

 This approach maintains a number of versions of a data item

and allocates the right version to a read operation of a
transaction.
 Thus unlike other mechanisms a read operation in this
mechanism is never rejected.
 When a transaction requires access to an item, an appropriate
version is chosen to maintain the serializability of the
currently executing schedule, if possible.
 An obvious drawback of multiversion techniques is that more
storage is needed to maintain multiple versions of the
database items.

29
 Cont.…
Multiversion concurrency control scheme types:

 Multiversion Technique Based on Timestamp Ordering

 Multiversion Two-Phase Locking Using Certify Locks

 Validation (Optimistic) techniques

30
 Cont.…
Multiversion Technique Based on Timestamp Ordering:
 This approach maintains a number of versions of a data item and
allocates the right version to a read operation of a transaction.

 Thus unlike other mechanisms a read operation in this

mechanism is never rejected.

 Two timestamps associated with each version are kept

̶ read_TS(Xi)
̶ write_TS(Xi)

 Side effects: Significantly more storage (RAM and disk) is

required to maintain multiple versions. To check unlimited growth
of versions, a garbage collection is run when some criteria is
satisfied.
31
 Cont.…
Multiversion technique based on timestamp ordering…
 Assume X1, X2, …, Xn are the version of a data item X
created by a write operation of transactions. With each Xi
a read_TS (read timestamp) and a write_TS (write
timestamp) are associated.
 read_TS(Xi): The read timestamp of Xi is the largest of all the
timestamps of transactions that have successfully read version Xi.

 write_TS(Xi): The write timestamp of Xi that wrote the value of

version Xi.

 A new version of Xi is created only by a write operation.

32
 Cont.…
Multiversion technique based on timestamp ordering…
 To ensure serializability, the following two rules are used.
1. If transaction T issues write_item (X) and version i of X has the
highest write_TS(Xi) of all versions of X that is also less than or
equal to TS(T), and read _TS(Xi) > TS(T), then abort and roll-
back T; otherwise create a new version Xi and read_TS(X) =
write_TS(Xj) = TS(T).

2. If transaction T issues read_item (X), find the version i of X that

has the highest write_TS(Xi) of all versions of X that is also less
than or equal to TS(T), then return the value of Xi to T, and set
the value of read _TS(Xi) to the largest of TS(T) and the current
read_TS(Xi).

 Rule 2 guarantees that a read will never be rejected.

33
 Cont.…
 Multiversion Two-Phase Locking Using Certify Locks:

 Concept:
̶ Allow a transaction T’ to read a data item X while it is write locked
by a conflicting transaction T.

̶ This is accomplished by maintaining two versions of each data

item X where one version must always have been written by some
committed transaction. This means a write operation always
creates a new version of X.

34
 Cont.…
Multiversion Two-Phase Locking Using Certify Locks…
Steps:
1. X is the committed version of a data item.
2. T creates a second version X’ after obtaining a write lock on X.
3. Other transactions continue to read X.
4. T is ready to commit so it obtains a certify lock on X’.
5. The committed version X becomes X’.
6. T releases its certify lock on X’, which is X now.

Compatibility tables for

35
 Validation (Optimistic) Concurrency
Control Technique
 In all the concurrency control techniques, a certain degree of checking is

done before a database operation can be executed.

 For example,
 In locking, a check is done to determine whether the item being accessed
is locked.

 In timestamp ordering, the transaction timestamp is checked against

the read and write timestamps of the item. Such checking represents
overhead during transaction execution, with the effect of slowing down the
transactions.

 In validation, No checking is done while the transaction is

executing.

36
 Cont.…
 In optimistic concurrency control scheme, updates in the
transaction are not applied directly to the database items until
the transaction reaches its end.

 During transaction execution, all updates are applied to local

copies of the data items that are kept for the transaction.

 At the end of transaction execution, a validation phase checks

whether any of the transaction’s updates violate serializability.

 Certain information needed by the validation phase must be kept by

the system.

 If serializability is not violated, the transaction is committed and the

database is updated from the local copies; otherwise, the
transaction is aborted and then restarted later.
37
 Cont.…
 Optimistic concurrency control has Three phases:
1. Read phase: A transaction can read values of committed data items.
However, updates are applied only to local copies (versions) of the data
items (in database cache).
2. Validation phase: Serializability is checked before transactions write their
updates to the database.
 This phase for Ti checks that, for each transaction Tj that is either committed
or is in its validation phase, one of the following conditions holds:
 Tj completes its write phase before Ti starts its read phase.

 Ti starts its write phase after Tj completes its write phase, and the read_set of
Ti has no items in common with the write_set of Tj.
 Both the read_set and write_set of Ti have no items in common with the
write_set of Tj, and Tj completes its read phase.
3. Write phase: On a successful validation transactions’ updates are applied
38
to the database; otherwise, transactions are restarted.
 Granularity of Data Items and Multiple
Granularity Locking
 All concurrency control techniques assume that the database is
formed of a number of named data items.
 A database item granularity could be chosen to be one of the
following:
̶ A database record.
̶ A field value of a database/record.
̶ A whole file.
̶ The whole database.
̶ A disk block.
 The granularity can affect the performance of concurrency control
and recovery.

39
 Cont.…
Granularity Level Considerations for Locking:
 The size of data items is often called the data item granularity.
̶ Fine granularity refers to small item sizes, whereas
̶ Coarse granularity refers to large item sizes. Several tradeoffs
must be considered in choosing the data item size.

 The larger the data item size is, the lower the degree
of concurrency permitted.
• Example: entire disk block locked
 The smaller the data item size is, the more the
number of items in the database.
• Higher overhead
40
 Cont.…
 Multiple Granularity Level Locking:

 Locking Granularity is the size of data item allowed to lock.

 Multiple Granularities:

o It can be defined as hierarchically breaking up the database into

blocks which can be locked.
o The Multiple Granularity protocol enhances concurrency and
reduces lock overhead.
o It maintains the track of what to lock and how to lock.

o It makes easy to decide either to lock a data item or to unlock a

data item. This type of hierarchy can be graphically represented as
a tree.

41
 Cont.…

Figure: A granularity hierarchy for illustrating multiple granularity level locking

 The levels, starting from the coarsest (top) level are

1. database
2. area
3. file
42 4. record
 Cont.…
 Intention locks are needed
̶ Transaction indicates along the path from the root to the desired
node, what type of lock (shared or exclusive) it will require from one
of the node’s descendants
 Intention lock types
̶ Intention-shared (IS)
 Shared locks will be requested on a descendant node

̶ Intention-exclusive (IX)
 Exclusive locks will be requested

̶ Shared-intension-exclusive (SIX)
 Current node is locked in shared mode but one or more exclusive locks
will be requested on a descendant node

43
 Cont.…
Figure Lock compatibility matrix for multiple
granularity locking.

The multiple granularity locking (MGL) protocol consists of the following rules:
1. The lock compatibility (based on above Figure) must be adhered to.
2. The root of the tree must be locked first, in any mode.
3. A node N can be locked by a transaction T in S or IS mode only if the parent node N is already locked by
transaction T in either IS or IX mode.
4. A node N can be locked by a transaction T in X, IX, or SIX mode only if the parent of node N is already
locked by transaction T in either IX or SIX mode.
5. A transaction T can lock a node only if it has not unlocked any node (to enforce the 2PL protocol).
6. A transaction T can unlock a node, N, only if none of the children of node N are currently locked by T.

44
 Using Locks for Concurrency Control in Indexes
 By locking the data item, a transaction only prevents other
transactions from updating information about what tuples are in the
relation. Locking is still required on tuples.

 A transaction that directly accesses a tuple can be granted a lock on

the tuples even when another transaction has an exclusive lock on
the data item corresponding to the relation itself.

 The major disadvantage of locking a data item corresponding

to the relation is the low degree of concurrency two transactions
that insert different tuples into a relation are prevented from
executing concurrently.

45
 Cont.…
 A better solution is using an index-locking technique that
avoids locking the whole index.
 We eliminate the phantom phenomenon by imposing a locking
protocol for indices. For simplicity we shall consider only B+-
tree indices.
 The index-locking protocol takes advantage of the
availability of indices on a relation, by turning instances of the
phantom phenomenon into conflicts on locks on index leaf
nodes.
 Locking an index leaf node prevents any update to the node,
even if the update did not actually conflict with the predicate.

46
 Cont.…
 Two-phase locking can also be applied to B-tree and B+-tree indexes,
where the nodes of an index correspond to disk pages. However,
holding locks on index pages until the shrinking phase of 2PL.
Approaches used in index locking:
 Conservative approach
̶ Lock the root node in exclusive mode and then access the
appropriate child node of the root
 Optimistic approach
̶ Request and hold shared locks on nodes leading to the leaf node,
with exclusive lock on the leaf

 B-link tree approach

̶ Sibling nodes on the same level are linked at every level
̶ Allows shared locks when requesting a page
̶ Requires lock be released before accessing the child node
47
 Cont.…
Other Concurrency Control Issues:
 Insertion
̶ When new data item is inserted, it cannot be accessed until
after operation is completed

 Deletion operation on the existing data item

̶ Write lock must be obtained before deletion

 Phantom problem
̶ Can occur when a new record being inserted satisfies a
condition that a set of records accessed by another
transaction must satisfy
̶ Record causing conflict not recognized by concurrency
control protocol
48
 Cont.…
 Interactive transactions
̶ User can input a value of a data item to a transaction T
based on some value written to the screen by transaction T′,
which may not have committed
̶ Solution approach: postpone output of transactions to the
screen until committed

 Latches
̶ Locks held for a short duration
̶ Do not follow usual concurrency control protocol

49
 Questions?

50