kv: implement ranged locks for unreplicated locks

[ajwerner]

Is your feature request related to a problem? Please describe.

As of 20.1, read requests can acquire unreplicated locks to support SELECT FOR UPDATE. In the case of ScanRequest and ReverseScanRequest these locks acquire point locks on every row read. Such point locks do not prevent new rows from being inserted and invalidating the read upon refresh. Ranged locks would block the writing of new rows within the span that had been read.

Describe the solution you'd like

I'd like to see a bit that could be set on the ScanRequest and ReverseScanRequest which would enable the acquired locks to be ranged rather than point.

Additional context

See #49684 (comment).

If I understand correctly, postgres and many other relational databases do not acquire ranged locks for SELECT FOR UPDATE. I anticipate the reason is that these databases are generally operated using lower then SERIALIZABLE isolation levels where such inserts are not problematic.

It's an open question as to whether we'd want to default to using ranged locks in that context. They will certainly be valuable in supporting #52768 which is an important add-on to #55047.

This issue also relates to #49684 as acquiring exclusive ranged locks will lead to a worse user experience without obvious benefit.

Jira issue: CRDB-3618

[blathers-crl]

Hi @ajwerner, I've guessed the C-ategory of your issue and suitably labeled it. Please re-label if inaccurate.

While you're here, please consider adding an A- label to help keep our repository tidy.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[sumeerbhola]

I'd like to see a bit that could be set on the ScanRequest and ReverseScanRequest which would enable the acquired locks to be ranged rather than point.

What is a workload for which we expect to see a benefit from this?
And is there a particular strength that is most useful?

[ajwerner]

What is a workload for which we expect to see a benefit from this?

It's not immediately obvious that we'd even want to enable this in any workload up-front as it does differ from postgres semantics. I'd anticipate if we did enable it by default to use ranged locks with select for update, then a workload which runs a whole-table UPDATE <table> SET <column> = ... concurrently with inserts to the that table would see a major improvement. I imagine there ways to exacerbate the impact by, say, putting the UPDATE in an explicit transaction which is slow.

The primary motivation is the ability for transactional schema changes to hold off invalidating writes.

And is there a particular strength that is most useful?

I think that UPGRADE would be the most useful.

[andreimatei]

One thing that @ajwerner and I were discussing is the fact that unreplicated range locks would not only increase the chance of some refreshes succeeding (touched on in #52768), but also could make large refreshes an O(1) operation in the case when the lock is still in memory at refresh time.

[ajwerner]

It seems like if we wanted the ranged locks to be durable, we might be able to leverage the work in cockroachdb/pebble#1339.

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
10 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!