Обсуждение: Documenting serializable vs snapshot isolation levels

I'm still casting about to make sure I have my head around the issues
adequately to suggest a documentation update.  Here's my current
understanding.
The below is intended to help define the nature and scope of the
issue, not be the sort of text that belongs in user documentation.
Assume transactions T0, T1, and TN, where TN can be T1 or a different
transaction, and T0 is concurrent with T1 and TN.
Assume non-overlapping logical sets of data x and y (either or both of
which can be empty or not).
Differences in behavior between what is required by the standard for
serializable transactions and what occurs under snapshot isolation can
manifest when T0 reads x and modifies y based on what was read from x,
T1 modifies x in a way that would affect T0's modification to y, TN
reads y, and T1's modifications are visible to TN, either because it
is the same transaction or because T1 committed before TN got its
snapshot.
I think that transient SELECT anomalies can occur if TN also reads x
without modifying anything based on y.  My example of an incomplete
receipt journal is a case of this.
I think that persistent data integrity can be compromised when TN
modifies data based on y.  The example currently in the documentation
is a special case of this, where the modified data is part of x. 
Another example would be where someone attempted to maintain
referential integrity using snapshot isolation without additional
locks, T1 is TN, and one transaction checked for children before
deleting the parent while the other checked for a parent before
inserting a child.  Many other types of integrity enforcement would
fail if serializable behavior is assumed, such as ensuring the
existence of some minimum number of rows which meet certain criteria
(e.g., staffing) or ensuring that the sum of some numeric column for a
range of rows stays above a minimum amount (e.g., banking).
My initial intuition that simply applying the same locks which
guarantee serializable behavior in a non-snapshot database to a
snapshot database would guarantee integrity is just plain wrong. 
There are a number of academic papers suggesting techniques for
handling these issues.  Unfortunately, what I've seen so far suggests
that there are three main approaches available under PostgreSQL, all
with significant cost of one type or another.
(1)  A rigorous analysis of all queries allowed against the database
to determine where transaction conflicts can occur, with expertise
needed to resolve each.  Downsides are that ad hoc queries can cause
anomalies and that when new queries are introduced a time-intensive
review of all queries may need to be done, and locking changes may be
needed in programs which weren't otherwise modified.
(2)  A less rigorous examination might suffice, if rather brutal
table-level locks are applied mechanically.  Even this requires
knowledge of what's happening outside the area where the change is
being made.  If the receipt example is solved by adding a table lock
on the receipt table to the code which updates the control record, the
control record update must be modified if some other code modifies
some new table (say, receipt_voids) based on looking at the control
record to determine what to do.
(3)  A finer-grained approach would be to make no-effect updates to
rows to lock them if they are to be read for purposes of updating
something else in the transaction.  This could have a high cost in
disk access and table bloat.  It has the advantage of providing a
simple technique which, if applied consistently, doesn't require
knowledge of software beyond what is under development.
Of course, if the anomalies are infrequent enough and of a nature
which can be tolerated, the whole issue can be ignored, or monitored
for manual correction.
Any suggestions for refining the description of where the anomalies
can occur or how best to work around any particular classes of them
are welcome.  I'm particularly interested in practical methodologies
for ensuring that no holes are left for failures of business rules to
apply.  There are so many papers on the topic that I'm not sure where
to go next.
I hope someone can show me something good I've missed so far.
I haven't lost track of the language suggested by Robert Haas, which I
think frames the issue nicely.  I just want to follow it with a
reasonable description of where it's an issue and how to handle it.
-Kevin

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:

> (3)  A finer-grained approach would be to make no-effect updates to
> rows to lock them if they are to be read for purposes of updating
> something else in the transaction.  This could have a high cost in
> disk access and table bloat.  It has the advantage of providing a
> simple technique which, if applied consistently, doesn't require
> knowledge of software beyond what is under development.

"no-effect updates" would be just the same as SELECT FOR UPDATE

However this has the same problem that we previously discussed where someone
can still add new records which would have changed the results of the query.

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's Slony Replication
support!

On Mon, Dec 29, 2008 at 9:28 PM, Gregory Stark <stark@enterprisedb.com> wrote:
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> (3)  A finer-grained approach would be to make no-effect updates to
>> rows to lock them if they are to be read for purposes of updating
>> something else in the transaction.  This could have a high cost in
>> disk access and table bloat.  It has the advantage of providing a
>> simple technique which, if applied consistently, doesn't require
>> knowledge of software beyond what is under development.
>
> "no-effect updates" would be just the same as SELECT FOR UPDATE

...except that SELECT FOR UPDATE won't create table bloat, or as much
I/O... I think?

> However this has the same problem that we previously discussed where someone
> can still add new records which would have changed the results of the query.

