Version 6

    Optimistic Node Locking (version 1)

    by Manik Surtani (manik AT jboss DOT org) and Steve Woodcock (stevew AT jofti DOT com)



    The optimistic solution is almost entirely written as interceptors, most of which have counterparts in the pessimistic chain.  Transaction management from the other interceptors has been removed and put into an interceptor of its own.


    The general concept is that each transaction has its own workspace - all changes take place within this workspace.  All txs use 2 phase commits even if they are local and all methods have to be called inside a transaction.


    If you call a method without creating a transaction a temporary one is created and the method executes within this context.


    When a commit is issued, a prepare phase is entered which locks all the nodes in the workspace and validates that all changes can be applied to the cache itself. If it validates then a commit is invoked - this applies the changes and unlocks all the locks acquired in the prepare. If the prepare fails then a rollback is invoked.


    When a tree is distributed the order of calls is that the local prepare is run first - then if that works a remote prepare is isssued (there is no point doing this remotely if the local can't work). If this works then a commit starts - which commits the remote txs first then the local tx.


    The locks for the commit are acquired in the prepare phase so that prepares/validates run in two trees for the same nodes cannot both succeed as the locking will prevent this.


    Operations that appear to take place outside a tx are actually individually wrapped in a temporary transaction that commits at then end of the method call.





    • CallInterceptor

    Invokes calls on the underlying cache.


    • OptimisticNodeInterceptor

    Deals with all the put/get method interception for values and children - manges the addition of new

    nodes into the workspace/changes in the nodes in the workspace and wrapping of returned values. All put and get methods are intercepted and are not passed down to the next interceptor.


    • OptimisticCreateIfNotExistsInterceptor

    Creates a new node in the workspace only if it doesn't exist on put() methods.


    • OptimisticValidatorInterceptor

    On a prepare the validator chacks that all the nodes in the workspace are able to be committed against (currently only simple version number) - the intention is to replace this with slightly more comples validation - this should be a configurable parameter for the user as there will be a speed/complexity tradeoff. On the commit it applies the changes to the real nodes it has in the workspace to the cache. 

    On rollback clears the nodes in the workspace.  Does not pass prepare/commit/rollback methods to the next interceptor.


    • OptimisticLockingInterceptor

    On a prepare attempts to acquire write locks on all nodes in the workspace. On a commit or rollback releases all acquired locks.


    • OptimisticReplicationInterceptor:

    Uses 2PC to replicate workspace. Replicates synchronously on a local prepare all methods applied on the local store as a remote prepare. (if there is another tree in the view).  Replicates synchronously on commit and rollback to other tree on applying these methods locally.  Handles applying of all remote methods received prepare/commit/rollback.


    • OptimisticTxInterceptor:

    Handles all the transaction wrapping/suspending/creating for both local and remote methods. Uses 2 types of synchronisation handler to deal with commits and rollbacks for the transaction to differentiate whether local/remote. No other interceptor should deal with any of the transaction management.  This is the only interceptor to register a handler (local or remote)- as this is a substitute for correct XA tx handling and so it would be better to move this when refactored accordingly. It also allows just this handler to control the whole tx sequence without anyone else calling a commit or rollback.  All other interceptors just rely on method calls passed up the stack.


           JBossCache (A)                                   JBossCache (B)
    CallInterceptor                                CallInterceptor
    OptimisticNodeInterceptor                      OptimisticNodeInterceptor
    OptimisticCreateIfNotExistsInterceptor         OptimisticCreateIfNotExistsInterceptor
    OptimisticValidatorInterceptor                 OptimisticValidatorInterceptor
    OptimisticLockingInterceptor                   OptimisticLockingInterceptor
    OptimisticReplicationInterceptor  ------    ---OptimisticReplicationInterceptor 
                                            |   |                  
    OptimisticTxInterceptor                 |   |  OptimisticTxInterceptor
                      ^                     |   |            ^    ^
                |     |---------------------|---|            |    |
                |         remote call(B)    |----------------|    |
                |                               remote call(A)    |
                |local method call)                               | (local method call)


    New Classes (that are not interceptors):






    Used in the workspace node tree to provide a sorted order for all fqns - even if they do not implement Comparable. This is needed because the iterator for the locking always has to acquire the locks in a tree in the same order for a particular JVM in order to prevent deadlock clashes.


    The comparator walks through the fqn object list and compares each similar depth object by it's String value - even if the Object does not override toString - this allows us to ensure that for the life of say object java.lang.Object@23456 - this will remain as its fqn value and we can safely assume its order. Note the same Fqn does not have to be ordered on two JVMs in the same order - only matters that within the JVM the lock acquisition (which is local is the same).  The alternative is to make all Fqn objects implement Comparable.




    A sub interface of Node, with specific methods to access the actual DataNode represented by this WorkspaceNode.  This interface acts as a buffer to the real DataNode in the workspace, and all operations in the workspace are performed on this.  None of the operations are delegated to the underlying DataNode until commit time.



    Implementation of the above.



    Keeps track of additions and removals without changing the underlying real map - used as a substiute for

    the data and children map in the WorkspaceNode - so change are isolated from the real node maps until commit time.  Removals are only recorded if they were in the original map when the wrapper was created around the real node. Essentailly acts as snapshot for the maps in the real node.  The puts/removes are synchronized on the same object as there are really two data structures in each method - this is not a big bottle neck as each instance is local to a particular transaction.



    Te interface for the workspace for each transaction



    Implementation of the above.  Handles the node addition/retrieval of nodes and allows subtrees of nodes to be obtained from the local node Map.





    Local call:
    cache.put("/one/two","1", new Pojo());
    ->Invokes interceptor chain
    OptimisitcTxInterceptor: does tx creation, creates a workspace if needed and synchronisation handler registration
    OptimisticReplicationInterceptor: passes up 
    OptimisticLockingInterceptor: passes up
    OptimisticValidationInterceptor: passes up
    OptimisticNodeCreationInterceptor: creates nodes in workspace if not exists
    OptimisitcNodeInterceptor: adds the value under the key to nodewrapper -> returns
    Commit called on tx or transactionManager
    Prepare Phase
    -> SynchronisationHandler called: creates a prepare and passes to OptimisitcTxInterceptor
    OptimisitcTxInterceptor : checks tx and passes up
    OptimisticReplicationInterceptor: passes up 
    OptimisticLockingInterceptor: locks all nodes in workspace - if exception unlock - otherwise pass up
    OptimisticValidationInterceptor: validates nodewrappers against nodes - return or throw exception
    OptimisticLockingInterceptor:  pass back
    OptimisticReplicationInterceptor: if no exception - broadcast prepare if other trees in view - pass back or exception
    OptimisitcTxInterceptor: pass back
    SynchronisationHandler: if exception call rollback else commit
    Commit phase
    SynchronisationHandler: create commit pass up
    OptimisitcTxInterceptor: checks tx and passes up
    OptimisticReplicationInterceptor: call remote commit - if exception - pass up then return exception
    OptimisticLockingInterceptor: pass up
    OptimisticValidationInterceptor: apply changes return
    OptimisticLockingInterceptor: unlock
    OptimisticReplicationInterceptor: pass back
    OptimisitcTxInterceptor: pass back
    SynchronisationHandler: destroy entries in txtable
    Rollback phase
    SynchronisationHandler: create rollback pass up
    OptimisitcTxInterceptor: checks tx and passes up
    OptimisticReplicationInterceptor: call remote rollback - if exception - pass up then return exception
    OptimisticLockingInterceptor: pass up
    OptimisticValidationInterceptor: abandon workspace
    OptimisticLockingInterceptor: unlock
    OptimisticReplicationInterceptor: pass back
    OptimisitcTxInterceptor: pass back
    SynchronisationHandler: destroy entries in txtable




    By default optimistically locked nodes use an internal implementation of the org.jboss.cache.optimistic.DataVersion class.  Versioning may be explicit by passing in the version for each CRUD operation (using the Options API - see JBCACHE-106 and JBossCacheOptionsAPI).


    Stuff left to do

    1. Implement different validation strategies to make this more fine grained

    (e.g. backward/forward validation, partial non-conflicting merges, dependency merges, etc.)

    1. Write full threaded correctness tests to ensure locking behaves correctly.

    2. Integrate with the AOP stuff (Are any additional changes necessary?  Testing required)

    3. The XA interfaces should be properly implemented so the logic can be moved out of the synchronisation handlers (which are really for callback notifications - not for running the whole tx completion phase - indeed currently the after complete is used to run the complete - which is not its intended use.