Chapter 16 Two-Phase Locking

Review

Conflict Serializable

• Verify using either the "swapping" method or dependency graphs.
• Any DBMS that says that they support "serializable" isolation does this.

View Serializable

• No efficient way to verify.
• Andy doesn't know of any DBMS that supports this.
• Hence, we can ignore this.

We need a way to guarantee that all execution schedules are correct (i.e., serializable) without knowing the entire schedule ahead of time.

Solution: Use locks to protect database objects.

• Lock Types
• Two-Phase Locking
• Deadlock Detection + Prevention
• Hierarchical Locking

BASIC INFORMATION ABOUT LOCKS

LOCK TYPES

EXECUTING WITH LOCKS

We pursue the pattern like this:

1. Transactions request locks (or upgrades).
2. Lock manager grants or blocks requests.
3. Transactions release locks.
4. Lock manager updates its internal lock-table.
   • It keeps track of what transactions hold what locks and what transactions are waiting to acquire any locks.

But, it's obvioius that we need to be careful about how we use locks.

We can easily face this problem:

CONCURRENCY CONTROL PROTOCOL

Two-phase locking (2PL) is a concurrency control protocol that determines whether a txn can access an object in the database at runtime.

The protocol does not that a txn will execute need to know all the queries ahead of time.

我们今天所讲述的内容围绕2PL协议展开，因为在数据库的使用过程中不可能会始终了解所有线程的运行计划与时间，因此我们希望所有的线程遵循2PL协议，这样能够避免线程之间的各种冲突问题

TWO - PHASE LOCKING

INTRO

Phase #1: Growing

• Each txn requests the locks that it needs from the DBMS’s lock manager.

• The lock manager grants/denies lock requests.

Phase #2: Shrinking

• The txn is allowed to only release/downgrade locks that it previously acquired. It cannot acquire new locks.

Note

两阶段锁定协议（Two-Phase Locking, 2PL）是数据库管理系统（DBMS）中用来确保事务调度遵循串行化的协议。它分为两个阶段：增长阶段和收缩阶段。

阶段1：增长阶段 (Growing Phase)

• 请求锁（Requesting Locks）: 在这个阶段，事务会向数据库管理系统的锁管理器请求它所需要的所有锁。这些锁用于保护事务要读取或写入的数据。
• 锁管理器决定是否授予锁（Grant/Deny Locks）: 锁管理器根据当前系统中的锁状态，决定是否授予事务请求的锁。如果授予了锁，事务可以继续执行。如果不能授予锁，事务必须等待，直到锁可用。

阶段2：收缩阶段 (Shrinking Phase)

• 释放锁（Releasing Locks）: 在这个阶段，事务只能释放或降级它之前获得的锁，不能再获取新的锁。这意味着在事务开始释放锁之后，它就进入了收缩阶段，无法再对其他数据进行操作。

总结: 两阶段锁定协议的核心思想是，事务在增长阶段获取所有需要的锁，然后在收缩阶段释放锁。这种机制确保了在多个事务并发执行时，事务之间不会出现数据冲突或不一致的情况，有效防止了数据的竞争条件。

GRAPH

The txn is not allowed to acquire/upgrade locks after the growing phase finishes.

TWO - PHASE LOCKING

2PL on its own is sufficient to guarantee conflict serializability because it generates schedules whose precedence graph is acyclic.

2PL 本身足以保证冲突可串行化，因为它生成的调度的优先图是非循环的。

But it is subject to cascading aborts.

但它容易发生级联中止。

这张图描述了在两阶段锁定协议（2PL）中出现的级联回滚（Cascading Aborts）问题。

• 事务\(T_1\)和\(T_2\)正在执行。
• \(T_1\)获得了对象\(A\)和\(B\)的排他锁（X-LOCK）。
• \(T_1\)对\(A\)进行了读写操作，并在完成后释放了对\(A\)的锁。
• 此时，\(T_2\)开始执行，并尝试对\(A\)进行操作。因为\(T_1\)已经释放了锁，所以\(T_2\)可以获得\(A\)的锁，并对其进行读写操作。
• 但是，之后\(T_1\)发生了故障，被强制回滚（ABORT）。由于\(T_1\)的修改可能被泄露给了\(T_2\)，数据库管理系统必须回滚\(T_2\)以确保一致性。

