概述

第四个project是实现一个 lock manager, 然后用它来支持并发查询执行.

lock manager是用来追踪向事务发出的tuple级的锁, 并支持基于隔离级别适当地授予和释放共享和排他锁.

主要有以下三个Task

需要通过两个测试文件

1
2
3
4
5

cd build
make lock_manager_test
make transaction_test
./test/lock_manager_test
./test/transaction_test

TASK #1 - LOCK MANAGER

为确保事务操作交叉执行的正确性，DBMS将使用lock manager（LM）来控制事务何时被允许访问数据项。LM的基本思想是它维护有关活动事务当前锁的锁的内部数据结构。事务在允许访问数据项之前向LM发出锁定请求。LM将授予锁定到调用事务，阻塞(block)将该事务块，或中止事务。

在你的实现中，整个系统中将有一个全局LM（类似于缓冲池管理器）。表堆(table heap)和executor类将使用您的LM在事务需要访问/修改元组时获取元组记录上的锁（通过record ID RID）。

这个task要求你实现一个tuple-level的LM, 以支持三种通用的隔离级别: READ_UNCOMMITED, READ_COMMITTED, and REPEATABLE_READ. LM需要根据事务的隔离级别来授予和释放锁.

在仓库中, 提供了事务的context handle(在include/concurrency/transaction.h)中, 它带有隔离级别属性, 以及它已获得的锁的信息. LM将会检查事务的隔离级别, 并且做出正确的操作. 任何失败的lock操作都将导致事务ABORTED状态并且抛出异常. 事务管理器应该捕捉这个异常并且将事务中执行的写操作回滚.

作者建议阅读这篇文章来回顾C++并发知识

要求和提示

只需要修改一个类: concurrency/lock_manager.cpp和concurrency/lock_manager.h , 需要实现以下方法:

  • LockShared(Transaction, RID): txn尝试在rid上获取一个共享锁. 在等待锁的时候应该blocked, 在被授予锁的时候应该返回true. 如果事务rolled back的话返回false.

  • LockExclusive(Transaction, RID): txn获取一个排他锁.

  • LockUpgrade(Transaction, RID): txn尝试将一个共享锁升级为排他锁.

  • Unlock(Transaction, RID): 解锁

    锁管理器采用的特定锁机制取决于事务的隔离级别, 你应该先看一下transaction.h和lock_manager.h来熟悉API以及我们提供的成员变量. 我们还建议你复习隔离级别概念，因为这些函数的实现应与正在进行lock/unlock请求的事务的隔离级别兼容。你有在lock_manager.h中添加任何需要的数据结构的自由.

助教们的建议

  • 虽然你的锁管理器需要使用死锁预防，但我们建议您先实现锁管理器，而不进行任何死锁处理，然后在验证它在没有死锁发生时能正确地进行lock/unlock后，再添加预防机制。(由简到繁)
  • 你将需要一些方法来追踪哪些事务正在一个lock上waiting. 看看lock_manager.h中的LockRequestQueue类
  • LockUpgrade在LockRequestQueue上的操作转换为什么?
  • 您需要某种方法来通知可能能够获取锁的正在waiting的事务。我们建议使用std::condition_variable条件变量 (实现的原理和普通的锁的原理很像, 都是锁, 嘿嘿)
  • 尽管某些隔离级别是通过确保严格的两阶段锁定的属性来实现的，但锁管理器的实现只需要确保两阶段锁定的属性。严格2PL的概念将通过执行程序和事务管理器中的逻辑实现。看看Commit和Abort方法。
  • 你还应该维护事务的状态. 例如, 因为unlock操作, 事务的状态可能从GROWING阶段变成SHRINKING阶段. (提示: 看transaction.h中的方法)
  • 你还应该使用 shared_lock_set_ 和 exclusive_lock_set_ 来跟踪事务获取的共享/排他锁，以便当 TransactionManager 想要提交/中止事务时，LM 可以正确释放它们(目的)。
  • 将一个事务的状态设置为ABORTED将会隐式地中止它，但知道调用TransactionManager::abort，它才会明确中止。您应该阅读此功能以了解它的作用，以及如何在中止过程中使用锁定管理器。

