Reviewed 5 of 5 files at r1, 63 of 63 files at r2, 14 of 14 files at r3, 5 of 5 files at r4, 4 of 4 files at r5, 2 of 2 files at r6.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @andreimatei, @nvanbenschoten, and @tbg)

pkg/kv/kvserver/queue.go, line 652 at r3 (raw file):

		if st.IsValid() && !st.OwnedBy(repl.StoreID()) {
			if log.V(1) {
				log.Infof(ctx, "needs lease; not adding: %s", st.Lease.String())

We shouldn't have to call .String() here. Does st.Lease implement the wrong fmt.Stringer on the value type? Can we fix that instead?

pkg/kv/kvserver/replica_proposal_buf.go, line 489 at r7 (raw file):

		if !iAmTheLeader && p.Request.IsLeaseRequest() {
			// TODO DURING REVIEW: I needed this to deflake a test. But is
			// generally seems like a good idea.

Hmm, yes, it does.

pkg/kv/kvserver/replica_range_lease.go, line 507 at r3 (raw file):

// its state, unless state == leaseError.
//
// - The lease is considered valid if the current timestamp (now) is

"considered valid" suggests that the returned lease state would be valid. I think what this really tells me is that VALID is no longer a good name for the lease state. How about "usable", which indicates the intersection of "not expired at current clock yet" and "can actually serve that particular request"?

pkg/kv/kvserver/replica_range_lease.go, line 556 at r3 (raw file):

//   * the client fails to read their own write.
//
// - The lease is considered expired in all other cases.

This misses the proscribed case.

pkg/kv/kvserver/store_snapshot.go, line 669 at r3 (raw file):

					return true
				}
				// TODO(benesch): this check does detect inactivity on replicas with

while you're here, add the missing "not"

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 29 at r1 (raw file):

  // UNUSABLE indicates that a lease has not expired at the present time
  // (i.e. it is VALID), but cannot be used to serve a given request. A
  // lease may be unusable for one of two reason.

reasons

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 70 at r1 (raw file):

  // PROSCRIBED indicates that the lease's proposed timestamp is earlier
  // than allowed and can't be used to serve a request. This is used to
  // detect node restarts: a node that has restarted will see its former

Isn't it also used in transfers?

LGTM

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten and @tbg)

pkg/kv/kvserver/queue.go, line 652 at r3 (raw file):

I think he might be trying to avoid st escaping

pkg/kv/kvserver/replica_range_lease.go, line 507 at r3 (raw file):

// its state, unless state == leaseError.
//
// - The lease is considered valid if the current timestamp (now) is

I appreciate the effort to make this comment good.
One thing that I think is not sufficiently clear is the explanation about "now", and why anything about the present time is necessary. One might reasonably ask why the reqTS is not sufficient - like it is for sql schema leases, for example. Like, if I'm querying about yesterday, why does the relationship of whatever lease the replica has to the "present time" matter? I could articulate some stuff, but I think you can do it better.

pkg/kv/kvserver/replica_range_lease.go, line 562 at r3 (raw file):

	lease roachpb.Lease,
	now hlc.ClockTimestamp,
	minProposedTS hlc.ClockTimestamp,

not new, but since you're all up in here: minProposedTS is always r.mu.minProposedTS. Let's remove the argument.

pkg/kv/kvserver/replica_range_lease.go, line 613 at r3 (raw file):

//
// Common operations to perform on the resulting status are to check if
// is is valid using the IsValid method and to check whether the lease

is is

pkg/kv/kvserver/replica_range_lease.go, line 871 at r4 (raw file):

// its output should be completely determined by its parameters.
func newNotLeaseHolderError(
	l roachpb.Lease, proposerStoreID roachpb.StoreID, rangeDesc *roachpb.RangeDescriptor, msg string,

this makes me sad. Have you tried making a deep copy when assigning err.Lease? I'm thinking that should be enough to keep l from escaping.
Or, perhaps LeaseStatus.Lease should be a pointer. It's nice to make it non-nullable in the proto, but there's no good reason why LeaseStatus is even a proto. If it wasn't a proto, then the leases in it would probably always be on the heap anyway - and we might save some copying. No?

pkg/kv/kvserver/replica_range_lease.go, line 930 at r5 (raw file):

}

// checkRequestTimeRLocked checks that the provided request timestamp is not

have you done the math about what the timestamp of non-blocking txns will be, and how it relates to the lease renewal policy? Will these requests generally encounter a lease that is good for them?

pkg/kv/kvserver/replica_range_lease.go, line 942 at r5 (raw file):

func (r *Replica) checkRequestTimeRLocked(
	now hlc.ClockTimestamp, reqTS hlc.Timestamp,
) *roachpb.Error {

consider returning error here

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 24 at r1 (raw file):

  // ERROR indicates that the lease can't be used or acquired.
  ERROR = 0;
  // VALID indicates that the lease is valid at the present time and can

consider moving away from talking about "present time", and describe these statuses in relationship to an explicit query time - namely the one in LeaseStatus.Timestamp.

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 78 at r2 (raw file):

// LeaseStatus holds the lease state, the timestamp at which the state
// is accurate, the timestamp of the request, the lease, and optionally

the comment change makes it sound like there's now two different timestamps in here, but there aren't. In the next commit you can put a link to Replica.leaseStatus though, and explain something a request's timestamp.

Thanks for the reviews!

One thing I wanted to get both of your opinions on is this BatchRequest.Timestamp (and by extension, BatchResponse.Timestamp) field. For non-transactional requests, it holds the request's timestamp, which is fine. But for transactional requests, it holds the transaction's read timestamp. This is kind of strange, since as of #32487, we write intents all the way at the transaction's write timestamp. So I think that means two things, independent of this PR:

1. it is possible to write an intent at a timestamp past a leaseholder's current clock
2. it is possible to write an intent at a timestamp past the expiration of a lease

Both of these seem bad, for a few reasons. First, we occasionally bump the timestamp cache to a time based on an intent/value in a range due to server-side retries, and until #59086, it is completely illegal to bump the timestamp cache past a leaseholder's clock. This could result in lost timestamp cache updates on a lease transfer. Second, if a leaseholder can perform intent writes above its local HLC clock then our current proposal to address #36431 is not complete, because even an intent resolved at its write time may violate observed timestamps.

This was all obscured by the fact that lease checks were consulting the local HLC clock, not the BatchRequest.Timestamp directly (though the BatchRequest.Timestamp was used to update the HLC clock). Now that we're being explicit about the request timestamp and its timestamp, I wonder if there's more we can do here. Maybe we should get rid of this BatchRequest.Timestamp/BatchResponse.Timestamp field or never set it for transaction requests and then be more explicit about when we want Txn.ReadTimestamp (e.g. to pass to MVCCScan) vs. when we want max(Txn.ReadTimestamp, Txn.WriteTimestamp) (e.g. to compare against a lease)?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @andreimatei and @tbg)

pkg/kv/kvserver/queue.go, line 652 at r3 (raw file):

Right, that was the intention. But even without the .String(), it doesn't seem to be escaping. So I removed it.

pkg/kv/kvserver/replica_proposal_buf.go, line 489 at r7 (raw file):

I opened #59179 to track this and removed this commit.

pkg/kv/kvserver/replica_range_lease.go, line 507 at r3 (raw file):

I've made this change 3 times now before realizing it's unsafe, so that pretty clearly indicates that we need some better comments around here. The reason why we need both a reqTS and current clock reading is so that we can differentiate between EXPIRED and UNUSABLE. Only an EXPIRED lease can be non-cooperatively acquired by another node. If a node attempted to grab away an UNUSABLE lease (previously STASIS), it could violate reads served on the existing leaseholder.

I've added some additional assertions and some more documentation to make this clearer. What do you think?

pkg/kv/kvserver/replica_range_lease.go, line 507 at r3 (raw file):

Good point. I reworded a few comments to better indicate this. I didn't get quite as far as renaming valid to usable because I think they both work.

pkg/kv/kvserver/replica_range_lease.go, line 556 at r3 (raw file):

Done.

pkg/kv/kvserver/replica_range_lease.go, line 562 at r3 (raw file):

Eh, I think the idea is that the status is fully resolved by these arguments, so there are no hidden dependencies. That's also why we accept the lease. But that's also not quite true, because liveness is a dependency. Regardless, I don't feel strongly about this but will save additional refactoring for later.

pkg/kv/kvserver/replica_range_lease.go, line 613 at r3 (raw file):

Done.

pkg/kv/kvserver/replica_range_lease.go, line 871 at r4 (raw file):

Or, perhaps LeaseStatus.Lease should be a pointer. It's nice to make it non-nullable in the proto, but there's no good reason why LeaseStatus is even a proto. If it wasn't a proto, then the leases in it would probably always be on the heap anyway - and we might save some copying. No?

I looked into this and I think the issue is that we don't have any guarantee that the reference (r.mu.state.Lease) won't change once we drop the replica mutex. In practice, I think this would be safe because we only ever replace the reference wholesale. But I don't want to pull on that while making the rest of this change.

pkg/kv/kvserver/replica_range_lease.go, line 930 at r5 (raw file):

Non-blocking txns will never need to write/commit more than 1s in the future. Leases are 9 seconds long and renew every 4.5 seconds, as does node liveness. So we should be good here.

pkg/kv/kvserver/replica_range_lease.go, line 942 at r5 (raw file):

This change is made in #59086. I'll leave this as-is for now.

pkg/kv/kvserver/store_snapshot.go, line 669 at r3 (raw file):

Done.

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 24 at r1 (raw file):

See discussion above.

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 29 at r1 (raw file):

Done.

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 70 at r1 (raw file):

Yes, done.

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 78 at r2 (raw file):

Done.

Yeah, we should clean this up. It's likely too hard to remove the .Timestamp field completely (what about all of those non-transactional requests like QueryTxn, Increment, etc?) in the short term, but at the very least we should be forwarding it to the write timestamp to avoid the issues you pointed out.
It's always bothered me that too many timestamps were floating around in the lower levels of KV - txn read timestamp, txn write timestamp, batch.Timestamp - perhaps we can avoid any direct access to these timestamps and instead use .ReadTimestamp(), .WriteTimestamp() getters that can coalesce from these three sources. Not sure, I haven't looked at these code paths in a while.

Reviewed 73 of 73 files at r8, 63 of 63 files at r9, 14 of 14 files at r10, 5 of 5 files at r11, 4 of 4 files at r12, 2 of 2 files at r13, 3 of 3 files at r14.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @andreimatei, @nvanbenschoten, and @tbg)

