什么时候使用 CRDT 之类的东西而不是 paxos 或 raft 是个好主意？
问问题
10029 次
7 回答
35
如果您可以使用 CRDT 之类的东西，请这样做。您应该获得更好的性能。它还支持有趣的用例，例如离线工作然后稍后合并。但是，并非总是可以设计出让 CRDT 为您工作的东西。在这种情况下，paxos 可以为您解决难题。
但即使你决定使用 paxos，通常你也应该限制直接通过 paxos 算法完成的工作量。相反，出于性能原因，您希望为必要的操作（例如主选举）保留 paxos，然后让复制的主设置处理大多数决策。（在高吞吐量环境中，master 可能会做一些事情，比如将特定分片的责任委托给特定的子节点，这些子节点相互复制。不要让 master 成为瓶颈......）
也就是说，声称你会挥动 paxos 的魔杖比在实践中实际做到这一点要容易得多。有鉴于此，您可能会发现http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/chubby-osdi06.pdf是对现实世界的困难的有趣描述paxos 实现很可能会遇到。
于 2012-06-29T00:13:04.477 回答
15
于 2013-11-12T13:19:51.497 回答
9
CRDT 和 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}（如果他们从副本 1 读取）
{element2}（如果他们从副本 2 中读取）
{元素1，元素2}
{元素2，元素1}
负面的一面：这个集合很难推理，因为它显示了在顺序集合中不可能出现的状态。在我们的示例中，我们只观察到两个并发添加到一个集合的情况，这很简单。并发添加和删除更复杂有许多具有不同问题的数据类型：
积极的一面：高可用性：如果副本不能相互通信（网络分区），您的集合可以更新。副本将在它们重新连接时同步。高性能、低延迟：副本在回复客户端后立即回复客户端并在后台同步。
于 2016-10-12T10:55:45.930 回答
4
CRDT Treedoc 示例存在缺陷。当两个系统使用相同的键同时插入时，每个节点都需要一个消歧器。
发生这种情况后，系统不再可能在具有相同键但消歧器不同的条目之间插入，因为这需要系统插入另一个相同的键但控制消歧器的顺序。消歧器并不密集，所以这并不总是可能的。如果消歧器是另一棵树，那么您解决了一个问题，但随后需要另一个更深层次的冲突解决机制......等等。
这个未提及的问题，加上您需要进行两阶段提交来整理元数据的事实让我认为 CRDT 仍在进行中。
于 2014-05-12T13:13:51.147 回答
2
我们有多个指标：
- 吞吐量（CRDT 和 Paxos 是相同的，因为无论 CRDT 还是 Paxos，所有请求最终都会复制到所有副本上）；
- 延迟（CRDT 比 Paxos 更好，因为它写入的副本数量较少）；
- 可靠性（CRDT 比 Paxos 弱，因为它写入的副本数量较少（小于多数），这可能导致状态丢失）；
- 一致性（CRDT 比 Paxos 弱，因为它允许没有同步点的并发写入（基本上没有重叠副本），而 Paxos 写入总是需要重叠副本来进行序列化）。
我的建议是，当副本彼此相距不远时（例如，在数据中心内），我们应该使用 Paxos，而当网络分区正常时（例如，断开连接的移动设备），我们应该使用 CRDT。
于 2014-06-19T09:35:39.233 回答
1
评论@btilly 的回复：
该主题中的问题与不同的一致性模型以及设计模式有关：
CRDT 和 Paxos 是非常不同的东西，必须根据您的架构要求来决定其用法。我认为处理它的最佳方法是查看已成功应用这些算法的用例。
使用模式：
CRDT 可用于客户端（即移动设备）和服务器之间的数据同步、实时协作编辑、dist-db 实现中的值同步以及最终一致性很好的所有其他情况。
PAXOS 主要用于支持系统基础设施的专有系统（即 Chubby），或用于在 BigTable、Datastore、Spinnaker、Spanner 等分布式数据库系统中实现同步。
RAFT 在 ETCD、Consul 等 OSS 基础设施项目中更受欢迎...
（不记得 CockroachDB 和 TiDB 是基于什么的）
还有一个 BFT，但它用得较少。
ps PAXOS != ZooKeeper。ZooKeeper 使用称为 ZAB 的不同算法，它不是复制状态机，而是具有单一写入器和宽松读取模型的复制快照机。Google 的 Chubby 基于 Paxos，但它是专有的。
pss 有趣的是，PAXOS 这些年来是如何发展的。在过去的 20 年中，发明了许多变体来处理边缘情况、仲裁大小和集群重新配置的各种优化。
于 2018-06-18T08:20:53.957 回答
-2
什么时候合适。然而，PaxOS 并没有那么糟糕，因为它的吞吐量通常与 CRDT 相同，更不用说可靠性要高得多（CRDT 可能导致状态丢失），而且它的延迟也不是那么糟糕，因为它只需要多数副本回复而不是全部回复。
于 2014-02-24T03:40:30.383 回答