Re: [Xen-devel] [HACKERS] [OSSTEST PATCH 0/1] PostgreSQL db: Retry on constraint violation [and 2 more messages]

[Kevin Grittner <kgrittn@xxxxxxxxx>]

On Wed, Dec 14, 2016 at 12:44 AM, Robert Haas <robertmhaas@xxxxxxxxx> wrote:
> On Tue, Dec 13, 2016 at 1:00 PM, Ian Jackson <ian.jackson@xxxxxxxxxxxxx> 
> wrote:

> Saying that a set of transactions are serializable is equivalent to
> the statement that there is some serial order of execution which would
> have produced results equivalent to the actual results.  That is,
> there must be at least one schedule (T1, ..., Tn) such that running
> the transactions one after another in that order would have produced
> the same results that were obtained by running them concurrently.
> Any transactions that roll back whether due to serialization anomalies
> or manual user intervention or any other reason are not part of the
> schedule, which considers only successfully committed transactions.
> The rolled-back transactions effectively didn't happen, and
> serializability as a concept makes no claim about the behavior of such
> transactions.  That's not a PostgreSQL thing: that's database theory.

Right.  That said, with S2PL's reliance on blocking, it can provide
certain guarantees that are not required by the SQL standard nor by
normal definitions of serializable transactions.
(1)  The effective order of execution will match commit order of
successfully committed transactions.  Both the SQL standard and the
most definitions of serializable transactions merely require that
there is *some* order of transactions which provides the same
effects as having run the transactions one at a time in that order.
(2)  Even transactions terminated to resolve deadlocks never show
serialization anomalies before being canceled.

S2PL was the most common technique for implementing serializable
transactions for a long time, and some have come to think that its
guarantees should always be provided.  The problem is that in most
common workloads S2PL performs far worse than some other
techniques, including the SSI technique used by PostgreSQL, even
when the need to discard results from failed transactions is
considered.  Essentially, the position Ian has been taking is that
PostgreSQL should provide  the guarantee of (2) above.  As far as I
can see, that would require using S2PL -- something the community
ripped out of PostgreSQL because of its horrible performance and
has refused to consider restoring (for good reason, IMO).

> However, in practice, the scenario that you mention should generally
> work fine in PostgreSQL, I think.  If T performed any writes, the
> rollback throws them away, so imagine removing the actual T from the
> mix and replacing it with a substitute version T' which performs the
> same reads but no writes and then tries to COMMIT where T tried to
> ROLLBACK.  T' will succeed, because we never roll back a read-only
> transaction at commit time.

Huh, I had to think about that for a minute, but you are right
about never rolling back a read-only transaction at commit time
(except possibly for a prepared transaction -- I would have to look
at that more closely).  The reason is that to have a serialization
failure under SSI we must have a "dangerous structure" (of a pivot
(Tpivot) with both a rw-dependency in (Tin) and a rw-dependency out
(Tout)) and Tout must have committed (and committed first). If
Tpivot is still active, we will cancel it, because Tin, if it were
to be canceled and perform an immediate retry, could hit the exact
same problem, and be canceled again based on conflicts with the
exact same other transactions.  We don't want to burn resources
repeating transactions with no progress made.  So the only time the
read-only transaction can be canceled is when Tout and Tpivot are
running concurrently, Tout commits, Tpivot develops a rw-dependency
to Tout (either before or after the commit of Tout), Tin starts
(after the commit of Tout), Tpivot commits before Tin develops a
rw-dependency with it (otherwise Tpivot would be the one canceled),
and then Tin develops a rw-dependency to Tpivot.  That dependency
should be recognized when it is developed, causing Tin to be
canceled -- so the commit of Tin should never get the serialization
failure.

> If it were to fail, it would have to fail *while performing one
> of the reads*, not later.

Yeah, that's the concise statement of what my lengthy explanation
above proves.  ;-)

> But imagine a hypothetical database system in which anomalies are
> never detected until commit time.  We somehow track the global
> must-happen-before graph and refuse the commit of any transaction
> which will create a cycle.

You have just described optimistic concurrency control (OCC), which
has been used, although not in any really popular DBMS systems I
can think of.  It certainly has enjoyed a resurgence in some ORMs,
though -- implemented outside the DBMS.

> Let's also suppose that this system uses
> snapshots to implement MVCC.  In such a system, read-only transactions
> will sometimes fail at commit time if they've seen a view of the world
> that is inconsistent with the only remaining possible serial
> schedules.  For example, suppose T1 updates A -> A' and reads B.
> Concurrently, T2 updates B -> B'; thus, T1 must precede T2.  Next, T2
> commits.

In this, T1 is Tpivot and T2 is Tout from my above discussion.

> Now, T3 begins and reads B', so that T2 must precede T3.
> Next T1 commits.  T3, which took its snapshot before the commit of T1,
> now reads A.  Thus T3 has to proceed T1.  That's a cycle, so T3 won't
> be allowed to commit,

