MIT 6.830 Lab6
这个Lab要求实现SimpleDB的日志系统，能够支持回滚和崩溃恢复。
在Lab 4实现事务的时候，是在假设不发生故障的情况下完成的，BufferPool采用的是no-steal/force的策略，现在考虑到可能会发生的故障或者数据丢失情况，要将策略换成steal/no-force。两者的区别如下：
(no) steal：是否允许一个uncommitted的事务将修改更新到磁盘中。
若是steal策略，则磁盘上可能就包含uncommitted的数据，因此系统需要记录undo log，当事务发生abort时进行rollback；
若是no-steal策略，则磁盘上不可能存在uncommitted的数据，因此无需记录undo log。
(no) force：是否在事务committed之后立即持久化到磁盘。
若是force策略，事务在committed后会将所有更新立即持久化到磁盘，这样会导致磁盘发生很多小的写操作；
若是no-force策略，事务在committed后不会立即将更新持久化到磁盘，这样可以降低磁盘的写次数，但如果发生crash，那么未能持久化到磁盘的committed数据就会丢失，因此需要记录undo log，在系统重启时进行前滚roll forward。
为了支持steal/no-force策略，需要维护一个日志系统。
在SimpleDB中，undo log和redo log是合在一起的，都是update类型的日志。
对于redo log，其会记录事务操作的变化，在每次将数据页写入磁盘前用logWrite()方法来记录变化。这样，对于这些脏页，即使故障丢失了，也可以通过事务ID来判断其是否已经提交。若已提交，则重启时根据日志的内容即可恢复。
对于undo log，采用的方法是在Heap Page中保存一份旧数据：
事务提交时，对旧数据进行更新。当新事务回滚时，由于采用的是steal策略，脏页可能在页面淘汰时就已经写入磁盘了，因此可利用before image，即oldData（上一次成功事务的数据），就可以恢复到此次事务开始前的状态，实现事务的回滚。
根据Lab文档，可知SimpleDB的日志共有5种：ABORT、COMMIT、UPDATE、BEGIN、CHECKPOINT，分别用来记录事务失败、事务提交、写入磁盘前的脏页、事务开始、检测点五类事件，这些格式的日志都记在一个文件中，通用格式如下：
ABORT、COMMIT、BEGIN这三种日志中间的content部分是空的；
UPDATE的日志由两部分组成，即before image和after image，分别记录修改前和修改后的日志。事务提交失败进行回滚时会用before image，事务提交成功但数据丢失会用after image；
CHECKPOINT日志主要记录在检测点处活跃的事务数，以及每个活跃事务的ID和第一条日志记录的偏移量；在崩溃恢复时，checkpoint前的修改是已经写入磁盘的，因此只需要从checkpoint往后读，根据日志记录进行数据恢复即可。
roll back是undo log完成的事，即提供上一个版本的快照，在回滚时将上一个版本的数据写回磁盘，思路如下：
- 根据
tidToFirstLogRecord获取该事务第一条记录的位置
- 移动到日志开始的地方
- 根据日志格式读取记录，读到update格式的记录时根据事务ID判断是否为要修改的日志，若是，则写before image
- 若是checkpoint日志，则直接跳过
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
| public void rollback(TransactionId tid)
throws NoSuchElementException, IOException {
synchronized (Database.getBufferPool()) {
synchronized (this) {
preAppend();
long tidId = tid.getId();
rollback(tidId);
}
}
}
public void rollback(Long tidId) throws IOException{
Long begin = tidToFirstLogRecord.get(tidId);
raf.seek(begin);
while (true){
try {
int type = raf.readInt();
long curId = raf.readLong();
if (curId != tidId){
if (type == 3){
readPageData(raf);
readPageData(raf);
}
} else {
if (type == 3){
Page before = readPageData(raf);
Page after = readPageData(raf);
DbFile dbFile = Database.getCatalog().getDatabaseFile(before.getId().getTableId());
dbFile.writePage(before);
Database.getBufferPool().removePage(after.getId());
raf.seek(raf.getFilePointer() + 8);
break;
}
}
raf.seek(raf.getFilePointer() + 8);
} catch (EOFException e){
break;
}
}
}
|
recovery是redo log要完成的任务。实现思路如下：
从日志文件中，可以获取到checkpoint所在的位置。然后对checkpoint后面的日志记录进行读取并恢复数据。
- 对于未提交的事务，使用before image进行恢复
- 对于已提交的事务，使用after image进行恢复
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
| public void recover() throws IOException {
synchronized (Database.getBufferPool()) {
synchronized (this) {
Map<Long, List<Page[]>> map = new HashMap<>();
raf.seek(0);
print();
long checkPoint = raf.readLong();
if (checkPoint != -1){
Map<Long, Long> pos = new HashMap<>();
raf.seek(checkPoint);
raf.seek(raf.getFilePointer() + 12);
int num = raf.readInt();
while (num > 0){
long curId = raf.readLong();
long off = raf.readLong();
pos.put(curId, off);
num--;
}
for (Long i : pos.keySet()){
raf.seek(pos.get(i));
recoverSearch(raf, map);
}
} else {
System.out.println(raf.getFilePointer() + "-------------");
recoverSearch(raf, map);
}
for (Long tid : map.keySet()){
Page[] pages = map.get(tid).get(0);
Page before = pages[0];
DbFile dbFile = Database.getCatalog().getDatabaseFile(before.getId().getTableId());
dbFile.writePage(before);
}
map.clear();
}
}
}
public void recoverSearch(RandomAccessFile raf, Map<Long, List<Page[]>> map) throws IOException{
while (true){
try {
int type = raf.readInt();
long curId = raf.readLong();
if (type == 3){
if (!map.containsKey(curId)){
map.put(curId, new ArrayList<>());
}
Page before = readPageData(raf);
Page after = readPageData(raf);
Page[] pages = new Page[2];
pages[0] = before;
pages[1] = after;
map.get(curId).add(pages);
} else if (type == 2 && map.containsKey(curId)){
Page[] pages = map.get(curId).get(map.get(curId).size() - 1);
Page before = pages[0];
Page after = pages[1];
DbFile dbFile = Database.getCatalog().getDatabaseFile(before.getId().getTableId());
dbFile.writePage(after);
map.remove(curId);
} else if (type == 1 && map.containsKey(curId)){
Page[] pages = map.get(curId).get(0);
Page before = pages[0];
Page after = pages[1];
DbFile dbFile = Database.getCatalog().getDatabaseFile(before.getId().getTableId());
dbFile.writePage(before);
map.remove(curId);
}
raf.seek(raf.getFilePointer() + 8);
} catch (EOFException e){
break;
}
}
}
|
