SimpleDB-Lab4

0.实验目标

在这个实验中，你将在SimpleDB中实现一个简单的基于锁的事务系统。你将需要在代码中的适当位置添加锁和解锁调用，以及跟踪每个事务所持有的锁的代码，并在需要时授予事务锁。

本文档的其余部分描述了添加事务支持所涉及的内容，并提供了一个关于如何将这种支持添加到你的数据库的基本概要。

Transactions outline

事务

事务是一组以原子方式执行的数据库操作(例如插入、删除和读取)，也就是说，要么所有的动作都完成了，要么一个动作都没有完成，而数据库的外部观察者并不清楚这些动作不是作为单个不可分割动作的一部分完成的。

ACID特性

为了理解在SimpleDB中事务管理是如何工作的，接下来简要介绍它是如何满足ACID特性的：

• Atomicity：严格的两阶段锁以及缓冲区管理将确保原子性
• Consistency：通过原子性来保证事务的一致性，在SimpleDB中并未使用其他一致性方法（如键约束）
• Isolation：严格的两阶段提交保证隔离性
• Durability：强制缓冲区管理策略可确保持久性

两阶段锁

通过上述ACID特性可以得知两阶段锁在其中扮演重要的角色，那么首先来了解下什么是两阶段锁。两阶段锁协议的主要内容如下：

• 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁。在对任何数据进行读操作之前要申请获得S锁，在进行写操作之前要申请获得X锁。加锁不成功事务进入等待状态，直到加锁成功才成功继续执行。
• 在释放一个封锁之后，事务不再获得任何其他封锁；事务进入解锁阶段，在该阶段进行解锁操作不能再进行加锁操作。

两段锁的含义是事务分为两个阶段：

• 第一阶段是获得封锁，称为扩展阶段。
• 第二阶段称为释放阶段，也成为收缩阶段。

有如下三种两阶段锁：

• Basic 2PL：在事务过程中，分为获得锁和释放锁两个阶段
• Strict 2PL：直到事务结束为止，都不释放获得的锁
• Static 2PL：在事务开始前，获得所需的全部锁

两段封锁法可以这样来实现：事务开始后就处于加锁阶段，一直到执行ROLLBACK和COMMIT之前都是加锁阶段。ROLLBACK和COMMIT使事务进入解锁阶段，即在ROLLBACK和COMMIT模块中DBMS释放所有封锁。

Recovery and Buffer Management

为了简化你的工作，建议实现一个非强制缓冲区管理策略：

• 如果页面被未提交的事务锁住，你不应该从缓冲池中丢弃脏页(更新脏页)。
• 事务提交后，应该强制将脏页刷新至磁盘(这就是强制策略)。

为了进一步简化实现，可以假设SimpleDB在处理“transactionComplete”命令时不会崩溃。注意本次实验不需要实现基于日志的崩溃恢复，也不需要撤销(undo)任何工作(不必丢弃脏页)并且也不需要重做(redo)任何工作(在提交时强制更新并且在提交事务期间不会崩溃)。

1. Granting Locks

a. 要修改的文件

• src/simpledb/BufferPool.java

b. 实现说明

• 我们需要添加对SimpleDB的调用(例如在BufferPool中)，以允许调用方代表特定事务请求或释放特定对象上的(共享或独占)锁。

• 我们建议在页面粒度上锁，为了简化测试，不要实现表级锁定(即使可能)，本文档的其余部分和我们的单元测试假设页面级锁定。

• 我们需要创建数据结构来跟踪每个事务持有哪些锁，并检查是否应在请求时向事务授予锁。

• 我们需要实现共享锁和独占锁。回顾一下，这些锁的工作方式如下：

• 在事务进行读操作之前，它必须获得共享锁

• 在事务进行写操作之前，它必须获得独占锁

• 多个事务可以获取同一对象的共享锁

• 只有一个事务能获取对象的独占锁

• 如果事务t是持有对象o共享锁的唯一事务，t能够将持有的对象o的共享锁升级为独占锁(锁升级)

• 如果事务请求的锁不能立即被授予，你的代码应该锁住，直到锁可用(锁被不同线程的其他事务释放)；在锁实现中要注意争用条件——想想对锁的并发调用会如何影响行为。

c. 实现目标

• 编写BufferPool中获取和释放锁的方法。假设你使用的是页级锁，你将需要完成以下工作：

• 修改getPage()，使其在返回页面前阻塞并获得所需的锁。

• 实现unsafeReleasePage()。这个方法主要用于测试，以及在事务结束时使用。

• 实现 holdsLock()，以便练习2中的逻辑能够确定一个页面是否已经被事务锁定。 你可能会发现，定义一个LockManager类来负责维护事务和锁的状态是很有帮助的，但设计决定权在你。

• 通过单元测试LockingTest（需要完成下一个练习）。

务期间不会崩溃)。

2. Lock Lifetime

a. 要修改的文件

• src/simpledb/BufferPool.java

b. 实现说明

• 你将需要实现严格的两阶段锁。这意味着事务在访问任何对象之前应该获得相应类型的锁，并且在事务提交之前不应该释放任何锁。

• 幸运的是，SimpleDB的设计是这样的：在你读取或修改页面之前，有可能在BufferPool.getPage()中获得页面的锁。因此，我们建议在getPage()中获取锁，而不是在你的每个操作中添加对锁程序的调用。根据你的实现，你有可能不需要在其他地方获取锁。这要靠你自己去验证!

• 你需要在读取任何页面（或元组）之前获得一个共享锁，你需要在写入任何页面（或元组）之前获得一个独占锁。你会注意到，我们已经在BufferPool中传递了许可对象；这些对象表明调用者希望对被访问对象拥有的锁的类型（我们已经给了你许可类的代码。）

• 请注意，你对HeapFile.insertTuple()和HeapFile.deleteTuple()的实现，以及HeapFile.iterator()返回的迭代器的实现应该使用BufferPool.getPage()访问页面。仔细检查这些getPage()的不同用法是否传递了正确的权限对象（例如，Permissions.READ_WRITE 或 Permissions.READ_ONLY）。你也可以仔细检查你实现的BufferPool.insertTuple()和BufferPool.deleteTupe()是否在它们访问的任何页面上调用markDirty()（你在实验2中实现这段代码时应该这样做，但我们没有测试这种情况）。

• 在你获得锁之后，你也需要考虑何时释放它们。很明显，你应该在一个事务提交或中止后释放所有与之相关的锁，以确保严格的2PL。然而，在其他情况下，在事务结束前释放锁可能是有用的。例如，你可以在扫描页面找到空槽后释放一个共享锁（如下所述）。

• 确保你在整个SimpleDB获得和释放锁。一些（但不一定是全部）你应该验证的操作正常工作：

• 在SeqScan过程中从页面上读取 tuple（如果你在BufferPool.getPage()中实现了锁定，只要你的HeapFile.iterator()使用BufferPool.getPage()，这应该可以正确工作。）

• 通过BufferPool和HeapFile方法插入和删除图元（如果你在BufferPool.getPage()中实现了锁，只要HeapFile.insertTuple()和HeapFile.deleteTuple()使用BufferPool.getPage()，这应该能正确工作。）

• 你还需要特别考虑在以下情况下获取和释放锁的问题：

• 向HeapFile添加一个新的页面。你什么时候把这个页面写到磁盘上？是否存在与其他事务（在其他线程上）的竞赛条件，可能需要在HeapFile级别上特别注意，而不考虑页级锁定？

• 寻找一个可以插入图元的空槽。大多数实现都会扫描页面，寻找一个空槽，并且需要一个READ_ONLY锁来完成这个工作。然而，令人惊讶的是，如果一个事务t发现页面p上没有空槽，t可以立即释放p上的锁。虽然这显然与两阶段锁的规则相矛盾，但它是可以的，因为t没有使用页面上的任何数据，这样，一个更新p的并发事务t’不可能影响t的答案或结果。

c. 实现目标

• 通过单元测试LockingTest。

3. Implementing NO STEAL

a. 要修改的文件

• src/simpledb/BufferPool.java

b. 实现说明

• 一个事务的修改只有在它提交之后才会被写入磁盘。这意味着我们可以通过丢弃脏页并从磁盘重读来中止一个事务。因此，我们必须不驱逐脏页。这个策略被称为NO STEAL。
• 你将需要修改BufferPool中的evictPage方法。特别是，它必须永远不驱逐一个脏页。如果你的驱逐策略倾向于驱逐一个脏页，你将不得不找到一种方法来驱逐一个替代页。在缓冲池中的所有页面都是脏的情况下，你应该抛出一个DbException。如果你的驱逐策略驱逐了一个干净的页面，要注意事务可能已经持有被驱逐的页面的任何锁，并在你的实现中适当地处理它们。
• 需要在BufferPool的evictPage方法中实现必要的页面驱逐逻辑，而不驱逐脏页。

c. 实现目标

4. Transactions

a. 要修改的文件

• src/simpledb/BufferPool.java

b. 实现说明

• 在SimpleDB中，每次查询开始时都会创建一个TransactionId对象。这个对象被传递给每个参与查询的操作者。当查询完成后，BufferPool方法 transactionComplete被调用。

• 调用此方法可以提交或中止事务，由参数标志commit指定。在其执行过程中的任何时候，操作者都可以抛出一个TransactionAbortedException异常，这表明发生了内部错误或死锁。我们为你提供的测试案例创建了适当的TransactionId对象，以适当的方式将它们传递给你的操作者，并在查询完成后调用 transactionComplete。我们还实现了TransactionId。

• 需要在BufferPool中实现transactionComplete()方法。

• 请注意，transactionComplete有两个版本，一个是接受额外的布尔提交参数，另一个是不接受。没有额外参数的版本应该总是提交，所以可以简单地通过调用 transactionComplete(tid, true) 来实现。

• 当commit时，你应该将与事务相关的脏页冲到磁盘上。当abort的时候，你应该通过恢复页面到磁盘上的状态来恢复事务所做的任何改变。

• 无论事务是提交还是中止，你都应该释放BufferPool保存的关于该事务的任何状态，包括释放该事务持有的任何锁。

c. 实现目标

• 通过单元测试TransactionTest和AbortEvictionTest

• TransactionTest需要下一个练习完成

5. Deadlocks and Aborts

a. 要修改的文件

• src/simpledb/BufferPool.java

b. 实现说明

• SimpleDB中的事务有可能出现死锁（如果你不明白为什么，我们建议阅读Ramakrishnan & Gehrke中关于死锁的内容）。你需要检测这种情况并抛出一个TransactionAbortedException。

• 有很多死锁检测的方法，例如，实现一个简单的超时策略，如果事务在给定时间段后还没有完成，它将中止事务。

• 对于真实的场景，我们可以在依赖关系图数据结构中实现循环检测。在这个方案中，我们将定期或每当尝试授予新锁时检查依赖关系图中的周期，如果存在周期，则中止某些操作。如果检测到死锁的存在，我们必须解决死锁。假设当事务t等待锁时检测到死锁的存在，中止t正在等待的所有事务；这可能导致大量工作被撤销，但可以保证t会取得进展。或者，我们可以中止t，以使其他事务有机会取得进展。这意味最终用户必须重试事务t。

• 另一种方法是使用事务的全局排序来避免建立等待图。出于性能方面的考虑，这有时是首选，但是在这种方案下，本来可以成功的事务可能会被错误地中止。例子包括WAIT-DIE和WOUND-WAIT方案。

• 现死锁检测或预防。对于你的死锁处理系统，你有很多设计决定，但没有必要做一些非常复杂的事情。我们希望你能做得比每个事务的简单超时更好。一个好的起点是在每个锁请求前的等待图中实现周期检测，这样的实现将得到全额奖励。请在实验报告中描述你的选择，并列出你的选择与其他选择相比的优点和缺点。

• 你应该通过抛出TransactionAbortedException异常来确保你的代码在发生死锁时正确中止事务。这个异常将被执行事务的代码所捕获（例如，TransactionTest.java），它应该调用 transactionComplete() 来清理事务。我们不期望你自动重启一个因死锁而失败的事务–你可以假设更高级别的代码会处理这个问题。

• 我们在test/simpledb/DeadlockTest.java中提供了一些（不是单元的）测试。它们实际上有点复杂，所以它们可能需要超过几秒钟的时间来运行（取决于你的策略）。如果它们似乎无限期地挂起，那么你可能有一个未解决的死锁。这些测试构建了简单的死锁情况，你的代码应该能够逃脱。

• 注意，在DeadLockTest.java的顶部附近有两个计时参数；这些参数决定了测试检查是否已经获得锁的频率，以及中止的事务被重新启动前的等待时间。如果你使用基于超时的检测方法，你可以通过调整这些参数观察到不同的性能特征。测试将把解决死锁对应的TransactionAbortedExceptions输出到控制台。

• 在这一点上，你应该有一个可恢复的数据库，也就是说，如果数据库系统崩溃（在 transactionComplete() 以外的地方），或者如果用户显式地中止一个事务，那么在系统重新启动（或者事务中止）之后，任何正在运行的事务的影响将不可见。 你可能希望通过运行一些事务和显式地杀死数据库服务器来验证这一点。

c. 实现目标

• 通过TransactionTest系统测试（根据实现，它也可能运行相当长的时间）

小结

• 参考MIT 6.830数据库系统，将等待时间修改为原本十分之一

• execution中Delete和Insert原本没有正确使用TransactionId，做更正

• BufferPool中加入LockManager类型（自定义）的lockManager，用于管理锁，提供加锁、解锁等方法；加入Map<TransactionId, List<Page>>类型的tidToPagesMap，将事务id映射到对应的Page。

• 在getPage()中，根据Permissions来判断需要加锁的类型，并调用lockManager进行获取锁。若类型为Permissions.READ_WRITE，则将该Page添加到tid事务相关的PageList中。

• unsafeReleasePage()调用lockManager的对应方法。

• transactionComplete()中，若commit事务，则将事务涉及的Page都刷新到磁盘；否则，回滚事务，重新从磁盘中读取对应的Page。

• 在insertTuple()和deleteTuple()中，更新tidToPagesMap，将涉及到的Page加入到对应事务id。

• flushPages()通过tidToPagesMap，将传入的事务id对应的Page刷新到磁盘。

• 更新evictPage()方法，每次淘汰不脏的Page。若均为脏页，则抛出异常。

• 测试结果截图：