CONSENSUS:BRIDGING THEORY AND PRACTICE(第5章)

日志压缩

Raft日志会随着包含了越来越多的客户端请求而持续增长。当它变得很大的时候，将会占据更多的空间并且需要花费更多的时间去回放。如果没有一些日志压缩的手段，最终将会引起可用性问题：servers将或者执行到空间不足，或者要花费很久启动。因此，在任何实际系统中对日志以某些形式上的压缩都是必要的。

最一般的压缩想法是随着时间的流逝会有越来越多的日志成为废弃无用的并且可以被丢弃。例如，一个将x赋值为2的操作会在x赋值为3之后就成为废弃的了。一旦log entries被提交并且应用到状态机了，到达这个状态过程中的中间状态和操作都不再需要了，它们就可以被压缩掉。

不像核心的Raft算法和成员变更，不同的系统将会有不同的日志压缩需求。没有一个普适的日志压缩方案，这有几个原因。第一，不同的系统可能在易用性和性能上有着不同角度的权衡。第二，状态机必须与日志压缩密切相关，并且状态机在大小和存储介质(disk/memory)方面也存在很大差异。

本章的目标是讨论各种各样的日志压缩方法。在每一个方法中，日志压缩的大部分责任落在状态机上，状态及负责将状态写入磁盘并压缩状态。状态及可以通过不同的方法实现，通篇都会介绍，下图5.1是概括：

• memory-based状态机的快照在概念上是最简单的方法。快照时，整个当前系统的状态被写入到持久化存储的快照中，之后log中到这个点之前的都会被丢弃掉。快照在Chubby和Zookeeper中有所使用，并且我们在LogCabin中也实现了快照。快照是本章5.1节中讲述最深的。

• 对于disk-based状态机，系统最近状态的拷贝会维护在disk上，作为正常操作的一部分。因此，一旦状态机映射到了disk上Raft log就可以丢弃了，并且快照只会被用来为保证一致性而发送给其他servers(

  译者注：当然server restart的时候也会load

  )(5.2节)。
• 增量的方法做log压缩，比如日志清理和LSM-tree，在5.3节中有描述。这些方法可以高效的写入disk，并且能随着时间平坦的利用资源。
• 最后，5.4节讨论了一个通过把快照直接存储在log中的有着最小化的机制需求的日志压缩方法。然而实现很简单，这种方法只适合非常小的状态机。

LogCabin当前只是先了memory-based的快照方法(内嵌的一个memory-based的状态机)。

各种压缩方法其实共享一些核心概念。第一，不是将压缩决策集中在leader身上，而是每一个server独立地根据committed状态把之前的log进行压缩。这避免了leader把已经在follower中存在在log中的数据传输给follower。这也提高了模块性：大部分额日志压缩的复杂性留在了状态机中，不会太多地影响Raft本身。这也保持了整个系统的复杂性最小化：日志压缩特性的引入对整体复杂度的影响是加法性的增加，而不是乘法性的增加。可供选择的方法即leader集中化的压缩方式会在5.4节中有所讨论(并且对于非常小的状态机，leader-based的方法可能更好)。

第二，状态机和Raft的基本交互涉及到将之前的log的维护责任由Raft转给状态机。在entries被应用到状态机后，迟早状态机会把那些entries映射到disk上以便可以恢复系统当前状态。一旦完成，状态机将通知Raft可以丢弃相应的log。在Raft放弃对这些log的责任之前，它必须把它拥有的一些用于描述这些log的状态信息进行保存。特别地，Raft要保存最后被丢弃的entry的index和term；这个状态机状态点后面是剩余的Raft维护的log entries，同时也保证了AppendEntries一致性检查可以继续工作(它需要log中的第一个entry之前的index和term

译者注：Raft剩下的log的第一条之前的部分就是状态机保存的状态

)。Raft也保存了丢弃log中的最近的配置以支持集群成员变更

译者注：成员变更失败需要回退配置，最近的配置必须保存

。

