raft: introduce persistent leader term in raft log

[pav-kv]

The raft log currently does not "remember" the last term of the leader who appended entries to the log. The state of a raft instance currently contains the Term of its latest vote, which might or might not be the leader. This means that the content of the log is not necessarily a prefix of this Term's leader.

The impact of this manifests in multiple ways:

• Safety of commit index advancement [#122100] on a follower is implicit, and relies on the leader's knowledge about the follower's log state. The leader advances commit index on a follower only as part of a MsgApp message, or has to cap it at the follower's Match index.
• This may result in unnecessary delays in commit index advancement on a follower: https://github.com/etcd-io/raft/issues/138.
• The async log storage protocol implements a complex workaround to track the in-flight entries to the storage.

We should introduce a "leader term" field into the state (both the HardState and the in-memory state of the raft log), with the following invariant:

Log.Entry[last].Term <= LeaderTerm <= Term

The LeaderTerm should be updated every time the log accepts an append from a leader. The "leader term" can be used for safety checks on the follower, before advancing the commit index. It can also be used for a simpler async log protocol.

Ultimately, the LeaderTerm is the missing piece of state that makes Raft log equivalent to Paxos acceptor (TODO: link to the doc). The equivalence is that the LeaderTerm of the log is the "max accepted proposal ID" in Paxos.

The introduction of LeaderTerm can be done as:

1. A start-up migration that initializes LeaderTerm = Log.Entry[last].Term.
2. Followed by running the code that maintains this field.

Jira issue: CRDB-37894

Epic CRDB-39898

[blathers-crl[bot]]

cc @cockroachdb/replication

[nvanbenschoten]

We should introduce a "leader term" field into the state (both the HardState and the in-memory state of the raft log)

We are also planning to persist Lead into HardState in the near future.

When we do so, we should be sure to not create confusion by also introducing a field called LeaderTerm, which is neither guaranteed to be HardState.Lead's term nor HardState.Term's leader.

[pav-kv]

Naming-wise, I think we would be good with something like AccTerm / AcceptedTerm. This would also align with Paxos terminology. Or LogTerm, meaning that the state of the log is consistent with the leader at this term.

[pav-kv]

@nvanbenschoten The Lead field will be guaranteed to match the Term though, right? We'll either have {Term=t, Lead=0} meaning that we don't know the leader yet, or {Term=t, Lead=n} meaning that we've learned the current-term leader. In both cases, AccTerm <= Term, and only reflects the state of the log.

[lyang24]

do we need the leader term in Soft and Hard state?

[nvanbenschoten]

The Lead field will be guaranteed to match the Term though, right? We'll either have {Term=t, Lead=0} meaning that we don't know the leader yet, or {Term=t, Lead=n} meaning that we've learned the current-term leader.

Yes, that is correct.