[infinispan-dev] conflicts resolution in DeltaAware

[Sanne Grinovero]

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.
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.

Cheers,
Sanne


>
> On 8 avr. 2011, at 19:07, Sanne Grinovero wrote:
>
> Hi Mircea,
> I remember you recently mentioned that you have been looking into ways
> to give the ability to the application to resolve updating conflicts.
> I don't think you where referring to AtomicMap or any other DeltaAware
> specifically, but it seems now that we urgently need something like
> this in OGM.
>
> I'm looking into the Delta interface, which defines this single method:
>
> DeltaAware merge(DeltaAware d);
>
> This looks great to merge an update onto an existing value; But of
> course the world is made of parallel executing updates, especially so
> when transactions are involved, so we would like to be able to deal
> with multiple concurrent updates being applied on the same read value.
>
> I'm wondering if we could get something like
>
> DeltaAware merge(DeltaAware originalValue, DeltaAware updateA,
> DeltaAware updateB) throws UnsolvableConflict;
>
> As Emmanuel pointed out while implementing OGM, if two different
> updates are being applied to an AtomicMap, it's possible that the
> updates relate to different keys in the AtomicMap, and for the OGM
> usecase we would be totally fine with that and would *not* like the
> transaction to be rolled back. From my understanding of AtomicMap, if
> two different keys are changed one transaction will fail (correct?).
> Of course it's totally possible that both updates where going to
> affect the same keys, and in this case we want to have the operation
> rolled back.
>
> I don't mean the API I wrote literally, I wrote it like that just to
> give a general picture of what we need; I'm not really liking the idea
> of throwing an exception on a potentially frequently occurring event,
> and also while you could chain such invocations in case of multiple
> updates arriving on the same key, I think it would be far better to be
> able to try different combinations - or let the application try to be
> clever - to try resolving as much non conflicting DeltaAware updates
> as possible.
>
> Considering that each transaction might change multiple keys, it would
> be awesome to describe the API in such a way that either Infinispan or
> the application can be "smart" and be able to estimate which
> transaction could be removed (rolled back) to provide the minimum
> amount of rolled back transactions. I'm not even sure the policy
> should favour the maximum amount of transactions, maybe the
> application wants to favour the highest possible changeset, or a
> specific important one.
>
> Even if we start just implementing the method signature I proposed,
> that could bring a hell of scalability improvements; possibly not only
> to HibernateOGM but as far as I understood the TreeCache as well.
>
> Ideas?
>
> Emmanuel, do you agree this would fit the HibernateOGM needs?
>
> Cheers,
> Sanne
>
>
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>