Thread: WIP: Detecting SSI conflicts before reporting constraint violations

WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
Hi hackers,

As described in a recent Reddit discussion[1] and bug report 9301[2],
there are scenarios where overlapping concurrent read-write sequences
produce serialization failures without constraints, but produce
constraint violations when there is a unique constraint.  A simple
example is deciding on a new value for a primary key by first checking
the existing contents of a table.

This makes life difficult if you're trying to build systems that
automatically retry SERIALIZABLE transactions where appropriate,
because you have to decide how and when to handle unique constraint
violations too.  For example, people have experimented with automatic
retry-on-40001 at the level of HTTP requests for Django applications
when using the middleware that maps HTTP requests to database
transactions, and the same opportunities presumably exist in Java
application servers and other web service technologies, but unique
constraint violations get in the way of that.

Here is an experimental patch to report such SSI conflicts.  I had to
make a change to aminsert_function so that the snapshot could be
available to btree insert code (which may be unpopular).  The
questions on my mind now are:  Are there still conflicting schedules
that would be missed, or significant new spurious conflict reports, or
other theoretical soundness problems?  Is that PredicateLockPage call
sound and cheap enough?  It is the only new code that isn't in a path
already doomed to ereport, other than the extra snapshot propagation,
and without it read-write-unique-3.spec (taken from bug report 9301)
doesn't detect the conflict.

Thoughts?

[1] https://www.reddit.com/r/PostgreSQL/comments/3z74v2/postgres_acid_transactions_and_locking_to_prevent/
[2] http://www.postgresql.org/message-id/flat/20140221002001.29130.27157@wrigleys.postgresql.org

--
Thomas Munro
http://www.enterprisedb.com

Attachment

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Robert Haas
Date:
On Sun, Jan 31, 2016 at 5:19 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> As described in a recent Reddit discussion[1] and bug report 9301[2],
> there are scenarios where overlapping concurrent read-write sequences
> produce serialization failures without constraints, but produce
> constraint violations when there is a unique constraint.  A simple
> example is deciding on a new value for a primary key by first checking
> the existing contents of a table.
>
> This makes life difficult if you're trying to build systems that
> automatically retry SERIALIZABLE transactions where appropriate,
> because you have to decide how and when to handle unique constraint
> violations too.  For example, people have experimented with automatic
> retry-on-40001 at the level of HTTP requests for Django applications
> when using the middleware that maps HTTP requests to database
> transactions, and the same opportunities presumably exist in Java
> application servers and other web service technologies, but unique
> constraint violations get in the way of that.
>
> Here is an experimental patch to report such SSI conflicts.  I had to
> make a change to aminsert_function so that the snapshot could be
> available to btree insert code (which may be unpopular).  The
> questions on my mind now are:  Are there still conflicting schedules
> that would be missed, or significant new spurious conflict reports, or
> other theoretical soundness problems?  Is that PredicateLockPage call
> sound and cheap enough?  It is the only new code that isn't in a path
> already doomed to ereport, other than the extra snapshot propagation,
> and without it read-write-unique-3.spec (taken from bug report 9301)
> doesn't detect the conflict.
>
> Thoughts?

