[infinispan-dev] conflicts resolution in DeltaAware

[Emmanuel Bernard]

On 8 avr. 2011, at 19:47, Sanne Grinovero wrote:

> 2011/4/8 Emmanuel Bernard <emmanuel at hibernate.org>:
>> Yes I think that would fit the bill. Let me give some more background
>> Background
>> In Hibernate OGM, we store collections in a single key essentially as a
>> Set<Map<String,Object>> ie as a set of tuples, esch tuple representing the
>> equivalent of one row of an association table in a relational database. The
>> reason for that is to be able to get the collection state by doing key
>> lookups. If we were to store each tuple of the collection in a separate key,
>> we would have no way to get the list of matching keys for a given collection
>> (unless you get a key with the list of keys for a collection but then you
>> are just moving the problem instead of fixing it.
>> 
>> Today, we reach scalability problems very quickly as we end up touching the
>> collection key every time one entity is added or removed from it. In a
>> relational database, this operation scale quite well as locks are acquired
>> on each tuple and not on the whole tupes for a given collection.
>> 
>> What we could do is:
>>  - use AtomicMap<UUID,Map<String,Object>> instead of Set<Map<String,Object>>
>>  - trick infinispan so that it believes that the atomic lock is held at the
>> atomic map key level rather than the atomic map as a whole.
>> 
>> Many operations could be done consecutively:
>>  - update k1 in T1 and k2 in T2 in concurrently
>>  - add k1 in T1 and remove k2 in T2 concurrently
>> etc
>> what would still fail is:
>>  - modify k1 in T1 and k1 in T2 concurrently
>> 
>> Solution
>> The approach Sanne proposes would solve our use case.
>> To refine a bit the API:
>>  - to avoid the exception, you could return a boolean for success or failure
>>  - you could have DeltaAware merge(DeltaAware... deltaAwareOps)
>>  - I am not entirely sure you need the old value in our use case but that
>> seems like a good idea generally speaking even if that makes the algorithm
>> more complex I suspect as ISPN needs to find the common ancestor
> 
> Emmanuel,
> about the API, a boolean won't work:
> Infinispan is going to need the final value as this interface is in
> charge of defining the resolved map. Also on each DeltaWare you're
> only getting the operations which where applied to the map, so you
> need the original value as well to be able to replay them all on it.
> A
> "deltaAwareOp" has a similar role as a "List<LuceneWork>", for example
> {[delete doc 1], [delete doc 7], [write doc:fields]}; in case of the
> AtomicMap it's an ordered list of operations such as "add this",
> "remove that"; so you always need the original map to be able to
> figure out the output.

Not in the case of a map as it's key based and is not "ordered". But for a generic structure (say a List), you are correct.

> So we have to return a new DeltaWare object, and it's also likely
> needed to be able to tell which of the input DeltaAwareOps failed.
> 
> It just occurred me that for some kinds of isolations you might need
> to track read operations as well, to make sure the proposed writes are
> not the output result of an invalid read. I'm no expert on these
> matters, I hope we can ignore this for now.

Yes there is some hidden complexity here. 
In truth, what I really want is the keys of the AtomicMap to be treated as Cache keys (lock and isolation wise). I don't need the generic delta merge resolution solution.