OVERVIEW

概览

The fourth programming project is to implement Logging, Recovery, and Checkpoints in your database system. The first task is to implement write ahead logging (WAL) under No-Force/Steal buffering policy and log every single page-level write operation and transaction command. The second task is to implement a recovery mechanism, which will allow the the database to reconstruct itself from the log. The final task is to implement a simple, blocking checkpointing mechanism that generates fully consistent checkpoints.
这个项目的第四个编程任务是在你的数据库系统中实现日志记录、恢复和检查点。第一个任务是在无强制/抢占缓冲策略下实现预写式日志（WAL），并记录每个单独的页面级写操作和事务命令。第二个任务是实现恢复机制，允许数据库从日志中重建自身。最后一个任务是实现一个简单的阻塞检查点机制，生成完全一致的检查点。

The project is comprised of the following two tasks:
该项目由以下三个任务组成：

  • Task #1 - Log Manager
    任务＃1 - 日志管理器

  • Task #2 - System Recovery
    任务＃2 - 系统恢复

  • Task #3 - Checkpoints
    任务＃3 - 检查点

This is a single-person project that will be completed individually (i.e., no groups).
这是一个单人项目，需要独立完成（即没有小组）。

Please post all of your questions about this project on Piazza. Do not email the TAs directly with questions. The instructor and TAs will not debug your code. You may verbally describe test cases on Piazza, but do not post an excessive amount of testing code on Piazza either.
请在 Piazza 上发布有关该项目的所有问题。请勿直接通过电子邮件与助教联系。教师和助教不会调试您的代码。您可以口头描述测试用例，但请不要在 Piazza 上发布过多的测试代码。

Release Date: Nov 15, 2019
发布日期：2019年11月15日

Due Date: Dec 10, 2019 @ 11:59pm
截止日期：2019年12月10日 @ 11:59pm

PROJECT SPECIFICATION

项目规范

Like the previous project, we are providing you with stub classes that contain the API that you need to implement. You should not modify the signatures for the pre-defined functions in these classes. If you do this, then it will break the test code that we will use to grade your assignment you end up getting no credit for the project. If a class already contains certain member variables, you should not remove them. You may however add private helper functions and member variables to these classes. You can also add new public helper functions, e.g. in the Log Manager.
与之前的项目一样，我们提供了包含您需要实现的 API 的存根类。您不应该修改这些类中预定义函数的签名。如果您这样做，将会破坏我们用于评分的测试代码，导致您在项目中得不到任何学分。如果一个类已经包含某些成员变量，您不应该删除它们。但是，您可以向这些类添加私有辅助函数和成员变量。您还可以在日志管理器中添加新的公共辅助函数。

The correctness of this project depends on the correctness of your implementation of previous projects, we will not give solutions or binary files. However, this project may differ from the last ones in several aspects. We have already made the necessary modifications to the insert/delete/search operations in the TableHeap (include/storage/table/table_heap.h), as well as interactions between the log manager, buffer pool manager, transaction manager, and checkpoint manager.
这个项目的正确性取决于您之前项目实现的正确性，我们不会提供解决方案或二进制文件。然而，这个项目可能在几个方面与之前的项目有所不同。我们已经对TableHeap（include/storage/table/table_heap.h）中的插入/删除/搜索操作以及日志管理器、缓冲池管理器、事务管理器和检查点管理器之间的交互进行了必要的修改。

TASK #1 - LOG MANAGER

任务＃1 - 日志管理器

To achieve the goal of atomicity and durability, the database system writes information describing the modifications made by any transaction to stable storage. This information ensures that all modifications performed by committed transactions are reflected in the database (perhaps during the course of recovery actions after a crash). It can also help the DBMS ensure that no modifications made by an aborted or failed transaction persist in the database after a crash/restart. The most widely used structure for recording database modifications is the write-ahead log. The log is a sequence of log records, recording all the update activities in the database. We are providing you with the basic structure of a log record (include/recovery/log_record.h) and corresponding helper methods.
为了实现原子性和持久性的目标，数据库系统将描述任何事务所做修改的信息写入稳定存储。这些信息确保所有已提交事务所进行的修改都在数据库中得到反映（可能在崩溃后的恢复操作过程中）。它还可以帮助DBMS确保在崩溃/重启后，中止或失败的事务所做的任何修改都不会在数据库中持久存在。记录数据库修改的最常用结构是预写式日志。日志是一系列的日志记录，记录了数据库中的所有更新活动。我们为您提供了日志记录的基本结构（include/recovery/log_record.h）和相应的辅助方法。

