Delos中的虚拟共识
在我们进入这篇文章之前，如果你点击上面的链接，然后下载并打开这篇文章pdf，你可能会注意到USENIX熟悉的红色/橙色的飞溅，并欣赏它的完全开放的访问。Usenix是一个非营利性组织，致力于提供免费的内容和研究-包括会议记录和活动的录音陈述。如果今年没有面对面的会议，收入就会下降，活动也会受到威胁。如果你想帮助他们，你可以选择捐款，成为会员，甚至与你的组织讨论成为合作伙伴、捐赠者或赞助人。每一点都有帮助！
早在2017年，Facebook的工程团队就遇到了一个问题。他们需要一个表店来支持核心控制平面服务，这意味着对耐用性、一致性和可用性有强有力的保证。他们还需要尽快投入生产，目标是在6到9个月内投产。虽然最终这个新系统应该能够利用共识的最新进展来提高性能，但考虑到6-9个月的投产目标，这是不现实的。因此，现实地说，所能做的就是选择一个现有的共识实施方案，并将其整合起来。但是，集成现有实现本身也会带来问题：
将系统覆盖在现有的共享日志(如LogDevice)上将使我们能够快速投入生产，但也会将我们永久地与该共识实现的容错和性能属性捆绑在一起。
从字面上看，Facebook需要的是一份扔掉它的计划。也就是说，一个让他们利用现有实现快速投入生产的计划，然后能够在以后进行升级，而不会干扰系统操作(没有人想要取下中央控制平面进行维护！)。这就需要最古老的工具：一定程度的间接性。换句话说，基于API的抽象胜过共识，以及支持这些实现的热插拔的运行时。作为达成共识的API，最突出的候选者是共享日志。
最近，共享日志已经成为研究界和产业界达成共识的API。应用程序可以通过此API复制状态，方法是将更新附加到共享日志，检查其尾部，并从其中读回更新。共识协议隐藏在共享日志API之后，允许应用程序在部署时绑定到任何实现。
共享日志API的背后是一个日志抽象，它将日志位置映射到日志条目。如果您认为这有点像将内存地址映射到内存中的数据，那么就会想到另一个类似的东西：虚拟地址空间。一个逻辑日志，但日志地址空间的不同部分映射到不同的备份共享日志实例。这是Delos的核心理念，这是一个虚拟化共识的VirtualLog。
我们提出了一种新的虚拟共享日志(或虚拟日志)的抽象。VirtualLog公开了一个传统的共享日志API；它上面的应用程序不知道它的虚拟化性质。在幕后，VirtualLog将多个共享日志实例(称为Loglet)链接到单个共享日志中。
这是一个如此强大的想法，我可以想象，从现在开始，任何地方的分布式系统实现者都会采用它。VirtualLog给我们带来了什么？
首先，它解决了升级问题。我们有一个现有的Loglet将日志条目写入地址空间。为了升级，此Loglet管理的地址空间部分被密封以防止进一步写入，然后Loglet链被重新配置为在尾部添加新的Loglet。这不仅仅是理论上的，当Delos每天处理超过18亿笔交易时，Facebook实际上已经在生产中做到了这一点。最初的Delos版本在8个月后投入生产，使用的是动物园管理员支持的Loglet实现，4个月后，它被换成了新的定制NativeLoglet，端到端延迟提高了10倍。
一旦您有了从一种Loglet链配置到另一种Loglet链配置的可信重新配置协议，您就可以做很多有趣的事情。例如，Loglet可能是相同订购协议的实例，但参数不同，或者它们可能是完全不同的日志实现(例如，用RAFT替换Paxos)，或者它们可能是外部存储系统上的垫片。如果您有一个具有自己的领导者选举、内部重新配置和纪元的现有实现，那么它可以愉快地位于Loglet抽象之下。但至关重要的是，Loglet不再需要处理所有这些复杂性：
虽然VirtualLog的重新配置机制只能用于在完全不同的Loglet实现之间迁移，但它也可以在同一Loglet协议的不同实例之间切换，同时更改领导权、角色、参数和成员资格。因此，Loglet本身可以是静态配置的协议，而不需要对重新配置提供任何内部支持。事实上，Loglet甚至不需要实现容错共识(即通过领导人选举实现高度可用的附加)，只要它提供一个容错密封命令就可以了，这在理论上更弱，实现起来也更简单。
这种关注点的分离将重新配置转移到VirtualLog控制平面，让Loglet负责数据平面。它使重新配置变得更容易，并简化了Loglet的实现。如果Loglet追加失败，它将被简单地密封，并且VirtualLog切换到一个新的Loglet。
最小的Loglet需要通过共享日志API提供完全有序的持久存储。它可以在静态配置中做到这一点，不支持角色或成员更改，也不支持领导人选举。然而，它必须提供的是一个高度可用的密封命令，以防止任何新的附加被确认。
一旦密封，Loglet就永远不能解封。因此，我们有几个方便的属性，可以使实现Seal比实现通用的高可用性的append容易得多：只有一个值可以被提出，而且这个值是粘性的。在Facebook的NativeLoglet实现中，Seal只需在一定数量的服务器上设置一点即可。
除了SEAL之外，最小的Loglet还负责自己的故障检测，在检测到故障时要求VirtualLog重新配置，并提供新的Loglet配置(不包括出现故障的服务器)。
现有的共识系统通常将配置和历元信息内联存储在与其他命令相同的完全有序的日志中。对于VirtualLog，这意味着在新Loglet被密封之前，将新Loglet的配置写入传出Loglet的日志地址空间中。这将增加Loglet的复杂性，要求它们高度可用于附加，而不仅仅是密封。
VirtualLog改为使用单独的MetaStore，其工作是随着时间的推移管理VirtualLog的配置。因为重新配置发生的频率低于常规命令排序，所以重新配置的共识协议可能更倾向于简单性，而不是彻底的性能。对于Facebook的Delos来说，10ms的重新配置延迟是可以接受的。
MetaStore公开支持条件写入的单个版本化寄存器：写入需要提供新值和预期的现有版本。任何客户端都可以启动重新配置，或完成由另一个客户端开始的重新配置。重新配置有三个步骤：
客户端通过密封其活动段来密封当前链。调用check Tail现在将返回新活动段的开始。这是一个幂等运算。
重新配置的客户端将新的链写入MetaStore。由于条件写入，如果多个客户端竞相重新配置，最多只能有一个客户端获胜。
重新配置客户端从MetaStore获取新的链(在步骤2中写入失败的情况下)。
尝试在步骤1之后写入旧的活动段的客户端将收到‘Seed’错误代码，并且可以在从MetaStore获取最新链后重试。
Delos目前支持三个分散的Loglet，它们充当外部服务(ZooKeeper、LogDevice服务和用于冷藏的备份服务)的填补。它还有两个自己的Loglet实现，既可以聚合也可以分解运行：NativeLoglet和StridingLoglet。
在生产中，Facebook以融合的形式使用NativeLoglet。NativeLoglet通过在一定数量的服务器上设置位来实现密封。它使用中央定序器为命令分配位置，并将请求转发给LogServer。一旦多数人同意，追加就被认为是全球承诺的。如果定序器失败，NativeLoglet就不能用于追加。
实际上，我们发现这个协议比容错共识容易实现得多：仅用了不到4个月的时间就实现和部署了一个产品级质量的原生Loglet。
StripedLoglet是事情开始变得更加有趣的地方。StriedLoglet负责全局日志地址空间的一部分，但在内部它会在多个嵌套的Loglet上进一步映射(条带化)该部分。
这提供了一种简单的方式(大约300loc)来扩展吞吐量。例如，可以通过引入旋转定序器(多个定序器在它们之间划分地址空间并共享相同的下属LogServer)来缓解共享定序器瓶颈。或者，可以将地址空间映射到多个底层LogServer集群，以增加吞吐量。
即使它是复合的，StriedLoglet仍然必须作为一个整体被密封，即使只需要重新配置它的一个条纹。
评估部分提供了大量关于在生产中运行Delos的经验的好信息，以及一些综合基准。从ZK Loglet到NativeLoglet的产品内转换于2019年4月2日首次完成，在P99版本中，GET的性能提高了10倍，写入性能提高了5倍。
我最喜欢的例子是一个非常酷的重新配置用例。在大多数情况下，Delos使用聚合的Loglet实现运行，因为这减少了非常关键系统的外部依赖性。不过，在日志峰值下，它可以重新配置为使用分解的Loglet运行，从而提供更高的吞吐量。一个相关的例子是，当Delos在聚合模式下运行时，例如五个聚合数据库副本中的两个崩溃。现在，数据库和共享日志是命运共享的，如果再有一个节点丢失，则会面临风险(…。
在这种情况下(这种情况并不少见)，我们发现将系统重新配置为分解日志是很有价值的，暂时将数据库和日志的命运分开。一旦数据库恢复到五个副本，我们就重新配置回去。
虚拟化的开销低得令人满意：在p99延迟时约为100-150微秒，重新配置时约为10毫秒，对峰值吞吐量没有影响。
这一切听起来都很神奇，不是吗？有几个限制：(1)利用推测或交换性的共识协议目前不适合Loglet API。“在未来的工作中，我们计划将虚拟共识扩展到部分有序的共享日志。”以及(2)VirtualLog驱动的重新配置存在延迟问题，这在您的场景中可能很重要，也可能不重要。
