Update on true serializable techniques in MVCC

Kevin Grittner wrote:

Just to make those who care aware of it, here is Michael Cahill's
Doctoral Thesis based on implementing Serializable Snapshot
Isolation in InnoDB using a refined version of the techniques
previously used in the Berkley DB (and previously discussed on this
list):

http://hdl.handle.net/2123/5353

Seriously, this post is just for the benefit of those who may be
interested in following these developments -- I don't have the
inclination or energy for another round of debate on the topic just
now. :-/

I understand that, and thank you for the information.
Although it may have seemed that I was out to shoot the idea down,
I am interested in the topic. I guess my way of understanding something
is trying to find holes in it...

I read into the text, and I was particularly interested how he solved
the problem of phantom reads.

Quote:
The problem [of phantom reads] was identified in (Eswaran et al., 1976),
but the general purpose "predicate locking" solution suggested there
has not been widely adopted because of the difficulty in testing mutual
satisfiability of predicates.

Instead, locking DBMS implementations commonly use algorithms based on
"next-key locking". In these, a range of key space is protected against
concurrent insertion or deletion by acquiring a shared lock on the next
row in order, as a scan is made to check whether rows match a predicate.
The scan might be through the data records or through an index.

Inserts and deletes follow the same protocol, obtaining an exclusive
lock on the row after the one being inserted or deleted. The result
of this locking protocol is that a range scan prevents concurrent
inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Yours,
Laurenz Albe

2009/12/16 Albe Laurenz <laurenz.albe@wien.gv.at>:

Quote:
  The problem [of phantom reads] was identified in (Eswaran et al., 1976),
  but the general purpose "predicate locking" solution suggested there
  has not been widely adopted because of the difficulty in testing mutual
  satisfiability of predicates.

  Instead, locking DBMS implementations commonly use algorithms based on
  "next-key locking". In these, a range of key space is protected against
  concurrent insertion or deletion by acquiring a shared lock on the next
  row in order, as a scan is made to check whether rows match a predicate.
  The scan might be through the data records or through an index.

  Inserts and deletes follow the same protocol, obtaining an exclusive
  lock on the row after the one being inserted or deleted. The result
  of this locking protocol is that a range scan prevents concurrent
  inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

That boils down to 2PL, using a granularity that is somewhere between
table locks and single-row locks (note that the latter doesn't
correctly enforce serializability, hence something more coarse which
also locks not-yet-existing rows is needed).

Disadvantages:

1. Unstable latency: Depending on whether indexes or table scans are
used (i.e., the plan), other transactions may be blocked for long
durations or not.
2. Unstable susceptibility to deadlocks: Idem; it is possible that
once the planner starts to use another kind of scans, that your
transactions start to deadlock.

It seems that the proposed SIREAD method fixes at least (1), because
there is no additional blocking involved. I am not sure whether the
serialization failures that it may cause are dependent on the plan
used. If so, that would be very similar to (2).

Nicolas

* Albe Laurenz:

That sounds like it should actually work.

If you have got an index, yes. It seems to me that it would make
locking behavior dependent on your query plan, too.

BTW, PostgreSQL could raise a different error when a unique constraint
violation is detected which involves a row which is not visible at the
current snapshot. At least in my limited experience, that would allow
applications to recover more easily if small transactions fail
(similar to what you have to do on deadlock). Right now (well, at
least with 8.3, haven't checked 8.4 yet), it's not possible to tell a
unique constraint violation caused by a phantom from an application
bug. (We currently faking this by retrying a fixed number of times
and bailing out if the error returned by PostgreSQL looks like a
unique constraint violation.)

--
Florian Weimer <fweimer@bfk.de>
BFK edv-consulting GmbH http://www.bfk.de/
Kriegsstraße 100 tel: +49-721-96201-1
D-76133 Karlsruhe fax: +49-721-96201-99

Nicolas Barbier wrote:

Quote:

[...]

That sounds like it should actually work.

That boils down to 2PL, using a granularity that is somewhere between
table locks and single-row locks (note that the latter doesn't
correctly enforce serializability, hence something more coarse which
also locks not-yet-existing rows is needed).

That's how I understood it too.

Disadvantages:

1. Unstable latency: Depending on whether indexes or table scans are
used (i.e., the plan), other transactions may be blocked for long
durations or not.
2. Unstable susceptibility to deadlocks: Idem; it is possible that
once the planner starts to use another kind of scans, that your
transactions start to deadlock.

It seems that the proposed SIREAD method fixes at least (1), because
there is no additional blocking involved. I am not sure whether the
serialization failures that it may cause are dependent on the plan
used. If so, that would be very similar to (2).

Well, I guess that you have to pay somehow for serializability - there
will be more locks and more lock management.

I did not think of that, but it is really unpleasant if your transactions
suddenly start receiving serialization errors because the plan has been
changed. And the thesis says that the tests did not reveal too many
false positives, so maybe it is not that bad.

But maybe that's a price worth paying for serializability?

Yours,
Laurenz Albe

On Wed, Dec 16, 2009 at 4:52 AM, Albe Laurenz <laurenz.albe@wien.gv.at> wrote:

Kevin Grittner wrote:

Just to make those who care aware of it, here is Michael Cahill's
Doctoral Thesis based on implementing Serializable Snapshot
Isolation in InnoDB using a refined version of the techniques
previously used in the Berkley DB (and previously discussed on this
list):

http://hdl.handle.net/2123/5353

Seriously, this post is just for the benefit of those who may be
interested in following these developments -- I don't have the
inclination or energy for another round of debate on the topic just
now.  :-/

I understand that, and thank you for the information.
Although it may have seemed that I was out to shoot the idea down,
I am interested in the topic. I guess my way of understanding something
is trying to find holes in it...

I read into the text, and I was particularly interested how he solved
the problem of phantom reads.

Quote:
  The problem [of phantom reads] was identified in (Eswaran et al., 1976),
  but the general purpose "predicate locking" solution suggested there
  has not been widely adopted because of the difficulty in testing mutual
  satisfiability of predicates.

  Instead, locking DBMS implementations commonly use algorithms based on
  "next-key locking". In these, a range of key space is protected against
  concurrent insertion or deletion by acquiring a shared lock on the next
  row in order, as a scan is made to check whether rows match a predicate.
  The scan might be through the data records or through an index.

  Inserts and deletes follow the same protocol, obtaining an exclusive
  lock on the row after the one being inserted or deleted. The result
  of this locking protocol is that a range scan prevents concurrent
  inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index. If it gets to the data some other way it might
accidentally circumvent the lock. That's kind of a killer in terms of
making this work for PostgreSQL.

...Robert

Moin,

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

Inserts and deletes follow the same protocol, obtaining an exclusive
lock on the row after the one being inserted or deleted. The result
of this locking protocol is that a range scan prevents concurrent
inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index. If it gets to the data some other way it might
accidentally circumvent the lock. That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Andres

On Wed, Dec 16, 2009 at 10:29 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

  Inserts and deletes follow the same protocol, obtaining an exclusive
  lock on the row after the one being inserted or deleted. The result
  of this locking protocol is that a range scan prevents concurrent
  inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index.  If it gets to the data some other way it might
accidentally circumvent the lock.  That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Yeah, I guess you have to insert the new tuple. I guess while you
were at it you might check whether the next tuple is locked...

...Robert

"Albe Laurenz" <laurenz.albe@wien.gv.at> wrote:

Although it may have seemed that I was out to shoot the idea down,
I am interested in the topic. I guess my way of understanding
something is trying to find holes in it...

No problem. That's how ideas are explored and improved. The brick
wall was that there seemed to be overwhelming opposition to any new
technique which causes serialization failures under conditions where
the cause isn't blindingly obvious, regardless of the resulting
improvements in data reliability.

I was particularly interested how he solved the problem of phantom
reads.

That sounds like it should actually work.

Well, that's certainly not the novel part -- those techniques were
described and proven theoretically decades ago and have been in use
by many popular products for almost as long. It's that non-blocking
SIREAD lock which is the fun part. ;-)

I just wish I had time to read all the documents referenced in the
footnotes....

-Kevin

Nicolas Barbier <nicolas.barbier@gmail.com> wrote:

I am not sure whether the serialization failures that it may cause
are dependent on the plan used.

They are.

-Kevin

Robert Haas escribi�:

On Wed, Dec 16, 2009 at 10:29 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

� Inserts and deletes follow the same protocol, obtaining an exclusive
� lock on the row after the one being inserted or deleted. The result
� of this locking protocol is that a range scan prevents concurrent
� inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index. �If it gets to the data some other way it might
accidentally circumvent the lock. �That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Yeah, I guess you have to insert the new tuple. I guess while you
were at it you might check whether the next tuple is locked...

So you'd have to disable HOT updates when true serializability was
active?

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

