Re: Question about SSI, subxacts, and aborted read-only xacts

This question comes about after reading the VLDB paper "Serializable
Snapshot Isolation in PostgreSQL".

We release predicate locks after a transaction abort, but not after a
subtransaction abort. The paper says that the reason is:

"We do not drop SIREAD locks acquired during a subtransaction if the
subtransaction is aborted (i.e. all SIREAD locks belong to the top-level
transaction). This is because data read during the subtransaction may
have been reported to the user or otherwise externalized." (section
7.3).

But that doesn't make sense to me, because that reasoning would also
apply to top-level transactions that are aborted, but we release the
SIREAD locks for those.

In other words, this introduces an inconsistency between:

BEGIN ISOLATION LEVEL SERIALIZABLE;
SAVEPOINT s1;
...
ROLLBACK TO s1;
COMMIT;

and:

BEGIN ISOLATION LEVEL SERIALIZABLE;
...
ROLLBACK;

I'm not suggesting this is a correctness problem: holding SIREAD locks
for longer never causes incorrect results. But it does seem a little
inconsistent.

For top-level transactions, I don't think it's possible to preserve
SIREAD locks after an abort, because we rely on aborts to alleviate
conflicts (and when using 2PC, we may need to abort a read-only
transaction to correct the situation). So it seems like users must not
rely on any answers they get from a transaction (or subtransaction)
unless it commits.

Does that make sense?

If so, I think we need a documentation update. The serializable
isolation level docs don't quite make it clear that serializability only
applies to transactions that commit. It might not be obvious to a user
that there's a difference between commit and abort for a RO transaction.
I think that, in S2PL, serializability applies even to aborted
transactions (though I haven't spent much time thinking about it), so
users accustomed to other truly-serializable implementations might be
surprised.

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> This question comes about after reading the VLDB paper
> "Serializable Snapshot Isolation in PostgreSQL".

... and I know Jeff read that quite closely because he raised a
question off-list about an error he found in it which managed to
survive the many editing and review passes that paper went through.
:-)

> We release predicate locks after a transaction abort, but not
> after a subtransaction abort. The paper says that the reason is:
>
> "We do not drop SIREAD locks acquired during a subtransaction if
> the subtransaction is aborted (i.e. all SIREAD locks belong to the
> top-level transaction). This is because data read during the
> subtransaction may have been reported to the user or otherwise
> externalized." (section 7.3).
>
> But that doesn't make sense to me, because that reasoning would
> also apply to top-level transactions that are aborted, but we
> release the SIREAD locks for those.
>
> In other words, this introduces an inconsistency between:
>
> BEGIN ISOLATION LEVEL SERIALIZABLE;
> SAVEPOINT s1;
> ...
> ROLLBACK TO s1;
> COMMIT;
>
> and:
>
> BEGIN ISOLATION LEVEL SERIALIZABLE;
> ...
> ROLLBACK;
>
> I'm not suggesting this is a correctness problem: holding SIREAD
> locks for longer never causes incorrect results. But it does seem
> a little inconsistent.
>
> For top-level transactions, I don't think it's possible to
> preserve SIREAD locks after an abort, because we rely on aborts to
> alleviate conflicts (and when using 2PC, we may need to abort a
> read-only transaction to correct the situation). So it seems like
> users must not rely on any answers they get from a transaction (or
> subtransaction) unless it commits.
>
> Does that make sense?

I think the behavior is correct because a function's control flow
might be directed by what it reads in a subtransaction, even if it
rolls back -- and the transaction as a whole might leave the
database in a different state based on that than if it had read
different data (from a later snapshot). For example, if a plpgsql
function has a BEGIN/EXCEPTION/END block, it might read something
from the database and use what it reads to attempt some write. If
that write fails and the EXCEPTION code writes something, then the
database could be put into a state which is dependent on the data
read in the subtransaction, even though that subtransaction is
rolled back without the client ever directly seeing what was read.

This strikes me as significantly different from returning some rows
to a client application and then throwing an error for the
transaction as a whole, because the client will certainly have an
opportunity to see the failure (or at worst, see a broken connection
before being notified of a successful commit).

