asynchronous heartbeat can cause a stale leader to hold lease indefinitely during disk IO stall

[Qian-Cheng-nju]

Hi, we found a path where a stale leader can maintain its lease indefinitely through what we call "phantom contacts". We have a reproduction test for this. Posting here to verify our analysis and see if a fix makes sense.

The inconsistency

In replicateTo(), the response term is checked before updating the last contact time:

// replicateTo() — replication.go L238-245
if resp.Term > req.Term {
    r.handleStaleTerm(s)
    return true
}
s.setLastContact()

In heartbeat(), this check is missing — setLastContact() is called unconditionally when the transport call succeeds:

// heartbeat() — replication.go L423-438
if err != nil {
    // ... handle error
} else {
    s.setLastContact()
    failures = 0
    s.notifyAll(resp.Success)
    // no resp.Term check
}

This means that even when a follower rejects the heartbeat due to a higher term (resp.Term > req.Term, resp.Success == false), the leader still records a successful contact with that follower.

What's the problem

Under normal operation, replicate() calls replicateTo() every CommitTimeout, which does check resp.Term — so the stale term gets caught quickly. This acts as a safety net.

But heartbeat() exists precisely to run independently when replicate() is blocked:

// heartbeat is used to periodically invoke AppendEntries on a peer
// to ensure they don't time out. This is done async of replicate(),
// since that routine could potentially be blocked on disk IO.

When the replicate() goroutine blocks on disk IO (e.g. GetLog() during setPreviousLog()), the safety net is gone. Only heartbeat() is sending RPCs, and it keeps calling setLastContact() for followers that have already moved on to a higher term. These "phantom contacts" feed into checkLeaderLease(), which counts them toward quorum, keeping the stale leader alive.

Concrete scenario

1. 3-node cluster: Leader L at term T, Followers F1 and F2
2. L's disk IO slows down — replicate() goroutines block on GetLog()
3. Network partition: L loses contact with F2
4. F1 ends up at term T+N (e.g. participated in a higher-term election during a transient partition), then connectivity between L and F1 is restored
5. L's heartbeat() sends AppendEntries{Term: T} to F1
6. F1's appendEntries handler: a.Term (T) < currentTerm (T+N) — rejects, returns resp.Term = T+N, resp.Success = false
7. Transport returns err = nil
8. L's heartbeat() calls setLastContact() for F1 — phantom contact
9. L's checkLeaderLease(): contacted = {L, F1} = 2 = quorum → L stays Leader at stale term T

This continues indefinitely as long as disk IO remains slow.

This requires three conditions to coincide: network partition, node restart, and disk IO stall on the leader. Not an easy combination to hit.

Reproduction

We wrote a test that reproduces this: https://github.com/specula-org/hashicorp-raft/blob/heartbeat-term-check-bug/heartbeat_term_bug_test.go

Suggested fix

Add the same resp.Term check to heartbeat():

} else {
    if resp.Term > req.Term {
        r.handleStaleTerm(s)
        return
    }
    s.setLastContact()
    failures = 0
    s.notifyAll(resp.Success)
}

Does this analysis hold up, or is there a mechanism we're not seeing that would prevent this path in production?

Thanks for your time.

[otoolep]

@Qian-Cheng-nju -- drive-by comment. If you want to make this as easy as possible you should fork this repo and create new unit test in the existing test suite. The generate a PR, and watch the CI system mark the unit test as failing.

[Qian-Cheng-nju]

@otoolep Thanks for your reminder!

PR submitted: #667

The test (TestRaft_HeartbeatTermCheck) is expected to fail on CI — it asserts the leader should step down after heartbeat receives a higher term, which doesn't happen with the current code.

Would appreciate it if someone could approve the workflow run so CI can confirm the failure.

[Qian-Cheng-nju]

Hi @tgross @otoolep, friendly follow-up on this. Per @otoolep's suggestion, I submitted PR #667 with a failing test (TestRaft_HeartbeatTermCheck) that demonstrates the issue. The CI workflow is pending approval.

