re[2]: [Jdbm-developer] Garbage collection on old versions of rows

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>Just a thought:&nbsp;
 </FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>If the versions
 are maintained external to the record itself
 (in a version pointer list), then the version
 list can be stored in a sorted list and accessed
 using binary or linear search.&nbsp; This
 presumes that some purging of old versions
 will eventually occur.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>In that scenario,
 a reader would operate as follows:</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>1.&nbsp; Look
 up physical offset of requested recid</FONT></DIV>
<DIV><FONT face=Arial size=2>2.&nbsp; check
 bit in translation table slot to determine
 if the pointer is to a physical row, or another
 logical row that represents a version table
 for the logical&nbsp;recid&nbsp;(version
 list contains transaction ID that created
 the version, plus the physical offset of
 the actual version)</FONT></DIV>
<DIV><FONT face=Arial size=2>3.&nbsp; If
 the version list bit is set, retrieve the
 version table from the specified logical
 recid (we use logical here to allow the version
 table to be moved around if necessary)</FONT></DIV>
<DIV><FONT face=Arial size=2>4.&nbsp; Perform
 a search of the version table for the appropriate
 version for the current tx</FONT></DIV>
<DIV><FONT face=Arial size=2>5.&nbsp; Retrieve
 actual row at offset specified in version
 table</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>there are many
 implementation details here that could be
 tweaks (do we have the bit in the translation
 slot, or in the record itself, etc...), but
 the general idea holds.&nbsp; Garbage collection
 would be achieved by walking the translation
 table looking for rows that have versions,
 then checking the version table for a given
 row against the current transaction to see
 if there are any entries in the version table
 that can be safely purged.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>Your comments
 on 2PL and MVCC locking (i.e. obtaining a
 lock on write that prevents reads) is exactly
 my concern with combining the two protocols.&nbsp;
 The biggest advantage of MVCC is that it
 does not cause blocking of readers, when
 2PL gets introduced into the mix,&nbsp;I
 believe that blocking reads comes along with
 the package.&nbsp; Unfortunately, because
 2PL is so coarse grained in it's approach
 to enforcing serializability, there are a
 large number of transaction orderings that
 would be allowed by MVCC (and would not cause
 aborts) that would be prevented by the 2PL
 component...</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2>All that said,
 the structured log concept may completely
 remove the need for tracking versions of
 individual rows - they may have a much more
 efficient data structure that is implicit
 to the threaded log file instead of tacked
 on like my concept.</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></FONT>&nbsp;</DIV>
<DIV><FONT face=Arial size=2></FONT>&nbsp;</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=red>&gt;
 Kevin,<BR><BR>If we only mark the version
 that created a row, then there is no means<BR>available
 to get to a previous version of a row from
 that row, right?<BR>I would think that we
 need the ability to access the previous versions<BR>of
 a row during concurrent transactions since
 a reader must read the<BR>appropriate version....
 &nbsp;However I could definately be wrong
 here. &nbsp;I<BR>have not thought through
 the relationship between 2PL and the MVCC<BR>versions
 that a transaction reads. &nbsp;I would think
 that the locking is<BR>designed to prevent
 writes that would conflict with the reads,
 so once<BR>a share lock is obtained, no writes
 can occur on the locked resource <BR>until
 the share lock readers complete.... &nbsp;So,
 you always read the<BR>current version and
 writes block until there are no more readers,
 at<BR>which point we write new versions (which
 can occur concurrently).<BR><BR>So maybe
 we do not need the currentVersion-&gt;priorVersion
 field in the<BR>record header after all.
 &nbsp;That would be nice. &nbsp;In that case
 I would<BR>still like to think about a data
 structure (ala a btree) in which we<BR>could
 lookup historical versions (for use with
 an immortal database).<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/27/2006
 9:19 PM<BR>Subject: [Jdbm-developer] Garbage
 collection on old versions of rows<BR><BR>I
 believe that the book-keeping for this will
 be relatively minor. &nbsp;<BR><BR>If a master
 list of transactions is retained, and each
 transaction has<BR>it's ID and the ID of
 the youngest transaction present in the system<BR>when
 it committed, then it should be easy for
 a garbage collector to<BR>sweep versions
 that are no longer needed (and finally sweep
 the<BR>transaction from the master transaction
 list).<BR><BR>This will require another non-transactional
 data structure, but it<BR>definitely doesn't
 require writes to each record on commit or
 anything<BR>like that (each version of a
 record will be marked with either the<BR>transaction
 ID that created it, or null if it is the
 only version in the<BR>db)..<BR><BR>- K<BR><BR>Kevin
 Day<BR>Trumpet, Inc.<BR><A href="http://www.trumpetinc.com"><FONT
 color=#0000ff>&lt;http://www.trumpetinc.com&gt;</FONT></A>
 <A href="http://www.trumpetinc.com"><FONT
 color=#0000ff>www.trumpetinc.com</FONT></A><BR><A
 href="mailto:ke...@tr..."><FONT
 color=#0000ff>&lt;mailto:ke...@tr...&gt;</FONT></A>
 <A href="mailto:ke...@tr..."><FONT
 color=#0000ff>ke...@tr...</FONT></A><BR>602-438-7030<BR><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>