CAP
C（一致性）：所有节点的请求结果都是一致的
A（可用性）：所有请求都会成功，不存在服务响应超时或报错等
P（分区容错性）：网络分区后依然可以正常使用
Raft = CP
算法分析
- 既然是一致性算法就必然会有多节点，多节点同时存储某些数据会有一致或不一致，客户端的常常需求是得到一个强一致的结果，而不是最终一致
- 多节点如果同时对外提供服务，有通信成本前提下，无法实现更新完全同步，所以单节点对外会更容易实现强一致
- 一般都会使用主从模型“一主多从”，所有请求都通过leader发送给follower，follower只负责接收leader消息然后更新
- Raft最先讨论怎么才算写入成功，谁可以成为leader
基于Quorum机制的写入（过半写入）
- leader理论上和follower数据是一致的，leader收到消息后通知所有follower都写完再回复，这样会很浪费时间，而且某些节点宕机、网络延迟也会导致请求失败，Quorum就是写入过半就算成功。
- 过半写入后各个节点数据会不一致，虽然leader是最新的，读取也是读leader，但考虑到leader会宕机，这时就不满足是CAP里面的A了，要选出拥有最新数据的follower当leader，这时就要判断谁才是最新，如果没有类似版本号的概念直接覆盖就分不出数据新旧了，所以加入日志状态机模型。
日志状态机模型（日志索引）：
- 通过有索引的日志实现数据的有序化，初始化索引从1开始，每次修改+1，所以保证每个节点都按顺序、逐一写入。
基于日志比较的选举
- leader选举有两种情况
- 最开始所有节点都是follower索引都是1，谁是leader都可以
- 中途leader宕机，就应该选择索引最新的节点成为leader，通过日志状态机很容易比较出来。
- 选举的规则：
- 要过半数的节点支持才能成为leader，否则可能选出多个leader即产生脑裂
- 一节点一票：一个节点投出一票即可，follower当轮投票后不再投票。
- 过半写入：过半写入在选举过程中也体现了价值，过半follower拥有最新数据，选举需要过半票数，所以参加选举的follower中一定包括有最新数据的节点，这个节点就是新leader
- 为什么推荐单数节点：写入和选举都是过半成功，以最低的3节点为例，其中一个节点宕机后剩余节点还可以正常运行，2节点当任意宕机一节点即不可用，考虑过半机制4节点容灾效果和3节点一样，以此类推3节点允许宕机1台，5节点允许宕机2台，才是经济实惠的最佳选择
Raft算法中的选举
- 除了leader、follower还有一种角色candidate（候选人），各节点任意时刻都是这三种中的一种
- 消息一共两种，leader和follower通过心跳消息的方式保持联系：
- RequestVote：请求投票，由candidate角色发出
- AppendEntries：日志复制或心跳（索引不增的情况下是心跳），由leader发出
- ※term全局时钟（任期）：
- 这块可以按真实选举理解，换届就会+1，选举开始时会增加term，发送RequestVote消息时会带上新term（其实所有消息都会带），各节点接到任意消息和自己本地term比较，如果收到了更大的term说明因为leader宕机、分区恢复等原因换届了，这时自身无论是leader和candidate都会退化成follower，所以term的变动对于raft是一个大事
- term作为leader的任期号，follower一个选举term内只能投一次，必要时要做持久化避免宕机后重复投票。
- term和日志index都是最新的情况下，日志此时最新
- ※角色迁移过程：
- 系统开始时都是follower，这时还没有leader被选出来
- follower自身会有一个机制，一段时间没有收到心跳消息触发心跳超时，自身会转变成candidate并向其他follower发出投票请求
- 收到过半回复（candidate会默认投自己）后变成leader，如果一直未收到过半消息到超时后发起下次选举，如果其他candidate已经收到过半消息变成新leader，发出的心跳会让这个没选上的candidate退化成follower
- leader出现后会发出心跳，follower收到后重置心跳超时，所以一般情况下follower不会触发超时（所以心跳间隔设计上要比心跳超时短），也就不会再出现candidate
- 如果心跳超时是固定的，可能同时会出现多个candidate，大概率都会获得了未过半的票数就会进入下轮选举，所以心跳超时加一个小随机数可以有效避免这种情况例如超时3s~4s，心跳取间隔1s即可
角色状态变化
Raft算法中的日志复制
- 操作数据和term即都是日志，在消息中一起发出
- 日志需要先追加再持久化，有两种状态
- 追加但未持久化：没接收到确认请求前都不做持久化操作
- 已持久化：被认为是有效日志，推进commitIndex
- 已持久化索引commitIndex这些日志被认为是有效日志，刚启动时为0
- leader会记录各个节点nextIndex下个需要复制的索引和matchIndex已匹配日志的索引
- nextIndex：最大log+1
- matchIndex：follower响应时会带自身的已提交index
- ※复制流程：
- leader接收客户端请求，追加日志，通知follower
- 过半follower响应成功后leader日志持久化，推进commitIndex并通知follower持久化
- 通知follower持久化、leader响应客户端，这两步同时进行没有顺序要求
持久化
- 一些异常场景：
- follower追加后leader宕机未收到持久化请求，这时超时follower未持久化数据就会清掉
- leader未收到过半消息超时就回复失败，清理未持久化数据
- follower因为各种网络原因日志会参差不齐，leader当选后会强制同步
- 细节其实还很多要考虑各种网络异常场景、分区、恢复后的日志补偿，进而有各种补救措施和相关变量，了解设计思路和容灾策略对以后写代码有帮助暂时就可以了。
