Two-Phase Locking Algorithm: Database Engineering Guide

Introduction and Core Concepts

The two-phase locking algorithm (2PL) is the foundational concurrency control protocol that guarantees serializability in database management systems. At its core, 2PL ensures that concurrent transactions produce results equivalent to some serial execution, preventing anomalies like lost updates, dirty reads, and inconsistent analysis. Without a rigorous locking discipline, interleaved transactions could corrupt data integrity, making 2PL essential for any system that requires ACID properties, particularly Atomicity, Consistency, and Isolation.

The central principle of the two-phase locking algorithm is deceptively simple: every transaction must be divided into two distinct phases. In the first phase, known as the Growing Phase or Expanding Phase, the transaction may acquire locks but may not release any. In the second phase, called the Shrinking Phase, the transaction may release locks but may not acquire any new ones. Once a transaction releases its first lock, it has entered the shrinking phase and is forbidden from requesting additional locks. This strict ordering is what enforces conflict serializability.

To understand why this matters, consider a database handling thousands of concurrent transactions per second, such as an airline reservation system or a banking ledger. Two transactions might attempt to read and write the same account balance simultaneously. Without 2PL, a schedule could interleave operations in a way that is not serializable, leading to incorrect final states. The two-phase locking algorithm provides a provably correct mechanism to prevent such schedules. It is pessimistic in nature, meaning it assumes conflicts will happen and blocks transactions preemptively, in contrast to optimistic concurrency control which detects conflicts at commit time.

Lock Types and Compatibility

2PL relies on two fundamental lock modes. A Shared lock (S-lock or read lock) allows a transaction to read but not write a data item. Multiple transactions can hold a shared lock on the same item simultaneously. An Exclusive lock (X-lock or write lock) allows both reading and writing, but no other transaction may hold any lock (shared or exclusive) on that item while the exclusive lock is held. This compatibility matrix is the enforcement mechanism for isolation.

The protocol also defines rules for lock upgrading and downgrading. A transaction holding a shared lock may upgrade it to an exclusive lock if it needs to write, but only if no other transaction holds a shared lock on the same item. This upgrade must still occur during the growing phase. Understanding these lock modes is critical because the correctness of 2PL depends entirely on adhering to the compatibility rules while respecting the two-phase boundary.

How It Works

The mechanism of the two-phase locking algorithm is governed by three core rules. First, a transaction must acquire a shared lock before reading and an exclusive lock before writing any data item. Second, once the transaction releases any lock, it can never acquire another lock. Third, all locks must be eventually released, typically at or after commit or abort. The point in a transaction's execution where it has acquired all the locks it will ever need, just before it releases its first lock, is called the lock point.

The growing phase is characterized by lock acquisition. As the transaction executes its read and write operations, it requests locks from the lock manager. If the requested lock is compatible with existing locks held by other transactions, it is granted immediately. If not, the requesting transaction is blocked and placed in a wait queue until the conflicting lock is released. This phase continues until the transaction determines it needs no more locks. Importantly, the transaction does not need to know its entire read/write set in advance; it can acquire locks on demand, as long as it has not yet started releasing.

The shrinking phase begins with the first unlock operation. From this moment forward, the transaction can only release locks. In the basic 2PL variant, locks can be released incrementally as soon as they are no longer needed, which increases concurrency. However, this early release can lead to cascading aborts if the transaction later aborts after other transactions have read its uncommitted writes. This vulnerability leads to stricter variants like Strict 2PL and Rigorous 2PL, which delay unlocks until commit. The serializability guarantee comes from the fact that the lock points of conflicting transactions order them. If transaction T1's lock point precedes T2's lock point, then all conflicting operations of T1 will appear before those of T2 in any equivalent serial schedule.

The Lock Manager and Deadlock Handling

A central component called the Lock Manager or Lock Table is responsible for tracking which transaction holds which lock on which resource, the lock mode, and the wait queues. The lock manager maintains a hash table indexed by data item identifier, with entries containing granted locks and waiting requests. When a transaction requests a lock, the manager checks the compatibility matrix and either grants, denies, or queues the request.

