CS186 Project 4: SimpleDB Transactions

CS186 Project 4: SimpleDB Transactions

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

Transactions, Locking, and Concurrency Control

Transactions

事务是原子执行的一组数据库操作(例如,插入,删除和读取);也就是说,要么所有动作都已完成,要么全部都失败回滚。

The ACID Properties

原子性:严格的两阶段锁定和缓冲区管理可确保原子性。

一致性:由于原子性,数据库是事务一致的。

隔离性:严格的两阶段锁定提供隔离。

持久性:FORCE缓冲区管理策略可确保持久性

Recovery and Buffer Management

实施NO STEAL / FORCE缓冲区管理策略。需要做:

  • 如果脏页被未提交的事务锁定,则不应从缓冲池中清除脏页(这称为NO STEAL)。
  • 在事务提交时,应将脏页强行写入磁盘(这称为FORCE)。

Granting Locks

这一部分需要在SimpleDB添加调用,允许调用者代表特定事务请求或释放对特定对象的(共享或独占)锁,建议锁定页面粒度。同时还需要创建数据结构,以跟踪每个事务持有哪些锁,并检查是否应在请求事务时将锁授予该事务。

共享锁和互斥锁有以下特性:

  • 在事务可以读取对象之前,它必须具有共享锁。
  • 在事务可以写入对象之前,它必须具有互斥锁。
  • 多个事务可以在一个对象上拥有一个共享锁。
  • 只有一个事务可以在对象上具有互斥锁。
  • 如果事务t是唯一持有对象o共享锁的事务,则t可以将其对o的锁升级为互斥锁。

如果某个事务请求了不应授予的锁,则您的代码应阻塞,等待该锁可用。

这里先说几个重要的辅助类, Permission.javaLockState.java LockManager.java

Permission.java

/**
 * Class representing requested permissions to a relation/file.
 * Private constructor with two static objects READ_ONLY and READ_WRITE that
 * represent the two levels of permission.
 */
public class Permissions {
  int permLevel;

  private Permissions(int permLevel) {
    this.permLevel = permLevel;
  }

  public String toString() {
    if (permLevel == 0)
      return "READ_ONLY";
    if (permLevel == 1)
      return "READ_WRITE";
    return "UNKNOWN";
  }

  public static final Permissions READ_ONLY = new Permissions(0);
  public static final Permissions READ_WRITE = new Permissions(1);

}

这个类是用来表示某个object的锁的类型,READ_ONLYREAD_WRITE分别表示共享锁和互斥锁。

LockState

    private TransactionId tid;
    private Permissions perm;

主要通过TransactionIdPermissions来记录一个锁的状态,当然锁都是针对页面的,每个页面有不同的transactionpermission,后面可以看到LockManager用了一个map来记录它们的对应关系。

LockManager

LockManager是锁管理类,实现了锁相关的很多方法,应该是项目4的核心内容。

    //Key相当于资源,LockState存放事务id与锁类型,故每个LockState代表某事务在Key上加了锁
    //故整个map为所有资源的锁信息
    private Map<PageId, List<LockState>> lockStateMap;

    //Key为事务,PageId为正在等待的资源,相当于保存了等待的信息,PS:BufferPool中实际用的是sleep体现等待
    private Map<TransactionId, PageId> waitingInfo;
        public LockManager() {
        //使用支持并发的容器避免ConcurrentModificationException
        lockStateMap = new ConcurrentHashMap<>();
        waitingInfo = new ConcurrentHashMap<>();
        }	

lock()

LockManagerlock()方法对某个页面上锁,将它加入lockStateMap中,并从等待HashMapwaitingInfo中移除, waitingInfo中保留的是等待信息,即某个事务在等待某个页面,当这个页面被当前事务锁定,对应的映射就应该从waitingInfo中移除,因为事务已经使用上某个页面,而不是一直在等待,因此这个事务就应该从当前的等待队列中移除.

    private synchronized boolean lock(PageId pid, TransactionId tid, Permissions perm) {
        LockState nls = new LockState(tid, perm);
        ArrayList<LockState> list = (ArrayList<LockState>) lockStateMap.get(pid);
        if (list == null) {
            list = new ArrayList<>();
        }
        list.add(nls);
        lockStateMap.put(pid, list);
        waitingInfo.remove(tid);
        return true;
    }

unlock()

