[infinispan-dev] Fine grained maps

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[infinispan-dev] Fine grained maps

Radim Vansa
Hi all,

I have realized that fine grained maps don't work reliably with
write-skew check. This happens because WSC tries to load the entry from
DC/cache-store, compare versions and store it, assuming that this
happens atomically as the entry is locked. However, as fine grained maps
can lock two different keys and modify the same entry, there is a risk
that the check & store won't be atomic. Right now, the update itself
won't be lost, because fine grained maps use DeltaAwareCacheEntries
which apply the updates DC's lock (there can be some problems when
passivation is used, though, [1] hopefully deals with them).

I have figured this out when trying to update the DeltaAware handling to
support more than just atomic maps - yes, there are special branches for
atomic maps in the code, which is quite ugly design-wise, IMO. My
intention is to do similar things like WSC for replaying the deltas, but
this, obviously, needs some atomicity.

IIUC, fine-grained locking was introduced back in 5.1 because of
deadlocks in the lock-acquisition algorithm; the purpose was not to
improve concurrency. Luckily, the days of deadlocks are far back, now we
can get the cluster stuck in more complex ways :) Therefore, with a
correctness-first approach, in optimistic caches I would lock just the
main key (not the composite keys). The prepare-commit should be quite
fast anyway, and I don't see how this could affect users
(counter-examples are welcome) but slightly reduced concurrency.

In pessimistic caches we have to be more cautious, since users
manipulate the locks directly and reason about them more. Therefore, we
need to lock the composite keys during transaction runtime, but in
addition to that, during the commit itself we should lock the main key
for the duration of the commit if necessary - pessimistic caches don't
sport WSC, but I was looking for some atomicity options for deltas.

An alternative would be to piggyback on DC's locking scheme, however,
this is quite unsuitable for the optimistic case with a RPC between WSC
and DC store. In addition to that, it doesn't fit into our async picture
and we would send complex compute functions into the DC, instead of
decoupled lock/unlock. I could also devise another layer of locking, but
that's just madness.

I am adding Sanne to recipients as OGM is probably the most important
consumer of atomic hash maps.

WDYT?

Radim

[1]
https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e

--
Radim Vansa <[hidden email]>
JBoss Performance Team

_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Radim Vansa
Using infinispan-dev as debugging duck...

The pessimistic case is somewhat precarious. Since during the 1PC commit
we cannot set the order by synchronizing on primary owner, we should
lock on all owners. However, the opens the possibility to lock locally
and do a RPC to lock remotely (since we lock in LockingInterceptor and
DistributionInterceptor is below that), which leads to the well-known
deadlocks. So we could move the locking into new interceptor below DI;
however, the idea is that the WSC load should happen in
EntryWrappingInterceptor/CacheLoaderInterceptor, as this is the place to
load stuff into context, and we need to lock it before these, which are
above DI :-/

So the only way I could think of is move the replication of
PrepareCommand in pessimistic caches above
PessimisticLockingInterceptor. And that's rather big for my taste.

And in order to prevent deadlocks due to different ordering of locked
keys, we have to order the keys as in optimistic caches. However, if
user locks the keys that atomic maps use explicitly, he could lock them
in different order and that would lead to deadlocks!

Pheew. Almost lost an apetite for such changes.

Radim

PS: non-tx caches aren't that complex, the situation there is quite
similar to optimistic caches.
PPS: (Repl|Dist)WriteSkewAtomicMapAPITests have testConcurrentTx
disabled, instead of requiring the WSC to be thrown :-/

On 09/26/2016 09:36 AM, Radim Vansa wrote:

> Hi all,
>
> I have realized that fine grained maps don't work reliably with
> write-skew check. This happens because WSC tries to load the entry from
> DC/cache-store, compare versions and store it, assuming that this
> happens atomically as the entry is locked. However, as fine grained maps
> can lock two different keys and modify the same entry, there is a risk
> that the check & store won't be atomic. Right now, the update itself
> won't be lost, because fine grained maps use DeltaAwareCacheEntries
> which apply the updates DC's lock (there can be some problems when
> passivation is used, though, [1] hopefully deals with them).
>
> I have figured this out when trying to update the DeltaAware handling to
> support more than just atomic maps - yes, there are special branches for
> atomic maps in the code, which is quite ugly design-wise, IMO. My
> intention is to do similar things like WSC for replaying the deltas, but
> this, obviously, needs some atomicity.
>
> IIUC, fine-grained locking was introduced back in 5.1 because of
> deadlocks in the lock-acquisition algorithm; the purpose was not to
> improve concurrency. Luckily, the days of deadlocks are far back, now we
> can get the cluster stuck in more complex ways :) Therefore, with a
> correctness-first approach, in optimistic caches I would lock just the
> main key (not the composite keys). The prepare-commit should be quite
> fast anyway, and I don't see how this could affect users
> (counter-examples are welcome) but slightly reduced concurrency.
>
> In pessimistic caches we have to be more cautious, since users
> manipulate the locks directly and reason about them more. Therefore, we
> need to lock the composite keys during transaction runtime, but in
> addition to that, during the commit itself we should lock the main key
> for the duration of the commit if necessary - pessimistic caches don't
> sport WSC, but I was looking for some atomicity options for deltas.
>
> An alternative would be to piggyback on DC's locking scheme, however,
> this is quite unsuitable for the optimistic case with a RPC between WSC
> and DC store. In addition to that, it doesn't fit into our async picture
> and we would send complex compute functions into the DC, instead of
> decoupled lock/unlock. I could also devise another layer of locking, but
> that's just madness.
>
> I am adding Sanne to recipients as OGM is probably the most important
> consumer of atomic hash maps.
>
> WDYT?
>
> Radim
>
> [1]
> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>


--
Radim Vansa <[hidden email]>
JBoss Performance Team

_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Pedro Ruivo-2
In reply to this post by Radim Vansa


On 26-09-2016 08:36, Radim Vansa wrote:

> Hi all,
>
> I have realized that fine grained maps don't work reliably with
> write-skew check. This happens because WSC tries to load the entry from
> DC/cache-store, compare versions and store it, assuming that this
> happens atomically as the entry is locked. However, as fine grained maps
> can lock two different keys and modify the same entry, there is a risk
> that the check & store won't be atomic. Right now, the update itself
> won't be lost, because fine grained maps use DeltaAwareCacheEntries
> which apply the updates DC's lock (there can be some problems when
> passivation is used, though, [1] hopefully deals with them).

Aren't you getting a ClassCastException (re: ISPN-2729)?

BTW, why not removing the FineGrainedAtomicMap? The grouping API should
provide similar semantics and it would be simpler to handle/use. Also,
it provides method to return and remove all keys associated to the group
(AdvancedCache#getGroup() and AdvancedCache#removeGroup()).

>
> I have figured this out when trying to update the DeltaAware handling to
> support more than just atomic maps - yes, there are special branches for
> atomic maps in the code, which is quite ugly design-wise, IMO. My
> intention is to do similar things like WSC for replaying the deltas, but
> this, obviously, needs some atomicity.
>
> IIUC, fine-grained locking was introduced back in 5.1 because of
> deadlocks in the lock-acquisition algorithm; the purpose was not to
> improve concurrency. Luckily, the days of deadlocks are far back, now we
> can get the cluster stuck in more complex ways :) Therefore, with a
> correctness-first approach, in optimistic caches I would lock just the
> main key (not the composite keys). The prepare-commit should be quite
> fast anyway, and I don't see how this could affect users
> (counter-examples are welcome) but slightly reduced concurrency.
>
> In pessimistic caches we have to be more cautious, since users
> manipulate the locks directly and reason about them more. Therefore, we
> need to lock the composite keys during transaction runtime, but in
> addition to that, during the commit itself we should lock the main key
> for the duration of the commit if necessary - pessimistic caches don't
> sport WSC, but I was looking for some atomicity options for deltas.
>
> An alternative would be to piggyback on DC's locking scheme, however,
> this is quite unsuitable for the optimistic case with a RPC between WSC
> and DC store. In addition to that, it doesn't fit into our async picture
> and we would send complex compute functions into the DC, instead of
> decoupled lock/unlock. I could also devise another layer of locking, but
> that's just madness.
>
> I am adding Sanne to recipients as OGM is probably the most important
> consumer of atomic hash maps.
>
> WDYT?
>
> Radim
>
> [1]
> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>
_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Dan Berindei
In reply to this post by Radim Vansa
On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:

