如果 etcd raft 的日志复制乱序怎么办？

Question

我是etcd的新手，对日志复制有一些困惑：

比如leader发出{term:2,index:3}，然后发出{term:2,index:4}，大部分也按顺序响应。但是由于网络延迟，leader收到的响应乱序，先收到{term:2,index:4}的响应。

etcd如何处理这种情况？好像直接忽略日志{term:2,index:3}，直接commit {term:2,index:4}

func (pr *Progress) MaybeUpdate(n uint64) bool {
    var updated bool
    if pr.Match < n {
        pr.Match = n
        updated = true
        pr.ProbeAcked()
    }
    pr.Next = max(pr.Next, n+1)
    return updated
}

当响应数据包（例如{term:2,index:3}的响应）丢失发生时，etcd如何重试？我在 etcd 项目中找不到任何代码片段来处理这个问题。

Answer 1

您问的问题与 raft 相关的多于与 etcd 相关的问题（etcd 实现了 raft，因此它们仍然相关）。为了深入了解 raft 算法，我强烈建议您查看 raft webpage and raft paper（写得真好！）。我相信第 5.3 节“日志复制”会有所帮助。

首先让我们建立一些基础：Leader 跟踪与每个 follower 匹配的条目。它将信息保存在论文中的 nextIndex[] 和 matchIndex[] 中（检查图 2）以及 etcd 中的 ProgressMap 中。

// ProgressMap is a map of *Progress.
type ProgressMap map[uint64]*Progress

type Progress struct {
    Match, Next uint64
    ...
}

现在让我们跳到您的问题。

For example, leader send out {term:2,index:3} and then {term:2,index:4}, the majority respond in order too. But due to network delay, leader receive the responses out of order, receive response of {term:2,index:4} first. How etcd handle such case? It seems like just ignore the log {term:2,index:3}, commit {term:2,index:4} directly.

这里完全取决于跟随者的状态（从领导者的角度来看）。让我们深入研究 StateProbe 和 StateReplicate.

在 StateProbe 中，leader 试图弄清楚应该将哪些条目发送给 follower。它一次发送一条消息并等待响应（这可能是拒绝响应，在这种情况下领导者必须减少与该跟随者相关的 Next 并重试）。在这种状态下，向同一个追随者发送 2 个不同的 MsgApp 是不可能的。

在 StateReplicate 中，领导者假设网络稳定并发送（可能）许多 MsgApp 消息。让我们举个例子。

Match := 2、Next := 2

关注者日志：[E1, E2]（E 代表“条目”）

领导日志：[E1, E2]

在此状态下，领导者收到条目 E3、E4 和 E5 的请求。假设最大批处理大小为 2，因此所有新条目都不能在单个消息中发送。 Leader 将发送 2 条消息：(Index: 3, Entries: [E3, E4]) 和 (Index: 5, Entries: [E5])。第二条消息将在获得第一条消息之前发送。在图片中的情况下，follower 收到第一条消息，检查它是否可以使用请求中的 Index 附加它（检查在 (raft).handleAppendEntries > (raftLog).maybeAppend > (raftLog).matchTerm > (raftLog).term 中执行），将条目附加到它的日志并发送 ack。稍后，follower 收到第二个请求并对其执行相同的操作（检查它是否可以附加它并发送 ack）。

关注者在发送 ack 之前检查它是否可以附加条目这一事实在这里很重要。一旦 leader 收到任何消息的 ack，可以确保所有 Index + len(Entries) 之前的条目都填充在 follower 的日志中（否则该消息将被拒绝而不是被确认）。因此，如果第一个 ack 延迟（甚至丢失）并不重要。

How etcd retry when response packet(e.g. resp of {term:2,index:3}) loss happen? I can't find any code snippet to handle this in the etcd project.

我现在将重点放在 etcd 上，因为在 raft 论文中它被描述为“领导者无限期地重试 AppendEntries RPC”，这是相当没有建设性的。每隔很短的时间间隔，leader 会向 follower 发送 MsgHeartbeat，follower 会回复 MsgHeartbeatResp。作为 MsgHeartbeatResp 处理的一部分，领导者会跟随

if pr.Match < r.raftLog.lastIndex() {
    r.sendAppend(m.From)
}

应理解为：“如果追随者没有任何条目，请将第一个丢失的条目发送给他”。这可以看作是重试机制，因为 pr.Match 不会在没有来自追随者的确认的情况下增加。

如果 etcd raft 的日志复制乱序怎么办？

What if log replication out-of-order of etcd raft?

etcd

consensus

raft