Replicating gradescope tests locally
The code can be compiled using Maven; the following command generates a jar file for the entire project,
mvn packageYou can simulate what the grader machines will do by running the autograder script as follows:
java -Xmx1536m -Xms1536m -jar target/tests.jar This will output a json file that should match the graded tests run on gradescope.
Submitting your solution
Run
create_submission.shThis will create a file student_submission.zip that you should upload to gradescope.
Alternatively, just make a zip file containing only TransactionManager.java with no directory structure and upload that.
Teaching Staff Autograder Setup
Create Autograder files and upload zip archive to Gradescope.
bash make_autograder.sh实现思路
采用的Commit Logging这种事务的实现方式，在《凤凰架构》的本地事务这一节里边也有提到。简单来说：
所有对数据的真实修改都必须发生在事务提交以后，即日志写入了 Commit Record 之后。
我的实现中，用LogRecord对象来表示一行日志记录，记录的类型其实只需要两种，一种是写操作（OPS）；另一种是提交操作（COMMIT），表示整个事务已经完成持久化。对于读操作是不需要开启事务的，因为返回的是latestValues中的值，而更新其中的值是确保在事务完成提交之后：
Returns the latest committed value for a key by any transaction.（来自
TransactionManager#read()注释）
代码实现当中比较重要的是commit()和initAndRecover()，分别代表提交和崩溃恢复。我在实现writePersisted()过程中费了不少功夫，后边看了这个仓库中对这个部分的实现才有了思路。
总流程
首先得明确事务的持久化过程，在这个课程的PPT中有详细的描述。简单来说：1️⃣ start；2️⃣ 写记录；3️⃣ commit，表明这个事务成功落盘，完成了持久化(persist)。整个过程是顺序追加写入磁盘文件的，这是比较高效的写磁盘的方式。完成上边三步并不意味着这个事务圆满完成了，此时事务中的操作还没有被应用(apply)到数据库中，即没有真正修改具体的数据。apply过程不要求实现，在StorageManager中已经提供好了，但会在apply后回调writePersist()，这是需要实现的。
编码 解码
因为日志（log）在LogManager中是以byte数组(byte[])的形式持久化的，所以编码、解码日志信息稍微有一点点麻烦。首先需要知道持久化LogRecord中的字段以及这些字段的大小，因为LogRecord实例有两种类型，对于COMMIT类型，不会有key和value两个值，但为了处理方便，在创建COMMIT类型的LogRecord实例时，我为这两个字段设置了缺省，这样在编/解码时就不存在空指针异常了。
第二个需要注意的点是在崩溃恢复(initAndRecover())时，需要读取并解码LogRecord，则需要确定每一个记录的边界，也就是每一个LogRecord的size。我直接把这个值存放在每一个记录对应的byte[]的最开始的四个字节。这是我能想到的最简便的方式，我看到别的实现中要进行移位感觉稍微有些复杂。
实现commit()
接下来说说重头戏commit()（提交事务）和initAndRecover()（崩溃恢复）。commit()的思路比较直白，可以细分为两个子过程，persist 和apply。persist过程是将整个事务日志持久化，首先为该事务（如T1）写下<T1,commit>（即commit record，如上图），然后将整个事务落盘。“写下<T1,commit>”是非常关键的步骤，在崩溃恢复时，判断哪些日志需要恢复的依据就是这一条记录，拥有这一条记录的事务才能被认为需要被恢复的。
persist子过程中，调用LogManager#appendLogRecord()会返回在添加这条记录之前日志的长度，换句话说，就是这条记录在日志中的起始位置（以下称为offset），这个值会被作为TaggedValue中的tag，也就是每一个value都会有一个tag，我觉得这实际上是为每一个key对应的value加上一个版本。因为看了StorageManagerImpl的源码会发现其实为一个key更新了一个value后旧的value是不会被删除的，而是被保留在版本链上。对这个版本链上的各个value做区分的方式就通过tag，而用offset作为tag的好处在于，越新的版本会越后写入log，对应的offset值就越大。
apply子过程除了更新数据库以外（StorageManager#queueWrite()），还需要更新latestValues，注意这个过程是一定要在persist子过程之后发生，以确保这些数据已被持久化。
实现initAndRecover()
initAndRecover()的实现最重要的是committedTxn变量，用来记录哪些事务需要做恢复的。依据是：一个记录（LogRecord实例）的类型是COMMIT，那么这个记录对应的事务就需要被恢复。有种情况也是有可能发生的：假如一个事务有7个写入操作，即7个LogRecord实例，在只apply了前三个后发生崩溃，在恢复的时候因为这个事务还有COMMIT记录在日志（log）中，此时还会接着恢复剩下的4个记录，也就是说，存在一个事务一部分被commit并apply了，而一部分没有的情况。这种情况应该没啥问题，因为Commit Logging这种事务实现方式（准确是是原子性和持久性实现方式），是不会在commit之前真正修改数据的，并不像WAL（write ahead logging），会在commit之前就对数据信息了修改。
实现writePersisted()
writePersisted()实现是我纠结最久的地方，核心问题是什么时候truncate log？我最开始的思维非常粗暴，只要persisted_tag参数的值是大于LogManager的logTruncationOffset属性就可以，这样的做法有个很明显的问题：更新数据库中的值（apply过程）是并发的，也就是说，tag值高的（也即offset值高的），有可能会先于tag值低的被apply到数据库中，这种情况下，低tag值的log record会在还没有确保被apply之前就被truncate掉（logTruncationOffset>该record的tag值），在数据库没有崩溃是还好，但崩溃恢复时只会从logTruncationOffset开始加载record，这时便不可能恢复到这个record了。最后的实现思路是参考了这个仓库，确保被truncate的offset是由小到大进行的。