Transaction Management and Concurrency Control

ACID Properties

In the realm of database management systems (DBMS), a transaction is a single unit of work that performs a sequence of database operations. These operations can be read operations, write operations, or a combination of both. For a database to maintain its integrity and consistency, especially in environments where multiple transactions might be executing concurrently, it's crucial that transactions adhere to a set of properties known as ACID properties. ACID is an acronym that stands for Atomicity, Consistency, Isolation, and Durability. These properties ensure that database transactions are processed reliably.

Atomicity

Atomicity means that a transaction is treated as a single, indivisible unit of work. Either all of its operations are successfully completed and committed to the database, or none of them are. If any part of the transaction fails, the entire transaction is aborted, and the database is rolled back to its state before the transaction began. This prevents partial updates that could leave the database in an inconsistent state. For example, consider a bank transfer where money is debited from one account and credited to another. Atomicity ensures that either both operations complete successfully, or neither does. If the debit succeeds but the credit fails, the debit is undone.

Consistency

Consistency ensures that a transaction brings the database from one valid state to another. It guarantees that any transaction will preserve the integrity constraints defined on the database. These constraints can include things like primary keys, foreign keys, data types, and business rules. If a transaction would violate any of these constraints, it is aborted. For instance, if a database has a rule that an account balance cannot be negative, a transaction attempting to withdraw more money than available would violate this constraint and be rolled back to maintain consistency. The system's state before the transaction and after the transaction (if committed) must be valid according to all defined rules.

Isolation

Isolation ensures that concurrently executing transactions do not interfere with each other. Each transaction appears to be executed in isolation, as if it were the only transaction running on the system. This means that the intermediate results of one transaction are not visible to other concurrent transactions until the first transaction is committed. If isolation were not enforced, issues like dirty reads, non-repeatable reads, and phantom reads could occur, leading to incorrect data. Different levels of isolation exist, offering varying degrees of protection against these anomalies.

Durability

Durability ensures that once a transaction has been committed, its changes are permanent and will survive any subsequent system failures, such as power outages or crashes. This is typically achieved by writing transaction logs to non-volatile storage before acknowledging the commit to the user. If the system fails after a transaction is committed, the DBMS will use these logs to restore the committed data upon recovery. For example, if you receive confirmation that your online order has been placed, durability guarantees that the order will still be in the system even if the server crashes immediately afterward.

Serializability

Serializability is a property that ensures the outcome of executing multiple concurrent transactions is equivalent to some serial execution of those transactions. In other words, even though transactions might be interleaved in their execution, the final state of the database should be the same as if they were executed one after another in some sequential order. This is a fundamental concept for maintaining data integrity in concurrent environments.

There are two main types of serializability:

1. Conflict Serializability

A schedule (an ordering of operations from concurrent transactions) is conflict serializable if it can be transformed into a serial schedule by a series of swappings of adjacent non-conflicting operations. Two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation.

Consider two transactions, T1 and T2. If T1 reads data item 'X' and then T2 writes to 'X', these operations conflict. If T1 writes to 'X' and T2 reads 'X', they conflict. If both T1 and T2 write to 'X', they also conflict. The order matters.

2. View Serializability

View serializability is a weaker notion than conflict serializability. A schedule is view serializable if it has the same "view" as some serial schedule. The "view" of a schedule includes the initial read values, the final values written, and the read-modify-write operations. A schedule can be view serializable even if it's not conflict serializable. For example, a schedule involving a "dirty read" (reading uncommitted data) might be view serializable but not conflict serializable.

Ensuring serializability is essential for the correctness of concurrent transaction processing. While full serializability can be computationally expensive to guarantee, DBMSs often aim for conflict serializability or provide different isolation levels that offer practical trade-offs between consistency and performance.

Lock-Based Concurrency Control

Lock-based protocols are a common approach to ensure serializability and manage concurrency in databases. In this method, transactions acquire locks on data items before accessing them and release these locks when they are done. Locks prevent other transactions from performing conflicting operations on the same data item until the lock is released.

There are two primary types of locks:

• Shared Lock (S-lock or Read Lock): Multiple transactions can hold a shared lock on the same data item simultaneously. This allows them to read the data. However, no transaction can acquire an exclusive lock on a data item that already has one or more shared locks.
• Exclusive Lock (X-lock or Write Lock): Only one transaction can hold an exclusive lock on a data item at a time. This lock is required for writing to the data item. If a transaction holds an X-lock, no other transaction can acquire either an S-lock or an X-lock on that item.

Two-Phase Locking (2PL)

