Unit 9: Concurrency Control

Introduction to Concurrency Control

In a multi-user database system, multiple transactions can execute concurrently. Concurrency Control is the process of managing simultaneous operations to ensure data integrity and consistency while maximizing throughput and response time.

Definition: Concurrency Control ensures that concurrent execution of transactions produces the same results as if they were executed serially (one after another), known as serializability.

The primary goals of concurrency control are:

• Serializability: Ensure that the concurrent execution of transactions is equivalent to some serial execution.
• Isolation: Prevent transactions from interfering with each other's operations.
• Consistency: Maintain the database in a consistent state before and after transaction execution.
• Durability: Ensure that committed transactions persist even in the event of system failures.

Lock-Based Protocols

Lock-based protocols are fundamental concurrency control mechanisms where transactions acquire locks on data items before accessing them. Locks prevent other transactions from accessing the same data item in a conflicting mode until the lock is released.

Types of Locks:

• Shared Lock (S-lock or Read Lock): Permits other transactions to acquire shared locks on the same item, but not exclusive locks. Used for read operations.
• Exclusive Lock (X-lock or Write Lock): Prevents any other transaction from acquiring any type of lock (shared or exclusive) on the same item. Used for write operations.

A lock manager is a system component responsible for granting and releasing locks, and maintaining a lock table.

Two-Phase Locking (2PL)

Two-Phase Locking (2PL) is a widely used protocol that ensures serializability. It ensures that transactions acquire all required locks before releasing any, thus dividing the transaction's lifetime into two phases.

Phases of 2PL:

1. Growing Phase: A transaction can acquire locks but cannot release any. It continues to acquire locks as needed.
2. Shrinking Phase: A transaction can release locks but cannot acquire any new locks. Once a transaction enters the shrinking phase, it cannot acquire any more locks.

Important Observation: The point at which a transaction has acquired its final lock and is about to release its first lock is called the lock point.

Types of 2PL:

• Strict 2PL: A transaction holds all its exclusive (write) locks until it commits or aborts. This prevents dirty reads and ensures recoverability.
• Rigorous 2PL: A transaction holds all its locks (both shared and exclusive) until it commits or aborts. This is even stricter than Strict 2PL and guarantees recoverability and cascade-free rollbacks.

Advantages of 2PL:

• Guarantees serializability.
• Relatively easy to implement.

Disadvantages of 2PL:

• Can lead to deadlocks.
• Can reduce concurrency compared to other protocols due to holding locks for longer durations.
• Not always optimal for performance.

Lock Granularity

Lock granularity refers to the size of the data item on which a lock is applied. Choosing the right granularity is crucial for performance.

• Fine Granularity: Locking individual tuples (rows) or attributes.
  • Advantages: Higher concurrency (less contention).
  • Disadvantages: Higher overhead (more locks to manage).
• Coarse Granularity: Locking entire tables, pages, or even the entire database.
  • Advantages: Lower overhead (fewer locks to manage).
  • Disadvantages: Lower concurrency (more contention).

Many systems use a multiple-granularity locking scheme, where locks can be acquired at different levels of granularity (e.g., database, file, page, record).

Timestamp-Based Protocols

Timestamp-based protocols assign a unique timestamp to each transaction. These timestamps determine the serializability order of transactions, ensuring that conflicting operations are processed in the order of their timestamps.

Definition: A timestamp is a unique identifier assigned to a transaction, typically reflecting the order in which transactions start or are submitted to the system.

The system maintains two timestamp values for each data item Q:

• W_timestamp(Q): The largest timestamp of any transaction that successfully wrote Q.
• R_timestamp(Q): The largest timestamp of any transaction that successfully read Q.

Timestamp Ordering (TO) Protocol

The TO protocol ensures that if transaction Ti has a smaller timestamp than transaction Tj (TS(Ti) < TS(Tj)), then the system must ensure that Ti's operations appear to execute before Tj's operations in the serializable schedule.

Processing Read Operation (read(Q) by Ti):

• If TS(Ti) < W_timestamp(Q): This means Ti is trying to read a value that has already been overwritten by a younger transaction. This is a "too late" read. Ti is rolled back (aborted) and restarted with a new, larger timestamp.
• If TS(Ti) ≥ W_timestamp(Q): The read operation is allowed. Update R_timestamp(Q) to max(R_timestamp(Q), TS(Ti)).

Processing Write Operation (write(Q) by Ti):

• If TS(Ti) < R_timestamp(Q): This means Ti is trying to write a value that has already been read by a younger transaction. This is a "too late" write, potentially causing a dirty write or overwriting a value that a younger transaction based its read on. Ti is rolled back.
• If TS(Ti) < W_timestamp(Q): This means Ti is trying to write a value that has already been overwritten by a younger transaction. This is also a "too late" write. Ti is rolled back.
• If TS(Ti) ≥ R_timestamp(Q) AND TS(Ti) ≥ W_timestamp(Q): The write operation is allowed. Update W_timestamp(Q) to TS(Ti).