unlock同样是改变lockStateMap中与当前PageId对应的lockState的list的状态,也就是把对应的lockState移除,这个时候并不需要把tidpid放入到waitingInfo中,因为它只是把锁去掉,waitingInfo中存储的是事务请求某个资源等待的信息。

    public synchronized boolean unlock(TransactionId tid, PageId pid) {
        ArrayList<LockState> list = (ArrayList<LockState>) lockStateMap.get(pid);
        if (list == null || list.size() == 0) return false;
        LockState ls = getLockState(tid, pid);
        if (ls == null) return false;
        list.remove(ls);
        lockStateMap.put(pid, list);
        return true;
    }

wait()

wait方法就是把对应的transactionIdpageId放到waitingInfo这个map里面,是个单独的方法,在需要调用的时候才把某个transaction下的page设为wait状态,而不是解锁了就要加入,这个方法在事务请求某个页面不得,需要等待的时候调用。

    private synchronized boolean wait(TransactionId tid, PageId pid) {
        waitingInfo.put(tid, pid);
        return false;
    }

grantSLock()

grantSLock()用于授予共享锁,逻辑如下:

  • 如果LockState的list不为空:

    • 如果LockState的list长度为1:
      • 如果这个唯一的锁是自己的锁:
        • 如果是读锁,那就直接返回,否则就是自己的写锁,那就上读锁
      • 这个唯一的锁不是自己的锁:
        • 如果是别人的读锁,那可以加锁并返回,否则就是别人的写锁,那就等待
    • LockState的list长度不为1,而是多个:
      • 如果有个写锁:
        • 如果是自己的锁,那就返回true,否则就是别人的写锁,那就等待
      • 否则,如果是自己的读锁:
        • 直接返回true
    • 遍历后还是没有返回,说明都是别的transaction的读锁,那就上自己的读锁
  • 否则pid对应的LockState的list为空,那么说明这个页面没有加任何的锁,可以直接加锁,加锁就只是改变lockStateMap的状态了,不涉及是否有锁的判断.

    public synchronized boolean grantSLock(TransactionId tid, PageId pid) {
        ArrayList<LockState> list = (ArrayList<LockState>) lockStateMap.get(pid);
        if (list != null && list.size() != 0) {
            if (list.size() == 1) {//pid上只有一个锁
                LockState ls = list.iterator().next();
                if (ls.getTid().equals(tid)) {//判断是否为自己的锁
                    //如果是读锁,直接返回(在||的之前返回),否则加锁再返回
                    return ls.getPerm() == Permissions.READ_ONLY || lock(pid, tid, Permissions.READ_ONLY);
                } else {
                    //如果是别人的读锁,加锁再返回,是写锁则需要等待
                    return ls.getPerm() == Permissions.READ_ONLY ? lock(pid, tid, Permissions.READ_ONLY) : wait(tid, pid);
                }
            } else {
                //多个锁有四种情况
                // 1.两个锁,且都属于tid(一读一写)    2.两个锁,且都属于非tid的事务(一读一写)
                // 3.多个读锁,且其中有一个为tid的读锁  4.多个读锁,且没有tid的读锁
                for (LockState ls : list) {
                    if (ls.getPerm() == Permissions.READ_WRITE) {
                        //如果其中有一个写锁,那么根据是否为自己的来判断属于情况1还是2
                        return ls.getTid().equals(tid) || wait(tid, pid);
                    } else if (ls.getTid().equals(tid)) {//如果是读锁且是tid的
                        return true;//情况3在此返回,也可能是情况1(如果先遍历到读锁)
                    }
                }
                //情况4
                return lock(pid, tid, Permissions.READ_ONLY);
            }
        } else {
            return lock(pid, tid, Permissions.READ_ONLY);
        }
    }

grantXLock()

