MODULE 5

Concurrency Control in Databases: Two-phase locking techniques

for Concurrency control, Concurrency control based on Timestamp
ordering, Multiversion Concurrency control techniques, Validation
Concurrency control techniques, Granularity of Data items and
Multiple Granularity Locking.

NOSQL Databases and Big Data Storage Systems: Introduction to

NOSQL Systems, The CAP Theorem, Document-Based NOSQL
Systems and MongoDB, NOSQL Key-Value Stores, Column-Based or
Wide Column NOSQL Systems, NOSQL Graph Databases and Neo4j
Two-Phase Locking Techniques for Concurrency Control
Introduction: Some of the main techniques used to control
concurrent execution of transactions are based on the concept of
locking data items. A lock is a variable associated with a data item
that describes the status of the item with respect to possible
operations that can be applied to it. Generally, there is one lock for
each data item in the database. Locks are used as a means of
synchronizing the access by concurrent transactions to the database
items.

Types of Locks and System Lock Tables

1. Binary Locks.
2. Shared/Exclusive (or Read/Write) Locks
1. Binary Locks : A binary lock can have two states or values: locked
and unlocked
(or 1 and 0, for simplicity). A distinct lock is associated with each
database item X. If the value of the lock on X is 1, item X cannot be
accessed by a database operation that requests the item. If the value of
the lock on X is 0, the item can be accessed when requested, and the
lock value is changed to 1.

Two operations, lock_item and unlock_item, are used with binary

locking. A transaction requests access to an item X by first issuing a
lock_item(X) operation. If LOCK(X) = 1, the transaction is forced to wait.
If LOCK(X) = 0, it is set to 1 (the transaction locks the item) and the
transaction is allowed to access item X. When the transaction is
through using the item, it issues an unlock_item(X) operation.

Note: Binary lock enforces mutual exclusion on the data item.

Figure Lock and unlock operations for binary locks.
Implemention:
Each lock can be a record with three fields: <Data_item_name, LOCK,
Locking_transaction> Items not in the lock table are considered to be
unlocked.
Every transaction must obey the following rules:
1. A transaction T must issue the operation lock_item(X) before any
read_item(X) or write_item(X) operations are performed in T.
2. A transaction T must issue the operation unlock_item(X) after all
read_item(X) and write_item(X) operations are completed in T.
3. A transaction T will not issue a lock_item(X) operation if it already
holds the lock on item X
4. A transaction T will not issue an unlock_item(X) operation unless it
already holds the lock on item X.
These rules can be enforced by the lock manager module of the DBMS.
Between the lock_item(X) and unlock_item(X) operations in transaction
T, T is said to hold the lock on item X. At most one transaction can hold
the lock on a particular item. Thus no two transactions can access the
same item concurrently.
Shared/Exclusive (or Read/Write) Locks.
Binary locking scheme is too restrictive for database items because at
most one transaction can hold a lock on a given item. We should allow
several transactions to access the same item X if they all access X for
reading purposes only.
Different type of lock, called a multiple-mode lock, is used. In this
scheme—called shared/exclusive or read/write locks—there are
three locking operations: read_lock(X), write_lock(X), and unlock(X). A
lock associated with an item X, LOCK(X), now has three possible states:
read-locked, write-locked, or unlocked. A read-locked item is also
called share-locked because other transactions are allowed to read
the item, whereas a write-locked item is called exclusive-locked
because a single transaction exclusively holds the lock on the item.
Implemention:
Each record in the lock table will have four fields: <Data_item_name,
LOCK, No_of_reads, Locking_transaction(s)>. The system needs to
maintain lock records only for locked items in the lock table. The value
(state) of LOCK is either readlocked or write-locked,

Each of the three locking operations should be considered indivisible;

no interleaving should be allowed once one of the operations is
started until either the operation terminates by granting the lock or
the transaction is placed in a waiting queue for the item.

The three operations read_lock(X), write_lock(X), and unlock(X) are

described in BELOW Figure.
 Figure
Locking and unlocking operations for two mode
(read/write, or shared/exclusive) locks.

read_lock(X):
B: if LOCK(X) = “unlocked”
then begin LOCK(X) ← “read-locked”;
no_of_reads(X) ← 1
end
else if LOCK(X) = “read-locked”
then no_of_reads(X) ← no_of_reads(X) + 1
else begin
wait (until LOCK(X) = “unlocked”
and the lock manager wakes up the transaction);
go to B
end;
write_lock(X):
B: if LOCK(X) = “unlocked”
then LOCK(X) ← “write-locked”
else begin
wait (until LOCK(X) = “unlocked”
and the lock manager wakes up the
transaction);
go to B
end;
unlock (X):
if LOCK(X) = “write-locked”
then begin LOCK(X) ← “unlocked”;
wakeup one of the waiting transactions, if any
end
else it LOCK(X) = “read-locked”
then begin
no_of_reads(X) ← no_of_reads(X) −1;
if no_of_reads(X) = 0
then begin LOCK(X) = “unlocked”;
wakeup one of the waiting transactions, if any
end
end;
When we use the shared/exclusive locking scheme, the system must enforce
the following rules:
1. A transaction T must issue the operation read_lock(X) or write_lock(X)
before any read_item(X) operation is performed in T.
2. A transaction T must issue the operation write_lock(X) before any
write_item(X) operation is performed in T.
3. A transaction T must issue the operation unlock(X) after all read_item(X)
and write_item(X) operations are completed in T.
4. A transaction T will not issue a read_lock(X) operation if it already holds
a read (shared) lock or a write (exclusive) lock on item X. This rule may be
relaxed for downgrading of locks, as we discuss shortly.
5. A transaction T will not issue a write_lock(X) operation if it already
holds a read (shared) lock or write (exclusive) lock on item X. This rule may
also be relaxed for upgrading of locks, as we discuss shortly.
6. A transaction T will not issue an unlock(X) operation unless it already
holds a read (shared) lock or a write (exclusive) lock on item X.
Conversion (Upgrading, Downgrading) of Locks. It is desirable to
relax conditions 4 and 5 in the preceding list in order to allow lock
conversion; that is, a transaction that already holds a lock on item
X is allowed under certain conditions to convert the lock from one
locked state to another.
For example, it is possible for a transaction T to issue a
read_lock(X) and then later to upgrade the lock by issuing a
write_lock(X) operation. If T is the only transaction holding a read
lock on X at the time it issues the write_lock(X) operation, the lock
can be upgraded; otherwise, the transaction must wait. It is also
possible for a transaction T to issue a write_lock(X) and then later
to downgrade the lock by issuing a read_lock(X) operation.
Guaranteeing Serializability by Two-Phase Locking
A transaction is said to follow the two-phase locking protocol if all
locking operations (read_lock, write_lock) precede the first unlock
operation in the transaction. Such a transaction can be divided into
two phases: an expanding or growing (first) phase, during which new
locks on items can be acquired but none can be released; and a
shrinking (second) phase, during which existing locks can be released
but no new locks can be acquired. If lock conversion is allowed, then
upgrading of locks (from read-locked to write-locked) must be done
during the expanding phase, and downgrading of locks (from write-
locked to read-locked) must be done in the shrinking phase.
Transactions T1 and T2 do not follow the two-phase locking protocol
because the write_lock(X) operation follows the unlock(Y) operation in
T1, and similarly the write_lock(Y) operation follows the unlock(X)
operation in T2. If we enforce two-phase locking, the transactions can
be rewritten as T1′ and T2′.
Transactions T1′ and T2′,
which are the same as T1
and T2 in above Figure but
follow the two-phase
locking protocol. Note that
they can produce a
deadlock.
Figure A nonserializable
schedule S that uses
locks.

Result of schedule
S: X=50, Y=50
(nonserializable)
The locking protocol, by enforcing two-phase locking rules enforces
serializability.
VARIATIONS:
Basic, Conservative, Strict, and Rigorous Two-Phase Locking.
The technique described is known as basic 2PL. A variation known as
conservative 2PL (or static 2PL) requires a transaction to lock all the items it
accesses before the transaction begins execution, by predeclaring its read-set
and write-set. Conservative 2PL is a deadlock-free protocol. The most popular
variation of 2PL is strict 2PL, which guarantees strict schedules. In this
variation, a transaction T does not release any of its exclusive (write) locks
until after it commits or aborts. Hence, no other transaction can read or write
an item that is written by T unless T has committed, leading to a strict
schedule for recoverability. Strict 2PL is not deadlock-free. A more restrictive
variation of strict 2PL is rigorous 2PL, which also guarantees strict schedules.
In this variation, a transaction T does not release any of its locks (exclusive or
shared) until after it commits or aborts, and so it is easier to implement than
strict 2PL.
Dealing with Deadlock and Starvation
Deadlock occurs when each transaction T in a set of two or more
transactions is waiting for some item that is locked by some other
transaction T′ in the set.

(a) (b)
Figure Illustrating the deadlock problem. (a) A partial schedule of T1′
and T2′ that is in a state of deadlock. (b) A wait-for graph for the partial
schedule in (a).
Deadlock Prevention Protocols.
Conservative two-phase locking, requires that every transaction lock all
the items it needs in advance (which is generally not a practical
assumption)—if any of the items cannot be obtained, none of the items
are locked. Rather, the transaction waits and then tries again to lock all
the items it needs.
Obviously, this solution further limits concurrency.
A second protocol, which also limits concurrency, involves ordering all the
items in the database and making sure that a transaction that needs
several items will lock them according to that order.
Various techniques in use those uses concept of transaction timestamp
TS(T′), which is a unique identifier assigned to each transaction & are
typically based on the order in which transactions arestarted; hence, if
transaction T1 starts before transaction T2, then TS(T1) < TS(T2).
Two schemes that prevent deadlock are called wait-die and wound-
wait. Suppose that transaction Ti tries to lock an item X but is not able
to because X is locked by some other transaction Tj with a conflicting
lock. The rules followed by these schemes are:
■ 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 with the same timestamp.
■ 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.
In 1st, an older transaction is allowed to wait for a younger transaction,
whereas a younger transaction requesting an item held by an older
transaction is aborted and restarted.
The II approach does the opposite: A younger transaction is allowed to
wait for an older one, whereas an older transaction requesting an item
held by a younger transaction preempts the younger transaction by
aborting it. Two techniques are deadlock-free
Another group of protocols; No waiting (NW) and Cautious waiting (CW)
algorithms
No waiting (NW): If a transaction is unable to obtain a lock, it is
immediately aborted and then restarted after a certain time delay
without checking whether a deadlock will actually occur or not. In this
case, no transaction ever waits, so no deadlock will occur. However, this
scheme can cause transactions to abort and restart needlessly.
Cautious waiting (CW): The cautious waiting algorithm was proposed
to try to reduce the number of needless aborts/restarts. Suppose that
transaction Ti tries to lock an item X but is not able to do so because X is
locked by some other transaction Tj with a conflicting lock. The cautious
waiting rule is as follows:
■ Cautious waiting. If Tj is not blocked (not waiting for some other
locked item), then Ti is blocked and allowed to wait; otherwise abort Ti.
Deadlock Detection. An alternative approach to dealing with deadlock
is deadlock detection, where the system checks if a state of deadlock
actually exists.
If transactions are long and each transaction uses many items, or if the
transaction load is heavy, it may be advantageous to use a deadlock
prevention scheme and if transactions are short and each transaction
load is light there is no interference.
A simple way to detect a state of deadlock is for the system to construct
and maintain a wait-for graph. One node is created in the wait-for
graph for each transaction that is currently executing. Whenever a
transaction Ti is waiting to lock an item X that is currently locked by a
transaction Tj, a directed edge (Ti → Tj) is created in the wait-for graph.
When Tj releases the lock(s) on the items that Ti was waiting for, the
directed edge is dropped from the wait-for graph. We have a state of
deadlock if and only if the wait-for graph has a cycle.
Victim selection : Younger transactions.
Another simple scheme to deal with deadlock is the use of timeouts.
This method is practical because of its low overhead and simplicity. In
this method, if a transaction waits for a period longer than a system-
defined timeout period, the system assumes that the transaction may be
deadlocked and aborts it—regardless of whether a deadlock actually
exists.
Starvation.
-> first-come-first-served queue
-> Transactions to have priority over others but increases the
priority of a transaction the longer it waits
-> wait-die and wound-wait schemes