问题：

级联回滚（Cascading Aborts）：当一个事务（如\(T_1\)）失败并回滚时，其他依赖其数据的事务（如\(T_2\)）也必须回滚。这会导致大量不必要的工作和性能损失。

主要原因：

-\(T_2\)依赖于\(T_1\)已提交但后来回滚的数据，这意味着\(T_2\)所做的工作可能基于不一致的状态，必须被回滚。

解决方法：

• 一种常见的解决方案是使用严格两阶段锁定协议（Strict 2PL），其中事务只有在完全提交之后才释放所有锁，这样可以避免级联回滚问题。

There are potential schedules that are serializable but would not be allowed by 2PL because locking limits concurrency.

• Most DBMSs prefer correctness before performance.

May still have "dirty reads".

• Solution: Strong Strict 2PL (aka Rigorous 2PL)

May lead to deadlocks.

• Solution: Detection or Prevention

STRONG STRICT TWO - PHASE LOCKING

\(Define\) (Strict)

A schedule is strict if a value written by a txn is not read or overwritten by other txns until that txn finishes.

Advantages:

• Does not incur cascading aborts.

• Aborted txns can be undone by just restoring original values of modified tuples.

2PL DEADLOCKS

May lead to deadlocks.

Solution: Detection or Prevention

A deadlock is a cycle of transactions waiting for locks to be released by each other.

Two ways of dealing with deadlocks:

1. Deadlock Detection
2. Deadlock Prevention

DEADLOCK DETECTION

The DBMS creates a waits-for graph to keep track of what locks each txn is waiting to acquire:

• Nodes are transactions
• Edge from \(T_i\) to \(T_j\) if \(T_i\) is waiting for \(T_j\) to release a lock.

The system periodically checks for cycles in waits-for graph and then decides how to break it.

DEADLOCK HANDLING

When the DBMS detects a deadlock, it will select a "victim" txn to rollback to break the cycle.

The victim txn will either restart or abort (more common) depending on how it was invoked.

There is a trade-off between the frequency of checking for deadlocks and how long txns wait before deadlocks are broken.

DEADLOCK HANDLING: VICTIM SELECTION

选择成为“受害者”的标准如下

Selecting the proper victim depends on a lot of different variables….

• By age (lowest timestamp)
• By progress (least/most queries executed)
• By the # of items already locked
• By the # of txns that we have to rollback with it

We also should consider the # of times a txn has been restarted in the past to prevent starvation.

DEADLOCK HANDLING: ROLLBACK LENGTH

After selecting a victim txn to abort, the DBMS can also decide on how far to rollback the txn's changes.

Approach #1: Completely

• Rollback entire txn and tell the application it was aborted.

Approach #2: Partial (Savepoints)

• DBMS rolls back a portion of a txn (to break deadlock) and then attempts to re-execute the undone queries.

Partial (Savepoints)方案如何知道回滚多少才合适

在处理死锁时，使用部分回滚（Partial Rollback 或 Savepoints）的方案的目的是在不完全终止事务的情况下，通过回滚到某个合适的保存点（Savepoint）来打破死锁，并尝试重新执行回滚的查询。为了确定回滚多少才合适，DBMS 会根据以下几种方法来判断：

1. 识别死锁循环中的关键操作：

   • 循环检测：DBMS 可以通过死锁检测算法（如等待图）找到死锁循环中导致死锁的关键操作。例如，事务 A 持有锁 X 并等待锁 Y，而事务 B 持有锁 Y 并等待锁 X。
   • 最小影响回滚：DBMS 可以选择 回滚到一个保存点 ，在这个保存点之后发生了导致死锁的操作。例如，事务 A 持有锁 X 后，又发起了对锁 Y 的请求导致死锁。DBMS 可以选择回滚到持有锁 X 之前的保存点，并重新尝试获取锁 X 和 Y，从而打破死锁。

2. 保存点策略：

   • 预定义保存点：在 事务执行过程中，DBMS 可能会在特定位置创建多个保存点。DBMS 可以根据事务的执行顺序和锁请求的顺序选择最近的一个保存点进行回滚。
   • 动态保存点：有时，DBMS 可能会根据检测到的死锁情况动态创建保存点，回滚到某个动态生成的保存点。