> Hi all,
>
> I have realized that fine grained maps don't work reliably with
> write-skew check. This happens because WSC tries to load the entry from
> DC/cache-store, compare versions and store it, assuming that this
> happens atomically as the entry is locked. However, as fine grained maps
> can lock two different keys and modify the same entry, there is a risk
> that the check & store won't be atomic. Right now, the update itself
> won't be lost, because fine grained maps use DeltaAwareCacheEntries
> which apply the updates DC's lock (there can be some problems when
> passivation is used, though, [1] hopefully deals with them).
>

I had a hard time understanding what the problem is, but then I
realized it's because I was assuming we keep a separate version for
each subkey. After I realized it's not implemented like that, I also
found a couple of bugs I filed for it a long time ago:

https://issues.jboss.org/browse/ISPN-3123
https://issues.jboss.org/browse/ISPN-5584

> I have figured this out when trying to update the DeltaAware handling to
> support more than just atomic maps - yes, there are special branches for
> atomic maps in the code, which is quite ugly design-wise, IMO. My
> intention is to do similar things like WSC for replaying the deltas, but
> this, obviously, needs some atomicity.
>

Yes, for all the bugs in the AtomicMaps, it's even harder implementing
a DeltaAware that is not an AtomicMap...

But I don't see any reason to do that anyway, I'd rather work on
making the functional stuff work with transactions.

> IIUC, fine-grained locking was introduced back in 5.1 because of
> deadlocks in the lock-acquisition algorithm; the purpose was not to
> improve concurrency. Luckily, the days of deadlocks are far back, now we
> can get the cluster stuck in more complex ways :) Therefore, with a
> correctness-first approach, in optimistic caches I would lock just the
> main key (not the composite keys). The prepare-commit should be quite
> fast anyway, and I don't see how this could affect users
> (counter-examples are welcome) but slightly reduced concurrency.
>

I don't remember what initial use case for FineGrainedAtomicMaps was,
but I agree with Pedro that it's a bit long in the tooth now. The only
advantage of FGAM over grouping is that getGroup(key) needs to iterate
over the entire data container/store, so it can be a lot slower when
you have lots of small groups. But if you need to work with all the
subkeys in the every transaction, you should probably be using a
regular AtomicMap instead.

IMO we should deprecate FineGrainedAtomicMap and implement it as a
regular AtomicMap.

> In pessimistic caches we have to be more cautious, since users
> manipulate the locks directly and reason about them more. Therefore, we
> need to lock the composite keys during transaction runtime, but in
> addition to that, during the commit itself we should lock the main key
> for the duration of the commit if necessary - pessimistic caches don't
> sport WSC, but I was looking for some atomicity options for deltas.
>

-1 to implicitly locking the main key. If a DeltaAware implementation
wants to support partial locking, then it should take care of the
atomicity of the merge operation itself. If it doesn't want to support
partial locking, then it shouldn't use AdvancedCache.applyDelta().
It's a bit unfortunate that applyDelta() looks like a method that
anyone can call, but it should only be called by the DeltaAware
implementation itself.

However, I agree that implementing a DeltaAware partial locking
correctly in all possible configurations is nigh impossible. So it
would be much better if we also deprecate applyDelta() and start
ignoring the `locksToAcquire` parameter.

> An alternative would be to piggyback on DC's locking scheme, however,
> this is quite unsuitable for the optimistic case with a RPC between WSC
> and DC store. In addition to that, it doesn't fit into our async picture
> and we would send complex compute functions into the DC, instead of
> decoupled lock/unlock. I could also devise another layer of locking, but
> that's just madness.
>

-10 to piggyback on DC locking, and -100 to a new locking layer.

I think you could lock the main key by executing a
LockControlCommand(CACHE_MODE_LOCAL) from
PessimisticLockingInterceptor.visitPrepareCommand, before passing the
PrepareCommand to the next interceptor. But please don't do it!

> I am adding Sanne to recipients as OGM is probably the most important
> consumer of atomic hash maps.
>
> WDYT?
>
> Radim
>
> [1]
> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>
> --
> Radim Vansa <[hidden email]>
> JBoss Performance Team
>
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Radim Vansa
To Pedro: I have figured out that it shouldn't work rather
theoretically, so I haven't crashed into ISPN-2729.

On 09/26/2016 10:51 PM, Dan Berindei wrote:

> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
>> Hi all,
>>
>> I have realized that fine grained maps don't work reliably with
>> write-skew check. This happens because WSC tries to load the entry from
>> DC/cache-store, compare versions and store it, assuming that this
>> happens atomically as the entry is locked. However, as fine grained maps
>> can lock two different keys and modify the same entry, there is a risk
>> that the check & store won't be atomic. Right now, the update itself
>> won't be lost, because fine grained maps use DeltaAwareCacheEntries
>> which apply the updates DC's lock (there can be some problems when
>> passivation is used, though, [1] hopefully deals with them).
>>
> I had a hard time understanding what the problem is, but then I
> realized it's because I was assuming we keep a separate version for
> each subkey. After I realized it's not implemented like that, I also
> found a couple of bugs I filed for it a long time ago:
>
> https://issues.jboss.org/browse/ISPN-3123
> https://issues.jboss.org/browse/ISPN-5584
>
>> I have figured this out when trying to update the DeltaAware handling to
>> support more than just atomic maps - yes, there are special branches for
>> atomic maps in the code, which is quite ugly design-wise, IMO. My
>> intention is to do similar things like WSC for replaying the deltas, but
>> this, obviously, needs some atomicity.
>>
> Yes, for all the bugs in the AtomicMaps, it's even harder implementing
> a DeltaAware that is not an AtomicMap...
>
> But I don't see any reason to do that anyway, I'd rather work on
> making the functional stuff work with transactions.

Yes, I would rather focus on functional stuff too, but the Delta* stuff
gets into my way all the time, so I was trying to remove that. However,
though we could deprecate fine grained maps (+1!) we have to keep it
working as OGM uses that. I am awaiting some details from Sanne that
could suggest alternative solution, but he's on PTO now.

>
>> IIUC, fine-grained locking was introduced back in 5.1 because of
>> deadlocks in the lock-acquisition algorithm; the purpose was not to
>> improve concurrency. Luckily, the days of deadlocks are far back, now we
>> can get the cluster stuck in more complex ways :) Therefore, with a
>> correctness-first approach, in optimistic caches I would lock just the
>> main key (not the composite keys). The prepare-commit should be quite
>> fast anyway, and I don't see how this could affect users
>> (counter-examples are welcome) but slightly reduced concurrency.
>>
> I don't remember what initial use case for FineGrainedAtomicMaps was,
> but I agree with Pedro that it's a bit long in the tooth now. The only
> advantage of FGAM over grouping is that getGroup(key) needs to iterate
> over the entire data container/store, so it can be a lot slower when
> you have lots of small groups. But if you need to work with all the
> subkeys in the every transaction, you should probably be using a
> regular AtomicMap instead.

Iterating through whole container seems like a very limiting factor to
me, but I would keep AtomicMaps and let them be implemented through
deltas/functional commands (preferred), but use the standard locking
mechanisms instead of fine-grained insanity.

