Re: Serializable Isolation without blocking - Mailing list pgsql-hackers

Simon Riggs <simon@2ndQuadrant.com> wrote:
> Do we need full locking of everything we might
> touch, or tracking of what we have touched?
> If you need the "might touch" then you either need to implement
> locking that will effect everybody (which ain't ever gonna fly round
> here), or you implement a scheme that is harder work but avoids
> locking. That is clearly O(N^2) for non-locking design.
> 
> If you track "have touched" only then we can do that with a hash
> table in shared memory. That would be O(k), if it is possible.
To quote what I think is a relevant section from the paper:
> One property of Berkeley DB that simplified our implementation was
> working with page level locking and versioning. In databases that
> version and lock at row-level granularity (or finer), additional
> effort would be required to avoid phantoms, analogous to standard
> two phase locking approaches such as multigranularity locking.
Since these techniques are used in quite a few databases, I assume
that implementation is fairly well understood.  The big difference is
that rather than traditional read locks which block updates, it would
be these new non-blocking SIREAD locks.  As I understand it, the point
of this technique is to approximate "might touch" through locking
"have touched" on both rows and index ranges.  I know that is
considered crude by some, but the O(N^2) cost of actual predicate lock
calculation would be insane in most real-world environments.
I do have to concede that the paper is silent on how transactions at
other isolation levels behave in this mix.  On a first think-through,
it doesn't seem like they would need to obtain SILOCKs for their
reads, since there is no guarantee that they see things in a state
which would be consistent with some serial execution of the database
transactions.  I don't think transactions at less stringent
transaction isolation levels need to look for SILOCKs, either.  I
wouldn't consider my first pass thinking it through to be particularly
definitive, though.
That interpretation would mean, however, that while the serializable
transactions would satisfy the new, more stringent requirements of
recent versions of the SQL standard, they would still not provide
quite the same guarantees as traditional blocking serializable
transactions.  In my receipting example, traditional techniques would
cause the attempt to update the control record to block until the
receipts on the old date committed or rolled back, and the attempt to
report the day's receipts couldn't proceed until the control record
update was committed, so as long as the transactions which modify data
were serializable, no select at READ COMMITTED or highter could see a
state inconsistent with some serial application of the serializable
transactions.  With this interpretation, even a SELECT-only
transaction would need to be SERIALIZABLE to ensure that that it did
not see the new deposit date when there were still pending receipts
for the old deposit date.  I think I'm OK with that if everyone else
is.
-Kevin