MATRUSRI ENGINEERING COLLEGE�DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

SUBJECT NAME: DataBase Management Systems

FACULTY NAME: K Sunil Manohar Reddy

Insert Your Photo here🡪

MATRUSRI

ENGINEERING COLLEGE

INTRODUCTION: ��THIS UNIT DEALS WITH CONCURRENCY CONTROL AND RECOVERY SYSTEM

UNIT-V

OUTCOMES:

​

Upon completion of this unit, student will be able to:

• To familiarize theory of serializability and Understand the working of concurrency control and recovery mechanisms

MATRUSRI

ENGINEERING COLLEGE

CONTENTS:�CONCURRENCY CONTROL: LOCK BASED PROTOCOLS, TIMESTAMP BASED PROTOCOLS, VALIDATION BASED PROTOCOLS, MULTIPLE GRANULARITY, MULTI VERSION SCHEMES, DEADLOCK HANDLING, INSERT AND DELETE OPERATIONS, WEAK LEVELS OF CONSISTENCY, CONCURRENCY OF INDEX STRUCTURES.���

OUTCOMES:

Upon completion of this module, student will be able to:

• To familiarize theory of Concurrency Control

MODULE-I

MATRUSRI

ENGINEERING COLLEGE

Lock-Based Protocols

A lock is a mechanism to control concurrent access to a data item

Data items can be locked in two modes :

1. exclusive (X) mode. Data item can be both read as well as

written. X-lock is requested using lock-X instruction.

2. 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.

Lock-compatibility matrix

​

​

MATRUSRI

ENGINEERING COLLEGE

Lock-Based Protocols (Cont.)

• A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions
• Any number of transactions can hold shared locks on an item,
• But if any transaction holds an exclusive on the item no other transaction may hold any lock on the item
• Example of a transaction performing locking:

T₂: lock-S(A);

read (A);

unlock(A);

​

lock-S(B);

read (B);

unlock(B);

display(A+B)

• Locking as above is not sufficient to guarantee serializability

​

MATRUSRI

ENGINEERING COLLEGE

Timestamp-Based Protocols

Each transaction T_i is issued a timestamp TS(T_i) when it enters the system.

Each transaction has a unique timestamp

Newer transactions have timestamps strictly greater than earlier ones

Timestamp could be based on a logical counter

Real time may not be unique

Can use (wall-clock time, logical counter) to ensure

Timestamp-based protocols manage concurrent execution such that � time-stamp order = serializability order

Several alternative protocols based on timestamps

MATRUSRI

ENGINEERING COLLEGE

Timestamp-Based Protocols (Cont.)

Suppose that transaction T_i issues write(Q).

​

1. If TS(T_i) < R-timestamp(Q), then the value of Q that T_i is producing

was needed previously, and the system assumed that that value

would never be produced.

• Hence, the write operation is rejected, and T_i is rolled back.

2. If TS(T_i) < W-timestamp(Q), then T_i is attempting to write an

obsolete value of Q.

• Hence, this write operation is rejected, and T_i is rolled back.

3. Otherwise, the write operation is executed, and W-timestamp(Q) is

set to TS(T_i).

MATRUSRI

ENGINEERING COLLEGE

Timestamp-Ordering Protocol

• The timestamp ordering (TSO) protocol
• Maintains for each data Q two timestamp values:
• W-timestamp(Q) is the largest time-stamp of any transaction that executed write(Q) successfully.
• R-timestamp(Q) is the largest time-stamp of any transaction that executed read(Q) successfully.
• Imposes rules on read and write operations to ensure that
• Any conflicting operations are executed in timestamp order
• Out of order operations cause transaction rollback

Suppose a transaction T_i issues a read(Q)

​

1. If TS(T_i) ≤ W-timestamp(Q), then T_i needs to read a value of Q that

was already overwritten.

Hence, the read operation is rejected, and T_i is rolled back.

​

2. If TS(T_i) ≥ W-timestamp(Q), then the read operation is executed, and

