re[4]: [Jdbm-developer] Optimistic CC

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>
<DIV><FONT face=Arial size=2>Bryan-</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2></FONT></DIV>
<DIV><FONT face=Arial size=2>Correct - the
 2PL (rw) + MVCC(ww) approach that you are
 proposing is most certainly not optimistic.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>The MVCC approach
 that PostreSQL and others are using (where
 all concurrency control is being achieved
 via MVCC and there is no 2PL)&nbsp;definitely
 has optimistic characteristics.&nbsp; With
 MVCC there are no rw conflicts - ever.&nbsp;
 That leaves only ww conflicts.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>I think I'm
 going on need some help from you in understanding
 the combined 2PL/MVCC approach.&nbsp; Can
 you please give me an explicit transaction
 trace example of how that would work?&nbsp;
 All of the transaction flows that I can come
 up with wind up with the read locks under
 2PL preventing any write contention at all...&nbsp;
 Given that MVCC is primarily centered around
 preventing rw contention, how exactly do
 you intend to have MVCC to protect against
 ww conflict?</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>Thanks!</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>- K</FONT></DIV>
<DIV><FONT face=Arial size=2>&nbsp;</FONT>
 
<TABLE>
<TBODY>
<TR>
<TD width=1 bgColor=blue><FONT face=Arial
 size=2></FONT></TD>