Because 2PL blocks transactions, it is inherently prone to deadlocks. A deadlock occurs when two or more transactions wait for each other in a cycle, for example, T1 holds an X-lock on A and waits for B, while T2 holds an X-lock on B and waits for A. The system must have a deadlock detection or prevention scheme. Detection typically uses a wait-for graph where nodes are transactions and edges represent waiting relationships; a cycle indicates deadlock. Prevention schemes like Wait-Die and Wound-Wait use timestamps to decide which transaction should wait or abort to break potential cycles before they form.

Implementation

Implementing the two-phase locking algorithm requires a lock manager, transaction abstraction, and enforcement of the two-phase rule. Below is a simplified but functional Python implementation that demonstrates the core concepts. This implementation is for educational purposes and omits persistence and recovery logic found in production databases.

from collections import defaultdict, deque
import threading

class LockManager:
    """Centralized lock manager handling S and X locks."""
    def __init__(self):
        # resource_id -> {txn_id: lock_type}
        self.lock_table = defaultdict(dict)
        # resource_id -> deque of (txn_id, lock_type)
        self.wait_queues = defaultdict(deque)
        self._lock = threading.Lock()

    def _is_compatible(self, resource, requested_type):
        """Check if requested lock is compatible with granted locks."""
        granted = self.lock_table[resource]
        if not granted:
            return True
        if requested_type == "S":
            # S is compatible only if no X lock exists
            return all(lock_type == "S" for lock_type in granted.values())
        else:  # requested_type == "X"
            # X is incompatible with any existing lock
            return False

    def acquire(self, txn_id, resource, lock_type):
        """Try to acquire lock. Returns True if granted, False if must wait."""
        with self._lock:
            if self._is_compatible(resource, lock_type):
                self.lock_table[resource][txn_id] = lock_type
                print(f"Txn {txn_id} GRANTED {lock_type}-lock on {resource}")
                return True
            else:
                self.wait_queues[resource].append((txn_id, lock_type))
                print(f"Txn {txn_id} WAITING for {lock_type}-lock on {resource}")
                return False

    def release(self, txn_id, resource):
        """Release lock and grant to next waiter if compatible."""
        with self._lock:
            if txn_id in self.lock_table[resource]:
                del self.lock_table[resource][txn_id]
                print(f"Txn {txn_id} RELEASED lock on {resource}")
                # Try to grant waiting requests in FIFO order
                self._grant_waiters(resource)

    def _grant_waiters(self, resource):
        while self.wait_queues[resource]:
            txn_id, lock_type = self.wait_queues[resource][0]
            if self._is_compatible(resource, lock_type):
                self.wait_queues[resource].popleft()
                self.lock_table[resource][txn_id] = lock_type
                print(f"Txn {txn_id} GRANTED {lock_type}-lock on {resource} (from queue)")
            else:
                break

class Transaction2PL:
    """Transaction enforcing two-phase locking rule."""
    def __init__(self, txn_id, lock_manager):
        self.txn_id = txn_id
        self.lock_manager = lock_manager
        self.held_locks = set()
        self.phase = "GROWING"  # GROWING or SHRINKING
        self.state = "ACTIVE"

    def read(self, resource):
        """Acquire S-lock if needed, then read."""
        if self.phase == "SHRINKING":
            raise Exception(f"Txn {self.txn_id}: Cannot acquire lock in SHRINKING phase!")
        
        if resource not in self.held_locks:
            granted = self.lock_manager.acquire(self.txn_id, resource, "S")
            if not granted:
                self.state = "WAITING"
                return False  # Blocked
            self.held_locks.add(resource)
        print(f"Txn {self.txn_id} READS {resource}")
        return True

    def write(self, resource):
        """Acquire X-lock if needed, then write. Handles upgrade."""
        if self.phase == "SHRINKING":
            raise Exception(f"Txn {self.txn_id}: Cannot acquire lock in SHRINKING phase!")
        
        # Need X-lock for write
        if resource not in self.held_locks:
            granted = self.lock_manager.acquire(self.txn_id, resource, "X")
            if not granted:
                self.state = "WAITING"
                return False
            self.held_locks.add(resource)
        else:
            # Upgrade S -> X if currently holding S
            # In real system, check compatibility before upgrade
            print(f"Txn {self.txn_id} UPGRADES to X-lock on {resource}")
        print(f"Txn {self.txn_id} WRITES {resource}")
        return True

    def unlock(self, resource):
        """Release a lock and enter shrinking phase."""
        if resource in self.held_locks:
            self.lock_manager.release(self.txn_id, resource)
            self.held_locks.remove(resource)
            if self.phase == "GROWING":
                print(f"Txn {self.txn_id} ENTERS SHRINKING PHASE")
                self.phase = "SHRINKING"

    def commit(self):
        """Release all remaining locks (Strict 2PL would hold until here)."""
        print(f"Txn {self.txn_id} COMMITTING")
        for resource in list(self.held_locks):
            self.unlock(resource)
        self.state = "COMMITTED"

# Demonstration of Strict Two-Phase Locking (Strict 2PL)
# Strict 2PL holds all X-locks until commit to prevent cascading aborts

class StrictTransaction2PL(Transaction2PL):
    """Strict 2PL variant: holds all exclusive locks until commit."""
    def __init__(self, txn_id, lock_manager):
        super().__init__(txn_id, lock_manager)
        self.x_locks = set()

    def write(self, resource):
        success = super().write(resource)
        if success:
            self.x_locks.add(resource)
        return success

    def unlock(self, resource):
        # In Strict 2PL, X-locks cannot be released early
        if resource in self.x_locks:
            print(f"Txn {self.txn_id} DELAYS release of X-lock on {resource} until commit")
            return False
        return super().unlock(resource)

    def commit(self):
        print(f"Txn {self.txn_id} STRICT COMMIT - releasing all locks")
        for resource in list(self.held_locks):
            self.lock_manager.release(self.txn_id, resource)
        self.held_locks.clear()
        self.x_locks.clear()
        self.state = "COMMITTED"

# Example usage
lm = LockManager()
t1 = StrictTransaction2PL(1, lm)
t2 = StrictTransaction2PL(2, lm)

t1.write("A")  # T1 gets X-lock on A
t2.read("A")   # T2 waits - A is X-locked by T1
t1.commit()    # T1 releases A, T2 is granted
t2.read("A")   # Now succeeds
t2.commit()

# Deadlock Detection using Wait-For Graph
from collections import defaultdict

class DeadlockDetector:
    """Detects cycles in wait-for graph for 2PL."""
    def __init__(self):
        # txn_id -> set of txn_ids it waits for
        self.wait_for_graph = defaultdict(set)

    def add_edge(self, waiting_txn, holding_txn):
        """Add edge waiting_txn -> holding_txn."""
        self.wait_for_graph[waiting_txn].add(holding_txn)

    def remove_transaction(self, txn_id):
        """Remove txn and all edges involving it."""
        if txn_id in self.wait_for_graph:
            del self.wait_for_graph[txn_id]
        for waits in self.wait_for_graph.values():
            waits.discard(txn_id)

    def has_deadlock(self):
        """Detect cycle using DFS. Returns cycle if found."""
        visiting = set()
        visited = set()
        path = []

        def dfs(node):
            if node in visiting:
                # Found cycle
                cycle_start = path.index(node)
                return path[cycle_start:] + [node]
            if node in visited:
                return None
            visiting.add(node)
            path.append(node)
            for neighbor in self.wait_for_graph.get(node, []):
                result = dfs(neighbor)
                if result:
                    return result
            path.pop()
            visiting.remove(node)
            visited.add(node)
            return None

        for node in list(self.wait_for_graph.keys()):
            if node not in visited:
                cycle = dfs(node)
                if cycle:
                    return cycle
        return None

# Example: T1 waits for T2, T2 waits for T1 -> deadlock
detector = DeadlockDetector()
detector.add_edge(1, 2)  # T1 waits for T2 (T2 holds B)
detector.add_edge(2, 1)  # T2 waits for T1 (T1 holds A)
cycle = detector.has_deadlock()
if cycle:
    print(f"DEADLOCK detected: {' -> '.join(map(str, cycle))}")
    # Victim selection: abort youngest transaction
    victim = max(cycle[:-1])  # Highest txn_id = youngest
    print(f"Aborting victim Txn {victim} to break deadlock")

