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

我正在计划使用一个分布式数据库系统无共享架构 http://en.wikipedia.org/wiki/Shared_nothing_architecture and 多版本并发控制 http://en.wikipedia.org/wiki/Multiversion_concurrency_control。冗余将通过以下方式实现异步复制 http://www.webopedia.com/TERM/A/asynchronous_replication.html（如果发生故障，只要系统中的数据保持一致，就允许丢失一些最近的更改）。对于每个数据库条目，一个节点具有主副本（仅该节点对其具有写访问权限），此外，出于可扩展性和冗余目的，一个或多个节点还具有该条目的辅助副本（辅助副本是只读的） 。当条目的主副本更新时，它会被加上时间戳并异步发送到具有辅助副本的节点，以便最终它们将获得该条目的最新版本。拥有主副本的节点可以随时更改 - 如果另一个节点需要写入该条目，它将请求主副本的当前所有者将该条目的主副本的所有权授予该节点，并在收到所有权后该节点可以写入条目（所有事务和写入都是本地的）。

最近我一直在思考当集群中的节点出现故障时该怎么办，即使用什么策略进行故障转移。这里有一些问题。我希望您知道至少其中一些的可用替代方案。

• 有哪些算法可用于在分布式系统中进行故障转移？
• 分布式系统中有哪些共识算法？
• 集群中的节点应该如何判断某个节点宕机了？
• 节点应如何确定哪些数据库条目在发生故障时在故障节点上拥有其主副本，以便其他节点可以恢复这些条目？
• 如何确定哪个节点拥有某个条目的最新辅助副本？
• 如何决定哪个节点的辅助副本应提升为新的主副本？
• 如果本来应该宕机的节点突然又恢复正常了怎么办？
• 如何避免脑裂场景，即网络暂时分裂成两半，双方都认为对方已经死亡？

* 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?

依靠。心跳实际上是一个很好的方法。问题是存在误报，但这是不可避免的，并且在同一 LAN 上具有可管理负载的集群中，它们是准确的。 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 FileSystem 论文中真正受益。在 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 http://the-paper-trail.org处理很多这样的事情。

cheers,

Henry