Concurrency Control Techniques

Database Concurrency Control

Purpose of Concurrency Control

Enforces isolation among conflicting transactions through mutual exclusion.
Preserves database consistency by ensuring consistency-preserving execution of transactions.
Resolves read-write and write-write conflicts.
Example: If transaction T1 conflicts with T2 over data item A, the concurrency control mechanism decides which transaction gets A and whether the other transaction waits or is rolled back.

Two-Phase Locking (2PL) Techniques

Locking: An operation that secures permission to read or write a data item for a transaction.
- Example: Lock(X) locks data item X on behalf of the requesting transaction.
Unlocking: An operation that removes read or write permissions from the data item.
- Example: Unlock(X) makes data item X available to other transactions.
Lock and Unlock operations are atomic.

Essential Components of 2PL

Two Lock Modes:
- Shared (Read): Allows multiple transactions to read X, but no exclusive (write) lock can be applied by other transactions.
- Exclusive (Write): Only one write lock can exist on X at a time; no shared locks allowed concurrently.
Conflict Matrix:
Write Read
Read N N
Write N Y
Lock Manager: Manages locks on data items.
Lock Table: Used by the lock manager to store information about transactions locking a data item, including the transaction ID, data item ID, lock mode, and a pointer to the next locked data item. Can be implemented using linked lists.
- Example Structure:
  - Transaction ID: T1
  - Data item ID: X1
  - Lock mode: Read
  - Ptr to next data item: Next
Well-Formed Transactions:
- Must lock a data item before reading or writing it.
- Must not lock an already locked data item.
- Must not attempt to unlock a free data item.

	Write	Read
Read	N	N
Write	N	Y

Lock Operation Code:

B: if LOCK(X) = 0 (*item is unlocked*) then
    LOCK(X) ← 1 (*lock the item*)
else
    begin
    wait (until lock(X) = 0 and the lock manager wakes up the transaction);
    goto B
    end;

Unlock Operation Code:

LOCK(X) ← 0 (*unlock the item*)
if any transactions are waiting then
    wake up one of the waiting transactions;

Read Operation Code:

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 Operation Code:

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;

Unlock Operation Code:

if LOCK(X) = “write-locked” then
    begin
    LOCK(X) ← “unlocked”;
    wakes up one of the transactions, if any
    end
else if 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”;
        wake up one of the transactions, if any
        end
    end;

Lock Conversion:
- Lock Upgrade: Converting an existing read lock to a write lock.
  - If transaction Ti has a read-lock (X) and no other transaction Tj has a read-lock (X) (where $i <br />\neq j$ ), then convert read-lock (X) to write-lock (X); otherwise, Ti waits until Tj unlocks X.
- Lock Downgrade: Converting an existing write lock to a read lock.
  - If transaction Ti has a write-lock (X) (and no other transaction has any lock on X), convert write-lock (X) to read-lock (X).

The 2PL Algorithm

Two Phases:
- Locking (Growing) Phase: Transactions acquire locks (read or write) on desired data items.
- Unlocking (Shrinking) Phase: Transactions release their locked data items.
Requirement: The locking and unlocking phases must be mutually exclusive; unlocking cannot begin during the locking phase, and locking cannot begin during the unlocking phase.

2PL Example

Example demonstrating serial execution:
T1 T2 Result
read_lock(Y) Initial values: X=20; Y=30
read_item(Y)
unlock(Y)
read_lock(X)
read_item(X) Result of serial execution…
unlock(X) T1 followed by T2
write_lock(Y)
write_item(Y) X=50, Y=80
Non-serializable due to Two-Phase Policy Violation:
T1 T2 Result
read_lock(Y)
read_item(Y) X=50; Y=50
unlock(Y) Nonserializable because it violated two-phase policy.
read_lock(X)
read_item(X)

T1	T2	Result
`read_lock(Y)`		Initial values: X=20; Y=30
`read_item(Y)`
`unlock(Y)`
	`read_lock(X)`
	`read_item(X)`	Result of serial execution…
	`unlock(X)`	T1 followed by T2
	`write_lock(Y)`
	`write_item(Y)`	X=50, Y=80

2PL and Deadlock