>
> IMO we should deprecate FineGrainedAtomicMap and implement it as a
> regular AtomicMap.
>
>> In pessimistic caches we have to be more cautious, since users
>> manipulate the locks directly and reason about them more. Therefore, we
>> need to lock the composite keys during transaction runtime, but in
>> addition to that, during the commit itself we should lock the main key
>> for the duration of the commit if necessary - pessimistic caches don't
>> sport WSC, but I was looking for some atomicity options for deltas.
>>
> -1 to implicitly locking the main key. If a DeltaAware implementation
> wants to support partial locking, then it should take care of the
> atomicity of the merge operation itself. If it doesn't want to support
> partial locking, then it shouldn't use AdvancedCache.applyDelta().
> It's a bit unfortunate that applyDelta() looks like a method that
> anyone can call, but it should only be called by the DeltaAware
> implementation itself.

As I have mentioned in my last mail, I found that it's not that easy, so
I am not implementing that. But it's not about taking care of atomicity
of the merge - applying merge can be synchronized, but you have to do
that with the entry stored in DC when the entry is about to be stored in
DC - and this is the only moment you can squeeze the WSC inl, because
the DeltaAware can't know anything about WSCs. That's the DC locking
piggyback you -10.

>
> However, I agree that implementing a DeltaAware partial locking
> correctly in all possible configurations is nigh impossible. So it
> would be much better if we also deprecate applyDelta() and start
> ignoring the `locksToAcquire` parameter.
>
>> An alternative would be to piggyback on DC's locking scheme, however,
>> this is quite unsuitable for the optimistic case with a RPC between WSC
>> and DC store. In addition to that, it doesn't fit into our async picture
>> and we would send complex compute functions into the DC, instead of
>> decoupled lock/unlock. I could also devise another layer of locking, but
>> that's just madness.
>>
> -10 to piggyback on DC locking, and -100 to a new locking layer.
>
> I think you could lock the main key by executing a
> LockControlCommand(CACHE_MODE_LOCAL) from
> PessimisticLockingInterceptor.visitPrepareCommand, before passing the
> PrepareCommand to the next interceptor. But please don't do it!

Okay, I'll just wait until someone tells me why the heck anyone needs
fine grained, discuss how to avoid it and then deprecate it :)

Radim

>
>> I am adding Sanne to recipients as OGM is probably the most important
>> consumer of atomic hash maps.
>>
>> WDYT?
>>
>> Radim
>>
>> [1]
>> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>>
>> --
>> Radim Vansa <[hidden email]>
>> JBoss Performance Team
>>
>> _______________________________________________
>> infinispan-dev mailing list
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev


--
Radim Vansa <[hidden email]>
JBoss Performance Team

_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Sanne Grinovero-3
Hibernate OGM is using the FGAMs and needs their "fine-grained"
semantics as it's being used to store what is perceived possibly as
independent user entries; having these entries share a same lock would
introduce possibilities of deadlock depending on the end user's
business logic; we're an abstraction layer and these semantics are
being relied on.
I believe a good analogy to this is the comparison of databases
implementing row-level locking vs. page-level locking; such changes in
granularity would make end users loose hair so I'll not change our
usage from FGAMS to AMs.

We can maybe move to grouping or to queries; this wasn't considered
back then as neither grouping nor (unindexed) queries were available.
Both grouping and queries have their drawbacks though, so we can take
this in consideration on the OGM team but it's going to take some
time;

So feel free deprecate FGAMs but please don't remove them yet.

For the record, OGM never uses write skew checks on FGAMs, and also
Hibernate OGM / Hot Rod doesn't use FGAMs (whe use them only in
embedded mode, when transactions are available).

Thanks,
Sanne


On 27 September 2016 at 08:28, Radim Vansa <[hidden email]> wrote:

> To Pedro: I have figured out that it shouldn't work rather
> theoretically, so I haven't crashed into ISPN-2729.
>
> On 09/26/2016 10:51 PM, Dan Berindei wrote:
>> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
>>> Hi all,
>>>
>>> I have realized that fine grained maps don't work reliably with
>>> write-skew check. This happens because WSC tries to load the entry from
>>> DC/cache-store, compare versions and store it, assuming that this
>>> happens atomically as the entry is locked. However, as fine grained maps
>>> can lock two different keys and modify the same entry, there is a risk
>>> that the check & store won't be atomic. Right now, the update itself
>>> won't be lost, because fine grained maps use DeltaAwareCacheEntries
>>> which apply the updates DC's lock (there can be some problems when
>>> passivation is used, though, [1] hopefully deals with them).
>>>
>> I had a hard time understanding what the problem is, but then I
>> realized it's because I was assuming we keep a separate version for
>> each subkey. After I realized it's not implemented like that, I also
>> found a couple of bugs I filed for it a long time ago:
>>
>> https://issues.jboss.org/browse/ISPN-3123
>> https://issues.jboss.org/browse/ISPN-5584
>>
>>> I have figured this out when trying to update the DeltaAware handling to
>>> support more than just atomic maps - yes, there are special branches for
>>> atomic maps in the code, which is quite ugly design-wise, IMO. My
>>> intention is to do similar things like WSC for replaying the deltas, but
>>> this, obviously, needs some atomicity.
>>>
>> Yes, for all the bugs in the AtomicMaps, it's even harder implementing
>> a DeltaAware that is not an AtomicMap...
>>
>> But I don't see any reason to do that anyway, I'd rather work on
>> making the functional stuff work with transactions.
>
> Yes, I would rather focus on functional stuff too, but the Delta* stuff
> gets into my way all the time, so I was trying to remove that. However,
> though we could deprecate fine grained maps (+1!) we have to keep it
> working as OGM uses that. I am awaiting some details from Sanne that
> could suggest alternative solution, but he's on PTO now.
>
>>
>>> IIUC, fine-grained locking was introduced back in 5.1 because of
>>> deadlocks in the lock-acquisition algorithm; the purpose was not to
>>> improve concurrency. Luckily, the days of deadlocks are far back, now we
>>> can get the cluster stuck in more complex ways :) Therefore, with a
>>> correctness-first approach, in optimistic caches I would lock just the
>>> main key (not the composite keys). The prepare-commit should be quite
>>> fast anyway, and I don't see how this could affect users
>>> (counter-examples are welcome) but slightly reduced concurrency.
>>>
>> I don't remember what initial use case for FineGrainedAtomicMaps was,
>> but I agree with Pedro that it's a bit long in the tooth now. The only
>> advantage of FGAM over grouping is that getGroup(key) needs to iterate
>> over the entire data container/store, so it can be a lot slower when
>> you have lots of small groups. But if you need to work with all the
>> subkeys in the every transaction, you should probably be using a
>> regular AtomicMap instead.
>
> Iterating through whole container seems like a very limiting factor to
> me, but I would keep AtomicMaps and let them be implemented through
> deltas/functional commands (preferred), but use the standard locking
> mechanisms instead of fine-grained insanity.
>
>>
>> IMO we should deprecate FineGrainedAtomicMap and implement it as a
>> regular AtomicMap.
>>
>>> In pessimistic caches we have to be more cautious, since users
>>> manipulate the locks directly and reason about them more. Therefore, we
>>> need to lock the composite keys during transaction runtime, but in
>>> addition to that, during the commit itself we should lock the main key
>>> for the duration of the commit if necessary - pessimistic caches don't
>>> sport WSC, but I was looking for some atomicity options for deltas.
>>>
>> -1 to implicitly locking the main key. If a DeltaAware implementation
>> wants to support partial locking, then it should take care of the
>> atomicity of the merge operation itself. If it doesn't want to support
>> partial locking, then it shouldn't use AdvancedCache.applyDelta().
>> It's a bit unfortunate that applyDelta() looks like a method that
>> anyone can call, but it should only be called by the DeltaAware
>> implementation itself.
>
> As I have mentioned in my last mail, I found that it's not that easy, so
> I am not implementing that. But it's not about taking care of atomicity
> of the merge - applying merge can be synchronized, but you have to do
> that with the entry stored in DC when the entry is about to be stored in
> DC - and this is the only moment you can squeeze the WSC inl, because
> the DeltaAware can't know anything about WSCs. That's the DC locking
> piggyback you -10.
>
>>
>> However, I agree that implementing a DeltaAware partial locking
>> correctly in all possible configurations is nigh impossible. So it
>> would be much better if we also deprecate applyDelta() and start
>> ignoring the `locksToAcquire` parameter.
>>
>>> An alternative would be to piggyback on DC's locking scheme, however,
>>> this is quite unsuitable for the optimistic case with a RPC between WSC
>>> and DC store. In addition to that, it doesn't fit into our async picture
>>> and we would send complex compute functions into the DC, instead of
>>> decoupled lock/unlock. I could also devise another layer of locking, but
>>> that's just madness.
>>>
>> -10 to piggyback on DC locking, and -100 to a new locking layer.
>>
>> I think you could lock the main key by executing a
>> LockControlCommand(CACHE_MODE_LOCAL) from
>> PessimisticLockingInterceptor.visitPrepareCommand, before passing the
>> PrepareCommand to the next interceptor. But please don't do it!
>
> Okay, I'll just wait until someone tells me why the heck anyone needs
> fine grained, discuss how to avoid it and then deprecate it :)
>
> Radim
>
>>
>>> I am adding Sanne to recipients as OGM is probably the most important
>>> consumer of atomic hash maps.
>>>
>>> WDYT?
>>>
>>> Radim
>>>
>>> [1]
>>> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>>>
>>> --
>>> Radim Vansa <[hidden email]>
>>> JBoss Performance Team
>>>
>>> _______________________________________________
>>> infinispan-dev mailing list
>>> [hidden email]
>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>> _______________________________________________
>> infinispan-dev mailing list
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>
>
> --
> Radim Vansa <[hidden email]>
> JBoss Performance Team
>
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Radim Vansa
On 09/27/2016 01:35 PM, Sanne Grinovero wrote:

> Hibernate OGM is using the FGAMs and needs their "fine-grained"
> semantics as it's being used to store what is perceived possibly as
> independent user entries; having these entries share a same lock would
> introduce possibilities of deadlock depending on the end user's
> business logic; we're an abstraction layer and these semantics are
> being relied on.
> I believe a good analogy to this is the comparison of databases
> implementing row-level locking vs. page-level locking; such changes in
> granularity would make end users loose hair so I'll not change our
> usage from FGAMS to AMs.

I am not asking you to move from FGAMs to AMs as-is - I am trying to
precisely asses your needs and provide an option that suits them best,
while not creating malfunctioning configurations and breaking encapsulation.

OGM uses <transaction lockingMode="OPTIMISTIC" ... /> configuration by
default (not sure if you support changing that to pessimistic). With
this configuration, there's no risk of deadlocks within Infinispan, no
matter what order you use to read/write entries in a transaction. All
locks are acquired in a deterministic order only during transaction
commit, that appears to OGM (or the user) as a single atomic operation.
So what fine-grained gives you now is that you don't have to wait until
the tx1.commit() call completes before tx2.commit() can start. So I see
the performance impact upon highly concurrent modification of single
entry, but from the end-user perspective it should not have any visible
effect (least lose hair :)).

Another important feature of AtomicMaps (but FGAM and AM have it in
common) is that they send only the delta over the wire - such behaviour
must be preserved, of course, but functional API should supersede the
hacks in place now.

> We can maybe move to grouping or to queries; this wasn't considered
> back then as neither grouping nor (unindexed) queries were available.
> Both grouping and queries have their drawbacks though, so we can take
> this in consideration on the OGM team but it's going to take some
> time;
>
> So feel free deprecate FGAMs but please don't remove them yet.

We wouldn't remove the interface in 9.0; we would return something that
does what you need but differently.

>
> For the record, OGM never uses write skew checks on FGAMs, and also
> Hibernate OGM / Hot Rod doesn't use FGAMs (whe use them only in
> embedded mode, when transactions are available).

And that's the only reason why it was not fixed sooner :)

Radim

>
> Thanks,
> Sanne
>
>
> On 27 September 2016 at 08:28, Radim Vansa <[hidden email]> wrote:
>> To Pedro: I have figured out that it shouldn't work rather
>> theoretically, so I haven't crashed into ISPN-2729.
>>
>> On 09/26/2016 10:51 PM, Dan Berindei wrote:
>>> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
>>>> Hi all,
>>>>
>>>> I have realized that fine grained maps don't work reliably with
>>>> write-skew check. This happens because WSC tries to load the entry from
>>>> DC/cache-store, compare versions and store it, assuming that this
>>>> happens atomically as the entry is locked. However, as fine grained maps
>>>> can lock two different keys and modify the same entry, there is a risk
>>>> that the check & store won't be atomic. Right now, the update itself
>>>> won't be lost, because fine grained maps use DeltaAwareCacheEntries
>>>> which apply the updates DC's lock (there can be some problems when
>>>> passivation is used, though, [1] hopefully deals with them).
>>>>
>>> I had a hard time understanding what the problem is, but then I
>>> realized it's because I was assuming we keep a separate version for
>>> each subkey. After I realized it's not implemented like that, I also
>>> found a couple of bugs I filed for it a long time ago:
>>>
>>> https://issues.jboss.org/browse/ISPN-3123
>>> https://issues.jboss.org/browse/ISPN-5584
>>>
>>>> I have figured this out when trying to update the DeltaAware handling to
>>>> support more than just atomic maps - yes, there are special branches for
>>>> atomic maps in the code, which is quite ugly design-wise, IMO. My
>>>> intention is to do similar things like WSC for replaying the deltas, but
>>>> this, obviously, needs some atomicity.
>>>>
>>> Yes, for all the bugs in the AtomicMaps, it's even harder implementing
>>> a DeltaAware that is not an AtomicMap...
>>>
>>> But I don't see any reason to do that anyway, I'd rather work on
>>> making the functional stuff work with transactions.
>> Yes, I would rather focus on functional stuff too, but the Delta* stuff
>> gets into my way all the time, so I was trying to remove that. However,
>> though we could deprecate fine grained maps (+1!) we have to keep it
>> working as OGM uses that. I am awaiting some details from Sanne that
>> could suggest alternative solution, but he's on PTO now.
>>
>>>> IIUC, fine-grained locking was introduced back in 5.1 because of
>>>> deadlocks in the lock-acquisition algorithm; the purpose was not to
>>>> improve concurrency. Luckily, the days of deadlocks are far back, now we
>>>> can get the cluster stuck in more complex ways :) Therefore, with a
>>>> correctness-first approach, in optimistic caches I would lock just the
>>>> main key (not the composite keys). The prepare-commit should be quite
>>>> fast anyway, and I don't see how this could affect users
>>>> (counter-examples are welcome) but slightly reduced concurrency.
>>>>
>>> I don't remember what initial use case for FineGrainedAtomicMaps was,
>>> but I agree with Pedro that it's a bit long in the tooth now. The only
>>> advantage of FGAM over grouping is that getGroup(key) needs to iterate
>>> over the entire data container/store, so it can be a lot slower when
>>> you have lots of small groups. But if you need to work with all the
>>> subkeys in the every transaction, you should probably be using a
>>> regular AtomicMap instead.
>> Iterating through whole container seems like a very limiting factor to
>> me, but I would keep AtomicMaps and let them be implemented through
>> deltas/functional commands (preferred), but use the standard locking
>> mechanisms instead of fine-grained insanity.
>>
>>> IMO we should deprecate FineGrainedAtomicMap and implement it as a
>>> regular AtomicMap.
>>>
>>>> In pessimistic caches we have to be more cautious, since users
>>>> manipulate the locks directly and reason about them more. Therefore, we
>>>> need to lock the composite keys during transaction runtime, but in
>>>> addition to that, during the commit itself we should lock the main key
>>>> for the duration of the commit if necessary - pessimistic caches don't
>>>> sport WSC, but I was looking for some atomicity options for deltas.
>>>>
>>> -1 to implicitly locking the main key. If a DeltaAware implementation
>>> wants to support partial locking, then it should take care of the
>>> atomicity of the merge operation itself. If it doesn't want to support
>>> partial locking, then it shouldn't use AdvancedCache.applyDelta().
>>> It's a bit unfortunate that applyDelta() looks like a method that
>>> anyone can call, but it should only be called by the DeltaAware
>>> implementation itself.
>> As I have mentioned in my last mail, I found that it's not that easy, so
>> I am not implementing that. But it's not about taking care of atomicity
>> of the merge - applying merge can be synchronized, but you have to do
>> that with the entry stored in DC when the entry is about to be stored in
>> DC - and this is the only moment you can squeeze the WSC inl, because
>> the DeltaAware can't know anything about WSCs. That's the DC locking
>> piggyback you -10.
>>
>>> However, I agree that implementing a DeltaAware partial locking
>>> correctly in all possible configurations is nigh impossible. So it
>>> would be much better if we also deprecate applyDelta() and start
>>> ignoring the `locksToAcquire` parameter.
>>>
>>>> An alternative would be to piggyback on DC's locking scheme, however,
>>>> this is quite unsuitable for the optimistic case with a RPC between WSC
>>>> and DC store. In addition to that, it doesn't fit into our async picture
>>>> and we would send complex compute functions into the DC, instead of
>>>> decoupled lock/unlock. I could also devise another layer of locking, but
>>>> that's just madness.
>>>>
>>> -10 to piggyback on DC locking, and -100 to a new locking layer.
>>>
>>> I think you could lock the main key by executing a
>>> LockControlCommand(CACHE_MODE_LOCAL) from
>>> PessimisticLockingInterceptor.visitPrepareCommand, before passing the
>>> PrepareCommand to the next interceptor. But please don't do it!
>> Okay, I'll just wait until someone tells me why the heck anyone needs
>> fine grained, discuss how to avoid it and then deprecate it :)
>>
>> Radim
>>
>>>> I am adding Sanne to recipients as OGM is probably the most important
>>>> consumer of atomic hash maps.
>>>>
>>>> WDYT?
>>>>
>>>> Radim
>>>>
>>>> [1]
>>>> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>>>>
>>>> --
>>>> Radim Vansa <[hidden email]>
>>>> JBoss Performance Team
>>>>
>>>> _______________________________________________
>>>> infinispan-dev mailing list
>>>> [hidden email]
>>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>>> _______________________________________________
>>> infinispan-dev mailing list
>>> [hidden email]
>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>>
>> --
>> Radim Vansa <[hidden email]>
>> JBoss Performance Team
>>
>> _______________________________________________
>> infinispan-dev mailing list
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev


--
Radim Vansa <[hidden email]>
JBoss Performance Team

_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Dan Berindei
In reply to this post by Radim Vansa
On Tue, Sep 27, 2016 at 10:28 AM, Radim Vansa <[hidden email]> wrote:

> To Pedro: I have figured out that it shouldn't work rather
> theoretically, so I haven't crashed into ISPN-2729.
>
> On 09/26/2016 10:51 PM, Dan Berindei wrote:
>> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
>>> Hi all,
>>>
>>> I have realized that fine grained maps don't work reliably with
>>> write-skew check. This happens because WSC tries to load the entry from
>>> DC/cache-store, compare versions and store it, assuming that this
>>> happens atomically as the entry is locked. However, as fine grained maps
>>> can lock two different keys and modify the same entry, there is a risk
>>> that the check & store won't be atomic. Right now, the update itself
>>> won't be lost, because fine grained maps use DeltaAwareCacheEntries
>>> which apply the updates DC's lock (there can be some problems when
>>> passivation is used, though, [1] hopefully deals with them).
>>>
>> I had a hard time understanding what the problem is, but then I
>> realized it's because I was assuming we keep a separate version for
>> each subkey. After I realized it's not implemented like that, I also
>> found a couple of bugs I filed for it a long time ago:
>>
>> https://issues.jboss.org/browse/ISPN-3123
>> https://issues.jboss.org/browse/ISPN-5584
>>
>>> I have figured this out when trying to update the DeltaAware handling to
>>> support more than just atomic maps - yes, there are special branches for
>>> atomic maps in the code, which is quite ugly design-wise, IMO. My
>>> intention is to do similar things like WSC for replaying the deltas, but
>>> this, obviously, needs some atomicity.
>>>
>> Yes, for all the bugs in the AtomicMaps, it's even harder implementing
>> a DeltaAware that is not an AtomicMap...
>>
>> But I don't see any reason to do that anyway, I'd rather work on
>> making the functional stuff work with transactions.
>
> Yes, I would rather focus on functional stuff too, but the Delta* stuff
> gets into my way all the time, so I was trying to remove that. However,
> though we could deprecate fine grained maps (+1!) we have to keep it
> working as OGM uses that. I am awaiting some details from Sanne that
> could suggest alternative solution, but he's on PTO now.
>
>>
>>> IIUC, fine-grained locking was introduced back in 5.1 because of
>>> deadlocks in the lock-acquisition algorithm; the purpose was not to
>>> improve concurrency. Luckily, the days of deadlocks are far back, now we
>>> can get the cluster stuck in more complex ways :) Therefore, with a
>>> correctness-first approach, in optimistic caches I would lock just the
>>> main key (not the composite keys). The prepare-commit should be quite
>>> fast anyway, and I don't see how this could affect users
>>> (counter-examples are welcome) but slightly reduced concurrency.
>>>
>> I don't remember what initial use case for FineGrainedAtomicMaps was,
>> but I agree with Pedro that it's a bit long in the tooth now. The only
>> advantage of FGAM over grouping is that getGroup(key) needs to iterate
>> over the entire data container/store, so it can be a lot slower when
>> you have lots of small groups. But if you need to work with all the
>> subkeys in the every transaction, you should probably be using a
>> regular AtomicMap instead.
>
> Iterating through whole container seems like a very limiting factor to
> me, but I would keep AtomicMaps and let them be implemented through
> deltas/functional commands (preferred), but use the standard locking
> mechanisms instead of fine-grained insanity.
>

Indeed, it can be limiting, especially when you have one small group
that's iterated over all the time and one large group that's never
iterated in the same cache. I was hoping it would be good enough as a
bridge until we have the functional API working with transactions, but
based on Sanne's comments I guess I was wrong :)

>>
>> IMO we should deprecate FineGrainedAtomicMap and implement it as a
>> regular AtomicMap.
>>
>>> In pessimistic caches we have to be more cautious, since users
>>> manipulate the locks directly and reason about them more. Therefore, we
>>> need to lock the composite keys during transaction runtime, but in
>>> addition to that, during the commit itself we should lock the main key
>>> for the duration of the commit if necessary - pessimistic caches don't
>>> sport WSC, but I was looking for some atomicity options for deltas.
>>>
>> -1 to implicitly locking the main key. If a DeltaAware implementation
>> wants to support partial locking, then it should take care of the
>> atomicity of the merge operation itself. If it doesn't want to support
>> partial locking, then it shouldn't use AdvancedCache.applyDelta().
>> It's a bit unfortunate that applyDelta() looks like a method that
>> anyone can call, but it should only be called by the DeltaAware
>> implementation itself.
>
> As I have mentioned in my last mail, I found that it's not that easy, so
> I am not implementing that. But it's not about taking care of atomicity
> of the merge - applying merge can be synchronized, but you have to do
> that with the entry stored in DC when the entry is about to be stored in
> DC - and this is the only moment you can squeeze the WSC inl, because
> the DeltaAware can't know anything about WSCs. That's the DC locking
> piggyback you -10.
>

I think you're making it harder than it should be, because you're
trying to come up with a generic solution that works with any possible
data structure. But if a data structure is not suitable for
fine-grained locking, it should just use regular locking instead
(locksToAcquire = {mainKey}).

E.g. any ordered structure is out of the question for fine-grained
locking, but it should be possible to implement a fine-grained set/bag
without any new locking in core.

As you may have seen from ISPN-3123 and ISPN-5584, I think the problem
with FGAM is that it's not granular enough: we shouldn't throw
WriteSkewExceptions just because two transactions modify the same
FGAM, we should only throw the WriteSkewException when both
transaction modify the same subkey.

>>
>> However, I agree that implementing a DeltaAware partial locking
>> correctly in all possible configurations is nigh impossible. So it
>> would be much better if we also deprecate applyDelta() and start
>> ignoring the `locksToAcquire` parameter.
>>
>>> An alternative would be to piggyback on DC's locking scheme, however,
>>> this is quite unsuitable for the optimistic case with a RPC between WSC
>>> and DC store. In addition to that, it doesn't fit into our async picture
>>> and we would send complex compute functions into the DC, instead of
>>> decoupled lock/unlock. I could also devise another layer of locking, but
>>> that's just madness.
>>>
>> -10 to piggyback on DC locking, and -100 to a new locking layer.
>>
>> I think you could lock the main key by executing a
>> LockControlCommand(CACHE_MODE_LOCAL) from
>> PessimisticLockingInterceptor.visitPrepareCommand, before passing the
>> PrepareCommand to the next interceptor. But please don't do it!
>
> Okay, I'll just wait until someone tells me why the heck anyone needs
> fine grained, discuss how to avoid it and then deprecate it :)
>
> Radim
>
>>
>>> I am adding Sanne to recipients as OGM is probably the most important
>>> consumer of atomic hash maps.
>>>
>>> WDYT?
>>>
>>> Radim
>>>
>>> [1]
>>> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>>>
>>> --
>>> Radim Vansa <[hidden email]>
>>> JBoss Performance Team
>>>
>>> _______________________________________________
>>> infinispan-dev mailing list
>>> [hidden email]
>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>> _______________________________________________
>> infinispan-dev mailing list
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>
>
> --
> Radim Vansa <[hidden email]>
> JBoss Performance Team
>
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Radim Vansa
On 09/27/2016 04:47 PM, Dan Berindei wrote:

> On Tue, Sep 27, 2016 at 10:28 AM, Radim Vansa <[hidden email]> wrote:
>> To Pedro: I have figured out that it shouldn't work rather
>> theoretically, so I haven't crashed into ISPN-2729.
>>
>> On 09/26/2016 10:51 PM, Dan Berindei wrote:
>>> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
>>>> Hi all,
>>>>
>>>> I have realized that fine grained maps don't work reliably with
>>>> write-skew check. This happens because WSC tries to load the entry from
>>>> DC/cache-store, compare versions and store it, assuming that this
>>>> happens atomically as the entry is locked. However, as fine grained maps
>>>> can lock two different keys and modify the same entry, there is a risk
>>>> that the check & store won't be atomic. Right now, the update itself
>>>> won't be lost, because fine grained maps use DeltaAwareCacheEntries
>>>> which apply the updates DC's lock (there can be some problems when
>>>> passivation is used, though, [1] hopefully deals with them).
>>>>
>>> I had a hard time understanding what the problem is, but then I
>>> realized it's because I was assuming we keep a separate version for
>>> each subkey. After I realized it's not implemented like that, I also
>>> found a couple of bugs I filed for it a long time ago:
>>>
>>> https://issues.jboss.org/browse/ISPN-3123
>>> https://issues.jboss.org/browse/ISPN-5584
>>>
>>>> I have figured this out when trying to update the DeltaAware handling to
>>>> support more than just atomic maps - yes, there are special branches for
>>>> atomic maps in the code, which is quite ugly design-wise, IMO. My
>>>> intention is to do similar things like WSC for replaying the deltas, but
>>>> this, obviously, needs some atomicity.
>>>>
>>> Yes, for all the bugs in the AtomicMaps, it's even harder implementing
>>> a DeltaAware that is not an AtomicMap...
>>>
>>> But I don't see any reason to do that anyway, I'd rather work on
>>> making the functional stuff work with transactions.
>> Yes, I would rather focus on functional stuff too, but the Delta* stuff
>> gets into my way all the time, so I was trying to remove that. However,
>> though we could deprecate fine grained maps (+1!) we have to keep it
>> working as OGM uses that. I am awaiting some details from Sanne that
>> could suggest alternative solution, but he's on PTO now.
>>
>>>> IIUC, fine-grained locking was introduced back in 5.1 because of
>>>> deadlocks in the lock-acquisition algorithm; the purpose was not to
>>>> improve concurrency. Luckily, the days of deadlocks are far back, now we
>>>> can get the cluster stuck in more complex ways :) Therefore, with a
>>>> correctness-first approach, in optimistic caches I would lock just the
>>>> main key (not the composite keys). The prepare-commit should be quite
>>>> fast anyway, and I don't see how this could affect users
>>>> (counter-examples are welcome) but slightly reduced concurrency.
>>>>
>>> I don't remember what initial use case for FineGrainedAtomicMaps was,
>>> but I agree with Pedro that it's a bit long in the tooth now. The only
>>> advantage of FGAM over grouping is that getGroup(key) needs to iterate
>>> over the entire data container/store, so it can be a lot slower when
>>> you have lots of small groups. But if you need to work with all the
>>> subkeys in the every transaction, you should probably be using a
>>> regular AtomicMap instead.
>> Iterating through whole container seems like a very limiting factor to
>> me, but I would keep AtomicMaps and let them be implemented through
>> deltas/functional commands (preferred), but use the standard locking
>> mechanisms instead of fine-grained insanity.
>>
> Indeed, it can be limiting, especially when you have one small group
> that's iterated over all the time and one large group that's never
> iterated in the same cache. I was hoping it would be good enough as a
> bridge until we have the functional API working with transactions, but
> based on Sanne's comments I guess I was wrong :)
>
>>> IMO we should deprecate FineGrainedAtomicMap and implement it as a
>>> regular AtomicMap.
>>>
>>>> In pessimistic caches we have to be more cautious, since users
>>>> manipulate the locks directly and reason about them more. Therefore, we
>>>> need to lock the composite keys during transaction runtime, but in
>>>> addition to that, during the commit itself we should lock the main key
>>>> for the duration of the commit if necessary - pessimistic caches don't
>>>> sport WSC, but I was looking for some atomicity options for deltas.
>>>>
>>> -1 to implicitly locking the main key. If a DeltaAware implementation
>>> wants to support partial locking, then it should take care of the
>>> atomicity of the merge operation itself. If it doesn't want to support
>>> partial locking, then it shouldn't use AdvancedCache.applyDelta().
>>> It's a bit unfortunate that applyDelta() looks like a method that
>>> anyone can call, but it should only be called by the DeltaAware
>>> implementation itself.
>> As I have mentioned in my last mail, I found that it's not that easy, so
>> I am not implementing that. But it's not about taking care of atomicity
>> of the merge - applying merge can be synchronized, but you have to do
>> that with the entry stored in DC when the entry is about to be stored in
>> DC - and this is the only moment you can squeeze the WSC inl, because
>> the DeltaAware can't know anything about WSCs. That's the DC locking
>> piggyback you -10.
>>
> I think you're making it harder than it should be, because you're
> trying to come up with a generic solution that works with any possible
> data structure.

I am trying to work with two concepts: (Copyable)DeltaAware interface,
and ApplyDeltaCommand with its set of locks. Atomic maps are
higher-level concept and there should not be any Ugh!s [1].

In any implementation of DeltaAwareCacheEntry.commit(), you'll have to
atomically load the (Im)mutableCacheEntry from DC/cache store and store
it into DC. Yes, you could do a load, copy (because the delta is
modifying), apply delta/run WSC, compare&set in DC, but that's quite
annoying loop implemented through exception handling <- I haven't
proposed this and focused on changing the locking scheme.

[1]
https://github.com/infinispan/jdg/blob/3aaa3d85fe9a90ee3c371b44ff5e5b36414c69fd/core/src/main/java/org/infinispan/container/entries/ReadCommittedEntry.java#L150

>   But if a data structure is not suitable for
> fine-grained locking, it should just use regular locking instead
> (locksToAcquire = {mainKey}).
>
> E.g. any ordered structure is out of the question for fine-grained
> locking, but it should be possible to implement a fine-grained set/bag
> without any new locking in core.
>
> As you may have seen from ISPN-3123 and ISPN-5584, I think the problem
> with FGAM is that it's not granular enough: we shouldn't throw
> WriteSkewExceptions just because two transactions modify the same
> FGAM, we should only throw the WriteSkewException when both
> transaction modify the same subkey.

