1

Here's an interesting scenario, consider a cache with many buckets, and resources that can be shared between buckets:

Bucket Highest to lowest priority
Foo A, B, C, D
Bar B, C, D
Baz A

In the example above Foo and Bar share the resources B, C, D; Foo and Baz share A; and Bar and Baz share no resources.

Problem statement

We have two processes:

  • Inserter puts data into one or more buckets in a transaction
  • Inserter isolation level is Read-Committed
  • Deleter removes data from one or more buckets in another transaction
  • Deleter isolation level is Read-Committed, but it can be changed
  • Deleter can never remove the highest-priority resource for any bucket
    • In the example above, it cannot remove A or B
  • An external object store is used for keeping data associated to each resource

Phantom read race condition

If the Deleter checks for buckets and their state in order to decide what resources to delete, there's a chance to do a Phantom read if there's an uncommitted concurrent transaction on the Inserter side, that bumps a resource's from a lower priority into the highest priority.

Consider the following example for a single bucket:

t Inserter Deleter TX state Committed state
1 A, B, C, D
2 BEGIN (Inserter)
A, B, C, D
3 UPSERT D (Inserter)
D, A, B, C
4 Put D in external store (Inserter)
D, A, B, C
5 BEGIN (Deleter)
A, B, C, D
6 SELECT NON-LATEST (Deleter)
A, B, C, D
7 DELETE B, C, D (Deleter)
A
8 Remove B, C, D from external store (Deleter)
A
9 COMMIT A
10 COMMIT D, A

Resulting state is D, A. Which is inconsistent with our non-transactional data store because the Deleter removed D on t = 8. The phantom read occurs because our Deleter captured D which was being concurrently bumped by the Inserter.

Failed approach - Optimistic Concurrency Control (OCC)

Since the issue is the state changing while the Deleter is working, OCC helps when the Inserter commits before the Deleter:

  • Inserter BEGIN
  • Inserter Does changes...
  • Deleter BEGIN
  • Deleter Does changes...
  • Inserter COMMIT
  • Deleter OCC detects conflict on state
  • Deleter Undo changes to non-transaction store
  • Deleter ROLLBACK and try again

If the Inserter commits after the Deleter does the OCC check, the latter won't detect any conflicts.


What would be the best way to handle cases like this? From the top of my head there's a couple of stuff we can try:

  • At least in Postgres, Serializable isolation level might be helpful because it doesn't block the whole table. However, changing the isolation level of the Inserter to other than Read-Committed should be avoided; interested in knowing if there are other solutions

  • Locking the buckets each process is using seems useful at first, but that only locks existing buckets. New buckets can still cause consistency issues

  • Locking the resources we're working on (e.g. lock B, C, D) seems like a good approach, assuming there's little contention on them

  • Is there any solution that doesn't use Two-phase Locking (2PL) / Pessimistic Concurrency Control?

  • Implement a mechanism to allow for dirty-reads, that way the Inserter can mark a resources as "being-handled" in its own standalone transaction, which would become visible from the Deleter

2
  • You're showing the TX state as a list, and saying the order indicates priority. Can you provide specific detail about how the priority list is stored in the database? Seems to me that it is the ordering that needs to be locked, not the resources A, B, C.. , but how is that ordering manifest.
    – Erik Eidt
    Commented Apr 9, 2023 at 20:59
  • @ErikEidt Sorry for taking so long to reply. For the actual manifestation of the examples, think of a Buckets table a Resources table with a one-to-many relationship, the "latest" resource can be deduced from the insertion timestamp, so to get all items from a bucket you do SELECT * FROM Resources WHERE bucket_id = 123 ORDER BY created_on DESC for example.
    – danielrs
    Commented Apr 11, 2023 at 4:51

2 Answers 2

1

In PostgreSQL, all concurrency control anomalies can be handled by true serializability. It's a form of optimistic concurrency control. PostgreSQL determines whether there's a risk that one transaction steps on the foot of another, and rolls back one of the transactions due to a serialization anomaly.

Just execute:

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

and you're set. Note that in cases where a transaction steps on the foot of another, one of them is rolled back automatically. You should be expected to handle that by random exponential back-off with retry. Note that due to possibility of deadlocks, you really need a retry scheme even if you don't use SERIALIZABLE isolation level, so you already have that, right?

Other poorer database systems that lack true serializability and may only have MVCC false serializable (that's really only snapshot isolation) can't do what PostgreSQL can do.

With true serializable, it's guaranteed that there exists an ordering of transactions where executing the transactions serially (non-paralleled) in that order would create the same result as executing the transactions in parallel with your real parallel database created.

(Edit: sorry, I didn't immediately notice that there's a restriction that you can't change the isolation level to anything other than read committed. However, I believe this is an artificial restriction and you shouldn't have that -- you should explain why it's impossible to change the isolation level.)

2
  • It is possible to make the Inserter be Read-Committed but the Deleter be Serializable? While the former can be changed I'm interested in knowing if there are easier solutions than changing existing implementation paradigms.
    – danielrs
    Commented Apr 9, 2023 at 18:08
  • My understanding is that there is no point in mixing isolation levels, apart from using snapshot isolation for read-only transactions in cases where others use read committed. You should use serializable in every transaction.
    – juhist
    Commented Apr 9, 2023 at 18:09
0

I didn't quite understand all the scenario or the rationale for all the desirables mentioned, but from what I understand, the problem is that you are selecting data to make a decision, but before the transaction which results from that decision is executed, the data on which the decision depended is changed.

The answer generally is more locking. You must prevent the decision-data being altered, until the transaction caused by that decision is committed. You can either use SERIALIZABLE isolation, or you can use the HOLDLOCK hint when selecting the data which determines the decision.

Depending on the exact context, the UPDLOCK or XLOCK may also be necessary to pre-emptively (i.e. at the time of selecting the data which will determine the decision) seize a lock which will allow the transaction to complete, and to exclude any other threads from progressing in the meantime.

2
  • Your understanding is correct. There's a decision space that changes concurrently, causing the Deleter to remove wrong entries. Maybe I'm mistakenly calling this a Phantom Read? That's my understanding of what this issue is called.
    – danielrs
    Commented Apr 9, 2023 at 18:47
  • @DanielRS, I forget myself the correct lingo to describe all the so-called anomalies in SQL. It's an area where it can be difficult to make sense of all the jigsaw pieces.
    – Steve
    Commented Apr 9, 2023 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.