Software Transactional Memory relies on optimistic locking to avoid deadlock, but as a result suffers at least one serious problem.
An optimistic update transaction will succeed when the data being updated remains stable for the period of the transaction.
If n threads are trying to update a shared variable at m Hz, on average there will be an attempt to change the variables value about every (n m)-1 secs.
As that interval falls towards the average time it takes to perform an update transaction, the success rate for transactions will fall precipitously to almost zero, and the system will grind to a starved halted state that’s as bad as deadlock.
We must make some progress even under heavy contention
Pessimistic locking is one approach, but it suffers from deadlock problems.
The software equivalent of “Changeset Merging” is another.
In a version controlled system, we do not Revert Changes any time someone else has edited the same file. That seems wasteful, but that’s essentially what basic STM does. Rather, someone or something examines the two conflicting changesets, and merges them together. This might involve discarding part or all of one change, or some blend.
Changeset merges in STM
A transaction could declare a merge routine to be run after a conflict. It is given the current system state, and the transaction that lost out on the update race, and can either transform them into one merged state that is saved, or fallback to the default retry if it cannot do so.
Of course, it’s likely there are other (3rd, 4th ..etc) transactions in progress while that merge is taking place. But this can simply be resolved by the running the merge routine again, which now blends the previous merge with the next incoming transaction, as the new system state.
I must credit [http://lists.basho.com/pipermail/riak-users_lists.basho.com/2009-September/000029.html] and [http://debasishg.blogspot.com/] for leading me to this idea.
RSS Feed 