<TD><FONT face=Arial size=2><FONT color=blue>&gt;
 Kevin,<BR><BR>Absolutely right: _optimistic_.<BR><BR>CC
 gets divided into three realms:<BR><BR>&nbsp;-
 locking<BR>&nbsp;- timestamp<BR>&nbsp;- verification
 (aka optimistic) <BR><BR>The notion in optimistic
 is that you verify that the transactions
 did<BR>not conflict. &nbsp;The proposed 2PL(rw)
 + MVCC(ww) approach is NOT optimistic<BR>in
 this sense since it uses locking to place
 an ordering over read-write<BR>conflicts.<BR><BR>-bryan<BR><BR>-----Original
 Message-----<BR>From: <A href="mailto:jdb...@li..."><FONT
 color=#0000ff>jdb...@li...</FONT></A><BR>To:
 JDBM Developer listserv<BR>Sent: 2/28/2006
 7:06 PM<BR>Subject: re[2]: [Jdbm-developer]
 Opportunistic CC<BR><BR>Bryan-<BR><BR>Just
 to clarify, I think you are refering to "optimistic"
 not<BR>"opportunistic"... &nbsp;the papers
 referenced refer to the former, not the<BR>later.
 &nbsp;Opportunistic locking is something
 used in net-bios and other<BR>distributed
 file systems and it gives me the willies
 - I've had no end<BR>of problems with opp
 locks over the years.<BR><BR>I believe that
 optimistic CC and MVCC are in the same genre
 of CC<BR>algorithms (or at least MVCC can
 be said to be relatively 'optimistic'),<BR>but
 MVCC removes a large category of conflicts
 that could cause an<BR>opportunistic algorithm
 to force an abort (r-w, w-r). &nbsp;In MVCC,
 the only<BR>conflict that can cause an abort
 is a write-write conflict. &nbsp;The<BR>decision
 of when and which tx to abort can be deferred
 to commit time to<BR>increase the available
 information for making a decision of which<BR>aborted
 txs will require the least re-work. &nbsp;The
 other school of thought<BR>is that an abort
 should occur as soon as a w-w conflict is
 detected...<BR><BR>I'm not sure that either
 option is better than the other - they'll
 both<BR>probably perform equally poorly for
 a highly contested resource.<BR><BR>- K<BR><BR>&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&gt;
 All,<BR><BR>I know that we have been discussing
 things in terms of 2PL and MVCC,<BR>but I
 think that it might be worth while to do
 a little bit of reading<BR>on the third family
 of concurrency control techniques: opportunistic.<BR>For
 some examples, see [1], [2], [3]. &nbsp;I
 have not read up in this area<BR>since I
 was focusing on MVCC. &nbsp;However it does
 appear likely that an<BR>opportunistic concurrency
 control strategy could have the highest<BR>concurrency
 for many scenarios.<BR><BR>FYI - I am prototyping
 2PL with multiple granularities per Gray
 and<BR>the JPEG that I distributed last week.<BR><BR>-bryan<BR><BR>[1]
 &nbsp;<A href="http://en.wikipedia.org/wiki/Optimistic_concurrency_control"><FONT
 color=#0000ff>&lt;http://en.wikipedia.org/wiki/Optimistic_concurrency_control&gt;</FONT></A><BR><A
 href="http://en.wikipedia.org/wiki/Optimistic_concurrency_control"><FONT
 color=#0000ff>http://en.wikipedia.org/wiki/Optimistic_concurrency_control</FONT></A><BR><BR>[2]
 Bernstein, P. A. and Goodman, N. 1981. Concurrency
 Control in<BR>&nbsp;&nbsp;Distributed Database
 Systems. ACM Comput. Surv. 13, 2 (Jun. 1981),<BR>&nbsp;&nbsp;185-221.
 DOI= &nbsp;<A href="http://doi.acm.org/10.1145/356842.356846"><FONT
 color=#0000ff>&lt;http://doi.acm.org/10.1145/356842.356846&gt;</FONT></A><BR><A
 href="http://doi.acm.org/10.1145/356842.356846"><FONT
 color=#0000ff>http://doi.acm.org/10.1145/356842.356846</FONT></A><BR><BR><BR><A
 href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/Concurrency"><FONT
 color=#0000ff>&lt;http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/Concurrency</FONT></A><BR>Contr&gt;<BR><A
 href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyC"><FONT
 color=#0000ff>http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyC</FONT></A><BR>ontr<BR>ol.pdf<BR><BR>[3]
 Apologizing Versus Asking Permission: Optimistic
 Concurrency<BR>&nbsp;&nbsp;Control for Abstract
 Data Types MAURICE HERLIHY Carnegie Mellon<BR>&nbsp;&nbsp;University.<BR>&nbsp;&nbsp;&nbsp;&nbsp;<A
 href="http://www.cs.brown.edu/~mph/Herlihy90a/p96-herlihy.pdf"><FONT
 color=#0000ff>&lt;http://www.cs.brown.edu/~mph/Herlihy90a/p96-herlihy.pdf&gt;</FONT></A><BR><A
 href="http://www.cs.brown.edu/~mph/Herlihy90a/p96-herlihy.pdf"><FONT
 color=#0000ff>http://www.cs.brown.edu/~mph/Herlihy90a/p96-herlihy.pdf</FONT></A><BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"An
 optimistic concurrency control technique
 is one that<BR>&nbsp;&nbsp;&nbsp;&nbsp;allows
 transactions to execute without synchronization,<BR>&nbsp;&nbsp;&nbsp;&nbsp;relying
 on commit-time validation to ensure serializability."<BR><BR>-bryan<BR><BR>&lt;<BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>-------------------------------------------------------
 This SF.Net<BR>email is sponsored by xPML,
 a groundbreaking scripting language that<BR>extends
 applications into web and mobile media. Attend
 the live webcast<BR>and join the prime developer
 group breaking into this new coding<BR>territory!<BR><A
 href="http://sel.as-us.falkag.net/sel?cmd=lnk&amp;kid=110944&amp;bid=241720&amp;dat=121642"><FONT
 color=#0000ff>http://sel.as-us.falkag.net/sel?cmd=lnk&amp;kid=110944&amp;bid=241720&amp;dat=121642</FONT></A><BR>_______________________________________________
 Jdbm-developer mailing<BR>list <A href="mailto:Jdb...@li..."><FONT
 color=#0000ff>Jdb...@li...</FONT></A><BR><A
 href="https://lists.sourceforge.net/lists/listinfo/jdbm-developer"><FONT
 color=#0000ff>https://lists.sourceforge.net/lists/listinfo/jdbm-developer</FONT></A><BR><BR>&lt;<BR></FONT></FONT></TD></TR></TBODY></TABLE></DIV></FONT></BODY></HTML>