Transactions following 2PL can still be subject to deadlocks.
Example:
T’1 T’2
read_lock(Y) T1 and T2 follow two-phase policy
read_item(Y) …but are subject to deadlock.
read_lock(X)
read_item(X)
write_lock(X)
write_lock(Y) Unlock (Y)
Conservative 2PL: Prevents deadlock by locking all desired data items before the transaction begins execution.
Basic 2PL: Locks data items incrementally, which may cause deadlock but deals with the possibility of deadlock if it arises.
Strict 2PL: A stricter version of Basic 2PL where unlocking is performed only after the transaction terminates (commits or aborts and rolls back). This is the most commonly used 2PL algorithm.

T’1	T’2
`read_lock(Y)`		T1 and T2 follow two-phase policy
`read_item(Y)`		…but are subject to deadlock.
	`read_lock(X)`
	`read_item(X)`
`write_lock(X)`
	`write_lock(Y)`	Unlock (Y)

Dealing with Deadlock and Starvation

Deadlock Prevention:
- Transactions lock all required data items before execution begins.
- Prevents waiting for data items, thus avoiding deadlock.
- Used by conservative two-phase locking.
Deadlock Detection and Resolution:
- Deadlocks are allowed to occur.
- The scheduler maintains a wait-for graph to detect cycles.
- If a cycle exists, one transaction in the cycle is selected as a victim and rolled back.
- The wait-for graph is created using the lock table.
- Cycles like Ti waits for Tj waits for Tk waits for Ti or Tj indicate a deadlock.
Deadlock Avoidance:
- Variations of 2PL that prevent cycles from completing.
- If blocking a transaction is likely to create a cycle, the transaction is rolled back.
- Wound-Wait and Wait-Die algorithms use timestamps to avoid deadlocks.
Starvation:
- Occurs when a transaction consistently waits or is restarted, never getting a chance to proceed.
- May occur in deadlock resolution if the same transaction is repeatedly selected as the victim.
- Inherent in priority-based scheduling mechanisms.
- In Wound-Wait scheme, a younger transaction may always be wounded (aborted) by a long-running older transaction, creating starvation.

Timestamp-Based Concurrency Control

Timestamp: A monotonically increasing variable (integer) indicating the age of an operation or transaction.
- Larger timestamp values indicate more recent events or operations.
Timestamp-based algorithms use timestamps to serialize the execution of concurrent transactions.
Basic Timestamp Ordering:
- For a write_item(X) operation by transaction T:
  - If read_TS(X) > TS(T) or write_TS(X) > TS(T), abort and roll back T because a younger transaction has already read/written the data item.
  - Otherwise, execute write_item(X) and set write_TS(X) to TS(T).
- For a read_item(X) operation by transaction T:
  - If write_TS(X) > TS(T), abort and roll back T because a younger transaction has already written to the data item.
  - Otherwise, execute read_item(X) and set read_TS(X) to the larger of TS(T) and the current read_TS(X).
Strict Timestamp Ordering:
- For a write_item(X) operation by transaction T: If TS(T) > read_TS(X), delay T until the transaction T’ that wrote or read X has terminated.
- For a read_item(X) operation by transaction T: If TS(T) > write_TS(X), delay T until the transaction T’ that wrote or read X has terminated.
Thomas’s Write Rule:
- If read_TS(X) > TS(T), abort and roll back T.
- If write_TS(X) > TS(T), ignore the write operation and continue execution (most recent writes count).
- Otherwise, execute write_item(X) and set write_TS(X) to TS(T).

Multiversion Concurrency Control

Maintains multiple versions of a data item and allocates the correct version to a read operation.
Read operations are never rejected.
Side Effect: Requires significantly more storage (RAM and disk).
Garbage collection is needed to limit version growth.
Multiversion Technique Based on Timestamp Ordering:
- Versions of a data item X are denoted as X1, X2, …, Xn with associated read_TS(Xi) and write_TS(Xi).
  - read_TS(Xi): The largest timestamp of transactions that have successfully read version Xi.
  - write_TS(Xi): The timestamp of the transaction that wrote the value of version Xi.
- A new version of Xi is created only by a write operation.
Serializability Rules:
- If transaction T issues write_item(X):
  - Find version i of X with the highest write_TS(Xi) such that write_TS(Xi)  TS(T). If read_TS(Xi) > TS(T), abort and roll back T.
  - Otherwise, create a new version Xi and set read_TS(X) = write_TS(Xj) = TS(T). Note: there appears to be a typo here with read_TS(X) = write_TS(Xj) = TS(T); write_TS(Xi) = TS(T) seems more accurate
