From: Kevin D. <ke...@tr...> - 2006-03-01 00:10:15
|
<!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> </DIV> <DIV><FONT face=Arial size=2></FONT></DIV> <DIV><FONT face=Arial size=2>For thouroughness, the answer is "yes" - I believe that 2PL could be used for jdbm. Lock releasing at the record level would occur during the first phase of the commit itself. The B-link trees and other special data structures would reside outside the CC layer to maximize concurrency (they will have to implement their own form of CC).</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>I think that using 2PL to induce timestamps in MVCC will prevent the biggest advantage of MVCC, namely removing the potential for r-w and w-r conflicts. I believe that these kinds of conflicts will outnumber w-w conflicts by a significant margin (probably measured in orders of magnitude) in typical use cases...</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>I'm challenged to think of how MVCC will prevent write conflicts - by my understanding, 2PL is what is going to be preventing the write conflict implicitly because it will not allow two tx to even read the same row (and in jdbm at least, a read is required prior to performing a write on an existing record).</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Anything I'm missing here?</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>- K</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2> </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>> Kevin,<BR><BR>I have one more issue for this list:<BR><BR>3. Do we believe that we can use a 2PL protocol for jdbm?<BR><BR>A 2PL protocol is more than simply locking resources. It requires<BR>that locks are acquired during one phase and then released during<BR>a second phase. Once any lock has been released, no more locks may<BR>be acquired. The transition between the lock acquisition stage and<BR>the lock release stage is the "locked point" of the transaction.<BR><BR>Its been a while since I read the b-link article, but it seems to <BR>me that it had some non-2PL locking. If so, then how do we manage<BR>that in a context in which 2PL is being used to induce timestamps<BR>for MVCC? (Perhaps we can discount btree locks if they are only<BR>used as index structures for records since the record state is<BR>primary? Or perhaps a distinct locking mechanism is required for<BR>the b-link tree?)<BR><BR>-bryan<BR><BR>-----Original Message-----<BR>From: Thompson, Bryan B.<BR>To: 'Kevin Day '; <A href="mailto:jdb...@li..."><FONT color=#0000ff>'jdb...@li...</FONT></A> '; 'JDBM<BR>Developer listserv '<BR>Sent: 2/28/2006 8:19 AM<BR>Subject: RE: [Jdbm-developer] Use of 2PL and MVCC for concurrency<BR><BR>Kevin wrote:<BR><BR>> 1. Do any of us believe that pre-declared write sets are feasible<BR>> in jdbm?<BR><BR>No. Based on reading and on my conversation with the postgres people<BR>I do not believe that any "real" databases use pre-declared write sets.<BR><BR>> 2. Does anyone see a way of creating a progressive (blocking)<BR>> transaction set without pre-declared write sets?<BR><BR>No. "Progressive" means that transaction rollbacks are not used in the<BR>CC strategy. This is not something that I can see us achieving.<BR><BR>However, there is another option. See [1], section 5.3.1. The<BR>option is to use locking to induce timestamps. This is not a<BR>progressive protocol and transactions may result in deadlocks<BR>in which case some transaction(s) will be restarted. However<BR>it allows the use of share locks, which means that you have<BR>concurrent readers, and SIX locks, which means that a share<BR>lock can be escalated to an exclusive lock once the other readers<BR>have released their locks. Once the "locked point" of the 2PL<BR>protocol has been reached for a transaction a timestamp is computed<BR>for that transaction. Deadlocks occur in the 2PL protocol if they<BR>occur. ww synchronization never conflicts since it uses MVCC and<BR>aways creates a new version.<BR><BR>I also have questions about the effective concurrency of this CC<BR>strategy and the situations under which it is possible to have a<BR>ww synchronization resulting in concurrent creation of multiple<BR>versions. It may be that you get all the concurrency with 2PL and<BR>just more overhead from the MVCC aspect. I have not seem any papers<BR>on the performance of this approach.<BR><BR>It appears that the highest concurrency comes from an optimistic CC<BR>strategy. However this means that you must retain the read sets and<BR>write sets of all concurrent transactions, so this is pretty much in<BR>direct conflict with the use of VLR Tx concurrently with short txs.<BR><BR>-bryan<BR><BR>[1] Bernstein, P. A. and Goodman, N. 1981. Concurrency Control in<BR> Distributed Database Systems. ACM Comput. Surv. 13, 2 (Jun. 1981),<BR> 185-221. DOI= <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><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>ontrol.pdf<BR><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:09 PM<BR>Subject: [Jdbm-developer] Use of 2PL and MVCC for concurrency<BR><BR>Hi all- finally back from fun and frolic. I'm going tos end a couple<BR>of emails with my comments on some of the discussions that have happened<BR>over the past week. I originally wrote these in a single email, but I<BR>think it will be better to have them separated...<BR><BR>Here's the first:<BR><BR>Use of 2PL and MVCC for concurrency - <BR><BR>In the JPEG that Bryan sent out outling things, he indicated that RW<BR>synchronizsation will be done by locking, and ww sync would be done<BR>using MVCC. I'm struggling to see why MVCC would be of any advantage<BR>over 2PL in a ww conflict scenario if it is not also applied in a rw<BR>scenario... When I consider that a transaction will have to read a<BR>record before it can write to it, 2PL will pretty much prevent any two<BR>tx from ever having multiple versions of a single record...<BR><BR>The two papers ([1] and [2]) that Bryan has pointed us to are quite<BR>descriptive on the general strategy of mixing MVCC and 2PL. As I read<BR>it, the only apparent way to actually combine 2PL and MVCC is if you<BR>have pre-defined write-sets. Without that, 2PL forces an exclusive,<BR>blocking lock on each read (it's the only way to ensure that the<BR>transaction's are both serializable AND progressive - the term<BR>'progressive' was missing from my vocabulary last week).<BR><BR>As I apply my understanding of 2PL to an MVCC implementation (and as<BR>implied in [1], and explicitly stated in [2] - see page 212 in original<BR>paper, sentence: "These methods all require predeclaration of<BR>writelocks"), without a pre-declared writeset, all bets are off in terms<BR>of combining 2PL and MVCC.<BR><BR>[1] - <A href="http://www.vldb.org/conf/1983/P074.PDF"><FONT color=#0000ff>http://www.vldb.org/conf/1983/P074.PDF</FONT></A><BR><A href="http://www.vldb.org/conf/1983/P074.PDF"><FONT color=#0000ff><http://www.vldb.org/conf/1983/P074.PDF></FONT></A> <BR>[2] -<BR><A href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/Concurrency"><FONT color=#0000ff><http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/Concurrency</FONT></A><BR>Contr><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>ontrol.pdf<BR><BR>If 2PL is implemented without pre-declared write sets, any advantages of<BR>MVCC will be lost (unless I am missing something very important, under<BR>2PL, there would never be more than one version of any given row). This<BR>pushes a hybrid scheme in the direction of either allowing the user to<BR>specify which model they want during start up, or having the system<BR>dynamically flip to 2PL for a period of time when it detects a bunch of<BR>tx restarts.<BR><BR>Alternatively, intention locks could be used on the read side of things<BR>to help the CC system determine whether it actually needs to abort a<BR>transaction in a write conflict (and determine which transaction to<BR>abort). But unless I see a very compelling mathematical proof<BR>otherwise, I do not believe that ensuring 'progressive' behavior will be<BR>possible with intention locks, in which case, we are back to aborting<BR>transactions during conflict - maybe the number of aborts will be<BR>reduced because the intention locks provide information that will<BR>determine whether a transaction should be blocked or aborted? I'd be<BR>curious about even that. With 2PL (unless we have predeclared write<BR>sets), we still have the problem of deadlock and lock contention, so you<BR>are going to have tx aborts there as well.<BR><BR><BR><BR>Another thing to consider: Given that there are typically many more<BR>reads in a database system than writes, the overhead of intention<BR>locking could be quite high. With a pure MVCC implementation, only<BR>write locks are required.<BR><BR><BR><BR>I think that this is a critical aspect of the discussion that really<BR>needs to be hammered out, and relatively soon. To that end, here are<BR>some specific questions:<BR><BR>1. Do any of us believe that pre-declared write sets are feasible in<BR>jdbm?<BR>2. Does anyone see a way of creating a progressive (blocking)<BR>transaction set without pre-declared write sets?<BR><BR><BR><BR><BR>Cheers!<BR><BR>- K<BR><BR><BR>Kevin Day<BR>Trumpet, Inc.<BR><A href="http://www.trumpetinc.com"><FONT color=#0000ff><http://www.trumpetinc.com></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><mailto:ke...@tr...></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&kid=110944&bid=241720&dat=121642"><FONT color=#0000ff>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&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><<BR></FONT></FONT></TD></TR></TBODY></TABLE></DIV></FONT></BODY></HTML> |
From: 'Kevin D. ' <ke...@tr...> - 2006-03-02 05:46:05
|
<!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> </DIV> <DIV><FONT face=Arial size=2></FONT></DIV> <DIV><FONT face=Arial size=2>OK - I'll address this here... For reference, here's the comment from the other email, just so we have them all in one place:</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT color=#000080 size=2>BBT: MVCC does NOT remove the rw synchronization problem. This was the<BR> point of figure 11 in [1]. A writer MUST abort if a reader has read<BR> a version later than the timestamp which the writer would write. The<BR> optimistic strategies do NOT block, but may abort during<BR> verification.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2><FONT face=Tahoma color=#000080>[1] Bernstein, P. A. and Goodman, N. 1981. Concurrency Control in<BR> Distributed Database Systems. ACM Comput. Surv. 13, 2 (Jun. 1981),<BR> 185-221. DOI= </FONT><A href="http://doi.acm.org/10.1145/356842.356846"><FONT face=Tahoma color=#000080>http://doi.acm.org/10.1145/356842.356846</FONT></A><BR><BR><A href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyContr"><FONT face=Tahoma><A href="http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyControl.pdf"><FONT color=#000080>http://www-static.cc.gatech.edu/classes/AY2003/cs8803i_fall/ConcurrencyContr</FONT></FONT></A><FONT face=Tahoma><FONT color=#000080>ol.pdf</FONT></A></FONT><BR></FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>KD: I believe that we all need to agree on what Fig 11 in [1] is actually showing, and whether it applies to MVCC or not. To that end, I would like to start with an assertion, then an argument of why the assertion is true:</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2><STRONG><U>Assertion: </U></STRONG></FONT></DIV> <DIV><FONT face=Arial size=2>Figure 11 in [1] does NOT accurately reflect the behavior of a properly implemented MVCC system. It reflects a timestamping multi-version system that tracks *timestamps* of when a given version of a given row was created or read. A properly implemented MVCC system will never abort or block because of a rw conflict, because there is never a rw conflict under MVCC.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2><STRONG><U>Argument:</U></STRONG></FONT></DIV> <DIV><FONT face=Arial size=2>MVCC does not *timestamp* versions. It marks versions with the transaction ID. Further, a version of a record that is stamped with a txid for a transaction that hasn't committed is NOT available for reading from any other tx. This is a critical difference that completely invalidates the pont that the authors in [1] are trying to make.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Taking Figure 11 as an example, the timestamping that the authors are showing looks like this (please check my interpretation to make sure I'm not missing something):</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Tx0: write data at time 50 (these aren't explicitly shown in the Fig, but the earlier versions of the record had to come from somewhere, so I'm going to toss this Tx0 into the flow)</FONT></DIV> <DIV><FONT face=Arial size=2>Tx0: commit</FONT></DIV> <DIV><FONT face=Arial size=2>Tx1: write data at time 92</FONT></DIV> <DIV><FONT face=Arial size=2>Tx2: read data at time 95 - in the Fig 11 example, this would retrieve V92</FONT></DIV> <DIV><FONT face=Arial size=2>Tx1: write data at time 100</FONT></DIV> <DIV><FONT face=Arial size=2>Tx1 commit</FONT></DIV> <DIV><FONT face=Arial size=2>Tx2 commit</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>At this point, tx2 is absolutely hosed - but it is hosed because they've broken isolation, which has made the concurrent execution of these two transactions not serialzable. To avoid this problem, the authors introduce a block on the read. This has a very negative impact on concurrency.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Now, let's look at the same sequence using a more appropriate MVCC strategy:</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2> <DIV><FONT face=Arial size=2>Tx0: write data at time 50 (these aren't explicitly shown in the Fig, but the earlier versions of the record had to come from somewhere, so I'm going to toss this Tx0 into the flow)</FONT></DIV> <DIV><FONT face=Arial size=2>Tx0: commit</FONT></DIV> <DIV><FONT face=Arial size=2>Tx1: write data at time 92</FONT></DIV> <DIV><FONT face=Arial size=2>Tx2: read data at time 95 - in MVCC, this would retrieve V50</FONT></DIV> <DIV><FONT face=Arial size=2>Tx1: write data at time 100</FONT></DIV> <DIV><FONT face=Arial size=2>Tx1 commit</FONT></DIV> <DIV><FONT face=Arial size=2>Tx2 commit</FONT></DIV></FONT><FONT face=Arial size=2></FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>At this point, both Tx1 and Tx2 succesfully commit, exactly as if Tx1 executed followed by Tx2 (i.e. serialized execution). Note that there is no blocking whatsoever. There is absolutely no way that this would cause an abort of either tx.</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>The only question is how do we work the magic of having the Tx2 read at time 95 retrieve V50 and not V92. Here's how:</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>Each version is marked with the transaction id that created the version (let's call this the Originator Tx ID, or OID) and (implicitly) the transaction id of the youngest transaction that still needs that version (let's call this the Expiry Tx ID, or EID). If the transaction pointed to by the OID has not commited, then EID is null. Otherwise, the EID is the TxID of the youngest, uncomitted Tx at the time of the OID commit. If the EID is null, then the only transaction that is allowed to use that version is the OID transaction. All other transactions will immediately skip to the previous version and evaluate their ordinal relative to the OID and EID of earlier versions.</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>The rule for testing a version for whether it should be used by a given Tx is quite simple - for the sake of clarity, I'm going to assume that the Tx IDs are assigned in ascending order (i.e. their ordinal and value provde the same compareTo() result) - this is not at all strictly necessary, but that's a discussion for another day.</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>Assume we have an active Tx (TXID) that is performing a read on a multi-version record.</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>To locate the version that TXID should use, start with the youngest version and loop backwards through versions until we find the one that meets the following criteria:</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>OID = TXID</FONT></DIV> <DIV><FONT size=2>OR</FONT></DIV> <DIV><FONT size=2>(</FONT></DIV> <DIV><FONT size=2> EID != null</FONT></DIV> <DIV><FONT size=2> AND</FONT></DIV> <DIV><FONT size=2> TXID >= OID</FONT></DIV> <DIV><FONT size=2> AND</FONT></DIV> <DIV><FONT size=2> TXID > EID</FONT></DIV> <DIV><FONT size=2>)</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>A side note: The only time that you'd even have a version with a null EID is in the case of a VLR Tx where the versions were flushed from cache, but that's a fine point (it does lead into a great discussion of why MVCC makes VLR Tx handling a snap, though).</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>At this point, I feel that I've provided sufficient argument to say that my assertion is true.</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>Please tear what I'm saying apart and prove me wrong - lord knows I don't want to make an assumption that messes us up down the road. But I also don't want to lose out on a great implementation strategy that actually does work. [1] does provide a great overview of a lot of CC strategies, but it does not at all cover MVCC as I describe it above. This means that a great deal of care must be taken before applying [1]'s assertions without explicltly testing them against the strategy that's being suggested..</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>I really want to work to get us all on the same page on this - I'm completely open to reviewing any transaction trace against the multi-version system I describe (not the one that [1] describes) - bring it on!</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>I'm going to send you and Alex an Excel spreadsheet I've put together with a sample transaction flow that shows how the above scheme works - please take a few minutes to go through it - I think it will help to explain the strategy. You may also be able to poke holes in the strategy I describe based on what you find there.</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>Cheers,</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT size=2>- Kevin</FONT></DIV> <DIV><FONT size=2></FONT> </DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2> </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>> Kevin,<BR><BR>Yes and no. What you are missing is that MVCC does NOT prevent rw<BR>conflicts. A conflict arises when a reader has already read a version<BR>and a writer attempts to write an earlier version. In MVCC this conflict<BR>results in an abort rather than blocking. See my response to your other<BR>message.<BR><BR>I think that the trick to higher concurrency with 2PL + MVCC is to <BR>modify the semantics of the lock modes in order to permits write-write<BR>conflicts. E.g., X is normally exclusive read / write access. However<BR>if you want to benefit from using MVCC to write multiple versions <BR>concurrently, then you need to modify the locking semantics to permit<BR>concurrent writers. E.g., X is compatible with X and SIX (share<BR>intention exclusive) is compatible with SIX. I do not understand<BR>how read-write conflicts are managed since X can also read.... Maybe<BR>we need to define a "write" lock without read permission so that we<BR>can serialize multiple commits in parallel?<BR><BR>As you can see, I am having a hard time here as well :-)<BR><BR>-bryan <<BR></FONT></FONT></TD></TR></TBODY></TABLE></DIV></FONT></BODY></HTML> |
From: Alex B. <boi...@in...> - 2006-03-02 17:50:29
|
'Kevin Day ' wrote: > BBT: MVCC does NOT remove the rw synchronization problem. This was the > point of figure 11 in [1]. A writer MUST abort if a reader has read > a version later than the timestamp which the writer would write. The > optimistic strategies do NOT block, but may abort during > verification. Yes and no. True if you want completely serializable history. False if you (knowingly) relax the isolation requirements to improve concurrency. alex |
From: Alex B. <boi...@in...> - 2006-03-02 18:35:25
|
Here's a very concrete example to get started. I start a report that will take 15 minutes to complete. It essentially scans all tables of my databases to compute totals, averages and other stats. My isolation requirement here is REPEATABLE_READ since I want my report to be consistent. And I want my report to reflect the status of my data when I started the transaction, say at midnight. Now I need to continue processing transactions between midnight and 00:15am... otherwise my app becomes unavailable and my users will call and wake me up. If what you've said below is true, I can't accept any orders because somehow these updates will find their way into the information I'm processing in parallel for the report, e.g. updating the customer's last purchase date. So we need a way to let transactions update data that's already been read by another transaction in parallel, whether this other transaction has completed or not. Since MVCC works in optistic fashion, both update transactions and my reporting transaction can work in parallel. Update transactions (probably running at SERIALIZABLE isolation level) are allowed to commit since they don't violate any other serializable transactions. And when my reporting transaction completes, it is found that it has not violated any transactional constraints either. Everybody is happy. (I'm not sure if this clearly illustrates a case of relaxing isolation but it does show a case where we don't need to abort a transaction because of a read in another transaction) alex Thompson, Bryan B. wrote: >Alex, > >I am afraid that I simply do not have a handle on how "relaxing" >isolation might cause isolation failures which an application >deems significant. Some of the approaches, e.g., using 2PL to >induce timestamps or assigning timestamps at commit time use >more information to obtain a serializable history, but they are >still serializable histories -- isolation is not broken. > >You appear to be suggesting that we break isolation and I just >do not have any handle on how we can "knowingly" break isolation >in ways which are still "insignificant". > >-bryan > >-----Original Message----- >From: jdb...@li... >To: 'Kevin Day ' >Cc: JDBM Developer listserv >Sent: 3/2/2006 12:49 PM >Subject: Re: [Jdbm-developer] Use of 2PL and MVCC for concurrency > >'Kevin Day ' wrote: > > > >>BBT: MVCC does NOT remove the rw synchronization problem. This was >> >> >the > > >> point of figure 11 in [1]. A writer MUST abort if a reader has >> >> >read > > >> a version later than the timestamp which the writer would write. >> >> >The > > >> optimistic strategies do NOT block, but may abort during >> verification. >> >> > >Yes and no. > >True if you want completely serializable history. > >False if you (knowingly) relax the isolation requirements to improve >concurrency. > >alex > > > >------------------------------------------------------- >This SF.Net email is sponsored by xPML, a groundbreaking scripting >language >that extends applications into web and mobile media. Attend the live >webcast >and join the prime developer group breaking into this new coding >territory! >http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 >_______________________________________________ >Jdbm-developer mailing list >Jdb...@li... >https://lists.sourceforge.net/lists/listinfo/jdbm-developer > > |
From: Kevin D. <ke...@tr...> - 2006-03-02 23:12:15
|
<!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> </DIV> <DIV><FONT face=Arial size=2></FONT></DIV> <DIV><FONT face=Arial size=2>There was actually a pretty good example in one of the papers I read last week...</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Granularity of Locks and Degrees of Consistency in a Shared Data Base - page 381, paragraph starting "To give an example which demonstrates..."</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>This helped me quite a bit with understanding how there are situations where relaxing isolation may be desirable. Our discussion of record id mapping falls into this category of relaxed isolation - if properly designed, the data structure itself is protected against isolation - therefore, incurring the full overhead of full isolation would gain nothing and would cause significant bottlenecking and deadlocks.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>For the vast majority of application level programming, I would expect to find full isolation, though.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>- K</FONT></DIV> <DIV><FONT face=Arial size=2> </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>> Alex,<BR><BR>I am afraid that I simply do not have a handle on how "relaxing"<BR>isolation might cause isolation failures which an application<BR>deems significant. Some of the approaches, e.g., using 2PL to<BR>induce timestamps or assigning timestamps at commit time use<BR>more information to obtain a serializable history, but they are<BR>still serializable histories -- isolation is not broken.<BR><BR>You appear to be suggesting that we break isolation and I just<BR>do not have any handle on how we can "knowingly" break isolation<BR>in ways which are still "insignificant".<BR><BR>-bryan<BR><BR>-----Original Message-----<BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A><BR>To: 'Kevin Day '<BR>Cc: JDBM Developer listserv<BR>Sent: 3/2/2006 12:49 PM<BR>Subject: Re: [Jdbm-developer] Use of 2PL and MVCC for concurrency<BR><BR>'Kevin Day ' wrote:<BR><BR>> BBT: MVCC does NOT remove the rw synchronization problem. This was<BR>the<BR>> point of figure 11 in [1]. A writer MUST abort if a reader has<BR>read<BR>> a version later than the timestamp which the writer would write.<BR>The<BR>> optimistic strategies do NOT block, but may abort during<BR>> verification.<BR><BR>Yes and no.<BR><BR>True if you want completely serializable history.<BR><BR>False if you (knowingly) relax the isolation requirements to improve<BR>concurrency.<BR><BR>alex<BR><BR><BR><BR>-------------------------------------------------------<BR>This SF.Net email is sponsored by xPML, a groundbreaking scripting<BR>language<BR>that extends applications into web and mobile media. Attend the live<BR>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&kid=110944&bid=241720&dat=121642"><FONT color=#0000ff>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642</FONT></A><BR>_______________________________________________<BR>Jdbm-developer mailing list<BR><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><<BR></FONT></FONT></TD></TR></TBODY></TABLE></DIV></FONT></BODY></HTML> |
From: 'Kevin D. ' <ke...@tr...> - 2006-03-03 14:40:10
|
<!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> </DIV> <DIV><FONT face=Arial size=2></FONT></DIV> <DIV><FONT face=Arial size=2>Correct - there are absolutely cases where it is OPK for a tx to have read outdated data (for example, if you were running a tx against a real-time data processing stream and computing a running average, it would certainly be acceptable to change the data that you've already read). In most business application environments this is not going to be the case, but there are certainly cases where it is OK.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Another example is a data structure that takes care of it's own isolation - you can get performance gains by not running such a data structure on top of a CC that is also trying to provide isolation.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>In any case, isolation levels are orthoganol to the particular CC framework. Isolation has more to do with how you choose to handle a given lock conflict (i.e. do you block, do you let it run, do you abort, etc...).</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>- K</FONT></DIV> <DIV><FONT face=Arial size=2> </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>> So, if you do NOT abort the writer and the writer commits, then the<BR>reader (in figure 11) has read "old" (outdated) data and there are<BR>use cases were this does not matter? Is that the point to take away<BR>from this?<BR><BR>I am not sure that this corresponds to any of the traditional isolation<BR>levels for SQL. Perhaps those isolation levels were developed in a 2PL<BR>framework in which it is impossible to read "old" data?<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: 3/2/2006 6:15 PM<BR>Subject: re[2]: [Jdbm-developer] Use of 2PL and MVCC for concurrency<BR><BR>Bryan-<BR><BR>There was actually a pretty good example in one of the papers I read<BR>last week...<BR><BR>Granularity of Locks and Degrees of Consistency in a Shared Data Base -<BR>page 381, paragraph starting "To give an example which demonstrates..."<BR><BR>This helped me quite a bit with understanding how there are situations<BR>where relaxing isolation may be desirable. Our discussion of record id<BR>mapping falls into this category of relaxed isolation - if properly<BR>designed, the data structure itself is protected against isolation -<BR>therefore, incurring the full overhead of full isolation would gain<BR>nothing and would cause significant bottlenecking and deadlocks.<BR><BR>For the vast majority of application level programming, I would expect<BR>to find full isolation, though.<BR><BR>- K<BR> <BR> > Alex,<BR><BR>I am afraid that I simply do not have a handle on how "relaxing"<BR>isolation might cause isolation failures which an application<BR>deems significant. Some of the approaches, e.g., using 2PL to<BR>induce timestamps or assigning timestamps at commit time use<BR>more information to obtain a serializable history, but they are<BR>still serializable histories -- isolation is not broken.<BR><BR>You appear to be suggesting that we break isolation and I just<BR>do not have any handle on how we can "knowingly" break isolation<BR>in ways which are still "insignificant".<BR><BR>-bryan<BR><BR>-----Original Message-----<BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff><mailto:jdb...@li...></FONT></A><BR><A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A><BR>To: 'Kevin Day '<BR>Cc: JDBM Developer listserv<BR>Sent: 3/2/2006 12:49 PM<BR>Subject: Re: [Jdbm-developer] Use of 2PL and MVCC for concurrency<BR><BR>'Kevin Day ' wrote:<BR><BR>> BBT: MVCC does NOT remove the rw synchronization problem. This was<BR>the<BR>> point of figure 11 in [1]. A writer MUST abort if a reader has<BR>read<BR>> a version later than the timestamp which the writer would write.<BR>The<BR>> optimistic strategies do NOT block, but may abort during<BR>> verification.<BR><BR>Yes and no.<BR><BR>True if you want completely serializable history.<BR><BR>False if you (knowingly) relax the isolation requirements to improve<BR>concurrency.<BR><BR>alex<BR><BR><BR><BR>-------------------------------------------------------<BR>This SF.Net email is sponsored by xPML, a groundbreaking scripting<BR>language<BR>that extends applications into web and mobile media. Attend the live<BR>webcast<BR>and join the prime developer group breaking into this new coding<BR>territory!<BR><BR><A href="http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=12164"><FONT color=#0000ff><http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=12164</FONT></A><BR>2><BR><A href="http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642"><FONT color=#0000ff>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642</FONT></A><BR>_______________________________________________<BR>Jdbm-developer mailing list<BR><A href="mailto:Jdb...@li..."><FONT color=#0000ff><mailto:Jdb...@li...></FONT></A><BR><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><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><<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&kid=110944&bid=241720&dat=121642"><FONT color=#0000ff>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&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><<BR></FONT></FONT></TD></TR></TBODY></TABLE></DIV></FONT></BODY></HTML> |