...Robert

>>> "Robert Haas" <robertmhaas@gmail.com> wrote: 
> On Mon, Dec 29, 2008 at 9:28 PM, Gregory Stark
<stark@enterprisedb.com> wrote:
>> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>>> (3)  A finer-grained approach would be to make no-effect updates
to
>>> rows to lock them if they are to be read for purposes of updating
>>> something else in the transaction.  This could have a high cost in
>>> disk access and table bloat.  It has the advantage of providing a
>>> simple technique which, if applied consistently, doesn't require
>>> knowledge of software beyond what is under development.
>>
>> "no-effect updates" would be just the same as SELECT FOR UPDATE
> 
> ...except that SELECT FOR UPDATE won't create table bloat, or as
much
> I/O... I think?
The effects are different, I think, in that there isn't a
serialization failure in some conflict cases where you would get one
with actual updates.  I found a paper on how to use updates to provide
serializable transactions in a snapshot database, and I'd have to
review closely to see how that difference affected the technique.  I
had been thinking that the WAL generation and bloat issues made the
technique pretty iffy, but if SELECT FOR UPDATE suffices in place of
most of the proposed updates, it just might be feasible.
-Kevin

> The effects are different, I think, in that there isn't a
> serialization failure in some conflict cases where you would get one
> with actual updates.  I found a paper on how to use updates to provide
> serializable transactions in a snapshot database, and I'd have to
> review closely to see how that difference affected the technique.  I
> had been thinking that the WAL generation and bloat issues made the
> technique pretty iffy, but if SELECT FOR UPDATE suffices in place of
> most of the proposed updates, it just might be feasible.

In fact, I think SELECT FOR SHARE is enough.  That will give you
better concurrency, since it will block only updates and not
concurrent read transactions.

...Robert

>>> "Robert Haas" <robertmhaas@gmail.com> wrote: 
>>  The effects are different, I think, in that there isn't a
>> serialization failure in some conflict cases where you would get
one
>> with actual updates.  I found a paper on how to use updates to
provide
>> serializable transactions in a snapshot database, and I'd have to
>> review closely to see how that difference affected the technique. 
I
>> had been thinking that the WAL generation and bloat issues made the
>> technique pretty iffy, but if SELECT FOR UPDATE suffices in place
of
>> most of the proposed updates, it just might be feasible.
> 
> In fact, I think SELECT FOR SHARE is enough.  That will give you
> better concurrency, since it will block only updates and not
> concurrent read transactions.
When I mentioned my initial intuition up-thread, it was exactly that. 
In tests, I quickly came up with two issues that make a general
solution harder to describe.  One is that (in the upstream jargon) if
TN and T1 are the same transaction, this totally fails to provide
serializable behavior.  (I can provide details for every case I
describe if people want them, but really....)  The other issue is that
neither FOR SHARE or FOR UPDATE is allowed in some contexts which
matter -- like subqueries and aggregate functions.
I'm still trying to sort it all out, but I welcome all suggestions --
it's entirely possible that I'm missing something that will simplify
the whole issue for me.
Thanks,
-Kevin

On Mon, 2008-12-29 at 18:13 -0600, Kevin Grittner wrote:

> I hope someone can show me something good I've missed so far.

You're viewing this in problem-exposed language, unintentionally I'm
sure. My viewpoint on this is that database concurrency is a big issue,
but that the way we do things round here is a major leap forward on the
way things happened previously (and still do in older-style DBMS).

Our approach to serializable queries is an optimistic one in two ways:
It covers most cases, but not all theoretical cases. It also avoids
locks by default. 

Those are good things, with many benefits. If we put the default the
other way around, developers would spend much more time re-tuning
queries that had locked each other out. So I would say we choose to
avoid locking-on-every-query with good reason. Just look at the
facilities DB2 provides to avoid it. Ugh-ly.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

>>> Simon Riggs <simon@2ndQuadrant.com> wrote: 
> On Mon, 2008-12-29 at 18:13 -0600, Kevin Grittner wrote:
> 
>> I hope someone can show me something good I've missed so far.
> 
> You're viewing this in problem-exposed language, unintentionally I'm
> sure.
Hmmm....  My meaning was, "I hope someone can point me to a good paper
summarizing the nature and scope of possible anomalies, to save me
time casting about or thinking it through."  If that came of as
"there's nothing good about the current approach," I apologize.  That
was certainly not what I meant to convey.
> My viewpoint on this is that database concurrency is a big issue,
> but that the way we do things round here is a major leap forward on
the
> way things happened previously (and still do in older-style DBMS).
I absolutely agree.
> Our approach to serializable queries is an optimistic one in two
ways:
> It covers most cases, but not all theoretical cases.
Not sure about "most".  Referential integrity is a pretty common use
case, and it is not covered without explicit locking.  Many other
common use cases are not, either.  I agree many are, and that the rest
can be worked around easily enough that I wouldn't want to see
blocking introduced to the degree that non-MVCC databases use for
serializable access.
Thanks for pointing out a bad choice of words; no need for this to
become muddled over simple misunderstandings.
-Kevin