Would love to hear whether the analysis looks correct. Happy to make any adjustments to the PR. Thanks!

[tgross]

Apologies for the delay @Qian-Cheng-nju. I'm looking into this and the PR

[tgross]

@Qian-Cheng-nju before I get into my findings in my next post... I'm going to ask you to please be up front about the source of your findings when you're interacting with open source repository maintainers. I shouldn't have to dig into your organization's profile to find this:

AI-driven formal modeling and verification for real-world systems.

Libraries like this are catnip for drive-by AI bug findings from non-practitioner researchers, and we really need to make sure we're triaging them appropriately.

[tgross]

Hello again @Qian-Cheng-nju! #28 (comment) has a good description of what the heartbeat AppendEntries RPC is trying to do here on top of the usual replication:

Yeah, it's a subtle detail of how we've implemented raft. It's from section 5.3 on log replication. For a number of reasons, we do the heartbeats async from the AppendEntries with actual log data. Mostly it's to avoid head of line blocking on network and disk.

The heartbeat does include the leader's term, and in any case the follower always has the term in its response, so it's possible for us to check it on the leader when handling the response.

However, there are problems with the liveness problem as described. If the followers are getting heartbeats from the leader, they'll call setLastContact at the end of the appendEntries handler (ref raft.go#L1580), which resets the heartbeat timeout. The followers won't hold an election and therefore the term won't increase and the mechanism you've suggested to recover from this situation will never succeed. Assuming somehow the term did increment, the log store would need to be blocked indefinitely in order to indefinitely block the leader. Once we get even a single log replicated, the leader would step down.

Unfortunately your test doesn't seem to demonstrate the scenario, as it passes without having made any changes to the production code!

That said, I think the real challenge happens when we don't increment the term. That would allow the leader to keep the heartbeat alive and prevent followers from electing a new leader when blocked on disk IO, even in the face of the mitigation you've described. This may even be at the root of some open issues that were never resolved like #503, #612, and #614 In a couple of those, folks have (potentially dodgy) custom log stores that are causing blocking, which is what your test was trying to demonstrate.

Because we're sending the heartbeat to determine last contact even if there aren't logs to replicate, I suspect we'd need a way to set a "dirty" flag at the top of replicate where the heartbeat could stop if that flag was set for longer than some timeout. Tuning that timeout is a little tricky, given the whole point of the heartbeat is to allow the leader to hold onto the lease in the face of disk IO stalls. I'm going to circle up with some of my colleagues and see if they have thoughts on where to go with this next. @otoolep I'd welcome your thoughts here too, especially if you've run into this kind of thing on your project.

[otoolep]