获取互斥锁,逻辑是相对简单的,可以直接看解释:

  • 如果LockState的数组不为空:
    • 如果LockState的长度为1,说明只有一个锁:
      • 如果是自己的写锁,直接返回,否则即为自己的读锁,上面说了共享锁可以升级为互斥锁,因此选择上锁
      • 否则则是别人的锁,等待
    • 否则即有多个锁:
      • 如果只有两个锁:
        • 如果这两个锁有自己的写锁,直接返回true
      • 其他情况(多个读锁,两个锁都属于其他事务):都应该等待
    public synchronized boolean grantXLock(TransactionId tid, PageId pid) {
        ArrayList<LockState> list = (ArrayList<LockState>) lockStateMap.get(pid);
        if (list != null && list.size() != 0) {
            if (list.size() == 1) {//如果pid上只有一个锁
                LockState ls = list.iterator().next();
                //如果是自己的写锁,直接返回(在||之前返回),否则加锁再返回(在lock处返回)
                //如果这个锁是别人的,必须等待,也就是在wait处(冒号之后)返回
                return ls.getTid().equals(tid) ? ls.getPerm() == Permissions.READ_WRITE || lock(pid, tid, Permissions.READ_WRITE) : wait(tid, pid);
            } else {
                //多个锁有三种情况,只有第一种情况返回true,其余返回wait
                // 1.两个锁,且都属于tid(一读一写) 2.两个锁,且都属于非tid的事务(一读一写) 3.多个读锁
                if (list.size() == 2) {
                    for (LockState ls : list) {
                        if (ls.getTid().equals(tid) && ls.getPerm() == Permissions.READ_WRITE) {
                            return true;//两个锁而且有一个自己的写锁
                        }
                    }
                }
                return wait(tid, pid);
            }
        } else {//pid上没有锁,可以加写锁
            return lock(pid, tid, Permissions.READ_WRITE);
        }
    }