> If so, I think we need a documentation update. The serializable
> isolation level docs don't quite make it clear that
> serializability only applies to transactions that commit. It might
> not be obvious to a user that there's a difference between commit
> and abort for a RO transaction. I think that, in S2PL,
> serializability applies even to aborted transactions (though I
> haven't spent much time thinking about it), so users accustomed to
> other truly-serializable implementations might be surprised.

That's a fair point. Do you have any suggested wording, or
suggestions for exactly where in the documentation you think it
would be most helpful? The subsection on serializable transactions
seems like the most obvious location:

http://www.postgresql.org/docs/current/interactive/transaction-iso.html#XACT-SERIALIZABLE

Does any other section seem like it needs work?

-Kevin

On Mon, 2012-09-10 at 11:15 -0500, Kevin Grittner wrote:
> ... and I know Jeff read that quite closely because he raised a
> question off-list about an error he found in it which managed to
> survive the many editing and review passes that paper went through.
> :-)

Well, I need to keep up with the discussion on the interaction of
temporal and SSI :-)

> I think the behavior is correct because a function's control flow
> might be directed by what it reads in a subtransaction, even if it
> rolls back -- and the transaction as a whole might leave the
> database in a different state based on that than if it had read
> different data (from a later snapshot). For example, if a plpgsql
> function has a BEGIN/EXCEPTION/END block, it might read something
> from the database and use what it reads to attempt some write. If
> that write fails and the EXCEPTION code writes something, then the
> database could be put into a state which is dependent on the data
> read in the subtransaction, even though that subtransaction is
> rolled back without the client ever directly seeing what was read.

On reflection, I agree with that. Trying to puzzle through your
transactions (and application logic) to see if you are depending on any
information read in an aborted subtransaction is exactly the kind of
thing SSI was meant to avoid.

> This strikes me as significantly different from returning some rows
> to a client application and then throwing an error for the
> transaction as a whole, because the client will certainly have an
> opportunity to see the failure (or at worst, see a broken connection
> before being notified of a successful commit).

Oh, I see the distinction you're making: in PL/pgSQL, the exception
mechanism involves *implicit* subtransaction rollbacks. That's more of a
language issue, but a valid point.

I'm still not sure I see a theoretical difference, but it does seem wise
to keep predicate locks for aborted subtransactions.