I don't feel qualified to have an opinion on whether this is an
improvement.  I'm a little skeptical of changes like this on general
principle because sometimes one clientele wants error A to be reported
rather than error B and some other clientele wants the reverse.
Deciding who is right is above my pay grade.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Thu, Feb 4, 2016 at 7:48 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Sun, Jan 31, 2016 at 5:19 PM, Thomas Munro
> <thomas.munro@enterprisedb.com> wrote:
>> As described in a recent Reddit discussion[1] and bug report 9301[2],
>> there are scenarios where overlapping concurrent read-write sequences
>> produce serialization failures without constraints, but produce
>> constraint violations when there is a unique constraint.  A simple
>> example is deciding on a new value for a primary key by first checking
>> the existing contents of a table.
>>
>> This makes life difficult if you're trying to build systems that
>> automatically retry SERIALIZABLE transactions where appropriate,
>> because you have to decide how and when to handle unique constraint
>> violations too.  For example, people have experimented with automatic
>> retry-on-40001 at the level of HTTP requests for Django applications
>> when using the middleware that maps HTTP requests to database
>> transactions, and the same opportunities presumably exist in Java
>> application servers and other web service technologies, but unique
>> constraint violations get in the way of that.
>>
>> Here is an experimental patch to report such SSI conflicts.  I had to
>> make a change to aminsert_function so that the snapshot could be
>> available to btree insert code (which may be unpopular).  The
>> questions on my mind now are:  Are there still conflicting schedules
>> that would be missed, or significant new spurious conflict reports, or
>> other theoretical soundness problems?  Is that PredicateLockPage call
>> sound and cheap enough?  It is the only new code that isn't in a path
>> already doomed to ereport, other than the extra snapshot propagation,
>> and without it read-write-unique-3.spec (taken from bug report 9301)
>> doesn't detect the conflict.
>>
>> Thoughts?
>
> I don't feel qualified to have an opinion on whether this is an
> improvement.  I'm a little skeptical of changes like this on general
> principle because sometimes one clientele wants error A to be reported
> rather than error B and some other clientele wants the reverse.
> Deciding who is right is above my pay grade.

I don't see it as a difficult choice between two reasonable
alternatives.  It quacks suspiciously like a bug.

The theoretical problem with the current behaviour is that by
reporting a unique constraint violation in this case, we reach an
outcome that is neither a serialization failure nor a result that
could occur in any serial ordering of transactions.  The overlapping
transactions both observed that the key they planned to insert was not
present before inserting, and therefore they can't be untangled: there
is no serial order of the transactions where the second transaction to
run wouldn't see the key already inserted by the first transaction and
(presumably) take a different course of action.  (If it *does* see the
value already present in its snapshot, or doesn't even look first
before inserting and it turns out to be present, then it really
*should* get a unique constraint violation when trying to insert.)

The practical problem with the current behaviour is that the user has
to work out whether a unique constraint violation indicates:

1.  A programming error -- something is wrong that retrying probably won't fix

2.  An unfavourable outcome in the case that you speculatively
inserted without checking whether the value was present so you were
expecting a violation to be possible, in which case you know what
you're doing and you can figure out what to do next, probably retry or
give up

3.  A serialization failure that has been masked because our coding
happens to check for unique constraint violations without considering
SSI conflicts first -- retrying will eventually succeed.