当我们需要获取一个页面的时候,就需要用到getPage()函数。
getPage()要做的两步是分别获取对应的transaction和page下的锁,不管是读锁还是写锁,这样才有了权限去获取这个页面,然后先从缓存里面找,如果找到了就直接返回,如果没找到,就从磁盘读取。

    public Page getPage(TransactionId tid, PageId pid, Permissions perm)
            throws TransactionAbortedException, DbException, InterruptedException {
        // some code goes here
        boolean result = (perm == Permissions.READ_ONLY) ? lockManager.grantSLock(tid, pid)
                : lockManager.grantXLock(tid, pid);
        //下面的while循环就是在模拟等待过程,隔一段时间就检查一次是否申请到锁了,还没申请到就检查是否陷入死锁
        while (!result) {
            if (lockManager.deadlockOccurred(tid, pid)) {
                throw new TransactionAbortedException();
            }
            Thread.sleep(SLEEP_INTERVAL);
            //sleep之后再次判断result
            result = (perm == Permissions.READ_ONLY) ? lockManager.grantSLock(tid, pid)
                    : lockManager.grantXLock(tid, pid);
        }

        HeapPage page = (HeapPage) lruPagesPool.get(pid);
        if (page != null) {//直接命中
            return page;
        }
        //未命中,访问磁盘并将其缓存
        HeapFile table = (HeapFile) Database.getCatalog().getDbFile(pid.getTableId());
        HeapPage newPage = (HeapPage) table.readPage(pid);
        Page removedPage = lruPagesPool.put(pid, newPage);
        if (removedPage != null) {
            try {
                flushPage(removedPage);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return newPage;
    }

releasePage()相对简单,就是把对应的锁解除了就可以。

    public synchronized void releasePage(TransactionId tid, PageId pid) {
        // some code goes here
        // not necessary for proj1
        if (!lockManager.unlock(tid, pid)) {
            //pid does not locked by any transaction
            //or tid  dose not lock the page pid
            throw new IllegalArgumentException();
        }
    }

holdsLock()也是挺简单的,就是返回状态。

    /**
     * Return true if the specified transaction has a lock on the specified page
     */
    public boolean holdsLock(TransactionId tid, PageId p) {
        // some code goes here
        // not necessary for proj1
        return lockManager.getLockState(tid, p) != null;
    }

Lock Lifetime

实施严格的两阶段锁定。这意味着事务在访问该对象之前应获得对任何对象的相应的锁,并且在事务提交后才释放任何锁.获取锁之后,需要考虑何时释放锁。显然,在提交或中止与事务相关联的事务后,应释放所有与之相关的锁,以确保执行严格的2PL。

BufferPool做好了Page的管理后,HeapFile中获取tuple都需要通过BufferPool.getPage()这个方法来进行,并设置相应的权限。

HeapFileIteratorHeapFileIterator中有:

page = (HeapPage) Database.getBufferPool().getPage(tid, pid, Permissions.READ_ONLY);

HeapFile.insertTuple()实现如下:

    public ArrayList<Page> insertTuple(TransactionId tid, Tuple t)
            throws DbException, IOException, TransactionAbortedException {
        // some code goes here
        ArrayList<Page> affectedPages = new ArrayList<>();
        for (int i = 0; i < numPages(); i++) {
//            HeapPageId pid = new HeapPageId(getId(), i);
            HeapPageId pid = new HeapPageId(getId(), i);
            HeapPage page = null;
            try {
                page = (HeapPage) Database.getBufferPool().getPage(tid, pid, Permissions.READ_WRITE);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if (page.getNumEmptySlots() != 0) {
                //page的insertTuple已经负责修改tuple信息来表明其存储在该page上
                page.insertTuple(t);
                page.markDirty(true, tid);
                affectedPages.add(page);
                break;
            }
        }
        if (affectedPages.size() == 0) {//说明page都已经满了
            //创建一个新的空白的Page
//            HeapPageId npid = new HeapPageId(getId(), numPages());
            HeapPageId npid = new HeapPageId(getId(), numPages());
            HeapPage blankPage = new HeapPage(npid, HeapPage.createEmptyPageData());
            numPage++;
            //将其写入磁盘
            writePage(blankPage);
            //通过BufferPool来访问该新的page
            HeapPage newPage = null;
            try {
                newPage = (HeapPage) Database.getBufferPool().getPage(tid, npid, Permissions.READ_WRITE);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            newPage.insertTuple(t);
            newPage.markDirty(true, tid);
            affectedPages.add(newPage);
        }
        return affectedPages;
        // not necessary for proj1
    }

HeapFile.deleteTuple()的实现如下:

    public Page deleteTuple(TransactionId tid, Tuple t) throws DbException,
            TransactionAbortedException {
        // some code goes here
        PageId pid = t.getRecordId().getPageId();
        HeapPage affectedPage = null;
        for (int i = 0; i < numPages(); i++) {
            if (i == pid.pageNumber()) {
                try {
                    affectedPage = (HeapPage) Database.getBufferPool().getPage(tid, pid, Permissions.READ_WRITE);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                affectedPage.deleteTuple(t);
                affectedPage.markDirty(true, tid);
            }
        }
        if (affectedPage == null) {
            throw new DbException("tuple " + t + " is not in this table");
        }
        return affectedPage;
    }

Implementing NO STEAL

如果脏页被未提交的事务锁定,则不应从缓冲池中清除脏页(这是NO STEAL)
事务的修改仅在提交后才写入磁盘。这意味着我们中止事务时,可以丢弃脏页并从磁盘重新读取它们。因此,在事务未提交的时候,我们不会驱逐脏页。这称为“NO STEAL”。

这一部分在PageLRUCache类中已经实现了页面清除,可以看一下那部分。

Transactions

SimpleDB中,在每个查询的开头会创建一个TransactionId对象。该对象传递给查询中涉及的每个运算符。查询完成后,将调用BufferPooltransactionComplete方法。 调用此方法将提交或中止事务(提交或中止由参数标志commit指定)。在执行过程中的任何时候,当方式发生内部错误或死锁, 操作符可能引发TransactionAbortedException异常。在测试用例中将创建适当的TransactionId对象,以适当的方式将其传递给操作符,并在查询完成后调用transactionComplete。这里需要实现transactionComplete方法。

这一部分主要关注的是事务完成时的持久化和回滚操作,分了两个状态,先把lock释放了,然后根据commit来决定是flushpage还是revert,如果committrue,那意味着事务完成,可以提交,这时候需要把所有的页面写入磁盘,否则,就是事务出现了中止或错误,需要把所有事务回滚,这里的方法就是把所有的页面从磁盘中重新读取进来,从而保证被中止的事务不会造成页面修改,这就是事务的"原子性"的体现,一个事务所做的操作,要么全部完成,要么全部失败回滚.提交时,应将与事务关联的脏页刷新到磁盘。中止时,应通过将页面恢复到其磁盘状态来还原事务所做的任何更改。
最后,无论事务是提交还是中止,都需要释放该事务持有的所有锁。

    /**
     * Commit or abort a given transaction; release all locks associated to
     * the transaction.
     *
     * @param tid    the ID of the transaction requesting the unlock
     * @param commit a flag indicating whether we should commit or abort
     */
    public synchronized void transactionComplete(TransactionId tid, boolean commit)
            throws IOException {
        // some code goes here
        lockManager.releaseTransactionLocks(tid);
        if (commit) {
            flushPages(tid);
        } else {
            revertTransactionAction(tid);
        }
    }
    /**
     * 在事务回滚时,撤销该事务对page造成的改变
     *
     * @param tid
     */
    public synchronized void revertTransactionAction(TransactionId tid) {
        Iterator<Page> it = lruPagesPool.iterator();
        while (it.hasNext()) {
            Page p = it.next();
            if (p.isDirty() != null && p.isDirty().equals(tid)) {
                lruPagesPool.reCachePage(p.getId());
            }
        }
    }

PageLruCache.reCachePage()

    /**
     * 将pid对应的page从磁盘中再次读入,即将其恢复为磁盘中该page的状态
     *
     * @param pid
     */
    public synchronized void reCachePage(PageId pid) {
        if (!isCached(pid)) {
            throw new IllegalArgumentException();
        }
        //访问磁盘获得该page
        HeapFile table = (HeapFile) Database.getCatalog().getDbFile(pid.getTableId());
        HeapPage originalPage = (HeapPage) table.readPage(pid);
        Node node = new Node(pid, originalPage);
        cachedEntries.put(pid, node);
        Node toRemoved = head;
        //这里不需要超出链表尾的判断(toRemoved为null),因为到这里肯定存在该page
        while (!(toRemoved = toRemoved.next).key.equals(pid)) ;
        node.front = toRemoved.front;
        node.next = toRemoved.next;
        toRemoved.front.next = node;
        if (toRemoved.next != null) {
            toRemoved.next.front = node;
        } else {
            //reCache的是尾节点,需要修改tail指针
            tail = node;
        }
    }

Deadlocks and Aborts

有很多可能的方法来检测死锁。可以实施一个简单的超时策略,如果在给定的时间段后未完成事务,则该事务将中止。或者,也可以基于等待图法来实现死锁检测。在此方案中,无论何时尝试授予新的锁(实际上不是无论合适,一般就是获取一个锁不成功,等待一段时间后继续尝试获取),都将在等待图法中检查循环,如果存在循环,则中止某些操作。

在检测到存在死锁之后,必须决定如何改善这种情况。如果在事务t等待锁时检测到死锁。可以选择终止所有造成t等待的交易。这可能会导致大量工作被撤消,但是可以保证t会往下执行。或者,也可以决定中止事务t,以使其他事务有机会继续进行,这样的话后面就需要把事务t重新执行.我们这里选择了后者,在检测到了死锁之后,就抛出一个TransactionAbortedException异常来确保代码在发生死锁时正确中止事务。执行事务的代码(例如TransactionTest.java)会捕获该异常,该代码应在事务完成后调用transactionComplete()进行清理。因此就不用我们来处理这个异常了.

HeapFile.getPage()的实现来看,我们用的是用的是基于等待图法的死锁检测,这个过程是每隔一段时间,如果获取不到一个Page的锁,就检测是否造成了环路等待.

下面是死锁检测的两个重要函数,也是相当重要,需要花点时间才能理解,虽然解释已经非常友好了

     * 通过检测资源的依赖图根据是否存在环来判断是否已经陷入死锁
     * 具体实现:本事务tid需要检测“正在等待的资源的拥有者是否已经直接或间接的在等待本事务tid已经拥有的资源”
     * <p>
     * 如图,括号内P1,P2,P3为资源,T1,T2,T3为事务
     * 虚线以及其上的字母R加上箭头组成了拥有关系,如果是字母W则代表正在等待写锁
     * 例如下图左上方T1到P1的一连串符号表示的是T1此时拥有P1的读锁
     * 图的边缘可以是虚线的转折点,例如为了表示T2正在等待P1
     * <p>
     * //     T1---R-->P1<-------
     * //                       W
     * //  ----------------------
     * //  W
     * //  ---T2---R-->P2<-------
     * //                       W
     * //  ----------------------
     * //  W
     * //  ---T3---R-->P3
     * <p>
     * 上图的含义是,Ti拥有了对Pi的读锁(1<=i<=3)
     * 因为T1在P1上有了读锁,所以T2正在等待P1的写锁
     * 同理,T3正在等待P2的写锁
     * <p>
     * 现在假设的情景是,此时T1要申请对P3的写锁,进入等待,这将会造成死锁
     /**
     * 判断tid是否直接或间接地在等待pids中的某个资源
     *
     * @param tid
     * @param pids
     * @param toRemove 需要排除toRemove来判断,具体原因见方法内部注释;
     *                 事实上,toRemove就是leadToDeadLock()的参数tid,也就是要排除它自己对判断过程的影响
     * @return
     */
    private synchronized boolean isWaitingResources(TransactionId tid, List<PageId> pids, TransactionId toRemove) {
        PageId waitingPage = waitingInfo.get(tid);
        if (waitingPage == null) {
            return false;
        }
        for (PageId pid : pids) {
            if (pid.equals(waitingPage)) {
                return true;
            }
        }
        //到达这里说明tid并不直接在等待pids中的任意一个,但有可能间接在等待
        //如果waitingPage的拥有者们(去掉toRemove)中的某一个正在等待pids中的某一个,说明是tid间接在等待
        List<LockState> holders = lockStateMap.get(waitingPage);
        if (holders == null || holders.size() == 0) return false;//该资源没有拥有者
        for (LockState ls : holders) {
            TransactionId holder = ls.getTid();
            if (!holder.equals(toRemove)) {//去掉toRemove,在toRemove刚好拥有waitingResource的读锁时就需要
                boolean isWaiting = isWaitingResources(holder, pids, toRemove);
                if (isWaiting) return true;
            }
        }
        //如果在for循环中没有return,说明每一个holder都不直接或间接等待pids
        //故tid也非间接等待pids
        return false;
    }

tid就是占领了被请求资源的transactionpids就是请求transaction拥有的所有page,也就是要判断你这个tid是不是在等待pids中的某一个,进入这个函数的缘由是:toRemove这个transaction正在等待获取tid这个transaction所拥有的某个资源,此时这个函数是要判断tid对应的transaction是否也在等待toRemove这个transaction所拥有的某个资源,如果有,说明死锁发生了。

这里用递归函数实现了类似于递归,回溯这样一个查找过程,就跟一条绳子一样,一个transaction一个transaction地往回拉,具体地,在上面的图中,有:

tid就是T3,它的waitingPage就是P2,因为它就是在等待P2的写锁,而T1要请求P3,此时我们要判断的是T3是否直接或间接地在等待T1的哪个page,也就是pids对应的那些页面中的哪一个,当然这里的pids只有P1,于是进入递归函数,显然T3正在等待的页面P2不和pids中的任一个相等,也就是不存在直接等待关系,但是P2的拥有者T2有可能在等呀,因此我们就把P2的所有拥有者列出来,这里就是只有T2,再次进入递归函数,此时我们就要判断T2是否直接或间接在等待pids中的某一个,一看真的是,T2不就在等待P1吗,此时构成了间接等待关系,因此返回true,否则的话还要把T2waitingPage的拥有者都拉出来,看下是不是直接或间接在等待pids中的某个page,这就是递归函数一层层地深入的过程。返回true的意思就是,T3间接在等待T1的资源P1,而T1想要请求T3的资源P3,这就造成了环路等待,死锁发生。关于!holder.equals(toRemove)这个语句,其实是保险起见加的,因为上面的语句:

        for (PageId pid : pids) {
            if (pid.equals(waitingPage)) {
                return true;
            }
        }

其实已经证明了toRemove这个transactionpids中没有waitingPage了,因此waitingPageLockState数组中应该是不会有toRemove的。

     * 导致死锁的本质原因就是将等待的资源(P3)的拥有者(T3)间接的在等待T1拥有的资源(P1)
     * 下面方法的注释以这个例子为基础,具体解释这个方法是如何判断出“T1在P3上的等待已经造成了死锁”的
     *
     * @param tid
     * @param pid
     * @return true表示进入了死锁,false表示没有
     */
    public synchronized boolean deadlockOccurred(TransactionId tid, PageId pid) {//T1为tid,P3为pid
        List<LockState> holders = lockStateMap.get(pid);
        if (holders == null || holders.size() == 0) {
            return false;
        }
        List<PageId> pids = getAllLocksByTid(tid);//找出T1拥有的所有资源,即只含有P1的list
        for (LockState ls : holders) {
            // 这里就是找到占领了当前pid的transaction
            TransactionId holder = ls.getTid();
            //去掉T1,因为虽然上图没画出这种情况,但T1可能同时也在其他Page上有读锁,这会影响判断结果
            // 虽然这一步还是没太看明白,但至少没啥矛盾的,因为本来就是tid要去请求pid嘛,照理说不至于在holder里面已经出现了,但也有可能,所以还是排除掉吧
            if (!holder.equals(tid)) {
                //判断T3(holder)是否直接或间接在等待P1(pids)
                //由图可以看出T3在直接等待P2,而P2的拥有者T2在直接等待P1,即T3在间接等待P1
                boolean isWaiting = isWaitingResources(holder, pids, tid);
                if (isWaiting) {
                    return true;
                }
            }
        }
        return false;
    }

CS186 Project 4: SimpleDB Transactions

上一篇:MySQL-MVCC实现原理


下一篇:deepin下安装MySQL8.0