Re: Update on true serializable techniques in MVCC

On Wed, Dec 16, 2009 at 4:52 AM, Albe Laurenz <laurenz(dot)albe(at)wien(dot)gv(dot)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