EagleBear2002 的博客

概念与定义

先明确一些定义：

• Quorum：在 Classic Paxos 中一直通过多数派（Majority）来保证算法的正确性，对多数派再进一步抽象化，称为“Quorum”，要求任意两个 Quorum 之间有交集（从而间接表达了 majority 的含义）。
• Round：在 Classic Paxos 中，提议者每次提案都用一个全序的编号表示，如果执行顺利，该编号的 Proposal 在经历 Phase1，Phase2 后最终会执行成功。在 Fast Paxos 称这个带编号的 Proposal 的执行过程为“Round”。
• i-Quorum：在 Classic Paxos 执行过程中，一般不会明确区分每次 Round 执行的 Quorum，虽然也可以为每个 Round 指定一个 Quorum。在 Fast Paxos 中会通过 i-Quorum 明确指定 Round i 需要的 Quorum。
• Classic Round：执行 Classic Paxos 的 Round 称为 Classic Round。
• Fast Round：如果领导者发送了 Any 消息，则认为后续通信是一个快速回合；若领导者未发送 Any 消息，还是跟之前一样通信，则后续行为仍然是 Classic Round。根据 Lamport 描述，Classic Round 和快速回合可通过 Round Number 进行加以区分。

Classic Paxos

参与角色

摘要

正如在实践中使用的那样，传统的共识算法需要三个消息延迟，然后任何进程才能学习选择的值。 Fast Paxos 是经典 Paxos 算法的扩展，它允许在两个消息延迟中学习值。非正式地解释了该算法的工作方式和原因，该算法的 TLA+ 规范作为附录出现。

简介

共识问题需要一组过程来选择单个值。本文考虑了非拜占庭错误的异步消息传递系统中的共识问题。这个问题的解决方案绝不能允许选择两个不同的值，尽管有任意数量的故障，并且如果足够多的进程没有故障并且可以相互通信，它最终必须选择一个值。

在共识问题的传统陈述中，每个过程都提出一个值，并且选择的值必须是那些提出的值之一。不难看出，任何解决方案都需要至少两次消息延迟，然后任何进程才能了解已选择的值。许多算法在最好的情况下实现了这种延迟。经典的 Paxos 算法很受欢迎，因为它在实际系统中使用时在正常情况下实现了最佳延迟。

摘要

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

资本主义再生产和资本积累

资本主义的简单再生产

物质资料的生产是人类社会的基础。人类社会要生存下去，生产就不能中断，生产过程必须连续不断地反复进行。所以生产实际上就是再生产过程。

生产规模不变的再生产叫做简单再生产。

工资是工人创造价值的一部分。所以，决不是资本家拿出工资来养活工人，而是工人凭借自己的劳动在养活自己。不仅不是资本家养活工人，恰恰相反，是工人养活了资本家。

货币转化为资本

资本总公式及其矛盾

商品交换发展的结果产生货币，而货币正式资本的最初表现形态。资本最初表现为货币，但货币并不一定就是资本。货币是商品交换的媒介，货币的运动就是按现代公式进行的：

\[ W(商品)-G(货币)-W(商品) \]

公式两端是使用价值不同而价值量相等的两种商品，货币起着交换的媒介作用。作为资本的货币，它的运动就不同了。资本的运动是以货币为起点，又以货币为终点的。它的公式是：

商品

商品是用来交换的劳动产品。资本主义生产关系首先是从小商品生产者的分化中产生的。所以小商品生产即简单商品生产是资本主义经济的历史起点。商品是资本主义经济的细胞。而且，在这个最常见的商品中，已经包含着资本主义一切矛盾的胚芽。

商品的两个因素：使用价值和价值

物的有用性就是物的使用价值。使用价值是商品的第一个因素。使用价值是商品体的自然属性。使用价值构成社会财富的物质内容。商品不但应该有使用价值，还应具有与其他商品相交换的属性，即还要有交换价值。使用价值是交换价值的物质承担者。

交换价值首先表现为一种使用价值同另一种使用价值相交换的量的比例。

前言

相比于无状态的分布式系统，有状态的数据库在分布式领域将会面临更多的挑战。

故障模型

每个节点保存本地状态，通过网络来互相同步这些状态。同时节点需要访问时间组件来获取当前时间（逻辑时间或物理时间）。

这些环节没有一个是可靠的。不可靠贯穿了分布式系统的整个生命周期。

读写异常

并发操作带来的数据不一致性包括丢失修改（lost update）、不可重复读（non-repeatable read）和读“脏”数据（dirty read）。

丢失修改

两个事务 \(T_1\) 和 \(T_2\) 读入同一数据并修改，\(T_2\) 的提交结果破坏了 \(T_1\) 的提交结果，导致 \(T_1\) 的修改被丢失。

不可重复读

一致性是高可用的必备条件

分布式数据库的节点并不总是处于活动状态且相互能够通信的。系统高可用性是分布式数据库一个极其重要的特性。

为了使系统能够高度可用，系统需要被设计成允许一个或多个节点的崩溃或不可访问。

高可用必须要尽可能满足业务连续性和数据一致性这两个指标。第三个因素网络分区会对可用性产生影响。

CAP 理论与注意事项

摘要

传统的容错分布式事务是在 Paxos 共识协议之上的传统并发控制协议。这种方法提供了可扩展性、可用性和强一致性。然而，当用于广域存储时，这种方法会引发两次跨数据中心的连续协调：一次用于并发控制，然后一次用于共识。在本文中，我们主要观察到并发控制和共识所需的协调高度相似。具体来说，每个都试图确保交易的序列化图是非循环的。我们在 Janus 的设计中利用了这种洞察力，这是一个统一的并发控制和共识协议。 Janus 的目标是编写为存储过程的一次性事务，这是一种常见但受限制的事务类。像 MDCC 和 TAIR 一样，Janus 可以在一次往返中提交此类中的不冲突事务。与 MDCC 和 TAPIR 不同，Janus 避免了由于争用而中止：只要网络运行良好并且每个服务器副本的大多数都处于活动状态，它最多在两次往返中提交此类中的冲突事务。

我们将 Janus 与分层设计和 TAPIR 在此类中的各种工作负载下进行比较。我们的评估表明，在无竞争的微基准测试中，Janus 的吞吐量是分层系统的 5 倍，是 TAPIR 吞吐量的 90%。当工作负载竞争时，Janus 提供比基线低得多的延迟和更高的吞吐量（高达 6.8 倍）。

简介

可扩展、可用且高度一致的分布式事务通常是通过在 Paxos 共识协议复制的数据存储分片之上分层传统并发控制协议来实现的。将数据分片成许多可以由不同服务器存储和服务的小子集提供了可扩展性。尽管服务器出现故障，但通过共识复制每个分片可提供可用性。尽管不同事务的数据访问存在冲突，但使用 USENIX 关联并发控制跨复制分片协调事务可提供强一致性。这种方法在实践中很常用。例如，Spanner 实现了两阶段锁定 (2PL) 和两阶段提交 (2PC)，其中数据和锁都由 Paxos 复制。作为另一个例子，Percolator 实现了机会并发控制 (OCC) 的变体，它在 BigTable 之上使用 2PC，它依赖于主备份复制和 Paxos。