R-timestamp(Q) is set to

max(R-timestamp(Q), TS(T_i)).

​

MATRUSRI

ENGINEERING COLLEGE

Multiversion Schemes

• Multiversion schemes keep old versions of data item to increase concurrency.
• Multiversion Timestamp Ordering
• Multiversion Two-Phase Locking
• Each successful write results in the creation of a new version of the data item written.
• Use timestamps to label versions.
• When a read(Q) operation is issued, select an appropriate version of Q based on the timestamp of the transaction, and return the value of the selected version.
• reads never have to wait as an appropriate version is returned immediately.

MATRUSRI

ENGINEERING COLLEGE

MVCC: Implementation Issues

• Creation of multiple versions increases storage overhead
• Extra tuples
• Extra space in each tuple for storing version information
• Versions can, however, be garbage collected
• E.g. if Q has two versions Q5 and Q9, and the oldest active transaction has timestamp > 9, than Q5 will never be required again

​

MATRUSRI

ENGINEERING COLLEGE

Validation-Based Protocols

Execution of transaction T_i is done in three phases.

1. Read and execution phase: Transaction T_i writes only to temporary local variables

2. Validation phase: Transaction T_i performs a ``validation test'' to determine if local variables can be written without violating serializability.

3. Write phase: If T_i is validated, the updates are applied to the database; otherwise, T_i is rolled back.

​

The three phases of concurrently executing transactions can be interleaved, but each transaction must go through the three phases in that order.

Assume for simplicity that the validation and write phase occur together, atomically and serially

I.e., only one transaction executes validation/write at a time.

​

Also called as optimistic concurrency control since transaction executes fully in the hope that all will go well during validation

​

• Validation is based on two timestamps:
• start time
• validation time

​

MATRUSRI

ENGINEERING COLLEGE

The Two-Phase Locking Protocol

A protocol which ensures conflict-serializable schedules.

Phase 1: Growing Phase

Transaction may obtain locks

Transaction may not release locks

Phase 2: Shrinking Phase

Transaction may release locks

Transaction may not obtain locks

• The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points (i.e., the point where a transaction acquired its final lock).
• Two-phase locking does not ensure freedom from deadlocks
• Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading roll-back
• Strict two-phase locking: a transaction must hold all its exclusive locks till it commits/aborts.
• Ensures recoverability and avoids cascading roll-backs
• Rigorous two-phase locking: a transaction must hold all locks till commit/abort.
• Transactions can be serialized in the order in which they commit.
• Most databases implement rigorous two-phase locking, but refer to it as simply two-phase locking

​

MATRUSRI

ENGINEERING COLLEGE

The Two-Phase Locking Protocol (Cont.)

• Two-phase locking is not a necessary

condition for serializability

• There are conflict serializable

schedules that cannot be obtained

if the two-phase locking protocol

is used.

• In the absence of extra information

(e.g., ordering of access to data), two-phase

locking is necessary for conflict

serializability in the following sense:

• Given a transaction T_i that does

not follow two-phase locking, we

can find a transaction T_j that uses

two-phase locking, and a schedule

for T_i and T_j that is not conflict

serializable.

MATRUSRI

ENGINEERING COLLEGE

Locking Protocols

• Given a locking protocol (such as 2PL)
• A schedule S is legal under a locking protocol if it can be generated by a set of transactions that follow the protocol
• A protocol ensures serializability if all legal schedules under that protocol are serializable
• Lock Conversions:
• Two-phase locking protocol with lock conversions:
• – Growing 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)
• – Shrinking Phase:
• can release a lock-S
• can release a lock-X
• can convert a lock-X to a lock-S (downgrade)
• This protocol ensures serializability

​

MATRUSRI

ENGINEERING COLLEGE

Implementation of Locking

