Обсуждение: BUG #13681: Serialization failures caused by new multixact code of 9.3 (back-patch request)

The following bug has been logged on the website:

Bug reference:      13681
Logged by:          Olivier Dony
Email address:      odo@odoo.com
PostgreSQL version: 9.3.10
Operating system:   Ubuntu 14.04 LTS
Description:

This is a back-patch request of 05315498012530d44cd89a209242a243374e274d to
9.3 and 9.4.

As discussed in the -general list[1], both 9.3 and 9.4 show spurious
serialization failures when faced with the use case included below.

In 9.2, T2 used to block until T1's commit, but then continued without
error, and in 9.5 both T1 and T2 proceed without blocking nor error.

Kevin Grittner located[2] the root cause as a regression that was fixed by
Álvaro at 0531549 [3].

For what it's worth, our system uses many long-running transactions
(background jobs, batch data imports, etc.) that are frequently interrupted
and rolled back by micro-transactions coming from users who just happen to
update minor data on their records (such as their last login date). So this
bug appears to cause more than just a performance regression.

Let me know if there is anything I can do to help the back-patch happen...


# The use case

-- 1. Setup tables
CREATE TABLE users (id serial PRIMARY KEY,
                    name varchar,
                    date timestamp );
CREATE TABLE orders (id serial PRIMARY KEY,
                     name varchar,
                     user_id int REFERENCES users (id) );
INSERT INTO users (id, name) VALUES (1, 'foo');
INSERT INTO orders (id, name) VALUES (1, 'order 1');


-- 2. Run 2 concurrent transactions: T1 and T2
              T1                                T2
|-----------------------------|----------------------------------|
    BEGIN ISOLATION LEVEL
          REPEATABLE READ;

    UPDATE orders
    SET name = 'order of foo',
        user_id = 1
    WHERE id = 1;

                                      BEGIN ISOLATION LEVEL
                                            REPEATABLE READ;

                                      UPDATE users
                                      SET date = now()
                                      WHERE id = 1;

                                      COMMIT;

    UPDATE orders
    SET name = 'order of foo (2)',
        user_id = 1
    WHERE id = 1;

T1 fails with:
ERROR:  could not serialize access due to concurrent update
CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."users" x WHERE "id"
OPERATOR(pg_catalog.=) $1 FOR KEY SHARE OF x"

# --

Many thanks,

Olivier


[1] http://www.postgresql.org/message-id/flat/560AA479.4080807@odoo.com
[2]

http://www.postgresql.org/message-id/flat/560AA479.4080807@odoo.com#1354271993.744124.1444079872314.JavaMail.yahoo@mail.yahoo.com
[3]
http://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=0531549

odo@odoo.com wrote:

> This is a back-patch request of 05315498012530d44cd89a209242a243374e274d to
> 9.3 and 9.4.
>
> As discussed in the -general list[1], both 9.3 and 9.4 show spurious
> serialization failures when faced with the use case included below.
>
> In 9.2, T2 used to block until T1's commit, but then continued without
> error, and in 9.5 both T1 and T2 proceed without blocking nor error.
>
> Kevin Grittner located[2] the root cause as a regression that was fixed by
> Álvaro at 0531549 [3].
>
> For what it's worth, our system uses many long-running transactions
> (background jobs, batch data imports, etc.) that are frequently interrupted
> and rolled back by micro-transactions coming from users who just happen to
> update minor data on their records (such as their last login date). So this
> bug appears to cause more than just a performance regression.

I would like to understand why does that patch fix the problem -- maybe
it's spurious and the real reason is something different.  The commit
message states:
    Commit 0ac5ad5134f2 removed an optimization in multixact.c that skipped
    fetching members of MultiXactId that were older than our
    OldestVisibleMXactId value.  The reason this was removed is that it is
    possible for multixacts that contain updates to be older than that
    value.  However, if the caller is certain that the multi does not
    contain an update (because the infomask bits say so), it can pass this
    info down to GetMultiXactIdMembers, enabling it to use the old
    optimization.

In your test case,

