[Jdbm-developer] Chink in the armor...

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0
 Transitional//EN">
<HTML><HEAD>
<STYLE type=text/css> P, UL, OL, DL, DIR,
 MENU, PRE { margin: 0 auto;}</STYLE>

<META content="MSHTML 6.00.2900.2802" name=GENERATOR></HEAD>
<BODY leftMargin=1 topMargin=1 rightMargin=1><FONT
 face=Tahoma size=2>
<DIV><FONT face=Arial>In the middle of writing
 another email, the following occured to me:</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>What are the implications
 of changes to multiple records by multiple
 transcations in the proposed MVCC(k) algorithm?&nbsp;
 If I have Ti make a change to x, and Tj make
 a change to y, does this imply that anything
 is wrong or invalid after both transactions
 complete?&nbsp; This may be the example that
 breaks the proposed algorithm...</DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>T1 - read(x0)</FONT></DIV>
<DIV><FONT face=Arial>T2 - read(x0)</FONT></DIV>
<DIV><FONT face=Arial>T1 - read(y0)</FONT></DIV>
<DIV><FONT face=Arial>T2 - read(y0)</FONT></DIV>
<DIV><FONT face=Arial>T1 - write(x1)&nbsp;&nbsp;
 &lt;-- insert contents of y0</FONT></DIV>
<DIV><FONT face=Arial>T2 - write(y1)&nbsp;&nbsp;
 &lt;-- insert contents of X0</FONT></DIV>
<DIV><FONT face=Arial>T1 - commit</FONT></DIV>
<DIV><FONT face=Arial>T2 - commit</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>The net result of this
 log would be to swap x and y (i.e. x1=y0,
 y1=x0).&nbsp; However, if these transactions
 were executed serialy, you'd wind up with
 either x1 = y1 = x0 or x1 = y1 = y0.</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>I think this is a bad
 thing.</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>Alex - this would seem
 to validate Bryan's comment that you have
 to have writers block readers, unless you
 know a-priori that&nbsp;a given transaction
 is read-only.</FONT></DIV>
<DIV>&nbsp;</DIV>
<DIV>Alternatively, we have to do some sort
 of commit time analysis to ensure that this
 situation doesn't occur (i.e. the read *and*
 write sets of any two concurrent transactions
 can not intersect).&nbsp; This would push
 the algorithm far into the realm of optimistic
 (no judgement on that - I'm quite happy with
 optimistic).</DIV></FONT>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial> I'm beginning to see
 why the PostgreSQL team decided to use 2PL
 for updaters, and reserving MVCC for read-only
 tx and roll-back of VLR tx (not that we necessarily
 want to do what they did - I'm just seeing
 why they did what they did).</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>If we go for the optimistic
 approach, then the conflict check at commit
 time becomes a fairly obvious set intersection
 operation...&nbsp; There's also still no
 reason we couldn't do both - it just means
 that my w-w conflict check is not sufficient
 - we also need the opportunistic check at
 the end.</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>Comments?</FONT></DIV>
<DIV><FONT face=Arial></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial>- K</FONT></DIV></FONT></BODY></HTML>