From: Thompson, B. B. <BRY...@sa...> - 2006-03-28 17:37:21
|
Resend as plain test to get around the listserve message size limit. = -bryan ________________________________________ From: Thompson, Bryan B.=20 Sent: Tuesday, March 28, 2006 12:32 PM To: 'Kevin Day '; ''JDBM Developer listserv ' ' Subject: RE: re[8]: [Jdbm-developer] 2PL: transactions, threads and = lockin g (rese nd!) Kevin, There seems to be an API mismatch still.=A0 There is no single "lock = manager", rather there is a queue per resource.=A0 It seems that we need to = deepen our examples a little bit so that we can show the relationship between = these things.=A0 Let me just focus on the fetch operation for a minute. void DATA fetch(recid){ =A0=A0=A0=A0lockMgr.assertCurrentTransaction(this); // this will throw = an exception if the current tx for the thread is not 'this' =A0=A0=A0=A0lockMgr.lock(recid, READ); =A0=A0=A0=A0// do actual fetch } If I accept this as written, then I would infer: lockMgr.lock( long recid, mode ) { =A0=A0=A0 Object transaction =3D getCurrentThreadTransaction(); // = error if not defined. =A0=A0=A0 Queue queue =3D get( recid ); // creates queue if none exists = for that resource =A0=A0=A0 queue.lock( transaction, mode ); // blocks if lock not = available; error if deadlock would result. } Note that lockMgr.get( long recid ) should use a weak value hash map so = that we can GC Queues for resources that are no longer in use.=A0 If we = don't do this then we will swiftly run out of memory.=20 The thread that would block is the thread in which lockMgr.lock is = invoked.=A0 The synchronization logic inside of Queue.lock() needs to operate on threads, so Queue would need to track the thread in which lock() was = invoked for each request that blocked.=A0 This is required in order to = notifyAll() the thread when the lock is available.=A0 The rest of the queue state (the = granted group and pending requests queue) and the state for the deadlock = detection algorithm (TxDag) can be based on transaction objects. 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?=A0 There are many, many possible Queue instances.=A0 You = would need to know whether or not the transaction was blocked in any Queue instance.=A0 Are we going to use a thread local variable for that as = well?=A0 If so, it seems that this would have to be set by Queue.lock(). -bryan ________________________________________ From: jdb...@li... [mailto:jdb...@li...] On Behalf Of Kevin = Day=20 Sent: Tuesday, March 28, 2006 11:34 AM To: ''JDBM Developer listserv ' ' Subject: re[8]: [Jdbm-developer] 2PL: transactions, threads and lockin = g (rese nd!) Bryan- =A0 >> Just to be clear, the design that I proposed did not allow the possibility >> one thread running more than one transaction. =A0 Right - that's why I'm proposing a subtle change to the approch where = locks are transaction based and not thread based. =A0 =A0 Alex - In the following discussion, notice that we are having to do a = lot of asserts in the transaction methods - this is one of the reasons that I = was thinking we should just pass the transaction into the=A0calls on the = lock manager...=A0 If we do that, it gets rid of the = setCurrentThreadTransaction and releaseCurrentThreadTransaction completely, and keeps the context = of the locks straight...=A0 I guess I'm still not entirely convinced that = using the thread local variable is a good thing here... =A0 =A0 =A0 Anyway, back to the proposed implementation using thread local: =A0 Bryan - in this design, setCurrentThreadTransaction must be called = before the API is used for performing locking operations on a given = transaction.=A0=20 =A0 =A0 =A0 In extremely rough pseudo code, here is how these methods would be = used.=A0 There may very well be a good way to refactor this (not sure if the = lock manager reference belongs in the transaction object itself), but it = gets the idea across: =A0 void startTransaction(){ =A0=A0=A0=A0lockMgr.setCurrentThreadTransaction(this); // this will = throw exception if there is already a current tx for the thread =A0=A0=A0=A0return tx; } =A0 void suspendTransaction(){ =A0=A0=A0=A0Transaction oldTx =3D = lockMgr.releaseCurrentThreadTransaction(); =A0=A0=A0 assert(oldTx =3D=3D this); // if this is not true, something = bad happened } =A0 void resumeTransaction(){ =A0=A0=A0=A0lockMgr.setCurrentThreadTransaction(this); // this will = throw exception if there is already a current tx for the thread } =A0 void DATA fetch(recid){ =A0=A0=A0=A0lockMgr.assertCurrentTransaction(this); // this will throw = an exception if the current tx for the thread is not 'this' =A0=A0=A0=A0lockMgr.lock(recid, READ); =A0=A0=A0=A0// do actual fetch } =A0 void commit(){ =A0=A0=A0=A0lockMgr.assertCurrentTransaction(this); =A0=A0=A0=A0lockMgr.releaseLocks(); =A0=A0=A0=A0lockMgr.releaseCurrentThreadTransaction(); =A0=A0=A0=A0// do actual commit =A0 } =A0 =A0 Please note that I'm not convinced that the above is the way to go - = but I am pretty sure that dis-allowing overlapping transactions in the same = thread is not a design tradeoff we want to make at this point... =A0 =A0 - K =A0=20 > Kevin, Just to be clear, the design that I proposed did not allow the = possibility of one thread running more than one transaction. =A0Now, on to your = proposal. Can you clarify the semantics of the following when setCurrentThreadTransaction( Object transaction ) has not been called? = =A0Is it illegal to use the locking API in this case? Also, can you build out how you would use these methods to construct = the start/suspend/resume semantics that we have been discussing? -bryan -----Original Message----- From: jdb...@li... To: 'JDBM Developer listserv ' Sent: 3/28/2006 10:19 AM Subject: re[6]: [Jdbm-developer] 2PL: transactions, threads and lockin = =A0g (rese nd!) Bryan- > We are straying a little far away from this use case in our discussions and > I would like to handle this before getting into more rarified use cases. =A0We > can always refactor once we have the basic mechanisms in place, = right? Actually, I think that the current discussion is quite important to making sure we don't get painted into a corner that will be very difficult to get out of. =A0If we know up front that the thread->transaction equivalence in the current discussion is going to = be a problem, I think that we should consider a different approach. I'm not suggesting that we actually design or write code for the high concurrency, non blocking situation - just that we don't intentionally make a design decision that would preclude future development in this area. I think that Alex's suggestion on one *current* transaction per thread is a nice compromise that should be relatively easy to include in the design. =A0I think this needs to be addressed now, instead of pushing = it out and attempting to refactor later, because it will absolutely impact the interface to the locking sub-system. I believe that this is relatively simple to do - just have the locking subsystem have the following additional calls: setCurrentThreadTransaction(Object transaction) - if there is already a current transaction for the thread, this call throws an exception. Otherwise, it sets the current transaction for the thread in thread local storage ( http://java.sun.com/j2se/1.5.0/docs/api/java/lang/ThreadLocal.html <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/ThreadLocal.html> ) Object releaseCurrentThreadTransaction() - Clears the thread local = value and returns the old transaction object that was stored there.=20 Once we have this in place, all locking calls operate in the context of the transaction stored in the thread local variable, instad of using Thread.currentThread() to obtain context. Another thing to consider here: =A0If we use thread->transaction equivalence, and we do wind up with multiple overlapping transactions running on the same thread (for example, if we are running a unit test to check things out), the lock system will fail. =A0I'd much rather see = a deadlock occur than the locking fail to operate properly in this situation. - K =A0 =A0=A0=A0=A0> Kevin, It seems to me that the core use case for 2PL is to force serial execution of concurrent processes when those processes would result in incompatible access to the same resource and to detect and abort (or restart) transactions whose locking requests would result in a deadlock We are straying a little far away from this use case in our discussions and I would like to handle this before getting into more rarified use = cases. We can always refactor once we have the basic mechanisms in place, right? It is clear that we need to continue what is essentially a requirements discussion for jdbm transactions, but I would like to take a phased approach to this so that we do not demand up front more than we can easily accomplish. Does that make sense? -bryan -----Original Message----- From: =A0<mailto:jdb...@li...> jdb...@li... To: JDBM Developer listserv Sent: 3/28/2006 9:45 AM Subject: re[4]: [Jdbm-developer] 2PL: transactions, threads and lockin = g (rese nd!) Bryan- In the non-blocking IO situation, the developer wouldn't make a = blocking call - that's why I explicitly requested non-blocking lock checks. = =A0In that situation, the lock request would fail, and the system would queue the request for the next cycle through - in effect, the state machine for the request context would switch from 'active processing' to 'try again'. We may very well find that using optimistic locking is more appropriate for these high performance non-blocking IO operation, or we may find that providing a completely separate non blocking interface to jdbm2 it the way to go. =A0My goal here is to make sure we don't make any design decisions that would preclude that possibility in the future (I definitely don't think we want to include that in our first cut at developing the system). If we make a hard thread->transaction 1:1 mapping, this would = definitely preclude the possibility, so I want to make sure we relax that requirement. Your comments on locking vs synchronization are dead on. =A0These two concepts share many attributes, but they are definitely not the same. = =A0I think Alex's comment regarding the concurrent package was that if a developer *wanted* to implement synchronization mechanisms to better manage the database interaction, they could. =A0There is often = information at the application level that allows for more efficient processing of requests than 2PL - for example, an application server could have a business object that it synchronizes when it makes changes to it. =A0If you have a ton of threads that could all be making changes to that object at the same time, synchronization would be a very good idea, = even though the low level locking in the database would theoretically = protect against data corruption due to concurrent access. Another thing to consider in the locking library is that maybe all of the methods should be non blocking, but make a monitor object available if a user of the framework wants to actually block. =A0The concurrent package could be used for handling the details of blocking, release, etc... and it keeps the locking/blocking concerns separated... =A0just = a thought... In jdbm's use of the locking library, we would almost certainly block = if a lock failed - at least in 2PL mode. Cheers! - K =A0=A0=A0>=20 Let me try to summarize. =A0There are two reasons why = start/suspend/resume might be required: non-blocking single threaded IO and passing responsibility for executing a transaction down a chain of thread pools associated with a staged processing model. =A0The other use case that I find interesting is parallel processing. =A0=A0 The staged processing use case makes the most sense, but I wonder what = a transaction restart would look like under that framework? =A0It seems = that not only would the tx need to restart, but it would need to restart at the first thread pool of the staged processor.=20 I am not convinced that a persistence layer that is using a locking strategy is suitable for a non-blocking single threaded process. =A0If = any lock request blocks, then the entire server will halt without a chance to resume. =A0This seems unworkable. =A0My other concern with this = scenario is that the latency involved in disk IO can be quite large and is not necessarily predicable, e.g., an incremental write could occur at an arbitrary moment. =A0Such latency could cause the server to drop = messages, which also seems unworkable. =A0Please let me know if I am wrong, but I = do not see how jdbm could be used in such an environment, especially in conjunction with a locking strategy for managing resource access contention.=20 However, I would also like to talk more about the 2PL locking model. = =A0I have been designing based on the early work by Gray and Bayer covering 2PL, intention and implicit locking, and online deadlock detection algorithms. =A0This is quite different from java.util.concurrent in two ways. =A0First, the lock modes are not just READ (Share) and WRITE (Exclusive), but also include intention and implicit lock modes. Second, deadlocks are detected using an induced WAITS_FOR graph among the transactions that are blocked. =A0There is no comparable feature in java.util.concurrent =A0the classes in those packages are not design to support deadlock detection.=20 I have been writing up the package semantics for the 2PL support [1]. Some feedback on this would be useful.=20 Thanks,=20 -bryan=20 [1] <http://cvs.sourceforge.net/viewcvs.py/cweb/concurrent/src/java/org/Cogn= > <http://cvs.sourceforge.net/viewcvs.py/cweb/concurrent/src/java/org/Cogn= itiveWeb/concurrent/locking/package.html?rev=3D1.3&view=3Dlog> <http://cvs.sourceforge.net/viewcvs.py/cweb/concurrent/src/java/org/Cogn= i> http://cvs.sourceforge.net/viewcvs.py/cweb/concurrent/src/java/org/Cogni= tiveWeb/concurrent/locking/package.html?rev=3D1.3&view=3Dlog=20 From: =A0=A0=A0<mailto:jdb...@li...> <mailto:jdb...@li...> <mailto:jdb...@li...> jdb...@li... <mailto:jdb...@li...> <mailto:jdb...@li...> <mailto:jdb...@li...> [mailto:jdb...@li...] On Behalf Of Kevin Day Sent: Tuesday, March 28, 2006 12:06 AM To: JDBM Developer listserv Subject: re[2]: [Jdbm-developer] 2PL: transactions, threads and locking (rese nd!)=20 Alex-=20 OK - I wrote a big long email explaining my thoughts, and finally managed to work myself around to understanding where you are coming from...=20 Suspend and resume does indeed take care of the issue. =A0If each = thread has a single active transaction, then that thread will block as soon as it hits a lock that doesn't belong to that transaction. =A0The key is = that if a tx is blocked, it can't possibly be switched to a different thread (this is what the suspend call is providing for), which ensures that we can't have multiple threads making calls against the same tx at the = same time. =A0At this point, blocking becomes a matter of simple wait/notify = on the lock object - unless we want to implement some sort of priority based notification (which we might...).=20 This means that using thread local storage for the transaction does = make sense. =A0I also think that the transaction itself will need to store = it's associated thread for use in checks to ensure that the user doesn't continue to use a tx after it suspends it. =A0I suppose another thing = that could be done here would be to make the resume call implicit (we are already going to have to check each Transaction.insert/update/delete/commit call to ensure that the current thread is correct).=20 Not sure about the performance implications of actually performing that check for each call...=20 Thanks guys, sorry to slow the process down.=20 - K=20 > Kevin Day wrote:=20 Interesting. =A0Does this imply that there can only be one executing Tx per thread at any given point in time? =A0I think this starts to break down, though, because you can't release the locks when you suspend a Tx (not without viloating 2PL, anyway). I don't understand. =A0Can you provide an example of what you mean? No matter what Bryan does, he still has to deal with the fact that a single thread could wind up needing to block itself (by definition, = this would be deadlock). =A0This scenario is pretty easy to detect, and = should probably abort one of the transactions (it implies that the application developer has not designed their threading/transaction handling properly). In the scheme I was proposing, a transaction holds locks, = not a thread. =A0=A0If a transaction holds a lock, it cannot block itself. = =A0You can only get into a deadlock situation with two or more transactions. (If you want locks for synchronizing threads, you can use java.util.concurrency or something alike) alex < < =A0=A0=A0 ------------------------------------------------------- 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=3Dlnk&kid=3D110944&bid=3D241720&dat= =3D12164 2> http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ Jdbm-developer mailing list =A0<mailto:Jdb...@li...> Jdb...@li... <https://lists.sourceforge.net/lists/listinfo/jdbm-developer> https://lists.sourceforge.net/lists/listinfo/jdbm-developer < =A0=A0=A0=A0 ------------------------------------------------------- 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=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ Jdbm-developer mailing list Jdb...@li... https://lists.sourceforge.net/lists/listinfo/jdbm-developer < |