algorithm - Paxos 和 Cassandra 中的 W+R>=N 有什么区别？

Question

类似 Dynamo 的数据库（例如 Cassandra）可以通过 quorum 来强制一致性，即应以 W+R>N 的方式选择同步写入的副本数 (W) 和要读取的副本数 (R) N 是复制因子。另一方面，像 Zookeeper 这样的基于 PAXOS 的系统也被用作一致的容错存储。

这两种方法有什么区别？PAXOS 是否提供 W+R>N 模式未提供的保证？

Answer 1

是的，Paxos 提供了类似 Dynamo 的系统及其读写仲裁不提供的保证。不同之处在于如何处理故障以及在写入期间会发生什么。成功写入后，两种系统的行为相似。数据将被保存并可供以后读取（直到被覆盖或删除）等等。

差异出现在写入期间和失败之后。在向最终一致的系统写入内容时，直到您从 W 节点获得成功的答案，然后数据可能已写入某些节点而不是其他节点，并且无法保证整个系统就当前值达成一致。如果您此时尝试读回数据，一些客户端可能会取回新数据和一些旧数据。换句话说，系统不是立即一致的。这是因为写入在这些系统中的节点之间不是原子的。通常有一些机制可以“修复”这样的不一致性，并且“最终”系统将再次变得一致（即读取将再次始终返回相同的值，直到写入新的内容）。这就是为什么他们经常被称为“

使用 Paxos，可以跨节点进行原子写入，因此可以避免节点之间的不一致。Paxos 算法可以保证非故障节点在任何时间点都不会对写入的结果产生分歧。写入要么在任何地方成功，要么在任何地方都不成功。在任何时候都不会出现任何不一致的读取（当然，如果正确实施并且所有假设都成立）。然而，这是有代价的。主要是，当太多节点（或它们之间的通信）不工作时，系统可能需要延迟一些请求并且不可用。这对于确保没有给出不一致的答复是必要的。

总结一下：主要区别在于类似 Dynamo 的系统可以在写入期间或失败一段时间后返回不一致的结果（但最终会从中恢复），而基于 Paxos 的系统可以通过有时被取而代之的是不可用和延迟请求。

Answer 2

Paxos 实现起来并不简单，而且价格昂贵，以至于许多使用它的系统也使用提示，或者仅将其用于领导者选举或其他用途。但是，它确实在出现故障的情况下提供了保证的一致性——当然要受到其特定故障模型的限制。

我看到的第一个基于仲裁的系统假设某种领导者或事务基础设施可以确保足够的一致性，您可以相信仲裁机制有效。这个基础设施很可能是基于 Paxos 的。

查看诸如https://cloudant.com/blog/dynamo-and-couchdb-clusters/之类的描述，Dynamo 似乎不是基于保证其仲裁系统一致性的基础设施 - 所以它是非常聪明还是偷工减料？根据http://muratbuffalo.blogspot.co.uk/2010/11/dynamo-amazons-highly-available-key.html，“Dynamo 系统强调可用性到牺牲一致性的程度。摘要写着“Dynamo 在某些故障场景下牺牲一致性”。实际上，后来很清楚 Dynamo 即使在没有故障的情况下也会牺牲一致性：Dynamo 可能会变得不一致存在多个并发写入请求，因为副本可能因多个协调器而分歧。” （结束报价）

因此，在 Dynamo 中实现的仲裁的情况下，Paxos 似乎提供了更强的可靠性保证。

Answer 3

Paxos 和 W+R>N quorum 试图解决稍微不同的问题。Paxos 通常被描述为复制状态机的一种方式，但实际上它更像是一个分布式日志：写入日志的每个项目都会获得一个索引，并且不同的服务器最终持有相同的日志项目 + 其索引。（复制状态机可以通过将状态机的输入写入日志来实现，每个服务器根据它们的索引在约定的输入上重放状态机）。你可以在我在这里写的一篇博文中了解更多关于 Paxos 的信息。

W+R>N quorum 解决了在多个服务器之间共享单个值的问题。在学术界它被称为“共享寄存器”。共享寄存器有两个操作：读取和写入，我们期望读取返回之前写入的值。

因此，Paxos 和 W+R>N quorum 存在于不同的域中，并且具有不同的属性（例如，Paxos 保存了一个有序的项目列表）。但是，Paxos 可以用来实现共享寄存器，并且可以使用 W+R>N quorum 来实现分布式日志（尽管效率很低）。

综上所述，有时 W+R>N 仲裁并没有以“完全稳健”的方式实现，因为它需要不止一轮的通信。因此，在需要低延迟的系统中，W+R>N 仲裁的实现可能会提供较弱的属性（例如，冲突的值可以共存）。

综上所述，理论上，Paxos 和 W+R>N 可以达到相同的目标。实际上，这将是非常低效的，并且对于稍微不同的东西，每个都更好。更实际的是，W+R>N 并不总是完全实现，因此为了速度而牺牲了一些一致性属性。

更新：Paxos 支持一个非常通用的故障模型：消息可以被丢弃，节点可以崩溃并重新启动。W+R>N quorum 方案有不同的实现，其中许多假设不太普遍的失败。因此，两者之间的差异还取决于对支持的可能故障的假设。

Answer 4

没有区别。仲裁的定义表明任何两个仲裁的交集都不为空。简单多数法定人数是一个例子而不是一个定义。看看 Lamport 博士后来的论文“Vertical Paxos”，他在其中给出了一些其他可能的 quorum 配置。

多法令 paxos 协议（AKA Multi-Paxos），在稳定状态下它只是两阶段提交。仅当领导者失败时才需要更改选票号码。

Zookeeper 的复制协议（ZAB）和 RAFT 都是基于 Paxos 的。区别在于领导者失败后的故障检测和转换。

Answer 5

正如其他答案中提到的，在 R+W > N 系统中，写入并非在所有节点上都是原子的，这意味着当写入正在进行时（或在写入失败期间），一些节点将具有更新的值和一些较旧的值。以 n=3、r=2 和 w=2 的系统为例。为清楚起见，我们假设 3 个节点分别命名为 A、B 和 C。考虑这种情况：正在写入；节点 A 已更新，而 B 和 C 仍在接收更新值的过程中。从 A 和 B 读取的客户端将看到较新的值（使用版本向量或上次写入获胜解决），从 B 和 C 读取的客户端将看到旧值。这种类型的读取不被认为是可线性化的。使用适当的线性化系统（如 Paxos 或 Raft）不会出现此类问题。