In your implementation, there is a global LogManager object for the entire system (similar to your BufferPoolManager). The TablePage class will explicitly create a log record (before any update operations) and invoke the AppendLogRecord method of LogManager to write it into log buffer when the global variable enable_logging (include/common/config.h) flag is set to be true. We recommend that you to read this article to refresh your C++ concurrency knowledge. More detailed documentation about condition variable is available here.
在您的实现中，整个系统都有一个全局的LogManager对象（类似于您的BufferPoolManager）。TablePage类将明确创建一个日志记录（在任何更新操作之前），并在全局变量enable_logging（include/common/config.h）标志设置为true时调用LogManager的AppendLogRecord方法将其写入日志缓冲区。我们建议您阅读这篇文章以刷新您的C++并发知识。有关条件变量的更详细文档可在此处找到。

IMPLEMENTATION DETAILS FOR LOGGING/RECOVERY

This list points out some implementation details that have been set up in advance to enable your logging/recovery system.
以下是事先设置的一些实现细节，以使您的日志记录和恢复系统正常运行。

  • Transaction Manager: There is a ReaderWriterLatch instance in the TransactionManager called global_txn_latch_. This latch is used in the two helper functions for stopping the execution of transactions (BlockAllTransactions, ResumeTransactions).

  • 事务管理器 (Transaction Manager): 在 TransactionManager 中有一个名为 global_txn_latch_ 的 ReaderWriterLatch 实例。该锁用于两个辅助函数，用于停止执行事务 (BlockAllTransactions、ResumeTransactions)。

  • Global Variables: There is a global variable called enable_logging within include/common/config.h. Logging functionality should only be active when this is set to true. You may need to explicitly set it to false in order to pass some of the previous test cases. The constant log_timeout is defined within config.h, for every log_timeout seconds, your LogManager implementation needs to execute a flush operation (more details in the next section).

  • 全局变量 (Global Variables): 在 include/common/config.h 中有一个名为 enable_logging 的全局变量。只有当该变量设置为 true 时，日志记录功能才会生效。为了通过之前的某些测试用例，您可能需要显式将其设置为 false。常量 log_timeout 也在 config.h 中定义，对于每个 log_timeout 秒，您的 LogManager 实现需要执行一次刷新操作（更多细节将在下一部分介绍）。

  • Buffer Pool Manager: BufferPoolManager‘s constructor accepts a DiskManager and LogManager as input parameters. The default value for log_manager is nullptr, and log_manager is only valid when enable_logging is set to true. We have also added two simple getter functions: Page* GetPages() and size_t GetPoolSize(). These are used to test your CheckpointManager.

  • 缓冲池管理器 (Buffer Pool Manager): BufferPoolManager 的构造函数接受 DiskManager 和 LogManager 作为输入参数。log_manager 的默认值为 nullptr，只有当 enable_logging 设置为 true 时，log_manager 才有效。我们还添加了两个简单的获取函数：Page* GetPages() 和 size_t GetPoolSize()。这些函数用于测试您的 CheckpointManager。

  • Disk Manager: The DiskManager creates the database file as well as the log file for its constructor. We have also provided separate helper functions WriteLog and ReadLog to support accessing the log file.

  • 磁盘管理器 (Disk Manager): DiskManager 在其构造函数中创建数据库文件和日志文件。我们还提供了单独的辅助函数 WriteLog 和 ReadLog 来支持对日志文件的访问。

  • HashTableHeaderPage: There is a member variable lsn_ to record the page’s log sequence number. You do not need to update lsn_ within your index implementation, we only test logging and recovery functionalities on table page level.

  • 哈希表页头 (HashTableHeaderPage): 有一个成员变量 lsn_ 用于记录页面的日志序列号。在索引实现中不需要更新 lsn_，我们只在表页面级别上测试日志和恢复功能。

  • Page: The Page object has GetLSN and SetLSN helper methods. Remember that the log sequence number is a 4-byte int32_t stored in the page’s data_ array.

  • 页面 (Page): 页面对象具有 GetLSN 和 SetLSN 辅助方法。请记住，日志序列号是一个存储在页面的 data_ 数组中的 4 字节的 int32_t 值。

  • TablePage: We extended TablePage to make appropriate calls to the LogManager on insert, update, and delete operations. Please make sure to review these changes and make sure you understand what they’re doing.

  • TablePage: 我们扩展了 TablePage，在插入、更新和删除操作中调用了适当的 LogManager 方法。请确保仔细查看这些更改，并确保理解其功能。

  • Transaction: The Transaction object has the GetPrevLSN and SetPrevLSN helper methods. Each transaction is responsible for maintaining the previous log sequence number to be used in the undo phase. Please consult Chapter 16.8 in the textbook for more detailed information.

  • Transaction: Transaction 对象具有 GetPrevLSN 和 SetPrevLSN 辅助方法。每个事务负责维护用于撤销阶段的先前日志序列号。请参考教科书中的 Chapter 16.8 获取更详细的信息。

  • LogRecord: We have provided the implementation of physiological log record that supports different type of write operations within database system. Each log type corresponds to a write operation within the TablePage class (storage/page/table_page.h, so please make sure you understand the record structure.

  • LogRecord: 我们提供了 LogRecord 的实现，它支持数据库系统中不同类型的写操作。每种日志类型对应于 TablePage 类中的一个写操作（storage/page/table_page.h），所以请确保您理解记录的结构。

REQUIREMENTS AND HINTS

要求和提示

The files you need to modify for this task are:
您需要修改的文件有：

  • LogManager: recovery/log_manager.cpp, include/recovery/log_manager.h)

  • LogRecovery: recovery/log_recovery.cpp, include/recovery/log_recovery.h

  • TransactionManaer: concurrency/transaction_manager.cpp, include/concurrency/transaction_manager.h

  • CheckpointManager: recovery/checkpoint_manager.cpp, include/recovery/checkpoint_manager.h

  • BufferPoolManager: buffer/buffer_pool_manager.cpp, include/buffer/buffer_pool_manager.h

