CS186 笔记04

事务

是什么 (What it is)

事务是DBMS（数据库管理系统）中对应应用程序或者活动的一种抽象视图。
它是一系列对数据库对象进行读写操作的序列。
事务作为一个原子单位，其所有工作批次必须要么全部提交（完成），要么全部终止（回滚）。
从应用程序的角度来看，事务的结构始于 begin transaction，包含一系列SQL语句，并最终以 end transaction 结束。
事务管理器（Xact Manager）控制事务的执行。DBMS只关注从数据库中读取或写入的数据，不关心应用程序的程序逻辑。

为什么 (Why it's needed)

引入事务主要是为了解决并发操作带来的不一致性问题。如果没有事务，并发操作会带来以下具体问题：

不一致读 (Inconsistent Reads)：当一个事务正在修改数据时，另一个事务读取了部分修改后的数据和部分未修改的数据，导致读取到的数据是不一致的。这类似于Java并发编程中常见的数据不一致问题。例如，在转账场景中，如果T1从账户R扣除金额后、向账户S增加金额前中断，而此时T2读取了R和S的总和，T2会看到一个错误（较低）的总和。
丢失更新 (Lost Update)：当两个并发事务同时尝试更新同一个数据项时，一个事务的更新可能会被另一个事务的更新覆盖，导致其中一个更新“丢失”。例如，用户1将产品价格降低，同时用户2给产品打折，如果操作顺序不当，某个更新可能会被覆盖而失效。
脏读 (Dirty Reads)：一个事务读取了另一个尚未提交的事务写入的数据。如果这个尚未提交的事务最终回滚（中止），那么它对数据库的修改将不会生效，而读取了这些“脏”数据的事务基于不正确的数据做出了判断或修改，导致当前事务的结果与真实情况不一致。

怎么做 (How it works)

ACID 属性各自解决了什么问题？它们之间有什么关联？

A (Atomicity - 原子性)：
- 解决了什么问题：确保事务中的所有操作要么全部成功（提交），要么全部失败（中止/回滚）。它避免了部分完成的事务对数据库造成的不一致状态。例如，在转账过程中，如果系统在扣除了一个账户的钱但还没来得及增加另一个账户的钱时崩溃，原子性确保之前的扣款操作也会被撤销，从而避免资金“丢失”。
- 关联：与持久性 (Durability) 紧密相关。DBMS通常通过日志 (logging) 机制实现对失败事务的撤销操作（Undo）。
C (Consistency - 一致性)：
- 解决了什么问题：确保事务将数据库从一个一致的状态转换到另一个一致的状态。数据库的一致性通常通过一系列声明性完整性约束 (Integrity Constraints, ICs)，如 CREATE TABLE/ASSERTION 语句来表达。如果事务违反了这些约束，它将被中止。这保证了数据的有效性和合法性。
- 关联：是其他三个属性的最终目标。原子性、隔离性和持久性共同作用，以维护数据库的一致性。DBMS会自动检查的部分一致性（如完整性约束）由系统强制执行，而更复杂的应用层一致性则需要程序员通过事务逻辑来保证。
I (Isolation - 隔离性)：
- 解决了什么问题：确保并发执行的事务在彼此之间是隔离的，每个事务都感觉它好像是系统中唯一运行的事务。它解决了并发操作带来的不一致读、丢失更新、脏读等问题，使得用户和程序员无需考虑其他并发事务的影响。
- 关联：是并发控制的核心目标。通过并发控制机制（如两阶段锁）来实现，使得交错执行的事务的净效果必须等同于以某种串行顺序执行所有事务。
D (Durability - 持久性)：
- 解决了什么问题：确保一旦事务成功提交，其对数据库的修改就是永久性的，即使发生系统故障（如崩溃）也能存活下来。这保证了数据不会因为系统故障而丢失。
- 关联：与原子性 (Atomicity) 紧密相关。DBMS通常通过日志 (logging) 机制实现对已提交但尚未完全写入磁盘的事务的操作进行重做（Redo）。

为什么不能简单地串行执行所有事务？并发执行带来了什么好处？

是什么 (What it is)

简单地串行执行所有事务（即一次只运行一个事务）是安全的，但效率低下，性能会很差。
数据库管理系统（DBMS）必须交错执行事务的操作以获得更好的性能。

为什么 (Why it's needed)

并发执行带来了以下显著好处：

吞吐量 (Throughput - TPS，transactions per second)：
- 提高处理器/磁盘的利用率，从而完成更多的事务每秒。
- 在单核CPU系统中，当一个事务在进行磁盘读/写操作时，CPU可以被另一个事务使用，从而提高CPU利用率。
- 在多核CPU系统中，吞吐量理想情况下可以随着处理器数量的增加而扩展。
延迟 (Latency - response time per transaction，每个事务的响应时间)：
- 多个事务可以同时运行。
- 因此，一个事务的延迟不需要依赖于另一个不相关的事务，这有助于提高系统的响应速度。

什么是正确的并发执行？如何形式化定义这种正确性？

是什么 (What it is)

正确的并发执行指的是DBMS交错执行多个事务操作时，要确保两个事务不会“相互干扰”。每个事务执行起来都好像是独立运行的，并发访问不会影响事务的行为。最终效果必须等同于以某种串行顺序执行所有事务。

怎么做 (How it works)

事务调度 (Transaction Schedules)：
- 一个调度是来自一个或多个事务的数据操作序列。
- 操作包括：Begin (开始), Read (读), Write (写), Commit (提交) 和 Abort (中止)。
- 通常，调度只包含已提交的事务，并省略 Begin 和 Commit 操作。
串行调度 (Serial Schedule)：
- 每个事务从开始到结束运行，期间没有其他事务的任何干预操作。
- 这是正确行为的“试金石”概念。
等价性 (Equivalence)：
- 如果两个调度：
  - 涉及相同的事务。
  - 每个独立事务的操作顺序相同。
  - 都使数据库处于相同的最终状态。
- 则称这两个调度是等价的。
可串行化 (Serializability)：
- 调度S是可串行化的，如果S等价于某个串行调度。

为什么冲突可串行化是实际中更常用的标准，而不是视图可串行化？视图可串行化有什么优势和劣势？

是什么 (What it is)

冲突操作 (Conflicting Operations)：
- 两个操作（读/写）如果满足以下条件则冲突：
  - 它们由不同的事务执行。
  - 它们操作的是同一个数据对象。
  - 其中至少一个操作是写入操作。
- 非冲突操作的顺序对数据库的最终状态没有影响。
冲突可串行化 (Conflict Serializability)：
- 如果调度S能够通过交换非冲突的连续操作（来自不同事务）而转换为某个串行调度，则S是冲突可串行化的。
- 形式化定义：如果调度S与某个串行调度冲突等价，则S是冲突可串行化的。
- 冲突等价：两个调度如果满足以下条件则冲突等价：
  - 它们涉及相同的事务和相同的操作。
  - 所有冲突操作对的顺序在两个调度中都相同。

为什么 (Why it's needed)

冲突可串行化作为更常用的标准：
- 效率高：冲突可串行化更容易高效地实现和强制执行。它可以通过构建冲突依赖图 (Dependency Graph) 来判断，如果依赖图无环，则调度是冲突可串行化的。这是一种计算上相对简单的方法。
- 保守性：它提供了一个“保守”的正确性测试。这意味着所有冲突可串行化的调度都是可串行化的（真阳性），但它会排除一些实际上也是可串行化的调度（假阴性），从而牺牲了一部分并发性以换取更容易的正确性检查。
视图可串行化 (View Serializability) 的优势和劣势：
- 优势：
  - 允许更多并发：视图可串行化允许比冲突可串行化更多的调度，因为它允许所谓的“盲写”（blind writes）。这意味着它能识别出一些冲突可串行化无法识别的可串行化调度，从而可能实现更高的并发度。
- 劣势：
  - 难以高效强制执行：视图可串行化很难高效地在实践中强制执行。检查视图等价性要比检查冲突等价性复杂得多。
  - 无法理解语义：与冲突可串行化一样，视图可串行化也无法允许所有实际可串行化的调度，因为它们都不理解操作或数据的实际语义。

怎么做 (How it works)

冲突可串行化通常通过两阶段锁 (Two-Phase Locking - 2PL) 机制来实现。

两阶段锁 (Two-Phase Locking - 2PL) 的具体规则：
- 阶段一：增长阶段 (Growing Phase)：
  - 事务可以获得锁，但不能释放任何已持有的锁。
  - 当事务需要访问一个数据项时，如果该数据项没有被其他事务锁定，或者锁定的方式与当前事务请求的锁兼容（例如，多个事务可以同时持有读锁，但写锁是排他的），那么事务就可以获得锁。
- 阶段二：收缩阶段 (Shrinking Phase)：
  - 事务可以释放锁，但不能获得任何新的锁。
  - 一旦事务释放了任何一个锁，它就进入收缩阶段，此后不能再申请任何新的锁。
- 锁类型：通常使用共享锁（S锁，用于读操作）和排他锁（X锁，用于写操作）。
  - S锁（共享锁）：多个事务可以同时持有S锁。
  - X锁（排他锁）：只能由一个事务持有，且不能与其他任何锁（S锁或X锁）共存。
两阶段锁如何保证冲突可串行化：
- 2PL保证了事务的每个操作（读或写）都必须先获得相应的锁。
- 由于锁的排他性或兼容性，它确保了所有冲突操作（读-写、写-读、写-写）的顺序是明确的，并且一旦事务进入收缩阶段，它就固定了其对数据项的访问顺序，从而防止了导致非冲突可串行化的依赖循环。
如何避免死锁等问题：
- 虽然两阶段锁可以保证冲突可串行性，但它不能避免死锁。死锁是并发控制中一个常见的问题，当两个或多个事务互相等待对方释放资源时发生。
- 死锁的避免和处理策略：
  1. 死锁预防 (Deadlock Prevention)：
    - 核心思想：通过强制限制来阻止死锁条件的发生（如循环等待）。
    - 常见技术：
      - 资源排序：对所有资源（数据项）定义一个全局的加锁顺序。所有事务都必须严格按照这个预定义的顺序获取锁。这可以有效地消除循环等待（死锁的根本原因），但可能导致不必要的串行化，降低并发度，并且难以实现，特别是当事务无法预知所有需要的资源时。
      - 预先加锁：要求事务在开始执行之前就获取所有它可能需要的锁。这可以防止死锁，但同样不实用，因为事务通常无法预知所有将要访问的数据，而且会导致资源长时间被占用，降低并发度。
  2. 死锁避免 (Deadlock Avoidance)：
    - 核心思想：在运行时动态地检查资源分配，以确保不会出现死锁状态。通常基于事务的“年龄”或优先级来分配优先级。
    - 常见策略：
      - Wait-Die：如果请求锁的事务（Ti）比持有锁的事务（Tj）“老”（优先级更高），则Ti等待Tj释放锁；否则（Ti比Tj“年轻”），Ti立即中止（die）并回滚。
      - Wound-Wait：如果请求锁的事务（Ti）比持有锁的事务（Tj）“老”（优先级更高），则Ti“伤害”（wounds）Tj，导致Tj中止并释放锁；否则（Ti比Tj“年轻”），Ti等待Tj释放锁。
    - 优点：这些方案通过强制一个事务等待或中止来打破潜在的循环等待，从而保证无死锁。
    - 重要细节：如果一个事务被中止并重新启动，它必须保留其原始的时间戳（或优先级）。否则，一个“年轻”的事务可能会在反复中止后变得“老”起来，从而获得不公平的优势，导致“饥饿”问题。
  3. 死锁检测与解决 (Deadlock Detection and Resolution)：
    - 核心思想：允许死锁发生，但会周期性地检查系统是否存在死锁，一旦发现则选择一个事务作为“牺牲者”并中止它来打破死锁。
    - 机制：
      - 构建“等待图”（Waits-For Graph）：一个有向图，每个节点代表一个事务，如果事务Ti正在等待事务Tj释放锁，则存在一条从Ti到Tj的边。
      - 周期性检查循环：死锁检测器会定期检查等待图中是否存在循环。如果发现循环，则表示发生了死锁。
      - 选择牺牲者并中止：一旦检测到死锁，系统会选择循环中的一个或多个事务作为牺牲者，强制其中止并回滚，从而打破死锁循环。选择牺牲者的策略通常基于成本考虑（例如，回滚成本最小的事务）。
    - 经验事实：大多数死锁循环都比较小（通常是2-3个事务）。
  - 超时 (Timeouts)：
    - 许多系统简单地使用超时机制来处理死锁。如果一个事务等待锁的时间超过预设的阈值，系统就认为它可能陷入了死锁并强制其中止。
    - 优点：实现简单。
    - 缺点：不够精确，可能错误地中止没有死锁的事务，或者死锁发生后需要较长时间才能检测到。
    死锁检测示例：
```
初始状态：所有事务无锁，等待图为空。
1. T1请求S(A)并获得。T1请求S(D)并获得。
2. T2请求X(B)并获得。
3. T1请求S(B)。此时T2持有B的X锁，与T1请求的S(B)冲突，T1等待T2。等待图：T1 -> T2。
4. T3请求S(D)。T1持有D的S锁，S锁与S锁兼容，T3获得S(D)。
5. T3请求S(C)并获得。
6. T2请求X(C)。T3持有C的S锁，与T2请求的X(C)冲突，T2等待T3。等待图：T1 -> T2 -> T3。
7. T4请求X(B)。T2持有B的X锁，与T4请求的X(B)冲突，T4等待T2。等待图：T1 -> T2 -> T3, T4 -> T2。
8. T3请求X(A)。T1持有A的S锁，与T3请求的X(A)冲突，T3等待T1。等待图：T1 -> T2 -> T3 -> T1。
```
  检测结果：检测器发现循环 T1 -> T2 -> T3 -> T1。发生死锁。此时，T1、T2、T3都处于死锁状态，持有锁却无法继续。T4可能仍在正常执行。系统会周期性地提取等待图，发现循环，然后选择一个事务中止来打破死锁。

锁粒度 (Lock Granularity)

是什么 (What it is)

锁粒度是指数据库系统中锁定数据项的大小级别，例如可以是行 (Record/Tuple)、页 (Page)、表 (Table) 甚至整个数据库 (Database)。
选择合适的锁粒度是一个权衡问题：
- 细粒度锁 (Fine-grained locking)：锁定更小的数据单元（如行）。
  - 优势：更高的并发度，因为不同事务可以同时访问同一页或表中的不同行。
  - 劣势：管理和维护大量锁的开销更大（锁管理器需要维护更多的锁条目）。
- 粗粒度锁 (Coarse-grained locking)：锁定更大的数据单元（如表）。
  - 优势：管理锁的开销较小（锁管理器维护的锁条目更少）。
  - 劣势：并发度较低，因为即使只需要访问其中一小部分数据，整个大范围的数据也会被锁定，导致其他事务无法访问，造成并发损失。

怎么做 (How it works)

为了解决锁粒度的权衡问题，数据库系统引入了多粒度锁 (Multiple Granularity Locking - MGL)。

多粒度锁的理念：
- 允许数据项以各种大小存在，并定义一个数据粒度的层次结构，其中较小的粒度嵌套在较大的粒度中（例如：数据库 -> 表 -> 页 -> 记录）。
- 当一个事务显式地锁定层次结构中的某个节点时，它会隐式地以相同模式锁定该节点的所有后代。
层次结构示例：
- DB (数据库) 包含 T1, T2 (表)
- T1 包含 Pa, Pb, Pc (页)
- Pa 包含 ra1, ra2, ran (行)
意向锁模式 (Intention Lock Modes)：
- 为了实现多粒度锁，引入了额外的意向锁模式：
  - IS (Intent-to-Share)：意图在更细粒度级别上获取S锁（共享锁）。
  - IX (Intent-to-Exclusive)：意图在更细粒度级别上获取X锁（排他锁）。
  - SIX (Share with Intent-to-Exclusive)：同时持有S锁和IX锁。这在事务需要读取整个节点（如表）并同时修改其内部某些更细粒度数据时很有用。
- 作用：意向锁允许在不检查所有后代节点的情况下，对更高级别的节点（如表）进行S或X模式锁定。例如，如果一个事务想锁定一个页的X锁，它必须先在表上获得IX锁，这样其他事务就知道该表的某个部分正在被排他性修改。
多粒度锁协议：
1. 每个事务从层次结构的根节点开始获取锁。
2. 要在节点上获取S或IS锁，必须在其父节点上持有IS或IX锁。
3. 要在节点上获取X、IX或SIX锁，必须在其父节点上持有IX或SIX锁。
4. 锁必须以自下而上（从细粒度到粗粒度）的顺序释放。
5. 两阶段锁（2PL）和锁兼容性矩阵规则也同时强制执行。
- 正确性：该协议是正确的，因为它等价于直接在层次结构的最底层（叶子级别）设置锁。
实际的锁粒度示例（以MS SQL Server为例）：
- RID (Row Identifier)：行锁，用于锁定堆中的单行。
- KEY (键)：索引中的行锁，用于保护可串行化事务中的键范围。
- PAGE (页)：一个8KB的数据页或索引页。
- EXTENT (区)：八个连续页的组。
- HoBT (Heap or B-tree)：保护B树（索引）或没有聚集索引的表中的堆数据页的锁。
- TABLE (表)：整个表，包括所有数据和索引。
- FILE (文件)：数据库文件。
- APPLICATION (应用程序)：应用程序指定的资源。
- METADATA (元数据)：元数据锁。
- ALLOCATION_UNIT (分配单元)：一个分配单元。
- DATABASE (数据库)：整个数据库。

补充信息

索引 (Indexes) 的锁：
- 在B+树页面上直接使用2PL（常规的两阶段锁）是一个糟糕的主意，因为它会严重限制并发性，尤其是在B+树的根节点。
- 相反，数据库系统会使用巧妙的短锁 (latches) 机制。B+树的更高层级只需要正确地引导流量，而不需要严格的可串行化或2PL。
- 存在各种技巧来利用这一点，例如B-link树（一种优雅的设计）和针对内存数据库的Bw-tree（一种较新的变体）。
幻影 (Phantoms)：
- 幻影问题发生在当一个事务在执行两次相同的范围查询时，第二次查询返回了第一次查询时不存在的新行（这些行在两次查询之间被另一个事务插入）。这打破了串行化。
- 这个问题不能简单地通过元组级（行级）锁来解决，因为新插入的行在第一次查询时根本不存在，无法对其加锁。
- 解决方案是通过在索引中巧妙地设置锁，即所谓的 “临键锁”（next key locking） ，它能锁定一个范围，包括潜在的插入点。

CS186 笔记04 ​

事务 ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

ACID 属性各自解决了什么问题？ 它们之间有什么关联？ ​

为什么不能简单地串行执行所有事务？ 并发执行带来了什么好处？ ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

什么是正确的并发执行？ 如何形式化定义这种正确性？ ​

是什么 (What it is) ​

怎么做 (How it works) ​

为什么冲突可串行化是实际中更常用的标准，而不是视图可串行化？ 视图可串行化有什么优势和劣势？ ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

锁粒度 (Lock Granularity) ​

是什么 (What it is) ​

怎么做 (How it works) ​

补充信息 ​

CS186 笔记04

事务

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

ACID 属性各自解决了什么问题？它们之间有什么关联？

为什么不能简单地串行执行所有事务？并发执行带来了什么好处？

是什么 (What it is)

为什么 (Why it's needed)

什么是正确的并发执行？如何形式化定义这种正确性？

是什么 (What it is)

怎么做 (How it works)

为什么冲突可串行化是实际中更常用的标准，而不是视图可串行化？视图可串行化有什么优势和劣势？

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

锁粒度 (Lock Granularity)

是什么 (What it is)

怎么做 (How it works)

补充信息