Lots of comments, but this is really coming out quite nicely!

Reviewed 3 of 3 files at r3, 2 of 2 files at r4, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @arulajmani)

pkg/kv/kvserver/concurrency/lock_table.go line 273 at r4 (raw file):

	// between separate concurrency.Manager instances.
	//
	// finalizedTxnCacheMu provides mutual exclusion to cache accesses. It must be

TODO: we had discussed a desire to get rid of this. It's a performance concern and also implies a subtle need for a consistent finalized txn cache snapshot across scanAndMaybeEnqueue.

pkg/kv/kvserver/concurrency/lock_table.go line 792 at r4 (raw file):

			}
			conflicts := func() bool {
				l.mu.Lock()

Closures are a bit of a clutch to avoid creating a clean, explicit abstraction around an operation. That can certainly be ok in some cases, but this feels too central to the lock table to not be given a name and an explicit set of inputs and outputs. That's especially true because we're using this to establish a critical section under l.mu. In this sense, I do think the current structure of tryActiveWait is getting it right.

pkg/kv/kvserver/concurrency/lock_table.go line 795 at r4 (raw file):

				defer l.mu.Unlock()
				if l.isEmptyLock() {
					locksToGC = append(locksToGC, l)

We had talked about getting rid of this.

pkg/kv/kvserver/concurrency/lock_table.go line 798 at r4 (raw file):

					return false
				}
				conflicts := l.scanAndMaybeEnqueue(g, notify)

nit: what is the "scan" part of this name referring to? Haven't we already scanned through the lock table and found the lock?

pkg/kv/kvserver/concurrency/lock_table.go line 799 at r4 (raw file):

				}
				conflicts := l.scanAndMaybeEnqueue(g, notify)
				// TODO(arul): It's weird that we're checking for a non-empty lock

If we get rid of the previous append to locksToGC and then address this TODO, does that let us push the locking into scanAndMaybeEnqueue and then get rid of this closure? Should we address the TODO now? Or maybe fall back to the transitionedToFree bool return value until we do address the TODO?

pkg/kv/kvserver/concurrency/lock_table.go line 1630 at r4 (raw file):

// conflict resolution with the supplied request. It may[1] enqueue the request
// in the receiver's wait queues. The return value indicates if a conflict was
// found or not. If a conflict is found, the caller is expected to suspend its

I'm not sure whether conflicts is an improvement over wait. Is conflicts well-defined? Is it clear that a enqueuer that does enqueue and immediately claims the lock is not considered to "conflict" with it? Similarly, is it clear to a caller how it is expected to behave in response to the conflicts bool?

wait also parallels lockTableGuard.ShouldWait, so it's clearer how ties together.

pkg/kv/kvserver/concurrency/lock_table.go line 1636 at r4 (raw file):

// 3 separate cases:
// 1. Transactional requests of the locking nature are always enqueued.
// 2.Transactional requests that are non-locking are only enqueued if there is a

nit: missing space