These examples illustrate the critical enforcement of the growing and shrinking phases, the role of the lock manager in mediating compatibility, and the necessity of deadlock handling. In a production system, the lock manager would also handle lock escalation, timeout-based deadlock resolution, and integration with the write-ahead log for recovery.

Step-by-Step Example

To make the two-phase locking algorithm concrete, let us walk through a classic bank transfer scenario with two concurrent transactions operating on accounts A and B. Assume initial values are A = 1000 and B = 2000. Transaction T1 transfers $100 from A to B, while Transaction T2 reads both balances to compute total assets.

Transaction T1 consists of operations: read(A), A = A - 100, write(A), read(B), B = B + 100, write(B). Transaction T2 consists of: read(A), read(B), display(A+B). Without concurrency control, an interleaving could cause T2 to see an inconsistent state where the debit from A is visible but the credit to B is not yet applied, resulting in an incorrect total of 2900 instead of 3000.

Let us see how Basic 2PL enforces serializability. Initially, both transactions are in the growing phase. T1 requests an X-lock on A to perform its write. The lock manager grants it since no other transaction holds a lock on A. T1 reads A and writes A. Concurrently, T2 requests an S-lock on A to read it. Since T1 holds an X-lock on A, the request is incompatible, so T2 is blocked and placed in the wait queue for A. This blocking is the key to preventing the inconsistent read.

T1 continues by requesting an X-lock on B. This is granted, and T1 completes its write to B. At this point, T1 has acquired all locks it needs. It now begins its shrinking phase by releasing its X-lock on A. The moment it releases this first lock, it can no longer acquire any new locks. The lock manager then grants T2's waiting S-lock request on A. T2 reads A, which now reflects T1's committed transfer. T1 then releases its lock on B, and T2 can acquire its S-lock on B and read the updated value. T2 then releases both locks and commits. The resulting schedule is conflict serializable and equivalent to the serial order T1 followed by T2.

What Happens Without Strictness?

If T1 had used Basic 2PL and released its lock on A immediately after writing A, but then aborted before writing B, T2 would have read an uncommitted value of A that is later rolled back, causing a dirty read and a cascading abort where T2 must also be aborted. This is why most commercial databases implement Strict 2PL, where all exclusive locks are held until the transaction commits or aborts, ensuring strict schedules that are both serializable and recoverable without cascading aborts.

This step-by-step walkthrough demonstrates the lock point concept. T1's lock point occurs just before it releases its first lock, after it has acquired locks on both A and B. T2's lock point occurs when it acquires its final lock on B. Since T1's lock point precedes T2's lock point, the equivalent serial schedule is T1 before T2, which matches the actual execution order enforced by blocking.

Complexity Analysis

Analyzing the two-phase locking algorithm requires distinguishing between the protocol's logical guarantees and the implementation costs of the lock manager. The protocol itself does not have a traditional algorithmic time complexity like sorting, but its overhead can be quantified in terms of lock operations, concurrency, and deadlock handling.

Lock acquisition and release operations are typically O(1) average case when using a hash table for the lock table, assuming good hashing and low contention. Checking compatibility requires examining the list of granted locks for a resource, which is O(k) where k is the number of transactions currently holding a lock on that resource. In practice, k is small, often 1 for exclusive locks or a handful for shared locks, so this is effectively constant time. However, under high contention with many shared locks, this check can degrade.

The dominant cost in 2PL is blocking and deadlock management. In the best case with no contention, transactions never wait, and throughput scales linearly with the number of transactions. In the average case with moderate contention, some transactions wait, introducing latency but preserving correctness. In the worst case with high contention or deadlock, the system may experience thrashing where most transactions are blocked, and deadlock detection, which is O(V + E) for a wait-for graph with V transactions and E wait edges, must be run periodically. Deadlock detection frequency is a tunable parameter that trades off detection latency against CPU overhead.