Thomas's Write Rule

Thomas's Write Rule is a modification to the basic Timestamp Ordering protocol for write operations that can improve concurrency. It avoids unnecessary rollbacks in certain scenarios.

Modification for Write Operation (write(Q) by Ti):

• If TS(Ti) < R_timestamp(Q): Ti is rolled back (same as TO protocol).
• If TS(Ti) < W_timestamp(Q): Instead of rolling back Ti, the write operation is simply ignored (this is known as a "timestamp write-ahead" or "obsolete write"). The idea is that a younger transaction has already written a value that would have overwritten Ti's write anyway.
• If TS(Ti) ≥ R_timestamp(Q) AND TS(Ti) ≥ W_timestamp(Q): The write operation is performed, and W_timestamp(Q) is updated to TS(Ti) (same as TO protocol).

Exam-Oriented Note: Thomas's Write Rule allows for greater concurrency but may lead to schedules that are not view serializable, although they remain conflict serializable.

Validation-Based Protocols (Optimistic Concurrency Control)

Validation-based protocols, also known as Optimistic Concurrency Control (OCC), assume that conflicts between transactions are rare. Transactions execute without explicit locking and validate their operations only at commit time.

If conflicts are detected during validation, the transaction is rolled back and restarted. This approach is "optimistic" because it hopes that conflicts will not occur.

Phases of a Transaction in OCC:

1. Read Phase: The transaction reads all data items it needs and stores them in its local workspace. All write operations are performed on temporary local copies. No locks are acquired.
2. Validation Phase: The transaction performs a check to ensure that its operations have not violated serializability with respect to other concurrently executing transactions. This is where conflicts are detected.
3. Write Phase: If the validation is successful, the transaction's local updates are made permanent in the database. If validation fails, the transaction is aborted and restarted.

Validation Test (for transaction Ti):

Ti's validation phase checks if it conflicts with any transaction Tj that committed while Ti was executing its read phase. This typically involves checking if:

• Ti has read any data item that Tj wrote.
• Tj has read any data item that Ti wrote (and Ti is still in its read phase).
• Ti has written any data item that Tj read or wrote.

If any conflict is detected, Ti is aborted. Otherwise, it commits.

Advantages of OCC:

• Higher concurrency compared to lock-based protocols when conflict rates are low.
• No deadlocks (since no locks are held during execution).

Disadvantages of OCC:

• High overhead if conflict rates are high (frequent rollbacks).
• Longer transactions are more likely to be aborted.
• Cannot guarantee progress for transactions that are frequently chosen as victims.

Deadlock Handling

A deadlock occurs when two or more transactions are indefinitely waiting for each other to release a lock, resulting in a standstill where none of the transactions can proceed.

Definition: A deadlock is a state in which each member of a group of transactions is waiting for another member of the group to take action (e.g., release a lock) to resume its own execution.

Conditions for Deadlock (typically used in operating systems but applicable to DB locking):

• Mutual Exclusion: At least one resource (data item) must be held in a non-sharable mode.
• Hold and Wait: A transaction holding at least one resource is waiting to acquire additional resources held by other transactions.
• No Preemption: Resources cannot be forcibly taken from a transaction; they can only be released voluntarily.
• Circular Wait: A circular chain of transactions exists, where each transaction in the chain is waiting for a resource held by the next transaction in the chain.

There are generally two strategies for handling deadlocks:

Deadlock Prevention

Deadlock prevention protocols ensure that deadlocks can never occur by imposing restrictions on how transactions request and acquire locks. This is typically done by breaking one of the four deadlock conditions.

Common Prevention Schemes:

• Wait-Die Scheme:
  • If TS(Ti) < TS(Tj) (Ti is older), and Ti requests a resource held by Tj: Ti is allowed to wait.
  • If TS(Ti) > TS(Tj) (Ti is younger), and Ti requests a resource held by Tj: Ti is immediately aborted ("dies") and restarted with its original timestamp.

  This scheme ensures that only older transactions wait for younger ones, preventing circular waits.

• Wound-Wait Scheme:
  • If TS(Ti) < TS(Tj) (Ti is older), and Ti requests a resource held by Tj: Tj is aborted ("wounded") and restarted (Ti "wounds" Tj).
  • If TS(Ti) > TS(Tj) (Ti is younger), and Ti requests a resource held by Tj: Ti is immediately allowed to wait.

  This scheme ensures that younger transactions wait for older ones, preventing circular waits.

• Resource Ordering: All transactions request resources in a predefined global order. This prevents circular waits.
• Pre-claiming: Transactions declare all required resources at the beginning and acquire them all or none. This prevents hold and wait.

