Implementing S2PL with a Lock Manager

Two-Phase Locking (2PL): The Foundational Protocol

The first major protocol for using locks is called Two-Phase Locking (2PL). It's a simple but powerful idea that forces an ordering on conflicting transactions. The protocol divides a transaction's life into two distinct phases:

1. Growing Phase: The transaction can acquire any locks it needs (shared or exclusive). It cannot release any locks during this phase.
2. Shrinking Phase: After releasing its first lock, the transaction enters the shrinking phase. In this phase, it can only release locks; it is not allowed to acquire any new ones.

The point where the transaction acquires its final lock is called the "lock point." By ensuring that a transaction doesn't acquire new locks after it has started releasing old ones, 2PL guarantees that all schedules will be conflict-serializable.

The following video provides an excellent conceptual overview of these two phases.

The Problem with Basic 2PL: Cascading Aborts

While 2PL guarantees serializability, it has a significant practical drawback: it is susceptible to cascading aborts. This occurs when one transaction reads data that was modified by another transaction that has not yet committed.

Consider this scenario:

1. T1 acquires an exclusive lock on record A, writes a new value, and then releases the lock (entering its shrinking phase).
2. T2 acquires an exclusive lock on A, reads T1's uncommitted change, and continues its work.
3. Later, T1 decides to abort.

Because T2 read "dirty" data from T1, T2 must also be aborted to maintain consistency. If a third transaction, T3, had read data from T2, it would also need to abort, and so on. This chain reaction is a cascading abort, which wastes significant computational resources.

The next video clip explains this problem clearly.

Strict Two-Phase Locking (S2PL): The Practical Solution

To solve the problem of cascading aborts, nearly all commercial database systems use a more restrictive version of 2PL called Strict Two-Phase Locking (S2PL). The rule is even simpler than basic 2PL:

A transaction must hold all its exclusive locks until it commits or aborts.

In practice, most systems implement Strong Strict 2PL, which extends this rule to all locks (both shared and exclusive). This completely prevents cascading aborts because a transaction can never read or write data that another active transaction has modified. The "shrinking phase" is effectively reduced to a single atomic step at the very end of the transaction's life.

The following video offers a concise summary of S2PL and its benefits.

To see S2PL in action, let's look at the banking example from the video, comparing execution without 2PL to execution with S2PL.

Implementing S2PL: Integrating the Lock Manager

Now, let's focus on the main goal: implementing this. You've already designed the LockManager. How do we enforce the S2PL protocol?

This isn't done in the LockManager alone. It's a collaborative effort between the Transaction object, the TransactionManager, and the query Executors. The CMU project specs provide an excellent blueprint for how these components work together.

Based on this blueprint, here's how the implementation works:

1. Transaction State Management

The Transaction object itself must track its state. As described in the project spec, it will have states like GROWING, SHRINKING, COMMITTED, and ABORTED. It also maintains sets of the RIDs for which it holds shared and exclusive locks.

• A new transaction starts in the GROWING state.
• For basic 2PL: The first time Unlock() is called for a transaction, its state transitions to SHRINKING. Any subsequent attempt to acquire a lock while in the SHRINKING state must be rejected by the LockManager.
• For Strict 2PL: The rule is simpler. A transaction stays in the GROWING state for its entire active life. An explicit Unlock() call by an executor should be disallowed or simply not happen.

2. Integrating Locks into Query Executors

The components that actually access data—the query executors—are responsible for acquiring the necessary locks. Before an executor can read or modify a tuple, it must call the LockManager.

• SeqScanExecutor::Next(): Before returning a tuple, it must acquire a Shared Lock on the tuple's RID.
• UpdateExecutor::Next(): Before modifying a tuple, it must acquire an Exclusive Lock.
• InsertExecutor::Next(): Must acquire an Exclusive Lock on the RID of the new tuple it's creating.

Crucially, under S2PL, these executors never call Unlock(). They only acquire locks.

3. The Role of the Transaction Manager

The responsibility of releasing locks falls to the TransactionManager. When an application commits or aborts a transaction, the TransactionManager performs the final cleanup.

• TransactionManager::Commit(txn): After successfully committing the transaction's changes, this method iterates through the transaction's lock sets (shared_lock_set_ and exclusive_lock_set_) and calls LockManager::Unlock() for every lock held by the transaction.
• TransactionManager::Abort(txn): Similarly, when rolling back a transaction, this method must also release all of its locks to allow other transactions to proceed.

This division of responsibility is clean and effective. Executors handle acquisition, and the TransactionManager handles release, ensuring the S2PL protocol is followed correctly.

Conclusion

Today, you've bridged the gap between having a lock manager and having a correct concurrency control system. We've seen that a simple locking protocol can enforce serializability, and a slightly stricter version can make the system much more robust and efficient to manage.

Key Takeaways:

• Two-Phase Locking (2PL) guarantees conflict serializability by separating a transaction into a growing phase (acquiring locks) and a shrinking phase (releasing them).
• Basic 2PL suffers from cascading aborts, a practical problem where the failure of one transaction can force many others to roll back.
• Strict Two-Phase Locking (S2PL) solves this by requiring transactions to hold all exclusive (and typically shared) locks until they commit or abort. This is the de facto standard in most relational databases.
• Implementing S2PL involves a clear separation of concerns: query executors acquire locks, and the TransactionManager releases them upon transaction completion (commit or abort).

Preview of the Next Lesson

S2PL is highly effective, but it introduces a new problem. What happens if T1 is waiting for a lock held by T2, and T2 is waiting for a lock held by T1? Neither can proceed. This circular dependency is called a deadlock. In our next lesson, we will learn how to implement deadlock detection using a "waits-for" graph to identify these cycles and choose a victim transaction to abort, allowing the system to continue making progress.