什么时候使用Paxos这样的共识算法而不是Vector Clock？ [英] When do I use a consensus algorithm like Paxos vs using a something like a Vector Clock?

问题描述

我已经阅读了很多有关确保分布式系统中节点之间一致性的不同策略的信息，但是我在确定何时使用哪种算法方面遇到了一些麻烦。

I've been reading a lot about different strategies to guarantee consistency between nodes in distributed systems, but I'm having a bit of trouble figuring out when to use which algorithm.

我将在哪种系统上使用矢量时钟？哪种系统最适合使用Paxos之类的东西？两者是互斥的吗？

With what kind of system would I use something like a vector clock? Which system is ideal for using something like Paxos? Are the two mutually exclusive?

推荐答案

有一个由2个节点组成的分布式系统，用于存储数据。数据被复制到两个节点，因此，如果一个节点死亡，则数据不会丢失（耐用性）并继续提供服务（可用性）。而且，您还希望您的2节点系统每秒能够处理两倍的请求（可伸缩性）。

There's a distributed system of 2 nodes that store data. The data is replicated to both nodes so that if one node dies, the data is not lost (durability) and continues to be served (availability). And also you hope your 2-node system will handle twice as many requests per second (scalability).

假设对单个密钥的写入可以到达任何节点。您的客户写 1作为某个键的值，然后决定写 2。第一次写到节点＃1。它将复制请求发布到节点2。但是，您存储 2的请求早于复制请求到达节点＃2（记住，我们可以存储在任何节点上）。它存储 2，向节点＃1发出带有 2的复制请求，从中接收到具有 1的复制请求，将其 2更改为 1，而节点＃1将其 1更改为 2。现在，存储节点之间的数据不一致。另外，如果节点＃1死亡，那么您所拥有的只是节点＃2，其值为 1，同时您还记得在 1之后发送了 2 1，以及存储系统已经确认它已保存。实际上，根据您对存储系统的期望（读取写入内容，单调读取内容等），很多事情可能会出错，因此您需要一种方法来真正找出密钥的真实，良好和实际价值是，甚至防止系统以这种方式破坏数据。为此，存储系统需要知道在节点之间发生了什么之前发生的事情，或者甚至可能考虑到客户对事件顺序的看法。 矢量时钟和版本向量是实践中用于实现该目标或声明2个事件同时发生的技术，您需要其他方法来决定它们的结果。

Suppose the writes to a single key can come to any node. Your client writes "1" as the value for some key, then it decides to write "2". The first write goes to node#1. It issues a replication request to node#2. However, your request to store "2" comes to node#2 (we can store on any node, remember) earlier than the replication request. It stores "2", issues a replication request with "2" to node#1, receives a replication request with "1" from it, changes its "2" to "1", while node#1 changes its "1" to "2". Now you have inconsistency in your data between the storage nodes. Also, if node#1 dies, all you have is node#2 that has value "1", while you remember it very well that you sent "2" after "1", and the storage system has confirmed that it saved it. Actually, many things might go "wrong", depending on what you expect from your storage system (read your writes? monotonic reads? etc), so you need a way to actually find out what the true, good, actual value for the key is, or even to prevent the system from "corrupting" data in this way. For that, the storage system needs to know what happened before what, either between its nodes, or it might even include your clients vision of the order of events into consideration. Vector clocks and version vectors are some of the techniques used in practice to achieve that or claim that 2 events have happened concurrently and you need some other way to decide between the results of them.

为了避免所有这些复杂性，您决定以不同的方式解决问题：对某个键的所有写操作都将到达一个节点（称为 leader），并且它将将这些写入复制到另一个节点上。确实，这看起来像是一种更简单的方案：在一个节点（可能是一个进程）内，您拥有快速且行之有效的并发控制技术，可以轻松地对事件进行排序，可以以相同的顺序应用复制；而且，总是有权威的正确数据来源。唯一的问题是您的2个存储节点需要同意哪个节点是特定密钥的领导者。如果您有3个节点，其中一个节点死亡，则其他2个节点需要确定1）他们都认为旧领导者死亡，2）其中一个是新领导者。为此，存在共识协议（ Paxos ，两阶段提交，筏，Zab，三相提交等）。

You decide to tackle the problem in a different way in order to avoid all these complexities: all writes for a certain key will go to one node (called "leader"), and it will replicate these writes onto the other node. Indeed, that looks like a simpler scheme: within one node (and likely one process) you have fast and proven concurrency control techniques, can order events easily, can apply replication in the same order; also, there's always an authoritative source of the right data. The only problem is that your 2 storage nodes need to agree which node is the leader for a particular key. And if you had 3 nodes and one of them died, the other 2 would need to decide 1) that they both think the old leader died, 2) which one of them is the new leader. For that, consensus protocols exist (Paxos, 2-phase commit, Raft, Zab, 3-phase commit etc).

为什么不总是选择单个领导者（因此是共识协议）而不是无领导者计划（因此也是如此）版本向量之类的排序机制）？协商领导需要花费时间（最多可能需要几秒钟或数十秒），在此期间您的系统将不可用或在某些特殊模式下部分可用。无领导者也可以在其他一些条件下表现更好（例如，由于软件问题或网络问题导致领导者变慢：采用无领导者方法，其他节点可能会接替其职责）。随着参与者数量的增加，共识变得越来越困难，因此无领导者可能会更好地进行扩展。

Why not always choose single leader (and hence a consensus protocol) over leader-less scheme (and hence an ordering mechanism like version vectors)? Negotiating leadership takes time (think up to seconds or tens of seconds) during which your system is unavailable or partially available in some special mode. Leaderless can perform better under some other conditions as well (e.g. the leader becomes slow due to software problems or network problems: with leaderless approach other nodes might take over its duties). Consensus becomes harder as the number of participants increases, so leaderless can potentially scale better.

最后，让我们逐字逐句浏览一下您的问题：

Finally, let's gallop through your questions literally:

在什么样的系统上我将使用矢量时钟？

With what kind of system would I use something like a vector clock?

您可能希望将版本向量用于无领导者分布式存储。您可以将矢量时钟用于同一时钟（尽管它是更不合适；该文章还建议您将其用于一致的快照，以实现因果顺序在一般的分布式系统中）。

You might want to use a version vector for a leaderless distributed storage. You might use vector clocks for the same (although it's a worse fit; the article also suggests you use it for consistent snapshots, for implementing causal ordering in general distributed systems etc).

哪种系统最适合使用Paxos之类的东西？

Which system is ideal for using something like Paxos?

单领导者或多领导者的分布式存储。很少更新数据（认为配置），集群参与信息的数据库-如果此信息很关键，则八卦的扩展性更好。分布式锁。

A single-leader or multi-leader distributed storage. A database of rarely updated data (think configs), cluster participation info -- if this information is critical, otherwise gossip scales better. Distributed locks.

这两个互斥吗？

Are the two mutually exclusive?

否。两者都可用于解决相同的任务（例如，分布式存储）。可以将它们组合在一起（参加集群的paxos，然后使用该知识来确定哪些节点构成最终一致的（通过版本向量）系统中的仲裁）。

No. Both can be used for solving the same tasks (e.g. distributed storage). They can be combined (paxos for cluster participation and then use that knowledge to determine which nodes form a quorum in an eventually consistent (through version vectors) system).

这篇关于什么时候使用Paxos这样的共识算法而不是Vector Clock？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！