[infinispan-dev] L1 Consistency with Sync Caches

Dan Berindei dan.berindei at gmail.com
Fri Jun 28 05:53:50 EDT 2013 

On Fri, Jun 28, 2013 at 12:51 AM, William Burns <mudokonman at gmail.com>wrote:

> On Thu, Jun 27, 2013 at 4:40 PM, Dan Berindei <dan.berindei at gmail.com>
> wrote:
> >
> >
> > On Thu, Jun 27, 2013 at 4:40 PM, William Burns <mudokonman at gmail.com>
> wrote:
> >>
> >> Comments that were outstanding on PR:
> >>
> >> @danberindei:
> >>
> >>  > +1 to move the discussion to the mailing list, could you summarize
> >> your changes (preferably for both non-tx and tx cases) and send an
> >> email to the list?
> >>  > And now to add some more to this already unwieldy discussion :)
> >>
> >>  >  1. Many interceptors check ownership, I don't think that would be
> >> a problem. Besides, I think creating a new L1ReadSynchronizer for
> >> every read is just as bad for performance as locking the key on every
> >> read, so you'd need that check either way.
> >> >
> >> We can't use a try lock approach for L1 invalidation when gets are
> >> locked without possibly dropping a L1 update
> >> We can't use a timed lock approach for L1 invalidation when writes
> >> lock the key as we could get into a timed deadlock situation when
> >> another node concurrently writes to a value/stripe
> >>
> >> I still don't see how we can get away with locking on a get.  What are
> >> you proposing?
> >
> >
> > I'm proposing something like this:
> >
> > 1. For get commands: acquire local lock + remote get + store in L1 +
> release
> > local lock
> > 2. For invalidate commands: acquire local lock + remove entry from L1 +
> > release local lock
> > 3. For write commands: invoke on primary owner, and the primary owner
> sends
> > invalidation back to originator; alternatively, skip the invalidation
> > command to the originator and do invoke on primary owner + acquire local
> > lock + remove entry from L1 + release local lock
>
> I do like this and think it would be simpler for non-tx.  However this
> will still not be as performant I wouldn't think (just a gut feeling).
>

It would indeed be less performant in some cases, e.g. if we have two get
commands for a remote key at the same time and the key doesn't exist, my
proposal would request the key twice.

The writes to L1 *should* be rare enough that the extra lock contention
there would be minimal. There is a chance that an invalidation will be
stuck waiting for a remote get, so it will again be slower than your
approach.

 However I am more than certain it will be slower when collisions
> occur, which is more likely with lock striping.
>
>
I'm not that worried about lock striping - the user can always increase the
number of stripes to get less contention. And I hope they know better than
to use lock striping and transactions with multiple keys, or they'll get
deadlocks with or without L1 enabled.


> I don't think this however is feasible for tx caches.
>
> Optimistic - we don't want to have gets being blocked when the tx is
> being committed - that could be quite a bit of a performance hit
> especially if it has to do a 2 phase commit.  Updating the L1 on a
> remoteGetBeforeWrites  could help remedy this (since get wouldn't need
> to lock), however then you would be almost implementing what I have
> and still have locking overhead.  Maybe this would occur so
> infrequently it wouldn't matter though?
>
>
Yes, I would propose removing the L1 commit in EntryWrappingInterceptor as
well, and moving it to the L1 interceptor - immediately after the value was
retrieved from the remote owner. The local lock would also be released
immediately.

The part I wanted to avoid from your proposal was
L1ReadSync/L1ReadSynchronizer, because I found it kind of hard to
understand. I guess I'd find it more approachable all the synchronization
(the map of L1ReadSynchronizers and the interaction with it) would be in a
separate class, with its own tests, and the L1 interceptor would only know
about the high-level stuff. Like the LockManager also hides a map of locks;
not like the LockManager unit tests, because they're kind of lacking, but
LockManager has the advantage that almost all the tests touch it indirectly.


> Pessimistic - I haven't looked into pessimistic closely yet, but in
> that case I don't think it ever acquires the local locks so it would
> have to acquire a remote lock on a get, which would be pretty
> disastrous (gets would indirectly have a weak FORCE_WRITE_LOCK
> enabled).  Making this to acquire local locks might work as well, but
> then would still have the same issue as optimistic when committing - I
> really am not as familiar with Pessimistic to say for sure.
>
>
Nope, acquiring a local lock should be enough. We don't want to prevent
other txs from modifying the key at all, we just want to delay the
invalidation commands triggered by those modifications on the local node.
And the lock would only be held for the duration of the remote get + L1
update, not all the way to the commit.


