I am thinking in terms of building concurrency utilities right now and gaining some experience with them and then figuring out how to support the integration of different concurrency strategies within the store.  I would like to look at optimistic concurrency control strategies next, but I wanted to start out with a 2PL strategy first in order to support the easier path to a concurrent jdbm design.

 

-bryan

 


From: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] On Behalf Of Kevin Day
Sent: Thursday, March 30, 2006 9:46 AM
To: JDBM Developer listserv
Subject: re[12]: [Jdbm-developer] re[14]: 2PL: transactions, threads < s nip>

 

Bryan-

 

Perfect - I'm glad that I understand where you are coming from now.

 

This is actually a very natural extension (and improvement) to our earlier conversations about exposing a mechanism for allowing application developers to use higher level synchronization constructs on jdbm resources.  I think that as long as we expose an appropriate lock object, that the application developer can use whatever locking system they want for the higher level stuff.

 

If a developer does this kind of implementation, then giving them an optimistic locking option in jdbm will make for a very nice solution.

 

At this time, though, I do not think that this type of locking needs to be accounted for in the jdbm design (other than exposing a unique, cross-transactional object that represents each row).

 

 

So....  do we need to implement 2PL at the jdbm level?  Or do we use optimistic, and tell developers that they have to use locking at the application level if they want to avoid rollbacks for highly contended records?

 

What do you guys think?

 

- K

 

 

>
Kevin,
 
Yes, the application would have to define this structured based on its own structure.  The notion is that it could declare this structure using a directed graph model and that implict and intention locking would operate in terms of that structure.
 
Without such a structure you only have read (share) and write (exclusive) locks.  You can still use deadlock detection in fact, you must, but you may loose concurrency and efficiency in the locking system with respect to an application that declares such structures.  It all depends of course on your application.
 
We can look at other locking models than the one proposed by Gray.  E.g., integrating java.util.concurrents read-write lock with the deadlock detection.  In this sense the locking system should be, if not pluggable, then at least integratable (if that is a word) by the application.  Use of different locking models may require different APIs, so classes such as the TransactionManager and Tx that I sent out yesterday might be possible integrations that an application could use, or write their own.
 
I think that we are probably heading in this direction anyway since there is interest in concurrency utilities as opposed to concurrency solutions.
 
-bryan
 


From: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] On Behalf Of Kevin Day
Sent: Wednesday, March 29, 2006 7:29 PM
To: JDBM Developer listserv
Subject: re[10]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip>
 

Bryan-

 

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.

 

Can you give me a picture of what this might look like in the context of jdbm?

 

Thanks!

 

- K

  

 
>
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, 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].
 
-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: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] 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 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.  
 
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: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] 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: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] 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: jdbm-developer-admin@lists.sourceforge.net
[mailto:jdbm-developer-admin@lists.sourceforge.net] 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: jdbm-developer-admin@lists.sourceforge.net
[mailto:jdbm-developer-admin@lists.sourceforge.net] 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 Jdbm-developer@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/jdbm-developer