一、实验预览

lab4要做的是让SimpleDB支持事务，所以实验前需要对事务的基本概念有了解，并知道ACID的特点。lab4是基于严格两阶段*协议去实现原子性和隔离性的，所以开始前也需要了解两阶段*协议是如何实现事务的。对于一致性和持久性，这里假设暂时不会发送断电等异常，所以暂时不需要崩溃恢复，不需要undo log从，后面lab6会有专门的崩溃恢复的解决方案。

事务的基本概念：

A transaction is a group of database actions (e.g., inserts, deletes,
and reads) that are executed atomically; that is, either all of
the actions complete or none of them do, and it is not apparent to an
outside observer of the database that these actions were not completed
as a part of a single, indivisible action.

ACID特性：

To help you understand
how transaction management works in SimpleDB, we briefly review how
it ensures that the ACID properties are satisfied:

• Atomicity: Strict two-phase locking and careful buffer management
  ensure atomicity.
• Consistency: The database is transaction consistent by virtue of
  atomicity. Other consistency issues (e.g., key constraints) are
  not addressed in SimpleDB.
• Isolation: Strict two-phase locking provides isolation.
• Durability: A FORCE buffer management policy ensures
  durability (see Section 2.3 below)

这里提到了ACID在SimpleDB中如何去实现。ACID实现的前提是严格两阶段*协议(Strict two-phase locking)。所以我们需要先了解两阶段*协议。

两阶段*协议

首先是*协议：我们将要求在系统中的每一个事务遵从*协议，*协议的一组规则规定事务何时可以对数据项们进行加锁、解锁。

对于两阶段*协议：两阶段*协议要求每个事务分两个节点提出加锁和解锁申请：

1. 增长阶段：事务可以获得锁，但不能释放锁；
2. 缩减阶段：事务可以释放锁，但不能获得新锁。

最初，事务处于增长阶段，事务根据需要获得锁。一旦该事务释放了锁，它就进入了缩减阶段，并且不能再发出加锁请求。

严格两阶段*协议不仅要求*是两阶段，还要求事务持有的所有排他锁必须在事务提交后方可释放。这个要求保证未提交事务所写的任何数据在该事务提交之前均已排他方式加锁，防止了其他事务读这些数据。

强两阶段*协议。它要求事务提交之前不释放任何锁。在该条件下，事务可以按其提交的顺序串行化。

锁转换：在两阶段*协议中，我们允许进行锁转换。我们用升级表示从共享到排他的转换，用降级表示从排他到共享的转换。锁升级只能发送在增长阶段，锁降级只能发生在缩减阶段。

Recovery and Buffer Management

To simplify your job, we recommend that you implement a NO STEAL/FORCE
buffer management policy.

As we discussed in class, this means that:

• You shouldn’t evict dirty (updated) pages from the buffer pool if they
  are locked by an uncommitted transaction (this is NO STEAL).

  在事务提交前不需要将脏页写回磁盘

• On transaction commit, you should force dirty pages to disk (e.g.,
  write the pages out) (this is FORCE).

  事务提交时将脏页写回磁盘

To further simplify your life, you may assume that SimpleDB will not crash
while processing a transactionComplete command. Note that
these three points mean that you do not need to implement log-based
recovery in this lab, since you will never need to undo any work (you never evict
dirty pages) and you will never need to redo any work (you force
updates on commit and will not crash during commit processing).

因为是在事务提交后才将脏页写入磁盘的，所以不需要实现redo log；

因为我们保证在提交事务的时候不会发送故障，所以不需要实现undo log；

Granting Locks

You will need to add calls to SimpleDB (in BufferPool,
for example), that allow a caller to request or release a (shared or
exclusive) lock on a specific object on behalf of a specific
transaction.

We recommend locking at page granularity; please do not
implement table-level locking (even though it is possible) for simplicity of testing. The rest
of this document and our unit tests assume page-level locking.

You will need to create data structures that keep track of which locks
each transaction holds and check to see if a lock should be granted
to a transaction when it is requested.

