08 | Raft算法（二）：如何复制日志？

Feb 28, 2020

08 | Raft算法（二）：如何复制日志？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

08 | Raft算法（二）：如何复制日志？

2020-02-28 韩健来自北京

《分布式协议与算法实战》

课程介绍



讲述：于航

时长09:41大小7.76M



你好，我是韩健。
通过上一讲的学习，你应该知道 Raft 除了能实现一系列值的共识之外，还能实现各节点日志的一致，不过你也许会有这样的疑惑：“什么是日志呢？它和我的业务数据有什么关系呢？”
想象一下，一个木筏（Raft）是由多根整齐一致的原木（Log）组成的，而原木又是由木质材料组成，所以你可以认为日志是由多条日志项（Log entry）组成的，如果把日志比喻成原木，那么日志项就是木质材料。
在 Raft 算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和应用（Apply）日志项到状态机的过程。
那 Raft 是如何复制日志的呢？又如何实现日志的一致的呢？这些内容是 Raft 中非常核心的内容，也是我今天讲解的重点，我希望你不懂就问，多在留言区提出你的想法。首先，咱们先来理解日志，这是你掌握如何复制日志、实现日志一致的基础。
如何理解日志？刚刚我提到，副本数据是以日志的形式存在的，日志是由日志项组成，日志项究竟是什么样子呢？
其实，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。那你该怎么理解这些信息呢？
指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
任期编号：创建这条日志项的领导者的任期编号。
从图中你可以看到，一届领导者任期，往往有多条日志项。而且日志项的索引值是连续的，这一点你需要注意。
讲到这儿你可能会问：不是说 Raft 实现了各节点间日志的一致吗？那为什么图中 4 个跟随者的日志都不一样呢？日志是怎么复制的呢？又该如何实现日志的一致呢？别着急，接下来咱们就来解决这几个问题。先来说说如何复制日志。
如何复制日志？你可以把 Raft 的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟。那日志复制的具体过程是什么呢？
首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上。
接着，如果领导者接收到大多数的“复制成功”响应后，它将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端。
学到这里，有同学可能有这样的疑问了，领导者将日志项应用到它的状态机，怎么没通知跟随者应用日志项呢？
这是 Raft 中的一个优化，领导者不直接发送消息通知其他节点应用指定日志项。因为领导者的日志复制 RPC 消息或心跳消息，包含了当前最大的，将会被提交（Commit）的日志项索引值。所以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。
因此，当其他节点接受领导者的心跳消息，或者新的日志复制 RPC 消息后，就会将这条日志项应用到它的状态机。而这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为了一段提交，降低了一半的消息延迟。
为了帮你理解，我画了一张过程图，然后再带你走一遍这个过程，这样你可以更加全面地掌握日志复制。
接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项应用到它的状态机中。
领导者将执行的结果返回给客户端。
当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中。
不过，这是一个理想状态下的日志复制过程。在实际环境中，复制日志的时候，你可能会遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。那么在这种情况下，Raft 算法是如何处理不一致日志，实现日志的一致的呢？
如何实现日志的一致？在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。具体有 2 个步骤。
首先，领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。
然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。
我带你详细地走一遍这个过程（为了方便演示，我们引入 2 个新变量）。
PrevLogEntry：表示当前要复制的日志项，前面一条日志项的索引值。比如在图中，如果领导者将索引值为 8 的日志项发送给跟随者，那么此时 PrevLogEntry 值为 7。
PrevLogTerm：表示当前要复制的日志项，前面一条日志项的任期编号，比如在图中，如果领导者将索引值为 8 的日志项发送给跟随者，那么此时 PrevLogTerm 值为 4。
领导者通过日志复制 RPC 消息，发送当前最新日志项到跟随者（为了演示方便，假设当前需要复制的日志项是最新的），这个消息的 PrevLogEntry 值为 7，PrevLogTerm 值为 4。
如果跟随者在它的日志中，找不到与 PrevLogEntry 值为 7、PrevLogTerm 值为 4 的日志项，也就是说它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项，并返回失败信息给领导者。
这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，这个消息的 PrevLogEntry 值为 6，PrevLogTerm 值为 3。
如果跟随者在它的日志中，找到了 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的日志项，那么日志复制 RPC 返回成功，这样一来，领导者就知道在 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的位置，跟随者的日志项与自己相同。
领导者通过日志复制 RPC，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。
从上面步骤中你可以看到，领导者通过日志复制 RPC 一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致。需要你注意的是，跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。
内容小结本节课我主要带你了解了在 Raft 中什么是日志、如何复制日志、以及如何处理不一致日志等内容。我希望你明确这样几个重点。
在 Raft 中，副本数据是以日志的形式存在的，其中日志项中的指令表示用户指定的数据。
兰伯特的 Multi-Paxos 不要求日志是连续的，但在 Raft 中日志必须是连续的。而且在 Raft 中，日志不仅是数据的载体，日志的完整性还影响领导者选举的结果。也就是说，日志完整性最高的节点才能当选领导者。
Raft 是通过以领导者的日志为准，来实现日志的一致的。
学完本节课你可以看到，值的共识和日志的一致都是由领导者决定的，领导者的唯一性很重要，那么如果我们需要对集群进行扩容或缩容，比如将 3 节点集群扩容为 5 节点集群，这时候是可能同时出现两个领导者的。这是为什么呢？在 Raft 中，又是如何解决这个问题的呢？我会在下一讲带你了解。
课堂思考我提到，领导者接收到大多数的“复制成功”响应后，就会将日志应用到它自己的状态机，然后返回“成功”响应客户端。如果此时有个节点不在“大多数”中，也就是说它接收日志项失败，那么在这种情况下，Raft 会如何处理实现日志的一致呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的朋友。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 26

提建议

07 | Raft算法（一）：如何选举领导者？

09 | Raft算法（三）：如何解决成员变更的问题？

 写留言

精选留言(86)

花家舍
置顶
2020-03-13
http://thesecretlivesofdata.com/raft/ 动画演示比文章牛逼多了
编辑回复: 这个资源好，推荐
共 7 条评论
77
Mars
2020-03-11
老师，我有个问题，在那个复制日志的五个过程里，如果第四步执行返回结果成功了，leader突然挂了，此时leader 的状态机已经更新，follower状态机没有更新，此时新选举出来的leader怎么处理这个流程来保证上一个leader的状态机更新apply到其他节点上了呢？
作者回复: 加一颗星:)，领导者选举能保证新领导者一定包含这条committed的日志项，但这条日志项在新领导者上处于未提交状态，这时新领导者，会尝试从最新日志项开始，向其他节点复制日志，如果，某条uncommitted的日志项，被发现已经成功复制到大多数节点上，这时这条日志项将处于提交状态，并被应用到状态机，通知其他节点提交这条日志。
共 23 条评论
51
Scott
2020-03-01
我有一个问题，考虑下面这种情况，假设集群有1 leader 多 follower 1. leader发出一条set x = 1，index为最新的appendEntries到所有的follower 2. 只有一台follower响应了，所以leader对client返回fail 3. 这时leader挂了，剩余机器重新进行选举，因为前面那台follower有最新的uncommited的日志，所以它会被选举为leader 这时就会有一个不一致，外部client认为set x = 1没有成功，但是实际上x = 1是成功的，这种情况合法吗？
展开
作者回复: 加一颗星:)，合法的，如果操作具有冥等性，比如“set x = 1”，就没关系，不影响结果，而且最后日志会去重压缩处理的，如果操作不具有冥等性，需要实现客户端协议，确保只提交一次。关于客户端协议，我后面会做补充。
共 33 条评论
33
葉月喵
2020-02-28
上一章跟随者投票时会比较日志索引号大小，用的是已提交的日志，还是已经复制的日志？
作者回复: 复制的，uncommited的。
共 2 条评论
24
阿kai(aeo
2020-03-16
感觉处理日志一致性问题的时候非常不efficient，如果follower落后得多了，那么来回的RPC大部分都是failure，很耗时间和带宽。follower是否可以直接返回它拥有的最新index，然后leader根据那个index开始看是否match自己的日志，如果match就直接一次性把剩余日志都给follower发过去。这样会有效率一些吧？
作者回复: 加一颗星:)，这是个工程实现层面的优化方式:)
共 5 条评论
14
XHH
2020-02-28
提供一个Raft算法动态演示教程，很清晰： http://thesecretlivesofdata.com/raft/
共 3 条评论
10
piboye
2020-09-17
为什么跟随者不直接告诉领导者我从哪里缺日志，而让领导者一个一个去尝试？
作者回复: 加一颗星:)，因为存在跟随者日志和领导者日志不一致的情况，这时领导者就不能只同步跟随者缺失的日志项，而是要先做日志一致性检查，如果日志项不一致，领导者要同步并覆盖掉跟随者节点上已存在但不一致的日志项。
共 2 条评论
10
DZ
2020-03-19
老师，请教下如果在指定时间内没有收到大部分follower复制成功响应，只收到少数，那么领导者如何处理这次提交？是直接不做任何处理，由心跳或者下次提交重新对齐日志？还是有重试或者rollback机制？
作者回复: 加一颗星:)，此时日志项仍处于未提交状态，领导者需要继续重试，按顺序复制日志项，只有当日志项被成功复制到大多数节点时，该日志项处于提交状态，然后被应用到状态机。
共 5 条评论
9
Geek_d40030
2020-07-02
老师您好，在日志更新的时候为什么有索引值了，还要判断任期呢？理论上索引值是单调递增的就能够判断跟随者的日志在什么位置吧。
作者回复: 加一颗星:)，这是因为日志项可能来自不同的领导者，比如，节点A、B的索引值4对应的日志项，它的任期编号分别为1和2，那么，这两个日志项，就是2个不同的领导者创建的，即它们是不同的日志项。
8
bc
2020-03-11
客户端并不知道谁是leader，怎么保证客户端的请求一定是由lead来处理的？
作者回复: 加一颗星:)。一般有2种实现方式：1. 接收到写请求的跟随者充当“代理”，转发写请求给领导者；2. 跟随者返回领导者信息给客户端，客户端再发起请求，直接联系领导者。在19、20讲，有更具体的分析。
共 2 条评论
7
Jialin
2020-02-28
1.Raft 日志格式： • 指令：一条由客户端请求指定的、状态机需要执行的指令。即客户端提交的数据 • 索引值：日志项对应的整数索引值，用来标识日志项的，是一个连续的、单调递增的整数号码 • 任期编号：创建这条日志项的领导者的任期编号 2.理想的日志复制阶段： • 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中 • 领导者通过日志复制 RPC，将新的日志项复制到其他的服务器 • 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中 • 领导者将执行的结果返回给客户端 • 当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中 3.实际生产环境中，复制日志的时候遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。Raft 算法按照“Raft 是通过以领导者的日志为准，来实现各节点日志的一致的”原则处理不一致日志，实现日志的一致，具体如下： • 领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。 • 领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致课后思考题：领导者接收到大多数的“复制成功”响应后，就会将日志提交到它自己的状态机，然后返回“成功”响应客户端。如果此时有个节点不在“大多数”中，也就是说它接收日志项失败，那么在这种情况下，Raft 会通过日志复制 RPC 的一致性检查，找到失败者节点上，与自己相同日志项的最大索引值，然后领导者强制该失败者更新覆盖的不一致日志项，实现日志的一致
展开
作者回复: 加一颗星:)
7
严海波
2021-10-06
这里有个优化没有说，对于日志落后很多的节点，这么一步步的往回走是很低效的，这种情况下leader可以阶段性发送snapshots一次性把落后的节点的日志迅速的追回到某个snapshots
5
后端进阶
2020-04-03
老师，我这里有个疑问：文章讲了raft优化成一阶段提交，二阶段提交变成心跳或者下一次日志复制的rpc请求，那么在leader返回成功给client时，还没来得及心跳和下一次rpc日志复制，此时leader宕机了，某个follower成为新的leader，而这个follower并没有这条uncommitted log，此时会不会这条日志会不会被覆盖掉？
作者回复: 加一颗星:)，会的，uncommitted log不能保证一定会被提交。
共 8 条评论
5
kylexy_0817
2020-03-29
日志必须的连续的，也就是说，新加入的节点必须要全量复制日志？如果日志量大，是否意味着新节点在完成复制日志前的一段很长的时间，都不能成为追随者？
作者回复: 加一颗星:)，是的，新节点需要同步全部日志，日志同步完成后，才具有投票权。
5
语法糖不甜
2020-04-25
老师我想问一下：图中的第二步是【领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。】那么此时跟随者会复制日志并提交吗吗？还是跟随者一定是在领导者确认之后才提交的呀？
作者回复: 加一颗星:)，不能哟，只有当日志项被复制到大多数节点上时，日志项才处于提交（committed）状态，然后领导者才会将该日志项应用到状态机，并通知跟随者将该日志项应用到状态机。
3
唐明
2020-03-01
如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端。我有个疑问，有ABC三个节点，假设领导者将日志复制给了A节点，在将日志复制给B和C时失败，A节点已经复制的日志项要怎么处理才能不出错呢？
作者回复: 加一颗星:)，会继续不断重试，按顺序复制，当将日志项复制到大多数节点时，应用该日志项到状态机。我们要注意的是，已提交的日志项，是一定存在，不会丢失的，未提交的日志项，可能会被覆盖，也可能会被提交。
共 3 条评论
4
shenfl
2020-02-28
老师有个疑问，当领导者提交日志到本地状态机后与客户端网络出问题了，此时客户端会以为本次写入不成功，这样就导致客户端与集群信息不一致，该怎么处理呢？
作者回复: 重试，指令操作具有冥等性就可以了，比如，set x = v。
共 3 条评论
4
山头
2020-08-16
Raft 能实现一系列值的共识，一系列值的共识是什么意思
作者回复: 加一颗星:)，可以理解为各节点就多个“位置”的内容达成共识，并且不再改变，比如，各节点在“位置”1存放“X”，在“位置”2存放“Y”。
3
Dovelol
2020-06-20
老师好，想问一下，raft算法日志复制中，假如当前客户端发送请求，领导者处理请求，日志是term是4，索引是8，那么会复制到跟随者，但是由于部分跟随者返回失败，最终领导者给客户端返回失败了，那么下次在处理请求的时候，term是4，索引会变成9还是继续保持8呢？
作者回复: 加一颗星:)，这个取决于实现，一般是9，因为操作的冥等性和状态机，能保证最终的结果是符合预期的，不会因为指令重复提交，而对结果产生影响。但如果我们需要实现线性一致性，那么，我们就需要客户端协议的配合，保证操作只执行一次，此时，索引仍是8。
3
z
2020-06-15
从follower节点的读请求一般会返回uncommitted状态的数据吗
作者回复: 加一颗星:)，不会，读请求读到的数据是状态机运算后的数据，即对所有应用（Applied）到状态机的日志项指令，运算后的值。
3