• A lock manager can be implemented as a separate process
• Transactions can send lock and unlock requests as messages
• The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back, in case of a deadlock)
• The requesting transaction waits until its request is answered
• The lock manager maintains an in-memory data-structure called a lock table to record granted locks and pending requests
• Dark rectangles indicate granted locks, light colored ones indicate waiting requests
• Lock table also records the type of lock granted or requested
• New request is added to the end of the queue of requests for the data item, and granted if it is compatible with all earlier locks
• Unlock requests result in the request being deleted, and later requests are checked to see if they can now be granted
• If transaction aborts, all waiting or granted requests of the transaction are deleted
• lock manager may keep a list of locks held by each transaction, to implement this efficiently

​

​

​

MATRUSRI

ENGINEERING COLLEGE

Graph-Based Protocols

Graph-based protocols are an alternative to two-phase locking

Impose a partial ordering → on the set D = {d₁, d₂ ,..., d_h} of all data items.

If d_i → d_j then any transaction accessing both d_i and d_j must access d_i before accessing d_j.

Implies that the set D may now be viewed as a directed acyclic graph, called a database graph.

The tree-protocol is a simple kind of graph protocol.

Tree Protocol :

Only exclusive locks are allowed.

The first lock by T_i may be on any data item. Subsequently, a data Q can be locked by T_i only if the parent of Q is currently locked by T_i.

Data items may be unlocked at any time.

A data item that has been locked and unlocked by T_i cannot subsequently be relocked by T_i

MATRUSRI

ENGINEERING COLLEGE

Graph-Based Protocols (Cont.)

• The tree protocol ensures conflict serializability as well as freedom from deadlock.
• Unlocking may occur earlier in the tree-locking protocol than in the two-phase locking protocol.
• Shorter waiting times, and increase in concurrency
• Protocol is deadlock-free, no rollbacks are required
• Drawbacks
• Protocol does not guarantee recoverability or cascade freedom
• Need to introduce commit dependencies to ensure recoverability
• Transactions may have to lock data items that they do not access.
• increased locking overhead, and additional waiting time
• potential decrease in concurrency
• Schedules not possible under two-phase locking are possible under the tree protocol, and vice versa.

MATRUSRI

ENGINEERING COLLEGE

Multiple Granularity

Allow data items to be of various sizes and define a hierarchy of data granularities, where the small granularities are nested within larger ones

