第 2 部分 — 日志复制

介绍

Raft 是一种共识算法，旨在以分布式方式编排副本。Raft 在设计时考虑了可理解性，只有几个活动部件并且易于实施。在上一篇文章中，我讲了 Raft 的基础知识，并解释了领导者选举机制。在这篇文章中，我们将关注另一个重要问题——日志复制。

基础知识

Raft 本质上是一堆复制的状态机。每当领导节点收到请求时，都会将其附加到日志中以确保持久性。相同的日志被复制到多台机器上以实现冗余。

图 0. Raft 日志，作者图

例如，在图 1 中，当前领导者的日志中有四个条目。关注者 1 完全同步，但关注者 2 缺少最新条目。如果你不明白图0中的Term是什么，可以看看我之前的文章。

用于日志复制的 RPC

为便于理解而设计，Raft 仅使用两个 RPC 调用进行所有通信：

AppendEntry：这个RPC由leader发起，携带最新收到的命令。它还用作心跳消息。当追随者收到此消息时，选举计时器将重置。AppendEntry消息是这样的结构（我在这里使用 Golang）

type AppendEntryArgs struct {
	Term			int		// current term of the leader, very IMPORTANT
	LeaderId 		int		// id of the leader, 0 to N-1 where N = total servers
	Entries			[]Entry // new data to sync
	PrevLogIndex	int		// important metadata for log correctness
	PrevLogTerm		int		// important metadata for log correctness
	LeaderCommit	int 	// what index have been received by the majority
}

type AppendEntryReply struct {
	Term 			int 	// current term of the receiving node
	Success			bool	// AppendEntry declined or accepted
	ConflictIndex	int		// if declined, specifying the conflicting index
	ConflictTerm	int		// if declined, specifying the conflicting term
}

如果您不了解每个字段的含义也没关系。我们将一一检查。

RequestVote：这个RPC用于leader选举，在上一篇文章中有介绍。我将跳过它，因为我们只关心日志复制。

日志复制详细信息

让我们从普通日志复制算法开始。每当领导者收到请求时，它会将日志条目转发给所有追随者并等待大多数人确认。

问题 1：日志排序

香草算法会在追随者到达后立即向他们发送消息。为此，它只需要消息中的两个字段—— leaderID和Entry。一个主要问题是由于潜在的消息延迟而无法保留日志顺序。考虑图 1 中的场景。

图 1. 日志排序问题，作者图

Raft 使用两个额外的字段来确保日志的完整性——PrevLogIndex和PrevLogTerm。当一个新条目发出时，leader 也会发出之前条目的索引和任期号。接收方在将新请求附加到其本地日志之前确保其最新条目具有相同的索引和任期。

图 2.附加记账的AppendEntry，作者图

有了这两个额外的参数，我们可以实现一些很棒的东西：

1. 给定日志索引，如果来自两个日志（在两台不同机器上）的条目共享相同的术语，则它们是相同的
2. 如果不同日志中的两个条目具有相同的索引和任期，则所有前面的条目都是相同的

第一个性质很容易证明。假设索赔是错误的。如果存在两个具有相同任期的不同条目，则其中一个必须比另一个更晚被领导者接收。由于日志是仅附加的，因此其中一个条目将具有更大的PrevLogIndex。但是，如果它们出现在两个不同日志的相同索引中，则它们必须具有相同的PrevLogIndex。（否则接收方拒绝） 矛盾！！

第二个主张可以通过归纳证明：

图 3. 声明 2 的归纳证明，作者图

这两个保证共同构成了 Raft 的日志匹配特性。

问题 2：具有冲突条目的关注者

如果 leader 日志是集群中唯一的权限，它将覆盖 follower 的任何冲突。是否有可能丢失一些日志条目？考虑以下情况：

图 4. 日志冲突，作者图

在深入探讨这个问题之前，我想说服您上述情况确实会发生。日志在索引 2 之前同步。从那里开始，创建这些日志可能会发生以下情况：

1) 节点 2 成为领导者（从自己投票，1 和 0）任期 22) 节点 2 收到来自客户端的请求，但未能与其他节点同步
3) 节点 0 成为领导者（来自 1 和它自己的投票），任期为 3 
4) 节点 0 收到来自客户端的请求。但未能同步

现在，如果节点 0 重新与节点 2 联系，它将尝试复制其日志，如图 5 所示

图 5. 覆盖冲突，作者图

如您所见，绿色条目确实被丢弃了。按照目前的设计，这个问题是不可避免的。然而，这里的一个关键观察是绿色条目没有在大多数（至少两个节点）上复制。如果是，它将永远不会被丢弃，原因如下：

1. 如果一个条目在大多数情况下被复制，则至少有 N/2 + 1 个节点拥有它
2. 对于没有进入选举的节点，它需要其他节点的N/2票（候选人总是为自己投票）
3. 由于候选人没有条目，因此具有条目的 N/2 + 1 个节点不会投票给它（选举限制在第 1 部分中解释）
4. It won't get enough votes to win the election

这就是 Raft 的第二个关键特性——日志完整性属性。如果一个条目在 majority 上被复制，它将始终出现在未来的领导者日志中，无论它可能是哪个节点。如果没有在大多数人身上复制，则如果领导层发生变化，条目可能会被删除。

对于日志完整性属性，重要的是不要在大多数人收到之前确认客户端请求。

问题 3：何时提交？

最后，我们到了最后一个问题——什么时候提交条目？首先什么是commit，为什么要commit？Raft 是一种低级共识算法，供上层应用程序使用，如键值存储（例如 ZooKeeper）。当一个条目被 Raft 安全地复制时，我们要确保客户端可以通过应用程序看到它。因此，Raft 需要决定何时告诉上层应用程序一个条目已准备好使用（一个部分复制的条目，因为领导者日志中的最后一个条目不应该是可见的！）。

图 6. 提交，作者图

到目前为止，我们的香草算法没有携带任何关于提交索引的信息。因为数据流是单向的，从领导者流向追随者，所以节点不知道一个条目是否在大多数节点上被复制。

为了解决这个问题，我们可以在AppendEntry消息中添加另一个字段，称为LeaderCommit。如果大多数接收到一个条目，领导者会增加提交索引。下面是跟踪领导节点使用的提交索引的实际代码。

for n := rf.getLastIndex(); n >= rf.commitIndex; n-- {
// start from the latest entry
	count := 1

	if rf.log[n].Term == rf.currentTerm {
// leader only cares about entries of its term
// entries with smaller terms are commited automatically when higher terms are 
// committed 
		for i := 0; i < len(rf.peers); i++ {
			if rf.peer[i].hasEntry(n) {
							count++
						}
					}
		}
	if count > len(rf.peers) / 2 {
		rf.commitIndex = n
// no need to go further back, for reasons stated in line 7 and 8
		break
	}
}

领导者如何跟踪提交索引

概括

在这篇文章中，我们从普通的日志复制算法（广播条目，没有任何额外的簿记）开始，并通过考虑各种极端情况将其发展为成熟的版本。日志复制中最重要的 RPC 是AppendEntry RPC，它使用具有四个字段的结构：

• Term：对于日志复制和领导者选举非常重要
• LeaderId : 显示候选人的身份。
• 条目：领导者希望复制的条目列表。
• PrevLogIndex ：在Entries[0]之前的日志条目的索引。用于确保日志完整性和日志匹配属性
• PrevLogTerm ：在Entries[0]之前的日志条目的任期。用于确保日志完整性和日志匹配属性
• LeaderCommit：对上层应用很重要。只有已提交的条目才能应用于应用程序并且对客户端可见。