摘要
分布式共识是分布式系统最重要的构建块之一。 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)\) 的以下观察结果的评估: