Horton

Thread

  1. Re: SSI predicate locking on heap -- tuple or row?

    Kevin Grittner <kevin.grittner@wicourts.gov> — 2011-05-26T03:19:31Z

    > Dan Ports  wrote:
> On Tue, May 24, 2011 at 04:18:37AM -0500, Kevin Grittner wrote:
 
>> These proofs show that there is no legitimate cycle which could
>> cause an anomaly which the move from row-based to tuple-based
>> logic will miss. They don't prove that the change will generate
>> all the same serialization failures; and in fact, some false
>> positives are eliminated by the change.
>
> Yes, that's correct. That's related to the part in the proof where
> I claimed T3 couldn't have a conflict out *to some transaction T0
> that precedes T1*.
>
> I originally tried to show that T3 couldn't have any conflicts out
> that T2 didn't have, which would mean we got the same set of
> serialization failures, but that's not true. In fact, it's not too
> hard to come up with an example where there would be a
> serialization failure with the row version links, but not without.
> However, because the rw-conflict can't be pointing to a transaction
> that precedes T1 in the serial order, it won't create a cycle. In
> other words, there are serialization failures that won't happen
> anymore, but they were false positives.
 
Dan and I went around a couple times chasing down all code, comment,
and patch changes needed, resulting in the attached patch.  We found
and fixed the bug which originally manifested in a way which I
confused with a need for row locks, as well as another which was
nearby in the code.  We backed out the changes which were causing
merge problems for Robert, as those were part of the attempt at the
row locking (versus tuple locking).  We removed a function which is
no longer needed.  We adjusted the comments and an affected isolation
test.
 
As might be expected from removing an unnecessary feature, the lines
of code went down -- a net decrease of 93 lines.
 
This patch applies against HEAD, `make check-world` passes as does
`make -C src/test/isolation installcheck` and `make
installcheck-world` against a database with
default_transaction_isolation = 'serializable'.  Dan is running
stress testing against the patched version tonight with DBT-2.
 
These changes generate merge conflicts with the work I've done on
handling CLUSTER, DROP INDEX, etc.  It seems to me that the best
course would be to commit this, then I can rebase the other work and
post it.  Since these issues are orthogonal, it didn't seem like a
good idea to combine them in one patch, and this one seems more
urgent.
 
-Kevin

  2. Re: SSI predicate locking on heap -- tuple or row?

    Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> — 2011-05-26T08:06:49Z

    On 26.05.2011 06:19, Kevin Grittner wrote:
> Dan and I went around a couple times chasing down all code, comment,
> and patch changes needed, resulting in the attached patch.  We found
> and fixed the bug which originally manifested in a way which I
> confused with a need for row locks, as well as another which was
> nearby in the code.  We backed out the changes which were causing
> merge problems for Robert, as those were part of the attempt at the
> row locking (versus tuple locking).  We removed a function which is
> no longer needed.  We adjusted the comments and an affected isolation
> test.

Could you explain in the README, why it is safe to only take the lock on 
the visible row version, please? It's not quite obvious, as we've seen 
from this discussion, and if I understood correctly the academic papers 
don't touch that subject either.

> As might be expected from removing an unnecessary feature, the lines
> of code went down -- a net decrease of 93 lines.

That's the kind of patch I like :-).

> These changes generate merge conflicts with the work I've done on
> handling CLUSTER, DROP INDEX, etc.  It seems to me that the best
> course would be to commit this, then I can rebase the other work and
> post it.  Since these issues are orthogonal, it didn't seem like a
> good idea to combine them in one patch, and this one seems more
> urgent.

Agreed.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com

  3. Re: SSI predicate locking on heap -- tuple or row?

    Kevin Grittner <kevin.grittner@wicourts.gov> — 2011-05-26T19:03:48Z

    Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> wrote:
 
> Could you explain in the README, why it is safe to only take the
> lock on the visible row version, please?
 
Sure.  I actually intended to do this last night but ran out of
steam and posted what I had, planning on following up with that.
 
The place it seemed to fit best was in the "Innovations" section,
since the SSI papers and their prototype implementations seemed
oriented toward "rows" -- certainly the SIREAD locks were at the row
level, versus a row version level.
 
Since this doesn't touch any of the files in yesterday's patch, and
it seems entirely within the realm of possibility that people will
want to argue about how best to document this more than the actual
fix, I'm posting it as a separate patch -- README-SSI only.
 
I mostly just copied from Dan's posted proof verbatim.
 
-Kevin

  4. Re: SSI predicate locking on heap -- tuple or row?

    Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> — 2011-05-30T09:36:04Z

    On 26.05.2011 06:19, Kevin Grittner wrote:
> 	/*
> 	 * Check whether the writer has become a pivot with an out-conflict
> 	 * committed transaction, while neither reader nor writer is committed. If
> 	 * the reader is a READ ONLY transaction, there is only a serialization
> 	 * failure if an out-conflict transaction causing the pivot committed
> 	 * before the reader acquired its snapshot.  (That is, the reader must not
> 	 * have been concurrent with the out-conflict transaction.)
> 	 */
> 	if (!failure)
> 	{
> 		if (SxactHasSummaryConflictOut(writer))
> 		{
> 			failure = true;
> 			conflict = NULL;
> 		}
> 		else
> 			conflict = (RWConflict)
> 				SHMQueueNext(&writer->outConflicts,
> 							 &writer->outConflicts,
> 							 offsetof(RWConflictData, outLink));
> 		while (conflict)
> 		{
> 			if (SxactIsCommitted(conflict->sxactIn)
> 				&& (!SxactIsCommitted(reader)
> 					|| conflict->sxactIn->commitSeqNo <= reader->commitSeqNo)
> 				&& (!SxactIsCommitted(writer)
> 					|| conflict->sxactIn->commitSeqNo <= writer->commitSeqNo)
> 				&& (!SxactIsReadOnly(reader)
> 					|| conflict->sxactIn->commitSeqNo <= reader->SeqNo.lastCommitBeforeSnapshot))
> 			{
> 				failure = true;
> 				break;
> 			}
> 			conflict = (RWConflict)
> 				SHMQueueNext(&writer->outConflicts,
> 							 &conflict->outLink,
> 							 offsetof(RWConflictData, outLink));
> 		}
> 	}

The comment is not in sync with the code. The code is not checking that 
"neither reader or writer has committed", but something more complicated.

Looking at OnConflict_CheckForSerializationFailure(), it's really hard 
to see how it works, and why the conditions it checks are sufficient. I 
find it helps tremendously to draw the dangerous structures being 
checked, in addition to just explaining them in text. Ascii art is a bit 
clunky, but I think we have to do it here.

I did some of that in the comments, and I think I understand it now. See 
attached patch. Does that look right to you? (note that I swapped the 
second and third check in the function, I think it's more 
straightforward that way). I also added a couple of questions about the 
conditions, marked with XXX comments. Can you answer those, please?

PS. Should we say "Cancelled on identification as pivot, during ...", or 
"Cancelled on identification as a pivot, during ..." ? We seem to use 
both in the error messages.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com