Expand on this please.  What is the role fulfilled by locking in this design? -bryan

 


From: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] On Behalf Of Kevin Day
Sent: Tuesday, April 04, 2006 10:40 AM
To: JDBM Developer listserv
Subject: re[8]: [Jdbm-developer] re[2]: DefaultTransactionManager - dr aft of prototype.

 

Bryan-

 

This is completely different with MVCC.  Transactions operate in complete isolation from each other, regardless of what type of locking you use.

 

In the proof of concept I've put together, you can release locks whenever you want without violating isolation.  Locking is only necessary to ensure serializability.

 

Nice, eh?

 

- K

 

 

>
Kevin,
 
You need to hold locks until the tx is stable so that no other tx can modify the record during the commit.  Read locks lock out writers and write locks lock out readers.  If you release locks early then various isolation characteristics may be violated.
 
Maybe this is slightly different for MVCC?
 
-bryan
 


From: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] On Behalf Of Kevin Day
Sent: Monday, April 03, 2006 12:34 PM
To: JDBM Developer listserv
Subject: re[6]: [Jdbm-developer] re[2]: DefaultTransactionManager - dr aft of prototype.
 

Bryan-

 

I have not read the article - if you have a reference, please send it on.

 

In terms of beforeCommit/afterCommit, I'm pretty sure that you want to release the locks as early in the process as possible (without violating 2PL).  If you release locks before the commit, you are not violating 2PL because you are guaranteed to never request another lock.  If we do it afterwards, then we are going to be holding locks durring disk writes, etc...  Remember that we are working in a multi-version environment, so we don't have to worry about another transaction clobbering data before it gets written to the safe...

 

If we do have to abort a transaction at commit time (e.g. optimistic locking), we definitely want to abort before we do the processing associated with commiting the transaction - otherwise, we have to go back and undo all the work we've done in the multi-version system, safe, cache, etc...

 

I'm pretty sure that beforeCommit is the way to go on this... but I'm open to a discussion to hash it out.

 

- K

  

 
>
Kevin,
 
I believe that you want to use afterCommit to release the locks since locks must be held during the commit operation.  You probably need before and after events since the important operations may occur before or after depending on the CCmethod.  E.g., validation occurs before while locking releases after.
 
Have you read the FLASK articles?  They should be a good source of guidance on the perils of attempting to abstract the CC policy out of the persistence store.
 
-bryan
 


From: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] On Behalf Of Kevin Day
Sent: Monday, April 03, 2006 11:35 AM
To: JDBM Developer listserv
Subject: re[4]: [Jdbm-developer] re[2]: DefaultTransactionManager - dr aft of prototype.
 

Bryan-

 

In the world I live in (where the sky is purple and dogs talk :-) ), I think of a lock context almost entirely as equivalent to a transaction - but keeping the concept of a lock context separate helps (in my mind at least) me to remembernot to put lock related code into the transaction sub-system.

 

In the recman implementation that I have got going now, I have put together an interface for a lock manager that receives event notifications as the user interacts with the record manager.  It is then the lock manager's responsibility toprovide the correct behavior.

 

