MIT 6.830 数据库实验 Lab 4 实验报告

发表于 更新于 分类于 ， 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 6 分钟

摘要

本次 Lab 主要实现的数据库的事务功能，包含并发控制、死锁检测等。本 Lab 要求实现一个页面粒度的锁管理器，支持多事务的并发，且使用等待图完成死锁的检测。

理论知识

事务是一个包含多个操作的序列，应当被原子化地执行，其具有以下 ACID 特性：

  • 原子性（Atomicity:）：事务中的操作要么都被执行，要么都不被执行。
  • 一致性（Consistency）：数据库是执行事务前是一致的，在执行事务后依然是一致的。
  • 隔离性（Isolation）：每个事务的执行与其他事务隔离。实际上 DBMS （数据库管理系统）会在多个事务间交叉执行，并不会按顺序一个个执行，但 DBMS 会保证每个事务看起来是隔离执行的，隐藏了并发的细节。
  • 持久性（Durability）：如果事务提交到数据库，结果会持久存在，即使刚提交 DBMS 就崩溃了也一样。

事务管理器包含以下两个模块：

  • 锁管理器：使用共享锁、排它锁、意向锁等实现事务间访问的并发控制
  • 日志和恢复：当事务需要回滚时，逐步地撤销事务已完成的操作

严格两阶段锁

为了保证事务的 ACID 特性，DBMS 使用严格两阶段锁（Strict Two Phase Locking）来完成事务的锁管理，该方法具有以下特点：

  • 每个资源有一个共享锁（S，Shared）和排它锁（Exclusive，X）。
    • 至多一个事务可以持有该资源的排它锁，但是很多其他事务可以持有其的共享锁。
  • 事务在读之前必须获得排它锁，在写之前必须获得共享锁
  • 事务在释放任何锁之后都无法获得新锁。这是保证可串行性的关键。
  • 严格两阶段锁特性：事务在结束前统一释放锁，而非在过程中逐个释放锁。

最后一点是为了避免级联回滚的问题。级联回滚意味着回滚一个事务会要求回滚另一个事务。考虑下面的场景

  1. T1 先读、写了 R，但是还没有提交到 DBMS
  2. T2 后读、写了 R

这时，要回滚 T1，必须回滚 T2，因为 T2 读的是 T1 写后的数据，如果 T1 回滚了，就不存在 T2 读的数据了，即脏数据。

死锁

当事务间存在资源的循环等待，满足死锁条件时，就会发生死锁。在操作系统上，通常有以下三种方法处理死锁：

  • 预防。按照指定的顺序请求资源，例如静态指定顺序，打破循环等待条件。
  • 避免。分配时预测是否可能出现死锁。
  • 检测和处理。周期性检测是否有死锁，并处理

也有一些数据库系统，直接不作处理。如果事务超时了就猜测发生了死锁，直接中止回滚。但这也会误伤真的需要很久才能计算出结果的事务，不提倡。

DBMS 广泛使用的是基于等待图的死锁检测。一个后台进程周期性地构建事务间的依赖图，当依赖图存在环时，就出现了死锁的循环等待条件，即出现了死锁。这种情况下就需要中止某个环内的事务打破循环，可以根据某些指标确定优先级，例如事务的持续时间、持有锁的数量等。

意向锁

锁的粒度需要同时考虑并发性能和管理成本。考虑极端情况：

  • 只使用一个锁，锁住整个数据库，很简单，但是不能并行
  • 对每个元组上锁，可以很好的并发，但是锁太多，需要庞大的内存开销，锁管理的负载也会很大

因此，需要折中：

  • 细粒度的锁有利于并发
  • 少数的锁方便管理

多粒度加锁可以较好地折中，其思想是： - 不应该为所有的事务设置相同的锁粒度 - 允许数据可变规模 - 定义一个加锁的层级，高层包含低层 - 可以表示为一棵树

当对底层的元组或者页面加共享锁 / 排他锁时，需要相应的为高层页面加意向共享锁和意向排他锁。意向锁的设计允许高层节点进行 S 和 X 加锁时，无需检查所有的底层节点。如果没有意向锁，需要遍历所有底层节点才能知道能否给这个节点加锁。

Exercise

LockManager