> > If so, I think we need a documentation update. The serializable
> > isolation level docs don't quite make it clear that
> > serializability only applies to transactions that commit. It might
> > not be obvious to a user that there's a difference between commit
> > and abort for a RO transaction. I think that, in S2PL,
> > serializability applies even to aborted transactions (though I
> > haven't spent much time thinking about it), so users accustomed to
> > other truly-serializable implementations might be surprised.
>
> That's a fair point. Do you have any suggested wording...

I'll write something up. Can I document that you may depend on the
results read in aborted subtransactions, or should I leave that
undefined for now?

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> wrote:

> Oh, I see the distinction you're making: in PL/pgSQL, the
> exception mechanism involves *implicit* subtransaction rollbacks.
> That's more of a language issue, but a valid point.

I think it holds for the general case of functions -- there's no
reason to believe that you are aware of all subtransactions within a
function or will know what was read by an aborted subtransaction
within any function. It's pretty easy to describe in plpgsql, but I
doubt the issue is specific to that language.

> I'm still not sure I see a theoretical difference, but it does
> seem wise to keep predicate locks for aborted subtransactions.

I think that if it was guaranteed that application software was
aware of all subtransactions and their completion states, there
would still be a subtle issue as long as what was read in the
subtransaction could in any way influence the behavior of subsequent
steps in the enclosing transaction (or subtransaction). In essence,
you have no reasonable way of knowing what the outer transaction
would have done had it been able to see the work of a concurrent
transaction, so you can't know whether the behavior of a set of
transactions is the same as it would have been had they run
one-at-a-time. A really stringent analysis of the logic of the code
might be able to answer that for some cases (maybe even all cases?)
but not at a reasonable cost. SSI admits that it might cause
rollbacks in some cases where correctness doesn't require it, but it
ensures that it will roll back enough transactions to ensure
correctness and tries to do so at a reasonable cost.

> I'll write something up. Can I document that you may depend on the
> results read in aborted subtransactions, or should I leave that
> undefined for now?

Hmm. They will be read with the correct snapshot, and since we're
holding predicate locks they can't show any anomalies if the final
transaction complete, so I sure can't see any reason it is a problem
to depend on data viewed in an aborted subtransaction. If you think
that is a property that could be useful to users, I guess it should
be documented.

-Kevin

On Sat, Sep 08, 2012 at 11:34:56AM -0700, Jeff Davis wrote:
> If so, I think we need a documentation update. The serializable
> isolation level docs don't quite make it clear that serializability only
> applies to transactions that commit. It might not be obvious to a user
> that there's a difference between commit and abort for a RO transaction.
> I think that, in S2PL, serializability applies even to aborted
> transactions (though I haven't spent much time thinking about it), so
> users accustomed to other truly-serializable implementations might be

Yes, I agree that this is probably worth mentioning in the
documentation.

It might be worth noting that serializable mode will not cause
read-only transactions to fail to commit (as might be possible in some
optimistic concurrency control systems). However, it might require
other transactions to be aborted to ensure serializability. If the
user aborts the read-only transaction, that won't necessarily happen.

Figure 2 of the aforementioned paper is actually a nice example of
this. The read-only transaction T1 is allowed to commit, but as a
result T2 has to be aborted. If T1 had ABORTed instead of COMMIT, T2
would be allowed to proceed.

Dan

--
Dan R. K. Ports UW CSE http://drkp.net/

On Mon, 2012-09-10 at 21:59 -0400, Dan Ports wrote:
> It might be worth noting that serializable mode will not cause
> read-only transactions to fail to commit

For the archives, and for those not following the paper in detail, there
is one situation in which SSI will abort a read-only transaction.

When there are three transactions forming a dangerous pattern where T1
(read-only) has a conflict out to T2, and T2 has a conflict out to T3;
and T3 is committed and T2 is prepared (for two-phase commit). In that
situation, SSI can't roll back the committed or prepared transactions,
so it must roll back the read-only transaction (T1).

Even in that case, SSI will ordinarily prevent T2 from preparing. It's
only if T1 takes its snapshot after T2 prepares and before T2 commits
that the situation can happen (I think).

Fortunately, for two-phase commit, that's not a big problem because the
window between PREPARE TRANSACTION and COMMIT PREPARED is supposed to be
narrow (and if it's not, you have bigger problems anyway). As long as
the window is narrow, than it's reasonable to retry the transaction T1,
and expect it to succeed after a short interval.

Regards,
Jeff Davis

On Mon, 2012-09-10 at 11:15 -0500, Kevin Grittner wrote:
> That's a fair point. Do you have any suggested wording, or
> suggestions for exactly where in the documentation you think it
> would be most helpful? The subsection on serializable transactions
> seems like the most obvious location:

Attached. I thought about putting it as a "note", but it seems like it's
easy to go overboard with those.

Regards,
Jeff Davis

On Mon, Sep 10, 2012 at 10:44:57PM -0700, Jeff Davis wrote:
> For the archives, and for those not following the paper in detail, there
> is one situation in which SSI will abort a read-only transaction.
>
> When there are three transactions forming a dangerous pattern where T1
> (read-only) has a conflict out to T2, and T2 has a conflict out to T3;
> and T3 is committed and T2 is prepared (for two-phase commit). In that
> situation, SSI can't roll back the committed or prepared transactions,
> so it must roll back the read-only transaction (T1).

This is true, but it isn't the only situation where a read-only
transaction can be rolled back -- this can happen even without
two-phase commit involved.

You can have a situation where two read/write transactions T2 and T3
conflict such that T2 appears to have executed first in the serial
order, but T3 commits before T2. If there's a read-only transaction T1
that takes its snapshot between when T3 and T2 commit, it can't be
allowed to read the data that the other two transactions modified: it'd
see the changes made by T3 but not T2, violating the serial order.

Given a choice, we'd prevent this by aborting one of the read/write
transactions. But if they've both already committed by the time the
read-only transaction T1 does its reads, we'd have to abort it instead.

(Note that this is still an improvement over two-phase locking, which
wouldn't allow any of the transactions to execute concurrently!)

What I was getting at in my previous mail was that there aren't any
situations where COMMIT will return a serialization failure for
a read-only transaction.

Dan

--
Dan R. K. Ports UW CSE http://drkp.net/