On Wed, Dec 16, 2009 at 1:14 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Robert Haas escribió:

On Wed, Dec 16, 2009 at 10:29 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

  Inserts and deletes follow the same protocol, obtaining an exclusive
  lock on the row after the one being inserted or deleted. The result
  of this locking protocol is that a range scan prevents concurrent
  inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index.  If it gets to the data some other way it might
accidentally circumvent the lock.  That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Yeah, I guess you have to insert the new tuple.  I guess while you
were at it you might check whether the next tuple is locked...

So you'd have to disable HOT updates when true serializability was
active?

I thought about that, but I don't think so. HOT only applies to
updates, and predicate locking only applies to inserts. Unless I have
my head in the sand?

...Robert

On Wed, Dec 16, 2009 at 1:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Dec 16, 2009 at 1:14 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Robert Haas escribió:

On Wed, Dec 16, 2009 at 10:29 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

  Inserts and deletes follow the same protocol, obtaining an exclusive
  lock on the row after the one being inserted or deleted. The result
  of this locking protocol is that a range scan prevents concurrent
  inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index.  If it gets to the data some other way it might
accidentally circumvent the lock.  That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Yeah, I guess you have to insert the new tuple.  I guess while you
were at it you might check whether the next tuple is locked...

So you'd have to disable HOT updates when true serializability was
active?

I thought about that, but I don't think so.   HOT only applies to
updates, and predicate locking only applies to inserts.  Unless I have
my head in the sand?

Err, no, wait. Predicate locking can apply to updates, but since HOT
updates never update an indexed column, I think we might still be OK?

...Robert

Robert Haas �rta:

On Wed, Dec 16, 2009 at 1:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Dec 16, 2009 at 1:14 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Robert Haas escribi�:

On Wed, Dec 16, 2009 at 10:29 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

Inserts and deletes follow the same protocol, obtaining an exclusive
lock on the row after the one being inserted or deleted. The result
of this locking protocol is that a range scan prevents concurrent
inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index. If it gets to the data some other way it might
accidentally circumvent the lock. That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Yeah, I guess you have to insert the new tuple. I guess while you
were at it you might check whether the next tuple is locked...

So you'd have to disable HOT updates when true serializability was
active?

I thought about that, but I don't think so. HOT only applies to
updates, and predicate locking only applies to inserts. Unless I have
my head in the sand?

Err, no, wait. Predicate locking can apply to updates, but since HOT
updates never update an indexed column, I think we might still be OK?

A predicate can include columns from an index plus others.
Am I missing something?

...Robert

--
Bible has answers for everything. Proof:
"But let your communication be, Yea, yea; Nay, nay: for whatsoever is more
than these cometh of evil." (Matthew 5:37) - basics of digital technology.
"May your kingdom come" - superficial description of plate tectonics

----------------------------------
Zolt�n B�sz�rm�nyi
Cybertec Sch�nig & Sch�nig GmbH
http://www.postgresql.at/

Alvaro Herrera <alvherre@commandprompt.com> wrote:

So you'd have to disable HOT updates when true serializability was
active?

I wouldn't think so; but someone familiar with HOT logic could
probably determine whether the unmodified algorithm could be used by
reviewing the "simplifying assumptions" near the bottom of page 42,
and the page about "Generalizing to other database engines" (section
4.8). I think those portions might stand on their own without
reading the rest of the document.

-Kevin

On Wed, Dec 16, 2009 at 1:29 PM, Boszormenyi Zoltan <zb@cybertec.at> wrote:

Robert Haas írta:

On Wed, Dec 16, 2009 at 1:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Dec 16, 2009 at 1:14 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Robert Haas escribió:

On Wed, Dec 16, 2009 at 10:29 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday 16 December 2009 16:24:42 Robert Haas wrote:

  Inserts and deletes follow the same protocol, obtaining an exclusive
  lock on the row after the one being inserted or deleted. The result
  of this locking protocol is that a range scan prevents concurrent
  inserts or delete within the range of the scan, and vice versa.

That sounds like it should actually work.

Only if you can guarantee that the database will access the rows using
some particular index.  If it gets to the data some other way it might
accidentally circumvent the lock.  That's kind of a killer in terms of
making this work for PostgreSQL.

Isnt the whole topic only relevant for writing access? There you have to
access the index anyway.

Yeah, I guess you have to insert the new tuple.  I guess while you
were at it you might check whether the next tuple is locked...

So you'd have to disable HOT updates when true serializability was
active?