You're right that WSC is not fine-grained enough, and at this point you
can't solve that generally - how do you apply WSC on DeltaAware when you
know that it locks certain keys? And you would add the static call to
WSCHelper into DeltaAwareCacheEntry, class made for storing value &
interacting with DC?

>
>>> However, I agree that implementing a DeltaAware partial locking
>>> correctly in all possible configurations is nigh impossible. So it
>>> would be much better if we also deprecate applyDelta() and start
>>> ignoring the `locksToAcquire` parameter.
>>>
>>>> An alternative would be to piggyback on DC's locking scheme, however,
>>>> this is quite unsuitable for the optimistic case with a RPC between WSC
>>>> and DC store. In addition to that, it doesn't fit into our async picture
>>>> and we would send complex compute functions into the DC, instead of
>>>> decoupled lock/unlock. I could also devise another layer of locking, but
>>>> that's just madness.
>>>>
>>> -10 to piggyback on DC locking, and -100 to a new locking layer.
>>>
>>> I think you could lock the main key by executing a
>>> LockControlCommand(CACHE_MODE_LOCAL) from
>>> PessimisticLockingInterceptor.visitPrepareCommand, before passing the
>>> PrepareCommand to the next interceptor. But please don't do it!
>> Okay, I'll just wait until someone tells me why the heck anyone needs
>> fine grained, discuss how to avoid it and then deprecate it :)
>>
>> Radim
>>
>>>> I am adding Sanne to recipients as OGM is probably the most important
>>>> consumer of atomic hash maps.
>>>>
>>>> WDYT?
>>>>
>>>> Radim
>>>>
>>>> [1]
>>>> https://github.com/infinispan/infinispan/pull/4564/commits/2eeb7efbd4e1ea3e7f45ff2b443691b78ad4ae8e
>>>>
>>>> --
>>>> Radim Vansa <[hidden email]>
>>>> JBoss Performance Team
>>>>
>>>> _______________________________________________
>>>> infinispan-dev mailing list
>>>> [hidden email]
>>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>>> _______________________________________________
>>> infinispan-dev mailing list
>>> [hidden email]
>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>>
>> --
>> Radim Vansa <[hidden email]>
>> JBoss Performance Team
>>
>> _______________________________________________
>> infinispan-dev mailing list
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev


--
Radim Vansa <[hidden email]>
JBoss Performance Team

_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Dan Berindei
On Tue, Sep 27, 2016 at 6:15 PM, Radim Vansa <[hidden email]> wrote:
> On 09/27/2016 04:47 PM, Dan Berindei wrote:
>> On Tue, Sep 27, 2016 at 10:28 AM, Radim Vansa <[hidden email]> wrote:
>>> To Pedro: I have figured out that it shouldn't work rather
>>> theoretically, so I haven't crashed into ISPN-2729.
>>>
>>> On 09/26/2016 10:51 PM, Dan Berindei wrote:
>>>> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
...

>>>>> In pessimistic caches we have to be more cautious, since users
>>>>> manipulate the locks directly and reason about them more. Therefore, we
>>>>> need to lock the composite keys during transaction runtime, but in
>>>>> addition to that, during the commit itself we should lock the main key
>>>>> for the duration of the commit if necessary - pessimistic caches don't
>>>>> sport WSC, but I was looking for some atomicity options for deltas.
>>>>>
>>>> -1 to implicitly locking the main key. If a DeltaAware implementation
>>>> wants to support partial locking, then it should take care of the
>>>> atomicity of the merge operation itself. If it doesn't want to support
>>>> partial locking, then it shouldn't use AdvancedCache.applyDelta().
>>>> It's a bit unfortunate that applyDelta() looks like a method that
>>>> anyone can call, but it should only be called by the DeltaAware
>>>> implementation itself.
>>> As I have mentioned in my last mail, I found that it's not that easy, so
>>> I am not implementing that. But it's not about taking care of atomicity
>>> of the merge - applying merge can be synchronized, but you have to do
>>> that with the entry stored in DC when the entry is about to be stored in
>>> DC - and this is the only moment you can squeeze the WSC inl, because
>>> the DeltaAware can't know anything about WSCs. That's the DC locking
>>> piggyback you -10.
>>>
>> I think you're making it harder than it should be, because you're
>> trying to come up with a generic solution that works with any possible
>> data structure.
>
> I am trying to work with two concepts: (Copyable)DeltaAware interface,
> and ApplyDeltaCommand with its set of locks. Atomic maps are
> higher-level concept and there should not be any Ugh!s [1].
>

We can't look at ApplyDeltaCommand in isolation, as the user of the
data structure should never call applyDelta() directly. All DeltaAware
structures should have a user-facing proxy that knows the internal
structure and calls applyDelta(), following the rules that we set.

The way I see it, these are the 2 low-level concepts, both using the
DeltaAware interface:

1) Coarse-grained DeltaAware (high-level equivalent: AtomicMap).
These use PutKeyValueCommand(with Flag.DELTA_WRITE set in the
constructor), although I do have a stale branch trying to make them
use ApplyDeltaCommand(locksToAcquire=null).
These are merged in the invocation context, using only the regular locks.

2) Fine-grained DeltaAware (high-level equivalent: FineGrainedAtomicMap).
These use use ApplyDeltaCommand(locksToAcquire=CompositeKey*) and
DeltaAwareCacheEntry, and must be able to merge concurrent updates to
separate subkeys without losing updates.

Currently both types of data structures can implement either
DeltaAware or CopyableDeltaAware, but non-copyable DeltaAware breaks
transaction isolation (and listeners, and query), so we should require
all DeltaAwares to be copyable. (As a bridge, we can use
serialization+deserialization for those that are not.)

In theory, applyDelta() can also apply a delta without first issuing a
read for the key, e.g. a set of counters or the DeltaAwareList used by
our old M/R framework. I don't think we have any tests for this
scenario now, so I'd prohibit it explicitly.

> In any implementation of DeltaAwareCacheEntry.commit(), you'll have to
> atomically load the (Im)mutableCacheEntry from DC/cache store and store
> it into DC. Yes, you could do a load, copy (because the delta is
> modifying), apply delta/run WSC, compare&set in DC, but that's quite
> annoying loop implemented through exception handling <- I haven't
> proposed this and focused on changing the locking scheme.
>

I'm ok with doing the merge while holding the DC lock for fine-grained
DeltaAware, as we do now. For coarse-grained DeltaAware, we can keep
doing the merge in the context entry.

I'm not convinced we need new locking for the write-skew check in either case.

> [1]
> https://github.com/infinispan/jdg/blob/3aaa3d85fe9a90ee3c371b44ff5e5b36414c69fd/core/src/main/java/org/infinispan/container/entries/ReadCommittedEntry.java#L150
>
>>   But if a data structure is not suitable for
>> fine-grained locking, it should just use regular locking instead
>> (locksToAcquire = {mainKey}).
>>
>> E.g. any ordered structure is out of the question for fine-grained
>> locking, but it should be possible to implement a fine-grained set/bag
>> without any new locking in core.
>>
>> As you may have seen from ISPN-3123 and ISPN-5584, I think the problem
>> with FGAM is that it's not granular enough: we shouldn't throw
>> WriteSkewExceptions just because two transactions modify the same
>> FGAM, we should only throw the WriteSkewException when both
>> transaction modify the same subkey.
>
> You're right that WSC is not fine-grained enough, and at this point you
> can't solve that generally - how do you apply WSC on DeltaAware when you
> know that it locks certain keys? And you would add the static call to
> WSCHelper into DeltaAwareCacheEntry, class made for storing value &
> interacting with DC?
>

I'm not sure how we should do it, but we'd almost certainly need a new
kind of metadata that holds a map of subkeys to versions instead of a
single version.

