现在主流的分布式集群一致性问题大多都吸收了PAXOS算法¹的思想。然而，如果完全按照Leslie Lamport的论文²，实现复杂度比较高。因此，大多数实现都采用PAXOS的某种变形。Lamport的重要贡献，献是把分布式一致性的问题，形式化并给出了证明，给出了理论指导。³

关于Paxos算法，在网上看到了一个Fast Paxos算法，见淘宝核心系统团队博客, paxos 实现

Paxos算法看起来还是很复杂的，没有仔细研究，倒是在网上另外找到了两个简单的master选举算法。

霸道算法

Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法（Bully Algorithm）⁴。当一个进程 P 发现协调者进程不再响应时，这个进程就召集选举。由于进程的独立性，在同一个时刻，系统中可能有多个召集选举的过程。假设 P 是召集选举的进程，每个召集选举的过程如下：

1. P 向所有比自己编号大的进程发送一条 ELECTION（选举）消息。
2. 如果 P 得不到任何回复，则 P 赢得选举，P 向所有进程发送 COORDINATOR（协调者）消息，宣布自己的胜利。
3. 如果 P 得到任何一个回复，回复一定来自于比自己编号大的进程。P 的召集选举的工作结束，因为 P 此时已经不可能赢得选举。

其他进程或正在召集选举，或可能接收到比自己编号小的进程的 ELECTION 消息。当它收到一个 ELECTION 后，它回复一个 OK 消息给发送消息的进程；如果这时它还不是召集选举的进程，它也将开始一个召集选举的过程，即执行 1 到 3 的操作。 拥有最大编号的进程不召集选举，它直接发送 COORDINATOR 消息宣布胜利，霸道算法的名字由此得来。

环选举算法

关于选举的另一个著名算法是基于进程环的机制设计的。与一般的环算法不同的是，环选举算法并不使用令牌。在这个算法中，我们假设所有进程能够在物理上或逻辑上组成一个环结构，每个进程都保留一个按进程编号逻辑排序的一个表，因此知道自己的所有后继进程。⁵

算法的过程非常简单。当一个进程 P 注意到协调者进程不再工作时，它将启动一个召集选举的过程：

1. 进程 P 构造一个包含自己进程编号的 ELECTION 给后继进程，如果直接后继进程没有响应，进程 P 就将消息发送给环上的下一个进程，直到找到一个正常运行的进程。
2. 接收到 ELECTION 消息的进程将自己的编号增加到 ELECTION 消息中，然后按照同样的方式将消息发送给后继进程。这样，消息在环上的传递将构造一个包含所有正常运行的进程的编号表。
3. 当 ELECTION 消息最后回到召集选举的进程时，消息中最大编号的进程即成为选举的胜利者。召集选举的进程将消息类型改为 COORDINATOR，然后将消息沿着环重新发送一次，将选举结果通知所有的进程。
4. 当 COORDINATOR 消息重新回到召集选举的进程时，算法终止。

同样，在环选举算法中，也可能同时存在多个召集选举的过程。当在这个时刻环结构不变时，最后的结果也是一致的，只是消息数量多一些，并无大碍。

选举算法的讨论

霸道选举算法和环选举算法都依赖一系列苛刻的假设：

1. 假设了可靠的通道通信，更进一步的假设是系统中任何两个进程之间都可以通信。
2. 每个进程都知道其他进程的编号，也就是说算法依赖一个全局的数据。
3. 在多个并发召集选举的过程中，进程组的正常进程数量保持稳定，而且在环选举算法中，环结构也必须稳定。
4. 假设进程能够明确地判断出一个正常运行的进程和一个已经崩溃的进程。

有很多放宽假设条件下如何改进算法的讨论，但就算法的应用来说，召集选举的过程不应该是很频繁的，参与选举的进程数量和结构应该是相对稳定的。我们看不到频繁故障下的频繁选举的应用价值。因此，虽然算法的适用条件比较苛刻，但它们基本能够满足应用的需求。[^5]

一种多进程霸道算法实现

常常有这样的场景，在同一台主机上运行着多个进程，这些进程需要选举一个master进行管理工作，但是总体场景比较简单，环境也不是很复杂，这种情况下可以使用文件锁并结合霸道算法来实现master进程的选举。

文件锁可以用于进程间的同步，它支持读锁和写锁。具体算法如下：

假设：

• 有固定的一个路径下的文件file，用于选举和保存每个进程的通信端口。
• 进程编号单调递增的。
• 进程通过TCP方式通信，当然也可以采用其它方式通信，例如共享内存的方式。

进程启动时：

1. 对于一个进程启动后，检查固定的文件file，如果没有该文件不存在，创建该文件file，加写锁，执行第2步；如果存在，执行第3步，
2. 并声明自己为master，为自己分配编号1，将自己的端口、编号和master身份写入文件中。如果还有其它进程存在，为其它进程分配编号，向其它进程声明自己为master，并将其它进程的端口和编号写入file。算法结束。
3. 对文件file加写锁，如果加锁成功，读取文件中的port信息，然后向文件中的所有进程询问是否有进程存活，如果有进程响应，表明这些进程正在选举，等待新的master产生，有了新master后，该进程向master注册，进程结束；如果没有进程响应，则清空文件，执行第2步。如果加锁不成功，向master注册，算法结束。

向master注册时：

1. 进程A向master提交自己的端口号，master为进程A分配一个编号，master将进程A的端口号和编号写入file中，并进程A的端口通知给其它进程。

系统中，每个进程都维持着一张当前所有进程的表，每个进程都定期向所有的进程发送心跳数据。

当master无相应时：

1. 感知到master无响应时，发起master选举，直到产生新的master进程。
2. 新的master先创建一个file副本，然后加写锁，用副本替换file，然后所有进程的编号和端口写入到file文件中，并通知所有的进程自己为master，当然这时也可以重置所有的进程编号。

以上是我设想的一个算法，现在仅仅是一个思路，没有经过验证，慎用。 关于文件锁，我也写了一个简单的文件锁测试程序。