- If transaction T issues read_item(X): Find the version i of X that has the highest write_TS(Xi) such that write_TS(Xi)  TS(T), return the value of Xi to T, and set read_TS(Xi) to the largest of TS(T) and the current read_TS(Xi). This guarantees reads are never rejected.

Multiversion Two-Phase Locking Using Certify Locks

Concept: Allows a transaction T’ to read a data item X while it is write-locked by a conflicting transaction T.
Maintains two versions of each data item X, where one version has always been written by a committed transaction.
Write operations always create a new version of X.
Steps:
1. X is the committed version.
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 now X.
Compatibility tables for Read/Write locking and Read/Write/Certify locking schemes are used.
Improves concurrency by processing read and write operations from conflicting transactions concurrently, but can delay transaction commit due to obtaining certify locks. It avoids cascading aborts, but conflicting transactions may deadlock.

Validation (Optimistic) Concurrency Control

Serializability is checked only at commit time.
Transactions are aborted if non-serializable schedules are detected.
Three Phases:
1. Read Phase: Transactions read values of committed data items but apply updates only to local copies (versions) in the database cache.
2. Validation Phase: Serializability is checked before writing updates to the database.
  - For transaction Ti, it checks that for each transaction Tj that is either committed or is in its validation phase, one of the following conditions holds:
    1. Tj completes its write phase before Ti starts its read phase.
    2. Ti starts its write phase after Tj completes its write phase, and the readset of Ti has no items in common with the writeset of Tj.
    3. Both the readset and writeset of Ti have no items in common with the write_set of Tj, and Tj completes its read phase.
  - During validation of Ti, condition (1) is checked first, then (2), and then (3). If none of these conditions holds, validation fails, and Ti is aborted.
3. Write Phase: If validation is successful, transactions’ updates are applied to the database; otherwise, transactions are restarted.

Granularity of Data Items and Multiple Granularity Locking

Granularity: The size of the lockable data unit (e.g., entire database, file, record, or attribute).
Data item granularity significantly affects concurrency control performance.
Coarse granularity results in low concurrency, while fine granularity results in high concurrency.
Examples of data item granularity:
1. A field of a database record (an attribute of a tuple).
2. A database record (a tuple of a relation).
3. A disk block.
4. An entire file.
5. The entire database.
A hierarchy of granularity exists from coarse (database) to fine (record).
Additional locking modes are defined to manage such hierarchies:
- Intention-Shared (IS): Indicates that a shared lock(s) will be requested on some descendant nodes(s).
- Intention-Exclusive (IX): Indicates that an exclusive lock(s) will be requested on some descendant node(s).
- Shared-Intention-Exclusive (SIX): Indicates that the current node is locked in shared mode, but an exclusive lock(s) will be requested on some descendant nodes(s).
A compatibility matrix defines how these locks interact.
IS IX S SIX X
IS yes yes yes yes no
IX yes yes no no no
S yes no no no no
SIX yes no no no no
X no no no no no
Rules for producing serializable schedules:
1. Lock compatibility 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 T in S or IX mode only if the parent node is already locked by T in either IS or IX mode.
4. A node, N, can be locked by T in X, IX, or SIX mode only if the parent of N is already locked by T in either IX or SIX mode.
5. T can lock a node only if it has not unlocked any node (to enforce 2PL policy).
6. T can unlock a node, N, only if none of the children of N are currently locked by T.

T1	T2	Result
`read_lock(Y)`
`read_item(Y)`		X=50; Y=50
`unlock(Y)`		Nonserializable because it violated two-phase policy.
	`read_lock(X)`
	`read_item(X)`

	IS	IX	S	SIX	X
IS	yes	yes	yes	yes	no
IX	yes	yes	no	no	no
S	yes	no	no	no	no
SIX	yes	no	no	no	no
X	no	no	no	no	no

	IS	IX	S	SIX	X
IS	yes	yes	yes	yes	no
IX	yes	yes	no	no	no
S	yes	no	no	no	no
SIX	yes	no	no	no	no
X	no	no	no	no	no

	IS	IX	S	SIX	X
IS	yes	yes	yes	yes	no
IX	yes	yes	no	no	no
S	yes	no	no	no	no
SIX	yes	no	no	no	no
X	no	no	no	no	no