Phantom read race condition keeping RDBMS in sync with external storage

Question

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

Answer 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.)

Answer 2

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.