I'd try to modify EntryWrappingInterceptor to add dummy
ClusteredRepeatableReadEntries in the context for all the
`locksToAcquire` composite keys during ApplyDeltaCommand. I think we
can add all the subkey versions to the transaction's versionsSeenMap
the moment we read the DeltaAware, and let the prepare perform the
regular WSC for those fake entries.

Of course, those fake entries couldn't load their version from the
data container/persistence, so we'd also have to move the version
loading to the EntryWrappingInterceptor, but I think you've already
started working on that.

Cheers
Dan
_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [infinispan-dev] Fine grained maps

Radim Vansa
On 09/28/2016 09:09 AM, Dan Berindei wrote:

> On Tue, Sep 27, 2016 at 6:15 PM, Radim Vansa <[hidden email]> wrote:
>> On 09/27/2016 04:47 PM, Dan Berindei wrote:
>>> On Tue, Sep 27, 2016 at 10:28 AM, Radim Vansa <[hidden email]> wrote:
>>>> To Pedro: I have figured out that it shouldn't work rather
>>>> theoretically, so I haven't crashed into ISPN-2729.
>>>>
>>>> On 09/26/2016 10:51 PM, Dan Berindei wrote:
>>>>> On Mon, Sep 26, 2016 at 10:36 AM, Radim Vansa <[hidden email]> wrote:
> ...
>>>>>> In pessimistic caches we have to be more cautious, since users
>>>>>> manipulate the locks directly and reason about them more. Therefore, we
>>>>>> need to lock the composite keys during transaction runtime, but in
>>>>>> addition to that, during the commit itself we should lock the main key
>>>>>> for the duration of the commit if necessary - pessimistic caches don't
>>>>>> sport WSC, but I was looking for some atomicity options for deltas.
>>>>>>
>>>>> -1 to implicitly locking the main key. If a DeltaAware implementation
>>>>> wants to support partial locking, then it should take care of the
>>>>> atomicity of the merge operation itself. If it doesn't want to support
>>>>> partial locking, then it shouldn't use AdvancedCache.applyDelta().
>>>>> It's a bit unfortunate that applyDelta() looks like a method that
>>>>> anyone can call, but it should only be called by the DeltaAware
>>>>> implementation itself.
>>>> As I have mentioned in my last mail, I found that it's not that easy, so
>>>> I am not implementing that. But it's not about taking care of atomicity
>>>> of the merge - applying merge can be synchronized, but you have to do
>>>> that with the entry stored in DC when the entry is about to be stored in
>>>> DC - and this is the only moment you can squeeze the WSC inl, because
>>>> the DeltaAware can't know anything about WSCs. That's the DC locking
>>>> piggyback you -10.
>>>>
>>> I think you're making it harder than it should be, because you're
>>> trying to come up with a generic solution that works with any possible
>>> data structure.
>> I am trying to work with two concepts: (Copyable)DeltaAware interface,
>> and ApplyDeltaCommand with its set of locks. Atomic maps are
>> higher-level concept and there should not be any Ugh!s [1].
>>
> We can't look at ApplyDeltaCommand in isolation, as the user of the
> data structure should never call applyDelta() directly. All DeltaAware
> structures should have a user-facing proxy that knows the internal
> structure and calls applyDelta(), following the rules that we set.
>
> The way I see it, these are the 2 low-level concepts, both using the
> DeltaAware interface:
>
> 1) Coarse-grained DeltaAware (high-level equivalent: AtomicMap).
> These use PutKeyValueCommand(with Flag.DELTA_WRITE set in the
> constructor), although I do have a stale branch trying to make them
> use ApplyDeltaCommand(locksToAcquire=null).
> These are merged in the invocation context, using only the regular locks.
>
> 2) Fine-grained DeltaAware (high-level equivalent: FineGrainedAtomicMap).
> These use use ApplyDeltaCommand(locksToAcquire=CompositeKey*) and
> DeltaAwareCacheEntry, and must be able to merge concurrent updates to
> separate subkeys without losing updates.
>
> Currently both types of data structures can implement either
> DeltaAware or CopyableDeltaAware, but non-copyable DeltaAware breaks
> transaction isolation (and listeners, and query), so we should require
> all DeltaAwares to be copyable. (As a bridge, we can use
> serialization+deserialization for those that are not.)
>
> In theory, applyDelta() can also apply a delta without first issuing a
> read for the key, e.g. a set of counters or the DeltaAwareList used by
> our old M/R framework. I don't think we have any tests for this
> scenario now, so I'd prohibit it explicitly.
>
>> In any implementation of DeltaAwareCacheEntry.commit(), you'll have to
>> atomically load the (Im)mutableCacheEntry from DC/cache store and store
>> it into DC. Yes, you could do a load, copy (because the delta is
>> modifying), apply delta/run WSC, compare&set in DC, but that's quite
>> annoying loop implemented through exception handling <- I haven't
>> proposed this and focused on changing the locking scheme.
>>
> I'm ok with doing the merge while holding the DC lock for fine-grained
> DeltaAware, as we do now. For coarse-grained DeltaAware, we can keep
> doing the merge in the context entry.
>
> I'm not convinced we need new locking for the write-skew check in either case.

"...doing the merge while holding DC lock..." means that it's already
second phase of 2PC. Therefore, if the WSC fails, you can't rollback the
transaction. Unless you want to do a RPC while holding DC lock.

Btw., I guess that you don't have any motivation to move persistence
loading from ClusteredRepeatableReadEntry to persistence-related
interceptors?

>> [1]
>> https://github.com/infinispan/jdg/blob/3aaa3d85fe9a90ee3c371b44ff5e5b36414c69fd/core/src/main/java/org/infinispan/container/entries/ReadCommittedEntry.java#L150
>>
>>>    But if a data structure is not suitable for
>>> fine-grained locking, it should just use regular locking instead
>>> (locksToAcquire = {mainKey}).
>>>
>>> E.g. any ordered structure is out of the question for fine-grained
>>> locking, but it should be possible to implement a fine-grained set/bag
>>> without any new locking in core.
>>>
>>> As you may have seen from ISPN-3123 and ISPN-5584, I think the problem
>>> with FGAM is that it's not granular enough: we shouldn't throw
>>> WriteSkewExceptions just because two transactions modify the same
>>> FGAM, we should only throw the WriteSkewException when both
>>> transaction modify the same subkey.
>> You're right that WSC is not fine-grained enough, and at this point you
>> can't solve that generally - how do you apply WSC on DeltaAware when you
>> know that it locks certain keys? And you would add the static call to
>> WSCHelper into DeltaAwareCacheEntry, class made for storing value &
>> interacting with DC?
>>
> I'm not sure how we should do it, but we'd almost certainly need a new
> kind of metadata that holds a map of subkeys to versions instead of a
> single version.
>
> I'd try to modify EntryWrappingInterceptor to add dummy
> ClusteredRepeatableReadEntries in the context for all the
> `locksToAcquire` composite keys during ApplyDeltaCommand. I think we
> can add all the subkey versions to the transaction's versionsSeenMap
> the moment we read the DeltaAware, and let the prepare perform the
> regular WSC for those fake entries.

It's not limited to ApplyDeltaCommand - this command should modify the
metadata, adding the subkeys, but you have to record the versions seen
upon first read (e.g. Get*). But ok, you can check the subkeys in the
metadata. You also have to deal with non-existent versions of subkeys
for existing keys later on as you don't know about subkeys added
concurrently.

>
> Of course, those fake entries couldn't load their version from the
> data container/persistence, so we'd also have to move the version
> loading to the EntryWrappingInterceptor, but I think you've already
> started working on that.

No; I've dropped my refactoring efforts for now, all what I've done is
in [1] - please review when time permits.

[1] https://github.com/infinispan/infinispan/pull/4564

Radim

>
> Cheers
> Dan
> _______________________________________________
> infinispan-dev mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/infinispan-dev


--
Radim Vansa <[hidden email]>
JBoss Performance Team

_______________________________________________
infinispan-dev mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/infinispan-dev
Loading...