4.2. Recovery in the LSM-tree

当新的条目插入到lsm树的C0组件时，滚动合并进程将条目信息依次迁移到更大的组件中，这项工作将在内存缓冲的多页块中进行。与任何此类内存缓冲更改一样，在将工作写入磁盘之前，它不会抵抗系统故障。我们面临着一个经典的恢复问题:在崩溃和内存丢失后，重建在内存中发生的工作。正如我们在第二章开始时提到的，我们不需要创建特殊的日志来恢复新创建记录上的索引项:事务为这些新记录插入日志写入顺序日志文件在正常情况下,它是一个简单的问题来治疗这些插入日志(通常包含所有字段值一起掉在插入的记录已经放置)作为逻辑基础重建索引条目。这种恢复索引的新方法必须构建到系统恢复算法中，并且可能会延长对此类事务性History插入日志进行存储回收的时间，但这是一个次要考虑因素。（有道翻译）

证明复苏LSM-tree指数的,重要的是,我们仔细定义的形式的一个检查站,并证明我们知道从哪里开始顺序日志文件,和如何应用连续日志,以确定性复制更新索引需要恢复。我们使用的方案如下。当在T0时刻请求检查点时，我们完成操作中的所有合并步骤，释放节点锁，然后推迟所有新条目插入到LSM-tree中，直到检查点完成;此时，我们使用以下操作创建一个LSM树检查点。（有道翻译）

我们将组件C0的内容写入一个已知的磁盘位置;在此之后，可以再次开始向C0插入条目，但合并步骤将继续延迟。（有道翻译）

• 我们将基于磁盘组件的所有脏内存缓冲节点刷新到磁盘。
• 创建带有如下信息的checkpoint：
  • T0时刻最后插入的索引行的日志序列号LSN0
  • 组件roots地址
  • 合并操作cursors位置
  • 当前动态申请的多页块信息

一旦将检查点信息放在磁盘上，我们就可以恢复lsm -树的常规操作。在发生崩溃和随后的重启时，可以定位这个检查点，并将保存的组件C0加载回内存，以及继续滚动合并所需的其他组件的缓冲块。然后，从LSN0之后的第一个LSN开始的日志被读入内存，并将它们相关联的索引项输入到LSM-tree中。在检查点出现时，包含所有索引信息的所有基于磁盘的组件的位置都记录在从根开始的组件目录中，它们的位置可以通过检查点日志得知。这些信息不会在以后写多页磁盘块时被抹去，因为这些写操作总是在磁盘上的新位置，直到后来的检查点使过时的多页磁盘块变得不必要为止。当我们恢复索引行的插入日志时，我们将新条目放入C0组件中;现在滚动合并再次开始，覆盖自检查点以来写入的任何多页块，但恢复所有新的索引项，直到最近插入的行已建立索引并完成恢复。（有道翻译）

这种恢复方法显然是有效的，惟一的缺点是在检查点过程中发生各种磁盘写操作时可能会有很大的暂停。不过，这个暂停并不是特别重要，因为我们可以在很短的时间内将C0组件写入磁盘，然后在完成对磁盘的其他写入操作时继续插入C0组件;这只会导致比通常更长的延迟时间，在此期间，新插入到C0的索引项不会合并到更大的基于磁盘的组件。一旦检查点完成，滚动合并进程就可以补上它错过的工作。注意，检查点日志列表中提到的最后一条信息是动态分配新多页块的当前信息。在发生崩溃的情况下，我们需要在恢复时弄清楚在动态磁盘存储分配算法中有哪些多页块可用。这显然不是一个困难的问题;事实上，在这样的块中，垃圾收集碎片信息的一个更困难的问题必须在[23]中解决。（有道翻译）

恢复的另一个细节与目录信息有关。注意,随着轧制合并的进行,每次一个多页的块或更高级别的目录节点从磁盘把它必须立即被分配一个新磁盘的位置,以防出现检查点清空之前完成,剩余的缓冲信息必须被迫离开到磁盘。这意味着指向空节点的目录条目必须立即更正为指向新节点位置。类似地，我们必须立即为新创建的节点分配磁盘位置，以便树中的目录条目能够立即指向磁盘上的适当位置。在每一点上，我们都需要注意，包含由滚动合并缓冲的低层节点指针的目录节点也要被缓冲;只有这样，我们才能快速地进行所有必要的修改，这样检查点才不会因为等待I/ o修正目录而被占用。而且，在检查点发生并且将多页块读入内存缓冲区以继续滚动合并之后，所有涉及到的块都必须分配到一个新的磁盘位置，因此所有指向附属节点的目录指针都必须更正。如果这听起来像是大量的工作，读者应该记得，没有额外的I/O必要，涉及的指针的数量可能只有64个左右的每个块缓冲。此外，这些更改应该分摊到大量合并的节点上，假设检查点的使用频率仅够保持恢复时间不超过几分钟;这意味着在检查点之间需要几分钟的I/O。（有道翻译）

todo：自己翻译，仔细阅读