Re: SSI rw-conflicts and 2PC

On 14.02.2012 04:57, Dan Ports wrote:
> Looking over the SSI 2PC code recently, I noticed that I overlooked a
> case that could lead to non-serializable behavior after a crash.
>
> When we PREPARE a serializable transaction, we store part of the
> SERIALIZABLEXACT in the statefile (in addition to the list of SIREAD
> locks). One of the pieces of information we record is whether the
> transaction had any conflicts in or out. The problem is that that can
> change if a new conflict occurs after the transaction has prepared.
>
> Here's an example of the problem (based on the receipt-report test):
>
> -- Setup
> CREATE TABLE ctl (k text NOT NULL PRIMARY KEY, deposit_date date NOT NULL);
> INSERT INTO ctl VALUES ('receipt', DATE '2008-12-22');
> CREATE TABLE receipt (receipt_no int NOT NULL PRIMARY KEY, deposit_date date NOT NULL, amount numeric(13,2));
>
> -- T2
> BEGIN ISOLATION LEVEL SERIALIZABLE;
> INSERT INTO receipt VALUES (3, (SELECT deposit_date FROM ctl WHERE k = 'receipt'), 4.00);
> PREPARE TRANSACTION 't2';
>
> -- T3
> BEGIN ISOLATION LEVEL SERIALIZABLE;
> UPDATE ctl SET deposit_date = DATE '2008-12-23' WHERE k = 'receipt';
> COMMIT;
>
> -- T1
> BEGIN ISOLATION LEVEL SERIALIZABLE;
> SELECT * FROM ctl WHERE k = 'receipt';
> SELECT * FROM receipt WHERE deposit_date = DATE '2008-12-22';
> COMMIT;
>
> Running this sequence of transactions normally, T1 will be rolled back
> because of the pattern of conflicts T1 ->  T2 ->  T3, as we'd expect. This
> should still be true even if we restart the database before executing
> the last transaction -- but it's not. The problem is that, when T2
> prepared, it had no conflicts, so we recorded that in the statefile.
> The T2 ->  T3 conflict happened later, so we didn't know about it during
> recovery.
>
> I discussed this a bit with Kevin and we agreed that this is important
> to fix, since it's a false negative that violates serializability. The
> question is how to fix it. There are a couple of options...
>
> The easiest answer would be to just treat every prepared transaction
> found during recovery as though it had a conflict in and out. This
> is roughly a one-line change, and it's certainly safe.But the
> downside is that this is pretty restrictive: after recovery, we'd
> have to abort any serializable transaction that tries to read
> anything that a prepared transaction wrote, or modify anything that
> it read, until that transaction is either committed or rolled back.

+1 for this solution.

> To do better than that, we want to know accurately whether the prepared
> transaction had a conflict with a transaction that prepared or
> committed before the crash. We could do this if we had a way to append
> a record to the 2PC statefile of an already-prepared transaction --
> then we'd just add a new record indicating the conflict. Of course, we
> don't have a way to do that. It'd be tricky to add support for this,
> since it has to be crash-safe, so the question is whether the improved
> precision justifies the complexity it would require.

Not worth the complexity, IMO.

Perhaps it would be simpler to add the extra information to the commit 
records of the transactions that commit after the first transaction is 
prepared. In the commit record, you would include a list of prepared 
transactions that this transaction conflicted with. During recovery, you 
would collect those lists in memory, and use them at the end of recovery 
to flag the conflicts in prepared transactions that are still in 
prepared state.

> A third option is to observe that the only conflicts *in* that
> matter from a recovered prepared transaction are from other prepared
> transactions. So we could have prepared transactions include in
> their statefile the xids of any prepared transactions they conflicted
> with at prepare time, and match them up during recovery to
> reconstruct the graph. This is a middle ground between the other two
> options. It doesn't require modifying the statefile after prepare.
> However, conflicts *out* to non-prepared transactions do matter, and
> this doesn't record those, so we'd have to do the conservative thing
> -- which means that after recovery, no one can read anything a
> prepared transaction wrote.

This would be fairly simple to do, but I'm not sure it's worth it, 
either. The nasty thing about this is whole thing is precisely that 
no-one can read anything the prepared transaction wrote, so making the 
conflict-in bookkeeping more accurate doesn't seem very helpful.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com