实现

需要梳理清楚几种操作对LM的结构的影响（或者说LM如何实现这几种操作的语义）

LockShared

这是获取共享锁, 那么如果当前RID上有排他锁, 则只能等待并且知道没有排他锁.

如果当前RID上有其他共享锁, 则可以一起共享, 并且授予共享锁.

如果当前RID上没有其他锁, 则可以授予共享锁.

BasicTest里只有这个LockShared的测试, 所以先只考虑这个. 测试是check状态的变化, 这个操作会导致状态发生什么变化呢?

一个事务执行LockShared之后, 应当变为Growing状态; Unlock之后变为Shrinking状态; 事务管理器执行Commit之后变为Committed状态.

状态的变化看transaction.h的注释, shringking的意思是收缩, growing是增长

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * Transaction states for 2PL:
 *
 *     _________________________
 *    |                         v
 * GROWING -> SHRINKING -> COMMITTED   ABORTED
 *    |__________|________________________^
 *
 * Transaction states for Non-2PL:
 *     __________
 *    |          v
 * GROWING  -> COMMITTED     ABORTED
 *    |_________________________^
 *
 **/

TASK #2 - DEADLOCK PREVENTION

如果您的锁管理器被告知使用预防死锁，那么您的锁管理器应该使用WOUND-WAIT算法来决定中止哪些事务。

获取锁时，您需要查看相应的LockRequestQueue，以查看它将等待的事务。

助教的建议

  • 仔细阅读幻灯片了解Wound-Wait算法如何实现。

  • 中止事务时，请务必使用SetState方法正确设置状态

  • 如果事务正在upgrading (等待获取X-Lock），则仍然可以中止。您必须正确处理此操作。

  • 等待图表在交易等待另一个事务时绘制边缘。请记住，如果多个事务使用一个共享锁，则单个事务可能等待在多个事务中。(意思是不要一个事务OK了就release)

  • 事务终止时，请务必将事务的状态设置为ABORTED并在锁管理器LM中抛出异常。事务管理器将处理显式中止和回滚更改。

  • 根据wound-wait的预防策略，一个正在等待锁的事务可能被另一个线程终止。你必须有办法通知他们已中止的等待事务。

TASK #3 - CONCURRENT QUERY EXECUTION

在并发查询执行期间，executors需要适当地lock/unlock tuples，以实现相应事务中指定的隔离级别。为简化此任务，您可以忽略并发索引执行，并专注于table tuples。

你需要更新一些在project3中实现的执行算子的Next()方法(如sequential scans, inserts, updates, deletes, nested loop joins, and aggregations). 请注意，锁定/解锁失败时事务将中止。虽然没有并发索引执行要求，但我们仍然需要在交易中止时适当地撤消两表元组和索引上的所有先前写入操作。为此，你需要在事务管理器的Abort()据了解方法中需要维护写入中的写入集。

您不应假设事务仅包含一个查询。具体来说，这意味着一个元组可能在一个事务中被不同的查询多次访问。想想你应该如何在不同的隔离级别下处理这个问题。

更具体地说，您需要在以下执行程序中添加对并发查询执行的支持：

  • src/execution/seq_scan_executor.cpp
  • src/execution/insert_executor.cpp
  • src/execution/update_executor.cpp
  • src/execution/delete_executor.cpp

资料

浅谈数据库并发控制 - 锁和 MVCC

这篇文章很好，里面介绍了wait-die协议和wound-wait协议。

另一种机制叫做 wound-wait，这是一种抢占的解决方案，它和 wait-die 机制的结果完全相反，当前事务如果先于另一事务执行并请求了另一事务的资源，那么另一事务会立刻回滚，将资源让给先执行的事务，否则就会等待其他事务释放资源。

分布式系统中的死锁处理 (Wound/Wait Mutexes reservation.c )