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

Question

我打算使用无共享架构和多版本并发控制来创建分布式数据库系统.冗余将通过异步复制实现(只要系统中的数据保持一致,就可以在发生故障时丢失一些最近的更改).对于每个数据库条目,一个节点具有主副本(仅该节点具有对其的写访问权),此外,一个或多个节点具有该条目的辅助副本以用于可伸缩性和冗余目的(辅助副本是只读的) .更新条目的主副本时,它会加上时间戳并异步发送到具有辅助副本的节点,以便最终获得最新版本的条目.具有主副本的节点可以随时更改 - 如果另一个节点需要写入该条目,它将请求主副本的当前所有者为该节点提供该条目的主副本的所有权,

最近我一直在考虑当集群中的节点发生故障时该怎么做,以及用于故障转移的策略.这是一些问题.我希望你能知道至少其中一些的可用替代品.

• 在分布式系统中进行故障转移有哪些算法？
• 在分布式系统中有哪些算法可以达成共识？
• 群集中的节点应如何确定节点已关闭？
• 如何在发生故障时节点确定哪些数据库条目在故障节点上具有主副本,以便其他节点可以恢复这些条目？
• 如何确定哪个节点具有某些条目的最新辅助副本？
• 如何确定应将哪个节点的辅助副本提升为新的主副本？
• 怎么处理它,如果那个虽然要关闭的节点突然回来,好像什么也没发生？
• 如何避免裂脑情况,网络暂时分成两部分,双方都认为对方已经死亡？

Answer 1

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

要看.Heartbeats实际上是一个非常好的方法.问题是你有误报,但这是不可避免的,并且在同一局域网上具有可管理负载的集群中,它们是准确的.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中,有一个专用的主节点,用于跟踪哪些节点具有哪些块.这个方案可能对你有用,但关键是要保持对这个master的访问最小化.

如果您不将此信息存储在专用节点上,则必须将其存储在任何位置.尝试使用主持有者的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处理了很多这样的事情.

干杯,

亨利

Answer 2

你问的是一个绝对庞大的问题,而你想知道的很多东西仍在积极研究中.

一些想法:

• 分布式系统很难,因为没有万无一失的系统来处理故障; 在异步系统中,无法确定节点是否已关闭或是否存在网络延迟.这可能听起来微不足道,但实际上并非如此.
• 可以通过Paxos算法系列实现共识,这些算法的版本在Google的bigtable和其他地方使用.

您将需要深入研究分布式系统教科书(或几个).我喜欢Tannenbaum的分布式系统:原理和范例

Answer 3

仅解决您问题的一小部分：在您描述的场景中无法（抽象地）决定哪个节点拥有最新的辅助副本。最好的情况是，某个节点可以轮询并确定（经过一些通信后）他们知道/可以看到的节点中的哪些节点，以及知道/可以看到它们的节点，并且看不到旧主节点拥有最新的节点复制。但：

• 他们无法找出他们无法到达的节点的状态
• 他们无法找出无法到达他们的节点的状态
• 他们无法确定他们认为自己知道的关于可以看到旧主节点的节点的状态是否是当前节点的状态——主节点可能在邻居报告状态后更新了共享邻居。

在更广泛的问题上，您可能想看看像 memcached 之类的东西是如何处理问题的，特别是通读列表，看看当理论与实践结合时他们遇到了哪些问题。