You will need to implement the following functionality:

您需要实现以下功能：

  • The StopFlushThread function is used to stop logging and join the flush thread
    StopFlushThread 函数用于停止日志记录并加入刷新线程。
  • Your LogManager will integrate the group commit feature. The motivation behind group commit is to amortize the costs of each fsync() over multiple commits from multiple parallel transactions. If there are, say, 10 transactions in parallel trying to commit, we can force all of them to disk at once with a single fsync() call, rather than do one fsync() for each. This can greatly reduce the need for fsync() calls, and consequently greatly improves the commits-per-second throughput. Within TransactionManager, whenever you call the Commit or Abort method, you need to make sure your log records are permanently stored on disk file before releasing the locks. But instead of forcing a flush, you need to wait for log_timeout or other operations to implicitly trigger the flush operations.

您的LogManager将集成组提交（group commit）功能。组提交的目的是将每个并行事务的提交操作中的fsync()成本分摊在一起。例如，如果有10个并行事务尝试提交，我们可以通过一次fsync()调用将它们全部一次性强制写入磁盘，而不是为每个事务执行一次fsync()。这可以大大减少对fsync()调用的需求，并且从而显著提高每秒提交数的吞吐量。在TransactionManager中，无论何时调用Commit或Abort方法，您都需要确保在释放锁之前将日志记录永久存储在磁盘文件中。但是，您不需要强制执行刷新操作，而是等待log_timeout或其他操作隐式触发刷新操作。

  • In your BufferPoolManager, when a new page is created, if there is already an entry in the page_table_ mapping for the given page id, you should make sure you explicitly overwrite it with the frame id of the new page that was just created. This is a minor behavioral change in the buffer pool manager, but it is a requirement to pass the test cases.
    在您的BufferPoolManager中，当创建一个新的页面时，如果page_table_映射中已经存在给定页面ID的条目，您应确保明确用新创建的页面的frame ID覆盖它。这是buffer pool manager中的一个小行为变化，但这是通过测试用例的要求。

  • Before your buffer pool manager evicts a dirty page from the clock replacer and writes this page back to the disk, it needs to flush all logs up to pageLSN. You need to compare persistent_lsn_ (a member variable in LogManager) with your pageLSN. However, unlike with group commit, the buffer pool can force the log manager to flush the log buffer (but still needs to wait for the logs to be stored before continuing).
    在缓冲池管理器从clock replacer中驱逐脏页面并将该页面写回磁盘之前，它需要将所有日志刷新到pageLSN。您需要将persistent_lsn_（LogManager中的一个成员变量）与您的pageLSN进行比较。然而，与组提交不同，缓冲池可以强制日志管理器刷新日志缓冲区（但仍然需要等待日志存储后才能继续）。

  • The TablePage class methods have some portions that deal with runtime write-ahead logging. They (1) create a log record, (2) invoke the LogManager‘s AppendLogRecord method to write it to the log buffer when the global variable enable_logging (include/common/config.h) is true, (3) update the prevLSN for the current transaction, and (4) update the LSN for the current page. Your job is to implement AppendLogRecord in the LogManager class so that the log records are properly serialized to the log buffer.
    TablePage类的方法中有一些部分处理运行时的”write-ahead”日志记录。它们(1)创建一个日志记录，(2)在全局变量enable_logging（include/common/config.h）为true时调用LogManager的AppendLogRecord方法将其写入日志缓冲区，(3)更新当前事务的prevLSN，(4)更新当前页面的LSN。您的任务是在LogManager类中实现AppendLogRecord，以便将日志记录正确地序列化到日志缓冲区中。

  • Inside the RunFlushThread function in the LogManager, you need to start a separate background thread which is responsible for flushing the logs to disk. The thread runs forever until system shutdown/StopFlushThread. The thread is triggered every log_timeout seconds or when the log buffer is full. Since your LogManager needs to perform asynchronous I/O operations, you will maintain two log buffers, one for flushing (called the flush_buffer) one for concurrently appending log records (called the log_buffer). You should swap buffers under any of the following three situations. (1) When the log buffer is full, (2) when log_timeout seconds have passed, and (3) When the buffer pool is going to evict a dirty page from the LRU replacer.
    在LogManager的RunFlushThread函数中，您需要启动一个单独的后台线程，负责将日志刷新到磁盘。该线程会一直运行，直到系统关闭或调用StopFlushThread。线程在以下三种情况下触发：每隔log_timeout秒、日志缓冲区已满，或者缓冲池将从LRU replacer中驱逐一个脏页。由于LogManager需要执行异步的I/O操作，您需要维护两个日志缓冲区，一个用于刷新（称为flush_buffer），一个用于并发追加日志记录（称为log_buffer）。在以下三种情况下，您应该交换缓冲区：(1) 当日志缓冲区已满时，(2) 当经过了log_timeout秒，以及(3) 当缓冲池将从LRU replacer中驱逐一个脏页时。