第三，一旦Raft丢弃了log前面的部分，状态机就负有了两个新的责任。如果server重启了，状态机在可以应用任何Raft log中的entry之前需要把相应丢弃的log entries对应部分的状态加载了。此外，状态机可能需要生成一个状态的镜像以便可以发送给较慢的follower(远落后于leader log的server)。等到集群中的每个成员都日志一致后再压缩是不可行的，由于minority成员不会影响集群可用性，而且新的server也随时可能被加入到集群中。因此，慢的followers或者新的servers将偶尔地需要通过网络收到它们的初始状态。Raft如果发现一个server的next entry在被丢弃了的log entries中，则状态机会提供一个状态的一致镜像并发送给follower。

memory-based状态机的快照

第一个快照应用是当状态机的状态保持在内存中的时候。这在状态机的数据集处于GB和10GB这个数量级的时候是合理的选择。由于不用去disk获取数据，操作会快速完成；这样做也使得变成更加简单了，因为有大量的数据结构可以使用并且每个操作都可以执行到完成(没有IO阻塞)。

图5.2显示了Raft中当状态机状态保存在内存中时的基本想法。每一个server独立的取得快照，只覆盖log中已提交的entries。快照工作的大部分涉及到序列化状态机当前状态，并且这对于独有的不同状态机都是特殊的。例如，LogCabin的状态机使用一个tree作为其主要数据结构；使用先序(前序)的深度优先遍历方式序列化tree(因此当应用快照时，父节点会在它的子节点之前创建)。状态机也需要把它为了客户端提供线性一致性特性保持的信息进行序列化(见第6章)。

一旦状态机写完了快照，log就可以被截断了。Raft首先存储重启需要的状态：快照中包含的最后entry的index和term以及直到该索引处的最新配置。然后就通过这个index丢弃log前面直到该index的entries。任何之前的快照也可以被丢弃了，它们已经没有用了。

由上面的介绍，leader可能偶尔需要把它的状态发送给慢followers并且发送给加入集群的新servers。在快照逻辑中，这个状态就是最新的快照，leader会通过一个新的InstallSnapshot RPC来传输，如图5.3。当一个follower通过这个RPC收到一个快照时，它必须决定对已存在的log entries做什么处理。通常快照将包含follower log中没有的新信息。这种情况下，follower会丢弃它所有的log；它将完全被快照取代并且可能存在与快照中冲突的未提交的entries(

译者注：以leader发来的快照为准

)。否则如果follower收到的快照内容已经包含在的它的log之中(由于重传或者错误)，则快照中表达的部分对应的log entries就会被删除，在快照后面部分的日志仍然有效并且需要被保持。

剩下段落的部分讨论memory-based状态机快照的次要问题：

• 5.1.1节讨论如何在生成快照和正常操作之间并行，进而最小化对客户端的影响
• 5.1.2节讨论什么时候获取快照，平衡空间使用和快照生成的负载
• 5.13.节讨论快照实现过程中出现的问题

快照的并发性

创建一个快照需要花费很长时间，包括序列化状态和disk的写入。例如，在今天的服务器上拷贝10GB的内存花费大约1秒钟，并且序列化它通常将花费更长的时间：即使SSD 1秒钟也仅能写入大约100MB。因此，序列化和写快照都必须与常规操作并发以避免可用性问题。

幸运的是copy-on-write技术允许新更新的应用不影响快照的写入。有两个方法来实现：

• 状态机可以用不可变的(功能性的)数据结构来支持构建实现。因为状态机命令不会in-place的方式修改状态(

  比如说通过追加的形式实现修改，获取的时候获取最新的追加的内容，后面再定期或定量整理垃圾。这样的话之前的状态就维持住了，就可以容易的生成快照了

  )，快照任务可以引用之前状态的并把状态一致地写入到快照。
• 可选择的，操作系统的copy-on-write也可以被使用(如果编程环境允许)。比如在Linux上，in-memory状态机可以使用fork来得到server的整个地址空间的拷贝。然后子进程就可以把状态机的状态写出并退出，整个过程中父进程都可以持续地提供服务。LogCabin中当前使用的就是这种方法。