3. 估算回滚代价与重试成功率：

   • 回滚代价：DBMS 可能会考虑回滚的代价，比如回滚后需要重新执行的操作数。如果回滚代价较低，DBMS 可能会选择回滚更多的操作，以确保重新执行时能够成功获取必要的锁。
   • 重试成功率：DBMS 还可能考虑重新执行的成功率。如果回滚到某个保存点后，重新执行操作很可能再次导致死锁，DBMS 可能会选择更深的回滚来避免同样的问题再次发生。

4. 事务优先级与重要性：

   • 事务的优先级：如果涉及到多个事务，DBMS 可能会根据事务的优先级来决定回滚多少。例如，高优先级的事务可能会回滚较少的操作，而低优先级的事务可能会回滚更多操作以打破死锁。
   • 部分回滚后的重要性：回滚多少还可能取决于事务的重要性和被回滚部分的作用。如果回滚会导致丢失重要操作，DBMS 可能会选择更谨慎的回滚。

5. 锁争用的历史与趋势：

   • 历史记录：DBMS 可能会分析事务之间的锁争用历史记录，判断哪些保存点是更好的回滚点。
   • 趋势分析：DBMS 还可能根据事务的执行趋势，推测未来可能发生的锁争用情况，从而决定回滚到哪个保存点最合适。

部分回滚（Partial Rollback）通过动态调整回滚的深度，结合对死锁循环、保存点、回滚代价、事务优先级等因素的考虑，来打破死锁并尽可能减少对事务执行的影响。

DEADLOCK PREVENTION

Assign priorities based on timestamps:

Older Timestamp = Higher Priority (e.g., T 1 > T2 )

这里的timestamp指的是 线程T启动的时间，越早启动的线程，其timestamp越小，优先级越高。

Wait-Die ("Old Waits for Young")

• If requesting txn has higher priority than holding txn, then requesting txn waits for holding txn.
• Otherwise requesting txn aborts.

Wound-Wait ("Young Waits for Old")

• If requesting txn has higher priority than holding txn, then holding txn aborts and releases lock.
• Otherwise requesting txn waits.

Note

Wait-Die 和 Wound-Wait 是两种经典的死锁预防策略，基于事务的优先级来决定如何处理事务之间的锁请求冲突。它们的主要目标是避免死锁的发生，而不是在死锁发生后进行处理。两种策略的区别在于对高优先级和低优先级事务之间的处理方式。以下是详细解释：

1. Wait-Die（等待-死亡）策略：

原理：

• 优先级机制：事务的优先级基于其时间戳，时间戳越早，优先级越高。例如，事务 \(T_1\) 时间戳早于 \(T_2\)，则 \(T_1\) 优先级高于 \(T_2\)。
• 处理方式：
  • 如果请求锁的事务（称为请求事务）优先级高于持有锁的事务（称为持有事务），那么请求事务会等待持有事务释放锁。
  • 如果请求事务优先级低于持有事务，则请求事务会主动放弃（即被终止），然后回滚并重新尝试。

具体情况：

• 高优先级事务等待：假设 \(T_1\)（高优先级）请求的资源被 \(T_2\)（低优先级）持有，那么 \(T_1\) 会等待 \(T_2\) 释放资源。
• 低优先级事务终止：如果 \(T_2\)（低优先级）请求的资源被 \(T_1\)（高优先级）持有，那么 \(T_2\) 会被终止，然后回滚。

效果：

• Wait-Die 策略有效避免了死锁，因为在任何一个冲突中，优先级低的事务要么等待（如果它是持有事务），要么终止（如果它是请求事务），而不会导致循环等待。

• Wound-Wait（受伤-等待）策略：

原理：

• 优先级机制：同样，事务的优先级基于其时间戳，时间戳越早，优先级越高。
• 处理方式：
  • 如果请求事务优先级高于持有事务，则持有事务会被强制终止（"受伤"），从而释放锁资源，供高优先级的请求事务使用。
  • 如果请求事务优先级低于持有事务，则请求事务会等待。

具体情况：

• 低优先级事务等待：假设 \(T_2\)（低优先级）请求的资源被 \(T_1\)（高优先级）持有，那么 \(T_2\) 会等待 \(T_1\) 释放资源。
• 高优先级事务强制终止低优先级事务：如果 \(T_1\)（高优先级）请求的资源被 \(T_2\)（低优先级）持有，那么 \(T_2\) 会被强制终止，释放资源给 \(T_1\)。