Can be represented graphically as a tree (but don't confuse with tree-locking protocol)

When a transaction locks a node in the tree explicitly, it implicitly locks all the node's descendants in the same mode.

Granularity of locking (level in tree where locking is done):

Fine granularity (lower in tree): high concurrency, high locking overhead

Coarse granularity (higher in tree): low locking overhead, low concurrency

​

MATRUSRI

ENGINEERING COLLEGE

Intention Lock Modes

• In addition to S and X lock modes, there are three additional lock modes with multiple granularity:
• intention-shared (IS): indicates explicit locking at a lower level of the tree but only with shared locks.
• intention-exclusive (IX): indicates explicit locking at a lower level with exclusive or shared locks
• shared and intention-exclusive (SIX): sub tree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks.
• Intention locks allow a higher level node to be locked in S or X mode without having to check all descendent nodes.

​

MATRUSRI

ENGINEERING COLLEGE

Intention Lock Modes

• These locks are applied using the following compatibility matrix:

MATRUSRI

ENGINEERING COLLEGE

Multiple Granularity Locking Scheme

Transaction T_i can lock a node Q, using the following rules:

• The lock compatibility matrix must be observed.

​

2. The root of the tree must be locked first, and may be locked in any

mode.

​

3. A node Q can be locked by T_i in S or IS mode only if the parent of Q is

currently locked by T_i in either IX or IS mode.

​

4. A node Q can be locked by T_i in X, SIX, or IX mode only if the parent

of Q is currently locked by T_i in either IX or SIX mode.

​

5. T_i can lock a node only if it has not previously unlocked any node (that

is, T_i is two-phase).

​

6. T_i can unlock a node Q only if none of the children of Q are currently

locked by T_i.

Observe that locks are acquired in root-to-leaf order, whereas they are released in leaf-to-root order.

Lock granularity escalation: in case there are too many locks at a particular level, switch to higher granularity S or X lock

MATRUSRI

ENGINEERING COLLEGE

Deadlock

• Consider the partial schedule

​

​

​

​

​

​

​

​

​

​

Neither T₃ nor T₄ can make progress — executing lock-S(B) causes T₄ to wait for T₃ to release its lock on B, while executing lock-X(A) causes T₃ to wait for T₄ to release its lock on A.

​

Such a situation is called a deadlock.

​

To handle a deadlock one of T₃ or T₄ must be rolled back and its locks released.

​

MATRUSRI

ENGINEERING COLLEGE

Deadlock (Cont.)

• The potential for deadlock exists in most locking protocols.
• Starvation is also possible if concurrency control manager is badly designed. For example:
• A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S-lock on the same item.
• The same transaction is repeatedly rolled back due to deadlocks.
• Starvation is the situation in which a transaction cannot proceed for an indefinite period of time while other transactions in the system continue normally.
• Starvation occurs when a particular transaction consistently waits or restarted and never gets a chance to proceed further.
• Concurrency control manager can be designed to prevent starvation.

MATRUSRI

ENGINEERING COLLEGE

Deadlock Handling

• System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set.

​

​

​

​

​

​

​

​

​

Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some prevention strategies:

• Require that each transaction locks all its data items before it begins execution (pre-declaration).
• Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order (graph-based protocol).

​

MATRUSRI

ENGINEERING COLLEGE

Deadlock Detection

• Wait-for graph
• Vertices: transactions
• Edge from T_i →T_j. : if T_i is waiting for a lock held in conflicting mode byT_j
• The system is in a deadlock state if and only if the wait-for graph has a cycle.
• Invoke a deadlock-detection algorithm periodically to look for cycles.

MATRUSRI

ENGINEERING COLLEGE

Deadlock Recovery

• When deadlock is detected :
• Some transaction will have to rolled back (made a victim) to break deadlock cycle.
• Select that transaction as victim that will incur minimum cost
• Rollback -- determine how far to roll back transaction
• Total rollback: Abort the transaction and then restart it.
• Partial rollback: Roll back victim transaction only as far as necessary to release locks that another transaction in cycle is waiting for
• Oldest transaction in the deadlock set is never chosen as victim

MATRUSRI

ENGINEERING COLLEGE

Insert/Delete Operations and Predicate Reads

• Locking rules for insert/delete operations
• An exclusive lock must be obtained on an item before it is deleted
• A transaction that inserts a new tuple into the database I automatically given an X-mode lock on the tuple
• Ensures that
• reads/writes conflict with deletes
• Inserted tuple is not accessible by other transactions until the transaction that inserts the tuple commits

MATRUSRI

ENGINEERING COLLEGE

Weak Levels of Consistency in SQL

• SQL allows non-serializable executions
• Serializable: is the default
• Repeatable read: allows only committed records to be read, and repeating a read should return the same value (so read locks should be retained)
• However, the phantom phenomenon need not be prevented
• T1 may see some records inserted by T2, but may not see others inserted by T2
• Read committed: same as degree two consistency, but most systems implement it as cursor-stability
• Read uncommitted: allows even uncommitted data to be read
• In many database systems, read committed is the default consistency level
• has to be explicitly changed to serializable when required
• set isolation level serializable

MATRUSRI

ENGINEERING COLLEGE

Concurrency in Index Structures

• Indices are unlike other database items in that their only job is to help in accessing data.
• Index-structures are typically accessed very often, much more than other database items.
• Treating index-structures like other database items, e.g. by 2-phase locking of index nodes can lead to low concurrency.
• There are several index concurrency protocols where locks on internal nodes are released early, and not in a two-phase fashion.
• It is acceptable to have non serializable concurrent access to an index as long as the accuracy of the index is maintained.
• In particular, the exact values read in an internal node of a �B⁺-tree are irrelevant so long as we land up in the correct leaf node.

MATRUSRI

ENGINEERING COLLEGE