分布式一致性协议:raft协议

关于raft的起源和历史

名词一： 复制状态机(Replicated state machines)

raft复制状态机

名词二： 任期和选举

raft协议：任期

为了判断过时的信息，过时的leader，raft协议提出了任期(term)的概念

1.什么时候开始选举

2.选举和投票

2.1 跟随者发起选举，要进行以下的4个动作

2.2注意项

2.2.1 安全（Safety）

安全（Safety） 指的是必须最多只有一个候选者可以在某一任期内赢得领导者地位。Raft 可以保证这件事。每台服务器只给一个候选者投票，一旦它投出选票，它就会拒绝来自其他候选者的任何请求。服务器并不关心它的票到底投给了哪台服务器。为了实现这种机制，服务器需要保证将自己的投票信息存储到磁盘，这样就能在服务器崩溃之后也能恢复到之前的状态。否则就会出现服务器已经作出投票，并在崩溃重启后，在同一任期内将票又投给了另外一个不同服务器的情况。因为每台服务器只能进行一次投票，而且每个候选者都必须获得多数票，也就可以发现，不可能出现两个候选者同时获胜的情况。

比方说有三台服务器在某一任期内进行选举，另外两台服务器显然无法获得多数票。不过后面会介绍不同任期间会出现不同候选者获胜的情况，但在某一确定的任期内，只有一个候选者可以被选举为领导者。

2.2.2 可用（Liveness）

需要保证一定有获胜者，这样系统不会永远处于没有领导者的状态。问题在于理论上，会反复出现分票的情况，多个候选者在同一任期内同时开始进行选举，这样就会导致分票，在超时之后，又进行新一轮的选举又再次出现分票，所以从理论上说这样的状态可以无限循环下去。Raft 需要分散出现超时的间隔，每台服务器都会随机的计算下次超时的间隔时间，这个时间间隔在 [T, 2T] 之间。 T 代表着选举超时的时间，即服务器可能出现超时的最短时间。通过将超时时间分散，可以降低两台服务器同时开始选举的机率，先启动的那台有足够的时间向其他所有服务器发起请求，并在其他服务器参与竞争之前就完成选举这个过程。当这个超时间隔时间远大于广播投票请求的时间时，这个策略会变得更为有效。这里的广播时间指的是，一台服务器与其他所有服务器通信所需的时间。

名词三： 日志(log)与日志复制(log replication)

现在我们已经完整的知道了选举流程，集群中已经稳定的有个leader节点，开始对外提供服务，所有读写请求都发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。事实上raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。

复制状态机

再让我们回到名词一：复制状态机我们在这一节里似乎只说了状态机，没有说清楚复制是做啥用的。何为复制状态机？

If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.

简单来说：相同的初识状态 + 相同的输入 = 相同的结束状态。

引文中有一个很重要的词deterministic，就是说不同节点要以相同且确定性的函数来处理输入，而不要引入一下不确定的值，比如本地时间等。如何保证所有节点 get the same inputs in the same order，使用replicated log是一个很不错的注意，log具有持久化、保序的特点，是大多数分布式系统的基石。

 log entry

因此，可以这么说，在raft中，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则状态肯定是一致的。

下图形象展示了这种log-based replicated state machine

raft协议：状态机

请求完整流程

  当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：

可以看到日志的提交过程有点类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的，而2PC需要所有节点回复OK才能提交，否则要回滚。

log的组成

raft协议：log

  logs由顺序编号的log entry组成 ，每个log entry除了包含command，还包含产生该log entry时的leader term。从上图可以看到，五个节点的日志并不完全一致，raft算法为了保证高可用，并不是强一致性，而是最终一致性（CAP理论：一致性（C）->在分布式系统中的所有数据备份，在同一时刻是否同样的值），leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。

log提交的流程

raft协议：log流程

  在上面的流程中，leader只需要日志被复制到大多数节点即可向客户端返回，一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的command）在任何异常的情况下都不会发生回滚。这里有两个词：commit（committed），apply(applied)，前者是指日志被复制到了大多数节点后日志的状态；而后者则是节点将日志应用到状态机，真正影响到节点状态。

The leader decides when it is safe to apply a log entry to the state machines; such an entry is called committed. Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers

日志一致性

如果不同服务器上的日志条目具有相同的索引（index）和任期号（term），那么:

日志安全性

如果某个leader发现某条log entry已经被提交，则这条entry必须存在于所有后续的leader中。 为了实现这一点，raft算法规定：

  1. leaders永远不会修改自己log中的entries，只能添加；这条性质叫AppendOnlyProperty,即leader只能添加日志，但不能修改日志；这意味着leaders中log entries永远不会被修改；
  2. 只有leaders中的log才能被提交；言外之意是，某条日志即使过半server都存在了，但在leader中不存在，也是不能被提交的；
  3. entries在被提交给state machine执行之前，必须已被提交；即只有已被提交的日志才能被执行； 某个日志已被提交 -> 这条日志必定在后续leader中存在 为了实现这个安全性目标，raft算法规定：

