MIT6.830-lab4-SimpleDB Transactions(数据库的事务LockManager、事务操作、死锁处理)

👉 代码获取和项目文档

任务介绍

MIT6.830的lab4中，我们主要需要实现事务处理和并发相关的功能，我们需要为SimpleDB设计一个二阶段锁的管理器。

事务是一组以原子方式执行的数据库操作（例如，插入、删除和读取）；也就是说，要么所有的动作都完成了，要么一个动作都没有完成。

• 原子性：通过两段锁协议和BufferPool的管理实现simpleDB的原子性；
• 一致性：通过原子性实现事务的一致性，simpleDB中没有解决其他一致性问题（例如，键约束）；
• 隔离性：严格的两段锁提供隔离；
• 持久性：事务提交时将脏页强制写进磁盘。

两段锁协议：

• 第一阶段：扩展阶段，事务可以申请获得任意数据上的任意锁，但是不能释放任何锁；
• 第二阶段：收缩阶段，事务可以释放任何数据上的任何类型的锁，但是不能再次申请任何锁。

遵守两端所协议可能会发生死锁：两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁。

simpleDB中的实现过程为，事务提交之前可以获取任何锁，事务提交之后释放该事务所拥有的所有锁。同时在获取锁的过程中进行死锁检测。

exercise 1 - Granting Locks

实现一个页级的锁管理器，在BufferPool.getPage()时，通过该管理器尝试获取该页的读/写权限，之后才能获取页并开始事务相关操作。事务结束后要在BufferPool.unsafeReleasePage()里通过该管理器释放锁。

本质是要通过实现严格二阶段封锁协议来实现对事务的支持。基于此实现获取锁、释放锁、读锁写锁之间的交互等功能。

主要实现以下三个任务：

• 修改getPage()函数，在返回页面之前阻塞并获取所需的锁；
• 实现unsafeReleasePage()函数，释放指定TransactionId和PageId的锁；
• 实现holdsLock()函数，判断指定TransactionId和PageId是否持有锁。

在在完成任务之前，我们要定义一个负责维护有关事务和锁的状态的锁管理器 LockManager 类。

先定义一个锁：

private Permissions permissions;
private TransactionId transactionId;
1
2

再看下锁管理器LockManager的设计：

//key：页id，value：作用于该页的所有lock
private Map<Integer, List<Lock>> lockCache;
1
2

成员变量就只有一个Map结构，保存了作用于一页的所有锁。

（1）获取锁

