在分布式系统中有哪些故障转移算法？

Question

在分布式系统中有哪些故障转移算法？

databasealgorithmdistributedcluster-computingfailover

19

我计划使用共享无什么架构和多版本并发控制创建分布式数据库系统。通过异步复制实现冗余（在故障情况下允许丢失一些最近的更改，只要系统中的数据保持一致）。对于每个数据库条目，一个节点拥有主副本（只有该节点可以写入它），此外还有一个或多个节点拥有条目的次要副本，以实现可扩展性和冗余（次要副本只读）。当一个条目的主副本更新时，它会被时间戳标记并异步发送到具有次要副本的节点，以便它们最终获得条目的最新版本。拥有主副本的节点随时可以更改-如果另一个节点需要写入该条目，则会请求拥有主副本的当前所有者将该条目的主副本所有权转移给该节点，并在接收所有权后该节点可以写入该条目（所有事务和写入都是本地的）。

最近我一直在思考当集群中的节点关闭时应该做什么，应该使用哪种故障转移策略。以下是一些问题。希望您能了解其中至少一些可用的替代方案。

分布式系统中有哪些故障转移算法？
分布式系统中有哪些共识算法？
集群中的节点应该如何确定某个节点已经宕机？
节点应该如何确定在宕机时，哪些数据库条目是其主副本，以便其他节点可以恢复这些条目？
如何决定哪个节点具有某个条目的最新辅助副本？
如何决定哪个节点的辅助副本应该晋升为新的主副本？
如果被认为宕机的节点突然回来了怎么处理？
如何避免出现网络暂时分裂成两个部分，双方都认为对方已经死亡的情况？

- Esko Luontola

1

@PhilCrow 有更有用的项目，所以我放弃了这个项目。 ;) - Esko Luontola

5个回答

10

你提出的问题非常庞大，而且你想了解的很多内容仍在积极研究中。

以下是一些想法：

分布式系统很难处理，因为没有绝对可靠的系统来处理故障。在异步系统中，无法确定节点是否已经宕机或者存在网络延迟。这听起来可能很琐碎，但其实并不是。
可以通过 Paxos 算法家族来达成共识，其版本被用于谷歌的 bigtable 和其他地方。

你需要深入研究分布式系统的教科书（或多本）。我喜欢 Tannenbaum 的《分布式系统原理与范例》。

- Rob

你提出了一个非常庞大的问题，而且你想知道的很多东西仍在积极研究中。这就是这个（业余）项目如此有趣的原因。它不是一个无聊的通用CRUD Web应用程序。挑战是有趣的。 :) - Esko Luontola

1

不，你完全正确。这是一个非常好的项目想法，我相信你会从中获得很多收获。一定要开始阅读一些教科书，并阅读Lamport关于Paxos的论文，非常易懂。 - Rob Lachlan

3

一个很棒的博客，讨论了很多分布式系统和分布式算法的内容，包括实现Paxos，链接为 http://the-paper-trail.org/。

- Kevin Weil

2

这个问题在VMS中已经被DEC解决，他们使用了分布式锁管理器。现代的解决方案基于这个设计。阅读维基百科文章可以了解当前的一些解决方案。你可以看看OCFS2，它现在已经成为Linux内核的一部分。

- Jared Oberhaus

0

仅回答您问题的一小部分：在您描述的情况下，没有办法（抽象地）确定哪个节点具有最新的辅助副本。最好的情况是，某些节点可以轮询并确定（经过一些通信后），他们所知道/可以看到的节点中，那些知道/可以看到他们，并且不能看到旧主节点的节点拥有最新的副本。但是：

他们无法找出无法到达的节点的状态
他们无法找出无法到达他们的节点的状态
当他们无法看到旧主节点时，他们无法确定自己对于能够看到旧主节点的节点状态的了解是否是最新的 - 主节点可能已经在邻居报告状态之后更新了共享邻居。

关于更广泛的问题，您可能需要查看类似memcached等处理问题的方式，特别是阅读列表，以了解当理论遇到实践时遇到的问题。

- MarkusQ

memcached 不处理这些问题，它假设客户端会处理。而且，它只是一个缓存系统，因此如果它失败了（或返回未找到），调用进程可以直接从源请求数据。 - MarkR

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HenryR · Accepted Answer

* What algorithms there are for doing failover in a distributed system?

可能不是算法，而是系统。您需要围绕所提出的问题设计架构。

* What algorithms there are for consensus in a distributed system?

你可能希望实现 Paxos。实现简单 Paxos 并不太难。如果你想要让它更加鲁棒，请阅读 Google 的“Paxos Made Live”论文。如果你希望让它高性能，请看 Multi-Paxos。

* How should the nodes in the cluster determine that a node is down?

这要看情况。心跳检测实际上是一种相当不错的方法。问题是你会出现假阳性，但这种情况有点不可避免，而且在同一局域网上、负载可控的集群中，它们是准确的。Paxos 算法的好处是可以自动处理假阳性。然而，如果你需要针对其他目的获取故障信息，则需要确保即使检测到一个节点失败，但它实际上只是负载较高，需要时间来响应心跳。

* How should the nodes determine that what database entries had their master copy on the failed node at the time of failure, so that other nodes may recover those entries?
* How to decide that which node(s) has the latest secondary copy of some entry?
* How to decide that which node's secondary copy should be promoted to be the new master copy?

我认为你可以从阅读Google File System的论文中获益匪浅。在GFS中，有一个专用的主节点来跟踪哪个节点有哪些块。这种方案可能适合你，但关键是要尽量减少对这个主节点的访问。

如果你不把这些信息存储在专用节点上，你就必须在任何地方都存储它。试着用主持人的id给数据打上标记。

* How to handle it, if the node which was though to be down, suddenly comes back as if nothing happened?

请参考上文，但基本点是要小心，因为不再是主节点的节点可能会误以为自己是主节点。有一件事情我认为你还没有解决: 如何使更新到达主节点——也就是说，客户端如何知道要将更新发送到哪个节点？

* How to avoid split-brain scenarios, where the network is temporarily split into two, and both sides think that the other side has died?

Paxos在这里通过防止发生完美拆分的情况来避免进展。否则，就像以前一样，您必须非常小心。

总的来说，解决知道哪个节点作为主节点获取哪个数据项的问题，您将迈出修复架构的重要一步。请注意，您不能仅让接收更新的节点成为主节点-如果两个更新同时发生会怎么样？也不要依赖同步全局时钟-那样会产生疯狂的结果。如果可能的话，您可能希望避免在每次写入时运行共识，因此可以采用慢的主故障转移协议和快速的写入路径。

如果您想了解更多细节，请随时给我发送邮件。我的博客http://the-paper-trail.org涉及很多这方面的内容。

谢谢，
Henry