You will need to implement shared and exclusive locks; recall that these
work as follows:

• Before a transaction can read an object, it must have a shared lock on it.
• Before a transaction can write an object, it must have an exclusive lock on it.
• Multiple transactions can have a shared lock on an object.
• Only one transaction may have an exclusive lock on an object.
• If transaction t is the only transaction holding a shared lock on
  an object o, t may upgrade
  its lock on o to an exclusive lock.

If a transaction requests a lock that cannot be immediately granted, your code
should block, waiting for that lock to become available (i.e., be
released by another transaction running in a different thread).
Be careful about race conditions in your lock implementation — think about
how concurrent invocations to your lock may affect the behavior.

1.一个事务读一个对象，必须持有共享锁；

2.一个事务写一个对象，必须持有排它锁；

3.多个事务可以对同一个对象加共享锁；

4.一个对象只能被一个事务加排它锁；

5.如果只有一个事务在一个对象上加共享锁，那么共享锁可能升级为排它锁

当一个事务申请锁不能立刻获得，此时应该阻塞。

二、实验过程

Exercise1 Granting Locks

Write the methods that acquire and release locks in BufferPool. Assuming
you are using page-level locking, you will need to complete the following:

• Modify getPage() to block and acquire the desired lock
  before returning a page.
• Implement unsafeReleasePage(). This method is primarily used
  for testing, and at the end of transactions.
• Implement holdsLock() so that logic in Exercise 2 can
  determine whether a page is already locked by a transaction.

You may find it helpful to define a LockManager class that is responsible for
maintaining state about transactions and locks, but the design decision is up to
you.

You may need to implement the next exercise before your code passes
the unit tests in LockingTest.

exercise1需要做的是在getPage获取数据页前进行加锁，这里我们使用一个LockManager来实现对锁的管理，LockManager中主要有申请锁、释放锁、查看指定数据页的指定事务是否有锁这三个功能，其中加锁的逻辑比较麻烦，需要基于严格两阶段*协议去实现。事务t对指定的页面加锁时，思路如下：

1. 锁管理器中没有任何锁或者该页面没有被任何事务加锁，可以直接加读/写锁；

2. 如果t在页面有锁，分以下情况讨论：

   2.1 加的是读锁：直接加锁；

   2.2 加的是写锁：如果锁数量为1，进行锁升级；如果锁数量大于1，会死锁，抛异常中断事务；

3. 如果t在页面无锁，分以下情况讨论：

   3.1 加的是读锁：如果锁数量为1，这个锁是读锁则可以加，是写锁就wait；如果锁数量大于1，说明有很多读锁，直接加；

   3.2 加的是写锁：不管是多个读锁还是一个写锁，都不能加，wait

其它两个就比较容易了。

实现LockManager前需要有一个简单的锁，PageLock主要有两个属性，一个是事务id，一个是锁的类型，在getPage时会传入该事务获取的锁的类型，我们去申请一个新锁时会创建一个PageLock对象，创建时指定锁的类型。实现代码如下：

public class PageLock{
    public static final int SHARE = 0;
    public static final int EXCLUSIVE = 1;
    private TransactionId tid;
    private int type;
    public PageLock(TransactionId tid, int type) {
        this.tid = tid;
        this.type = type;
    }

    public int getType() {
        return this.type;
    }

    public TransactionId getTid() {
        return this.tid;
    }

    public void setType(int type) {
        this.type = type;
    }
}

锁管理器的实现如下：

public class LockManager {

    private ConcurrentMap<PageId, ConcurrentMap<TransactionId, PageLock>> pageLocks;


    public LockManager() {
        pageLocks = new ConcurrentHashMap<>();
    }