Hi -- I have not received any reports from the field like this. rqlite uses the standard BoltDB (well, etcd's fork) for its log store. Those are interesting bug reports, haven't seen anything like that personally.

[tgross]

I've had a chat with my colleague @schmichael around this and we have a few notes...

Importantly, this is a liveness issue and not a correctness issue. Solving liveness issues will always involve tradeoffs and so we're trying to find a point in the design space that maximized liveness without impacting correctness. This is also not the problem described in Raft does not Guarantee Liveness in the face of Network Faults.

The partition between L and F2 in the scenario described here is a red herring. If F2 is partitioned from L and enters candidate status, F1 will always reject the election request because F1 is still has contact with the leader (ref raft.go#L1650-L1656). This check prevents a scenario where a persistent asymmetric partition with F1-F2 on one side and F1-L on the other has continuous leader elections.

But the liveness issue doesn't require a partition, partial or otherwise! If the leader can send heartbeats but not read from disk, it'll repeatedly update the lastContact on the followers, which will never hit their heartbeat timeout and therefore will never hold a new election. From the followers' perspective, there's no difference between this and the leader simply not having any more data to replicate.

One option here would be to make the heartbeat appendEntries serialized with data appendEntries, so that we only send heartbeats if we haven't sent data within a short timeout (10-20% of the leader lease, as we do today). The tradeoff here is that a temporary disk stall would result in leadership elections, and avoiding this is why they're concurrent today (as I mentioned yesterday, described in #28 (comment)). It's definitely possible for a disk to persistently stall, especially in cloud environments where you have NVMe-over-TCP disks that can simply disappear out from under you (ex #503). But operators of applications using this library today will already have a body of experience with the set of timeouts we have, so changing that behavior to introduce more elections to solve a somewhat rare liveness issue would make things worse rather than better.

The approach I've suggested in #666 (comment) is where we'd set a timestamp at the start of replicate function calls that we'd check in heartbeat. A pseudo-code diff is something like:

diff --git a/replication.go b/replication.go
index d48a8c8..52da064 100644
--- a/replication.go
+++ b/replication.go
@@ -200,6 +200,10 @@ PIPELINE:
 // given last index.
 // If the follower log is behind, we take care to bring them up to date.
 func (r *Raft) replicateTo(s *followerReplication, lastIndex uint64) (shouldStop bool) {
+
+       r.lastReplicationStart = time.Now()
+       defer func() { r.lastReplicationStart = time.Time{} }()
+
        // Create the base request
        var req AppendEntriesRequest
        var resp AppendEntriesResponse
@@ -404,6 +408,10 @@ func (r *Raft) heartbeat(s *followerReplication, stopCh chan struct{}) {
                        return
                }

+               if r.lastReplicationStart > time.Now().Sub(time.Second*30) {
+                       return
+               }
+
                s.peerLock.RLock()
                peer := s.peer
                s.peerLock.RUnlock()

(Obviously that's not the actual diff, as that'd have a bunch of data races.) This would not introduce extra leadership flapping so long as the timeout was sufficiently long. Given that we're trying to recover from a rare circumstance where there's persistent disk stalls, this timeout could even be very long (ex. 5x the heartbeat timeout). It'd essentially only be there as a stop-gap measure to attempt to restore forward progress before an operator gets woken up.

Next steps here:

• We're going to expand the documentation we have in the repo to explain some of the tradeoffs we're making, and where our implementation diverges from Diego Ongaro's thesis so that we can try to steer initial conversations more productively in the future.
• I'm going to write a new test (and probably some example code) to demonstrate the liveness issue.
• I'll work up a PR with fix approach I've suggested.

[schmichael]

We're going to expand the documentation we have in the repo to explain ... where our implementation diverges from Diego Ongaro's thesis

Here's that bit: #668

[Qian-Cheng-nju]

@tgross @schmichael @otoolep Thank you for the time and effort you put into this issue. I was genuinely moved by how seriously you engaged with our report and how thorough your analysis was. I learned a lot from this exchange.

On transparency:

I deeply apologize for not being upfront from the start. I used Specula which is a project that uses AI-assisted formal verification (TLA+ model checking) to find bugs in real-world systems. AI helps with TLA+ spec generation, but PRs, bug reproduction, and validation are done by me. The broken test in PR #667 was entirely my mistake. I failed to verify that the test actually fails without the proposed code change before submitting. Going forward, I will make sure to thoroughly verify and reproduce any findings before reporting, rather than wasting maintainers' time.

On the technical analysis:

I fully agree that the phantom contact scenario we described is not triggerable due to the check. The real liveness issue you identified: a leader with a disk IO stall maintaining its lease via heartbeat, preventing followers from electing a new leader while the cluster cannot commit new logs. It is far more fundamental and practical than what we reported.

I've closed PR #667. Thanks for pointing out the cluster test helper in the review, @tgross — will keep that in mind.

Thank you again for your patience and rigor. The divergence documentation in PR #668 will be a great resource for future contributors.

[tgross]

Very ugly working branch is here: https://github.com/hashicorp/raft/compare/liveness-on-leader-disk-stall This doesn't quite work yet, as it seems to be causing a test flake in TestRaft_FollowerRemovalNoElection even if we set the condition to be extremely long such that we can never hit it. I'll keep at it.