Two-Phase Locking and Distributed Serializability

The Two-Phase Locking Protocol

At its core, concurrency control aims to allow multiple transactions to execute simultaneously without violating correctness. The most intuitive way to prevent interference is by using locks. A transaction must acquire a lock on a data item before it can operate on it.

There are two basic lock modes:

• Shared (S) Lock: Allows a transaction to read an item. Multiple transactions can hold an S lock on the same item simultaneously.
• Exclusive (X) Lock: Allows a transaction to write (modify or delete) an item. Only one transaction can hold an X lock on an item, and it cannot coexist with any S locks.

Simply acquiring and releasing locks is not enough to guarantee serializability. If transactions can acquire and release locks in any order, anomalies can still occur. The Two-Phase Locking (2PL) protocol imposes a strict rule on the sequence of lock operations:

1. Growing Phase: A transaction can acquire locks but cannot release any.
2. Shrinking Phase: Once a transaction releases its first lock, it enters the shrinking phase. In this phase, it can only release locks; it cannot acquire any new ones.

This protocol ensures that the precedence graph of transactions is acyclic, which is the definition of conflict serializability. The point at which a transaction owns all its locks is called the "lock point," and the serial order of transactions is equivalent to the order of their lock points.

The following video provides an excellent introduction to the core concepts of locking and the 2PL protocol.

Strong Strict 2PL and Deadlocks

While 2PL guarantees serializability, the basic version has a significant practical problem: cascading aborts. A transaction might release its locks during the shrinking phase before it commits. If another transaction acquires those locks and reads the uncommitted data, it becomes dependent. If the first transaction then aborts, the second one must also be aborted, and so on. This can lead to a great deal of wasted work.

To solve this, most practical implementations use Strong Strict Two-Phase Locking (SS2PL). The rule is simple and much stricter: a transaction holds all its acquired locks until it has committed or aborted. This effectively eliminates the shrinking phase as a separate period of execution; all locks are released at once upon termination. This prevents any other transaction from reading uncommitted data, thus avoiding cascading aborts.

However, a fundamental problem with any locking scheme remains: deadlocks. A deadlock occurs when two or more transactions are waiting for each other to release locks. For example, T1 holds a lock on item A and requests a lock on B, while T2 holds a lock on B and requests a lock on A. Neither can proceed.

As the video explains, there are two main approaches to handling deadlocks:

1. Deadlock Detection

In this approach, the system allows deadlocks to occur but periodically checks for them.

• Waits-For Graph: The lock manager constructs a directed graph where nodes are transactions and an edge from T1 to T2 means T1 is waiting for a lock held by T2.
• Cycle Detection: A background thread periodically traverses the graph to find cycles. A cycle indicates a deadlock.
• Victim Selection: If a cycle is detected, the system must abort one of the transactions (the "victim") to break the cycle. Choosing the right victim is a non-trivial heuristic problem. A naive system might kill the newest transaction, but a sophisticated one might choose the one that has done the least work or the one whose termination would resolve the deadlock with minimal cascading impact.

2. Deadlock Prevention

This approach ensures deadlocks can never occur by imposing an ordering on lock requests. When a transaction T_i tries to acquire a lock held by T_j, the system uses their timestamps to decide what to do. Two common schemes are:

• Wait-Die (Older waits for Younger): If T_i has an earlier timestamp (is older) than T_j, T_i is allowed to wait. If T_i is younger, it "dies" (aborts) and is restarted.
• Wound-Wait (Older preempts Younger): If T_i is older, it "wounds" T_j (forces it to abort), releasing its locks. T_i can then get the lock. If T_i is younger, it waits for T_j. A restarted transaction typically retains its original timestamp to prevent starvation.

Deadlock prevention avoids the overhead of building and checking a waits-for graph but can lead to more transaction aborts than necessary. Deadlock detection is often preferred in general-purpose databases where deadlocks are relatively rare.

Locking Granularity and Intention Locks

So far, we've discussed locking abstract "items." In a real database, these items could be rows, pages, or entire tables. The choice of lock granularity presents a trade-off:

• Fine-grained locks (e.g., row-level): Maximizes concurrency, as two transactions can operate on different rows of the same table. However, it increases lock management overhead; a transaction updating millions of rows would need to acquire millions of locks.
• Coarse-grained locks (e.g., table-level): Minimizes lock overhead but severely limits concurrency. If one transaction locks a table, no other transaction can access any part of it.

