cockroachdb / cockroachdb/cockroach
raft: optimize leader replication flow with follower
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
When a Raft node becomes a new leader, it first sends out `MsgApp` messages to all its followers.
The first `MsgApp` is typically rejected unless there is an exact match between the leader's log and the follower's log.
### Current Behavior & Latency Issue:
When a follower rejects the first MsgApp, it responds with MsgAppResp(reject=true), providing a rejectHintIndex and rejectHintTerm.
Currently, upon receiving this rejection, the leader always sends another probing MsgApp and continues sending until it receives a MsgAppResp(reject=false).
This process has room for improvement.
### Proposed Optimization
Instead of blindly probing again, we can immediately transition the follower from `stateProbe` to `stateReplicate` if:
The `rejectHintIndex` and `rejectHintTerm` provided by the follower exist in the leader’s raftLog.
In this case, the leader can skip an extra probing message and directly send MsgApp with the log entry corresponding to `1 index higher of EntryId{rejectHintIndex, rejectHintTerm}.`
This is safe due to Raft’s Log Matching Property (Section 5.3 of the [Raft paper](https://raft.github.io/raft.pdf)), which states:
`If two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.`
### Why This Optimization Matters
The optimization reduces a single **Leader** -> `MsgApp` -> **Follower** -> `MsgAppResp` -> **Leader** round-trip, in a general scenario, reducing leader-follower synchronization latency.
The optimization is relevant in a general scenario because if client write workload is rather heavy, its unlikely that the new leader has most followers already caught up, and can directly replicate the "new leader dummy" entry without needing for a second probe.
In a global deployment, where network latency per hop may be tens of milliseconds, this improvement allows a new leader to catch up followers more quickly.
Faster leader-follower synchronization enables the leader to:
1 Replicate logs in stateReplicate sooner, which leader to:
2 Achieving quorum faster, allowing the leader to commit log entries earlier, which ultimately leads to:
3 Reducing client write latency in the event of a Raft leader change, since the leader can respond to leaseholder requests more quickly.
### Some additional thoughts:
A potential issue with the proposed fix is the leader falsely go into stateReplicate and send `MsgApp` with some entries, but when the follower receive this new `MsgApp`, it has already replicated the entries within it. So the follower rejects the MsgApp with a new rejectHint. The leader will go back to stateProbe when it sees the MsgAppResp with reject = true, since [it is currently in stateReplicate](https://github.com/cockroachdb/cockroach/blob/465e7721c22c61210e60b7dc1048bb367c07b684/pkg/raft/raft.go#L2060).
This can happen if there were redundant messages inflight to the follower(perhaps a snapshot from previous leader).
We essentially wasted an extra cycle in this scenario.
But I think this is ok, since its a more rare scenario than the one we are optimizing for here.
Jira issue: CRDB-47204
Contributor guide
Assessment
This issue has not been assessed yet.