Yes, all the conditions described above are matched here.

> but yet it's done a couple of reads and hasn't
> failed yet...  because of an implementation detail of the system.
> That's probably annoying from a user perspective -- if a transaction
> is certainly going to fail we'd like to report the failure as early as
> possible -- and it's probably crushingly slow, but according to my
> understanding it's unarguably a correct implementation of
> serializability (assuming there are no bugs), yet it doesn't deliver
> the guarantee you're asking for here.

100% accurate.

> I have not read any database literature on the interaction of
> serializability with subtransactions.  This seems very thorny.
> Suppose T1 reads A and B and updates A -> A' while concurrently T2
> reads A and B and updates B -> B'.  This is obviously not
> serializable;

Right, this pattern is generally described in the literature as
simple write skew.

> if either transaction had executed before the other in a
> serial schedule, the second transaction in the schedule would have had
> to have seen (A, B') or (A', B) rather than (A, B), but that's not
> what happened.  But what if each of T1 and T2 did the reads in a
> subtransaction, rolled it back, and then did the write in the main
> transaction and committed?  The database system has two options.
> First, it could assume that the toplevel transaction may have relied
> on the results of the aborted subtransaction.

This is what we do in our implementation of SSI.  Predicate locks
from reads within subtransactions are not discarded, even if the
work of the subtransaction is otherwise discarded.

> But if it does that,
> then any serialization failure which afflicts a subtransaction must
> necessarily also kill the main transaction, which seems pedantic and
> unhelpful.  If you'd wanted the toplevel transaction to be killled,
> you wouldn't have used a subtransaction, right?

We reasoned that the results of reads within the subtransaction
could have influenced the decision on whether to roll back the
subtransaction, so release of the predicate locks could easily lead
to non-repeatable results.

> Second, it could
> assume that the toplevel transaction in no way relied on or used the
> values obtained from the aborted subtransaction.  However, that
> defeats the whole purpose of having subtransactions in the first
> place.  What's the point of being able to start subtransactions if you
> can't roll them back and then decide to do something else instead?  It
> seems to me that what the database system should do is make that
> second assumption, and what the user should do is understand that to
> the degree that transactions depend on the results of aborted
> subtransactions, there may be serialization anomalies that go
> undetected.

Well, we opted for trying to prevent the anomalies even in the face
of subtransactions which rolled back.  The requirements within SSI
to cause a serialization failure (dangerous structure, commit
timings, etc.) are enough to allow useful subtransactions, I think.

> And the user should put up with that because the cure is
> worse than the disease.

Not as we saw it during development of the serializable transaction
feature, and I have not yet heard any complaints about that choice.

> Maybe there's a more formally satisfying
> answer than that but I'm not really seeing it...

It would take some actual field complaints about current behavior,
with reasonable use cases, to persuade me that your answer is
better than what has been implemented and out in the field for five
years.  The subtransactions are only causing a problem in *this*
case because the exception that is being ignored is coming from a
declarative constraint.  We relied on previous research showing
that apparent opportunities for serialization anomalies were often
prevented by declarative constraints.  With the difficulty in
acquiring the necessary predicate locks within the code
implementing the constraints, we felt we could not do that reliably
and still make the 9.1 release with the overall feature.  We
thought that the only down side was that that SQLSTATE codes from
the constraints could be thrown when the violation was caused by
the actions of a concurrent transaction -- meaning that a
serialization failure would be better in terms of knowing when to
retry a transaction rather than throwing an error in the face of an
end user.  This was always something we wanted to come back and
improve in a later release; but nobody has been willing to fund any
of the many improvements we know could be made to the serializable
transaction implementation, so it has so far remained in this
state.

What we missed is that, while we took action to try to ensure that
a serialization failure could not be discarded, we didn't consider
that a constraint violation exception which was preventing an
anomaly *could* be discarded.  Effectively, this has escalated
detection of serialization failures involving reads which are part
of enforcing declarative constraints from the level of a feature
request to cure a significant annoyance for those using them, to a
bug fix necessary to prevent serialization anomalies.

Fortunately, Thomas Munro took an interest in the problem as it
related to duplicates on primary keys, unique constraints, and
unique indexes, and put forward a patch that cured the defect in
the common cases, and provided an easy workaround for the one case
he was unable to fix in that initial patch.  To finish the work for
these constraints and indexes, I think we need to add predicate
locking while descending to the insertion point  during the check
for an existing duplicate.

I'm not sure about foreign key constraints and exclusion
constraints.  I have neither seen a failure related to either of
these, nor proven that there cannot be one.  Without having
assessed the scope of the problems (if any) in those constraints,
it's hard to say what needs to be done or how much work it is.

It also wouldn't hurt to double-check that the serializable
transaction's "doomed" flag is set and checked everywhere it should
be; but I have no reason to think it isn't.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel