Raft论文阅读小记 / RAFT paper reading notes 📝

https://raft.github.io/raft.pdf

建议读一下原Paper

背景

RAFT是一个分布式领域内的共识算法（Consensus Algorithm），目的是为了提供一个更加直观易懂（Understandability）、 更易于实现且不丧失相关的强一致性，可以理解就是PAXOS的通识版

因为此前PAXOS在这个领域占据主导地位，大量的教科书里都是用PAXOS来教学，初学者有较大的学习成本，并且工程实践方面也比较困难，表现在2点：

1. 理解的难度，再加上理论和实践的差距
2. PAXOS对于很多细节并没有阐述清晰，导致各方在实现的时候就会根据情况去变形，导致最终大家实现的都是有出入的

Conclusion里的这段我觉得能挺清晰的表达出RAFT对于易理解的追求：

Algorithms are often designed with correctness, efficiency, and/or conciseness as the primary goals. Although these are all worthy goals, we believe that understandability is just as important. None of the other goals can be achieved until developers render the algorithm into a practical implementation, which will inevitably deviate from and expand upon the published form. Unless developers have a deep understanding of the algorithm and can create intuitions about it, it will be difficult for them to retain its desirable properties in their implementation.

整体就是说，追求正确、效率和简洁明了通常是设计算法里的首要目的，但是RAFT的作者认为易于理解同样重要。除非深入的理解， 否则在实现或者在不同形式的传播中，很难一直保持其原有的设计思想或理念，也就是咱们前面说到的，实现中要根据情况、经验和认知去决定实现方式， 不可避免的结果就是会导致很多“版本”的流通

设计理念

RAFT借鉴了现实社会中的领导选举机制，还挺方便理解。从全局的角度看，整体遵循了这么几个点：

1. 只有三种角色：Leader（主，领导者）、Candidate（候选者）、Follower（跟随者）
2. 任期制：确保节点不可用时（尤其Leader）能快速感知和切换
3. 所有的操作只能在Leader上进行（需要注意，这种情况下性能层面会有一定问题，因此在某些应用场景还是需要结合一些其他缓存系统来保障高效的读写，这就是架构设计中需要注意的，没有银弹，一切都是取舍Tradeoff，当然要做tradeoff之前你是需要对涉及到的技术、系统的设计理念和应用场景有一定的认知，才能做出正确的判断）
4. 追加日志，日志从Leader复制到其他Follower
5. 安全性：日志复制需要经过一致性检查，大多数节点确认才可提交

其他的就是基于这些点下沉的一些细节，比如：

• 怎么选举
• 角色如何切换
• 怎么防止切换时日志被新主覆盖
• 节点故障的具体处理细节
• 如何保持心跳
• 如何处理在相同下标下的不同数据

选举

1. 刚启动，所有节点都是Follower（或者Leader没了，剩余的都是Follower）
2. 发现没有来自Leader的心跳同步包（Leader发送的心跳是跟着AppendEntriesRPC请求一起的，哪怕没有数据也可以发空payload代表这个请求只用于心跳用途），等待任期超时（每个节点的超时时间都是不同的，随机的，意图是这样能有效避免选票分散在多个同时发起选举的候选人身上）
3. 某些节点超时了，触发选举，将自己从Follower提升到Candidate，发送投票请求（RequestVote RPC）给所有节点（会携带上任期号term和最新的日志下标lastLogIndex, lastLogTerm）
4. 节点收到投票请求，会和本身的当前任期对比，如果自己所处的任期大于对方的，或者自己的日志比对方更多，拒绝投给对方，否则就投票给对方（同节点可能会收到多个投票请求，也是基于这个逻辑来确认投给谁）
5. 最终票数多的成为Leader（也有可能票数一样导致没有Leader产生，就会等下一任期到来再选举一波），开始定期发心跳维持自己的地位（某个节点在超时时间内收到Leader的心跳会重启超时等待，直到没收到就会回到Step 2.开启新的选举），此时其他节点全部退回Follower状态

日志复制

每个节点自身都维持了一个状态机（State）在内存，代表目前的数据情况，只有被确认提交的数据会进到这里，收到但还没确认的不会

日志追加的方式，通过AppendEntriesRPC请求同步给其他的节点，在大多数的节点确认后，会进行提交， 这样能有效确保Leader切换后数据不会丢失（拥有的日志越多的节点约有可能成为下一任Leader）

整体流程如下：

1. 收到写数据请求，操作附加到自己的日志中（此时还没提交生效）
2. 发送日志给其他节点（发AppendEntriesRPC请求），信息里面会包含一些诸如任期号、LeaderID，日志条目和下标等信息
3. Follower节点收到后，检查自己的日志条目情况，如果匹配就追加最新的，不匹配的话拒绝（Leader给的前面的Log的任期不同之类的情况）
4. Leader收到超过半数节点的成功响应后，确认已经传播到多数节点了，该日志条目被标记为提交（commited），应用条目到自己的状态机中（下一次AppendEntriesRPC就会告知Follower已经提交到这个位置，Follower也可以跟着提交到这个下标位置的Log）
5. Leader响应客户端

在此期间，Step 3.会有个分叉逻辑，就是Leader需要补发Follower缺失的Log， Log下标会往前推直到这个Follower最后的Log位置（此时会借助一些任期号来加快定位到需要补的日志的开头）

安全性

RAFT通过任期号、多数投票选举、日志的一些机制保障了安全性，以下列举几个点：

• 多数投票选举机制和任期号机制，防止出现脑裂（No Split-Brain）
• Leader包含所有已提交条目（Leader Completeness Property），统一负责读写，包括线性一致性读（Linearizable reads）
• 只有Follower的日志可以被覆盖，Leader的日志只能不断追加，不可再覆盖旧的
• 多数确认提交，确保多数确认的情况下才会提交

写在最后

整体过了一下RAFT的一些设计理念，从paper里的一些表述中能很明确的感受到作者的意图和想法，尽可能阅读最一手的资料是追求有效信息的好方法， 也可以避免信息传播过程中产生的变形（不过也有利弊，有些人会有更加翔实的分析和剖析，就像这篇文章一样也是二手信息）

值得一提的是，在paper里一句带过的Leader租约（Lease）机制，在实际应用中也是一个挺重要的点， 比如Consul和Etcd都实现这个机制，可以增加读的性能（风险取决于节点间的时钟差异程度和可接受的时钟漂移范围）