Replicated state machines

状态机是为了保证确定性，通常用复制日志来实现，

每个服务器都有一个记录着指令序列的日志，这些指令序列作为状态机的输入，不同机器上面的日志按照同样顺序记录着相同的日志

共识算法用来保证不同副本日志的一致性

The Raft consensus algorithm

Paxos算法主要的问题在于难以理解和实现，raft算法把共识问题分解为一下几个部分

  1. Leader election 如果已有leader挂了，需要选举新的leader
  2. Log replication leader需要接收客户端的请求，并且复制给其他副本，强制要求其他副本跟自己保持一致
  3. Safety 如果一个日志被加入到某个服务器的状态机指令序列中，其他任何服务器上对应位置的日志都应该是同样的

不变属性：

  1. Election Safety 一个任期里面最多只有一个leader
  2. Leader Append-Only leader只会append日志，不会覆盖或者删除
  3. Log Matching 如果两份日志中，有着日志编号和任期相同的一个记录，那这个记录以前的所有日志都相等
  4. Leader Completeness 如果一条日志记录在一个任期内被成功提交了，那么所有更高任期的主节点将包含这条的日志
  5. State Machine Safety 如果一个日志被提交到状态机，那么其他任何服务器状态机对应编号执行的日志应该相同

Raft basics

只有leader会处理客户端请求(如果一个follower节点收到了请求，会转发给leader节点)

每个leader都有一个任期，任期单调递增，每个节点都存储了当前的任期号

节点之间发生任何通信都会交换任期号，任期小的会被强制更新到大的

leader周期性发送心跳包给其他节点，当某个节点一定时间收不到leader的心跳的时候，就可以发起leader选举

节点间主要通过两种RPC通信：

  1. RequestVote RPCs 由候选节点在选举的时候发起
  2. AppendEntries RPCs 由主节点在复制日志和心跳的时候发起

Leader election

Raft使用心跳来触发选举

一个follower节点只要能够收到leader节点或者candidate节点的RPCs，就一直保持为follower身份

leader周期性发送心跳包(不带任何日志的AppendEntries PRCs)给所有的followers节点以维持统治

当一个follower长时间(election timeout)收不到心跳，就会发起选举：

  1. 增加自己的任期号，把自己变成candidate状态
  2. 给自己投票，给其他所有服务并行发送RequestVote RPCs

  3. 保持candidate状态直到以下事件发生：

    • 赢得选举(得到大部分节点的投票，先到先得) -> leader节点
    • 收到leader的AE RPC, 任期号不小于自己，接受 -> follower节点
    • 收到leader的AE RPC, 任期号小于自己，拒绝 -> 保持candidate状态
    • 选举超时(每个节点的超时时间都是随机的，避免每次都超时)，没人赢得选举 -> 重试

Log replication

同步流程：

  1. leader把指令加入到日志中
  2. 并行给各个服务器发送AppendEntries RPCs
  3. 确认安全后(commited，大部分节点完成复制)，把指令放到状态机中执行，并把执行结果返回给客户端
  4. 如果因为各种原因followers没有成功复制到日志，leader会无限期重试RPCs，直到所有节点成功写入日志

follower需要检查AE(AppendEntries)的合法性(AE包含了前一个日志的编号和任期)，是一个逐步的过程，初始状态位空，是一致的，每次收到新的AE，都要进行检查，不然就拒绝

leader会维护一个最大commited日志编号，并包含在AppendEntries RPCs(包括心跳)中，followers在收到这个编号之后，会把自己的日志提交到状态机

如果leader出现问题，新的leader上台，会出现日志冲突的情况，这时候需要处理冲突，raft要求follower强制跟leader保持一致(raft保证新上台的leader一定有前任所有的提交)

leader对每一个follower维护一个nextIndex，表示下一个应该给follower同步日志的编号，刚上台的leader的这个编号是自己最后一条日志的编号加一