> Not sure about "most".  Referential integrity is a pretty common use
> case, and it is not covered without explicit locking.  Many other
> common use cases are not, either.  I agree many are, and that the rest
> can be worked around easily enough that I wouldn't want to see
> blocking introduced to the degree that non-MVCC databases use for
> serializable access.

What do you mean by referential integrity?  I don't believe you can
construct a foreign key problem at any transaction isolation level.

...Robert

>>> "Robert Haas" <robertmhaas@gmail.com> wrote: 
>>  Not sure about "most".  Referential integrity is a pretty common
use
>> case, and it is not covered without explicit locking.  Many other
>> common use cases are not, either.  I agree many are, and that the
rest
>> can be worked around easily enough that I wouldn't want to see
>> blocking introduced to the degree that non-MVCC databases use for
>> serializable access.
> 
> What do you mean by referential integrity?  I don't believe you can
> construct a foreign key problem at any transaction isolation level.
I mean that if someone attempts to maintain referential integrity with
SQL code, without using explicit locks, it is not reliable. 
Presumably the implementation of foreign keys in PostgreSQL takes this
into account and blocks the kind of behavior shown below.  This
behavior would not occur with true serializable transactions.
-- setup
create table parent (parid int not null primary key);
create table child (chiid int not null primary key, parid int);
insert into parent values (1);

-- connection 1 (start of T0)
start transaction isolation level serializable;
select * from parent where parid = 1;
-- parent row exists; OK to insert child.
insert into child values (100, 1);

-- connection 2 (T1)
start transaction isolation level serializable;
select * from child where parid = 1;
-- child row doesn't exist; OK to delete parent
delete from parent where parid = 1;
commit;

-- connection 1 (end of T0)
commit transaction;

-- database now lacks referential integrity
select * from parent;parid
-------
(0 rows)

select * from child;chiid | parid
-------+-------  100 |     1
(1 row)

-Kevin

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> What do you mean by referential integrity?  I don't believe you can
>> construct a foreign key problem at any transaction isolation level.
> I mean that if someone attempts to maintain referential integrity with
> SQL code, without using explicit locks, it is not reliable. 
> Presumably the implementation of foreign keys in PostgreSQL takes this
> into account and blocks the kind of behavior shown below.  This
> behavior would not occur with true serializable transactions.

IIRC the RI code has to fudge the normal serializable-snapshot behavior
in order to guarantee no constraint violation --- it has to be aware of
concurrent changes that would otherwise be invisible to a serializable
transaction.
        regards, tom lane

> I mean that if someone attempts to maintain referential integrity with
> SQL code, without using explicit locks, it is not reliable.
> Presumably the implementation of foreign keys in PostgreSQL takes this
> into account and blocks the kind of behavior shown below.  This
> behavior would not occur with true serializable transactions.

I see your point now, but I don't think we're really getting anywhere
here.   Doing it this way rather than using a foreign key constraint
is dumb, and a foreign key constraint works fine - so I think Simon's
statement that our approach works in most cases is 100% accurate.
With respect to your example here, we're right back to what I said way
upthread: if you're worried about concurrent updates or deletes,
SELECT ... FOR SHARE is sufficient.  If you're worried about
concurrent inserts, as you are here (delete from parent wants to make
sure no row can be concurrently inserted into child), you need to take
a SHARE lock on the table into which you want to prevent inserts.

As you pointed out, SELECT ... FOR SHARE isn't always available; when
it isn't, you can either rewrite the query - if that's feasible - or
take a SHARE lock on the table instead.

It really seems to me that we're going around in circles here.  I
don't feel that statements like this are advancing the dialogue one
bit:

> Referential integrity is a pretty common use case, and it is not covered without explicit locking.  Many other
> common use cases are not, either.

I believe this to be plain false.  Referential integrity as I
understand it (i.e. foreign key constraints, rather than some
half-baked home grown approach) works fine without explicit locking
and without even changing the transaction isolation level.  The
assertion that there are many other common use cases that are not
covered is hand-waving unsupported by evidence.  The only problems
you've raised so far are well-known problems in database theory; I
learned about them from Jim Gray's 1993 "Transaction Processing", but
that's about a 700 page book.  I suspect there are shorter texts that
you could read to pick up the main ideas but I'm not familiar with
them so I can't provide any pointers.

On further review, I actually think that our documentation is pretty
clear about this topic, too.  Everything we've talked about thus far
all seems to be spelled out in chapter 13:

http://www.postgresql.org/docs/8.3/interactive/mvcc-intro.html
http://www.postgresql.org/docs/8.3/interactive/transaction-iso.html
http://www.postgresql.org/docs/8.3/interactive/explicit-locking.html
http://www.postgresql.org/docs/8.3/interactive/applevel-consistency.html

Note in particular section 13.2.2.1. Serializable Isolation versus
True Serializability

...Robert

On Fri, 2009-01-02 at 13:47 -0500, Tom Lane wrote:
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
> >> What do you mean by referential integrity?  I don't believe you can
> >> construct a foreign key problem at any transaction isolation level.
>  
> > I mean that if someone attempts to maintain referential integrity with
> > SQL code, without using explicit locks, it is not reliable. 
> > Presumably the implementation of foreign keys in PostgreSQL takes this
> > into account and blocks the kind of behavior shown below.  This
> > behavior would not occur with true serializable transactions.
> 
> IIRC the RI code has to fudge the normal serializable-snapshot behavior
> in order to guarantee no constraint violation --- it has to be aware of
> concurrent changes that would otherwise be invisible to a serializable
> transaction.

...just to add that this is exactly as required by SQL Standard, i.e. RI
works in Read Committed mode even within a Serializable transaction.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

I've rearranged the sequence of some lines in the previous post to
facilitate discussion.  I hope no offense is taken.
>>> "Robert Haas" <robertmhaas@gmail.com> wrote: 
> On further review, I actually think that our documentation is pretty
> clear about this topic, too.  Everything we've talked about thus far
> all seems to be spelled out in chapter 13:
> 
> http://www.postgresql.org/docs/8.3/interactive/mvcc-intro.html
> http://www.postgresql.org/docs/8.3/interactive/transaction-iso.html
> http://www.postgresql.org/docs/8.3/interactive/explicit-locking.html
>
http://www.postgresql.org/docs/8.3/interactive/applevel-consistency.html
> 
> Note in particular section 13.2.2.1. Serializable Isolation versus
> True Serializability
I read all of the above over very carefully, several times, before
starting this thread.  These are precisely the sections I feel could
use correction and improvement.
> Doing it this way rather than using a foreign key constraint
> is dumb, and a foreign key constraint works fine
The point is that it is something that would work reliably under
serializable isolation, but not under snapshot isolation.  I picked it
merely because it is a simple integrity test that someone might choose
to enforce in a trigger in some other database, and might not
recognize it as an unreliable technique in PostgreSQL.  Dumb or not,
they may lose integrity after moving to PostgreSQL if they miss this,
and I propose documenting the issue to assist people.
> The only problems
> you've raised so far are well-known problems in database theory; I
> learned about them from Jim Gray's 1993 "Transaction Processing",
but
> that's about a 700 page book.  I suspect there are shorter texts
that
> you could read to pick up the main ideas but I'm not familiar with
> them so I can't provide any pointers.
> With respect to your example here, we're right back to what I said
way
> upthread: if you're worried about concurrent updates or deletes,
> SELECT ... FOR SHARE is sufficient.  If you're worried about
> concurrent inserts, as you are here (delete from parent wants to
make
> sure no row can be concurrently inserted into child), you need to
take
> a SHARE lock on the table into which you want to prevent inserts.
This advice seems consistent with the current PostgreSQL documentation
(cited above) and might lead one to believe that in the example you
reference, adding a FOR SHARE to the SELECT which confirms the
existence of the parent row, and a LOCK TABLE on the child table at
the start of the transaction which does the DELETE of the parent would
provide integrity.  It does not; try it if you want confirmation.  It
does introduce blocking, but after the block clears, the result in the
database is identical to the example as originally posted.  This is
why I think the documentation could use enhancement.
> It really seems to me that we're going around in circles here.
Agreed.  I guess I contributed to that by questioning whether "most"
or "many" was a more appropriate adjective, which is pretty
irrelevant, really.  I'll try to stay focused on examples of things
that work in one environment and don't in the other, with tips to get
the desired behavior within PostgreSQL.  I have come up with many more
examples of these than I have posted on-list, but posting every single
example doesn't seem valuable to me.  I'm trying to generalize to
provide useful guidelines, but feel sure that I'm re-inventing the
wheel here.
Thanks for suggesting Jim Gray's "Transaction Processing".  I'll look
for it.  If it's framing things from a theoretical point of view,
there will be some work necessary to distill it down to the concise
and practical advice which I've found necessary to effectively guide
application programmers, but at least I can do it with more confidence
that I've covered all the relevant ground.
-Kevin