1. 起源
我们计算机网络这门课，有两个星期是外教给我们上的课，他主要讲的是分布式系统中信息一致性的问题。教授讲课挺好的，就是有一些听不懂，23333。然后那段时间我有些颓废，所以就去听了两次课，现在想想还是很可惜。
教授上完课后，给我们布置了一些可选的编程作业。我选择的是：Implement crash-tolerant consensus。
在选择这个作业后，我上网查了查相关资料，很快就发现了 Raft 这个解决分布式中一致性问题的算法。因为我自己对 Unity 熟悉，所以就用 Unity 把这个算法实现了一遍，做成了一个小 Demo，总共花了大概25个小时，就算是完成这个作业了。
2. 链接
首先介绍一下学习 Raft 的相关资料：（我自己就是照着那篇论文实现的）
- Raft 算法的官网：https://raft.github.io/
- 详细讲解 Raft 算法的文章：https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
再放上我自己实现 Raft 算法的源码和简单演示视频：
3. 我自己的理解
Raft 算法是用来解决这样一个问题的：分布式系统中，有时候主机会崩掉，有时候网络会有延时、会掉包，但是仍然希望来自高层的指令能够在各个主机里依照相同的次序执行。
Raft 算法和其他解决这一问题的算法比起来，其优势在于高可理解性。依照我看的论文所说，在 Raft 算法之前，业内解决这个问题通常用的是 Paxos 算法。但是 Paxos 算法非常非常的复杂，论文的作者，斯坦福大学的学者，花了近一年的努力来理解和实现这个算法，最后仍以失败告终。而 Raft 算法，对于我这个对此领域没有任何前置经验的大三学生来说，在经过七、八个小时的阅读后，也能理解不少了。
Raft 算法中的主要流程是这样的。
- 在一开始，所有的主机都是普通身份的“追随者”。如果“追随者”在一定时间内没有接收到“候选者”或“领导者”发送来的消息后，它会自动升级为“候选者”。
- “候选者”会周期性的向其他所有主机发出请求，接收到请求的主机会依照自身情况和候选者情况进行投票。如果“候选者”获得了大部分主机的投票，它会升级为“领导者”。如果“候选者”接收到了满足一定条件的“领导者”的消息时，它会降级成为“追随者”。
- “领导者”负责接收来自上层的所有指令。当此时没有上层的指令要执行时，“领导者”会周期性的发送消息给其他主机来维护自己“领导者”的地位。当有上层的指令要执行时，它会将这个指令发给其他主机。当大部分主机执行了这个指令的之后，它告诉上层这个指令已被执行。
“追随者”、“候选者”、“领导者”相当于一台主机的三个状态，可以采用状态机的方式来实现这个算法。可以每次单独考虑一个状态的所有操作。这样就使得实现这个算法变得简单起来。我自己就是这么做的：分别编写各个状态的初始化（Initialize）、更新方法（UpdateState）、状态转换（Transition），就实现了这个算法。
而算法的细节，根据论文所说，可以将其看为独立的三个过程：
- 选举阶段：“候选者”申请选举以成为“领导者”。通过一系列方法和限制，保证了同一轮选举中，哪怕有多个“候选者”，最终也只会产生至多一个的“领导者”。
- 广播命令阶段：“领导者”向其他各个主机广播来自上层的命令。通过一系列方法和限制，保证了：1. 只有大多数主机都收到并执行了这个命令，才会告诉上层该命令已被执行。 2. 任意两台主机的相同编号的命令，其内容一定是一样的。
- 容错性：当任意一台主机崩掉，再重启时，经过一些方法和限制后，其命令队列仍能跟上“领导者”的命令队列。
其具体实现我就不在这里说了，感兴趣的可以看看我上面列出的论文。