pkg/kv/kvserver/replica_range_lease.go, line 562 at r3 (raw file):

I'd leave as is, if anything this method should eventually become standalone rather than more tightly coupled with the Replica behemoth.

pkg/kv/kvserver/replica_range_lease.go, line 529 at r14 (raw file):

// - The lease is considered valid if the current timestamp (now) is
//   covered by the supplied lease and the lease can be used to serve a
//   request at the specified time. This is determined differently

I'm still not convinced by the structure of this comment and the notion of "validity". There are really two questions we ask about leases:

1. can I safely request a non-cooperative lease following the current lease? This is linked to the (lease or epoch) expiration and the now timestamp.
2. can the lease serve an operation at timestamp T? The answer is no if the lease has been relinquished at a timestamp >= T (minProposedTS, i.e. lease transfer or a restart), or if T >= stasis.

You didn't bite at my suggestion to rename VALID, but can I coax you into consistently upper-casing the enum variants in the comments to avoid confusion?

Strawman comment rewrite from my input above:

The lease status is linked to the desire to serve a request at a specific timestamp (which may be a future timestamp) under the lease, as well as a notion of the current hlc time (now).

A status of ERROR indicates a failure to determine the correct lease status, and should not occur under normal operations. The caller's only recourse is to give up or to retry.

