MVCC

    2573 字
    最后修改于

    15-445/645 Database Systems (Fall 2022) - Lecture Notes - 18 Multi-Version Concurrency Control (cmu.edu)
    多版本并发控制是比事务并发控制协议更大的概念范围。包含了 DBMS 设计与实现的所有层面，MVCC 是使用最广泛的模式，几乎过去十年的所有新的 DBMS 实现都使用了 MVCC。在一些不支持多语句事务的系统中（如 NoSQL），也会使用 MVCC。
    通过 MVCC，DBMS 维护单个逻辑对象的多个物理版本。当事务写入对象时，DBMS 会创建该对象的新版本。当事务读取对象时，它会读取事务启动时存在的最新版本。

    MVCC 的基本概念 / 好处是读写操作不会相互阻塞。这意味着一个事务可以修改对象，而其他事务可以读取旧版本。但是两个事务同时修改同一个对象的操作仍然会出现阻塞，因为与目标对象相关的版本上仍然存在锁。

    使用 MVCC 的一个优点是，只读事务可以在不需要任何锁的情况下持有一份数据库的一致快照。
    此外，具有多版本支持的 DBMS 可以轻松支持时间旅行查询。这些查询基于数据库在其他某个时间点的状态（例如，对数据库执行 3 小时前的查询）。

    典型的基于 MVCC 的数据库设计将：

    1. 有一个版本控制存储，用于存储同一逻辑对象的不同版本。
    2. 当事务开始时，DBMS 会拍摄数据库的快照（通过复制事务状态表）。
    3. DBMS 使用快照来确定哪些版本的对象对事务可见。

    有五个重要的 MVCC 设计决策：

    1. 并发控制协议
      1. 时间序列 T/O
      2. 乐观并发控制 OCC
      3. 两阶段锁协议 2PL
    2. 版本存储
    3. 垃圾回收
    4. 索引管理
    5. 删除
      并发协议的选择是在前面讲座中讨论的方法（两阶段锁定、时间戳排序、乐观并发控制）之间选择的。

    快照隔离 (SI)
    SI 容易受到写入偏差异常的影响。
    写偏移异常：
    两个事务同时更新。
    TX1: update set color='white' where color = 'black'
    TX2: update set color='black' where color = 'white'
    最终导致下图这样的问题。

    而期望的状态是这样的。

    快照隔离涉及在事务启动时为事务提供一致的数据库快照。快照中的数据值仅包含已提交事务中的值，并且事务在完成之前与其他事务完全隔离。这对于只读事务来说是理想的选择，因为它们不需要等待来自其他事务的写入。写入维护在事务的专用工作区中，或与事务元数据一起写入存储，并且仅在事务成功提交后才对数据库可见。

    写入冲突
    如果两个事务更新同一个对象，则第一个写入器获胜。
    当两个并发事务修改不同的对象时，可能会发生写入偏差异常，从而导致不可序列化的计划。例如，如果一个事务将所有白色弹珠更改为黑色，而另一个事务将所有黑色弹珠更改为白色，则结果可能与任何可序列化计划不对应。

    版本存储
    这是 DBMS 存储逻辑对象的不同物理版本的方式，以及事务如何找到它们可见的最新版本。
    DBMS 使用元组的指针字段为每个逻辑元组创建版本链，该版本链本质上是按时间戳排序的版本链。
    这允许 DBMS 查找在运行时对特定事务可见的版本。索引始终指向链的 “头部”，该 “头部” 是最新或最旧的版本，具体取决于实现。线程遍历链，直到找到正确的版本。
    不同的存储方案决定了每个版本的存储位置 / 内容。

    方法 #1：仅追加存储
    逻辑元组的所有物理版本都存储在同一个表空间中。版本在表中混合在一起，每次更新只是将元组的新版本追加到表中并更新版本链。链可以按从旧到最新的 （O2N） 排序，这需要在查找时进行链遍历，也可以按从新到旧的排序 （N2O），这需要为每个新版本更新索引指针。


    方法 #2：时间旅行存储 DBMS 维护一个单独的表，称为时间旅行表，用于存储旧版本的元组。每次更新时，DBMS 都会将旧版本的元组复制到时间旅行表中，并使用新数据覆盖主表中的元组。主表中的元组指针指向时间旅行表中的过去版本。


    方法 #3：增量存储 与时间旅行存储类似，但 DBMS 只存储增量，或元组之间的变化，而不是整个过去的元组，即所谓的增量存储段。然后，事务可以通过以相反的顺序循环访问增量并应用它们来重新创建旧版本。这导致写入速度比时间旅行存储更快，但读取速度更慢。



    版本链排序：
    从旧到新，将新版本添加到链尾，查找时需要遍历链。
    从新到旧，将新版本添加到链头，对个新版本都需要更新索引指针。

    GC
    随着时间推移，DBMS 需要从数据库中删除可回收的物理版本。如果某个版本没有活动事务可以 “看到” 该版本，或者该版本是由已中止的事务创建的，则该版本是可回收的。
    要考虑如何查找过期版本，如何决定何时可以安全地回收内存？

    方法 #1：元组级 GC 使用元组级垃圾回收，DBMS 通过直接检查元组来查找旧版本。
    有两种方法可以实现此目的：
    ・后台清空：单独的线程定期扫描表并查找可回收版本。这适用于任何版本的存储方案。一个简单的优化是维护一个 “脏页面位图”，它跟踪自上次扫描以来修改了哪些页面。这允许线程跳过未更改的页面。
    ・协作清理：工作线程在遍历版本链时识别可回收版本。这仅适用于 O2N 链。如果不访问数据，则永远不会清除数据。

    方法 #2：事务级 GC 使用事务级垃圾回收，每个事务都负责跟踪自己的旧版本，因此 DBMS 不必扫描元组。每个事务都维护自己的读 / 写集。当事务完成时，垃圾回收器可以使用它来标识要回收的元组。DBMS 确定已完成的事务创建的所有版本何时不再可见。

    索引管理
    所有主键 （pkey） 索引始终指向版本链的链头。DBMS 更新 pkey 索引的频率取决于系统在更新元组时是否创建新版本。如果事务更新了 pkey 属性，则将其视为 一次 DELETE + INSERT。管理二级索引更为复杂。有两种方法可以处理它们。

    方法 #1：逻辑指针 DBMS 使用每个元组的固定标识符，该标识符不会更改。这需要一个额外的间接层，用于将逻辑 ID 映射到元组的物理位置。然后，对元组的更新可以只更新间接层中的映射。

    方法 #2：物理指针 DBMS 使用版本链头的物理地址。这需要在更新版本链头时更新每个索引，这可能非常昂贵。MVCC DBMS 索引（通常）不存储有关元组及其键的版本信息。相反，每个索引都必须支持来自不同快照的重复键，因为相同的键可能指向不同快照中的不同逻辑元组。MVCC 重复键问题描述了当多个事务需要同一逻辑元组的多个版本时，需要在 MVCC DBMS 索引中支持重复键。例如，假设 TXN 1 指向逻辑元组的版本 0，而 TXN 2 创建同一逻辑元组的版本 1。我们的索引需要指向两个 TXN 的两个版本，以便每个交易始终可以访问正确的版本。工作人员可能会为一次提取取回多个条目，然后他们必须按照指针找到正确的物理版本。

    删除

    仅当逻辑上删除的元组的所有版本都不可见时，DBMS 才会从数据库中物理删除元组。如果已删除元组，则在最新版本之后不能有该元组的新版本。这意味着没有写入冲突，第一个写入者获胜。我们需要一种方法来表示元组在某个时间点已被逻辑删除。有两种方法可以做到这一点。
    方法 #1：删除标志 维护一个标志，以指示在最新的物理版本之后已删除逻辑元组。这可以位于元组标头中，也可以位于单独的列中。
    方法 #2：逻辑删除元组 创建一个空的物理版本，以指示删除逻辑元组。对逻辑删除元组使用单独的池，在版本链指针中只有一个特殊的位模式，以减少存储开销

    • 🥳0
    • 👍0
    • 💩0
    • 🤩0