> >
> > All the lock acquisitions would use a regular timeout, not a try lock
> > approach.
> In this case they could, yes.
> >
> >>
> >> >   2. By default L1 invalidations are sent as multicasts, so I'm not
> sure
> >> > ISPN-3273 really matters here. BTW, I wonder if we have a check to
> only send
> >> > L1 invalidations from one node if the threshold is 0...
> >> I agree that is the default, but we should support the operation,
> >> although it doesn't matter for this discussion.  Also I am curious as
> >> to why multicast for L1 isn't set to say 2 by default?  It seems
> >> wasteful to send a multicast to all members that they process when
> >> only 1 would do anything about it.  Do you know why this is like that?
> >
> >
> > I suppose it's because we don't have good perf numbers for different L1
> > invalidation threshold numbers...
> >
> > The problem is, we don't have a way to count all the requestors of a key
> in
> > the cluster, so it's reasonably likely that with a threshold of 2 you'd
> get
> > 1 unicast invalidation from one owner + 1 multicast invalidation from the
> > other owner, making it less efficient than a single multicast
> invalidation.
>
> It is a nitpick anyways, and really shouldn't make that big of a
> difference.
>
>
>
> >> >
> >> >  3a. Right, for put commands we can't hold the local lock while
> >> > executing the remote put, or we'll have a deadlock. But I think a
> shorter
> >> > lock, held only after the remote put completed (or after the lock on
> the
> >> > primary owner was acquired, with txs) should work.
> >> Same point under 1
> >
> >
> > I don't see how we could get a deadlock if we don't hold the local lock
> > during the remote write invocation.
>
> Agree.
>
> >
> >>
> >> >
> >> >  3b. We'd also have an ownership check before, so we'd only serialize
> >> > the get commands that need to go remotely for the same key. I think
> it would
> >> > be almost the same as your solution (although it does have one ?
> >> > disadvantage - if the key doesn't exist in the cache, all the get
> commands
> >> > will go remotely). The number of L1 writes should be very small
> compared to
> >> > the number of L1 reads anyway, otherwise it would be more efficient
> to get
> >> > the key from the owner every time.
> >> You are saying an optimization for owner nodes so they don't do the
> >> "corralling" for keys they own?  I like that.  Also I don't think it
> >> has the disadvantage, it only does remotes it if isn't an owner.
> >
> >
> > I meant your corralling strategy means if you have 2 concurrent get
> commands
> > and one of them retrieves a null from the entry owners, the other command
> > will return null directly. With regular locking, the other command
> wouldn't
> > find anything in L1 and it would do another remote get.
> >
> > I don't think there's any disadvantage in skipping the corralling for key
> > owners, in fact I think we need to skip it if the key already exists in
> L1,
> > too.
> +1
> >
> >>
> >> >
> >> > It would be nice to agree on what guarantees we want to provide for L1
> >> > invalidation in non-tx caches, I'm not sure if we can do anything to
> prevent
> >> > this scenario:
> >> Actually this scenario doesn't occur with non-tx since writes don't
> >> update the L1 with their value, they just invalidate.  Tx caches are
> >> fine with this because they acquire the primary owner lock for the
> >> duration of the write including the L1 update so you can't have this
> >> ordering.
> >
> >
> > Sounds good.
> >
> >>
> >> >
> >> > A initiates a put(k, v1) to the primary owner B
> >> > B performs the put(k, v1), invalidates every non-owner and returns
> >> > B performs another put(k, v2), invalidating every non-owner
> >> > A receives the result from B and puts k=v1 in its L1
> >>
> >> @pruivo:
> >>
> >> > The invalidation does not need to wait for the remote get. When you
> >> > receive an invalidation, you can mark the current remote get invalid.
> The
> >> > invalidation command can return immediately and the remote get can be
> >> > repeated. Also, it removes the key from data container (if exists)
> >> Dan hit it right in the head.  Unfortunately there is no guarantee the
> >> cancellation can work properly, so it is a best effort and if not wait
> >> until we know we will invalidate properly.
> >> > The writes can update the L1 through your L1Synchronized by adding a
> >> > simple method like updateL1(newValue). The blocking threads will
> return
> >> > immediately the new value and they don't need to wait for the reply.
> >> Non tx cache write operations aren't safe to update L1 with the value
> >> since they don't acquire the owning lock while updating the L1, which
> >> means you could have interleaved writes.  Which is the primary reason
> >> I rejected ISPN- 3214.  For tx caches we can't do this since the
> >> update has to take part of the tx, which the get would be updating the
> >> L1 outside of a transaction.
> >> > I see... However, I think that all the events should synchronize at
> some
> >> > point (update by remote get, update by local put and invalidation).
> >> I was hoping that would cover this.  Other than the outstanding issue
> >> in ISPN-2965.
> >>
> >> On Thu, Jun 27, 2013 at 9:18 AM, William Burns <mudokonman at gmail.com>
> >> wrote:
> >> > First off I apologize for the length.
> >> >
> >> > There have been a few Jiras recently that have identified L1
> consistency
> >> > issues with both TX and non TX sync caches.  Async caches with L1 have
> >> > their
> >> > own issues as well, but I only wanted to talk about sync caches.
> >> >
> >> > https://issues.jboss.org/browse/ISPN-3197
> >> > https://issues.jboss.org/browse/ISPN-2965
> >> > https://issues.jboss.org/browse/ISPN-2990
> >> >
> >> > I have proposed a solution in
> >> > https://github.com/infinispan/infinispan/pull/1922 which should
> start L1
> >> > consistency down the right track.  There are quite a few comments on
> it
> >> > if
> >> > you want to look into it more, but because of that I am moving this to
> >> > the
> >> > dev mailing list.
> >> >
> >> > The key changes in the PR are the following (non-tx):
> >> >
> >> > 1. Concurrent reads for a key that can retrieve a remote value are
> >> > "corralled" into a single thread of execution for that given key.
>  This
> >> > would reduce network traffic with concurrent gets for the same key.
> >> > Note
> >> > the "corralling" only happens on a per key basis.
> >> > 2. The single thread that is doing the remote get would update the L1
> if
> >> > able (without locking) and make available the value to all the
> requests
> >> > waiting on the get.
> >> > 3. Invalidations that are received would first check to see if there
> is
> >> > a
> >> > current remote get occurring for it's keys.  If there is it will
> attempt
> >> > to
> >> > cancel the L1 write(s) before it occurs.  If it cannot cancel the L1
> >> > write,
> >> > then it must also wait on the current remote get completion and
> >> > subsequently
> >> > run the invalidation.  Note the cancellation would fail when the
> remote
> >> > get
> >> > was done and it is in the middle of updating the L1, so this would be
> >> > very
> >> > small window.
> >> > 4. Local writes will also do the same thing as the invalidation with
> >> > cancelling or waiting.  Note that non tx local writes only do L1
> >> > invalidations and don't write the value to the data container.
>  Reasons
> >> > why
> >> > I found at https://issues.jboss.org/browse/ISPN-3214
> >> > 5. Writes that require the previous value and don't have it in the L1
> >> > would
> >> > also do it's get operations using the same "corralling" method.
> >> >
> >> > 4/5 are not currently implemented in PR.
> >> >
> >> > This approach would use no locking for non tx caches for all L1
> >> > operations.
> >> > The synchronization point would be done through the "corralling"
> method
> >> > and
> >> > invalidations/writes communicating to it.
> >> >
> >> > Transactional caches would do almost the same thing as non-tx.  Note
> >> > these
> >> > changes are not done in any way yet.
> >> >
> >> > 1. Gets would now update the L1 immediately after retrieving the value
> >> > without locking, but still using the "corralling" technique that
> non-tx
> >> > does.  Previously the L1 update from a get was transactional.  This
> >> > actually
> >> > would remedy issue [1]
> >> > 2. Writes currently acquire the remote lock when committing, which is
> >> > why tx
> >> > caches are able to update the L1 with the value.  Writes would do the
> >> > same
> >> > cancellation/wait method as non-tx.
> >> > 3. Writes that require the previous value and don't have it in the L1
> >> > would
> >> > also do it's get operations using the same method.
> >> > 4. For tx cache [2] would also have to be done.
> >> >
> >> > [1] -
> >> >
> >> >
> https://issues.jboss.org/browse/ISPN-2965?focusedCommentId=12779780&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-12779780
> >> > [2] - https://issues.jboss.org/browse/ISPN-1540
> >> >
> >> > Also rehashing is another issue, but we should be able to acquire the
> >> > state
> >> > transfer lock before updating the L1 on a get, just like when an entry
> >> > is
> >> > committed to the data container.
> >> >
> >> > Any comments/concerns would be appreciated.
> >> >
> >> > Thanks,
> >> >
> >> >  - Will
> >>
> >> _______________________________________________
> >> infinispan-dev mailing list
> >> infinispan-dev at lists.jboss.org
> >> https://lists.jboss.org/mailman/listinfo/infinispan-dev
> >
> >
> >
> > _______________________________________________
> > infinispan-dev mailing list
> > infinispan-dev at lists.jboss.org
> > https://lists.jboss.org/mailman/listinfo/infinispan-dev
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/infinispan-dev/attachments/20130628/21c85502/attachment-0001.html

More information about the infinispan-dev mailing list