Important: You should first take a look at the files we mention in this and previous sections to become familiar with the APIs and member variables we provide. You should consult with Chapter 16.8 in the textbook and make sure that your implementation follows the ARIES protocol (except for the checkpointing part). Since the LogManager needs to deal with background threads and thread synchronization, we recommend you to take a look at Future and Promise.
重要提示：您应首先查看我们在此和前几节提到的文件，以熟悉我们提供的API和成员变量。您应参考教科书中的第16.8章，并确保您的实现遵循ARIES协议（除了检查点部分）。由于LogManager需要处理后台线程和线程同步，我们建议您查看Future和Promise相关内容。

TESTING

There is a sample test in test/recovery/recovery_test.cpp.
在test/recovery/recovery_test.cpp中有一个样例测试。

TASK #2 - SYSTEM RECOVERY

任务 #2 - 系统恢复

The next part of the project is to implement the ability for the DBMS to recover its state from the log file.
下一个项目的一部分是实现数据库管理系统从日志文件中恢复其状态的能力。

REQUIREMENTS AND HINTS

要求和提示

The recovery process for our database system is pretty straightforward. Since we do not support fuzzy checkpoints, there is no need for an analysis pass. The only file you need to modify for this task is the LogRecovery class (recovery/log_recovery.cpp and include/recovery/log_recovery.h). You will need to implement the following functions:
我们的数据库系统的恢复过程非常简单。由于我们不支持模糊检查点，因此不需要进行分析阶段。你只需要修改以下文件来完成这个任务：LogRecovery 类（recovery/log_recovery.cpp 和 include/recovery/log_recovery.h）。你需要实现以下函数：

  • DeserializeLogRecord: Deserialize and reconstruct a log record from the log buffer. If the return value is true then the deserialization step was successful, otherwise the log buffer may contain incomplete log record.

  • DeserializeLogRecord：从日志缓冲区中反序列化和重构一个日志记录。如果返回值为true，则反序列化步骤成功，否则日志缓冲区可能包含不完整的日志记录。

  • Redo: Redo pass on the TABLE PAGE level (include/storage/page/table_page.h). Read the log file from the beginning to end (you must prefetch log records into the buffer to reduce unnecessary I/O operations), and for each log record, redo the action unless the page is already more up-to-date than this record. Also make sure to maintain the active_txn_ table and lsn_mapping_ table along the way.

  • Redo：对TABLE PAGE级别进行Redo操作（include/storage/page/table_page.h）。从头到尾读取日志文件（必须预取日志记录到缓冲区以减少不必要的I/O操作），对于每个日志记录，重新执行操作，除非页面已经比此记录更为更新。同时确保在此过程中维护active_txn_表和lsn_mapping_表。

  • Undo: Undo pass on the TABLE PAGE level (include/table/table_page.h). Iterate through the active_txn_ table and undo operations within each transaction. You do not need to worry about a crash during the recovery process, meaning no complementary logging is needed.

  • Undo：在TABLE PAGE级别上进行Undo操作（include/table/table_page.h）。遍历active_txn_表，并在每个事务中执行撤销操作。您无需担心恢复过程中的崩溃，也就是说不需要进行补充日志记录。

