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.
Interceptors
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):
org.jboss.cache.optimistic:
Comparator
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.
WorkspaceNode
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.
WorkspaceNodeImpl
Implementation of the above.
OptimisticMap
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.
TransactionWorkspace
Te interface for the workspace for each transaction
TransactionWorkspaceImpl
Implementation of the above. Handles the node addition/retrieval of nodes and allows subtrees of nodes to be obtained from the local node Map.
Behaviour
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
Versioning
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
Implement different validation strategies to make this more fine grained
(e.g. backward/forward validation, partial non-conflicting merges, dependency merges, etc.)
Write full threaded correctness tests to ensure locking behaves correctly.
Integrate with the AOP stuff (Are any additional changes necessary? Testing required)
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.
Comments