algorithm - 用于故障转移的分布式单例服务

Question

我有一个抽象的问题。

我需要一个具有容错能力的服务。该服务一次只能在一个节点上运行。这是关键。

有两个相连的节点:A 和 B。

• 如果 A 正在运行服务，则 B 必须等待。
• 如果 A 关闭，B 应该检测到并启动服务。
• 如果 A 再次打开，A 应该等待并且不要运行该服务。
• 等(如果B关闭，A启动，如果A关闭B启动)

我考虑过用于同步节点状态和检测超时的心跳协议(protocol)，但是存在很多竞争条件。

我可以添加带有全局锁的第三个节点，但我不确定该怎么做。

有人知道执行此操作的任何知名算法吗？或者更好 是否有任何开源软件可以让我控制这类事情？

谢谢

Answer 1

如果您可以在节点之间提供某种共享内存，那么就有解决此问题的经典算法，称为 Peterson's algorithm .

它基于两个额外的变量，称为 flag 和 turn。 Turn 是一个整型变量，其值表示当前允许激活的节点索引。换句话说，turn=1表示1号节点有权激活，其他节点应该等待。换句话说，轮到他主动了——这就是名字的由来。

Flag 是一个 bool 数组，其中 flag[i] 表示第 i 个节点声明自己已准备好提供服务。在您的设置中，flag[i]=false 表示第 i 个节点已关闭。该算法的关键部分是准备好服务的节点(即 flag[i] = true)必须等待，直到他获得 turn。

算法最初是为解决执行问题而开发的 critical section没有冲突。但是，在您的情况下，关键部分只是在运行该服务。您只需确保在第 i 个节点关闭之前，它将 flag[i] 设置为 false。这绝对是一个棘手的部分，因为如果一个节点崩溃了，它显然不能设置任何值。我会带着某种心跳去这里。

关于解决类似问题的开源软件，尝试搜索“集群故障转移”。了解 Google's Paxos和 Google FileSystem .有很多解决方案，但如果您想自己实现一些东西，我会尝试 Peterson 的算法。