It's complicated for a human to work out how to distinguish the third
category errors in each place where they might occur (and even to know
that they are possible, since AFAIK the manual doesn't point it out),
and impossible for an automatic retry-on-40001 framework to handle in
general.  SERIALIZABLE is supposed to be super easy to use (and
devilishly hard to implement...).

Here's an example.  Suppose you live in a country that requires
invoices to be numbered without gaps starting at one for each calendar
year.  You write:

  BEGIN ISOLATION LEVEL SERIALIZABLE;
  SELECT COALESCE(MAX(invoice_number) + 1, 1) FROM invoice WHERE year = 2016;
  INSERT INTO invoice VALUES (2016, $1, ...); -- using value computed above
  COMMIT;

I think it's pretty reasonable to expect that to either succeed or
ereport SQLSTATE 40001, and I think it's pretty reasonable to want to
be able to give the code that runs that transaction to a mechanism
that will automatically retry the whole thing if 40001 is reported.
Otherwise the promise of SERIALIZABLE is thwarted: you should be able
to forget about concurrency and write simple queries that assume they
are the only transaction in the universe.  The activities of other
overlapping transactions shouldn't change the outcome of your
transaction, other than potentially triggering 40001.

If you really want unique constraint violations for this case, then
with this patch you can remove the SELECT and get the UCV, or use a
lower isolation level since you are in fact depending on a hole in the
isolation between transactions.  Or you could consider the new SSI
conflict to be spurious (though it isn't!) and just retry, which
doesn't seem to have a downside since you already have to handle
those.

I added the (German?) invoice numbering example above as
specs/read-write-unique-4.spec in the attached new patch, with three
interesting permutations.  I am not sure what to think about the third
permutation yet -- an overlap between two transactions where one of
them just writes the key, and the other reads then writes -- the
outcome is possibly wrong there and I don't know off the top of my
head how to fix it if it is.  My thinking was that this case should be
covered by the new predicate lock I introduced, because even though s1
didn't explicitly SELECT anything, by successfully passing the unique
check phase it really has read something, so it's a transaction that
has read (the absence of the value) and written (the value).  This is
the part of the problem that I'm least sure of, but am hoping to work
out with some SSI expert help.

--
Thomas Munro
http://www.enterprisedb.com

Attachment

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Peter Geoghegan
Date:
On Wed, Feb 3, 2016 at 10:48 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> I don't feel qualified to have an opinion on whether this is an
> improvement.  I'm a little skeptical of changes like this on general
> principle because sometimes one clientele wants error A to be reported
> rather than error B and some other clientele wants the reverse.
> Deciding who is right is above my pay grade.

Exclusion constraints can sometimes have one client deadlock, rather
than see an exclusion violation. The particular client that sees an
error is undefined either way, so I personally felt that that wasn't
very important. But that's a problem that I'm closer to, and I won't
express an opinion on this patch.

-- 
Peter Geoghegan



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Kevin Grittner
Date:
On Wed, Feb 3, 2016 at 5:12 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

> I don't see it as a difficult choice between two reasonable
> alternatives.  It quacks suspiciously like a bug.

That seems a little strong to me; I think it would be an
unacceptable change in behavior to back-patch this, for example.
On the other hand, we have had multiple reports on these lists
asserting that the behavior is a bug (not to mention several
off-list communications to me about it), it seems like a POLA
violation, it hides the information that users of serializable
transactions consider most important in favor of relatively
insignificant (to them) details about what table and key were
involved, and it causes errors to be presented to end users that
the developers would prefer to be handled discretely in the
background.  The current behavior provides this guarantee:

"Any set of successfully committed concurrent serializable
transactions will provide a result consistent with running them one
at a time in some order."

Users of serializable transactions would, in my experience,
universally prefer to strengthen that  guarantee with:

"Should a serializable transaction fail only due to the action of a
concurrent serializable transaction, it should fail with a
serialization failure error."

People have had to resort to weird heuristics like performing a
limited number of retries on a duplicate key error in case it
happens to be due to a serialization problem, but that wastes
resources when it is not a serialization failure, and unnecessarily
complicates the retry framework.

> The theoretical problem with the current behaviour is that by
> reporting a unique constraint violation in this case, we reach an
> outcome that is neither a serialization failure nor a result that
> could occur in any serial ordering of transactions.

Well, not if you only consider successfully committed transactions.  ;-)

> The overlapping
> transactions both observed that the key they planned to insert was not
> present before inserting, and therefore they can't be untangled: there
> is no serial order of the transactions where the second transaction to
> run wouldn't see the key already inserted by the first transaction and
> (presumably) take a different course of action.  (If it *does* see the
> value already present in its snapshot, or doesn't even look first
> before inserting and it turns out to be present, then it really
> *should* get a unique constraint violation when trying to insert.)
>
> The practical problem with the current behaviour is that the user has
> to work out whether a unique constraint violation indicates:
>
> 1.  A programming error -- something is wrong that retrying probably won't fix
>
> 2.  An unfavourable outcome in the case that you speculatively
> inserted without checking whether the value was present so you were
> expecting a violation to be possible, in which case you know what
> you're doing and you can figure out what to do next, probably retry or
> give up
>
> 3.  A serialization failure that has been masked because our coding
> happens to check for unique constraint violations without considering
> SSI conflicts first -- retrying will eventually succeed.
>
> It's complicated for a human to work out how to distinguish the third
> category errors in each place where they might occur (and even to know
> that they are possible, since AFAIK the manual doesn't point it out),
> and impossible for an automatic retry-on-40001 framework to handle in
> general.  SERIALIZABLE is supposed to be super easy to use (and
> devilishly hard to implement...).

This is exactly on the mark, IMO.

FWIW, at the conference in Moscow I had people for whom this is
their #1 feature request.  (Well, actually, they also argued it
should be considered a bug fix; but on argument agreed that the
current guarantee is useful and operating as designed, so were
willing to see it treated as an enhancement.)

Another way of stating the impact of this patch is that it changes
the guarantee to:

"If you write a transaction so that it does the right thing when
run alone, it will always do the right thing as part of any mix of
serializable transactions or will fail with a serialization failure
error."

Right now we have to add:

"... or, er, maybe a duplicate key error."

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



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Simon Riggs
Date:
On 3 February 2016 at 23:12, Thomas Munro <thomas.munro@enterprisedb.com> wrote:
 
 It quacks suspiciously like a bug.

Agreed

What's more important is that is very publicly a bug in the eyes of others and should be fixed and backpatched soon.

We have a maintenance release coming in a couple of weeks and I'd like to see this in there.

Let's set good standards for responsiveness and correctness.


I'd also like to see some theory in comments and an explanation of why we're doing this (code).

--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Fri, Mar 11, 2016 at 8:50 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 3 February 2016 at 23:12, Thomas Munro <thomas.munro@enterprisedb.com>
> wrote:
>
>>
>>  It quacks suspiciously like a bug.
>
>
> Agreed
>
> What's more important is that is very publicly a bug in the eyes of others
> and should be fixed and backpatched soon.
>
> We have a maintenance release coming in a couple of weeks and I'd like to
> see this in there.

As I understand it, the approach I've taken here can't be backpatched
because it changes the aminsert_function interface (it needs the
current snapshot when inserting), so I was proposing this as an
improvement for 9.6.  I guess there are other way to get the right
snapshot into btinsert (and thence _bt_check_unique), but I didn't
think it would be very classy to introduce a 'current snapshot' global
variable to smuggle it in.

> Let's set good standards for responsiveness and correctness.
>
>
> I'd also like to see some theory in comments and an explanation of why we're
> doing this (code).

Will do.

-- 
Thomas Munro
http://www.enterprisedb.com



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Simon Riggs
Date:
On 10 March 2016 at 20:36, Thomas Munro <thomas.munro@enterprisedb.com> wrote:
On Fri, Mar 11, 2016 at 8:50 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 3 February 2016 at 23:12, Thomas Munro <thomas.munro@enterprisedb.com>
> wrote:
>
>>
>>  It quacks suspiciously like a bug.
>
>
> Agreed
>
> What's more important is that is very publicly a bug in the eyes of others
> and should be fixed and backpatched soon.
>
> We have a maintenance release coming in a couple of weeks and I'd like to
> see this in there.

As I understand it, the approach I've taken here can't be backpatched
because it changes the aminsert_function interface (it needs the
current snapshot when inserting), so I was proposing this as an
improvement for 9.6.  I guess there are other way to get the right
snapshot into btinsert (and thence _bt_check_unique), but I didn't
think it would be very classy to introduce a 'current snapshot' global
variable to smuggle it in.

But this is a Serializable transaction, so it only has one snapshot...

This is where adding comments on patch theory would help.
 
--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Fri, Mar 11, 2016 at 10:00 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 10 March 2016 at 20:36, Thomas Munro <thomas.munro@enterprisedb.com>
> wrote:
>>
>> On Fri, Mar 11, 2016 at 8:50 AM, Simon Riggs <simon@2ndquadrant.com>
>> wrote:
>> > On 3 February 2016 at 23:12, Thomas Munro
>> > <thomas.munro@enterprisedb.com>
>> > wrote:
>> >
>> >>
>> >>  It quacks suspiciously like a bug.
>> >
>> >
>> > Agreed
>> >
>> > What's more important is that is very publicly a bug in the eyes of
>> > others
>> > and should be fixed and backpatched soon.
>> >
>> > We have a maintenance release coming in a couple of weeks and I'd like
>> > to
>> > see this in there.
>>
>> As I understand it, the approach I've taken here can't be backpatched
>> because it changes the aminsert_function interface (it needs the
>> current snapshot when inserting), so I was proposing this as an
>> improvement for 9.6.  I guess there are other way to get the right
>> snapshot into btinsert (and thence _bt_check_unique), but I didn't
>> think it would be very classy to introduce a 'current snapshot' global
>> variable to smuggle it in.
>
>
> But this is a Serializable transaction, so it only has one snapshot...
>
> This is where adding comments on patch theory would help.

Here's a much simpler version with more comments, and an explanation
below.  It handles the same set of isolation test specs.

I dropped the calls to PredicateLockPage and
CheckForSerializableConflictOut, which means I don't even need a
snapshot (and if I ever do, you're right, doh, I should just use
GetTransactionSnapshot()).  They were part of my (so far unsuccessful)
attempt to detect a conflict for read-write-unique-4.spec permutation
"r2 w1 w2 c1 c2", where one transaction only writes.   That leaves
only a "hypothetical" CheckForSerializableConflictIn check (see
below).

This version seems to handle the obvious overlapping read-then-write
scenarios I've contrived and seen in bug reports.  I need to do more
study of the SSI code and theory, and see if there are other
conflicting schedules that are missed but could be detected at this
point.  (Possibly including that "r2 w1 w2 c1 c2" case.)

Explanation:

In unpatched master, when _bt_check_unique discovers that a key
already exists in the index, it checks if the heap tuple is live by
calling heap_hot_search, which in turn calls heap_hot_search_buffer,
and then throws away the buffer and returns true or false.  If the
result is true, a unique constraint violation is raised.

This patch introduces a drop-in replacement
check_unique_tuple_still_live to call instead of heap_hot_search.  The
replacement function also calls heap_hot_search_buffer, but while it
has the buffer it takes the opportunity to do an SSI conflict-in
check.  At that point we know that the transaction is already doomed
to ereport, it's just a question of figuring out whether it should
ereport 40001 first.

The new conflict-in check tells the SSI machinery that we are going to
insert at this index page, even though we aren't.  It mirrors the one
that happens right before _bt_findinsertloc and _bt_insertonpg, which
would be reached if this were a non-unique index.  It gives the SSI
machinery a chance to detect conflicts that would be created by
writing to this page.  If it doesn't detect a conflict, behaviour is
unchanged and the usual unique constraint violation will be raised.

I'm not sure what to make of the pre-existing comment about following
HOT-chains and concurrent index builds (which I moved).  Does it mean
there is some way that CREATE INDEX CONCURRENTLY could cause us to
consider the wrong tuple and miss an SSI conflict?

(Tangentially, I believe the nearby ON CONFLICT code needs some SSI
checks and I may investigate that some time if someone doesn't beat me
to it, but not as part of this patch.)

--
Thomas Munro
http://www.enterprisedb.com

Attachment

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Fri, Mar 11, 2016 at 6:31 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> I'm not sure what to make of the pre-existing comment about following
> HOT-chains and concurrent index builds (which I moved).  Does it mean
> there is some way that CREATE INDEX CONCURRENTLY could cause us to
> consider the wrong tuple and miss an SSI conflict?

No, because the check is done entirely on the basis of the the index
page.  The question may be arise if we discover that we also need a
conflict-out check here though, because it would be based on the tuple
that has been found by heap_hot_search_buffer.

-- 
Thomas Munro
http://www.enterprisedb.com



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Fri, Mar 11, 2016 at 6:31 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> This patch introduces a drop-in replacement
> check_unique_tuple_still_live to call instead of heap_hot_search.  The
> replacement function also calls heap_hot_search_buffer, but while it
> has the buffer it takes the opportunity to do an SSI conflict-in
> check.  At that point we know that the transaction is already doomed
> to ereport, it's just a question of figuring out whether it should
> ereport 40001 first.

Upon reflection, I want to forget about all that for now and propose
just a one line addition to _bt_check_unique that can handle the
explicit read-then-write cases reported.  See attached.

(There may be a separate follow-up patch that refactors to examine
heap tuples like in the previous version, if that turns out to be
necessary to detect more complicated cases like "r2 w1 w2 c1 c2" (as I
suspect), but I'm not sure about that or if I'll be able to do that
for this CF and until then there's no point in arranging the code that
way.)

--
Thomas Munro
http://www.enterprisedb.com

Attachment

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Kevin Grittner
Date:
On Thu, Mar 10, 2016 at 1:50 PM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 3 February 2016 at 23:12, Thomas Munro <thomas.munro@enterprisedb.com> wrote:
>
>>  It quacks suspiciously like a bug.
>
> Agreed
>
> What's more important is that is very publicly a bug in the eyes
> of others and should be fixed and backpatched soon.

I really am skeptical about back-patching this, since it changes
behavior that it is not inconceivable that someone, somewhere might
be relying on.  Given the number of times the current behavior has
been reported as a bug, I might be persuaded otherwise, but it
"feels" wrong to me.  I really don't like putting anything into a
minor release that might make someone reluctant to apply fixes for
serious bugs or security vulnerabilities.

> We have a maintenance release coming in a couple of weeks and I'd
> like to see this in there.

There is no shortage of people who would like to see that; but how
do we prove that we're not breaking things for anyone if we do
that?

> Let's set good standards for responsiveness and correctness.

This was discussed at the time SSI was implemented.  In particular,
I cited section 4.2 of the paper by Jorwekar, et al.[1], where a
tool for static analysis of serialization anomalies allowed by
applications discounted (as false positives) apparent dangerous
structures when integrity constraints prevented any anomaly from
actually manifesting itself in the database.  As discussed and
implemented at the time, no serialization anomalies can appear in
the database -- what we're talking about is improving the error
handling such that an application framework can automatically
handle transient errors without letting the end user (or even the
application software) see that there *was* a transient problem.
That's a nice feature to have, but I'm hard put to see where lack
of that feature constitutes a bug.

> I'd also like to see some theory in comments and an explanation
> of why we're doing this (code).

A reference to the 2007 VLDB paper would not be amiss there, along
with a brief description of the issue.

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

[1] http://www.vldb.org/conf/2007/papers/industrial/p1263-jorwekar.pdf   Sudhir Jorwekar, Alan Fekete, Krithi
Ramamritham,S. Sudarshan.   Automating the Detection of Snapshot Isolation Anomalies.   VLDB ‘07, September 23-28,
2007,Vienna, Austria. 



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Kevin Grittner
Date:
On Thu, Mar 10, 2016 at 11:31 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

> Here's a much simpler version with more comments

> It handles the same set of isolation test specs.

I'm impressed that you found a one-line patch that seems to get us
90% of the way to a new guarantee; but I think if we're going to do
something here it should take us from one clear guarantee to
another.  We really don't have a new guarantee here that is easy to
express without weasel-words.  :-(  Let me see whether I can figure
out how to cover that one permutation that is left after this
one-liner.

In terms of theory, one way to look at this is that an insert of an
index tuple to a unique index involves a read from that index which
finds a "gap", which in SSI is normally covered by a predicate lock
on the appropriate part of the index.  (Currently that is done at
the page level, although hopefully we will eventually enhance that
to use "next-key gap locking".)  Treating the index tuple insertion
as having an implied read of that gap is entirely justified and
proper -- internally the read actually does happen.

That leaves the question of whether it is theoretically sound to
report a transient error due to the actions of a concurrent
serializable transaction as a serialization failure when it
involves a unique index.

Anyone using serializable transactions to prevent problems from
race conditions would consider that the fact that an error was
caused by the action of a concurrent transaction and would not
occur if the transaction were retried from the start as far more
important than details such as it being a duplicate key error or
what table or key is involved.  If we can get LOG level logging of
those details, fine, but let's not put such things "in the face" of
the user when we don't need to do so -- anyone using serializable
transactions should have a generalized transaction retry mechanism
which should handle this quietly behind the scenes.

There have been multiple requests to have more information about
the details of serialization failures when such detail is
available, so that people can tune their transactions to minimize
such retries.  IMO we should see whether we can provide table/key
in the error detail for this sort of serialization failure.

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



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Sat, Mar 12, 2016 at 1:25 AM, Kevin Grittner <kgrittn@gmail.com> wrote:
> On Thu, Mar 10, 2016 at 11:31 PM, Thomas Munro
> <thomas.munro@enterprisedb.com> wrote:
>
>> Here's a much simpler version with more comments
>
>> It handles the same set of isolation test specs.
>
> I'm impressed that you found a one-line patch that seems to get us
> 90% of the way to a new guarantee; but I think if we're going to do
> something here it should take us from one clear guarantee to
> another.  We really don't have a new guarantee here that is easy to
> express without weasel-words.  :-(

+1

> Let me see whether I can figure
> out how to cover that one permutation that is left after this
> one-liner.
>
> In terms of theory, one way to look at this is that an insert of an
> index tuple to a unique index involves a read from that index which
> finds a "gap", which in SSI is normally covered by a predicate lock
> on the appropriate part of the index.  (Currently that is done at
> the page level, although hopefully we will eventually enhance that
> to use "next-key gap locking".)  Treating the index tuple insertion
> as having an implied read of that gap is entirely justified and
> proper -- internally the read actually does happen.

Right, that is what I was trying to achieve in earlier versions
immediately after _bt_check_unique returns without error, with
something like this:

+       /*
+        * By determining that there is no duplicate key, we have read an index
+        * gap, so we predicate lock it.
+        */
+       PredicateLockPage(rel, buf, GetTransactionSnapshot());

But since a conflict-in check immediately follows (because we insert),
wouldn't that be redundant (ie self-created SIREAD locks are dropped
at that point)?

Next I thought that a conflict-out check on the heap tuple might be
necessary to detect a problem here.  Back in the v2 patch I was making
an explicit call to CheckForSerializationConflictOut, but I now see
that a plain old heap_fetch would do that.  I was also using the wrong
htid because I missed that the CIC special case code reassigns htid.
See the attached experimental patch which applies on top of the v4 one
liner patch, adding a call to heap_fetch the conflicting tuple.  This
way, read-write-unique-4.out permutation "r1 w1 w2 c1 c2" now raises a
40001 after c1 completes and w2 continues, and no other isolation test
result changes.  So still no cigar for "r2 w1 w2 c1 c2".  Stepping
through CheckForSerializationConflictOut when it is called before w2
reports a UCV, I see that it returns here:

    if (RWConflictExists(MySerializableXact, sxact))
    {
        /* We don't want duplicate conflict records in the list. */
        LWLockRelease(SerializableXactHashLock);
        return;
    }

So the RW conflict (ie one edge) is detected (and already had been?),
but not a dangerous structure (there are not two consecutive edges in
the graph? We know that we have read something written by an
overlapping transaction, but not that it has read something
[hypothetically] written by us?).  I will have another look at this in
a few days but for now I need to do some other things, so I'm posting
these observations in case they are in some way helpful...

--
Thomas Munro
http://www.enterprisedb.com

Attachment

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
David Steele
Date:
Hi Thomas,

On 3/13/16 8:20 PM, Thomas Munro wrote:

> <...>  I will have another look at this in
> a few days but for now I need to do some other things, so I'm posting
> these observations in case they are in some way helpful...

It's not clear to me what state this patch should be in but the thread 
has been idle for over a week.

Have you had the chance to take a look as you indicated above?

Thanks,
-- 
-David
david@pgmasters.net



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Sat, Mar 26, 2016 at 5:04 AM, David Steele <david@pgmasters.net> wrote:
> Hi Thomas,
>
> On 3/13/16 8:20 PM, Thomas Munro wrote:
>
>> <...>  I will have another look at this in
>> a few days but for now I need to do some other things, so I'm posting
>> these observations in case they are in some way helpful...
>
>
> It's not clear to me what state this patch should be in but the thread has
> been idle for over a week.
>
> Have you had the chance to take a look as you indicated above?

Here's a summary of where we are today:

1.  It looks like we have general consensus that this is a problem and
that we should fix it, but not about whether a change should be
backpatched, if/when we arrive at an acceptable patch.

2.  We have a 1 line patch (+ comments and isolation tests) which
covers the cases that I've heard complaints about.  These cases all
involve either checking if a value already exists with SELECT or
computing a new value based on existing values with something like
SELECT MAX(id) + 1 and then inserting it in concurrent transactions.

3.  In the process of designing isolation tests, I found a case that
doesn't cover: where one session simply inserts, while the another
checks explicitly whether it's OK to insert, finds that it is, and
then tries to do so.  I haven't figured out how to detect an SSI
conflict before the UCV in this case.

Realistically I'm not going to have a solution to the third problem
before the 31st.

-- 
Thomas Munro
http://www.enterprisedb.com



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Michael Paquier
Date:
On Sun, Mar 27, 2016 at 8:15 AM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> Realistically I'm not going to have a solution to the third problem
> before the 31st.

Ping.
-- 
Michael



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Simon Riggs
Date:
On 7 April 2016 at 08:55, Michael Paquier <michael.paquier@gmail.com> wrote:
On Sun, Mar 27, 2016 at 8:15 AM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> Realistically I'm not going to have a solution to the third problem
> before the 31st.

Ping.

We agree its a bug, so the deadline doesn't need to constrain us.

I suggest we should apply what we have then fix the rest later when we work out how.

--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Kevin Grittner
Date:
On Thu, Apr 7, 2016 at 3:26 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

> We agree its a bug, so the deadline doesn't need to constrain us.

I'm not sure there is consensus across the community on that.

> I suggest we should apply what we have then fix the rest later
> when we work out how.

On that, I agree.  I will push what we have before the deadline
today, since it would cover about 90% of the SSI complaints I've
seen.

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



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Thomas Munro
Date:
On Thu, Apr 7, 2016 at 10:42 PM, Kevin Grittner <kgrittn@gmail.com> wrote:
> On Thu, Apr 7, 2016 at 3:26 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>
>> We agree its a bug, so the deadline doesn't need to constrain us.
>
> I'm not sure there is consensus across the community on that.
>
>> I suggest we should apply what we have then fix the rest later
>> when we work out how.
>
> On that, I agree.  I will push what we have before the deadline
> today, since it would cover about 90% of the SSI complaints I've
> seen.

Here is a version that includes an attempt to describe the situation
in the documentation.  The first three sentences highlight the general
problem and apply to all versions since 9.1.  Then the rest of the
paragraph beginning "This can be avoided ..." describes the improved
situation in 9.6 if this patch is committed.

--
Thomas Munro
http://www.enterprisedb.com

Attachment

Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Kevin Grittner
Date:
On Thu, Apr 7, 2016 at 8:49 AM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

> Here is a version that includes an attempt to describe the
> situation in the documentation.

Pushed with minor adjustments to the docs.  Mostly I thought your
new text was more appropriate as just another paragraph than as a
"note".  The previous paragraph was a little imprecise and was in
some conflict with the new one, so I adjusted that a little, too.

Nice work!  I sure wish we had spotted that a one-line check there
would have covered so much when the feature was first added.

I understand there is considerable feeling that this should be
back-patched, but I have not done that pending a clear consensus on
the point, since it is a user-visible behavioral change.

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



Re: WIP: Detecting SSI conflicts before reporting constraint violations

From
Robert Haas
Date:
On Thu, Apr 7, 2016 at 12:20 PM, Kevin Grittner <kgrittn@gmail.com> wrote:
> On Thu, Apr 7, 2016 at 8:49 AM, Thomas Munro
> <thomas.munro@enterprisedb.com> wrote:
>
>> Here is a version that includes an attempt to describe the
>> situation in the documentation.
>
> Pushed with minor adjustments to the docs.  Mostly I thought your
> new text was more appropriate as just another paragraph than as a
> "note".  The previous paragraph was a little imprecise and was in
> some conflict with the new one, so I adjusted that a little, too.
>
> Nice work!  I sure wish we had spotted that a one-line check there
> would have covered so much when the feature was first added.
>
> I understand there is considerable feeling that this should be
> back-patched, but I have not done that pending a clear consensus on
> the point, since it is a user-visible behavioral change.

I think that's a good call.  Conservatism in back-patching is entirely
warranted.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company