避免分裂，投票和法定人数 [英] Avoiding split-brain, votes and quorum

问题描述

假设你有n个进程，n> 2.你希望在他们之间达成协议，一个是活跃的。所以他们需要相互投票来确定哪一个是活动的。

所有进程都可能在任何时候失败，我们希望有一个进程可以活跃，但是。 ..

我们必须不要同时有两个活动，所以如果他们不能确定最好没有 - 一个活跃。 （即，我们想避免分裂大脑）

它们之间唯一可用的通信机制是pub-sub消息（不是点对点）。

一个或多个数据库可用，但没有一个数据库应该是单点故障。 IE浏览器。如果所有的过程都可以使用，那么这样做是非常不理想的，并且由于丢失了一个数据库而被阻止了这样做。

设计？需要发布哪些消息？

解决方案

理论：

这是领导选举， 共识问题的形式，有时也称为两个将军的问题。根据某些假设（完全异步和消息可能会丢失），已被证明是不可能的，证明是特别优雅的。

这个问题的直觉是：想象一下存在允许在某些固定数量的消息中达成共识的算法。由于可以容忍故障，我们可以从协议中删除一条消息，并且仍然可以工作。我们可以重复这个过程，直到没有消息，显然是不可能的。

在实践中，我们克服了这一点，使用故障检测器来模拟同步系统。

解决共识的最广为人知的算法是 Paxos ，它可以容忍多达一半参与节点的故障。 Paxos的声誉很难实施，因为对协议细节的轻微误解破坏了它的正确性。

实用解决方案：

虽然问题一般是相当困难的，但是将工作系统提升到更加容易。有可用的Paxos或等效算法的现成实现。 Apache Zookeeper 是我所知道的最好的。对于您的具体问题，我很确定这将是您最快的路线。其他Paxos实现也在附近，也可能在网络冗余虚拟IP工具上构建一些内容，如 Wackamole 。我相信大多数商业数据库的高端版本都提供了一个（昂贵）选项的仲裁功能。

此外，对于许多应用程序，可以轻易削弱正确性或以其他方式调整问题允许更简单的解决方案。

例如，如果单点故障是可以容忍的，因为恢复可能很快，那么问题是微不足道的：只需要一个特殊节点即可完成工作。 / p>

另一种方法可能是围绕幂等动作构建系统，因此重复处理变得容忍。

最后你可能将工作负载划分为非冗余系统池：这里的故障将延迟处理直到恢复，但只能在该节点上的项目，而不是整个工作负载。

这些排序妥协是简单得多的，因为它们往往是一个更好的选择。人们必须权衡一个完整的解决方案的实用性与执行它的复杂性，看看是否真的有价值。这就是为什么这么多实用系统只是使用 2阶段或 3阶段提交，尽管它们在某些情况下阻止：与完整法定系统的复杂性相比，可用性的降低可以容忍。

Suppose you have n processes, n > 2. You want to have agreement amongst them that one is to be active. So they need to vote amonst each other to determine which one is active.

All processes may fail at any time, we want to have one process active if possible, but ...

We must never have two active at the same time, so if they can't be sure it is better to have no-one active. (Ie. we want to avoid split brain)

The only available communication mechanism between them is pub-sub messaging (not point to point).

One or more databases are available, but no one database should be a single point of failure. Ie. it would be very undesirabloe if all the processes were available to work, and the were prevented from doing so by the loss of a single database.

Design? What messages need to be published?

解决方案

Theory:

This is leader election, which is a form of the Consensus Problem, also sometimes called The Two Generals Problem. Under some sets of assumptions (fully async and messages can be lost) it's been proven impossible, and the proof is particularly elegant.

The intuition of this problem is: imagine some algorithm exists that allows consensus to be reached in some fixed number of messages. Since failures are tolerated, we can drop one message from the protocol, and it should still work. We can repeat this process until there are no messages at all, clearly an impossibility.

In practice we overcome this using failure detectors to simulate a synchronous system.

The most widely known algorithm that solves consensus is Paxos, which can tolerate failure of up to half of the participating nodes. Paxos has the reputation of being very difficult to implement as even slight misunderstandings of the details of the protocol destroy it's correctness.

Practical solutions:

While the problem in general is quite difficult, getting working systems up is far easier. There are off the shelf implementations of Paxos or equivalent algorithms available. Apache Zookeeper is the best I'm aware of. For your specific problem, I'm pretty sure it'll be your quickest route. Other Paxos implementations are around, and it also might be possible to build something on network redundancy virtual ip tools like Wackamole. I believe the high end versions of most commercial databases offer quorum features as an (expensive) option.

Also, for many applications it's acceptable to weaken correctness slightly or otherwise adjust the problem to allow much simpler solutions.

For example, if a single point of failure is tolerable because recovery is likely to be quick, then the problem is trivial: just have one special node do the work.

Another approach might be to build the system around idempotent actions, so duplicate processing becomes tolerable.

Lastly you might partition the workload into a pool of non-redundant systems: here failures will delay processing until recovery but only for items at that node, not for the entire workload.

These sorts of compromises are so much simpler that they're often a better choice. One has to weigh the utility of a full solution against the complexity of implementing it and see if there's really value. This is why so many practical systems just use 2 Phase or 3 Phase Commit, even though they block in some scenarios: the decreased availability is tolerable compared to the complexity of a full quorum system.

这篇关于避免分裂，投票和法定人数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！