Servers并发地制作快照需要额外的内存，这应该被我们计划和管理。状态机通过流式的接口来做快照文件是必要的，以便快照创建时不会整体在内存中逗留。然而，copy-on-write机制下状态机的状态需要的额外内存的比例是会改变的。此外，依赖于操作系统的copy-on-write技术也会由于伪共享而使用更多的内存(例如两个不相关的数据落在了一个内存page上，当仅第一个数据失效时，第二个数据也就会在父子进程间产生多余的副本

译者注：第二条数据没有变更本可以一个内存副本，但是由于和第一条落在了一个page上，os是page为粒度管理内存的，则第二个也会copy-on-write进而产生一个多余副本

)。不幸的事件发生的话可能导致内存在快照期间被耗尽，这时候server应该停止接收log entries直到完成快照；这将临时地牺牲server的可用性(集群可能还是保持可用的)，但是这样至少server将会恢复。取消快照并在稍后重试可能并不好，因为下一次尝试可能面临相同问题(LogCabin使用流式的刷盘接口，但是目前也没有优雅地处理内存耗尽的问题)。

什么时候做快照

Servers需要决定什么时候做快照。如果一个server太过频繁地做快照，将来浪费disk带宽和其他资源；如果太不频繁地做快照，则有存储空间耗尽的风险，并且重启服务需要更长的重放日志时间。

一个简单的策略是当log达到了一定的大小后做快照。如果这个大小阈值设置的显著地大于快照预期的大小，那么快照带来的disk带宽负载将会是小的。然而，这会导致对于小的状态机时有着不必要的大的logs。

一个好的方法是引入快照大小和日志大小的对比。如果快照比日志小几倍，可能更值得做快照。然而，在制作快照之前计算快照的大小是困难并且繁重的，将会引入显著地状态机跟踪负担，或者需要几乎和制作快照差不多的动态大小计算的工作量。压缩快照文件也会带来空间和带宽的节省，但是预测压缩后的输出大小是困难的。

幸运的是，使用前一个快照的大小而不是下一个快照的大小会是比较合理的行为。一旦日志的大小超出了前一个快照的可配置的扩展因子倍数，servers就做快照。这个扩展因子权衡空间和带宽利用率。例如扩展因子为4的话会有20%的带宽用于快照(每1byte的快照写入有对应的4bytes的log写入)和大约6倍的硬盘空间使用(旧的快照➕log➕新的快照)。

快照会导致cpu和disk io的突发使用可能会影响客户端性能。这可以通过硬件方案来减轻状况，比如新增一个disk driver以提供额外的带宽。

也可能通过调度快照的制作以使得快照对客户端请求没有影响。servers需要协调保证在某一时刻集群只有小部分成员集同时在做快照。由于Raft是majority成员构成的commit，所以这样就不会影响请求的提交了。当leader想做快照的时候，首先要先下台，让其他server领导集群。如果这个方法充分地可行，就可能消除快照的并发，server在快照期间其实是不可用的(这可能会造成集群的容错能力降低的问题)。这是一个令人兴奋的提升集群性能并降低实现机制的机会。

实现的关注点

这一节回顾快照的主要组件的实现并讨论实现的难点：