Here are the events I have (I'm currently working with 'int' recids, eventually this will be expanded to long):

 

beforeRead(int resource, Object lockContext)

beforeChange(int resource, Object lockContext)

beforeCommit(Object lockContext)

beforeAbort(Object lockContext)

 

 

In a 2PL implementation, the beforeRead and beforeChange calls can block.  beforeCommit and beforeAbort both release all locks held by the specified context.  Natch, your current queue and DAG implementations would be used to implement this.

 

In an optimistic locking implementation, the beforeRead and beforeChange calls will be used to accumulate the read and write set of a given lock context, but would not block.  The beforeCommit would evaluate the read/write sets and abortif they aren't compatible.  beforeAbort would just be for cleanup.

 

 

- K

 

  

 
>
Kevin,
 
No problem.  I will update the 2PL module along the lines that you described and we can reconcile later.  It seems to me that the transaction API for jdbm2 will need to abstract all of this away from the underlying record manager (so that we can have more than one design) and away from the concurrency control logic (so that we can have more than one approach).
 
I am curious whether the concept of a lock context in the 2PL module makes more or less sense than just calling this a transaction.  Locking clearly supports only one property for transactions (isolation), but the notion of lock contextmay be too far removed from transaction.  What do you think?  This will just effect the parameter names and javadoc, not any code.
 
-bryan
 


From: jdbm-developer-admin@lists.sourceforge.net [mailto:jdbm-developer-admin@lists.sourceforge.net] On Behalf Of Kevin Day
Sent: Saturday, April 01, 2006 4:12 PM
To: JDBM Developer listserv
Subject: re[2]: [Jdbm-developer] re[2]: DefaultTransactionManager - draft of prototype.
 

Bryan-

 

I need to implement something along these lines in the transaction manager anyway (I already have the proof of concept for that put together), so I am going to implement the thread local thing at that level.  That approach fixes a numberof dependency issues that I've been unhappy with in the implementation, so I'm going to give it a crack.

 

Once I have that code written (and we have a place to share it :-)  ), I think that it will become evident why Alex suggested this approach.  Now, whether this has any place in the locking subsystem or not, I can't really say.  For the time being, let's just move forward assuming that the calls to lock() and unlock() will all have a parameter that describes the context that the lock is being made in.  I think that this lock context is going to be more important in the deadlock detectionarena than the actual locking arena (although it will, I suspect, be important for properly handling simple re-entrancy and lock upgrades).

 

So, I'm going to implement assuming a lock manager interface (I'll knock something together), then we can hash out the differences between what the transaction manager needs, and what can be provided by your current design.

 

Sound good?

 

Cheers!

 

- K

  

 
>
Kevin,
 
I am still not quite getting it.
 
The constraint that I am seeking to enforce is that at most one thread may do work on (invoke methods on the API of) a transaction at a time.  This constraint is achieved by binding a thread and a transaction.  
 
I realize that I must be misusing the thread local variable since having on the tx makes no sense  that should be a normal private field, in which case it would enforce the constraint that only the thread whose reference was set on thatfield could invoke methods on the tx.  Another thread could obtain the tx only iff the tx had first been released.  So I am not sure that I understand what the thread local variable was supposed to be used for since it looks like the semantics can be obtained directly from a normal field.  
 
If a thread local variable is shared by all access executing in the same thread, then I am not clear how this would be applied to create the constraint that at most one thread at a time may do work on a tx.
 
Perhaps it would be easier and more robust to make the queue / lock smarter so that it tracked internally the thread that a transaction was bound to during a lock request.  E.g., using a hash map based on the transaction object and checking for the existence of an entry for that transaction.  The value of the entry would be the thread in which the tx was requesting a lock (or blocked while requesting a lock).  At that point multiple threads could execute operations on the same transaction interface, but blocking in any thread would block all threads for that transaction.  Requests by multiple threads for the same lock would need to be coalesced within the queue, but all blocked threads would need to be notified.
 
-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 8:57 PM
To: JDBM Developer listserv
Subject: [Jdbm-developer] re[2]: DefaultTransactionManager - draft of prototype.
 

Bryan-

 

Just had a Homer Simpson 'dooh' realization on the way home.  The Queue.lock() method doesn't need to know anything about the current transaction - if lock() blocks, then there is an implicit 1:1 relationship between the current thread and the transaction.  If lock() doesn't block, then the transaction itself is responsible for freeing it's own locks.  In neither scenario is having the transaction object itself necessary.  That means that asserting the current transaction is sufficient to guarantee proper operation, even with suspending and resuming a transaction.

 

We do still need to be able to obtain the transaction object from thread local storage for other purposes though (interaction with the version manager, for example), so my suggestions still stand.

 

Anyway - I thought I'd better write this now so you don't think I'm a total idiot when you get my first email :-)

 

- K

 

 

Bryan-

 

I've done a cursory glance through this code (this will be a heck of a lot easier when we have svn access!)...

 

The only thing that stands out that I feel needs comments is the currentThread variable...  I think that you want this to be threadLocalTx.

 

So, the call to getCurrentThread and setCurrentThread will actually morph into getCurrentTx and setCurrentTx, etc..., as in:

 

 

       synchronized public static Tx getCurrentTx() {

           return (Tx) threadLocalTx.get();
        }

 

       synchronized public static void setCurrentTx(Tx contextTx) {
            if (threadLocalTx.get() != null) {
                throw new IllegalStateException("Tx already assigned for this thread");
            }
            threadLocalTx.set(contextTx);
        }

       /**
         * Throw exception if the specified lock context is not bound to the current thread.

        */
        synchronized public static void assertCurrentTx() {
            if (threadLocalLockContext.get() != this) {
                throw new IllegalStateException("Tx context not bound to this thread");
            }
        }

 

 