pkg/kv/kvserver/concurrency/lock_table.go line 1690 at r4 (raw file):

		// If that is the case, we designate this request to be such.
		if l.distinguishedWaiter == nil {
			l.distinguishedWaiter = g

Does this allow a waitSelf waiter to also become the distinguishedWaiter?

pkg/kv/kvserver/concurrency/lock_table.go line 1731 at r4 (raw file):

	if finalizedTxn != nil {
		// Clean up the lock before proceeding.
		// TODO(arul): Instead of this special casing for unreplicated locks, we

This TODO is actually suggesting something different than I had thought. I thought the idea was to immediately call clearLockHolder and lockIsFree to clean up the lock holder, but then to also enqueue on the lock even if it became free. That way we don't need to have the awkward transitionedToFree transition, but we also don't lose the claim.

Are there benefits to one approach over the other?

Also, I mentioned this above, but I'll ask here as well. This case seems quite awkward and it's kind of getting in your way. Would things be easier if we just addressed this TODO now (either as a preceding commit or PR) and then made the rest of this change?

pkg/kv/kvserver/concurrency/lock_table.go line 1794 at r4 (raw file):

//
// REQUIRES: l.mu to be locked.
func (l *lockState) alreadyHoldsLockAndIsAllowedToProceed(g *lockTableGuardImpl) bool {

We had talked about adjusting the wait-queue ordering so that this case acquires a claim on the lock, right? That's a change you'd want to make in a future PR? Doing so SGTM.

pkg/kv/kvserver/concurrency/lock_table.go line 1829 at r4 (raw file):

		return false // the lock isn't held; no conflict to speak of
	}
	assert(!g.isSameTxn(lockHolderTxn), "lock already held by the request's transaction")

Could you add a comment explaining that this has already been checked?

pkg/kv/kvserver/concurrency/lock_table.go line 1862 at r4 (raw file):

			// correctness issue in doing so.
			//
			// TODO(arul): I'm not entirely sure I understand why we have the

I'm also not sure. Looking forward to seeing what you find.

pkg/kv/kvserver/concurrency/lock_table.go line 1874 at r4 (raw file):

	// for conflicts.
	var reqMode lock.Mode
	switch g.curStrength() {

Should we add a g.getLockMode() method that we can use here and during the iteration in shouldRequestActivelyWait?

pkg/kv/kvserver/concurrency/lock_table.go line 1891 at r4 (raw file):

//
// REQUIRES: l.mu to be locked.
func (l *lockState) maybeEnqueueRequest(g *lockTableGuardImpl) error {

We discussed changing the signature of this function to return (ok, lengthExceeded bool).

pkg/kv/kvserver/concurrency/lock_table.go line 1892 at r4 (raw file):

// REQUIRES: l.mu to be locked.
func (l *lockState) maybeEnqueueRequest(g *lockTableGuardImpl) error {
	switch g.curStrength() {

Should this be if g.curStrength() == lock.None { ... } else { ... } for the same reason as the discussion in #103267 (review)? The choice of which queue to use should be locking strength agnostic, right?

pkg/kv/kvserver/concurrency/lock_table.go line 1912 at r4 (raw file):

	assert(g.curStrength() == lock.None, "unexpected locking strength; expected read")
	if !l.conflictsWithLockHolder(g) {
		return // no conflit, no need to enqueue

"conflict"

pkg/kv/kvserver/concurrency/lock_table.go line 1917 at r4 (raw file):

}

// enqueueNonLockingReader enqueues the supplied non-locking request in the

It feels like this function could be inlined to avoid the repeated assertion, but I don't feel strongly.

pkg/kv/kvserver/concurrency/lock_table.go line 1999 at r4 (raw file):

	}

	if g.curStrength() == lock.None {

If we do return an "enqueued" bool from maybeEnqueueRequest, we'll want to move this check above conflictsWithLockHolder and have it return true. // Non-locking read requests always actively wait.

pkg/kv/kvserver/concurrency/lock_table.go line 2005 at r4 (raw file):

	}

	// Iterate through the head of the queue until we find the request. As we

s/Iterate through the head of the queue/Start at the front of the queue and iterate backwards/

pkg/kv/kvserver/concurrency/lock_table.go line 2008 at r4 (raw file):

of the requests

Of the other requests?

pkg/kv/kvserver/concurrency/lock_table.go line 2033 at r4 (raw file):

		}
	}
	panic("lock table bug")

nit: mind using this as a comment to explain why it's a bug? Something like panic("lock table bug: did not find enqueued request")

pkg/kv/kvserver/concurrency/lock_table.go line 2047 at r4 (raw file):

// REQUIRES: l.mu to be locked.
func (l *lockState) maybeClaimBeforeProceeding(g *lockTableGuardImpl) {
	if g.curStrength() == lock.None {

This check feels out of place here. Can we scope this method to locking requests? I believe a few of the comments above outline a path to get there.

pkg/kv/kvserver/concurrency/lock_table.go line 2073 at r4 (raw file):

		if qqg.guard == g {
			if g.txn == nil {
				// NB: Before calling into removeWriter, we override the active

This all leads me to think that removeWriter is not what you want to be calling here, and should instead just call l.queuedWriters.Remove(e). removeWriter has a few assumptions that it is being called on behalf of another request.

Also, separately, why does removeWriter only check if g == l.distinguishedWaiter if qg.active. Is that assuming that the first condition implies the second? Do we need to tie the conditions together?

Thanks for the detailed reviews on this and accompanying PRs. RFAL.

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

pkg/kv/kvserver/concurrency/lock_table.go line 273 at r4 (raw file):

Got rid of it by pushing the use of this cache in just one place.

pkg/kv/kvserver/concurrency/lock_table.go line 792 at r4 (raw file):

We no longer need this now that we've landed #104782 and we no longer have locksToGC as a thing.

pkg/kv/kvserver/concurrency/lock_table.go line 795 at r4 (raw file):

Done.

pkg/kv/kvserver/concurrency/lock_table.go line 798 at r4 (raw file):

Yeah, but I was imagining there could be more than 1 locks on this key (once we have shared locks). So we would still be scanning through more than 1 locks in this method.

pkg/kv/kvserver/concurrency/lock_table.go line 799 at r4 (raw file):

Yup, like you noted, the closure goes away post #104782.

pkg/kv/kvserver/concurrency/lock_table.go line 1630 at r4 (raw file):

Ack, switched to wait instead and fixed up the commentary here.

pkg/kv/kvserver/concurrency/lock_table.go line 1690 at r4 (raw file):

Fixed

pkg/kv/kvserver/concurrency/lock_table.go line 1731 at r4 (raw file):

We spoke about this offline and landed #104782.

pkg/kv/kvserver/concurrency/lock_table.go line 1794 at r4 (raw file):

Yeah

pkg/kv/kvserver/concurrency/lock_table.go line 1874 at r4 (raw file):

Done; I named to curLockMode for the same mutability reasons we called it g.curStrength().

pkg/kv/kvserver/concurrency/lock_table.go line 1891 at r4 (raw file):

I implemented our original idea first, but after seeing how it looked, I ended up getting rid of this function entirely and moving the switch[1] into scanAndMaybeEnqueue. IMO, this is a bit easier to understand, but let me know if you disagree and I can switch back to the old thing.

[1] rewrote the switch as an if-else given the comment below.

pkg/kv/kvserver/concurrency/lock_table.go line 1892 at r4 (raw file):

Done.

pkg/kv/kvserver/concurrency/lock_table.go line 1917 at r4 (raw file):

Yeah, it's a one-liner with unnecessary assertions given the call path -- inlined it.

pkg/kv/kvserver/concurrency/lock_table.go line 1999 at r4 (raw file):

Another alternative here would be to never even call into this function for non-locking reads (and assert this here). Instead, we could handle non-locking reads at the caller (the structure of which dictates why non-locking reads have to always actively wait).

I don't have a strong preference either way. I keep going back and forth between wanting to treat non-locking reads as a completely separate thing in scanAndMaybeEnqueue (right up top, before any non-locking requests' handling) and the current structure. For now, I've implemented your suggestion.

pkg/kv/kvserver/concurrency/lock_table.go line 2008 at r4 (raw file):

Yeah; fixed.

pkg/kv/kvserver/concurrency/lock_table.go line 2047 at r4 (raw file):

Done; added an assertion.

pkg/kv/kvserver/concurrency/lock_table.go line 2073 at r4 (raw file):

Like we talked about offline last week, I've added an assertion here.

pkg/kv/kvserver/concurrency/lock_table.go line 1699 at r5 (raw file):

	if g.curStrength() == lock.None {
		conflicts := l.maybeEnqueueNonLockingReadRequest(g)

@nvanbenschoten like I mentioned below, an alternative is to handle the conflicts case here as well. We could pull out the datastructure changes in the shouldRequestActivelyWait block into its own function, call into that, and return early.

That allows us to completely handle non-locking readers, and say everything below only applies to locking requests. It's another round of reviews, but I think that's a bit cleaner. I can make the change if you feel similarly -- no strong feelings from me, either way.

This feels like it's getting close. At this point, I think it's just a bit of polish.

Reviewed 1 of 1 files at r6, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @arulajmani)

pkg/kv/kvserver/concurrency/lock_table.go line 1699 at r5 (raw file):

I think I like what you're suggesting. It means that we handle the non-locking request logic separately from the locking logic and don't try to mix them. The more we iterate on this, the more we're finding that it's easiest to just split these cases early on. So the change SGTM.

EDIT: if we address the two comments following this one, we may also be able to handle the waitQueueMaxLengthExceeded case with this same function. I'm imagining that it would be a function with a signature like func (g *lockTableGuardImpl) startWaitWithWaitingState(state waitingState, notify bool). Note that the g.key could be pulled from the waitingState to avoid the additional parameter.

pkg/kv/kvserver/concurrency/lock_table.go line 1682 at r6 (raw file):

// on them. However, they must be resolved before the request can evaluate. The
// guard's state is modified to indicate if there are locks that need
// resolution.

Do you want to update this comment to reflect the updated condition now that #104784 has landed?

pkg/kv/kvserver/concurrency/lock_table.go line 1730 at r6 (raw file):

		g.mu.startWait = true
		g.mu.curLockWaitStart = g.lt.clock.PhysicalTime()
		// This may be the first request to actively start waiting in the receiver's

This logic feels distinct from the logic to update the lockTableGuardImpl. It's closer to the manipulation of the lockWaitQueue state when enqueueing requests, so I wonder if it's in the wrong place.

Did you consider pulling out a small helper like func (l *lockState) maybeMakeDistinguishedWaiter(g *lockTableGuardImpl) and then calling this from maybeEnqueueNonLockingReadRequest and enqueueLockingRequest?

pkg/kv/kvserver/concurrency/lock_table.go line 1743 at r6 (raw file):

		ws := l.constructWaitingState(g)
		g.maybeUpdateWaitingStateLocked(ws, notify)
		g.mu.locks[l] = struct{}{}

We are already doing this in enqueueLockingRequest. Is it just missing from maybeEnqueueNonLockingReadRequest?

pkg/kv/kvserver/concurrency/lock_table.go line 1950 at r6 (raw file):

//
// REQUIRES: l.mu to be locked.
// REQUIRES: g.mu to be locked.

Is g.mu locked when calling this? Am I missing that? FWIW, the locking around lockTableGuardImpl is funky, but it doesn't seem like g.mu.locks needs to be mutated under lock, given that it's internal to the lock table.

pkg/kv/kvserver/concurrency/lock_table.go line 1977 at r6 (raw file):

		// would be more fair, but more complicated, and we expect that the
		// common case is that this waiter will be at the end of the queue.
		return true

nit: return true /* maxQueueLengthExceeded */

pkg/kv/kvserver/concurrency/lock_table.go line 1998 at r6 (raw file):

	}
	g.mu.locks[l] = struct{}{}
	return false

nit: return false /* maxQueueLengthExceeded */

RFAL.

First commit from #105562

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

pkg/kv/kvserver/concurrency/lock_table.go line 1699 at r5 (raw file):

Made the change. I quite like how it turned out, especially with the suggestion to call startWaitingWithWaitingState in the waitQueueMaxLengthExceeded case as well.

pkg/kv/kvserver/concurrency/lock_table.go line 1682 at r6 (raw file):

Good call; done.

pkg/kv/kvserver/concurrency/lock_table.go line 1730 at r6 (raw file):

That's a good idea, done. We also need to clear out this distinction in maybeClaimBeforeProceeding. Interestingly, making these changes uncovered a minor bug where an inactive waiter could be a distinguished waiter (fixed separately in #105562).

pkg/kv/kvserver/concurrency/lock_table.go line 1743 at r6 (raw file):

Yeah; moved this to maybeEnqueueNonLockingReadRequest -- that's the right place for this.

pkg/kv/kvserver/concurrency/lock_table.go line 1950 at r6 (raw file):
It wasn't, thanks for catching. Likely a result of moving some code around, there's been a lot of churn here 😅

but it doesn't seem like g.mu.locks needs to be mutated under lock, given that it's internal to the lock table.

I don't fully follow -- I thought we need this because g.mu.locks can be mutated by both the request itself and other requests being sequence through the lock table. It's not directly related to this patch, but could you say more about why we don't need locking here?

Reviewed 1 of 3 files at r7, 1 of 2 files at r8, 1 of 1 files at r9, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @arulajmani)

pkg/kv/kvserver/concurrency/lock_table.go line 1950 at r6 (raw file):

I thought we need this because g.mu.locks can be mutated by both the request itself and other requests being sequence through the lock table.

Yeah, I think you're right about this. Ignore me.

pkg/kv/kvserver/concurrency/lock_table.go line 767 at r9 (raw file):

}

// startWaitingWithWaitingState modifies state on the request's guard to let it

nit: consider moving this method closer to maybeUpdateWaitingStateLocked and updateWaitingStateLocked to keep related methods grouped together.

pkg/kv/kvserver/concurrency/lock_table.go line 2134 at r9 (raw file):

				l.queuedWriters.Remove(e)
			}
			qqg.active = false // claim the lock

nit: should we put this in an else branch?

TFTRs!

bors r=nvanbenschoten

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