>               T1                                T2
> |-----------------------------|----------------------------------|
>     BEGIN ISOLATION LEVEL
>           REPEATABLE READ;
>
>     UPDATE orders
>     SET name = 'order of foo',
>         user_id = 1
>     WHERE id = 1;
>
>                                       BEGIN ISOLATION LEVEL
>                                             REPEATABLE READ;
>
>                                       UPDATE users
>                                       SET date = now()
>                                       WHERE id = 1;
>
>                                       COMMIT;
>
>     UPDATE orders
>     SET name = 'order of foo (2)',
>         user_id = 1
>     WHERE id = 1;

we have a transaction that takes a lock-only multi in
table users, and then when we do the second update we don't look it up
because ...??  And then this causes the test case not to fail because
..?

I would like to understand the mechanism for this fix before declaring
that the fix is correct.

The patch doesn't apply cleanly because of other changes in the area, so
I attach the backpatched version here, as well as a test case for
isolationtester in a separate commit (with which it's easy to confirm
that the problem does exist and that the patch indeed fixes it.)

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

On Thu, Dec 17, 2015 at 12:31 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

>> [orders.user_id references users.id]

> In your test case,
>
>>               T1                                T2
>> |-----------------------------|----------------------------------|
>>     BEGIN ISOLATION LEVEL
>>           REPEATABLE READ;
>>
>>     UPDATE orders
>>     SET name = 'order of foo',
>>         user_id = 1
>>     WHERE id = 1;
>>
>>                                       BEGIN ISOLATION LEVEL
>>                                             REPEATABLE READ;
>>
>>                                       UPDATE users
>>                                       SET date = now()
>>                                       WHERE id = 1;
>>
>>                                       COMMIT;
>>
>>     UPDATE orders
>>     SET name = 'order of foo (2)',
>>         user_id = 1
>>     WHERE id = 1;
>
> we have a transaction that takes a lock-only multi in table
> users, and then when we do the second update we don't look it up
> because ...??

The referencing column value did not change.  (We would not have
looked up on the first update either, since it also didn't change
there.)

>  And then this causes the test case not to fail because ..?