follower处理AppendEntries消息的时候，会最一致性检查，不通过会返回失败，这时候leader需要把能nextIndex减1，直到AppendEntries成功

Safty

Election restriction

raft要求成为leader的资格是它拥有所有节点中committed任期最高的日志，所以一旦一个节点成为leader，不需要再从其他节点把日志同步给leader

因为一个日志被标记为committed状态的时候，需要得到大部分节点的认可，如果一个没有拥有最新committed的节点票选leader的时候，一定会被这大部分节点拒绝

RequestVote RPC会包含这个candidate的最新日志信息，收到这个票选请求的节点发现自己的log比candidate新，会拒绝这个票选

raft比较两份日志谁更新，首先比较最新日志的任期号，大的更新；如果任期号相同，越长越新

Committing entries from previous terms

leader不应该提交前任没来得及提交的日志，只允许提交现任的东西

由Log Matching属性保证，只要自己任期中成功提交过东西，前任的日志自动就会被提交掉

Safety argument

反正Leader Completeness

假设一个term T和一个最小的term U，满足U>T同时，leader_T的提交不存在leader_U中

由于leader不可删除或者更改日志，所以一开始(票选leader_U)的阶段就应该出现不一致

在票选过程中，一定有一个节点先接受了term T的AE，然后接受了term U的RV，如果反过来，AE是不会被接受的(term变大了)

那么，这个节点在收到RV的时候，leader_U的日志一定比这个节点新，所以分两种情况讨论：

  1. 如果leader_U的最新log和这个节点最新log处于相同term 由Log Matching保证日志一致，所以leader_U也一定包含term T已提交的部分，矛盾
  2. 如果leader_U的最新log的term跟新 那么生成leader_U最新日志的上一个leader，一定是包含term T已提交的部分的，不然违背了U是最小不包含T提交的term 这样leader_U一定也是包含term T已提交的部分，矛盾

Leader Completeness得到证明，然后可以简单推到出State Machine Safety Property也是满足的

State Machine Safety Property：如果一个服务器把某个日志应用到状态机，那么其他所有服务器在相同的位置也会应用相同的日志

  • 反证 如果某台服务器在某个别的服务器已应用日志的位置上应用了一个不同的日志，由Leader Completeness原理可知道，这个已提交的日志一定会出现在比它更新的服务器上同样的位置，然而那个位置并不是这条日志

Follower and candidate crashes

主节点无限重试就好了

Timing and availability

  • broadcastTime 节点并行发送RPCs给其他所有节点并得到回复的平均时间
  • electionTimeout 选举超时
  • MTBF 单个服务器两次故障之间的平均间隔时间

需要满足公式：

broadcastTime ≪ electionTimeout ≪ MTBF

RPC一般消耗0.5ms~20ms

所以electionTimeout很多时候被配置成10ms~500ms

而MTBF通常会很久，比如几个月之类的

Cluster membership changes

直接切换会有一个问题，进入新的配置的节点，和还在旧配置的节点互相注意不到对方，可能产生两个leader

为了解决这个问题，引入一个中间配置状态，旧的节点进入新的配置之前，必须经过中间配置状态

在中间配置状态，任何提交需要旧的配置和新的配置的机器一致通过

当进入中间配置的日志提交之后，节点要成为Leader，一定会有中间配置日志，所以一定能够注意到两边配置的机器

这时候引入三个问题：

  • 新机器加入的时候，可能没有啥数据 在切换配置之前，这些新机器需要追赶上主节点日志，避免切换阶段因为数据同步卡住不可用
  • 旧的机器在提交新配置日志的时候，可能不再属于新的配置的节点 旧leader提交了切换到新配置的日志之后(这之后新配置的集群可以独立工作了)，新配置的节点可能不再能注意到旧的leader，所以需要主动下台
  • 旧的机器在移除之前，因为收不到新配置leader的心跳，会发起leader选举，干扰新的机器正常工作 在服务器确信领导活着的时候，设置一个超时，超时时间内不接受leader选举