raft协议：日志安全性

如图所示，在集群遇到leader不断切换的时候：

为了保证raft的commit的记录一定不会消失，我们必须还要修改已有的提交规则！ leader必须看到至少一条来自leader term（即leader的current term）的日志也存在于大多数的server上； 即当新leader看到某条来自之前term的日志已经存在于大多数server上时，它不能再认为这条日志是committed了，必须等到来自其自身term的第一条日志也存在于大多数server上，才能认为之前term的那条日志是committed的；这其实相当于一种leader change场景下的延迟commitment吧，或者换种思路，相当于将上一个term时期的日志的commitment与当前term时期的commitment绑定在了一起。

AppendEntries 一致性检查

raft协议：一致性检查

安全性：领导者变更

介绍完上面的名词和各种规范约束后，我们已经知道选举/状态机/日志是如何保证raft协议中的数据安全性了，现在开始尝试理解一下比较难以掌握的情况：领导者变更

当发生领导者变更时，raft协议如何保证数据的安全性

新领导者任期开始时:

raft协议：领导者变更

如上图，followers的log有哪些与leader可能不同的情况呢：

  1. missing entries：即follower的log与leader相比缺少某些entries，如图中的a/b/e follower；
  2. extraneous entries：即follower的log与leader相比多出某些entries，如图中的c/d/f follower;

leader为了保证follower的log与之相同，必须：

  1. 删除follower中的多余entries；
  2. 用自己的entries填充follower中的缺失entries；

为了恢复log一致性，leader为集群中所有follower都保存一个状态变量，即nextIndex：

  1. nextIndex是leader准备向某个follower发送的下一个log entry的index；
  2. 当leader刚刚即位后，nextIndex的初始值是（1+leader’s last index）；

如图举例：

raft协议：领导者变更2

挑选最好的领导者

我们已经知道leader决定一切，leader不会修改自己的日志，如果旧leader挂掉，新leader会要求其他follower接受它的日志，覆盖掉不一致的地方。所以如何挑选最好的领导者，就变得很重要。

raft协议：挑选最好的领导者

举个例子，如图： S1是term2时期的leader，刚把日志4复制到S2、S3成功，立马宣布日志4已安全（即在大多数server中都有，已被committed），立即在状态机上执行日志4；这意味着日志4是已提交的，后续的leader中必须包含这条entry，我们怎么确保呢？

设想，此时S1突然网络不通，需要重新选举leader，我们逐个分析：

综合以上，可能成为leader的server都含有日志4 ，即新的term3时期的leader必定含有日志4；换言之，最终新leader必定含有已committed的entry；

平衡旧领导者（Neutralizing Old Leader）

被罢免的领导者可能并不是真的死了，它可能是暂时与网络断开连接，但此时其他服务器选出新的领导者 如果网络恢复旧的领导者重新连接，尝试提交日志条目，如何防止集群脑裂？

任期（term)，回顾一下名词二，任期在这里可以防止旧领导者提交日志

 为了判断过时的信息，过时的leader，raft协议提出了任期(term)的概念
- 时序被分割为多个领导者任期
- 每个任期最多1个领导者
- 有些任期没有领导者（如：上图上的第2个阶段选举失败，但是任期值还是会加1）
- 每个服务器维护当前任期的值

问题

通过两个问题，回顾一下raft协议的关键点。

1.如何判断一个请求是否已被commit？

续上一个问题，如果一个请求在leader向客户端返回成功之前，leader刚好挂掉，那这个请求是否丢失？

答：这个请求不会丢失。分情况说明，假如请求了一个set dboop=51ak 这条命令

  1. 如果这个请求产生的日志没产生，那么集群中没有这条记录。客户端发现执行命令一直得不到反馈，会不停的重试，直到新leader产生，响应这个请求，写入成功
  2. 如果leader已写入日志，但还发送到其他节点，旧leader挂掉后，情况同1
  3. 如果leader已经将日志发送给follower，因为日志是顺序传输的，那么将会在选举中产生一个日志最新的节点会成为leader一定会包含这个日志，此时数据已经写入成功，但是客户端没有收到执行成功的命令，还会再次在新Leader上执行set dboop=51ak 这条命令。这就会导致这条命令执行了2次，造成数据错误。所以raft协议
    1. 要求客户端为每个command生成一个唯一id，并在发送command时候带上该id
    2. 当leader记录command时，会将command的id也记录到log entry中；
    3. 在leader接受command之前，会先检查log中是否有带该id的entry；
    4. leader一旦发现log中已有该id的entry，则会忽略这个new command，并将old command的结果返回给client（如果此时old command还没执行完，会等待其完成再返回）；
    5. 因此，只要client不crash，我们就能实现exactly-once语义，即每个command只会被执行一次。这也是我们希望系统具有的，被叫做linearize ability。
>> Home

51ak

2022/01/24

Categories: raft 分布式 Tags: 原创 精品

《数据库工作笔记》公众号
扫描上面的二维码，关注我的《数据库工作笔记》公众号