I thought about that, but I don't think so.   HOT only applies to
updates, and predicate locking only applies to inserts.  Unless I have
my head in the sand?

Err, no, wait.  Predicate locking can apply to updates, but since HOT
updates never update an indexed column, I think we might still be OK?

A predicate can include columns from an index plus others.
Am I missing something?

Hmm, interesting point. In that case you couldn't use the index to
enforce predicate locking under MVCC without disabling HOT. But there
will be other cases where that wouldn't help anyway - a predicate
could also include unindexed columns exclusively. For those, the
traditional approach (not the one discussed in this paper) probably
requires locking against any heap insert, or checking each new heap
insert against the constraint, or... something.

...Robert

On Wed, Dec 16, 2009 at 1:30 PM, Kevin Grittner
<Kevin.Grittner@wicourts.gov> wrote:

Alvaro Herrera <alvherre@commandprompt.com> wrote:

So you'd have to disable HOT updates when true serializability was
active?

I wouldn't think so; but someone familiar with HOT logic could
probably determine whether the unmodified algorithm could be used by
reviewing the "simplifying assumptions" near the bottom of page 42,
and the page about "Generalizing to other database engines" (section
4.8).  I think those portions might stand on their own without
reading the rest of the document.

This thread veered off into a discussion of the traditional technique,
rather than the one in the paper. I think that's the part Alvaro was
responding to.

...Robert

Robert, Please forgive a couple editorial inserts to your statement
-- I hope it clarifies. If I've distorted your meaning, feel free
to straighten me out. :-)

Robert Haas <robertmhaas@gmail.com> wrote:

This thread veered off into a discussion of the traditional
[predicate locking] technique, rather than the [serializable] one
in the paper. I think that's the part Alvaro was responding to.

If you're right about Alvaro's concern -- my rough understanding is
that HOT creates a linked lists of tuples which are mutations of one
another without altering any value which is part of an index. If
that's anywhere near a correct understanding, I can't see how there
would be a problem with using the described locking techniques with
any tuple on the list.

As an aside, the thesis mentions smart use of multiple locking
granularities only under the "future work" section. I can't see an
implementation being considered production quality without that, as
without it there would be no way to constrain the space required to
track the locks. But there is no shortage of literature on how to
do that, so I view such discussions as more appropriate to low-level
implementation discussions should we ever get serious about using
the techniques which are the main thrust of Dr. Cahill's thesis.

If anyone is interested in reviewing recent literature on these
techniques, Dr. Cahill seemed to like (Hellerstein et al., 2007), to
the point where I may well track it down when I'm done pondering the
work which I referenced at the start of this thread.

-Kevin

Robert Haas wrote:

A predicate can include columns from an index plus others.
Am I missing something?

Hmm, interesting point. In that case you couldn't use the index to
enforce predicate locking under MVCC without disabling HOT. But there
will be other cases where that wouldn't help anyway - a predicate
could also include unindexed columns exclusively. For those, the
traditional approach (not the one discussed in this paper) probably
requires locking against any heap insert, or checking each new heap
insert against the constraint, or... something.

If I understand that correctly

[...] by acquiring a shared lock on the next
  row in order, as a scan is made to check whether rows match a predicate.
  The scan might be through the data records or through an index

I would say that in the case of a table scan, the whole table will
be SILOCKed. I guess that's pretty much unavoidable if you want
serializability.

Yours,
Laurenz Albe

[ Forgot the list, resending. ]

2009/12/16 Boszormenyi Zoltan <zb@cybertec.at>:

Robert Haas írta:

On Wed, Dec 16, 2009 at 1:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Dec 16, 2009 at 1:14 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

So you'd have to disable HOT updates when true serializability was
active?

I thought about that, but I don't think so.   HOT only applies to
updates, and predicate locking only applies to inserts.  Unless I have
my head in the sand?

Err, no, wait.  Predicate locking can apply to updates, but since HOT
updates never update an indexed column, I think we might still be OK?

A predicate can include columns from an index plus others.
Am I missing something?

This whole concept ("next-key locking") also applies in case there are
no indexes. In the case of a table scan, the "next key" is either the
next row relative to the scanned range (if the DBMS supports the
notion of non-full table scans, for example if the table contents are
themselves stored in sorted order), or something that indicates that
the whole table was scanned (i.e., a table lock).

Therefore, with next-key locking you better don't have too many table
scans if you want to have any concurrent transactions.

Nicolas