    public synchronized boolean requireLock(PageId pid, TransactionId tid, int requireType) throws InterruptedException, TransactionAbortedException {
        final String lockType = requireType == 0 ? "read lock" : "write lock";
        final String thread = Thread.currentThread().getName();

        ConcurrentMap<TransactionId, PageLock> pageLock = pageLocks.get(pid);
        //如果页面上没有锁
        if (pageLocks.size() == 0 || pageLock == null) {
            PageLock lock = new PageLock(tid, requireType);
            pageLock = new ConcurrentHashMap<TransactionId, PageLock>();
            pageLock.put(tid, lock);
            pageLocks.put(pid, pageLock);
            System.out.println(thread + ": the " + pid + " have no lock, transaction" + tid + " require " + lockType + ", accept");
            return true;
        }

        PageLock lock = pageLock.get(tid);
        if (lock != null) {
            if (requireType == PageLock.SHARE) {
                System.out.println(thread + ": the " + pid + " have one lock with same txid, transaction" + tid + " require " + lockType + ", accept");
                return true;
            }
            if (requireType == PageLock.EXCLUSIVE) {
                if (pageLock.size() > 1) {
                    System.out.println(thread + ": the " + pid + " have many read locks, transaction" + tid + " require write lock, abort!!!");
                    throw new TransactionAbortedException();
                }
                if (pageLock.size() == 1 && lock.getType() == PageLock.EXCLUSIVE) {
                    System.out.println(thread + ": the " + pid + " have write lock with same txid, transaction" + tid + " require " + lockType + ", accept");
                    return true;
                }
                if (pageLock.size() == 1 && lock.getType() == PageLock.SHARE) {
                    lock.setType(PageLock.EXCLUSIVE);
                    pageLock.put(tid, lock);
                    pageLocks.put(pid, pageLock);
                    System.out.println(thread + ": the " + pid + " have read lock with same txid, transaction" + tid + " require write lock, accept and upgrade!!!");
                    return true;
                }
            }
        }

        if (lock == null) {
            if (requireType == PageLock.SHARE) {
                if (pageLock.size() > 1) {
                    //有很多读锁，请求新的读锁
                    PageLock l = new PageLock(tid, requireType);
                    pageLock.put(tid, l);
                    pageLocks.put(pid, pageLock);
                    System.out.println(thread + ": the " + pid + " have many read locks, transaction" + tid + " require " + lockType + ", accept and add a new read lock");
                    return true;
                }
                PageLock one = null;
                for (PageLock l : pageLock.values()) {
                    one = l;
                }
                if (pageLock.size() == 1 && one.getType() == PageLock.SHARE) {
                    PageLock l = new PageLock(tid, requireType);
                    pageLock.put(tid, l);
                    pageLocks.put(pid, pageLock);
                    System.out.println(thread + ": the " + pid + " have one read lock with diff txid, transaction" + tid + " require read lock, accept and add a new read lock");
                    return true;
                }
                if (pageLock.size() == 1 && one.getType() == PageLock.EXCLUSIVE) {
                    System.out.println(thread + ": the " + pid + " have one write lock with diff txid, transaction" + tid + " require read lock, await...");
                    wait(50);
                    return false;
                }
            }
            if (requireType == PageLock.EXCLUSIVE) {
                System.out.println(thread + ": the " + pid + " have lock with diff txid, transaction" + tid + " require write lock, await...");
                wait(10);
                return false;
            }
        }
        //不可能到这里，如果到这里了，需要检查一下你加锁的思路对不对
        System.out.println("===========================other case=====================================");
        return true;
    }

    /**
     * 查看指定页面是否被指定事务锁定
     * @param pid
     * @param tid
     * @return
     */
    public synchronized boolean isHoldLock(PageId pid, TransactionId tid) {
        ConcurrentMap<TransactionId, PageLock> map = pageLocks.get(pid);
        if (map == null) return false;
        return map.get(tid) != null;
    }