效果：

• Wound-Wait 策略也避免了死锁，但不同于 Wait-Die，它强制终止低优先级的事务来确保高优先级事务能够顺利完成。这种方法通常会导致低优先级事务更频繁地被终止，但能确保高优先级事务的顺利执行。

总结与比较：

• Wait-Die 更倾向于保护低优先级事务，它们不会被高优先级事务强制终止，而是选择等待或者回滚。
• Wound-Wait 更倾向于保护高优先级事务，确保它们不被低优先级事务阻塞，通过强制终止低优先级事务来避免死锁。

两种策略都有效防止死锁，但它们在处理冲突的方式上有所不同，Wait-Die 更保守，Wound-Wait 更激进。选择哪种策略通常取决于系统的设计目标以及事务之间的优先级分配策略。

HIERARCHICAL LOCKING

LOCK GRANULARITIES

锁的粒度

All these examples have a one-to-one mapping from database objects to locks.

If a txn wants to update one billion tuples, then it must acquire one billion locks.

Acquiring locks is a more expensive operation than acquiring a latch even if that lock is available.

When a txn wants to acquire a "lock", can decide the granularity (i.e., scope)

• Attribute? Tuple? Page? Table?

The DBMS should ideally obtain fewest number locks that a txn needs.

Trade-off between parallelism versus overhead.

• Fewer Locks, Larger Granularity Granularity vs. More Locks, Smaller Granularity

We usually use Table-level and Tuple-level locks

INTENTION LOCKS

An intention lock allows a higher-level node to be locked in shared or exclusive mode without having to check all descendent nodes.

If a node is locked in an intention mode, then some txn is doing explicit locking at a lower level in the tree.

Intention-Shared (IS)

Indicates explicit locking at lower level with shared locks.

Intention-Exclusive (IX)

Indicates explicit locking at lower level with exclusive locks.

Shared+Intention-Exclusive (SIX)

The subtree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks.

在数据库系统中，意向锁（Intention Lock，简称IL）是一种锁的机制，用于优化多粒度锁定（多层次对象锁定，如表、页、记录等）时的性能，并确保并发操作的安全性。

背景：

在数据库系统中，经常需要对不同粒度的资源进行锁定。例如，可能需要锁定一个表中的单个记录，也可能需要锁定整个表。

为了支持这种多粒度锁定，数据库引入了意向锁的概念，以避免在对高层次资源（如表）进行锁定时必须检查所有低层次资源（如记录）的锁定状态。

意向锁的核心概念：

• 意向锁的作用：它允许在高层次节点（例如表）上施加共享锁或排他锁，而无需遍历所有的子节点（例如表中的所有记录）来检查这些子节点是否已经被锁定。
• 锁的类型：
• 意向共享锁（Intention Shared Lock, IS）：表示事务打算对某些更低层次的节点加共享锁（S）。
• 意向排他锁（Intention Exclusive Lock, IX）：表示事务打算对某些更低层次的节点加排他锁（X）。

具体解释：

1. 高层次节点加锁时的挑战：当一个事务希望对一个高层次的节点（如表）加锁（例如想要对整个表进行排他锁定），如果没有意向锁机制，它必须首先检查这个高层次节点下的所有低层次节点（如表中的每一条记录）是否被锁定。如果有任何低层次节点已经被加锁，尤其是与高层次节点的锁定冲突，那么高层次节点无法被锁定。
2. 意向锁的引入：为了避免上述遍历检查，数据库系统引入了意向锁。如果事务在某个高层次节点（如表）上发现了意向锁（例如意向共享锁 IS 或意向排他锁 IX），那么这个事务就知道有其他事务在低层次节点（如记录）上已经施加了锁定。
3. 意向锁的使用：
4. 如果某个事务需要对表中的某条记录进行操作，它会首先在高层次节点（如表）上加一个意向锁（如 IS 或 IX）。
5. 其他事务在尝试对这个高层次节点（如表）加共享或排他锁时，会首先检查是否存在意向锁。如果存在，则表明低层次的节点（如记录）上已经有锁定操作，该事务就可以决定是否继续进行锁定操作。

