19

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

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

  • 在分布式系统中进行故障转移有哪些算法？
  • 分布式系统中有哪些共识算法？
  • 集群中的节点应该如何判断一个节点宕机了？
  • 节点应如何确定故障时哪些数据库条目在故障节点上有其主副本，以便其他节点可以恢复这些条目？
  • 如何确定哪些节点具有某个条目的最新辅助副本？
  • 如何决定应该将哪个节点的辅助副本提升为新的主副本？
  • 本来以为down的节点突然又像什么都没发生一样怎么处理？
  • 如何避免出现裂脑场景，网络暂时一分为二，双方都认为对方已经死了？
4

5 回答 5

31 
* 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 中有一个专用的主节点，它跟踪哪些节点有哪些块。这个方案可能对你有用，但关键是尽量减少对这个 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处理了很多这样的东西。

干杯，

亨利

于 2009-03-08T23:57:36.113 回答
10

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

一些想法：

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

您需要深入研究分布式系统教科书（或多本）。我喜欢Tannenbaum 的分布式系统：原理和范式

于 2009-03-06T23:48:57.790 回答
3

http://the-paper-trail.org/是一个很棒的博客，它讨论了很多关于分布式系统和分布式算法——包括实现Paxos——

于 2009-03-08T18:57:19.767 回答
2

使用分布式锁管理器的 DEC for VMS 解决了这个问题。现代解决方案基于这种设计。阅读 Wikipedia 文章以了解一些当前的解决方案。您应该查看OCFS2，它现在是 Linux 内核的一部分。

于 2009-03-06T23:50:23.747 回答
0

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

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

在更广泛的问题上，你可能想看看 memcached 之类的东西是如何处理这些问题的，尤其是通读列表，看看他们在理论遇到实践时遇到了哪些问题。

于 2009-03-06T23:37:31.703 回答