    /**
     * 释放指定页面的指定事务加的锁
     * @param pid
     * @param tid
     */
    public synchronized void releaseLock(PageId pid, TransactionId tid) {
        final String thread = Thread.currentThread().getName();
        ConcurrentMap<TransactionId, PageLock> map = pageLocks.get(pid);
        if (map == null) return;
        if (tid == null) return;
        PageLock lock = map.get(tid);
        if (lock == null) return;
        final String lockType = map.get(tid).getType() == 0 ? "read lock" : "write lock";
        map.remove(tid);
        System.out.println(thread + " release " + lockType + " in " + pid + ", the tx lock size is " + map.size() + ", the txid is " + tid);
        if (map.size() == 0) {
            pageLocks.remove(pid);
            System.out.println( thread + " release last lock, the page " + pid + " have no lock, the page locks size is " + pageLocks.size() + " the txid is " + tid );
        }
        this.notifyAll();
    }

    public synchronized void completeTransaction(TransactionId tid) {
        Set<PageId> ids = pageLocks.keySet();
        for (PageId pageId : ids) {
            releaseLock(pageId, tid);
        }
    }
}

其中锁管理器的代码是lab4整个实验的核心，后续的exercise基本都是基于这个锁管理器去做的，所以这里必须要考虑清楚各种情况，把思路整理清楚再写代码。

getPage加锁：

