wxya（个人网站）Raft算法
资料
翻译: Raft论文翻译
实现
对于强一致性共识算法，当前工业生产中，最多使用的就是 Raft 协议，Raft 协议更容易让人理解，并且有很多成熟的工业算法实现，比如蚂蚁金服的 JRaft、Zookeeper 的 ZAB、Consul 的 Raft、百度的 braft、Apache Ratis
paxos以复杂和难以理解著称，通常来说raft是更容易理解的算法，也更容易在工程实践中采用。
- braft:百度基于C++实现
- Aeron Cluster:基于java实现
- etcd/raft:基于Go语言实现
状态
Raft协议一共包含如下3类角色：
- Leader（领袖）：领袖由群众投票选举得出，每次选举，只能选出一名领袖；
- Candidate（候选人）：当没有领袖时，某些群众可以成为候选人，然后去竞争领袖的位置；
- Follower（群众）：这个很好理解，就不解释了。
然后在进行选举过程中，还有几个重要的概念：
- Leader Election（领导人选举）：简称选举，就是从候选人中选出领袖；
- Term（任期）：它其实是个单独递增的连续数字，每一次任期就会重新发起一次领导人选举；
- Election Timeout（选举超时）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。
流程
选主流程 (Leader Election)
- 初始化状态:
- 所有节点启动时默认处于 Follower 状态。
- 超时检测:
- Follower 节点在随机时间间隔内没有接收到 Leader 或 Candidate 的心跳消息，则认为当前 Leader 失效，Follower 转变为 Candidate 状态并发起选举。
- 发起选举:
- Candidate 节点会将自身的任期号增加，并向集群中的其他节点发送 RequestVote 请求。
- 投票:
- 其他节点（通常是 Follower 和其他 Candidate）根据投票规则决定是否投票给该 Candidate。
- 如果投票给 Candidate，则会发送 VoteGranted 消息。
- 如果已经有投票给其他 Candidate 或者认为该 Candidate 的任期号不够新，则不会投票。
- 成为 Leader:
- 当一个 Candidate 收集到集群中超过半数节点的投票时，它就会成为新的 Leader。
日志复制流程 (Log Replication)
- 发送心跳:
- 成功当选的 Leader 会定期向所有的 Follower 发送心跳消息（AppendEntries RPC）以维持其领导地位。
- 追加条目:
- 当 Leader 收到来自客户端的新条目时，它会将这些条目追加到自己的日志中，并通过 AppendEntries 请求将其同步到所有 Follower。
- 日志匹配:
- Follower 需要确保其日志与 Leader 的日志保持一致。如果 AppendEntries 请求中的条目与 Follower 的日志不匹配，则 Follower 会拒绝该请求，并返回冲突点的信息。
- 日志截断:
- Leader 接收到冲突信息后，会调整 Follower 的日志使其与自己的日志相匹配，这通常涉及到删除 Follower 日志中不一致的部分。
- 日志应用:
- 当一个条目被复制到了大多数节点上，它就被认为是已提交的。Leader 会在本地应用这些已提交的日志条目，并通知 Follower 应用相应的条目。
安全性保障
- Raft 确保在同一时刻只能有一个 Leader。
- 通过维护日志的一致性，确保所有节点最终达成一致的状态。
Loading...