kv: Scans with limit scan too much of lockTable

[nvanbenschoten]

This is analogous to #9521, but for the lockTable.

Now that the lockTable is scanned ahead of evaluation, limited scans observe locks over their entire key range instead of just up to the point where they hit their limit. This can artificially increase contention in much the same way it does in #9521. The difference is that in #9521, limited scans will wait excessively long for artificially contending operations to complete. In this issue, limited scans will wait excessively long for the entire transaction that issued the artificially contending operations to complete.

The design of the lockTable took this into consideration, though we haven't implemented a solution for this issue yet. Namely, the lockTable is built using an immutable btree which supports O(1) snapshots in the same way the the latchManager does. The point of this is 1) to be able to scan the lockTable incrementally once we introduce a lockAwareIterator and 2) to potentially do exactly what we're doing in #33373 and push that prototype over the finish line. #33373 evaluate limited scans optimistically without latching until after the fact, when it has determined the full bounds of the scan. The ability to snapshot the lockTable means that we could do the same thing there.

The saving grace for v20.1 is that most intents don't actually end up in the lockTable because replicated locks are only pulled into the lockTable when they are discovered in the MVCC keyspace. This means that in most cases, this is a non-issue under low to moderate contention. However, it can become an issue under either high contention or when unreplicated locks are used heavily. A patch I'm about to push will mitigate the latter concern.

[sumeerbhola]

This is relevant for the separated lock table prototype that I am working on. So I'd like to clarify the approach and correctness.
There are two options:

• Check for conflicting locks during optimistic request evaluation: To keep the simplifications in mvcc.go regarding not knowing about intents and locks, one could have a special optimistic iterator that the code in mvcc.go is oblivious to, and the iterator would declare an error when encountering a lock conflict. This would cause an early failure so is potentially better than checking after the fact, but it is potentially more complicated.
• Check for conflicting locks after optimistic request evaluation.

Do you have a preference?

Correctness: lockState holds mutable information, unlike latch. So we can't tell if conflicted with a lock since it may have changed. But it seems latching saves us.

• latching will prevent other requests from starting after read request R has placed its latches in AcquireOptimistic. So the interesting ones are:
  • Other requests that have started before R but have not yet acquired/released locks. But we will see these when we do the latch check after optimistic evaluation, so they are not a concern.
  • Other requests that have completed and hold a lock. No other request can start after R starts that will change those locks.
• Concurrent releases of unreplicated locks aren't actually harmful since that conflict is gone. But concurrent releases of replicated locks are harmful since they can change a provisional value to a committed value. Neither can happen, so we will see previously acquired locks when doing the consistency check after evaluation.

Does this sound right?

[nvanbenschoten]

Do you have a preference?

I think I prefer the first option for two reasons:

1. it avoids useless work in the case that we do hit a conflicting lock, allowing us to fail earlier
2. it lets us get around answering the question of what we return from the iterator in the case that we hit a lock. For option 2, do we pretend the lock + its provisional value aren't there? Do we pretend they are already committed? This is important because mvcc.go may bail early if it detects certain logical invariant violations. For instance, Something like a CPut will return a ConditionFailedError in some cases, so we'd need to catch those and potentially swallow them after checking for conflicting locks if we went with option 2.

Does this sound right?

I had to go back and remind myself that AcquireOptimistic does, in-fact, place latches that block out other requests, it just doesn't wait on existing latches to start with. Given that, I agree with your reasoning.

Your point about concurrent releases of replicated locks being harmful because of the adjusted provisional value in interesting. We ideally want to get to a point where we can perform intent resolution without acquiring latches through the use of some indirection in an intentAwareIterator. I don't think that's in conflict with what we're discussing here. But to ensure correctness, we need to ensure that if the iterator returns the value for a pre-resolution value, the lock-table check cannot return the post-resolution lock state. The other three orderings (pre-resolution => old lock-table, post-resolution => old lock-table, post-resolution => new lock-table) are all valid.

So in that sense, I think the first option you listed above might make it easier to guarantee this, because we can enforce the invariant at a single atomicity point (during iteration) instead of trying to coordinate between what the iterator returns and what we later see in the lock table when we perform the optimistic conflict check. In other words, option 1 still ensures that we check the lock-table for a given key before ever observing the corresponding MVCC state, it just does so dynamically while scanning instead of upfront like we do today. Option 2 inverts the order of these two operations, which I suspect will lead to complexity here.

Does that line up with your thinking?

[sumeerbhola]

For instance, Something like a CPut will return a ConditionFailedError in some cases, so we'd need to catch those and potentially swallow them after checking for conflicting locks if we went with option 2.

That makes sense. Option 1 it is.

But to ensure correctness, we need to ensure that if the iterator returns the value for a pre-resolution value, the lock-table check cannot return the post-resolution lock state. The other three orderings (pre-resolution => old lock-table, post-resolution => old lock-table, post-resolution => new lock-table) are all valid.
So in that sense, I think the first option you listed above might make it easier to guarantee this, because we can enforce the invariant at a single atomicity point (during iteration) instead of trying to coordinate between what the iterator returns and what we later see in the lock table when we perform the optimistic conflict check.

I wasn't thinking about intent resolution without latches -- I'll keep it in mind. Since we will create the storage.Iterator in the lockTable before any optimistic evaluation, it should be easy to ensure that concurrently resolved intents are noticed when doing the check if we happened to do option 2.
For request evaluation in option 1 we'll need to order the creation of the storage.Iterator such that the one on the lock table key space is created before the one on the MVCC key space (since we don't want to create snapshots for request evaluation) so that we don't see a provisional value and not see the MVCCMetadata. Seeing the MVCCMetadata without the provisional value is fine since either the MVCCMetadata has a timestamp above this read and we were going to ignore the provisional value (and resolution will keep that invariant), or it is below this read in which case we are going to immediately exit this optimistic evaluation without trying to look for the missing provisional value.

[nvanbenschoten]

For request evaluation in option 1 we'll need to order the creation of the storage.Iterator such that the one on the lock table key space is created before the one on the MVCC key space.

Yes, we'll need to ensure this for the reasons you listed. I think that's how things would naturally be ordered, anyway, so we shouldn't have to do anything special here.