Menu
▾
▴
[Jdbm-developer] Use of 2PL and MVCC for concurrency
|
From: Kevin D. <ke...@tr...> - 2006-02-28 02:06:22
|
<!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>
<DIV><FONT face=Arial>Hi all- finally
back from fun and frolic. I'm going
tos end a couple of emails with my comments
on some of the discussions that have happened
over the past week. I originally wrote
these in a single email, but I think it will
be better to have them separated...</FONT></DIV>
<DIV> </DIV>
<DIV>Here's the first:</DIV>
<DIV> </DIV>
<DIV>Use of 2PL and MVCC for concurrency
-
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>In the JPEG that Bryan
sent out outling things, he indicated that
RW synchronizsation will be done by locking,
and ww sync would be done using MVCC.
I'm struggling to see why MVCC would be of
any advantage over 2PL in a ww conflict scenario
if it is not also applied in a rw scenario...
When I consider that a transaction will have
to read a record before it can write to it,
2PL will pretty much prevent any two tx from
ever having multiple versions of a single
record...</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>The two papers ([1]
and [2]) that Bryan has pointed
us to are quite descriptive on
the general strategy of mixing
MVCC and 2PL. As I read it, the only
apparent way to actually combine 2PL and
MVCC is if you have pre-defined write-sets.
Without that, 2PL forces an exclusive, blocking
lock on each read (it's the only way to ensure
that the transaction's are both serializable
AND progressive - the term 'progressive'
was missing from my vocabulary last week).</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>As I apply my understanding
of 2PL to an MVCC implementation (and as
implied in [1], and explicitly stated in
[2] - see page 212 in original paper, sentence:
"These methods all require predeclaration
of writelocks"), without a pre-declared writeset,
all bets are off in terms of combining 2PL
and MVCC.</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>
<DIV><FONT face=Arial>[1] - <A href="http://www.vldb.org/conf/1983/P074.PDF">http://www.vldb.org/conf/1983/P074.PDF</A></FONT></DIV>
<DIV><FONT face=Arial>[2] - <A href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyContr"><FONT
face=Tahoma color=#0000ff><A href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyControl.pdf">http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyContr</FONT></A><FONT
face=Tahoma>ol.pdf</A></FONT></FONT></DIV></FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>If 2PL is implemented
without pre-declared write sets, any advantages
of MVCC will be lost (unless I am missing
something very important, under 2PL, there
would never be more than one version of any
given row). This pushes a hybrid scheme
in the direction of either allowing the user
to specify which model they want during start
up, or having the system dynamically flip
to 2PL for a period of time when it detects
a bunch of tx restarts.</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>Alternatively, intention
locks could be used on the read side of things
to help the CC system determine whether it
actually needs to abort a transaction in
a write conflict (and determine which transaction
to abort). But unless I see a very
compelling mathematical proof otherwise,
I do not believe that ensuring 'progressive'
behavior will be possible with intention
locks, in which case, we are back to aborting
transactions during conflict - maybe the
number of aborts will be reduced because
the intention locks provide information that
will determine whether a transaction should
be blocked or aborted? I'd be curious
about even that. With 2PL (unless we
have predeclared write sets), we still have
the problem of deadlock and lock contention,
so you are going to have tx aborts there
as well.</FONT></DIV>
<P><FONT face=Arial></FONT> </P>
<P><FONT face=Arial>Another thing to consider:
Given that there are typically many more
reads in a database system than writes, the
overhead of intention locking could be quite
high. With a pure MVCC implementation,
only write locks are required.</P>
<DIV><BR></DIV></FONT>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>I think that this is
a critical aspect of the discussion that
really needs to be hammered out, and relatively
soon. To that end, here are some specific
questions:</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>1. Do any of
us believe that pre-declared write sets are
feasible in jdbm?</FONT></DIV>
<DIV><FONT face=Arial>2. Does anyone
see a way of creating a progressive (blocking)
transaction set without pre-declared write
sets?</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV>Cheers!</DIV>
<DIV> </DIV>
<DIV>- K</DIV></DIV></FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV></DIV>
<DIV><FONT face=Arial></FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV>
<DIV><FONT face=Arial>Kevin Day<BR>Trumpet,
Inc.<BR><A href="http://www.trumpetinc.com"><FONT
color=#0000ff>www.trumpetinc.com</FONT></A><BR><A
href="mailto:ke...@tr..."><FONT
color=#0000ff>ke...@tr...</FONT></A><BR>602-438-7030</FONT></DIV>
<DIV><FONT face=Arial></FONT> </DIV></FONT></BODY></HTML>
|