Hello, I'm working on new implementation for optimistic/serializable transaction mode (current implementation is inefficient and have bugs). This mode is supposed to be used when concurrent transactions do not update the same keys, in this case transactions can be executed more efficiently, but if concurrent transactions have read of write conflicts then TransactionOptimisticException can be thrown and transaction should be retried. Also with current transactions implementation user should order updated keys, otherwise deadlock is possible, we want to remove this requirement for optimistic/serializable mode.
Issue with read/write conflicts can be detected if when read is performed entry version is stored and then compared with current version when transaction lock is acquired. Another issue is avoid deadlocks when transactions acquire keys in different order. I created one possible solution using 'try-lock' approach: for each cache entry we already have queue with current lock owner and transactions trying to acquire entry lock. When optimistic/serializable transaction tries to acquire entry lock it checks that entry is not locked and there are no others transactions waiting for lock entry, otherwise transaction fails with TransactionOptimisticException. But this approach does not work well when two transaction have lot of intersecting keys: it is possible that these transaction will constantly conflict and will both constantly fail with TransactionOptimisticException. It seems there is better approach to resolve these conflicts to do not fail all conflicting transactions: - we should order all transactions by some attribute (e.g. all transactions already have unique version) - transaction with greater order should always 'win' transaction with lower order - per-entry queue with waiting transactions should be sorted by this order - when transaction tries to acquire entry lock it is added in waiting queue if queue is empty or last waiting transaction have lower order, otherwise transaction fails With this approach transaction lock assignment is ordered and transactions with lower order never wait for transactions with greater order, so this algorithm should not cause deadlocks. I also created unit test simulating this algorithm and it did not reveal any issues. Also in this unit tests I measured percent of rollbacks when concurrent updates have lots of conflicts: with 'try-lock' approach percent of rollbacks is ~80%, with new algorithm is ~1% (but of course with real-life test results can be different). Does anyone see problems with this locking approach?
