前言

最近打算深入学习一下分布式相关设计，尝试自己实现一套分布式的服务。不过我并没有选择分布式届悠久有名的Paxos协议，而是选择更容易理解的Raft协议，由于在开始之前阅读各方面的资料都有推荐过Raft，其中关注了一款国人开发的分布式时序数据库TiDB 也有参考和优化融入了Raft 的设计。在初步阅读过Raft的论文后，更加坚定地这个选择。

那么本系列主题就是作为学习过程一些个人理解的记录。

状态自动机

在谈分布式的时候首先需要了解状态自动机 ，分布式的每一个节点，就是一个状态自动机的模型。

有限状态自动机(finite state machine) 顾名思义，某事物存在有限集合的状态集，满足某条件执行某动作切换到另外一个状态

有限状态自动机是具有离散输入和输出的系统的一种数学模型，其主要特点有以下几个方面：

系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。
我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。
系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。
系统中有一个状态，它是系统的开始状态。
系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子

更简单点，脱离IT、系统、信息化这些概念，有句话说过万物皆可状态机，我们思考过程的向导方式其实就是状态机的一种

状态机拥有四要素：现态、条件、动作、次态

我们把需要吃饭的人看作一个状态机

确定有限状态自动机可以直白地解释成

一个肚子饿（现态）的人，因为需要补充体力（条件），所以就去吃饭（动作），然后他就饱了（次态）

hungry=>start: 状态：饿
cond=>condition: 需要补充体力
eat=>operation: 吃饭
full=>end: 状态：饱
hungry->cond
cond(yes)->eat->full

非确定有限状态自动机可以直白地解释成

一个肚子饿（现态）的人

如果需要补充体力（条件），所以就去吃饭（动作），然后他就饱了（次态）;

如果需要补充精神（条件），所以就去睡觉（动作），然后他就寐了（次态）;

graph LR
B(饿了)
    B --> C{选择}
    C -->|补充体力| D[去吃饭] -->E(饱了)
    C -->|补充精神| F[去睡觉] -->G(寐了)

不深入而浅出

在Raft协议设计分为3个阶段

领导选举 Leader Election
日志复制 Log Replication
安全性 Safety

领导选举

Raft协议的每个node节点一定是处于这三种有限状态的其中一种，分别是跟随者follower、候选者candidate、领导者leader 。

客户端只会通过leader与集群之间的通信，follower失去了leader 之后，会重新选举leader。

leader是通过过半的node同意而选举出来的，Raft协议中设计了两种超时机制来保证选举顺利进行

选举超时机制

选举超时（election timeout）,是指 follower 等待成为 candidate 的时间, 一般是150ms ～300ms 随机，每个节点都在等待，直到最早完成等待的follower就成为candidate，同时开始新一轮的任期（通常是election term 值往上+1）

最新的任期值在集群中是最具权威的

candidate会首先投票给自己，然后向其他节点发送选票请求，收到请求的节点如果在本轮任期中还没有投票，则会把票（votes）投给该请求的候选者，然后重置election timeout, 候选者得到足够多的选票就成为leader

心跳超时机制

成为leader之后，开始发送append entries message附加条目的消息给follower, 这就是heartbeat timeout 心跳超时机制。
follower 回复附加条目消息, 这轮选举任期就会保持下去，直到有follower停止接收心跳且成为candidate

在偶数节点情况下，加入有两个candidate 在同一任期开始拉票，同时得到2票，这种情况下会触发重新选举 re-election

日志复制

一旦在系统有存在leader, 那么我们就需要复制所有的操作记录到其他节点上
这是通过使用与心跳相同的附加条目消息append entries message来完成的

客户端发送一个修改到leader
这个修改操作记录到leader的日志中
leader会把这个修改记录附加到下一次心跳中向其他节点发送
leader会等待大部分的follower写入完成
收到有过半的follower应答的消息则把这个修改标记为commited
返回结果给客户端
leader通知其他node已经提交了
集群这时候达成一致的共识状态

raft可以在面对网络分区时保持一致性

安全性

Raft为了保证群集中的选举正确性，包括需要应对实际业务中节点离线、网络割离、集群脑裂等一些情况，领导选举和日志复制的过程中增加若干的约束检查，例如任期比较、日志长度记录比较、日志提交记录比较，同时避免日志无限制增长，需要有收缩日志的安全要求。

安全性是实现Raft比较重要的细节设计，具体怎么，不同的应用可能都有自己的思考的想法

Raft共识算法的浅出