If the lease is expired according to the now timestamp (and, in the case of epoch-based leases, the epoch), a status of EXPIRED is returned. Note that this ignores the timestamp of the request, which may well technically be eligible to be served under the lease. The key feature of an EXPIRED status is that it reflects that a new lease with a start timestamp greater than or equal to now can be acquired non-cooperatively.

If the lease is not EXPIRED, the request timestamp is taken into account. The expiration timestamp is adjusted for clock offset; if the request timestamp falls into the so-called stasis period at the end of the lifetime of the lease, the status is UNUSABLE, which callers typically want to react to by extending the lease, if they are in a position to do so.

Finally, for request timestamps falling before the stasis period, the request timestamp is additionally checked against the minProposedTimestamp. This timestamp determines the earliest timestamp the lease can be used for, and is set both in cooperative lease transfers and to prevent reuse of leases across node restarts (which would result in latching violations). Requests preceding this timestamp are assigned a status of PROSCRIBED and should be retried at a higher timestamp, or the lease transfer target, depending on the scenario.

On the surface, ...

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 81 at r14 (raw file):

// LeaseStatus holds the lease state, the current clock time at which the
// state is accurate, the request time at which the stats is accurate, the

stats?

Yeah, we should clean this up. ...

Sounds like a plan. I'll address this in a follow-up PR.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @andreimatei and @tbg)

pkg/kv/kvserver/replica_range_lease.go, line 529 at r14 (raw file):

Done. Thanks for the strawman 😄 I just made minor modifications.

pkg/kv/kvserver/kvserverpb/lease_status.proto, line 81 at r14 (raw file):

Done.