MIT 6.830 Lab4
这个Lab需要实现数据库的事务处理和并发相关的功能。
事务是数据库中一组原子操作的集合，具有ACID四个特性。
数据库一般采用锁来实现事务的这些特性，具体可分为共享锁和互斥锁：
- 若一个事务要对一个对象进行读操作，则必须持有其的共享锁
- 若一个事务要对一个对象进行写操作，则必须持有其的互斥锁
- 多个事务可以同时持有一个对象的共享锁，而同一时间只有一个事务可以持有某对象的互斥锁
- 若只有一个事务拥有某对象的共享锁，则该锁自动升级为互斥锁
上面的对象根据粒度的不同而不同，可以是一个表，一个页，一个元组；在这个Lab中，只考虑页级锁。
同时在申请锁的时候，如果一个事务需要的锁不能立即获得，那么它就需要进入阻塞状态，直到被分配到所需要的锁，数据库系统中一般会有一个专门管理锁的分配和释放的组件，可以称之为LockManager。
另外，要实现ACID，必须遵循两阶段锁协议（Two Phase Locking，2PL）。
增长阶段：事务可以获得锁，但不能释放锁；
缩减阶段：事务可以释放锁，但不能获得新锁。
相对地，严格两阶段锁协议（S2PL）对于锁的封锁要求不仅只在两个阶段，还要求事务持有的所有互斥锁必须在事务commit后才可释放。这样能保证执行过程中不出现死锁的情况。
另外，增长阶段共享锁可以升级为互斥锁，缩减阶段互斥锁可以降级为共享锁。
LockManager的详细实现如下：
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| public class LockManager {
private Map<Integer, List<Lock>> map;
public LockManager(){
this.map = new ConcurrentHashMap<>();
}
public synchronized Boolean acquireLock(TransactionId tid, PageId pageId, Permissions permissions){
Integer pid = pageId.getPageNumber();
Lock lock = new Lock(permissions, tid);
List<Lock> lockList = map.get(pid);
if(lockList == null){
lockList = new ArrayList<>();
lockList.add(lock);
map.put(pid, lockList);
return true;
}
if(lockList.size() == 1){
Lock firstLock = lockList.get(0);
if(firstLock.getTransactionId().equals(tid)){
if(firstLock.getPermissions().equals(Permissions.READ_ONLY) && lock.getPermissions().equals(Permissions.READ_WRITE)){
firstLock.setPermissions(Permissions.READ_WRITE);
}
return true;
} else {
if(firstLock.getPermissions().equals(Permissions.READ_ONLY) && lock.getPermissions().equals(Permissions.READ_ONLY)){
lockList.add(lock);
return true;
}
return false;
}
}
if(lock.getPermissions().equals(Permissions.READ_WRITE)){
return false;
}
for (Lock lock1 : lockList){
if(lock1.getTransactionId().equals(tid)){
return true;
}
}
lockList.add(lock);
return true;
}
public synchronized void releaseLock(TransactionId tid, PageId pageId){
List<Lock> lockList = map.get(pageId.getPageNumber());
for (int i=0; i<lockList.size(); i++){
Lock lock = lockList.get(i);
if(lock.getTransactionId().equals(tid)){
lockList.remove(lock);
if(lockList.size() == 0){
map.remove(pageId.getPageNumber());
}
return;
}
}
}
public synchronized void releaseAllLock(TransactionId tid){
for (Integer k : map.keySet()){
List<Lock> lockList = map.get(k);
for (int i=0; i<lockList.size(); i++){
Lock lock = lockList.get(i);
if(lock.getTransactionId().equals(tid)){
lockList.remove(lock);
if(lockList.size() == 0){
map.remove(k);
}
break;
}
}
}
}
public synchronized Boolean holdLock(TransactionId tid, PageId pageId){
List<Lock> lockList = map.get(pageId.getPageNumber());
for (int i=0; i<lockList.size(); i++){
Lock lock = lockList.get(i);
if(lock.getTransactionId().equals(tid)){
return true;
}
}
return false;
}
}
|
然后需要在原来的BufferPool代码上稍作修改，完善各个函数对页操作的加锁开锁步骤。例如，在getPage()时先获取当前Page的锁：
1
| lockAcquired = lockManager.acquireLock(tid, pid, perm);
|
这一项主要是注意使用getPage()方法时，申请的锁类型是否正确，即READ_WRITE和READ_ONLY的选择。
No Steal指的是在rollback的情况下，不允许从脏页中「steal」数据，即在事务提交时才将脏页写入磁盘或者事务中断时将脏页恢复成磁盘文件原来的样子。
在之前的Lab中，实现了基于LRU的页置换算法，但并没有区分脏页。现在不能像之前一样淘汰这些脏页。
当BufferPool满时，会调用evictPage()。那么，就从现在LRU的缓存中倒序遍历，淘汰第一个「脏标记」为空的页即可。
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
| private synchronized void evictPage() throws DbException {
Page value = lruCache.getTail().prev.value;
if (value != null && value.isDirty() != null){
findNotDirty();
} else {
lruCache.discard();
}
}
private void findNotDirty() throws DbException{
LRUCache<PageId, Page>.DLinkedNode head = lruCache.getHead();
LRUCache<PageId, Page>.DLinkedNode tail = lruCache.getTail();
tail = tail.prev;
while (head != tail){
Page value = tail.value;
if (value != null && value.isDirty() == null){
lruCache.remove(tail);
return;
}
tail = tail.prev;
}
throw new DbException("All dirty pages");
}
|
每个事务都有一个Transaction对象，SimpleDB用TransactionId来唯一标识一个事务。
事务开始之前，会创建一个Transaction对象，TransactionId此时也会自动获取。
当事务完成后，调用transactionComplete完成收尾处理工作。其会根据事务执行的成功与否分别进行处理，若事务执行成功，则将事务ID对应的脏页写入到磁盘中，若事务执行失败，则将事务ID对应的脏页淘汰出BufferPool并从磁盘中获取原来的数据页。
最后，释放该事务在所有数据页中加的锁。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void transactionComplete(TransactionId tid, boolean commit) {
if (commit){
try {
newFlushPages(tid);
} catch (IOException e){
e.printStackTrace();
}
} else {
rollback(tid);
}
lockManager.releaseAllLock(tid);
}
|
死锁的产生情况：
- 若有两个事务t0和t1，两个数据页p0和p1，t0有了p1的写锁后申请p0的写锁，t1有了p0的写锁后申请p1的写锁，发生死锁
- 若多个事务t0，t1，t2，t3都同时对数据页p0加了读锁，然后每个事务都要申请写锁，发生死锁
解决方案：
- 超时处理。对每个事务设置一个获取锁的时限，若超过该时限，事务仍未获得锁，则认为死锁，将该事务中断
- 循环等待图检测。建立事务等待的关系图，若该图中出现了环，则有死锁发生。在加锁前就进行检测，若此次申请会造成环，则终止该事务。
实现时采用了较为简单的第一种方案。
1
2
3
4
5
6
7
| while(!lockAcquired){
long now = System.currentTimeMillis();
if(now - start > timeout){
throw new TransactionAbortedException();
}
lockAcquired = lockManager.acquireLock(tid, pid, perm);
}
|