Space complexity is dominated by the lock table and wait queues. The lock table stores an entry for each locked data item, and each entry stores the list of holders. In the worst case where every transaction locks many items, space is O(N * M) where N is the number of active transactions and M is the average number of locks per transaction. In practice, lock managers use lock escalation to reduce memory by replacing many fine-grained row locks with a single table lock when a transaction exceeds a threshold, trading concurrency for memory efficiency.

* k = number of holders on resource, typically small
** w = wait queue length for resource
*** c = contention factor, T = number of transactions

The key takeaway is that 2PL's performance is highly workload-dependent. It excels in low-to-moderate contention workloads where blocking is rare, but can suffer under hot-spot contention where many transactions compete for the same few rows. This is why modern systems often combine 2PL with techniques like intention locks for hierarchical locking and timeouts to bound waiting.

Variations and Optimizations

Basic 2PL, while guaranteeing serializability, suffers from practical drawbacks like cascading aborts, deadlocks, and reduced concurrency due to early blocking. Several well-established variations address these limitations, each making different trade-offs between concurrency, recovery complexity, and overhead.

Strict Two-Phase Locking (Strict 2PL) is the most widely implemented variant in commercial databases such as PostgreSQL, MySQL InnoDB, and SQL Server. In Strict 2PL, all exclusive (X) locks are held until the transaction commits or aborts, while shared locks may be released earlier. This guarantees strict schedules, which are recoverable, avoid cascading aborts, and simplify recovery because no other transaction can read uncommitted writes. The cost is reduced concurrency, as read locks held by other transactions may be blocked longer waiting for X-locks to be released at commit.

Rigorous Two-Phase Locking goes one step further and holds all locks, both shared and exclusive, until commit or abort. This provides even stronger guarantees and makes the commit ordering equivalent to the serialization order, which simplifies distributed commit protocols. However, it further reduces concurrency compared to Strict 2PL, as shared locks are also held longer, blocking other readers unnecessarily in some cases.

Conservative or Static 2PL requires a transaction to pre-declare its entire read and write set and acquire all locks before execution begins. If any lock cannot be acquired, no locks are acquired and the transaction waits. This variant is deadlock-free because no transaction ever waits while holding locks, but it is impractical for most applications where the access set is not known in advance and it reduces concurrency by acquiring locks earlier than needed. It is primarily of theoretical interest or used in specialized embedded systems.

Advanced Optimizations

Beyond these core variants, production systems employ numerous optimizations. Intention Locks (IS, IX, SIX) enable hierarchical locking for multi-granularity, allowing a transaction to lock a table, page, or row efficiently. Before acquiring an S or X lock on a row, the transaction acquires intention locks on higher-level granules, allowing the lock manager to quickly check for conflicts at coarser levels without examining every row lock.

Lock escalation and de-escalation dynamically adjust granularity based on workload. If a transaction acquires too many fine-grained locks, the system escalates them to a coarser lock to save memory. Tree and DAG protocols exploit knowledge of access patterns, such as B-tree traversals, to release locks earlier than standard 2PL would allow while still guaranteeing serializability, significantly improving concurrency for index operations.

Real-World Applications

The two-phase locking algorithm is not merely an academic concept; it is the workhorse of concurrency control in virtually every major relational database management system. Its pessimistic nature makes it ideal for workloads where conflicts are common and the cost of aborting and retrying transactions is high.

In traditional RDBMS engines like IBM Db2, Oracle Database, Microsoft SQL Server, and MySQL's InnoDB storage engine, Strict 2PL is the default isolation mechanism for the SERIALIZABLE and REPEATABLE READ isolation levels. When a user executes BEGIN TRANSACTION, followed by SELECT ... FOR UPDATE or UPDATE statements, the engine acquires row-level exclusive locks that are held until COMMIT. This ensures that financial transactions, inventory management, and booking systems maintain perfect consistency even under thousands of concurrent connections. For example, an e-commerce platform processing orders will use 2PL to ensure that two customers cannot purchase the last item in stock simultaneously.

