A new locking startegy was proposed by
DanielMcAllansmith to allow non-conflicting transactions to execute in parallel.
The whole motivation for the lock idea is that the precondition checking within Transaction.executeOn() violates
InstantaneousTransactions. --
KlausWuestefeld
Well, not really precondition checking... querying state is the thing which
can take time. Presumably precondition checking will usually query state.
Even without precondition checks I think it would be hard work to ensure all
transactions were 'instantaneous', some querying is going to occur while
queueing up the transaction for deferred computation. --
DanielMcAllansmith
I believe that, using lazy evaluation, though, we can write a system with very complex transaction pre- conditions and still have instantaneous transactions. I shall elaborate in a future post. As I said before, the trick is the Transaction.executeOn() never returning a result or throwing an exception (throwing an exception is just a special way of returning a result). --
KlausWuestefeld
I'm eager to see how it could be acheived, and how difficult it would be to write the Transactions. Personally I'm usually willing to sacrafice a little speed for clarity. --
DanielMcAllansmith
I'm unconvinced that
Prevayler support for this is necessary. The premise is that Instantaneous Transactions aren't effective if you have some long-running Transaction.
For this situation I recommend creating a small Instantaneous Transaction that just forks a thread to do the real work.
My opinion is that in most applications, long-running Transactions are in the minority and I don't want to see
Prevayler add complexity to support a minority case that can be easily handled by just having the Transactions themselves fork new threads.
--Dave Orme
I second
DaveOrme's concerns, but wouldn't a Thread-spawning Transaction be undeterministic on some conditions, like the ones that suggest using them in the first place? --
CarlosVillela
I'm confused about a couple of things here: How does this give up the lock that happens when adding a Transaction to the queue? It seems that you're going to have to synchronize that no matter what. Or am I missing something else here? --
DaveOrme
Well, there is no actual queue. The transactions 'queue up' waiting to aquire locks. I have been known to be wrong before, but I think you can get away with much less synchronisation than occurs now. Though that's not to say that the current way is inherently more expensive... maybe it just hasn't experienced enough iterations. --
DanielMcAllansmith
Perhaps an outline of the current algorithm then the algorithm as you envision it would be helpful. --
DaveOrme
Righto. This is based off of my reading of the 1.x code, hopefully Klaus will point out any errors I make or differences in teh 2.0 code. I have left out actual logging of transations and transaction counting for purposes of snapshotting as that will probably be equivalent.
Current algorithm:
#log transaction asynchronously
#synch on transaction queue
#add transaction token to queue
#get logical transaction time
#synch on transaction token
#synch on transaction queue //thread sleeps until the transaction token is at the head of the queue. //indicating that it is time for this transaction to be executed.
#execute transaction //not in a synch block but the transaction queue is effectively locked, so no concurrent execution
#synch on transaction queue
#remove transaction token from head of queue
#get next token on transaction queue
#synch on next token
#notify token that its transaction can proceed
Proposed algorithm: //the only locks held during this method are those in aquire so transactions operating over disjoint subsets of state may proceed concurrently
#transaction aquires locks //could be no locks, global write (like now) or more. This prevents other transactions that operate on the same subset of state proceeding until release locks is called.
#check that transaction preconditions hold //bail out if they don't hold
#log the transaction asynchronously
#get logical transaction time
#commit the effects of the transaction
#transaction releases locks //transactions that operated over the same subset may proceed through the lock aquisition
As things stand, the implementation of the current algorithm synchs five times, and probably would make more method calls. If you're sure your transactions won't stomp each other you can do no locking in the proposed algorithm. If you want a global write lock you'd probably be looking at a couple of synch blocks, one for aquire and one for release of a lock object. If you want you can get more specific with your locking which basically gives you the ability to trade off between the cost of acheiving locks and the amount of concurrency possible.
It would require changes to the core and the Transaction interface, but I think the changes simplify things, are more expressive, are more conceptually accurate, and quite possibly more efficient even for the 'simple' case. But maybe I'm biased... @:) --
DanielMcAllansmith
The proposed algorithm is simply defined in a more abstract level than the current one. Please describe the "transaction acquires locks" step. Please describe the recovery phase too (how will it know which transactions can run concurrently and in which order).
I like the idea. I want to explore it more. --
KlausWuestefeld
To avoid deadlocks and allow locking to take place in parallel, we would also have to:
-Sequence transactions BEFORE they aquire their locks.
-Allow older transactions to "break" locks by newer ones. The newer ones would simpy have to try again later (or throw an UnableToAquireLockException to their callers, which is VERY BAD and doesn't occur today). --
KlausWuestefeld
No. No. There would be no problem with locking as long as use a sensible method of ordering lock aquisitions. It is (or at least should be!) standard practice to aquire locks in a well defined sequence to minimise the possiblity of deadlock. And given that locks are aquired in only one place ordered lock aquisition should totally prevent deadlock. --
DanielMcAllansmith
OK. So we would have to:
#Determine all locks a given transaction needs. Who will do that? Will the business have to signal that? Will the transaction break encapsulation and "just know"? Would we "analyse" the code via AOP and generate the locks? How?
#Acquire them in ascending order. All locks would have to be comparable! Each lock acquisition will require a synchronized block.
--
KlausWuestefeld
'describe the "transaction acquires locks" step' - The method of aquiring locks is not mandated. The prevayler simply makes a call to Transaction.aquireLocks, which could do anything from a 'no-op' right up to obtaining read/write locks on individual fields of multiple business objects.
'describe the recovery phase too (how will it know which transactions can run concurrently and in which order)' - Transactions are partially-ordered. The partial-ordering is determined by the locks which they require. The simplest thing to do is log the Transactions in a full-order that is consistent with their partial-ordering. The simplest form or recovery would be to replay the Transactions in the full-ordering.
If replaying the Transactions sequentially (ie on a single thread) you could disable the lock aquisition/release phases. Or you could replay Transactions concurrently (lock aquisition/release will allow concurrency consistent with the Transactions partial-order).
'Who will determine locks a transaction needs?' - The transaction writer, the prevayler simply provides the hook for the transaction to aquire and release the necessary locks.
In general the answer to the points below is 'Do it however you like, it's not mandated.', but I'll add my opinions.
'Will the transaction break encapsulation and "just know"?' - Personally I think the Transaction is a more correct place for lock objects than within the business objects. Business objects have no business with lock objects.
'Would we generate locks? How?' - That's one way to do it. With strict OO you could provide access to a canonicalized pool of lock objects, which are created on demand, to all transactions.
I'd be more inclined to see transactions as an Aspect of Business Object behaviour and define Transactions using aspects (ala
AspectJ). With this approach it seems feasible to have no mention of Transactions or
Prevayler in your (java) code. Also (hopefully) you could move to a different persistence mechanism by simply changing some abstract aspects.
'Acquire locks in ascending order. All locks would have to be comparable! Each lock acquisition will require a synchronized block.' - That would be my advice. I get scared when there are more than a handful of locks being aquired in random order at random points. It is so much easier to reason about when they are aquired in a defined order, and it will usually prevent deadlock.
In actuality each lock will most likely cost you two synchs, one to aquire and one to release. But transaction writers are free to use as few or many locks as they like.
If you wrote an application with very fine-grained transactions with the current system you incur 5 synchs to get a global lock. If your transactions all consist of setting a single field (excluding doubles and longs) they are already atomic and there is no need for any locking at all.
A similar problem exists if you write a single-threaded application, you pay for synchs you don't need.
--
DanielMcAllansmith