Important Observation: Both Wait-Die and Wound-Wait schemes prevent deadlocks but can lead to transaction starvation if a transaction is repeatedly aborted and restarted.

Deadlock Detection and Recovery

In this approach, deadlocks are allowed to occur. The system periodically checks for deadlocks and, if detected, takes action to resolve them.

Deadlock Detection:

• Wait-for Graph: The system maintains a directed graph where nodes are transactions and an edge from Ti to Tj means Ti is waiting for Tj to release a resource. A deadlock exists if and only if there is a cycle in the wait-for graph.

Deadlock Recovery:

Once a deadlock is detected, the system must break the cycle by aborting one or more transactions (victim selection).

• Victim Selection: The system chooses a transaction to abort based on criteria like:
  • Transaction that has done the least work so far.
  • Transaction that has held the fewest locks.
  • Transaction that will involve the minimum rollback cost.
  • Transaction that is furthest from completion.
• Rollback: The chosen victim transaction is rolled back. This means undoing all its partial work and releasing all its locks.
  • Partial Rollback: Rollback only enough to break the deadlock.
  • Total Rollback: Abort the transaction completely.
• Starvation: A transaction might be repeatedly chosen as a victim. To prevent this, a mechanism (e.g., giving higher priority to transactions that have been aborted multiple times) should be implemented.

Concurrency Control for Insert and Delete Operations

Insert and Delete operations introduce specific challenges for concurrency control, primarily related to the phantom problem.

Definition: A phantom is a row that matches a query's search criteria but is "invisible" at one point in a transaction and "visible" at another point due to an insert or delete operation by another concurrent transaction.

Example of Phantom Problem:

1. Transaction T1 reads all employees in 'Sales' department.
2. Transaction T2 inserts a new employee into the 'Sales' department and commits.
3. Transaction T1 re-reads all employees in 'Sales' department and finds a new employee it didn't see before, violating the repeatability of its read set.

Strategies to Handle Inserts and Deletes:

• Index Locking: If queries use an index, locks can be placed on the index entries that cover the range of records being accessed. For inserts, a lock might be placed on the "next key" or a "gap" between existing keys to prevent new records from appearing in a range that has been read.
• Predicate Locking: Locks are placed on conditions (predicates) rather than specific data items. If a transaction reads all rows satisfying a predicate P, it acquires a predicate lock on P. Any transaction attempting to insert or delete a row satisfying P would be blocked. This is powerful but complex to implement.
• Next-Key Locking: A combination of record locking and gap locking. A lock on a record also locks the "gap" before it, up to the next record. This prevents phantoms by ensuring that no new records can be inserted into the locked range. This is commonly used in databases to achieve Repeatable Read and Serializable isolation levels.

Weak Levels of Consistency (Isolation Levels)

While serializability is the gold standard for correctness, it can be overly restrictive and may lead to poor performance in high-concurrency environments. Many database systems offer weaker levels of consistency, also known as isolation levels, which relax some serializability requirements to improve performance.

The ANSI/ISO SQL standard defines four isolation levels:

1. Read Uncommitted

• Description: The lowest isolation level. A transaction can read data that has been modified by other transactions but not yet committed.
• Anomalies Allowed:
  • Dirty Read (or Uncommitted Read): A transaction reads data written by another concurrent transaction that has not yet committed. If the writing transaction aborts, the data read by the first transaction becomes invalid.
  • Non-repeatable Read
  • Phantom Read
• Use Case: Reporting applications where approximate data is acceptable and performance is critical.

2. Read Committed

• Description: A transaction can only read data that has been committed. This prevents dirty reads. However, subsequent reads within the same transaction might see different values if another transaction commits changes between reads.
• Anomalies Allowed:
  • Non-repeatable Read: A transaction re-reads data it previously read and finds that another transaction has modified and committed the data.
  • Phantom Read
• Use Case: Most common default isolation level in many database systems (e.g., Oracle, SQL Server). Provides a good balance between consistency and concurrency for many applications.

3. Repeatable Read

• Description: A transaction guarantees that if it reads a record, it will see the same value if it re-reads it later, as long as it's within the same transaction. This prevents dirty reads and non-repeatable reads. However, new rows matching a query's criteria can still appear.
• Anomalies Allowed:
  • Phantom Read: A transaction re-executes a query and finds new rows that satisfy the query condition, which were inserted by another committed transaction.
• Use Case: Applications requiring consistent reads of existing data during a transaction, but can tolerate new data appearing.

4. Serializable

• Description: The highest isolation level. It guarantees that the concurrent execution of transactions is equivalent to some serial execution. This prevents all three anomalies: dirty reads, non-repeatable reads, and phantom reads. It effectively makes transactions appear to execute one after another.
• Anomalies Allowed: None.
• Use Case: Applications where strict data consistency is paramount, such as financial transactions, often at the cost of reduced concurrency.

Summary of Isolation Levels and Anomalies Prevented: