[infinispan-dev] DLD continued/optimizing modifications within a tx

[Mircea Markus]

Hi,

Right now we support DLD in the following scenarios: local caches, 
symmetric tx that create deadlocks over two replicated caches (symmetric 
in the sense that  A replicates to B and B replicates to A at the same 
time).
In the case of distribution (replication as well, especially async one) 
there might still be a deadlock if both A and B replicate to C, but they 
replicate transactions that would result in deadlocks, so deadlock would 
result in C.
Let's take an example, A wants to replicate Tx1 that affects (key1, 
key2) in this sequence. B wants to replicate Tx2 that affects (key2, 
key1) in this sequence. While replicating on C, Tx1 and Tx2 would result 
in a deadlock (classic scenario).
Now a simple way of solving this (if I'm not missing something!!) is to 
order the keys in the replicated transaction based on some criterion 
(e.g. lexicographic) and apply them in the same sequence: Tx1(key1,key2) 
and Tx2(key1, key2). This will avoid deadlocks -> increase throughput.
    Now, at the core of this approach is the fact that the order of 
operations in the transaction is not relevant - which does not stand in 
current implementation. E.g. let's say we have a tx that does 
(remove(key), put(key, 'otherVal')). If we change the order  result is 
totally different - not good! A way to avoid this (and to also reduce 
the amount of replication, by compacting changes by key) is to keep the 
modifications in a Map<key,Modification>. For each key we keep only the 
last value set within it, so if we modify the same key 1000 times within 
a tx we only replicate last modification vs current approach where 1000 
operations are replicated. If a key is deleted, we still keep it in the 
map, with a marker for deletion. This way we only replicate the delta of 
modifications, and the order of operations is no longer relevant, so 
that we can leverage previously described deadlock detection.

The advantages of this would be higher throughput by reducing the chance 
of 'asymmetric' deadlocks (A,B encounter a deadlock while replicating on 
C) and possible reduction in the size of the transaction (if it has 
multiple operations on the same key). The drawback is mainly the fact 
that some additional computation needs to be made to manage the map 
content (not a lot I reckon, instead of a List.add we'll do an map.get() 
+  map.put(), for each modification within the transaction).

Wdyt?

Cheers,
Mircea