[YSQL] Support wait-on-conflict concurrency control

[rkarthik007]

Jira Link: DB-1529

In many scenarios, wait-on-conflict behavior is desirable, wherein the DB will wait for existing transactions (that might otherwise conflict) to complete before making progress.

Wait-on-conflict semantics are already part of READ COMMITTED isolation level. This is done via internal statement retries (in the query layer) with exponential backoff when a transaction detects conflicting transactions. A wait-queue based implementation will ensure lower latencies and be more resource efficient since it would eliminate statement retries.

Also, the wait queue based implementation should be agnostic to the isolation level i.e., it will allow wait-on-conflict semantics for all isolation levels.

Design doc - https://docs.google.com/document/d/1DCg4FjGlYZNBBIPcADk7z2B2TGznNHWtr8hU-0dUXyo/edit

Tracking Project: https://github.com/yugabyte/yugabyte-db/projects/67

TODO: Convert this doc to a .md file once the implementation has been completed.

Functional requirements

• [YSQL] Implement wait queue infrastructure for Wait-on-Conflict concurrency control #9589
• [YSQL] Implement distributed deadlock detection #9590
• [DST] Unblock transactions waiting on operations from rolled-back subtransactions #13590
• [dst] Improve test coverage of Wait-on-Conflict concurrency control with tablet splitting #13582
• [dst] Fix wait_queue handling of single tablet transactions #14014
• [dst] Improve metrics collection related-to Wait-on-Conflict concurrency control #13584
• [docs] Update documentation for Wait-on-Conflict concurrency control #13894
• [YSQL] Integrate READ COMMITTED isolation with wait queue based Wait-on-Conflict concurrency control to detect deadlocks and for higher performance #13211
• [docdb] Support transaction promotion for geo-partitioned workloads in use of WaitQueue and DeadlockDetector in Wait-on-Conflict concurrency control #13585

Nice-to-have

• [dst] Delay start of deadlock detection for a configurable amount of time #13576
• [dst] Avoid conflict resolution if waiting transaction is unblocked from unresolvable conflict #13577
• [dst] Prefer push-based mechanism for signaling waiting transactions #13578
• [dst] Improve tail-latency for operations of transactions using wait queues #13580
• [DocDb] Optimize deadlock detection to detect conflicts local to tserver when present #13586
• [YSQL] Throw the same error message as Pg when a deadlock is detected #14114
• [DocDB] Rollback only the youngest deadlocked transaction needed to make progress #14165
• [DocDB] Handle rolling restart situations when the gflag enable_wait_queues is modified #14935

[triump2020]

@rkarthik007 Have a plan or scheme to support pessimistic locking ?

[jaki]

Simple test:

CREATE TABLE t (i int);
INSERT INTO t VALUES (1);

bin/psql   --command 'update t set i = 2' & bin/psql   --command 'update t set i = 3' # both succeed
bin/ysqlsh --command 'update t set i = 2' & bin/ysqlsh --command 'update t set i = 3' # one fails

[salarali]

What is the expected timeline for this feature to be implemented? Is it still supposed to be shipped in April with 2.7 release?

We really need this feature in place, before trying out yugabyte.

[bmatican]

hey @salarali , thanks for the interest in Yugabyte!

can you describe a bit your use case, to better understand why this is a blocker for you? cc @rkarthik007

[salarali]

Thanks for the quick reply.

We have two applications that are touching the same record at the same time. We want the first transaction to finish and then handle the second transaction.

[bmatican]

@salarali is this a relatively isolated transaction, that you could retry from the client side? say, if you knew that the error code you got on the client was specifically a conflict?

we've actually not seen this be a significant blocker, so would really like to understand better if there's some easy workaround you could be ok with, to still try out Yugabyte, or if there's something more fundamental, that could be great feedback for us and the product

[salarali]

Yes, it is a relatively isolated transaction and we could retry from the client side after looking at the error code from the client.

Unfortunately, updating our code to support retries would require some engineering effort to update the pipelines.

[kulminaator]

as agreed on the yugabyte slack i will duplicate the text here so it is marked down.

while trying to port over an existing application that runs on postgresql i run into the issue that i need the pessimistic locking to be supported in order to avoid rewriting the whole application.

i will describe a few scenarios here:

Example on the select for update use case: i have to guarantee that a customer X does not get more than 3 subscriptions in activate state on his/her name. As uncommited transactions do not see each other's data what i do currently with postgres to guarantee this: i have separate tables for customers and subscriptions, when ever i do a status change on any of the subscriptions i at first grab the consumer's record lock with select for update (with no real intention to update it at all, just to lock it), do my operations & checks on the other records as necessary, release the lock with commit at transaction end. By doing this my application layer can remain very simple and very understandable to developers, and since i don't have a programmatic pattern to access subscriptions without the lock i do not have to lock or worry about locks on any of the subscription records. I also don't have to retry possible complex computations over and over again.

Another example on the parallel updates to the same record, postgresql has atomic increment support which is very useful for rapid parallel updates of numbers in records

whatever=# create table increment_test(any_number int);
CREATE TABLE
whatever=# insert into increment_test values(1);
INSERT 0 1

now when i have a small script like this (pg_sleep added for ease of testing)

begin;
update increment_test set any_number = any_number + 1;
select pg_sleep(5);
commit;

when thes update scripts are executed in parallel on postgresql, numbers get incremented by all script instances that were run (e.g. 2 parallel executions wait for each other due to row being locked by update and the result after 2 increments is 3). when i execute the script with a parallelism of 2 on yugabytedb i get the 40001 error on one of the transactions and i would have to retry this myself. not an issue if i do it on one record and seldom, but a huge problem if you run this at big concurrency against a small set of records, i could be almost stuck in a while loop for retries from the application side.

i am sure more compatibility with postgresql behavior would be a huge factor to win over customers from postgresql.

[RunningJon]

Supporting READ COMMITTED (PostgreSQL default) has also been a request so that existing applications have an easier time migrating from PostgreSQL to Yugabyte.

[pkj415]

@salarali @kulminaator in your use cases, what isolation level are you using?

[dbuenor]

@salarali @kulminaator in your use cases, what isolation level are you using?

Sorry for taking part in it, but in our case, we usually use READ COMMITED (Postgres default) like @RunningJon said before

[robertsami]

FYI -- we have moved towards the nomenclature of "wait-on-conflict" (FKA pessimistic locking) vs. "fail-on-conflict" (FKA optimistic locking). Issue details have been updated accordingly

[rthallamko3]

Closing this as we are using the board https://github.com/orgs/yugabyte/projects/19 to track the open items. All the necessary items have landed. cc @robertsami