Beyond databases, 2PL principles appear in distributed systems and web infrastructure. Distributed lock managers in systems like Apache ZooKeeper, etcd, and Google's Chubby use 2PL-like protocols to coordinate access to shared configuration or to elect leaders. In operating systems, file system locks and semaphore-based resource allocation often follow two-phase discipline to prevent race conditions when multiple processes access shared files or devices. Even in modern cloud-native architectures, transactional key-value stores like Google Spanner and CockroachDB implement variations of 2PL combined with timestamp ordering to achieve external consistency across globally distributed nodes.

However, 2PL is less suitable for workloads with very high contention and long-running transactions, such as in-memory OLTP systems or collaborative editing applications. In those domains, optimistic concurrency control or multi-version concurrency control (MVCC) is often preferred because it allows readers to never block writers. Many modern databases actually combine 2PL for write-write conflicts with MVCC for read-write conflicts, offering snapshot isolation as a more concurrent alternative while still using 2PL internally for serializable transactions.

Comparison with Alternatives

While the two-phase locking algorithm is a cornerstone of pessimistic concurrency control, it is not the only approach to achieving serializability. Understanding its trade-offs relative to other protocols is essential for database engineers when selecting an isolation strategy for a specific workload.

Timestamp Ordering (TO) assigns each transaction a unique timestamp at start and ensures that conflicting operations are executed in timestamp order. Unlike 2PL, TO is non-blocking for reads in its basic form but may abort and restart transactions that arrive out of order. It is deadlock-free but can cause higher abort rates under contention. Multi-Version Concurrency Control (MVCC) maintains multiple versions of each data item, allowing readers to access a consistent snapshot without blocking writers. This dramatically improves read concurrency and is the basis for snapshot isolation in PostgreSQL and Oracle. However, MVCC requires garbage collection of old versions and snapshot isolation alone does not guarantee serializability without additional checks like SSI.

Optimistic Concurrency Control (OCC) assumes conflicts are rare and lets transactions execute without locking, validating at commit time whether any conflicts occurred. If validation fails, the transaction is aborted and retried. OCC excels in low-contention, read-heavy workloads with short transactions, offering high concurrency with minimal locking overhead, but it performs poorly under high contention where most transactions would abort. In contrast, 2PL's pessimistic blocking ensures that once a transaction acquires its locks, it will eventually commit without validation failure, making it more predictable for high-contention, write-heavy workloads.

The choice often comes down to workload characteristics. For systems requiring strict serializability with frequent writes and where aborts are expensive, Strict 2PL remains the gold standard. For read-heavy analytical workloads or web applications where responsiveness is critical, MVCC or OCC is preferred. Many modern HTAP systems actually offer both, allowing the application to choose per transaction.

Common Mistakes and Best Practices

Even though the two-phase locking algorithm is conceptually simple, incorrect implementation or usage can lead to subtle bugs, performance degradation, and deadlocks. Awareness of common pitfalls is crucial for both database users and engine developers.

One of the most frequent mistakes is violating the two-phase rule by acquiring a lock after releasing one. Application-level code that manually manages locks, or an ORM that releases a lock early to improve concurrency, can inadvertently break serializability. For example, a transaction that reads a value, releases its shared lock, then later decides to update the same value and re-acquires an exclusive lock is no longer 2PL compliant and may produce non-serializable schedules. The rule must be enforced by the lock manager, not left to application discipline. Always ensure that the transaction's lock point is well-defined and that no new lock requests are issued after the first unlock.

Another common pitfall is holding locks for too long, especially in Strict 2PL where exclusive locks are held until commit. Long-running transactions that perform user interaction, network calls, or heavy computation while holding locks will block many other transactions and create contention hot spots. Best practice is to keep transactions as short as possible, acquire locks as late as possible, and release shared locks as early as possible when not using Rigorous 2PL. Techniques like lock escalation should be monitored, as escalating many row locks to a table lock can unexpectedly block all concurrent access to the table.

