Raft

译文 原文 有用的飞书文档 和其他的算法相比 Strong leader 日志只能从领导者发送到其他节点 Leader election 随机计时器选举领导，在心跳机制上加上一些额外的工作 Membership changes 角色变换 Replicated state machines # 复制状态机一般基于日志实现，通俗的理解只要所有的机器按照相同的顺序执行指令，那么每个节点的状态都是确定的，所以需要把指令日志复制到其他节点上去，这就是一致性算法的工作 如果只是要求最终所有的节点都执行一样顺序的指令，而不要求实时性，则可以限定 只有一个节点可以进行写操作，因为只有写操作才可以改变系统的状态 写节点同步指令到其他节点，最终所有节点指令顺序一致 一致性算法的共有特性 安全性 不会返回一个错误结果，只要是在非拜占庭错误情况下，包括网络延迟，乱序，丢包，分区，冗余等都可以保障正确性 可用性 集群只要大多数机器可以正常通信，就可以确保可用，失败节点可以忽略或者后续恢复状态，大多数指的是半数以上 不依赖时序保证一致性 时钟错误或者消息延迟只有在极端情况下才会导致可用性 慢节点不会影响消息的反馈，消息可以快速的响应 拜占庭将军问题 Paxos # 难以理解 没有公认的可以实现的基础架构，大部分系统从Paxos开始，在遇到问题的时候自行想办法解决，导致最后的系统实现只能是类似Paxos的算法 Raft # 管理复制状态机的一种算法，他会在集群中选举一个leader，之后会复制所有的日志到其他节点实现一致性 他可以分解为三个问题 领导选举 一个新的领导人需要被选举出来，当先存的领导人宕机的时候 日志复制 领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同 安全性 在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令 可以在这个网站查看实例 节点有三种状态 Follower Candidate Leader 他们之间的转换关系如下图 任期在 Raft 算法中充当逻辑时钟的作用，这会允许服务器节点查明一些过期的信息比如陈旧的领导者。每一个节点存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号；如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。 下面是详细的细节参数 下面的参数要求在节点上持久存在 currentTerm 服务器最后一次知道的任期号，初始化为 0，持续递增 votedFor 当前获得选票的候选人的Id log[] 日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号 下面的参数在节点上是随时变化的 commitIndex 已知的最大的已经被提交的日志条目的索引值 lastApplied 最后被应用到状态机的日志条目索引值，初始化为 0，持续递增 下面的参数需要在leader重新选举之后变化的 nextIndex[] 对于每一个服务器，需要发送给他的下一个日志条目的索引值，初始化为领导人最后索引值加一 matchIndex[] 对于每一个服务器，已经复制给他的日志的最高索引值 这篇图表示的是rpc的参数信息以及返回值，由领导人负责调用来复制日志指令；也会用作heartbeat 参数 term 领导人的任期号 leaderId 领导人的 Id，以便于跟随者重定向请求 prevLogIndex 新的日志条目紧随之前的索引值 prevLogTerm prevLogIndex 条目的任期号 entries[] 准备存储的日志条目，表示心跳时为空；一次性发送多个是为了提高效率 leaderCommit 领导人已经提交的日志的索引值 返回值 term 当前的任期号，用于领导人去更新自己 success 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真 如果 term < currentTerm 就返回 false 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false 如果已经已经存在的日志条目和新的产生冲突（相同偏移量但是任期号不同），删除这一条和之后所有的 附加任何在已有的日志中不存在的条目 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个 由候选人负责调用用来征集选票