摘要
分布式共识是分布式系统最重要的构建块之一。 Fast Paxos 是用于分布式共识的 Paxos 算法的最新变体之一。 Fast Paxos 允许接受者在快速回合次中单方面对其选择的值进行投票,从而消除了达成共识的沟通步骤。作为权衡,协调者必须建立一个大于 Classic Paxos 中使用的简单多数的法定人数。本文介绍了 Fast Paxos 算法的理论、实现和综合性能评估。与 Lamport 的原始文章相比,该理论以更易于理解的方式描述。特别是,导出了一个易于实现的协调器取值规则。在实现状态机复制的 Fast Paxos 时,开发了许多附加机制来应对实际场景。此外,实验表明 Fast Paxos 最适合在单客户端配置中使用。即使在局域网中存在两个或多个并发客户端也会导致频繁的冲突,这将降低系统吞吐量并增加客户端所经历的平均响应时间。由于频繁的冲突,Fast Paxos 在存在中到大量并发客户端的情况下实际上比 Classic Paxos 表现更差。
关键词:分布式共识、端到端延迟、容错、概率密度函数、仲裁要求、状态机复制、系统吞吐量
概论
分布式共识是分布式系统最重要的组成部分之一。例如,如果不使用一些分布式共识算法来确保所有副本保持一致,就不可能构建高可用性云服务。Fast Paxos 是用于分布式共识的原始 Paxos 算法(简称 Classic Paxos)的最新变体之一。Classic Paxos 非常适合状态机复制,它已被用于许多实际的容错系统中。 Fast Paxos 旨在通过使用更大的仲裁规模来进一步减少达成共识的延迟。与 Classic Paxos 类似,Fast Paxos 以回合次运行,每回合有两个阶段。如果一回合内没有达成共识,将启动新一回合的活跃度。在 Fast Paxos 中,可以有两种不同类型的回合:快速回合和经典回合。经典回合次的运行方式与经典 Paxos 中的回合次相同,只是协调器处的值选择规则不同,这将在后面的部分中解释。在 Lamport 于 2006 年发表的原始文章中,法定人数要求以及值选择规则取决于对该文中中称为 \(O4(v)\) 的以下观察结果的评估: