User-facing aspects of serializable transactions
I want to try to get agreement that it would be a good idea to
implement serializable transactions, and what that would look like
from the user side. At this point, we should avoid discussions of
whether it's possible or how it would be implemented, but focus on
what that would look like and whether it would be desirable.
Let's start with reasons:
(1) The standard has always required that the serializable
transaction isolation mode be supported. We don't comply with recent
versions of the standard, which have changed the definition of this
mode to go beyond the four specific anomalies mentioned, and now
requires that any execution of concurrent serializable transactions
must yield results consistent with some serial execution of those
transactions. Being able to show compliance with a significant point
in the standard has value, all by itself.
(2) The standard requires this because it is the only cost-effective
way to ensure data integrity in some environments, particularly those
with a large number of programmers, tables, and queries; and which
have complex data integrity rules. Basically, any serializable
transaction which can be shown to do the right thing when run by
itself will automatically, with no additional development effort, do
the right thing when run in any arbitrary mix of concurrent
transactions. This feature would be likely to make PostgreSQL a
viable option in some shops where it currently isn't.
(3) Many other database products provide serializable transactions,
including DB2, Microsoft SQL Server, and Sybase ASE. Some MVCC
databases, like recent Microsoft SQL Server releases, allow the user
to choose snapshot isolation or full serializable isolation.
(4) It may simplify the code to implement PostgreSQL foreign key
constraints and/or improve concurrency in the face of such
constraints.
(5) It may simplify application code written for PostgreSQL and
improve concurrency of transactions with possible conflicts, since
explicit locks will not need to be taken, and blocking currently
resulting from explicit locks can be eliminated.
Proposed user visible aspects are:
(A) Well known anomalies possible under snapshot isolation will not
be possible among transactions running at the serializable transaction
isolation level, with no need to explicitly take locks to prevent
them.
(B) While no blocking will occur between reads and writes, certain
combinations of reads and writes will cause a rollback with a SQLSTATE
which indicates a serialization failure. Any transaction running at
this isolation level must be prepared to deal with these.
(C) One or more GUCs will be added to control whether the new
behavior is used when serializable transaction isolation is requested
or whether, for compatibility with older PostgreSQL releases, the
transaction actually runs with snapshot isolation. In any event, a
request for repeatable read mode will provide the existing snapshot
isolation mode.
(D) It may be desirable to use these techniques, rather than current
techniques, to enforce the referential integrity specified by foreign
keys. If this is done, enforcement would produce less blocking, but
might increase rollbacks due to serialization failures. Perhaps this
should be controlled by a separate GUC.
(E) Since there will be a trade-off between the overhead of finer
granularity in tracking locks and the reduced number of rollbacks at a
finer granularity, it might be desirable to have a GUC to control
default granularity and a table property which can override the
default for individual tables. (In practice, with a different
database product which supported something like this, we found our
best performance with page level locks on all but a few small,
frequently updated tables -- which we set to row level locking.)
(F) Databases clusters making heavy use of serializable transactions
would need to boost the number of locks per transaction.
Thoughts?
-Kevin
On Wed, 2009-05-27 at 15:34 -0500, Kevin Grittner wrote:
(2) The standard requires this because it is the only cost-effective
way to ensure data integrity in some environments, particularly those
with a large number of programmers, tables, and queries; and which
have complex data integrity rules. Basically, any serializable
transaction which can be shown to do the right thing when run by
itself will automatically, with no additional development effort, do
the right thing when run in any arbitrary mix of concurrent
transactions. This feature would be likely to make PostgreSQL a
viable option in some shops where it currently isn't.
+1. It would be great if this could be accomplished with reasonable
performance, or at least predictable performance.
(C) One or more GUCs will be added to control whether the new
behavior is used when serializable transaction isolation is requested
or whether, for compatibility with older PostgreSQL releases, the
transaction actually runs with snapshot isolation. In any event, a
request for repeatable read mode will provide the existing snapshot
isolation mode.
I'm not sure a GUC is the best way here, are you talking about as a
migration path, or something that would exist forever?
Regards,
Jeff Davis
Jeff Davis <pgsql@j-davis.com> wrote:
On Wed, 2009-05-27 at 15:34 -0500, Kevin Grittner wrote:
(C) One or more GUCs will be added to control whether the new
behavior is used when serializable transaction isolation is
requested or whether, for compatibility with older PostgreSQL
releases, the transaction actually runs with snapshot isolation.
In any event, a request for repeatable read mode will provide the
existing snapshot isolation mode.I'm not sure a GUC is the best way here, are you talking about as a
migration path, or something that would exist forever?
I've gotten the distinct impression that some would prefer to continue
to use their existing techniques under snapshot isolation. I was sort
of assuming that they would want a GUC to default to legacy behavior
with a new setting for standard compliant behavior.
Another alternative here would be to just change a request for a
serializable transation to give you a serializable transaction, and
document that the existing snapshot isolation is now available only by
requesting repeatable read mode. Right now you get snapshot isolation
mode on a request for either repeatable read mode or serializable
mode.
I think that many people only use read committed; they would not be
impacted at all.
What do you think would be best here?
-Kevin
On Wed, 2009-05-27 at 18:54 -0500, Kevin Grittner wrote:
I've gotten the distinct impression that some would prefer to continue
to use their existing techniques under snapshot isolation. I was sort
of assuming that they would want a GUC to default to legacy behavior
with a new setting for standard compliant behavior.
That sounds like the "migration path" sort of GUC, which sounds
reasonable to me.
But what about all the other possible behaviors that were brought up
(mentioned in more detail in [1]http://archives.postgresql.org/pgsql-hackers/2009-05/msg01128.php), such as:
1. implementation of the paper's technique sans predicate locking, that
would avoid more serialization anomalies but not all?
2. various granularities of predicate locking?
Should these be things the user controls per-transaction? If so, how?
Regards,
Jeff Davis
[1]: http://archives.postgresql.org/pgsql-hackers/2009-05/msg01128.php
Jeff Davis <pgsql@j-davis.com> writes:
On Wed, 2009-05-27 at 18:54 -0500, Kevin Grittner wrote:
I've gotten the distinct impression that some would prefer to continue
to use their existing techniques under snapshot isolation. I was sort
of assuming that they would want a GUC to default to legacy behavior
with a new setting for standard compliant behavior.
That sounds like the "migration path" sort of GUC, which sounds
reasonable to me.
But what about all the other possible behaviors that were brought up
(mentioned in more detail in [1]), such as:
1. implementation of the paper's technique sans predicate locking, that
would avoid more serialization anomalies but not all?
2. various granularities of predicate locking?
Should these be things the user controls per-transaction? If so, how?
I think it's important to draw a distinction between performance issues
and correctness issues. True serializability vs snapshot
serializability is a fundamental behavioral issue, whereas fooling
around with lock granularity might improve performance but it doesn't
make the difference between a correct application and an incorrect one.
A lesson that I think we've learned the hard way over the past few years
is that GUCs are fine for controlling performance issues, but you expose
yourself to all sorts of risks if you make fundamental semantics vary
depending on a GUC.
Putting those two thoughts together, I would say that the right thing
is
* SET TRANSACTION ISOLATION LEVEL SERIALIZABLE should mean what the spec
says.
* SET TRANSACTION ISOLATION LEVEL something-else should provide our
current snapshot-driven behavior. I don't have a strong feeling about
whether "something-else" should be spelled REPEATABLE READ or SNAPSHOT,
but lean slightly to the latter.
* Anything else you want to control should be a GUC, as long as it
doesn't affect any correctness properties.
regards, tom lane
On Wed, May 27, 2009 at 7:54 PM, Kevin Grittner
<Kevin.Grittner@wicourts.gov> wrote:
Jeff Davis <pgsql@j-davis.com> wrote:
On Wed, 2009-05-27 at 15:34 -0500, Kevin Grittner wrote:
(C) One or more GUCs will be added to control whether the new
behavior is used when serializable transaction isolation is
requested or whether, for compatibility with older PostgreSQL
releases, the transaction actually runs with snapshot isolation.
In any event, a request for repeatable read mode will provide the
existing snapshot isolation mode.I'm not sure a GUC is the best way here, are you talking about as a
migration path, or something that would exist forever?I've gotten the distinct impression that some would prefer to continue
to use their existing techniques under snapshot isolation. I was sort
of assuming that they would want a GUC to default to legacy behavior
with a new setting for standard compliant behavior.Another alternative here would be to just change a request for a
serializable transation to give you a serializable transaction, and
document that the existing snapshot isolation is now available only by
requesting repeatable read mode. Right now you get snapshot isolation
mode on a request for either repeatable read mode or serializable
mode.I think that many people only use read committed; they would not be
impacted at all.What do you think would be best here?
I think we should introduce a new value for SET TRANSACTION ISOLATION
LEVEL, maybe SNAPSHOT, intermediate between READ COMMITTED and
SERIALIZABLE.
IOW, SET TRANSACTION ISOLATION LEVEL READ COMMITTED should do what it
does now. SET TRANSACTION ISOLATION LEVEL SNAPSHOT should do what
SERIALIZABLE currently does, which is take and keep the same snapshot
for the whole transaction. And SERIALIZABLE should do that, plus
whatever new and better stuff we add.
...Robert
Jeff Davis <pgsql@j-davis.com> wrote:
1. implementation of the paper's technique sans predicate locking,
that would avoid more serialization anomalies but not all?
I saw that as a step along the way to support for fully serializable
transactions. If covered by a "migration path" GUC which defaulted to
current behavior, it would allow testing of all of the code except the
predicate lock tracking (before the predicate locking code was
created), in order to give proof of concept, check performance impact
of that part of the code, etc. I wasn't thinking that it would be a
useful long-term option without the addition of the predicate locks.
Arguably, it would actually be a very weak partial implemenation of
predicate locking, in that it would get a non-blocking lock on tuples
viewed, up to some limit. At the point where we added an escalation
to table locking for the limit, started with the table lock when we
knew it was a table scan, and locked the index range for an index
scan, we would actually have achieved fully serializable transactions.
2. various granularities of predicate locking?
I haven't seen that configurable by transaction, and I'm not entirely
sure that would make sense. I have seen products where a default
granularity was set with the equivalent of a global GUC, and it could
be overridden for particular tables. I see such a setting as the
default for access to rows accessed through indexes. If there is a
table scan, the lock would have to start at the table level,
regardless of settings. If too many locks accrue for one transaction
against a table at one granularity, those locks would need to be
consolidated to a coarser granularity to avoid exhausting lock
tracking space in RAM.
We're slipping into implementation details here, but I'm not sure how
we can discuss the GUCs needed without at least touching on that....
-Kevin
On Wed, 2009-05-27 at 20:38 -0400, Tom Lane wrote:
A lesson that I think we've learned the hard way over the past few years
is that GUCs are fine for controlling performance issues, but you expose
yourself to all sorts of risks if you make fundamental semantics vary
depending on a GUC.
I agree with the philosophy here.
Putting those two thoughts together, I would say that the right thing
is* SET TRANSACTION ISOLATION LEVEL SERIALIZABLE should mean what the spec
says.* SET TRANSACTION ISOLATION LEVEL something-else should provide our
current snapshot-driven behavior. I don't have a strong feeling about
whether "something-else" should be spelled REPEATABLE READ or SNAPSHOT,
but lean slightly to the latter.* Anything else you want to control should be a GUC, as long as it
doesn't affect any correctness properties.
But that still leaves out another behavior which avoids some of the
serialization anomalies currently possible, but still does not guarantee
true serializability (that is: implementation of the paper's technique
sans predicate locking). Is that behavior useful enough to include?
Just trying to come up with a name for that might be challenging.
Regards,
Jeff Davis
Jeff Davis <pgsql@j-davis.com> writes:
On Wed, 2009-05-27 at 20:38 -0400, Tom Lane wrote:
* Anything else you want to control should be a GUC, as long as it
doesn't affect any correctness properties.
But that still leaves out another behavior which avoids some of the
serialization anomalies currently possible, but still does not guarantee
true serializability (that is: implementation of the paper's technique
sans predicate locking). Is that behavior useful enough to include?
Hmm, what I gathered was that that's not changing any basic semantic
guarantees (and therefore is okay to control as a GUC). But I haven't
read the paper so maybe I'm missing something.
regards, tom lane
Robert Haas <robertmhaas@gmail.com> wrote:
I think we should introduce a new value for SET TRANSACTION
ISOLATION
LEVEL, maybe SNAPSHOT, intermediate between READ COMMITTED and
SERIALIZABLE.
The standard defines such a level, and calls it REPEATABLE READ.
Snapshot semantics are more strict than required for that level, which
is something you are allowed to get when you request a given level, so
it seems clear to me that when you request REPEATABLE READ mode, you
should get our current snapshot behavior. I'm not clear on what the
benefit would be of aliasing that with SNAPSHOT. If there is a
benefit, fine; if not, why add it?
-Kevin
On Wed, 2009-05-27 at 19:51 -0500, Kevin Grittner wrote:
Jeff Davis <pgsql@j-davis.com> wrote:
1. implementation of the paper's technique sans predicate locking,
that would avoid more serialization anomalies but not all?I saw that as a step along the way to support for fully serializable
transactions. If covered by a "migration path" GUC which defaulted to
current behavior, it would allow testing of all of the code except the
predicate lock tracking (before the predicate locking code was
created), in order to give proof of concept, check performance impact
of that part of the code, etc. I wasn't thinking that it would be a
useful long-term option without the addition of the predicate locks.
OK, if that behavior is not ultimately useful, then I retract my
question.
We still need to know whether to use a GUC at all -- it won't actually
break applications to offer true serializability, it will only impact
performance.
Regards,
Jeff Davis
Tom Lane <tgl@sss.pgh.pa.us> wrote:
Hmm, what I gathered was that that's not changing any basic semantic
guarantees (and therefore is okay to control as a GUC). But I
haven't read the paper so maybe I'm missing something.
The paper never suggests attempting these techniques without a
predicate locking implementation. It was just something Robert Haas
noticed during our discussion at the bar (and he wasn't even consuming
any alcohol that night!) that it would be a possible development path.
I don't think either of us sees it as a useful end point.
Basically, if you just took out locks on the rows you happened to read
(rather than doing proper predicate locking) you would still prevent
some anomalies, in a more-or-less predictable and controllable way. I
think we both felt that the predicate locking might be the hardest
part to implement in PostgreSQL, so having such a proof of concept
partial implemenation without first implementing predicate locking
might fit with the "series of smaller patches" approach generally
preferred by the PostgreSQL developers.
-Kevin
On Wed, 2009-05-27 at 20:55 -0400, Tom Lane wrote:
Hmm, what I gathered was that that's not changing any basic semantic
guarantees (and therefore is okay to control as a GUC). But I haven't
read the paper so maybe I'm missing something.
On second read of this comment:
http://archives.postgresql.org/pgsql-hackers/2009-05/msg01128.php
it says "reduce the frequency of serialization anomalies", which doesn't
necessarily mean that it makes new guarantees, I suppose. I should have
gone to the original source.
Anyway, it's a moot point, because apparently that's just a possible
step along the way toward true serializability, and doesn't need to be
separately distinguished.
Regards,
Jeff Davis
On Wed, May 27, 2009 at 9:00 PM, Kevin Grittner
<Kevin.Grittner@wicourts.gov> wrote:
Robert Haas <robertmhaas@gmail.com> wrote:
I think we should introduce a new value for SET TRANSACTION
ISOLATION
LEVEL, maybe SNAPSHOT, intermediate between READ COMMITTED and
SERIALIZABLE.The standard defines such a level, and calls it REPEATABLE READ.
Snapshot semantics are more strict than required for that level, which
is something you are allowed to get when you request a given level, so
it seems clear to me that when you request REPEATABLE READ mode, you
should get our current snapshot behavior. I'm not clear on what the
benefit would be of aliasing that with SNAPSHOT. If there is a
benefit, fine; if not, why add it?
I guess my point is that we want to keep the two transaction isolation
levels we have now and add a third one that is "above" what we
currently call SERIALIZABLE. I don't much care what we call them.
...Robert
On 28 May 2009, at 01:51, "Kevin Grittner"
<Kevin.Grittner@wicourts.gov> wrote:
At the point where we added an escalation
to table locking for the limit, started with the table lock when we
knew it was a table scan, and locked the index range for an index
scan,
I still think you're stuck in the mssql/sybase mode of thought here.
Postgres supports a whole lot more scan types than just these two and
many of them use multiple indexes or indexes that don't correspond to
ranges of key values at all.
I think you have to forget about any connection between predicates and
either indexes or scan types. You need a way to represent predicates
which can be stored and looked up independently of any indexes.
Without any real way to represent predicates this is all pie in the
sky. The reason we don't have predicate locking is because of this
problem which it sounds like we're no closer to solving.
Greg Stark <greg.stark@enterprisedb.com> writes:
Without any real way to represent predicates this is all pie in the
sky. The reason we don't have predicate locking is because of this
problem which it sounds like we're no closer to solving.
Yeah. The fundamental problem with all the "practical" approaches I've
heard of is that they only work for a subset of possible predicates
(possible WHERE clauses). The idea that you get true serializability
only if your queries are phrased just so is ... icky. So icky that
it doesn't sound like an improvement over what we have.
regards, tom lane
--
Greg
On 28 May 2009, at 02:49, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Greg Stark <greg.stark@enterprisedb.com> writes:
Without any real way to represent predicates this is all pie in the
sky. The reason we don't have predicate locking is because of this
problem which it sounds like we're no closer to solving.Yeah. The fundamental problem with all the "practical" approaches
I've
heard of is that they only work for a subset of possible predicates
(possible WHERE clauses). The idea that you get true serializability
only if your queries are phrased just so is ... icky. So icky that
it doesn't sound like an improvement over what we have.
I think you get "true serializability" in the sense that you take out
a full table lock on every read. I.e. Your transactions end up
actually serialized... Well it would be a bit weaker than that due to
the weak read-locks but basically you would get random spurious
serialization failures which can't be explained by inspecting the
transactions without understanding the implementation.
Greg Stark <greg.stark@enterprisedb.com> wrote:
Postgres supports a whole lot more scan types than just these two
and many of them use multiple indexes or indexes that don't
correspond to ranges of key values at all.
Well, certainly all of the plans I've looked at which use btree
indexes could be handled this way. The fact that the index is scanned
as part of a bitmap process doesn't affect the logic at all, as far as
I can see. Do you see something I'm missing in regard to the btree
indexes?
In regard to other index types, if there is no way to note a GIN scan
such as
Index Cond: (text_tsv @@ '''amicus'' & ''brief'''::tsquery)
in a way that can be compared to DML operations, well, that just
means that some other type of lock would have to be used which is
broad enough to cover it. A table lock certainly would. In this
case, a column lock would be more precise and less likely to generate
false positives, so perhaps that will be found to be needed in the
tuning phase.
Although, looking at it, I would think that a predicate lock on a
condition such as this could be tested by seeing if there is a
difference in the truth of the test between "before" and "after"
images. That may well be naive, but I doubt that we've exhausted the
possibilities yet.
I think you have to forget about any connection between predicates
and either indexes or scan types. You need a way to represent
predicates which can be stored and looked up independently of any
indexes.
Sure. Heap or index pages, tables, columns, table segments -- there
are many options. We can clearly get correct behavior; the question
is about how best to tune it. That's why I was leaning toward an
initial "correct but crude" implementation, building up a large set of
tests for correctness, and then trying different approaches to
balancing the overhead of more accurate tracking against the cost of
dealing with transaction restarts.
Without any real way to represent predicates this is all pie in the
sky
And this is 180% opposite from what I just heard at PGCon should be
the focus of discussion at this point. Let's get agreement on what
would be nice user-facing behavior first. You can always critique
implementation suggestions later. Although, looking back I guess I
provoked this by lapsing into thoughts about an implementation path,
so I guess this one's on me. Apologies.
I tend to believe that if Microsoft can handle this, the PostgreSQL
developer community can get there, too -- even if we do have fancier
indexes.
-Kevin
On Wed, May 27, 2009 at 9:49 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Greg Stark <greg.stark@enterprisedb.com> writes:
Without any real way to represent predicates this is all pie in the
sky. The reason we don't have predicate locking is because of this
problem which it sounds like we're no closer to solving.Yeah. The fundamental problem with all the "practical" approaches I've
heard of is that they only work for a subset of possible predicates
(possible WHERE clauses). The idea that you get true serializability
only if your queries are phrased just so is ... icky. So icky that
it doesn't sound like an improvement over what we have.
I think we're veering off on a tangent, here.
As I understand it, the serialization anomalies that we have today are
caused by the fact that readers don't block concurrent writers. So if
I read some data from table A and write it to table B and meanwhile
someone reads from table B and writes to table A, we may pass each
other like ships in the night unless we remember to use SELECT ... FOR
SHARE to guard against concurrent UPDATEs and DELETEs and LOCK ... IN
SHARE MODE to guard against concurrent INSERTs.
It would be nice to be have the option to dispense with this explicit
locking and still get serializable behavior and AIUI that's what these
SIREAD locks are designed to do (they also don't lead to additional
blocking as explicit locks potentially do). The limitation is that
the granularity of the SIREAD locks isn't going to be magically better
than the granularity of your underlying lock subsystem. Fortunately,
our underlying locking system for protecting against UPDATE and DELETE
operations is already row-level and therefore as good as it gets. Our
underlying system for protecting against INSERT is pretty primitive by
comparison, so we'd have to decide whether to ignore inserts or take a
table-level SIREAD lock, and the latter would probably result in such
poor concurrency as to make the whole thing pointless.
But that doesn't mean that the entire project is pointless. It just
means that we'll be able to protect against concurrent UPDATEs and
DELETEs without explicit locking, if the transaction isolation level
is set to serializable, but we'll still fall short when it comes to
concurrent INSERTs. That would be a massive improvement versus where
we are now. I do a fair amount of explicit locking in my code and
it's nearly all row-level locks to protect against concurrent
updates/deletes, so I can't see that only handling those cases would
be a bad place to start. Fortunately, for my applications,
concurrency is low enough that explicit locking isn't a problem for me
anyway (also, I'm good at figuring out what to lock), but that's
clearly not true for everyone.
...Robert
Kevin Grittner wrote:
Greg Stark <greg.stark@enterprisedb.com> wrote:
Without any real way to represent predicates this is all pie in the
skyAnd this is 180% opposite from what I just heard at PGCon should be
the focus of discussion at this point. Let's get agreement on what
would be nice user-facing behavior first.
Ok, here goes:
1. Needs to be fully spec-compliant serializable behavior. No anomalities.
2. No locking that's not absolutely necessary, regardless of the
WHERE-clause used. No table locks, no page locks. Block only on
queries/updates that would truly conflict with concurrent updates.
3. No "serialization errors" that are not strictly necessary.
4. Reasonable performance. Performance in single-backend case should be
indistinguishable from what we have now and what we have with the more
lenient isolation levels.
5. Reasonable scalability. Shouldn't slow down noticeably when
concurrent updaters are added as long as they don't conflict.
6. No tuning knobs. It should just work.
Now let's discuss implementation. It may well be that there is no
solution that totally satisfies all those requirements, so there's
plenty of room for various tradeoffs to discuss. I think fully
spec-compliant behavior is a hard requirement, or we'll find ourselves
adding yet another isolation level in the next release to achieve it.
The others are negotiable.
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
