From: Thompson, B. B. <BRY...@sa...> - 2006-03-30 00:12:29
|
Kevin, Yes, I am suggesting that a jdbm application using 2PL will benefit from deepening the resource structure. This can be done declaratively by describing the resource structure as a directed graph. I have not built this facility yet, but it is a planned feature for the 2PL lock system. This is all as described in Gray et alia on locking at multiple granularities [1]. -bryan [1] J.N. Gray, R.A. Lorie, G.R. Putzolu, I.L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base. http://www.seas.upenn.edu/~zives/cis650/papers/granularity-locks.pdf _____ From: jdb...@li... [mailto:jdb...@li...] On Behalf Of Kevin Day Sent: Wednesday, March 29, 2006 12:22 PM To: JDBM Developer listserv Subject: re[8]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- I need to spend some time thinking about the lock escalation aspects of your email - I'll get back to you. My initial thought is that the lock hierarchy is extremely flat in jdbm, so grabbing an intention lock on the parent may not do much for us.... Are you proposing that we deepen the lock hierarchy to help things out? If so, what would that look like? On the re-entrancy comments, I'd like to reword what I think you are proposing just to make sure I understand: Because under 2PL we would never perform a release on a lock unless we are releasing all locks for a given transaction, it matters not at all if the same transaction makes 1, 5 or 10 lock requests on the same resource. If subsequent requests are no-ops, then 2PL guarantees that we won't have re-entrancy issues related to iterative programming, etc... Have I got that right? This should make the implementation a little bit simpler - but at the cost of tying the locking sub-system to 2PL. This may reduce the utility of the locking system for other applications (I'm really not sure on this point). For example, if we were going to attempt to use the same locking mechanism for the locks in the b-link tree, we could run into problems (actually, with b-link, the locks are so granular that I think we could avoid the re-entrancy problem by careful coding - but there may be other situations where that wouldn't be practical). Are there any hard reasons for not doing re-entrant monitor counts? When I've done this kind of thing in the past (hand writing semaphore classes), tracking the count has been pretty easy... - K > Kevin, Not terminating a transaction is going to do more than just cause memory leaks. If you are using locking then it will force other transactions requiring incompatible access to the same resources to block. If any of those resources is frequently used, then it will lock everyone else out of your database! I have another concern with releasing a transaction from a thread. A transaction t which is not bound to a thread is not running, so any other transactions waiting on resources locked by t will be unable to run until t is rebound to another thread. People doing this will have to be very careful. And as I mentioned earlier, transaction restart is going to be interesting if you are passing a transaction along from one thread pool to another. Restart may not be possible in that scenario. I also have questions about reentrant and escalating locks. I am of a mind that neither of these is a good thing. Let me explain. First, by a reentrant lock, do you mean not merely that requesting a lock which you already own is a NOP but that a counter tracks the #of times you have obtained a given lock? That kind of pattern suites recursive programming styles inwhich the locks are given up as you back out, but it is not very suited to 2PL in my mind, where the goal is to steadily acquire locks until the transaction holds all the locks that it needs and to never acquire another lock once it has started releasinglocks. Second, escalating a lock mode, e.g., from S (share) to X (exclusive) may not be such a good idea. The design proposed by Gray et alia used a directed graph of resource to support intention and implicit locks. Rather than escalating a lock on a specific resource, you would obtain an intention lock, e.g., SIX (share intention exclusive) on a parent resource. This would give you share access to all child resources and you could request an exclusive lock on specific child resources. If people want to use 2PL without intention and implicit locking, then there are various consequences. First, the memory burden is much higher since each individual resource requires its own queue to manage locking. Second, there is anincreased likelihood of deadlock since you can not use intention locks to coordinate locking over a child resources, which in turn reduces concurrency. The TxDag class can be reused to support deadlock detection without intention and implicit locking modes. For example, you could leverage the ReadWriteLock class in java.util.concurrent to detect deadlocks using TxDag. However, the ReadWriteLock class does NOT permit escalation of a read lock into a write lock. There are a lot of good reasons to avoid this since it makes deadlock much more likely. I realize that the transparent use of locks in jdbm would seem a natural fit for obtaining a share/read lock when you access a resource and then escalating to a write/exclusive lock when you update a resource, but I am not sure that thisis a practical scheme. -bryan From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Wednesday, March 29, 2006 9:17 AM To: JDBM Developer listserv Subject: re[6]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- Yes. Very elegantly put - I wish I had thought to explain it that way! Another thing that I like about this strategy is that it gives an implicit mechanism for protecting against memory leaks. If a developer creates a transaction and neither commits or aborts it, they can't create and use another one in the same thread without signalling their intention... Also, the thread local storage map could be used to see if a terminated thread still has a tx associated with it - if it does, then there's a memory leak. jdbm could check for that at shutdown and provide a warning log or something. That's a little thing, but it could keep a user of the package from accidentally shooting themselves in the foot... - K > So, the answer is that only the current thread for a tx may release the thread <-> tx bond? So, if the thread is blocked awaiting a lock it will not be possible to release that bond? -bryan From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 9:26 PM To: JDBM Developer listserv Subject: re[4]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- hmmm - I'm not seeing this. Setting the current thread's lock context (i.e. the transaction) shouldn't require any access to any queues at all. If the current thread is blocked, then it wouldn't be able to make the call to release thetransaction from the current lock context... Here's how I'm thinking about it: The queue for a given resource captures the entities that are waiting on that resource (or have locks on that resource). When the lock call is made, the current thread's lock context is retrieved, and that context is used to capture thereservation. If the lock can not be immediately granted, the call to lock() enters a wait loop. At a basic level, this could be achieved by synchronizing on the queue itself, and using wait/notify. The monitor on the wait loop is an event that callsnotify when locks are released from the queue. Why do we need to look at all queues to determine if a single lock request should block or not? - K From: Thompson, Bryan B. Sent: Tuesday, March 28, 2006 7:05 PM To: 'Kevin Day'; JDBM Developer listserv Subject: RE: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip> Kevin, Yes, prototypes may be the way to go. My concern is that blocking is something that a tx may do for any resource that it is accessing. However the notion of setting the bond between a tx and a thread has been discussed in terms of a specific resource / lock. You simply do not know at the Queue level (a single resource) whether or not the transaction is blocked on waiting in a queue for another resource. E.g., this decision needs to be made with respect to all resource locks requested by the tx, not with respect to a single resource. -bryan ________________________________________ From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 6:59 PM To: JDBM Developer listserv Subject: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip> Bryan- Hey - I used to work for Motorolla - we had manuals of TLAs we had to carry around... Any reason to not hold a map of all locks keyed by transaction? I suppose the locks could be held by the tx itself, but it kind of starts pushing the locking code into the transaction management code. I could see where maybe the locked *resource* could be held by the transaction (we will need something like this for caching purposes anyway) - if you are already maintaining a map of resource -> queues, could we combine those two to provide the notification for lock release? I really have no conceptual feel for the "correct" way for this to fall out - I think that we need to do some high level thinking about the interactions of the layers... A proof of concept implementation would be a very good starting place for helping us get our heads around the problem space. Back to the question about enforcing the behavior of the 'current' transaction for the thread not changing if the tx is blocked, I want to make sure that I fully understand your concern. Are you concerned about an application calling setCurrentThreadTransaction() while another thread has that transaction as *it's* current thread transaction? Or something else? Thanks! - K >Kevin, Yes, you do have a thing for TLAs! I think that there are unanswered questions below, notably. It sounds like a transaction probably needs to maintain a collection of all locks that it has obtained and not yet released or requested and not yet obtained. I do not handle this in the locking package since I was trying to avoid making decisions on the behalf of people who were designing their own Transaction API. However, maybe it would make sense if I did a sample design that demonstrated how the locking API could be integrated for that purpose? Bryan wrote: Given that the thread associated with a transaction may not change while that transaction is blocked, how are you going to enforce that at the lockMgr level? There are many, many possible Queue instances. You would need to know whether or not the transaction was blocked in any Queue instance. Are we going to use a thread local variable for that as well? If so, it seems that this would have to be set by Queue.lock(). -bryan ________________________________________ From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 5:29 PM To: 'JDBM Developer listserv ' Subject: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip> Bryan- Gotcha. Gotta love those TLAs... To answer the question about impact on the design I (actually, Alex) suggested: I don't think there is much impact at all, except that the waits for graph needs to hold transaction references, and not references to the current thread. As long as the call to lock() either includes the transaction as a parameter, or does it's own thread local lookup to obtain the transaction, then all is well. If you have the transaction as a parameter, then we can always wrap the library to allow for thread local storage of the current active transaction. If you do the thread local thing internal to the lock library, then we just use the library as is. The biggest thing is that we have got to have the extra level of indirection that allows us to provide a lock context that is not just the current thread, but any object (e.g. Transaction) that we want to associate with the current thread. The current javadocs in the header of the lock class you emailed earlier imply that the thread is itself the lock context, and I think we will want to relax that a bit with one layer of indirection. - K <snip > < < ------------------------------------------------------- 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: Thompson, B. B. <BRY...@sa...> - 2006-03-30 12:01:14
|
A Share or Exclusive lock gives implicit locks on all child resources. The tx does not need to request those locks explicitly. Intention locks are different. E.g., a SIX lock gives a Share locks but requires explicit locking of child resources in exclusive mode. -bryan _____ From: jdb...@li... [mailto:jdb...@li...] On Behalf Of Kevin Day Sent: Wednesday, March 29, 2006 8:14 PM To: JDBM Developer listserv Subject: re[8]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- Can you help me understand the concern on memory usage? In reading the paper on granular locks, the lowest level resource that is going to be worked with still has to be locked. In the normal operation of jdbm, operations are performed at the record level, so this would be the natural locking level. In the Gray paper, even, they show locking down the record level.... How is running 2PL without intention locking going to increase memory usage? - K > If people want to use 2PL without intention and implicit locking, then there are various consequences. First, the memory burden is much higher since each individual resource requires its own queue to manage locking. Second, there is an increased likelihood of deadlock since you can not use intention locks to coordinate locking over a child resources, which in turn reduces concurrency. < ------------------------------------------------------- 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: Thompson, B. B. <BRY...@sa...> - 2006-03-30 12:05:27
|
Incremental release is not a problem. It is just that batch release operations can be more efficient in terms of updating the deadlock detection matrices. The same work has to be done for each Queue in order to remove the transaction that has released its lock and notify waiting transactions that can now run. -bryan _____ From: jdb...@li... [mailto:jdb...@li...] On Behalf Of Kevin Day Sent: Wednesday, March 29, 2006 7:43 PM To: JDBM Developer listserv Subject: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- Fair enough. If allowing for incremental release prevents an efficient large group release implementation, then I absolutely agree with you. If it's a freebie, then it may be useful to have that capability for non 2PL situations - but certainly not at the cost of poor performance on the operation that will happen 99% of the time! I don't have a good feel for how much computational effort is required for incremental release vs batch release. Just noodling some ideas here on handling batch lock release: It seems to me that there are two distinct states for a given lock queue: blocked and unblocked. For an unblocked queue, release should be as simple as just invalidating the transaction object itself (this can happen as a single operation, and doesn't require a huge iteration across all queues that the transaction has ever touched). For a blocked queue, the blocking transaction needs to notify the queue, in addition to marking the transaction as invalid. Any time a lock request is made, invalidated transactions are removed. If the lock blocks, all transactions that currently have a lock on the queue receive a notification request. Does this type of strategy help things at all? I'm still fuzzy on it, but it may be an option that is more palatable than any alternatives... Along those lines, am I correct in assuming that a given transaction needs to hold on to a list of records it has read from and written to? I suspect this is a definite requirement for optimistic locking, and may be required to allow for batch unlocking. It's almost like we are moving the object cache into the transaction itself... If that's the case, then the cost of setting up lock release notifications may not be worth it - in other words, it may be faster for the tx to just iterate all of the resources it has locked and release them. - K > Kevin, It is just that it is not appropriate to a 2PL lock subsystem. You can of course use another lock subsystem. 2PL does permit applications to release locks incrementally, rather than just all at once, but my impression is that locks tend to be released in large groups. -bryan From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Alex Boisvert Sent: Wednesday, March 29, 2006 3:57 PM To: Kevin Day Cc: JDBM Developer listserv Subject: Re: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Kevin Day wrote: On the re-entrancy comments, I'd like to reword what I think you are proposing just to make sure I understand: Because under 2PL we would never perform a release on a lock unless we are releasing all locks for a given transaction, it matters not at all if the same transaction makes 1, 5 or 10 lock requests on the same resource. If subsequent requests are no-ops, then 2PL guarantees that we won't have re-entrancy issues related to iterative programming, etc... This is my understanding as well. 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: Thompson, B. B. <BRY...@sa...> - 2006-03-30 12:38:52
|
Kevin, I am sure that you are going to come back with this question, so let me answer up front. I do not have support for the intention/implict lock model implemented yet. I am not sure whether the SIX is essentially escalated to an X lock. Broadly, it is my understanding that the exclusive access will block until there are no other share locks on the parent/child resources, at which time the write operations will go through. My intention has been to prove out the basic queue and deadlock mechanisms and then go back and add the support for intention and implict locking to the Queue. It is basically a protocol for how you acquire and release locks on resources. -bryan _____ From: ke...@tr... [mailto:ke...@tr...] Sent: Wednesday, March 29, 2006 8:09 PM To: Thompson, Bryan B. Subject: re[8]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- One other question - just to make sure I'm clear on things: You aren't suggesting that a tx can't escalate a lock on a record from S to X, right? You are just saying that we can use lock hierarchies with intention locks to keep us from having to deal with thousands of locks, right? So, when I do a read on a given record, I'd grab a IS lock on some higher level layer (yet to be determined), that gates access to say a range of 500 records that happens to include the record of interest. I would then do my read. If I then later decide that I need to actually update the record, I would attempt to upgrade my IS lock to a SIX lock, at which point I would be granted exlusive access to the 500 records, or I would block. It seems that there is definitely no reason that the granularity of the above couldn't be the individual record (i.e. why block 500 records when I only need to use one of them?) - but at the cost of having to maintain a lot of individual locks. Unless those 500 records happened to be selected in a manner that would group them in a manner that avoided deadlock (and this would require much more information than is available to the database layer), I'm not sure that I see how this could help with avoiding deadlock. Keep in mind that a properly designed application will prevent most of this kind of issue at the application level - very likely using some sort of locking mechanism. Anyway, I think the idea of heirarchal lock structures is interesting - I'm just not seeing how to apply it just yet... Actually, what do you think about this (this is a completely random, half-baked thought, so it may be bunk): In jdbm2, I think that we actually do have a meaningful higher level grouping of records - the records that have been used first by a given transaction may make for a nice layer for lock resolution... For example: If Tx1 is the first tx to read RowA, RowB and RowC, then those 3 rows become part of a lock grouping called L1. If Tx2 comes along and reads RowB and RowD, then only RowD becomes part of locking group L2. RowB remains in locking group L1. So, Tx1 will, by definition have IS access on L1. If it decides that it needs to make any updates, it escalates it's access to L1 to SIX. If Tx2 then decides to modify RowB, it would have to escalate it's access to L1 to SIX (which would block until Tx1 terminates). I have no idea whether this would be better than just arbitrarily assigning ranges of recids to lock groups - but maybe... - K > Kevin, Not terminating a transaction is going to do more than just cause memory leaks. If you are using locking then it will force other transactions requiring incompatible access to the same resources to block. If any of those resources is frequently used, then it will lock everyone else out of your database! I have another concern with releasing a transaction from a thread. A transaction t which is not bound to a thread is not running, so any other transactions waiting on resources locked by t will be unable to run until t is rebound to another thread. People doing this will have to be very careful. And as I mentioned earlier, transaction restart is going to be interesting if you are passing a transaction along from one thread pool to another. Restart may not be possible in that scenario. I also have questions about reentrant and escalating locks. I am of a mind that neither of these is a good thing. Let me explain. First, by a reentrant lock, do you mean not merely that requesting a lock which you already own is a NOP but that a counter tracks the #of times you have obtained a given lock? That kind of pattern suites recursive programming styles inwhich the locks are given up as you back out, but it is not very suited to 2PL in my mind, where the goal is to steadily acquire locks until the transaction holds all the locks that it needs and to never acquire another lock once it has started releasinglocks. Second, escalating a lock mode, e.g., from S (share) to X (exclusive) may not be such a good idea. The design proposed by Gray et alia used a directed graph of resource to support intention and implicit locks. Rather than escalating a lock on a specific resource, you would obtain an intention lock, e.g., SIX (share intention exclusive) on a parent resource. This would give you share access to all child resources and you could request an exclusive lock on specific child resources. If people want to use 2PL without intention and implicit locking, then there are various consequences. First, the memory burden is much higher since each individual resource requires its own queue to manage locking. Second, there is anincreased likelihood of deadlock since you can not use intention locks to coordinate locking over a child resources, which in turn reduces concurrency. The TxDag class can be reused to support deadlock detection without intention and implicit locking modes. For example, you could leverage the ReadWriteLock class in java.util.concurrent to detect deadlocks using TxDag. However, the ReadWriteLock class does NOT permit escalation of a read lock into a write lock. There are a lot of good reasons to avoid this since it makes deadlock much more likely. I realize that the transparent use of locks in jdbm would seem a natural fit for obtaining a share/read lock when you access a resource and then escalating to a write/exclusive lock when you update a resource, but I am not sure that thisis a practical scheme. -bryan From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Wednesday, March 29, 2006 9:17 AM To: JDBM Developer listserv Subject: re[6]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- Yes. Very elegantly put - I wish I had thought to explain it that way! Another thing that I like about this strategy is that it gives an implicit mechanism for protecting against memory leaks. If a developer creates a transaction and neither commits or aborts it, they can't create and use another one in the same thread without signalling their intention... Also, the thread local storage map could be used to see if a terminated thread still has a tx associated with it - if it does, then there's a memory leak. jdbm could check for that at shutdown and provide a warning log or something. That's a little thing, but it could keep a user of the package from accidentally shooting themselves in the foot... - K > So, the answer is that only the current thread for a tx may release the thread <-> tx bond? So, if the thread is blocked awaiting a lock it will not be possible to release that bond? -bryan From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 9:26 PM To: JDBM Developer listserv Subject: re[4]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> Bryan- hmmm - I'm not seeing this. Setting the current thread's lock context (i.e. the transaction) shouldn't require any access to any queues at all. If the current thread is blocked, then it wouldn't be able to make the call to release thetransaction from the current lock context... Here's how I'm thinking about it: The queue for a given resource captures the entities that are waiting on that resource (or have locks on that resource). When the lock call is made, the current thread's lock context is retrieved, and that context is used to capture thereservation. If the lock can not be immediately granted, the call to lock() enters a wait loop. At a basic level, this could be achieved by synchronizing on the queue itself, and using wait/notify. The monitor on the wait loop is an event that callsnotify when locks are released from the queue. Why do we need to look at all queues to determine if a single lock request should block or not? - K From: Thompson, Bryan B. Sent: Tuesday, March 28, 2006 7:05 PM To: 'Kevin Day'; JDBM Developer listserv Subject: RE: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip> Kevin, Yes, prototypes may be the way to go. My concern is that blocking is something that a tx may do for any resource that it is accessing. However the notion of setting the bond between a tx and a thread has been discussed in terms of a specific resource / lock. You simply do not know at the Queue level (a single resource) whether or not the transaction is blocked on waiting in a queue for another resource. E.g., this decision needs to be made with respect to all resource locks requested by the tx, not with respect to a single resource. -bryan ________________________________________ From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 6:59 PM To: JDBM Developer listserv Subject: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip> Bryan- Hey - I used to work for Motorolla - we had manuals of TLAs we had to carry around... Any reason to not hold a map of all locks keyed by transaction? I suppose the locks could be held by the tx itself, but it kind of starts pushing the locking code into the transaction management code. I could see where maybe the locked *resource* could be held by the transaction (we will need something like this for caching purposes anyway) - if you are already maintaining a map of resource -> queues, could we combine those two to provide the notification for lock release? I really have no conceptual feel for the "correct" way for this to fall out - I think that we need to do some high level thinking about the interactions of the layers... A proof of concept implementation would be a very good starting place for helping us get our heads around the problem space. Back to the question about enforcing the behavior of the 'current' transaction for the thread not changing if the tx is blocked, I want to make sure that I fully understand your concern. Are you concerned about an application calling setCurrentThreadTransaction() while another thread has that transaction as *it's* current thread transaction? Or something else? Thanks! - K >Kevin, Yes, you do have a thing for TLAs! I think that there are unanswered questions below, notably. It sounds like a transaction probably needs to maintain a collection of all locks that it has obtained and not yet released or requested and not yet obtained. I do not handle this in the locking package since I was trying to avoid making decisions on the behalf of people who were designing their own Transaction API. However, maybe it would make sense if I did a sample design that demonstrated how the locking API could be integrated for that purpose? Bryan wrote: Given that the thread associated with a transaction may not change while that transaction is blocked, how are you going to enforce that at the lockMgr level? There are many, many possible Queue instances. You would need to know whether or not the transaction was blocked in any Queue instance. Are we going to use a thread local variable for that as well? If so, it seems that this would have to be set by Queue.lock(). -bryan ________________________________________ From: jdb...@li... <mailto:jdb...@li...> [mailto:jdb...@li...] <mailto:jdb...@li...> On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 5:29 PM To: 'JDBM Developer listserv ' Subject: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip> Bryan- Gotcha. Gotta love those TLAs... To answer the question about impact on the design I (actually, Alex) suggested: I don't think there is much impact at all, except that the waits for graph needs to hold transaction references, and not references to the current thread. As long as the call to lock() either includes the transaction as a parameter, or does it's own thread local lookup to obtain the transaction, then all is well. If you have the transaction as a parameter, then we can always wrap the library to allow for thread local storage of the current active transaction. If you do the thread local thing internal to the lock library, then we just use the library as is. The biggest thing is that we have got to have the extra level of indirection that allows us to provide a lock context that is not just the current thread, but any object (e.g. Transaction) that we want to associate with the current thread. The current javadocs in the header of the lock class you emailed earlier imply that the thread is itself the lock context, and I think we will want to relax that a bit with one layer of indirection. - K <snip > < < |
From: 'Kevin D. <ke...@tr...> - 2006-03-30 00:24:53
|
<!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>But what layers would you actually insert? Page, then record? Given that a given record is a logical construct, and a page is a physical construct, I don't think that's going to work... The application itself could certainly impose some sort of lock structure based on how it actually uses the data, but I'm having a bit of a tough time envisioning how to apply multi-layered locking into a general data store like jdbm... It seems to me that any layer added will be artificial.</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Can you give me a picture of what this might look like in the context of jdbm?</FONT></DIV> <DIV><FONT face=Arial size=2></FONT> </DIV> <DIV><FONT face=Arial size=2>Thanks!</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>> <BR>Kevin, <BR> <BR>Yes, I am suggesting that a jdbm application using 2PL will benefit from deepening the resource structure. This can be done declaratively by describing the resource structure as a directed graph. I have not built this facility yet, butit is a planned feature for the 2PL lock system. This is all as described in Gray et alia on locking at multiple granularities [1]. <BR> <BR>-bryan <BR> <BR>[1] J.N. Gray, R.A. Lorie, G.R. Putzolu, I.L. Traiger. <BR> Granularity of Locks and Degrees of Consistency in a Shared Data <BR> Base. <BR> <A href="http://www.seas.upenn.edu/~zives/cis650/papers/granularity-locks.pdf"><FONT color=#0000ff>http://www.seas.upenn.edu/~zives/cis650/papers/granularity-locks.pdf</FONT></A> <BR><BR><BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A> <A href="mailto:jdb...@li..."><FONT color=#0000ff>[mailto:jdb...@li...]</FONT></A> On Behalf Of Kevin Day<BR>Sent: Wednesday, March 29, 2006 12:22 PM<BR>To: JDBM Developer listserv<BR>Subject: re[8]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> <BR> <BR><BR>Bryan- <BR><BR> <BR><BR>I need to spend some time thinking about the lock escalation aspects of your email - I'll get back to you. My initial thought is that the lock hierarchy is extremely flat in jdbm, so grabbing an intention lock on the parent may not do much for us.... Are you proposing that we deepen the lock hierarchy to help things out? If so, what would that look like? <BR><BR> <BR><BR> <BR><BR> <BR><BR>On the re-entrancy comments, I'd like to reword what I think you are proposing just to make sure I understand: Because under 2PL we would never perform a release on a lock unless we are releasing all locks for a given transaction, it matters not at all if the same transaction makes 1, 5 or 10 lock requests on the same resource. If subsequent requests are no-ops, then 2PL guarantees that we won't have re-entrancy issues related to iterative programming, etc... <BR><BR> <BR><BR>Have I got that right? <BR><BR> <BR><BR>This should make the implementation a little bit simpler - but at the cost of tying the locking sub-system to 2PL. This may reduce the utility of the locking system for other applications (I'm really not sure on this point). For example, if we were going to attempt to use the same locking mechanism for the locks in the b-link tree, we could run into problems (actually, with b-link, the locks are so granular that I think we could avoid the re-entrancy problem by careful coding - but there may be other situations where that wouldn't be practical). <BR><BR> <BR><BR>Are there any hard reasons for not doing re-entrant monitor counts? When I've done this kind of thing in the past (hand writing semaphore classes), tracking the count has been pretty easy... <BR><BR> <BR><BR>- K <BR><BR> <BR><BR> <BR>> <BR>Kevin, <BR> <BR>Not terminating a transaction is going to do more than just cause memory leaks. If you are using locking then it will force other transactions requiring incompatible access to the same resources to block. If any of those resources is frequently used, then it will lock everyone else out of your database! <BR> <BR>I have another concern with releasing a transaction from a thread. A transaction t which is not bound to a thread is not running, so any other transactions waiting on resources locked by t will be unable to run until t is rebound to another thread. People doing this will have to be very careful. And as I mentioned earlier, transaction restart is going to be interesting if you are passing a transaction along from one thread pool to another. Restart may not be possible in that scenario. <BR> <BR>I also have questions about reentrant and escalating locks. I am of a mind that neither of these is a good thing. Let me explain. <BR> <BR>First, by a reentrant lock, do you mean not merely that requesting a lock which you already own is a NOP but that a counter tracks the #of times you have obtained a given lock? That kind of pattern suites recursive programming styles inwhich the locks are given up as you back out, but it is not very suited to 2PL in my mind, where the goal is to steadily acquire locks until the transaction holds all the locks that it needs and to never acquire another lock once it has started releasinglocks. <BR> <BR>Second, escalating a lock mode, e.g., from S (share) to X (exclusive) may not be such a good idea. The design proposed by Gray et alia used a directed graph of resource to support intention and implicit locks. Rather than escalating alock on a specific resource, you would obtain an intention lock, e.g., SIX (share intention exclusive) on a parent resource. This would give you share access to all child resources and you could request an exclusive lock on specific child resources. <BR> <BR>If people want to use 2PL without intention and implicit locking, then there are various consequences. First, the memory burden is much higher since each individual resource requires its own queue to manage locking. Second, there is anincreased likelihood of deadlock since you can not use intention locks to coordinate locking over a child resources, which in turn reduces concurrency. <BR> <BR>The TxDag class can be reused to support deadlock detection without intention and implicit locking modes. For example, you could leverage the ReadWriteLock class in java.util.concurrent to detect deadlocks using TxDag. However, the ReadWriteLock class does NOT permit escalation of a read lock into a write lock. There are a lot of good reasons to avoid this since it makes deadlock much more likely. <BR> <BR>I realize that the transparent use of locks in jdbm would seem a natural fit for obtaining a share/read lock when you access a resource and then escalating to a write/exclusive lock when you update a resource, but I am not sure that thisis a practical scheme. <BR> <BR>-bryan <BR> <BR><BR><BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A> <A href="mailto:jdb...@li..."><FONT color=#0000ff>[mailto:jdb...@li...]</FONT></A> On Behalf Of Kevin Day<BR>Sent: Wednesday, March 29, 2006 9:17 AM<BR>To: JDBM Developer listserv<BR>Subject: re[6]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> <BR> <BR><BR>Bryan- <BR><BR> <BR><BR>Yes. Very elegantly put - I wish I had thought to explain it that way! <BR><BR> <BR><BR>Another thing that I like about this strategy is that it gives an implicit mechanism for protecting against memory leaks. If a developer creates a transaction and neither commits or aborts it, they can't create and use another one in the same thread without signalling their intention... Also, the thread local storage map could be used to see if a terminated thread still has a tx associated with it - if it does, then there's a memory leak. jdbm could check for that at shutdown and provide a warning log or something. <BR><BR> <BR><BR>That's a little thing, but it could keep a user of the package from accidentally shooting themselves in the foot... <BR><BR> <BR><BR>- K <BR><BR> <BR><BR> <BR>><BR>So, the answer is that only the current thread for a tx may release the thread <-> tx bond? So, if the thread is blocked awaiting a lock it will not be possible to release that bond? <BR> <BR>-bryan <BR> <BR><BR><BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A> <A href="mailto:jdb...@li..."><FONT color=#0000ff>[mailto:jdb...@li...]</FONT></A> On Behalf Of Kevin Day<BR>Sent: Tuesday, March 28, 2006 9:26 PM<BR>To: JDBM Developer listserv<BR>Subject: re[4]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip> <BR> <BR><BR>Bryan- <BR><BR> <BR><BR>hmmm - I'm not seeing this. Setting the current thread's lock context (i.e. the transaction) shouldn't require any access to any queues at all. If the current thread is blocked, then it wouldn't be able to make the call to release thetransaction from the current lock context... <BR><BR> <BR><BR>Here's how I'm thinking about it: <BR><BR> <BR><BR>The queue for a given resource captures the entities that are waiting on that resource (or have locks on that resource). When the lock call is made, the current thread's lock context is retrieved, and that context is used to capture thereservation. If the lock can not be immediately granted, the call to lock() enters a wait loop. At a basic level, this could be achieved by synchronizing on the queue itself, and using wait/notify. The monitor on the wait loop is an event that callsnotify when locks are released from the queue. <BR><BR> <BR><BR> <BR><BR>Why do we need to look at all queues to determine if a single lock request should block or not? <BR><BR> <BR><BR>- K <BR><BR> <BR><BR> <BR><BR>From: Thompson, Bryan B. <BR>Sent: Tuesday, March 28, 2006 7:05 PM<BR>To: 'Kevin Day'; JDBM Developer listserv<BR>Subject: RE: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads<BR><snip><BR><BR>Kevin,<BR><BR>Yes, prototypes may be the way to go.<BR><BR>My concern is that blocking is something that a tx may do for any resource<BR>that it is accessing. However the notion of setting the bond between a tx<BR>and a thread has been discussed in terms of a specific resource / lock. You<BR>simply do not know at the Queue level (a single resource) whether or not the<BR>transaction is blocked on waiting in a queue for another resource. E.g.,<BR>this decision needs to be made with respect to all resource locks requested<BR>by the tx, not with respect to a single resource.<BR><BR>-bryan<BR><BR>________________________________________<BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A><BR><A href="mailto:jdb...@li..."><FONT color=#0000ff>[mailto:jdb...@li...]</FONT></A> On Behalf Of Kevin Day<BR>Sent: Tuesday, March 28, 2006 6:59 PM<BR>To: JDBM Developer listserv<BR>Subject: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip><BR><BR>Bryan-<BR> <BR>Hey - I used to work for Motorolla - we had manuals of TLAs we had to carry<BR>around...<BR> <BR>Any reason to not hold a map of all locks keyed by transaction? I suppose<BR>the locks could be held by the tx itself, but it kind of starts pushing the<BR>locking code into the transaction management code. I could see where maybe<BR>the locked *resource* could be held by the transaction (we will need<BR>something like this for caching purposes anyway) - if you are already<BR>maintaining a map of resource -> queues, could we combine those two to<BR>provide the notification for lock release?<BR> <BR>I really have no conceptual feel for the "correct" way for this to fall out<BR>- I think that we need to do some high level thinking about the interactions<BR>of the layers... A proof of concept implementation would be a very good<BR>starting place for helping us get our heads around the problem space.<BR> <BR> <BR> <BR>Back to the question about enforcing the behavior of the 'current'<BR>transaction for the thread not changing if the tx is blocked, I want to make<BR>sure that I fully understand your concern. Are you concerned about an<BR>application calling setCurrentThreadTransaction() while another thread has<BR>that transaction as *it's* current thread transaction?<BR> <BR>Or something else?<BR> <BR>Thanks!<BR> <BR>- K<BR> <BR> <BR> <BR> <BR> <BR><BR>>Kevin,<BR><BR>Yes, you do have a thing for TLAs!<BR><BR>I think that there are unanswered questions below, notably. It sounds like<BR>a transaction probably needs to maintain a collection of all locks that it<BR>has obtained and not yet released or requested and not yet obtained. I do<BR>not handle this in the locking package since I was trying to avoid making<BR>decisions on the behalf of people who were designing their own Transaction<BR>API. However, maybe it would make sense if I did a sample design that<BR>demonstrated how the locking API could be integrated for that purpose?<BR><BR>Bryan wrote:<BR><BR>Given that the thread associated with a transaction may not change while<BR>that transaction is blocked, how are you going to enforce that at the<BR>lockMgr level? There are many, many possible Queue instances. You<BR>would need to know whether or not the transaction was blocked in any Queue<BR>instance. Are we going to use a thread local variable for that as well?<BR>If so, it seems that this would have to be set by Queue.lock().<BR><BR>-bryan<BR>________________________________________<BR>From: <A href="mailto:jdb...@li..."><FONT color=#0000ff>jdb...@li...</FONT></A><BR><A href="mailto:jdb...@li..."><FONT color=#0000ff>[mailto:jdb...@li...]</FONT></A> On Behalf Of Kevin Day <BR>Sent: Tuesday, March 28, 2006 5:29 PM<BR>To: 'JDBM Developer listserv '<BR>Subject: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip><BR><BR>Bryan-<BR> <BR>Gotcha. Gotta love those TLAs...<BR> <BR>To answer the question about impact on the design I (actually,<BR>Alex) suggested:<BR> <BR>I don't think there is much impact at all, except that the waits for graph<BR>needs to hold transaction references, and not references to the current<BR>thread.<BR> <BR>As long as the call to lock() either includes the transaction as a<BR>parameter, or does it's own thread local lookup to obtain the transaction,<BR>then all is well.<BR> <BR>If you have the transaction as a parameter, then we can always wrap the<BR>library to allow for thread local storage of the current active<BR>transaction. If you do the thread local thing internal to the lock library,<BR>then we just use the library as is.<BR> <BR>The biggest thing is that we have got to have the extra level of indirection<BR>that allows us to provide a lock context that is not just the current<BR>thread, but any object (e.g. Transaction) that we want to associate with the<BR>current thread. The current javadocs in the header of the lock class you<BR>emailed earlier imply that the thread is itself the lock context, and I<BR>think we will want to relax that a bit with one layer of indirection.<BR> <BR>- K<BR> <BR><snip > <BR><<BR><<BR><<BR></FONT></FONT></TD></TR></TBODY></TABLE></DIV></FONT></BODY></HTML> |