总结：

1. 意向锁的主要意义在于提高了多粒度锁定机制的效率。它允许事务在高层次节点上加锁时，不必检查所有子节点的锁定状态。这种机制保证了系统能够安全地并发操作，同时避免了不必要的性能开销。
2. 简单来说，意向锁告诉数据库“有事务在低层次节点上施加了显式锁定操作”，从而在更高层次的节点上做出合适的锁定决策。

LOCKING PROTOCOL

Each txn obtains appropriate lock at highest level of the database hierarchy.

• To get S or IS lock on a node, the txn must hold at least IS on parent node.
• To get X, IX, or SIX on a node, must hold at least IX on parent node.

# You can understand these rules by hierarchical tree in Compilers
IS -> IS | S | EMPTY
IX -> IX | X | SIX | EMPTY

Note

在数据库系统的多粒度锁定机制中，Intention-Shared (IS)、Intention-Exclusive (IX) 和 Shared+Intention-Exclusive (SIX) 是三种不同的锁类型，用于优化多层次对象（如表、页、记录等）锁定时的并发控制和性能。下面详细解释每种锁的含义：

1. Intention-Shared (IS) 锁
   • 含义：IS锁表示某个事务在更低层次的节点（例如表中的记录）上打算加共享锁（Shared Lock, S）。
   • 用途：当事务需要对某个表中的记录加共享锁时，它会先在表这个高层次节点上加一个IS锁，表明它在低层次节点（例如表中的具体记录）上进行共享锁定。这种锁定通知其他事务，该事务在低层次节点上执行了共享锁定操作，但允许其他事务在高层次节点上进行并发的共享锁定。
   • 例子：如果一个事务需要读取表中的某条记录而不会修改它，事务首先在表上加IS锁，然后在记录上加共享锁（S锁）。
2. Intention-Exclusive (IX) 锁
   • 含义：IX锁表示某个事务在更低层次的节点上打算加排他锁（Exclusive Lock, X）。
   • 用途：当事务需要对某个表中的记录加排他锁时，它会先在表这个高层次节点上加一个IX锁，表明它在低层次节点（例如表中的具体记录）上进行排他锁定。IX锁允许其他事务在高层次节点上进行并发的意向锁定，但不允许在高层次节点上加共享锁（S锁）或排他锁（X锁）。
   • 例子：如果一个事务需要修改表中的某条记录，事务首先在表上加IX锁，然后在记录上加排他锁（X锁）。
3. Shared+Intention-Exclusive (SIX) 锁
   • 含义：SIX锁是IS锁和S锁的组合。这意味着：
   • 该节点（例如表）及其子树（例如表中的所有记录）在共享模式下被锁定，即其他事务可以读取但不能修改这些数据。
   • 该事务还计划在更低层次的节点（例如表中的某些记录）上进行排他锁定（加X锁）。
   • 用途：SIX锁用来优化锁定开销。如果事务想要在一个子树（例如整个表）上加共享锁，同时在这个子树的某些子节点（如表中的某些记录）上进行修改操作，SIX锁可以避免对每一个子节点单独加共享锁，而是直接在高层次节点上加SIX锁，表示该节点已经被共享锁定，但某些子节点上仍会加排他锁。
   • 例子：如果一个事务需要读取整个表的大部分数据（需要共享锁S），并且还要修改其中的部分记录（需要排他锁X），它会在表上加SIX锁。这样，在读取数据时加S锁的同时，也允许在某些记录上加X锁进行修改。

总结：

• IS锁：表示事务将在低层次节点加共享锁。
• IX锁：表示事务将在低层次节点加排他锁。
• SIX锁：表示高层次节点已经被共享锁定，且事务将在低层次节点加排他锁。

Hierarchical locks are useful in practice as each txn only needs a few locks.

Intention locks help improve concurrency:

• Intention-Shared (IS): Intent to get S lock(s) at finer granularity.
• Intention-Exclusive (IX): Intent to get X lock(s) at finer granularity.
• Shared + Intention-Exclusive (SIX): Like S and IX at the same time.

LOCK ESCALATION

escalation 升级

The DBMS can automatically switch to coarser-grained locks（粗粒度锁） when a txn acquires too many low-level locks.

This reduces the number of requests that the lock manager must process.