该 Exercise 要求实现 BufferPool 中的读页面请求锁、释放锁等功能，指导书要求在页面层级管理锁，不能直接在表层级加锁。指导书建议使用一个 LockManager 类来管理所有的锁，我先介绍下我对这个类的设计。先从简单的资源抽象开始，一个资源应该由一个唯一键标识，例如 Page 有 PageId，Tuple 有 RecordId。因此，LockManager 实际是维护了一个资源 - 锁的 Map，资源是任意类型的 Object。而锁对象（LockItem），应该包含以下属性：持有锁的事务，当前锁的类型。当一个加锁请求（资源，锁类型，事务）到达锁管理器时：

  1. 先获取资源的 LockItem
  2. LockItem 内，同步地判断能否完成这次加锁
    • 若可以（锁无事务持有，或类型兼容，或可以直接升级锁），则加锁返回
    • 否则，阻塞在 LockItem 对象上，等待其他事务释放锁后将其唤醒

当释放锁请求到达锁管理器时：

  1. 先获取资源的 LockItem
  2. LockItem 内，同步地释放锁，并 notifyAll 其他阻塞线程

在设计上，LockManager 应当遵循单例模式。我查阅了 JAVA 实现单例模式的几种方法，最优雅的就是使用枚举类。JAVA 保证了枚举类型的每个值都有唯一实例，进而可以简洁优雅、线程安全的实现单例模式。

Lock Lifetime

该 Exercise 要实现严格两阶段的锁生命周期：逐个地申请锁，只有在事务结束时才可以统一释放锁。锁的申请上，可以直接在 BufferPool.getPage 中进行申请，遵循一个即用即申的模式。

锁的释放上，正常应该在调用 BufferPool.transactionComplete 方法时，统一地释放所有锁。但会有些特殊情况，例如在插入元组的时候，扫到了一个页面没有空槽，这种情况下其实可以释放共享锁了。这看起来跟严格两阶段锁是违背的，但是实际上并不影响，因为插入元组这个操作中，只会对有空槽的页面造成影响。把这些锁及时释放可以允许更多的并行。

NO STEAL

由于种种原因，事务可能中止，这时需要逐个地回滚事务已经完成的操作。在本次 Lab 中，由于还没有日志模块记录已经完成的操作，要使用 NO STEAL 的模式。该模式的思想是，只有当事务提交到 DBMS 后，才将其脏页面写回磁盘。在页面逐出时不能逐出脏页面。这种思想非常的简单有效，只有事务提交后，脏页面写回磁盘，结果才真正生效。当事务中止时，直接将脏页面丢弃即可，无需额外回滚。但是这种方法也有问题，最大的问题是，BufferPool 中只有脏页面的时候，DBMS 就直接崩溃了。不过这种思想还是有好处的，事实上，页面逐出时，逐出脏页面会导致额外的写回开销，有一种策略就是优先逐出非脏页面，减少 IO。

这个 Exercise 在页面逐出时，按照优先级（例如 LRU）找到第一个非脏页面逐出即可。若页面全脏则抛出异常。

Transactions

根据上面已经实现的逻辑，实现 transactionComplete(tid, abort) 方法。当事务中止结束时，丢弃脏页面；提交结束后，写回脏页面。无论哪种结束，事务都需要释放持有的所有锁。

Deadlocks and Aborts

最后来到了本 Lab 的重头戏，死锁的检测。正如前文所说，避免死锁的方法有简单的超时中止，还有基于检测的等待图。指导书要求不能使用简单的超时中止策略，建议在每次分配锁前构建等待图，判断是否会发生死锁。这时，申请加锁就变成了下面的流程：

  1. 判断此次加锁是否会引入新的等待关系
    • 会，构建等待图，判断是否有死锁
      • 有，抛出异常
      • 没有，跳出
    • 不会，跳出
  2. 正常申请锁

可以看到，最重要的是多了一个等待图对象，需要保证它线程安全。可以直接使用一个 HashMap<TransacationId, LockItem>，HashMap 本身不是线程安全的，需要读写时加 synchornized，也可以使用线程安全的、并发性能更好的 ConcurrentHashMap。它将 HashMap 按键分成了若干个段，读写时只对对应的段加锁，提升了并发性能。

总结

本次 Lab 主要实现了事务的并发控制和死锁检测。正如指导书里面提到的，对并发进行 debug 是非常困难的事情。我本人花了一天时间才找到最后一个 exercise 的代码里的 bug 在哪里。当时还看了很多开源的代码实现，发现全是朴素的超时中止策略，没有使用等待图的。自己实现一遍还是收获颇丰。