To get the best of both worlds, databases use a lock hierarchy and a clever mechanism called intention locks. Before taking a fine-grained lock (like an S or X lock on a row), a transaction first places an "intention" lock on the coarser-grained ancestors in the hierarchy (e.g., the table and page).

• Intention Shared (IS): Signals an intent to place S locks on descendant nodes.
• Intention Exclusive (IX): Signals an intent to place X locks on descendant nodes.

IS and IX locks are compatible with each other. For example, two transactions can both hold an IX lock on a table, because they intend to lock different rows. However, a request for a coarse-grained X lock on the table would be denied because it's incompatible with the existing IX locks. This system allows the lock manager to quickly check for conflicts at a high level without having to inspect every fine-grained lock.

2PL in Distributed Systems: The Spanner Case

Now, let's bring this into the context of a distributed system like Spanner. As you know, Spanner uses Paxos for replication within each data shard (a Paxos group) and 2PC for transactions that span multiple shards. The missing piece of the puzzle is how concurrency is managed within each shard. This is where 2PL comes in.

For a transaction that needs to access data, it communicates with the leader of the Paxos group responsible for that shard. That leader acts as the lock manager for its data.

• For a read-write transaction, the client acquires locks from the leaders of all participating shards using 2PL. Once all locks are acquired, the 2PC protocol begins.
• The state of the 2PC protocol itself (e.g., "prepared," "committed") is written to the underlying Paxos state machine. This makes the coordinator fault-tolerant; if a leader fails, a new leader takes over, reads the 2PC state from the replicated log, and can continue the protocol.

This architecture is often described as 2PC and 2PL over Paxos leaders. It elegantly combines these three fundamental protocols: Paxos for fault-tolerant replication, 2PL for local concurrency control (ensuring serializability), and 2PC for atomic commitment across distributed components.

A Final Challenge: Phantom Reads

Even with strict row-level 2PL, a subtle anomaly can occur: the phantom read. Imagine a transaction that runs a query like SELECT COUNT(*) FROM Employees WHERE department_id = 10. While this transaction is running, another transaction inserts a new employee into department 10 and commits. If the first transaction reruns its query, it will see a different count—a "phantom" row has appeared.

This happens because the first transaction only locked the rows that existed when it first ran the query. It didn't lock the row that hadn't been inserted yet. The solution is to lock the predicate itself (WHERE department_id = 10).

• Predicate Locks: A conceptual solution where the lock applies to all objects matching a logical predicate. These are powerful but difficult to implement efficiently.
• Index-Range Locking: A practical implementation of predicate locking. Instead of locking the predicate, the database locks the corresponding range in the index. For our example, it would place a lock on the portion of the department_id index for the value 10, preventing any new insertions, updates, or deletions that would affect that range.

This video gives a great, concise explanation of the phantom problem and index-range locking.

Conclusion

In this lesson, we dissected Two-Phase Locking, the foundational protocol for providing serializability in databases. We've moved from the basic theory to the practical realities of its implementation in large-scale distributed systems.

Here are the key takeaways:

• Two-Phase Locking (2PL) guarantees conflict serializability by enforcing distinct growing and shrinking phases for lock acquisition and release.
• Strong Strict 2PL (SS2PL) is the de facto standard in real-world systems, as it prevents cascading aborts by holding all locks until a transaction terminates.
• Deadlocks are an inevitable side effect of locking and are handled via detection (with a waits-for graph) or prevention (e.g., Wound-Wait).
• Intention locks enable efficient multi-granularity locking, balancing concurrency with lock management overhead.
• In distributed databases like Spanner, 2PL is run on the leaders of consensus groups, working in tandem with protocols like 2PC to provide distributed, serializable transactions.
• Index-range locking is a practical solution to the phantom read problem, which standard row-level 2PL does not solve.

In our previous lesson, we saw how Spanner uses 2PC. In this lesson, we saw how it uses 2PL. In our next lesson, we will introduce the final, and most famous, ingredient: TrueTime. We will analyze how Spanner combines TrueTime, Paxos, and 2PL to implement externally consistent, globally distributed transactions, delivering the strongest consistency guarantee at a scale previously thought impossible.