无冲突复制数据类型(CRDT)与Paxos或Raft

Question

什么时候使用像CRDT而不是paxos或筏这样的东西是个好主意？

Answer 1

如果您可以使用CRDT之类的东西,请执行此操作.你应该得到更好的表现.它还支持有趣的用例,例如脱机工作,然后再合并.然而,并不总是能够设计出CRDT适合您的东西.在这种情况下,paxos可以为您解决难题.

但即使您决定使用paxos,通常也应该通过paxos算法直接限制工作量.相反,出于性能原因,您希望为主要选举等必要操作保留paxos,然后让复制的主设置处理大多数决策.(在高吞吐量环境中,主服务器可能会执行某些操作,例如将特定分片的委托责任委派给特定的子级,这些子级会相互复制.不要让主服务器成为瓶颈...)

也就是说,声称你将挥动paxos的魔杖比在实践中实际执行它更容易.从这个角度来看,您可能会发现http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/chubby-osdi06.pdf是一个有趣的描述现实世界的困难paxos实施很可能会遇到.

Answer 2

我想这家伙知道他在说什么:

博客

视频

关于分布式系统的结论

Answer 3

CRDTs 和 Paxos 有不同的目标，在不同的场景下使用。它们的共同点是帮助程序员处理并发/复制。CRDT 是假设会发生并发更新的数据类型。Paxos 是一种协议，通过对它们强制执行总顺序来强制它们不会。 让我们更详细地了解一下。

假设我们有一个复制集，它在两个不同的地方复制。

使用 Paxos 可以保证对集合的写入将由每个副本以相同的顺序执行。更一般地说，它保证所有副本都同意集合的状态如何演变。

例如，如果您让 user1 在 replica1 上执行 update1，将元素 1 添加到复制集中，同时 user2 执行 update2，在 replica2 上添加 element2，Paxos 将使副本同意这些更新的给定顺序，或者可能同意选择一个两次更新，丢弃第二次，这取决于您如何使用它以及您想要实现的目标。如果 Paxos 结果是 update1 在 update2 之前，则每个副本都将按该顺序更新集合。因此，在这些更新的同时读取集合的用户可以观察到，无论他们在哪里（在哪个副本）读取，只有集合的以下状态（假设集合在开始时为空）：

{}（空集）

{元素1}

{元素1，元素2}

此外，这些状态只能按该顺序看到，这意味着一旦集合的状态为 {element1, element2}（在每个副本上），后续读取将不会返回 {} 或 {element1}。

积极的一面：这个集合很容易推理，因为它相当于一个不可复制的集合。

消极方面：不可用：如果副本不能相互通信（网络分区），则您的集合无法更新，因为无法达成一致。低性能，高延迟：协议要求副本在回复客户端之前同步。这会导致与副本之间的延迟成正比的延迟。

CRDT 的保证较弱。CRDT 集不等同于顺序的、单副本的。它假定对于副本的更新方式没有一致意见或总顺序。

CRDT 保证如果集合的两个副本都看到相同的更新（无论它们看到它们的顺序如何），那么它们将表现出相同的状态；副本将收敛。

在我们的两个用户同时执行更新的示例中，一个不运行 Paxos 来对集合上的操作进行排序的系统（这种情况会发生，例如，在最终或因果一致性下），将允许副本 1 添加元素 1 而副本 2 正在添加元素 2

因此，replica1 处的状态将是：{element1}

副本 2 处的状态将是：{element2}

此时，副本出现分歧。稍后，当副本同步时，它们将交换它们的更新，最终表现出这种状态：

副本 1 处的状态将是：{element1, element2}

副本 2 处的状态将是：{element2, element1}

此时，副本已经收敛。

与这些更新同时读取集合的用户可以观察到，根据他们读取的位置（在哪个副本），集合的以下状态（假设该集合在开始时为空）：

{}（空集）

{element1}（如果他们从replica1 中读取）

{element2}（如果他们从replica2读取）

{元素1，元素2}

{元素2，元素1}

消极方面：这个集合很难推理，因为它显示了不能在顺序集合中出现的状态。在我们的例子中，我们只观察到两个并发添加到一个集合的情况，这很简单。并发添加和删除更复杂 有许多具有不同问题的数据类型：

收敛和交换复制数据类型的综合研究

积极的一面：高可用性：如果副本不能相互通信（网络分区），你的集合可以被更新。副本将在重新连接时同步。高性能、低延迟：副本在回复客户端后立即回复客户端并在后台同步。