kvserver: allow reads on circuit-broken replicas

[tbg]

Touches #33007.

Is your feature request related to a problem? Please describe.
As of #71806, when a replica's circuit breaker trips, reads bounce on the breaker. This might be unnecessary in some cases - if there is a valid lease, there is a chance that the read would go through.

Reads may not go through though, as inflight replication proposals hold latches that may block the read.

Describe the solution you'd like

Serve reads "when it is possible" (i.e. when they don't get stuck).

Two solutions present themselves:

use two circuit breakers

To the replication circuit breaker (that's the one we have today), add a latching circuit breaker which trips when latch acquisition takes a long time (or alternatively, if a latch is held for a long time, which catches more problems but may also be more prone to false positives).

Both are checked on the write path, i.e. writes fail fast if either is tripped.
For reads, check only the latter, i.e. if the replication circuit breaker is tripped, reads continue to be served (or at least attempted) until the latching breaker trips as well.

check transitive deps for writes in latching when breaker open

We stick with just one breaker. If a read is waiting for latches and the breaker trips (or is tripped to begin with), visit the transitive set of dependencies and fail fast if it contains a mutation.

This is probably awkward to implement.

Describe alternatives you've considered

Additional context
Transitively computing latch dependencies also came up in the context of #65099 (comment).

Jira issue: CRDB-12271

[tbg]

@nvanbenschoten pointed out (internal) a simplification that I had overlooked: reads don't block on reads, so if a read enters the replica while the breaker is tripped, we can let them in anyway but "somehow" give them a non-blocking latch policy where an error is returned if a blocking latch is encountered. Reads don't block on reads during latching, so the only way for a read to block on a latch is if it encounters a write, and it is reasonable to assume that the write latch is permanent until the replica becomes available again. This isn't quite enough, since reads may also trigger lease acquisitions, which would stall as well, so the read must additionally bail out if the lease is not valid (in effect behaving like a follower read). In fact, follower reads should never encounter latches, so perhaps we can unify things by making follower reads latch-rejectable and simply turning leaseholder-but-tripped reads into follower reads.

Note that there may be some reads that bounce right as the breaker trips, since reads that enter under a healthy breaker will not have this non-block policy. Instead, their context will be cancelled as the breaker trips, sending them back up the stack. If we wanted to, we could let them re-enter but it may not be a big enough issue to add complexity for.

[nvanbenschoten]

This isn't quite enough, since reads may also trigger lease acquisitions, which would stall as well, so the read must additionally bail out if the lease is not valid (in effect behaving like a follower read).

If the lease is not valid then the read will be promoted to a write when trying to acquire the lease. This write will then hit the breaker and return an error. Is there anything more needed?

Note that there may be some reads that bounce right as the breaker trips, since reads that enter under a healthy breaker will not have this non-block policy. Instead, their context will be cancelled as the breaker trips, sending them back up the stack. If we wanted to, we could let them re-enter but it may not be a big enough issue to add complexity for.

This is a good point that indicates that eagerly setting a policy is probably not the right solution.

An alternative that seems to have legs is to replace the non-blocking policy with a way to "poison" latches. Take Rust's support for Mutex poisoning as an example: https://doc.rust-lang.org/std/sync/struct.Mutex.html#poisoning. After a write has been proposed, it can't drop its latches until the proposal completes. However, if the proposed write was to somehow learn about the unavailability (does it already?), it could then poison its latches while continuing to hold them. This would instruct any request that is currently or will later wait on these latches to fail fast instead of waiting.

A few benefits of this change are that:

1. it does not require eagerly deciding on a wait policy, which bloats the latch manager API and has the race discussed above.
2. the poisoning is targetted to exactly the set of spans that are stuck on replication. A request would only be rejected if it directly conflicted with a poisoned latch, not if it indirectly conflicted through a series of dependent latches.
3. the behavior would apply to writes blocking on latches in the same way as it would apply to reads

I think this kind of approach could allow us to push down the replication circuit breaker into the replication layer (e.g. down into Replica.propose), instead of dealing with context cancellation all the way up in Replica.sendWithoutRangeID.

[nvanbenschoten]

If the lease is not valid then the read will be promoted to a write when trying to acquire the lease. This write will then hit the breaker and return an error. Is there anything more needed?

This same line of reasoning should also apply to transaction lock contention. I was concerned that with this latch-poisoning proposal, read requests could get blocked on locks indefinitely due to unavailability. However, that does not seem to be the case.

If the unavailability is on the lock holder's txn record's range, then the read-only request will hit the breaker error when it goes to push the record. Either the range will be unavailable with a lease and so the push will fail directly, or it will be unavailable without a lease and so the push will fail when it tries to acquire the lease.

If the unavailability is on the lock's range then the read-only request will hit the breaker error when it goes to resolve the lock.

Either way, the read-only request should not be blocked indefinitely.

[tbg]

If the lease is not valid then the read will be promoted to a write when trying to acquire the lease. This write will then hit the breaker and return an error. Is there anything more needed?

No, that's correct, good point.

However, if the proposed write was to somehow learn about the unavailability (does it already?)

Not in the way that you probably need. The client's context will be canceled. The proposal will remain in the proposals map. However, we could notify pending proposals in refreshProposalsLocked, which is currently tasked with tripping the breaker (though in the future there may be other mechanisms that do so, too).

cockroach/pkg/kv/kvserver/replica_raft.go

Lines 1123 to 1125 in c5d146b

	func (r *Replica) refreshProposalsLocked(
	ctx context.Context, refreshAtDelta int, reason refreshRaftReason,
	) {

I think this kind of approach could allow us to push down the replication circuit breaker into the replication layer (e.g. down into Replica.propose), instead of dealing with context cancellation all the way up in Replica.sendWithoutRangeID.

That's a good observation and everything you say above the quote is appealing to me as well. There is a question about what kinds of "unavailability" the circuit breaker is supposed to track, and ideally the answer is "any possible one", which would indicate that moving it completely to the replication layer isn't the right approach (as we'd want "slow requests" of any type to consider tripping the breaker, and its probe to exercise bits that require not only replication). But we could still move large parts of it down, definitely the replication/proposal-centric pieces.

[nvanbenschoten]

There is a question about what kinds of "unavailability" the circuit breaker is supposed to track, and ideally the answer is "any possible one", which would indicate that moving it completely to the replication layer isn't the right approach (as we'd want "slow requests" of any type to consider tripping the breaker, and its probe to exercise bits that require not only replication).

This is interesting. I did not realize the goal was for the circuit-breaker logic to be generalized beyond replication failures. What other kinds of unavailability do you have in mind? Perhaps stalled disks?

An alternative that seems to have legs is to replace the non-blocking policy with a way to "poison" latches.

For what it's worth, this wouldn't be very difficult. Here's a basic prototype that includes most of the necessary plumbing: nvanbenschoten@c1f2f47. I'd be happy to review any changes or work together on this issue if that helps, as I want to make sure we don't reduce follower read availability in this release.

[tbg]

@lunevalex made the good point that follower reads may not "always" be affected in case of a quorum loss. In steady state, only the leaseholder proposes commands. If quorum is lost, since the relevant leases are epoch-based, the lease remains valid (unless liveness heartbeats are affected, which for now I'll assume they're not). So followers should find no reason to trip their circuit breaker; they would only do so when trying to replicate a command, which they would only do to acquire a lease. The leaseholder, on the other hand, would trip (assuming it saw write activity), so we would be in the weird situation in which the leaseholder can't serve follower reads but the followers can. That discrepancy is unfortunate, and your suggestion would fix it. We should have a crack at it.

This is interesting. I did not realize the goal was for the circuit-breaker logic to be generalized beyond replication failures. What other kinds of unavailability do you have in mind? Perhaps stalled disks?

Slow evaluation, deadlocks, that sort of thing, but we haven't really had a conversation. Disk health should be adequately represented by replication; if disks are "slow" but fast enough to replicate commands in time, I don't think the circuit breaker should necessarily get involved unless we're really confident that traffic should be redirected elsewhere (which it may not; if the lease is local then we're the only place this traffic can be served from).

[tbg]

Working on #76673 I had another thought, which is that the poisoning idea gets mildly more complex if we allow certain requests to bypass the breaker. Basically, if you decide to wait on a poisoned latch anyway, you need to poison your own latch, too. (I think that's it).

[tbg]

Nathan and I met late last week to discuss this. Allowing requests to opt out of fail-fast behavior required some tweaks to Nathan's prototype above. I am starting to polish the result in #76858.

The poisoning machinery works like a charm. The remaining challenge amounts to a fairly extensive rework of the Replica circuit breaker plumbing, where we get rid of context cancellation as a primary mechanism. There are some technical challenges to solve (and fixing up the tests might reveal more issues), but nothing insurmountable.

[tbg]

Implemented in #76858.