Re: SSI patch version 14

On Thu, Jan 27, 2011 at 09:18:23AM -0800, Jeff Davis wrote:
> On Tue, 2011-01-25 at 05:57 -0500, Dan Ports wrote:
> > This summary is right on. I would add one additional detail or
> > clarification to the last point, which is that rather than checking for
> > a cycle, we're checking for a transaction with both "in" and "out"
> > conflicts, which every cycle must contain.
>
> To clarify, this means that it will get some false positives, right?

Yes, this is correct.

> Is there a reason we can't check for a real cycle, which would let T1
> succeed?

I talked today with someone who experimented with doing exactly that in
MySQL as part of a research project (Perfectly Serializable Snapshot
Isolation, paper forthcoming in ICDE)

It confirmed my intuition that this is possible but not as
straightforward as it sounds. Some complications I thought of in
adapting that to what we're doing:

1) it requires tracking all edges in the serialization graph; besides
the rw-conflicts we track there are also the more mundane
rw-dependencies (if T2 sees an update made by T1, then T2 has to
come after T1) and ww-dependencies (if T2's write modifies a tuple
created by T1, then T2 has to come after T1).

We are taking advantage of the fact that any cycle must have two
adjacent rw-conflict edges, but the rest of the cycle can be
composed of other types. It would certainly be possible to track the
others, but it would add a bit more complexity and use more memory.

2) it requires doing a depth-first search to check for a cycle, which
is more expensive than just detecting two edges. That seems OK if
you only want to check it on commit, but maybe not if you want to
detect serialization failures at the time of the conflicting
read/write (as we do).

3) it doesn't seem to interact very well with our memory mitigation
efforts, wherein we discard lots of data about committed
transactions that we know we won't need. If we were checking for
cycles, we'd need to keep more of it. I suspect summarization (when
we combine two transactions' predicate locks to save memory) would
also cause problems.

None of these seem particularly insurmountable, but they suggest it
isn't a clear win to try to find an entire cycle.

Dan

--
Dan R. K. Ports MIT CSAIL http://drkp.net/