Deadlock handling is often mishandled. A naive implementation that simply waits indefinitely will eventually freeze the system. Production systems must implement either deadlock detection with victim selection or deadlock prevention. When choosing a victim to abort, select the transaction that has done the least work, holds the fewest locks, or is youngest, to minimize wasted work. Additionally, always acquire locks in a consistent global order when possible. If all transactions lock resources in the same order, such as ordering by primary key, deadlocks can be largely avoided. Finally, be aware of lock upgrades: upgrading a shared lock to exclusive can cause deadlock if two transactions both hold shared locks and both try to upgrade. Use update locks or acquire exclusive locks upfront when a write is anticipated.

Best Practices Checklist

• Prefer Strict 2PL for most workloads to avoid cascading aborts and simplify recovery.
• Keep transactions short and avoid user input or external calls while holding locks.
• Access records in a consistent order to prevent deadlocks.
• Use appropriate lock granularity: row-level for high concurrency, table-level for bulk operations.
• Implement timeouts on lock waits to bound latency and provide fallback for deadlock detection.
• Monitor lock contention metrics and wait queue lengths to identify hot spots.
• Test under concurrent load, not just single-threaded execution, to expose race conditions.

Interview Questions

Understanding the two-phase locking algorithm is a frequent topic in database and backend engineering interviews. Below are common questions with concise, interview-ready answers.

1. What is the two-phase locking algorithm and why does it guarantee serializability?

2PL requires that every transaction has a growing phase where it can only acquire locks and a shrinking phase where it can only release locks, with no acquisitions after the first release. It guarantees conflict serializability because the lock point of each transaction, the moment it has acquired all its locks, defines a total order. If two transactions conflict on a data item, the one that acquires the lock first will have its lock point earlier, and all its conflicting operations will be ordered before the other's in the equivalent serial schedule. This prevents cycles in the precedence graph, ensuring serializability.

2. What is the difference between Basic, Strict, and Rigorous 2PL?

Basic 2PL allows locks to be released at any time after the lock point, which can lead to cascading aborts if a transaction reads uncommitted data that is later rolled back. Strict 2PL holds all exclusive locks until commit or abort, preventing dirty reads and cascading aborts while still allowing shared locks to be released early. Rigorous 2PL holds all locks, both shared and exclusive, until commit or abort, which ensures that commit order equals serializability order and simplifies recovery, but at the cost of lower concurrency. Most commercial databases use Strict 2PL as the default.

3. How does 2PL handle deadlocks? Explain Wait-Die and Wound-Wait.

2PL can deadlock when transactions wait for each other in a cycle. Two main approaches exist: detection and prevention. Detection builds a wait-for graph and periodically checks for cycles, aborting a victim when a cycle is found. Prevention schemes use timestamps to avoid cycles proactively. In Wait-Die, if an older transaction requests a lock held by a younger transaction, it waits; if a younger transaction requests a lock held by an older one, it dies and restarts. In Wound-Wait, if an older transaction requests a lock held by a younger one, it wounds the younger one, forcing it to abort; if a younger requests a lock held by older, it waits. Both are deadlock-free but differ in abort frequency.

4. Does 2PL guarantee freedom from cascading aborts or deadlocks?

No. Basic 2PL guarantees serializability but does not prevent cascading aborts or deadlocks. A transaction can read uncommitted data from another transaction that later aborts, forcing the reader to also abort. Deadlocks are inherent because transactions block waiting for locks. Strict and Rigorous 2PL prevent cascading aborts by holding exclusive locks until commit, but they still do not prevent deadlocks. Conservative 2PL, which pre-acquires all locks, is deadlock-free but is rarely used due to its impracticality.

5. Compare 2PL with Optimistic Concurrency Control. When would you choose one over the other?

2PL is pessimistic and blocks transactions on conflict, guaranteeing that a transaction that acquires its locks will commit without validation failure. It is ideal for high-contention, write-heavy workloads where aborts are expensive, such as banking. OCC is optimistic, lets transactions execute without locks, and validates at commit, aborting on conflict. It excels in low-contention, read-heavy workloads with short transactions where blocking would hurt throughput, such as web caches or in-memory OLTP. Choose 2PL when consistency and predictability under contention are paramount, and OCC when concurrency and low latency for reads are more important and conflicts are rare.