Important: We recommend that you read Chapter 16.8 in the textbook first to make sure that you understand the whole process of recovery and what the redo/undo pass is trying to do. The basic idea is that during recovery, redo does the exact operation (MARKDELETE -> MarkDelete) whereas undo does the complementary operation (MARKDELETE -> RollBackDelete). Then, figure out each write operation within the TablePage class and what the corresponding complementary operation is. For example, to undo an Insert operation, you need to call ApplyDelete function instead of MarkDelete. The complementary operations are: Insert <-> ApplyDelete, MarkDelete <-> RollBackDelete, Update <-> Update, NewPage <-> (do nothing)
Important: 我们建议您首先阅读教材中的第16.8章，以确保您理解恢复的整个过程以及重做/撤销操作的目的。基本思想是，在恢复过程中，重做执行与操作相同的操作（MARKDELETE -> MarkDelete），而撤销执行补充操作（MARKDELETE -> RollBackDelete）。然后，弄清楚TablePage类中的每个写操作以及相应的补充操作是什么。例如，要撤销一个Insert操作，您需要调用ApplyDelete函数而不是MarkDelete。补充操作是：Insert <-> ApplyDelete，MarkDelete <-> RollBackDelete，Update <-> Update，NewPage <-> (不进行任何操作)。

TESTING

There is a sample test in test/recovery/recovery_test.cpp.
在test/recovery/recovery_test.cpp中有一个简单的测试样例。

TASK #3 - CHECKPOINTS

任务 #3 - CHECKPOINTS

For the final task, you will implement a simple mechanism to make fully consistent checkpoints. We’ve added a new module called CheckpointManager that is responsible for handling this. It should work directly with the TransactionManager, BufferPoolManager, and LogManager to block any new transactions, flush the WAL to disk, and flush all dirty buffer pool pages to disk. Finally, it should allow new transactions to begin.
在最后的任务中，您需要实现一个简单的机制来创建完全一致的检查点。我们添加了一个名为CheckpointManager的新模块，它负责处理这个任务。它将直接与TransactionManager、BufferPoolManager和LogManager进行交互，以实现以下功能：阻止任何新的事务开始，将写前日志(WAL)刷新到磁盘，以及将所有脏的缓冲池页面刷新到磁盘。最后，它将允许新的事务开始执行。

REQUIREMENTS AND HINTS

提示和要求

The API for the CheckpointManager has two functions:
CheckpointManager的API包含两个函数：

  • BeginCheckpoint: Use the TransactionManager to block any new transactions from starting, then use the LogManager to ensure the contents of the WAL in memory is flushed to disk. Lastly, use the BufferPoolManager to flush all dirty pages to disk. Note that the DBMS must keep all transactions blocked when this method returns (this is necessary for grading).

  • BeginCheckpoint：使用TransactionManager阻止任何新事务的开始，然后使用LogManager确保内存中的WAL内容被刷新到磁盘。最后，使用BufferPoolManager将所有脏页面刷新到磁盘。请注意，在此方法返回时，DBMS必须保持所有事务被阻塞（这对于评分是必要的）。

  • EndCheckpoint: Use the TransactionManager to unblock transactions and allow new transactions to begin.

  • EndCheckpoint：使用TransactionManager解除事务的阻塞，允许新事务开始执行。

Adding checkpointing to your DBMS should be the simplest of the three tasks as it does not require a lot of code. You just need to extend your BufferPoolManager to flush all dirty pages to disk and mark them clean. With this in place, your BeginCheckpoint and EndCheckpoint methods should be short.
将检查点功能添加到您的DBMS应该是三个任务中最简单的，因为它不需要很多代码。您只需扩展BufferPoolManager以将所有脏页面刷新到磁盘并标记为干净。有了这个功能，您的BeginCheckpoint和EndCheckpoint方法应该很简短。

TESTING

There is a sample test in test/recovery/recovery_test.cpp.
在 test/recovery/recovery_test.cpp 中有一个简单的测试样例。

附录