public synchronized  Boolean acquireLock(TransactionId tid, PageId pageId, Permissions permissions){
    Lock lock = new Lock(tid, permissions);
    int pid = pageId.getPageNumber();
    List<Lock> locks = lockCache.get(pid);
    if(locks==null || locks.size()==0){
        locks = new ArrayList<>();
        locks.add(lock);
        lockCache.put(pid,locks);
        return true;
    }


    if(locks.size()==1){
        //当只有一个事务抢占锁
        Lock curLock = locks.get(0);
        if(curLock.getTransactionId().equals(tid)){
            //判断是否进行锁升级
            if(curLock.getPermissions().equals(Permissions.READ_ONLY) && lock.getPermissions().equals(Permissions.READ_WRITE)){
                curLock.setPermissions(Permissions.READ_WRITE);
            }
            return true;
        }else{
            //如果是多个读锁
            if(curLock.getPermissions().equals(Permissions.READ_ONLY) && lock.getPermissions().equals(Permissions.READ_ONLY)){
                locks.add(lock);
                return true;
            }
            return false;
        }
    }

    //当有多个事务抢占锁，说明必然是多个读事务
    if(lock.getPermissions().equals(Permissions.READ_WRITE)){
        return false;
    }

    //每一个事物读锁并不需要重复获取
    for(Lock l: locks){
        if(l.getTransactionId().equals(lock.getTransactionId())){
            return true;
        }
    }
    locks.add(lock);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

（2）释放锁

public synchronized  void releaseLock(TransactionId tid,PageId pageId){
    int pid = pageId.getPageNumber();
    List<Lock> locks = lockCache.get(pid);
    for(Lock l:locks){
        if(l.getTransactionId().equals(tid)){
            locks.remove(l);
            if(locks.size()==0){
                lockCache.remove(pid);
            }
            return;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

还需要实现两个函数：释放当前事务的所有锁、判断是否持有锁。这里就不贴出来了，判断逻辑很简单。

而完成了以上设计，我们的三个任务其实就很简单了，unsafeReleasePage和holdsLock这两个函数直接调用就行了，看下getPage()函数的部分修改：

public  Page getPage(TransactionId tid, PageId pid, Permissions perm)
    throws TransactionAbortedException, DbException {

    //先获取锁
    boolean lockAcquired = false;
    long start = System.currentTimeMillis();
    long timeout = new Random().nextInt(2000);
    while(!lockAcquired){
        long now = System.currentTimeMillis();
        if(now - start> timeout){
            throw new TransactionAbortedException();
        }
        lockAcquired = lockManager.acquireLock(tid,pid,perm);
    }

    if (this.buffer.get(pid)==null) {
        // find the right page in DBFiles
        DbFile dbFile = Database.getCatalog().getDatabaseFile(pid.getTableId());
        Page page = dbFile.readPage(pid);
        if (buffer.getSize() > numPages) {
            evictPage();
        }
        buffer.put(pid, page);
        return page;
    }
    return this.buffer.get(pid);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

这里是采用了自旋的方式不断获取锁，并设置一个获取锁的超时时间，超过这个时间了就抛出异常。一旦获取锁了，就可以进行接下来的读操作了。

exercise 2 - Lock lifeTime

这一部分就是基于Exercise 1，在BufferPool中getPage和releasePage对应的地方，增加LockManager的acquireLock和releaseLock方法，以此来实现严格二阶段封锁协议并实现事务的功能。

• BufferPool.getPage()：每次获取页之前，都要先判断是否能获取该页的锁，并且选择一种方式避免等待获取锁而导致死锁；
• HeapFile.insertTuple()：当事务向page中的空slot插入tuple时，首先需要获取该page上的锁。如果该page上没有空的slot，需要访问下一个page，如果该HeapFile上所有的page都已满，需要创建一个新的page将tuple插入其中。但是，虽然该事务不会对已满的page进行操作，可此时它依旧持有这些page上的锁，其它事务也不能访问这些page，所以当判断某一page上的slot已满时，需要释放掉该page上的锁。虽然这不满足两段锁协议，但该事务并没有使用page中的任何数据，后序也不会用到，所以并不会有任何影响，而且也可以让其他事务访问那些slot已满的page。

解决死锁的方式有：

• 超时等待：对每个事务设置一个获取锁的超时时间，如果在超时时间内获取不到锁，我们就认为可能发生了死锁，将该事务进行中断。
• 循环等待图检测：建立事务等待关系的等待图，当等待图出现了环时，说明有死锁发生，在加锁前就进行死锁检测，如果本次加锁请求会导致死锁，就终止该事务。

而其实在Exercise 1中，我们就已经使用了超时等待的方法来完善BufferPool.getPage()方法。这里在看下HeapFile.insertTuple()方法：

for(int i=0;i<numPages();i++){
    HeapPageId heapPageId = new HeapPageId(getId(),i);
    HeapPage heapPage = (HeapPage) Database.getBufferPool().getPage(tid,heapPageId,Permissions.READ_ONLY);
    if(heapPage==null){
        Database.getBufferPool().unsafeReleasePage(tid,heapPageId);
        continue;
    }
    if(heapPage.getNumEmptySlots()==0){
        Database.getBufferPool().unsafeReleasePage(tid,heapPageId);
        continue;
    }
    heapPage.insertTuple(t);
    heapPage.markDirty(true,tid);
    res.add(heapPage);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这一步骤就是遍历所有的page，看看有没有page可以进行插入，而当该page没有空位时，就需要释放该page的锁。

exercise 3 - Implementing NO STEAL

事务对page的修改只有在commit之后才会写入到磁盘，但是在之前的Lab中实现页面置换策略时，当置换掉的页面是dirty page时，也会将更改写回到磁盘。这是不允许的，所以需要完善evictPage()方法，当需要置换的page是dirty page时，需要跳过此page，去置换下一个非dirty的page。当BufferPool中缓存的page都是dirty page时，抛出异常。

在lab2中，我们也已经简单提及到了evictPage的实现，这里给出详细代码：

private synchronized  void evictPage() throws DbException {
    // some code goes here
    // not necessary for lab1
    Page page = buffer.getTail().prev.value;
    if(page!=null && page.isDirty()!=null){
        findNotDirty();
    }else{
        //不是脏页没改过，不需要写磁盘
        buffer.discard();
    }
}

private void findNotDirty() throws DbException {
    LRUCache<PageId, Page>.DLinkedNode head = buffer.getHead();
    LRUCache<PageId, Page>.DLinkedNode tail = buffer.getTail();
    tail = tail.prev;
    while (head != tail) {
        Page value = tail.value;
        if (value != null && value.isDirty() == null) {
            buffer.remove(tail);
            return;
        }
        tail = tail.prev;
    }
    //没有非脏页，抛出异常
    throw new DbException("no dirty page");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

exercise 4 - Transactions

完成BufferPool的transactionComplete()函数，transactionComplete() 有两个版本：一个接受额外的布尔参数（当布尔参数为true时，进行提交。false时进行回滚），另一个不接受。没有附加参数的版本应该总是提交，因此可以简单地通过调用来实现 transactionComplete(tid, true)。

public void transactionComplete(TransactionId tid) {
    // some code goes here
    // not necessary for lab1|lab2
    transactionComplete(tid,true);
}

public void transactionComplete(TransactionId tid, boolean commit) {
    // some code goes here
    // not necessary for lab1|lab2
    if(commit){
        try {
            flushPages(tid);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }else{
        rollback(tid);
    }
    lockManager.releaseAllLock(tid);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 当进行提交时，进行一次指定TransactionId的刷盘；
• 当进行回滚时，从BufferPool中清除掉该事务造成的脏页，并将原始版本重新读到BufferPool中。

private synchronized void rollback(TransactionId tid){
    LRUCache<PageId, Page>.DLinkedNode head = buffer.getHead();
    LRUCache<PageId, Page>.DLinkedNode tail = buffer.getTail();
    while(head!=tail){
        Page page = head.value;
        LRUCache<PageId, Page>.DLinkedNode next = head.next;
        if(page!=null && page.isDirty()!=null && page.isDirty().equals(tid)){
            buffer.remove(head);
            Page page1 = null;
            try {
                page1 = Database.getBufferPool().getPage(tid, page.getId(), Permissions.READ_ONLY);
                page1.markDirty(false,null);
            } catch (TransactionAbortedException e) {
                e.printStackTrace();
            } catch (DbException e) {
                e.printStackTrace();
            }

        }
        head = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

exercise 5 - DeadLock and Abort

这个部分就是解决死锁的问题，这点在exercise 1和exercise 2中都有提及和解决，就不说了。