• 保存和加载快照： 保存快照牵涉把状态机状态序列化后的数据存储到disk，而加载是一个相反的过程。我们发现这是相当直截了当的，尽管序列化不同本地情况的数据有几分乏味。状态机提供一个流式的接口将数据刷到disk是有必要以避免状态机暂存全部序列化的状态数据。可能对流进行压缩并附带一个checksum比较好。LogCabin先把快照写入一个临时文件，当写完并且刷到disk之后，再把文件改名。这是为了避免server启动的时候加载到部分的快照。
• 传输快照： 传输快照牵涉到主和从实现InstallSnapshot RPC。这是相当直截了当的，可能可以共享在磁盘上保存和加载快照的一些代码。传输的性能通常不是非常重要（一个需要这种动作的跟随者不会参与到entries的commitment决策中，因此不需要立即完成；另一方面，如果集群遭遇额外的失败，就可能需要尽快使得落后的follower赶上来以恢复集群的可用性）。
• 排除不安全的日志访问和丢弃日志条目： 我们最初设计LogCabin的时候没有考虑日志压缩，因此代码上假定了如果entry i 在日志中，那么entry 1 到 i - 1 也一定在日志中。有了日志压缩，这就不再成立了；例如，当AppendEntries RPC要确定前一个entry的term时，那个entry可能已经被丢弃了。贯穿代码移除这些假定需要仔细地推敲和测试。可能对一些强类型的系统做这些是简单的，编译器会强制检查日志访问并处理越界的问题。一旦我们使得所有的日志访问都是安全的，丢弃前面的日志就是直截了当的了。直到这点，我们都只能单独地测试保存、加载和传输快照，但是当日志条目可以被安全地丢弃的时候，就可以做令人兴奋的系统级的测试了。
• 通过copy-on-write并发地做快照： 并发做快照可能需要重做状态机或者利用操作系统的fork操作。LogCabin当前使用的是fork，不需要与线程和C++的析构打交道，通过这些做一个正确地工作是困难的。然而，以较少的代码消除了对状态机数据结构的修改，我们认为这是正确的方法。
• 决定什么时候做快照： 我们建议在开发的过程中每应用一条日志就做一个快照，这样便于快速定位问题。一旦实现完成，就需要增加一个更有效的机制选择什么时候做快照（例如使用Raft log和上一个快照的统计信息）。

我们发现分段开发和测试快照是有挑战的。在丢弃log entries的时候大多数组件都需要in-place，但是仅仅在系统集成测试的时候才能拥有这些新的代码。因此实现者应该小心考虑实现和测试组件的顺序。

Disk-based状态机的快照

这一节讨论一个对于大的状态机(在十或百GB这个量级)实现快照的方法，使用disk作为主存。这些状态机的运作是不同的，他们会在disk保持一份状态的副本以应对crash。应用没一个Raft log entry都会改变disk上的状态，进而等于生成了一个新的有效的快照。因此，一旦一个entry被应用之后就可以从Raft log中丢弃了（状态机也可以在内存中做缓冲以提升disk使用的性能；一旦缓冲写入了disk，相应的entries就可以从Raft log中丢弃了）。

Disk-based的状态机的主要问题是基于disk的状态变化会导致较差的性能体验。如果没有写缓冲，没一个命令的应用需要一个或者更多的随机disk访问，这会限制系统整体的写吞吐（即便又写缓冲也没有太大帮助）。5.3节会讨论一种增量的日志压缩方法，它会利用大的、顺序的写来提升写disk的性能。

Disk-based状态机必须要有能力提供一致的disk快照以满足传送给较慢的follower的需求。尽管它们在disk有快照，但是也在连续不断地修改它。因此，它们仍然需要copy-on-write技术以在一定期间内保持一个一致地快照以供传输。幸运的是，disk格式基本都是以逻辑块为单元，因此在状态机中实现copy-on-write技术是直截了当的(自己实现很直接简单，比如模仿linux fork后的cow机制)。Disk-based状态机也可以依赖操作系统的支持。比如，linux上的LVM可以被用来创建快照。

拷贝一个disk的镜像需要花费较长时间，并且由于disk的修改是累积的，因此为了保持快照额外的disk使用是必须的。尽管我们没有实现disk-based的快照，但是我们推断disk-based的快照可以通过下面的算法避免大多数的disk内容传输负载：

1. 对于没一个disk块，跟踪其last modified。
2. 在持续的普通操作期间，一个块一个块地传输整个disk的内容到follower。在这个过程中，在leader上没有额外的disk空间使用。由于块是会并发地被修改，这可能会导致从的disk镜像不一致。当每一块从leader传输的时候，注意它的last modification time。
3. 获取一个disk内容的copy-on-write快照。一旦取得了，leader就有了一个disk内容的一致性拷贝，但是由于客户端继续的操作disk会被修改，进而占用额外的disk空间。
4. 仅重传第2步和第3步的快照中相比变化了的块。

增量清理的方法

增量的方法做压缩，如同log cleaning和LSM tree，是可能的。尽管他们快照的实现会更复杂，增量的方法仍然有几个令人渴望的特点：