I didn't see an implementation for the Queue class itself, but I suspect that the Queue.lock() method will wind up accepting a lock context object as a parameter.  In jdbm, this lock context will be the transaction object returned by getCurrentTx().

 

Or am I maybe missing something important about how the Queue class operates?  It seems to me that the items on the queue must somehow be associated with the transaction that holds the lock (or is waiting for the lock)...

 

- K

 

 

  

 
>All,

Here is some code based on our discussions that attempts to integrate
the 2PL support with a transaction factory and support the binding of
threads to transactions.  Please take a look.  I have made some notes
where the code is incomplete, requires features not available, etc.

I am not sure where this is going right now.  I could see how this
could be re-factored into an extensible mechanism for creating
transactions and making use of the 2PL facilities, but I am not sure
that this much of the control structure belongs in a generic purpose
2PL locking package rather than in some jdbm specific transaction
management classes.

-bryan

package org.CognitiveWeb.concurrent.locking;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
* A factory for transaction objects supporting assignment of threads to
* transactions. A thread may assign a transaction to itself iff the
transaction
* is not currently bound to a thread. If a lock request would result in a
* deadlock, then a {@link DeadlockException} is thrown. If a lock request
* blocks, then a transaction will remain bound to that thread until the
lock
* request is granted, a timeout occurs, or the transaction is aborted. When
a
* thread is running, it may release the bound transaction. A transaction
that
* is not associated with any thread is not running. If other transactions
are
* waiting on a transaction that is not running, then those transactions
will
* block until the transaction is rebound to another thread and it releases
its
* locks. When a transaction completes (either aborts or commits), all locks
* associated with that transaction are released.
*
* @author <a href="mailto:thompsonbry@users.sourceforge.net">Bryan">Bryan">href="mailto:thompsonbry@users.sourceforge.net">Bryan
Thompson</a>
* @version $Id: DefaultTransactionManager.java,v 1.1 2006/03/29 14:41:46
thompsonbry Exp $
*/

public class DefaultTransactionManager
{
    
    /**
     * The maximum multi-programming level.
     */
    private final int capacity;
    
    /**
     * The directed graph of the WAITS_FOR relation which is used to
detect
     * deadlocks.
     */
    protected final TxDag waitsFor;

    /**
     * The active transaction objects.
     */
    private final Set transactions;

    /**
     * The queue for each in-use resource.
     *
     * FIXME This must be a weak value hash map so that queues may be
garbage
     * collected once they are no longer in use.
     */
    private final Map queues = new HashMap();
    
    /**
     * The maximum multi-programming level (from the constructor).
     */
    public int capacity() {
        return capacity;
    }

    /**
     * The current multi-programming level.
     */
    public int size() {
        return transactions.size();
    }
    
    /**
     * Create a transaction manager.
     *
     * @param capacity
     *            The maximum multiprogramming level (aka the maximum
#of
     *            concurrent transactions).
     */
    
    public DefaultTransactionManager( int capacity )
    {
        
        this.capacity = capacity;
        
        waitsFor = new TxDag( capacity );

        transactions = new HashSet( capacity );
        
    }

    /**
     * Create a new transaction. By default the transaction will be
bound to the
     * thread in which this request was made. If the maximum
multi-programming
     * level would be exceeded, then this request will block until the
     * concurrency level has decreased.
     *
     * @exception IllegalStateException
     *                If the thread is already bound to another
transaction.
     *                
     * @return The transaction.
     */
    
    public Tx createTx()
    {
        
        return createTx( 0L, 0 );

    }
    
    /**
     * Create a new transaction. By default the transaction will be
bound to the
     * thread in which this request was made. If the maximum
multi-programming
     * level would be exceeded, then this request will block until the
     * concurrency level has decreased.
     *
     * @param millis
     *
     * @param nanos
     *
     * @exception IllegalStateException
     *                If the thread is already bound to another
transaction.
     * @exception TimeoutException
     *                If the transaction could not be created in the
specified
     *                time.
     *                
     * @return The transaction.
     */
    