The concurrent update of the referencing table is not seen as a
write conflict (because it didn't actually change).

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

Kevin Grittner wrote:
> On Thu, Dec 17, 2015 at 12:31 PM, Alvaro Herrera
> <alvherre@2ndquadrant.com> wrote:

> > we have a transaction that takes a lock-only multi in table
> > users, and then when we do the second update we don't look it up
> > because ...??
>
> The referencing column value did not change.  (We would not have
> looked up on the first update either, since it also didn't change
> there.)
>
> >  And then this causes the test case not to fail because ..?
>
> The concurrent update of the referencing table is not seen as a
> write conflict (because it didn't actually change).

Okay, but I don't understand why that particular patch fixes the
problem.  That patch was only supposed to skip looking up members of
multixacts when they were not interesting; so it's just a performance
optimization which shouldn't change the behavior of anything.  However
in this case, it is changing behavior and I'm concerned that it might
have introduced other bugs.

Tracing through the test case, what happens is that s1's second update
calls SELECT FOR SHARE of the users tuple (via the RI code); this calls
ExecLockRows which calls heap_lock_tuple which calls
HeapTupleSatisfiesUpdate.  The latter returns HeapTupleUpdated, because
it sees that the tuple has been modified by a transaction that already
committed (s2).  But we already hold a for-key-share lock on the old
version of the tuple -- that HeapTupleUpdated result value should be
examined carefully by heap_lock_tuple to determine that, yes, it can
acquire the row lock without raising an error.

So, if I patch heap_lock_rows like below, the test passes too:

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 559970f..aaf8e8e 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -4005,7 +4005,7 @@ l3:
         UnlockReleaseBuffer(*buffer);
         elog(ERROR, "attempted to lock invisible tuple");
     }
-    else if (result == HeapTupleBeingUpdated)
+    else if (result == HeapTupleBeingUpdated || result == HeapTupleUpdated)
     {
         TransactionId xwait;
         uint16        infomask;

I think heap_lock_rows had that shape (only consider BeingUpdated as a
reason to check/wait) only because it was possible to lock a row that
was being locked by someone else, but it wasn't possible to lock a row
that had been updated by someone else -- which became possible in 9.3.
So this patch is necessary, and not just to fix this one bug.

I need to study the implications of this patch more closely, but I think
in theory it is correct.

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

Alvaro Herrera wrote:

> diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
> index 559970f..aaf8e8e 100644
> --- a/src/backend/access/heap/heapam.c
> +++ b/src/backend/access/heap/heapam.c
> @@ -4005,7 +4005,7 @@ l3:
>          UnlockReleaseBuffer(*buffer);
>          elog(ERROR, "attempted to lock invisible tuple");
>      }
> -    else if (result == HeapTupleBeingUpdated)
> +    else if (result == HeapTupleBeingUpdated || result == HeapTupleUpdated)
>      {
>          TransactionId xwait;
>          uint16        infomask;
>
> I think heap_lock_rows had that shape (only consider BeingUpdated as a
> reason to check/wait) only because it was possible to lock a row that
> was being locked by someone else, but it wasn't possible to lock a row
> that had been updated by someone else -- which became possible in 9.3.
> So this patch is necessary, and not just to fix this one bug.
>
> I need to study the implications of this patch more closely, but I think
> in theory it is correct.

Hmm.  So one thing against this patch is that some results of existing
isolation tests change.  For instance, this one (lock-update-delete):

starting permutation: s2b s1l s2u s2_blocker3 s2c s2_unlock
pg_advisory_lock


step s2b: BEGIN;
step s1l: SELECT * FROM foo WHERE pg_advisory_xact_lock(0) IS NOT NULL AND key = 1 FOR KEY SHARE; <waiting ...>
step s2u: UPDATE foo SET value = 2 WHERE key = 1;
step s2_blocker3: UPDATE foo SET value = 2 WHERE key = 1;
step s2c: COMMIT;
step s2_unlock: SELECT pg_advisory_unlock(0);
pg_advisory_unlock

t
step s1l: <... completed>
key            value

1              2

The initial SELECT is blocked and returns the updated tuple; if I patch
as proposed above, the returned tuple is the *original* tuple (i.e. it
returns value=1 instead).  I think there's room for arguing that that is
the correct result; since the tuple lock acquired by FOR KEY SHARE does
not conflict with the UPDATE, what would be the reason to reject the
original tuple?  In fact, in the permutation that does the
advisory_unlock before the commit, that's exactly what happens (value=1
is returned).

Also, in the repeatable read isolation level, the expected file has this
permutation as failing with "could not serialize" -- but with the patch,
it no longer fails and instead it returns the value=1 tuple instead.
Kevin, what's your opinion on that change?  Is this case supposed to
raise an error or not?

I have a hard time convincing myself that it's acceptable to back-patch
such a change, in any case.  I observed no other regression failure, but
what did change does make me a bit uncomfortable.

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

On Fri, Dec 18, 2015 at 12:53 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

> Hmm.  So one thing against this patch is that some results of existing
> isolation tests change.  For instance, this one (lock-update-delete):
>
> starting permutation: s2b s1l s2u s2_blocker3 s2c s2_unlock

[I had trouble reading your summary -- redone, hopefully better]

        session 2
        ---------
        SELECT pg_advisory_lock(0);
        BEGIN;

session 1
---------
SELECT * FROM foo
  WHERE pg_advisory_xact_lock(0) IS NOT NULL
    AND key = 1 FOR KEY SHARE;
<session 1 blocks>

        UPDATE foo SET value = 2 WHERE key = 1;
        UPDATE foo SET value = 2 WHERE key = 1;
        SELECT pg_advisory_unlock(0);

<session 1 unblocks>

        COMMIT;

> The initial SELECT is blocked and returns the updated tuple; if I patch
> as proposed above, the returned tuple is the *original* tuple (i.e. it
> returns value=1 instead).  I think there's room for arguing that that is
> the correct result; since the tuple lock acquired by FOR KEY SHARE does
> not conflict with the UPDATE, what would be the reason to reject the
> original tuple?

I completely agree -- if SELECT ... FOR KEY SHARE is not blocked,
it should return the original value.  I consider it a bug to do
otherwise.  If it *is* blocked, then it should follow the chain and
show the latest version of the row (or not find the row visible if
it has been deleted).

> In fact, in the permutation that does the advisory_unlock before
> the commit, that's exactly what happens (value=1 is returned).

Right; why should it be different if the commit comes first?

> Also, in the repeatable read isolation level, the expected file has this
> permutation as failing with "could not serialize" -- but with the patch,
> it no longer fails and instead it returns the value=1 tuple instead.
> Kevin, what's your opinion on that change?  Is this case supposed to
> raise an error or not?

At the REPEATABLE READ isolation level, you are only supposed to
get a serialization failure on a write conflict.  I don't see why a
SELECT ... FOR KEY SHARE against the row should count as a write
for that purpose, unless there is a conflicting row lock (including
those acquired by DELETE or UPDATE statements).  At the
SERIALIZABLE transaction isolation level there is no escaping the
fact that there can be some false positives (where a serialization
failure may occur even where it is not strictly necessary), and the
documentation mentions this; but at the REPEATABLE READ isolation
level it is arguably a bug to generate false positives.  If it does
not throw an error, the only valid value to return would be 1.

I don't see a reason that a SERIALIZABLE transaction cannot behave
the same as a REPEATABLE READ transaction for this case, but at
least it would not necessarily be a bug to get a false positive
(unnecessary serialization failure) in that case.

> I have a hard time convincing myself that it's acceptable to back-patch
> such a change, in any case.  I observed no other regression failure, but
> what did change does make me a bit uncomfortable.

I think it is fair to consider it a bug fix, but not necessarily
for a serious enough bug to back-patch, especially if it is
reasonable to think that people might be counting on the current
behavior.  I'm not sure that I buy that anyone will be, though,
especially since a tiny shift in timing that would not generally be
controlled by the user will generate the post-patch value anyway.

It would be interesting to hear whether anyone else thinks that the
old behavior is something someone might be counting on.

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

On Fri, Dec 18, 2015 at 7:53 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
>
> Alvaro Herrera wrote:
>
> > diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
> > index 559970f..aaf8e8e 100644
> > --- a/src/backend/access/heap/heapam.c
> > +++ b/src/backend/access/heap/heapam.c
> > @@ -4005,7 +4005,7 @@ l3:
> >               UnlockReleaseBuffer(*buffer);
> >               elog(ERROR, "attempted to lock invisible tuple");
> >       }
> > -     else if (result == HeapTupleBeingUpdated)
> > +     else if (result == HeapTupleBeingUpdated || result == HeapTupleUpdated)
> >       {
> >               TransactionId xwait;
> >               uint16          infomask;
> >
> > I think heap_lock_rows had that shape (only consider BeingUpdated as a
> > reason to check/wait) only because it was possible to lock a row that
> > was being locked by someone else, but it wasn't possible to lock a row
> > that had been updated by someone else -- which became possible in 9.3.
> > So this patch is necessary, and not just to fix this one bug.

I was surprised as well to see that the initial patch, supposed to be
an optimization, would be fixing this bug.
It's starting to make more sense with your analysis.


> (...)
> I have a hard time convincing myself that it's acceptable to back-patch
> such a change, in any case.  I observed no other regression failure, but
> what did change does make me a bit uncomfortable.

I'm afraid I won't be of much help to assess the consequences of the
patch, the PG source code and internal data structures are still
pretty new to me.

Would it count somehow in the balance that this use case worked fine
in 9.2, seems to be fine with regard to the documented behavior of
row-level locks and REPEATABLE READ isolation level, but suddenly
stopped working in 9.3/9.4? I suppose 9.3 is an old story, but 9.4 has
the same problem and will be around for a while, being the default
version in most LTS/stable distributions.

Thanks so much to both of you for looking further into this bug!

PS: I can confirm that the patch works, but you didn't need my confirmation ;-)

--
Olivier

I'm looking at this open bug again.  I attach two commits; the first one
adds two test cases illustrating the current (broken) behavior, and the
second one adds the fix and changes the test cases to match the new
behavior.  I spent a lot of time trying to find (a) any other
HeapTupleSatisfiesUpdate caller that needed to be changed, and (b)
additional test cases that showed misbehavior, and so far I haven't been
able to come up with any.

No other test case is affected AFAICS.

I intend to push this and backpatch to 9.3.

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

Alvaro Herrera wrote:
> I'm looking at this open bug again.  I attach two commits; the first one
> adds two test cases illustrating the current (broken) behavior, and the
> second one adds the fix and changes the test cases to match the new
> behavior.  I spent a lot of time trying to find (a) any other
> HeapTupleSatisfiesUpdate caller that needed to be changed, and (b)
> additional test cases that showed misbehavior, and so far I haven't been
> able to come up with any.
>
> No other test case is affected AFAICS.
>
> I intend to push this and backpatch to 9.3.

Pushed.

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