Two-Phase Locking (2PL) is a widely used protocol to ensure serializability. It requires that each transaction follows a specific locking discipline: it must acquire all the locks it needs before it starts releasing any of them. The protocol is divided into two phases:

1. Growing Phase: In this phase, a transaction can acquire locks on data items but cannot release any locks.
2. Shrinking Phase: In this phase, a transaction can release locks but cannot acquire any new locks.

Once a transaction releases a lock, it enters the shrinking phase and cannot acquire any more locks. This rule prevents cascading rollbacks and ensures serializability.

There are variations of 2PL:

• Strict Two-Phase Locking (Strict 2PL): In Strict 2PL, all exclusive locks acquired by a transaction are held until the transaction commits or aborts. Shared locks can be released earlier, but typically, all locks are held until the end. This protocol prevents dirty reads and cascading rollbacks and guarantees conflict serializability.
• Rigorous Two-Phase Locking: In Rigorous 2PL, all locks (both shared and exclusive) are held until the transaction commits or aborts. This is a stronger protocol than Strict 2PL and also guarantees conflict serializability, simplifying recovery as well.

Deadlocks

A deadlock is a situation where two or more transactions are waiting indefinitely for each other to release locks. For example, if Transaction T1 holds an exclusive lock on data item A and is waiting to acquire an exclusive lock on data item B, while Transaction T2 holds an exclusive lock on data item B and is waiting to acquire an exclusive lock on data item A, then T1 and T2 are deadlocked.

DBMSs typically handle deadlocks using one of three methods:

1. Deadlock Prevention: This involves imposing an order on lock requests or using specific protocols that prevent deadlocks from occurring in the first place. For example, assigning a unique timestamp to each transaction and requiring that transactions only request locks on data items with higher timestamps can prevent deadlocks.
2. Deadlock Detection: The system periodically checks for cycles in the wait-for graph (a graph where nodes are transactions and a directed edge from T1 to T2 means T1 is waiting for a resource held by T2). If a cycle is detected, it indicates a deadlock. The system then resolves the deadlock by aborting one or more transactions involved in the cycle.
3. Deadlock Avoidance: This is less common in database systems. It involves making decisions about granting or denying lock requests based on the current state of the system to avoid entering a deadlock state.

Time-Stamping Methods

Time-stamp ordering is another concurrency control method that ensures serializability. Each transaction is assigned a unique, monotonically increasing timestamp when it enters the system. This timestamp is used to order transactions. The protocol ensures that the execution order of transactions is equivalent to their timestamp order.

For each data item, the system maintains two time-stamps:

• Read-Timestamp (RTS): The timestamp of the latest transaction that read the data item.
• Write-Timestamp (WTS): The timestamp of the latest transaction that wrote to the data item.

When a transaction Ti with timestamp TS(Ti) attempts an operation on data item X:

• Read(X): If TS(Ti) < WTS(X), the read operation is rejected, and Ti is aborted because a more recent transaction has already modified X. Otherwise, RTS(X) is updated to max(RTS(X), TS(Ti)).
• Write(X): If TS(Ti) < RTS(X) or TS(Ti) < WTS(X), the write operation is rejected, and Ti is aborted. This is because Ti is attempting to modify X after it has been read or written by a more recent transaction. Otherwise, WTS(X) is updated to TS(Ti).

This method guarantees serializability but can lead to frequent transaction aborts if there are many concurrent transactions.

Optimistic Methods (Validation-Based Concurrency Control)

Optimistic concurrency control, also known as validation-based concurrency control, operates on the assumption that conflicts between transactions are rare. Instead of using locks, transactions execute freely without acquiring any locks during their execution phase. They perform their operations on private copies of data or in temporary storage.

Each transaction typically goes through three phases:

1. Read Phase: The transaction reads data and performs operations, possibly writing to private workspace.
2. Validation Phase: Before committing, the transaction's operations are checked to see if they conflict with any concurrently committed transactions. This phase determines if the transaction can be committed without violating serializability.
3. Write Phase: If the transaction passes validation, its changes are made permanent in the database. If it fails validation, it is aborted and must be restarted.

The validation phase is crucial. It checks for conflicts by comparing the read and write sets of the transaction with those of other concurrently executed and committed transactions. For a transaction Ti to be validated, it must satisfy the following conditions for all other transactions Tj that have committed before Ti starts its validation phase:

• The set of data items read by Ti must not have been written by Tj.
• The set of data items written by Ti must not have been read or written by Tj.

Optimistic methods can offer higher concurrency in low-conflict environments but can be inefficient if conflicts are frequent, as many transactions might be aborted and restarted.