    synchronized public Tx createTx( long millis, int nanos )
    {
        
        // @todo enforce multi-programming limit.  e.g., using
java.util.concurrent.Queue.
        
        Tx tx = new Tx( this );
        
        transactions.add( tx );
        
        return tx;
        
    }

    /**
     * Return the {@link Queue} for the identified resource.
     * <p>
     * Note: The {@link Queue}s are maintained in a weak value hash map
whose
     * keys are the resource identified. Each transaction must hold a
hard
     * reference to each queue for which it requests a lock and must
clear that
     * hard reference once it releases its lock. Once there are no more
     * references to a given {@link Queue}, the garbage collector will
reclaim
     * the queue. This is important since the number of queue objects is
bounded
     * by the number of distinct resources in the database and could
otherwise
     * easily exceed the available memory.
     *
     * @param resource
     *            The resource identified.
     *
     * @param insert
     *            When true a new {@link Queue} will be created iff none
exists
     *            for that resource.
     *
     * @return The queue for that resource or <code>null</code> iff
     *         <code> insert == false </code> and there is no queue for
that
     *         resource.
     */
    
    synchronized protected Queue getQueue( Object resource, boolean
insert )
    {
        
        if( resource == null ) {
            throw new IllegalArgumentException();
        }
        
        Queue queue = (Queue) queues.get(resource);
        
        if( queue == null && insert ) {
            
            queue = new Queue(waitsFor,resource);
            
            queues.put( resource, queue );
            
        }
        
        return queue;
        
    }
    
    /**
     * A transaction object. A transaction object may only be used by
the thread
     * to which it is currently bound. If the transaction is not bound
to any
     * thread, then it must be bound to a thread before any other
operations may
     * be taken. A transaction which is not bound to a thread is not
running and
     * any transactions waiting on that transaction can not run the
transaction
     * has been bound to a thread and its locks have been released.
     *
     * @author <a href="mailto:thompsonbry@users.sourceforge.net">Bryan">Bryan">href="mailto:thompsonbry@users.sourceforge.net">Bryan
Thompson</a>
     * @version $Id: DefaultTransactionManager.java,v 1.1 2006/03/29
14:41:46 thompsonbry Exp $
     *
     * @todo Define a transaction identifier, expose it, and use it as
the key
     *       in {@link DefaultTransactionManager#transactions}?
     */

    public static class Tx {

        /**
         * The transaction manager.
         */
        private final DefaultTransactionManager txMgr;

        /**
         * The {@link Queue} for each lock requested by this
transaction. The
         * queue is added to this collection before the lock request
is made and
         * is cleared from the collection once the lock has either
been released
         * or when a deadlock or timeout exception was thrown at the
time that
         * the lock was requested.
         */
        private final Set locks = new HashSet();
        
        /**
         * The transaction manager.
         */

        public DefaultTransactionManager getTranasctionManager() {
            return txMgr;
        }

        /**
         * Create a new transaction object.
         */
        protected Tx( DefaultTransactionManager txMgr ) {
            if( txMgr == null ) {
                throw new IllegalArgumentException();
            }
            this.txMgr = txMgr;
            setCurrentThread();
        }
        
        /**
         * A thread local variable whose value is either the thread
to which the
         * transaction is currently bound or <code>null</code> iff
the
         * transaction is not currently bound to any thread.
         *
         * @todo Review synchronization requirements for methods
that access and
         *       set this thread local variable.
         */
        private static ThreadLocal currentThread = new ThreadLocal()
{
            protected synchronized Object initialValue() {
                return null;
            }
        };

        /**
         * Return the thread to which this transaction is currently
bound or
         * <code>null</code> iff the transaction is not bound to any
         * thread.
         */
        synchronized public static Thread getCurrentThread() {
            return (Thread) currentThread.get();
        }

        /**
         * Release the transaction from the thread of the current
context.
         *
         * @exception IllegalStateException
         *                if the transaction is not bound to the
thread of the
         *                current context.
         */
        synchronized public static void releaseCurrentThread() {
            assertCurrentThread();
            currentThread.set(null);
        }