public synchronized  Page getPage(TransactionId tid, PageId pid, Permissions perm)
        throws TransactionAbortedException, DbException {
        // some code goes here
        int type = 0;
        if (perm == Permissions.READ_ONLY) {
            type = 0;
        } else {
            type = 1;
        }
        long st = System.currentTimeMillis();
        while (true) {
            //获取锁，如果获取不到会阻塞
            try {
                if (lockManager.requireLock(pid, tid, type)) {
                    break;
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            long now = System.currentTimeMillis();
            if (now - st > 500) throw new TransactionAbortedException();
        }
        if(!pageCache.containsKey(pid.hashCode())) {
            DbFile dbFile = Database.getCatalog().getDatabaseFile(pid.getTableId());
            Page page = dbFile.readPage(pid);
            pageCache.put(pid.hashCode(), page);
        }
        return pageCache.get(pid.hashCode());
    }

这里包括了exercise5的死锁解决方案，采用超时中断事务的方式去解决死锁，具体exercise5再讲清楚。

Exercise2 Lock Lifetime

exercise2主要是要让我们考虑什么时候要加锁，什么时候要解锁，其实和exercise1是连成一块的。

Ensure that you acquire and release locks throughout SimpleDB. Some (but
not necessarily all) actions that you should verify work properly:

• Reading tuples off of pages during a SeqScan (if you
  implemented locking in BufferPool.getPage(), this should work
  correctly as long as your HeapFile.iterator() uses
  BufferPool.getPage().)
• Inserting and deleting tuples through BufferPool and HeapFile
  methods (if you
  implemented locking in BufferPool.getPage(), this should work
  correctly as long as HeapFile.insertTuple() and
  HeapFile.deleteTuple() use
  BufferPool.getPage().)

You will also want to think especially hard about acquiring and releasing
locks in the following situations:

• Adding a new page to a HeapFile. When do you physically
  write the page to disk? Are there race conditions with other transactions
  (on other threads) that might need special attention at the HeapFile level,
  regardless of page-level locking?
• Looking for an empty slot into which you can insert tuples.
  Most implementations scan pages looking for an empty
  slot, and will need a READ_ONLY lock to do this. Surprisingly, however,
  if a transaction t finds no free slot on a page p, t may immediately release the lock on p.
  Although this apparently contradicts the rules of two-phase locking, it is ok because
  t did not use any data from the page, such that a concurrent transaction t’ which updated
  p cannot possibly effect the answer or outcome of t.

主要是让我们检查一下前面申请锁的时候，使用getPage方法获取数据页时申请锁，传入的锁类型是否正确。insertTuple应该是读写模式：

deleteTuple也应该是读写模式：

除了上述要的点，一个额外的点是：当我们要插入一个元组时，会去找到一个有空的slot的page，但是当我们获取的page没有空的slot了，我们应该立即释放在这个page的锁，即使这样会不符合严格二阶段*协议，但后续我们不会再使用到这个page了，所以并没有影响，这样能够让其它事务可以访问该page：

测试用例：

Exercise3 Implementing NO STEAL

Modifications from a transaction are written to disk only after it
commits. This means we can abort a transaction by discarding the dirty
pages and rereading them from disk. Thus, we must not evict dirty
pages. This policy is called NO STEAL.

You will need to modify the evictPage method in BufferPool.
In particular, it must never evict a dirty page. If your eviction policy prefers a dirty page
for eviction, you will have to find a way to evict an alternative
page. In the case where all pages in the buffer pool are dirty, you
should throw a DbException. If your eviction policy evicts a clean page, be
mindful of any locks transactions may already hold to the evicted page and handle them
appropriately in your implementation.

前面我们提到，为了支持原子性，我们对脏页的处理是在事务提交时才写入磁盘，或者事务中断时将脏页恢复成磁盘文件原来的样子。在之前我们实现的LRU缓存淘汰策略中，我们并没有对脏页加以区分。exercise4要我们在淘汰数据页时不能淘汰脏页，如果bufferpool全部是脏页则抛出异常，我们只需要修改淘汰页面时的代码：

Exercise4 Transactions

In SimpleDB, a TransactionId object is created at the
beginning of each query. This object is passed to each of the operators
involved in the query. When the query is complete, the
BufferPool method transactionComplete is called.

Calling this method either commits or aborts the
transaction, specified by the parameter flag commit. At any point
during its execution, an operator may throw a
TransactionAbortedException exception, which indicates an
internal error or deadlock has occurred. The test cases we have provided
you with create the appropriate TransactionId objects, pass
them to your operators in the appropriate way, and invoke
transactionComplete when a query is finished. We have also
implemented TransactionId.

SimpleDB是如何实现事务的？

在SimpleDB中，每个事务都会有一个Transaction对象，我们用TransactionId来唯一标识一个事务，TransactionId在Transaction对象创建时自动获取。事务开始前，会创建一个Transaction对象，后续的操作会通过传递TransactionId对象去进行，加锁时根据加锁页面、锁的类型、加锁的事务id去进行加锁。当事务完成时，调用transactionComplete去完成最后的处理。transactionComplete会根据成功还是失败去分别处理，如果成功，会将事务id对应的脏页写到磁盘中，如果失败，会将事务id对应的脏页淘汰出bufferpool或者从磁盘中获取原来的数据页。脏页处理完成后，会释放事务id在所有数据页中加的锁。

transactionComplete实现如下：

 public synchronized 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 {
            //如果提交失败，回滚，将脏页的原页面写回磁盘
            recoverPages(tid);
        }
        lockManager.completeTransaction(tid);
    }

recoverPages可以根据自己的喜好选择直接淘汰还是从磁盘中恢复，个人觉得前者好一些，用到的时候再去获取。

测试用例AbortEvictionTest：

测试用例TransactionTest：

Exercise5 Deadlocks and Aborts

It is possible for transactions in SimpleDB to deadlock (if you do not
understand why, we recommend reading about deadlocks in Ramakrishnan & Gehrke).
You will need to detect this situation and throw a
TransactionAbortedException.

There are many possible ways to detect deadlock. A strawman example would be to
implement a simple timeout policy that aborts a transaction if it has not
completed after a given period of time. For a real solution, you may implement
cycle-detection in a dependency graph data structure as shown in lecture. In this
scheme, you would check for cycles in a dependency graph periodically or whenever
you attempt to grant a new lock, and abort something if a cycle exists. After you have detected
that a deadlock exists, you must decide how to improve the situation. Assume you
have detected a deadlock while transaction t is waiting for a lock. If you’re
feeling homicidal, you might abort all transactions that t is
waiting for; this may result in a large amount of work being undone, but
you can guarantee that t will make progress.
Alternately, you may decide to abort t to give other
transactions a chance to make progress. This means that the end-user will have
to retry transaction t.

Another approach is to use global orderings of transactions to avoid building the
wait-for graph. This is sometimes preferred for performance reasons, but transactions
that could have succeeded can be aborted by mistake under this scheme. Examples include
the WAIT-DIE and WOUND-WAIT schemes.

什么时候会发生死锁？

1.如果两个事务t0,t1，两个数据页p0,p1，t0有了p1的写锁然后申请p0的写锁，t1有了p0的写锁然后申请p1的写锁，这个时候会发生死锁；

2.如果多个事务t0,t1,t2,t3同时对数据页p0都加了读锁，然后每个事务都要申请写锁，这种情况下只能每一个事务都不可能进行锁升级，所以需要有其中三个事务进行中断或者提前释放读锁，由于我们实现的是严格两阶段*协议，这里只能中断事务让其中一个事务先执行完。

死锁的解决方案？一般有两种解决方案：

1.超时。对每个事务设置一个获取锁的超时时间，如果在超时时间内获取不到锁，我们就认为可能发生了死锁，将该事务进行中断。

2.循环等待图检测。我们可以建立事务等待关系的等待图，当等待图出现了环时，说明有死锁发生，在加锁前就进行死锁检测，如果本次加锁请求会导致死锁，就终止该事务。

我实现的是较为简单的第一种方案：

测试用例：

三、踩坑记录

这是一个前面lab2留下的坑导致了debug一个星期的故事。。。。

前面写lab2的时候，需要完成一个HeapFile的迭代器，当时没有考虑到事务，为了减少全表扫描的次数，我这里错误的用上了单例。导致后面多线程时，一个线程用了这个iterator去遍历完所有tuple，然后next的值已经没有了，然后另外一个线程以为这是自己的iterator，才刚刚open，然后调用next的时候就会跑NoSuchElementException了。前面debug的时候以为是锁的实现有问题，尝试着违背两阶段*协议自己在一些case下去解锁，然后发现都过不了。然后就是不断的加日志，调整日志格式，debug，最后发现都过不了TransactionTest多个线程的用例，最多只能过两个线程。然后昨晚又整理了一遍加锁的思路，加锁的代码重新写了一遍，然后日志又重新打了一遍。早上调代码的时候意外发现这个问题：

当时一开始以为两个线程竟然可以有同个事务id，用同个事务id进行加读锁，后面看了下加锁的日志发现是根本不是这回事。然后就跟踪出现这个问题的代码，发现是迭代器的问题。修改后的代码：

整个过程可能有其它的bug，但是在调试这个小问题的时候不断的打日志，确保每一个环节不出错，整理思路，重写代码，在最后发现这个问题的时候，修改完也就顺利通过了。开心！！！

四、实验总结

lab4主要是让SimpleDb支持事务，一开始需要先去了解两阶段*协议，然后根据讲义写出加锁的思路，exercise1加锁是整个实验的重点也是难点。但说难也没有那么难，主要是得思路清晰，然后写代码的时候把各种情况考虑清楚。一开始写的时候完全没有想到多个读锁时申请写锁会死锁，后面和别人交流才发现了这种情况。锁管理器的完成程度很大程度能够决定后面exercise的代码难易。然后就是多线程调试的问题，前面lab2挖的坑在这里没发现，导致调了好久好久，整个过程不断重复加锁的思路，然后不断完善日志信息，调代码，有时候一些情况需要多试几遍才会出现，这也导致调代码的困难。这个实验感觉收获最多的调试代码的技巧，当然数据库的知识也很多，深深体会到写代码时加上清晰的日志的重要性。一开始对日志没有啥概念，就是简单的打印想要的信息，后面发现所有的日志都应该有个统一的格式，这样观察起来会方便很多。调代码的过程也尝试去打破两阶段*协议去解锁，最后发现都是失败，因为最核心的点没有找到。幸运的是最后找到了问题，整个人也开心了好多，晚上可以安心刷题了hhh。

实验时间：2021.10.17-2021.10.27

报告撰写时间：2021.10.27