• 每次只操作数据的一部分，所以压缩的负载随着时间来看是均匀的。
• 对disk的写入更有效率，包括正常操作和压缩期间，都会使用大的、顺序写。增量的方法也可以有选择地压缩disk上最具可回收价值的空间，因此相比memory-based的状态机会写入更少的数据到disk上。
• 可以非常简单地传输一致性状态快照 ，因为并不会in-place地修改disk的区域。

5.3.1节和5.3.2节首先描述了log cleaning和LSM tree通常情况下的基础知识。之后[5.3.3]节讨论如果应用到Raft中。

log清理基础

Log cleaning是在log-structured文件系统

译者注：可以参考维基百科

词条的内容中被引入的，并且最近被提议应用到内存文件系统比如RAMCloud中。原则上讲log cleaning可以被使用在任何数据结构上，尽管一些相比其他有效地实现起来会更困难。

Log cleaning维护日志作为记录系统状态的地方。为了优化顺序写而设计，并且也使得随机读更有效。因此，需要索引结构提升读取时的定位速度。

在log cleaning中，日志被分割到连续的区域(regions)之中，称之为段(segments)。每个log cleaner压缩日志的途径都使用一个3步的算法：

1. 首先选择要清理的段，这些段累积了大量的废弃entries。
2. 然后把有效的entries从那些段中拷贝到日志的头部。
3. 最后释放那些段的存储空间。

为了最小化对正常操作的影响，这个过程应该并发地做。

由于将有效的entries转发到日志的头部，因此这些entries将失去重放的顺序。Entries可以包含附加的信息(比如version number)以在log应用的时候重建正确的顺序。

选择哪些段做清理的策略对性能有非常大的影响；先前的工作提出了一个成本-效益策略，该策略不仅考虑到有效entries所占用的空间量，而且还考虑了这些条目可能存活的时间。

log-structured merge trees基础

LSM tree最先是被O’Neil提出并且之后通过BigTable流行于分布式系统(Cassandra、HyperDex、LevelDB、RocksDB)。

LSM tree像tree的结构存储有序的kv对。在高层级，对disk使用类似于log cleaning的方法：大的顺序写并且不in-place地修改disk上的数据。然而，LSM tree并没有在日志中维护所有状态，而是重新组织状态以便更好地进行随机访问。

典型的LSM tree将最近的写入在disk保持一份小的log。当log达到一定的大小后，对key进行排序并且写入一个叫做run的文件中。Runs不会in-place修改，但是会周期性地对runs进行merge，产生新的runs并丢弃旧的，merge的过程像merge sort，参考图5.1。

在正常操作期间，状态机可以直接在这些数据上操作。对于读一个key来说，首先检查是否在最近的log中有修改，之后检查每一个run。为了避免对每一个run做key的检查，一些系统对每一个run创建了bloom filter。

Raft中的日志清理和LSM-tree

我们还没有尝试在LogCabin中实现log cleaning或者LSM tree，但是我们推测两者都会做的很好。把LSM tree应用到Raft是相当直截了当的。因为Raft log已经在disk上持久存储了最近的entries，LSM tree可以在内存中以更方便的tree的格式保存最近的entries。这将提高查找的性能，并且当Raft log达到指定大小的时候，这个tree也可以直接刷成disk的一个新run。传输状态的时候leader需要把所有的run发送给follower(不包含in-memory tree)；幸运地是runs都是不可变的，因此传输期间不设计runs被改变。

把log cleaning应用到Raft就不是这么明显了。

译者注：懒得翻译了，反正应用有限，自己看看论文原文吧。简单说下就是原始的log cleaning算法meta和data混合在日志里，这样的话一旦开始前文提到的日志清理了，就会导致整理后的entries顺序乱了，也会出现类似于文件洞的section空洞。解决办法就是对于log cleaning，改造为meta和data分离，meta做Raft log，data在状态机中。

可供选择的：leader-based的方法

略。

日志中存储快照

略。

非常小的状态机使用Leader-based的方法

略。

讨论

略。