        /**
         * Bind the transaction to the thread of the current
context.
         *
         * @exception IllegalStateException
         *                if the transaction is already bound to a
thread.
         */
        synchronized public static void setCurrentThread() {
            if (currentThread.get() != null) {
                throw new IllegalStateException("thread
already assigned");
            }
            currentThread.set(Thread.currentThread());
        }

        /**
         * Throw exception if the {@link Tx} is not bound to the
thread of
         * the current context.
         */
        synchronized public static void assertCurrentThread() {
            if (currentThread.get() != Thread.currentThread()) {
                throw new IllegalStateException(
                        "transaction not bound to
this thread");
            }
        }

        /**
         * Request a lock on the identified resource in the
specified mode. This
         * method will block until the lock can be granted.
         *
         * @param resource
         *            The resource identifier.
         *
         * @param mode
         *            The mode - see {@link LockMode).
         *
         * @exception DeadlockException
         *                if the lock request would cause a
deadlock.
         *                
         * @todo add timeout variant of this method.
         * @todo add non-blocking variant of this method.
         */
        
        public void lock( final Object resource, final short mode )
        {
            
            if( resource == null ) {
                throw new IllegalArgumentException();
            }

            assertCurrentThread();

            final Queue queue = txMgr.getQueue( resource, true
);
            
            /*
             * Note: If locks are reentrant, then we need to be
careful to only
             * clear the Queue reference from [locks] once the
transaction has
             * reduced the lock counter to zero for that queue.
             */
            final boolean exists = locks.add( queue );
            
            try {
                queue.lock( mode ); // @todo lock( this,
mode );
            }
            catch( DeadlockException t ) {
                if( ! exists ) locks.remove( queue );
                throw t;
            }
            catch( TimeoutException t ) {
                if( ! exists ) locks.remove( queue );
                throw t;
            }
            catch( Throwable t ) {
                if( ! exists ) locks.remove( queue );
                throw new RuntimeException( t );
            }
            
        }

        /**
         * Release the lock on the identified resource.
         *
         * @param resource
         *
         * @exception IllegalStateException
         *                if the transaction does not have a lock on
that
         *                resource.
         */
        
        public void unlock( Object resource )
        {
            
            if( resource == null ) {
                throw new IllegalArgumentException();
            }
            
            assertCurrentThread();
            
            Queue queue = txMgr.getQueue( resource, true );
            
            if( queue == null ) {
                
                throw new IllegalStateException(
                        "no queue for resource:
resource=" + resource);
                
            }

            queue.unlock(); // @todo unlock( this );


            if( ! locks.remove( queue ) ) {
                
                throw new AssertionError();
                
            }
            
        }
        
        /**
         * This method MUST be invoked to signal that the
transaction has
         * completed its processing and is responsible for releasing
all locks
         * and other resources associated with the transaction. This
method MUST
         * be used whether the transaction was successful or
aborted.  This method
         * also releases the bond between the transaction and the
thread which is
         * executing that transaction.
         */
        
        public void complete()
        {

            /*
             * @todo Is it always possible to call this method,
e.g., on a tx
             * abort, from the thread associated with the tx?
Perhaps we need to
             * allow this method to be called by any thread and
always have it
             * release the tx - thread bond.
             */
            assertCurrentThread();
            
            /*
             * @todo In order to optimize lock release behavior
both this method
             * and Queue should probably synchronize on
waitsFor. This would
             * allow us to use a unlock() variant that did not
update the
             * waitsFor graph to release each of the locks and
then use the
             * optimized methods to clear the row and column for
this
             * transaction from the waitsFor graph.
             *
             * The code below just steps through all of the
locks that are still
             * held by this transaction releasing them one at a
time and
             * updating the waitsFor graph each time a lock is
released.
             *
             * @todo If we have re-entrant locks then this code
will not work
             * since the application will have to release the
locks the right
             * #of times. I really do not see the point of
re-entrant locks,
             * certainly not if they are associated with a lock
count as opposed
             * to simply returning immedately if the lock is
already held by the
             * transaction.
             */
            
            Iterator itr = locks.iterator();
            
            while( itr.hasNext() ) {
                
                Queue queue = (Queue) itr.next();
                
                queue.unlock(); // @todo unlock( this );


                itr.remove();
                
            }

            releaseCurrentThread();
            
        }
        
    } // class Tx.
    
}

<
<
<
<
<

 

------------------------------------------------------- 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