Hi Galder First of all, thanks for reading! On Mar 9, 2012 12:54 PM, "Galder Zamarreño" <galder(a)redhat.com&gt; wrote: happened? Exactly, it's when there is no state transfer in progress. no-longer-owners as requestors for the transferred keys". Do we really need L1OnRehash? What's the use case/motivation for this option? If we have a put on a new owner, it must know to invalidate the key both on the nodes that read it after the CH change and the ones that read before the CH change (from an old owner). It will become critical once we start staggering clustered get commands. The L1OnRehash requirement is a bit different, because the old owner wasn't on any requestor list before the ownership change. But the solution is the same. a cache store by default? Would that help? I think a cache store would slow things too much, but it would solve this. it have on memory consumption? It's not really a snapshot, I just called it a snapshot to convey the idea that the (Bounded)ConcurrentHashMap doesn't pick up all the changes made after the start of the iteration. fully understand. I think it would really help to build some diagrams explaining some of the process to help the community understand better your design, or alternative solutions. WDYT? Fair point. I focused more on keeping track of required code changes to make sure I don't miss anything, but that ended up being even more dense so I removed it from the wiki. Any particular diagram requests, to help prioritize things? Cheers Dan > Cheers, > On Mar 8, 2012, at 10:55 AM, Dan Berindei wrote: > > Hi guys > > > It's been a long time coming, but I finally published the non-blocking > > state transfer draft on the wiki: > > https://community.jboss.org/wiki/Non-blockingStateTransfer > > > Unlike my previous state transfer design document, I think I've > > fleshed out most of the implications. Still, there are some things I > > don't have a clear solution for yet. As you would expect it's mostly > > around merging and delayed state transfer. > > > I'm looking forward to hearing your comments/advice! > > > Cheers > > Dan > > > PS: Let's discuss this over the mailing list only. > > _______________________________________________ > > infinispan-dev mailing list > > infinispan-dev(a)lists.jboss.org > > https://lists.jboss.org/mailman/listinfo/infinispan-dev > -- > Galder Zamarreño > Sr. Software Engineer > Infinispan, JBoss Cache > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev

Wow ! Does this need to be so complex ? I've spent a hour trying to understand it, and am still overwhelmed... :-) My understanding (based on my changed in 4.2) is that state transfer moves/deletes keys based on the diff between 2 subsequent views: - Each node checks all of the affected keys - If a key should be stored in additional nodes, the key is pushed there - If a key shouldn't be stored locally anymore, it is removed IMO, there's no need to handle a merge differently from a regular view, and we might end up with inconsistent state, but that's unavoidable until we have eventual consistency. Fine... Also, why do we need to transfer ownership information ? Can't ownership be calculated purely on local information ? I'm afraid that the complexity will increase the state space (hard to test all possible state transitions), lead to unnecessary messages being sent and most importantly, might lead to blocks. The section on locking outright scares me :-) Perhaps reducing the level of details here - as Galder suggested - might help to understand the basic design. Sorry for being a bit negative, but I think state transfer is one of the most critical and important pieces of code in DIST mode, and this needs to work against large (say a couple of hundreds) clusters and nodes joining, leaving or crashing all the times... I'm going to re-read the design again, maybe what I said above is just BS ... :-) On 3/8/12 11:55 AM, Dan Berindei wrote: -- Bela Ban, JGroups lead (http://www.jgroups.org)

On Fri, Mar 9, 2012 at 6:03 PM, Sanne Grinovero <sanne(a)infinispan.org&gt; wrote: I thought I just did that with the different sections :) All the state transfer components are bound together by the approach we choose for updating the CH, so and I think most of the complications stem from the way we have to maintain ownership information - not just for the current cache view, but for the previous cache views as well. I thought it was the same thing, but in London we only had a very high-level discussion. We didn't discuss how a joiner gets the chain of CHs so that it knows which are the old owners, and we only briefly touched on how to discard old cache views. Please let me know where you think I've diverged from our discussions :) We do need to decide whether we want to allow CH updates without transferring the actual data or not - it has an impact on how big the "transaction log" on the new owners can get. We also need to decide whether we allow state transfer to finish successfully even though one node has already left the cache view. I've chosen to "interrupt" the state transfer on a leave in order to avoid weird situations where DM.getLocation(key) returns an empty set, but that complicates things a bit so we need to make it explicit here. E.g. after an error we can't just retry the same cache view, we have to account for leavers as well, so we can't say that a merge can only be the last view in the chain). We have to iterate over the data container in order to push data, and that iterator behaves as a snapshot. So there's nothing to avoid here. I did mention that we start refusing write commands - the iteration of the data container is the reason why we need the cache view id check. I'm not sure how this "authoritative invalidation" would work... any change to the data container may or may be reflected in the iteration done by the state transfer task, and actually by the time we send the invalidation command the entry could in fact be in a JGroups message on its way to the new owner. Actually no, we only keep the lock on the primary owner so we can't rely on the lock information being there in case of a leave. So we need to transfer transaction information instead - and the transaction information only gives a "possibly locked" status for a key. Even if we do treat the transaction information as the normal state, it doesn't mean that we don't have to handle it - in fact I wrote this idea and marked it [LATER] because I thought it would be too complicated to duplicate the data infrastructure for transaction information. Agree, it's simpler to flush everything out - but that doesn't mean we don't have to change anything, we still need to add the old owners as requestors if L1OnRehash is enabled. I could move out the fact that it's a current bug, but it's still something we need to do during state transfer and we have to decide what locks/latches we need to hold while doing it in order to ensure consistency. As I wrote the document I wasn't quite sure that the tree approach would work, but I'm more and more convinced that it would be fine. I agree that it sounds a little more complicated because I wrote it at first considering a list of cache views and I only started considering the generic tree approach when I wrote the merge section. But I couldn't change it as I wasn't 100% sold on the tree approach (another idea I had was to ignore any view change after a merge, so the cache view tree could only have more than 1 branch at the root level), so I try to leave the option open hoping for better suggestions from you guys. I don't want to solve consistent merging here, but I do want to make sure that it is possible. For instance if after a failed merge the information about the old partitions is lost, no "ConflictResolver object" could make that state consistent and state will be just lost. The long discussion about which view is newer is there because without merges we want to ensure consistency and apply received entries in their logical order (which happens the ascending order of their cache view id) - therefore we need to buffer data received for "intermediate" nodes in the cache view chain. Merges complicate this because the cache view tree has multiple leaves and we have no way of ordering them (unlike JGroups we identify a cache view only by its id, so there's no way compare cache views and decide one is a descendent of another - hence the need for the intermediate flag. The main use case I have in mind is when the user doesn't care about missing data (we're not the authoritative source) but he does care about staleness. Most users I talked with (not many, I grant you that) are willing to accept stale data but on very short timescales. L1, with its 10 minutes default lifespan, doesn't qualify - and making the L1 lifespan very short will make it useless. Agree with both ;-) Cheers Dan

Sorry for the delay, been busy ... Comments inline. On 3/9/12 7:20 PM, Dan Berindei wrote: OK Why do we have to lock at all if we use queueing of requests during a state transfer ? I didn't imply that; but I thought the London design was pretty simple, and I'm trying to figure out why we have such a big (maybe perceived) diff between London and what's in the document. OK Can't we queue the state transfer requests *and* the regular requests ? When ST is done, we apply the ST requests first, then the queued regular requests. -- Bela Ban, JGroups lead (http://www.jgroups.org)

Hi Dan, This statement makes me nervous. Would we still have inconsistencies in a transactional context as well? "We didn't discuss this in London, I added it afterwards as I realized that without forwarding we'll be losing data. I didn't realize at the time, however, that the current design has the same problem. I think I see a problem with my request forwarding plan: the requests will have a different source, so JGroups will not ensure an ordering between them and the originator's subsequent requests. This means we'll have inconsistencies anyway, so perhaps it would be better if we stuck to the current design's limitations and remove the requirement for old targets to forward commands to new ones." Regards, Erik

On 3/15/12 11:29 AM, Dan Berindei wrote: OK. I don't like the old design, as ST has to wait until all pending TXs (those with locks held) have to commit before we can make progress. If the lock acquition timeout is high, we'll have to wait for a long time. OK. Perhaps an overview of the new design in the document is warranted. There's a section on transfer of CacheEntries and one on locks, but I didn't see a combined discussion. Perhaps an example like the one above would be good ? I now realize how much simpler the use of total order is here: since all updates in a cluster happen in total order, we don't need to acquire locks in 1 phase and release them in another phase. ST is then just another update, inserted at a certain place in the stream of updates. I assume the Cloud-TM guys don't do state transfer in their prototype, or do they ? Pedro ? If not, then there needs to be an implementation of ST for TO. Cheers, -- Bela Ban, JGroups lead (http://www.jgroups.org)

Thanks Dan, here are some comments / questions: "2. Each cache member receives the ownership information from the coordinator and starts rejecting all commands started in the old cache view" How do you know a command was started in the old cache view; does this mean you're shipping a cache view ID with every request ? "2.1. Commands with the new cache view id will be blocked until we have installed the new CH and we have received lock information from the previous owners" Doesn't this make this design *blocking* again ? Or do you queue requests with the new view-ID, return immediately and apply them when the new view-id is installed ? If the latter is the case, what do you return ? An OK (how do you know the request will apply OK) ? "A merge can be coalesced with multiple state transfers, one running in each partition. So in the general case a coalesced state transfer contain a tree of cache view changes." Hmm, this can make a state transfer message quite large. Are we trimming the modification list ? E.g if we have 10 PUTs on K, 1 removal of K, and another 4 PUTs, do we just send the *last* PUT, or do we send a modification list of 15 ? "Get commands can write to the data container as well when L1 is enabled, so we can't block just write commands." Another downside of the L1 cache being part of the regular cache. IMO it would be much better to separate the 2, as I wrote in previous emails yesterday. "The new owners will start receiving commands before they have received all the state * In order to handle those commands, the new owners will have to get the values from the old owners * We know that the owners in the later views have a newer version of the entry (if they have it at all). So we need to go back on the cache views tree and ask all the nodes on one level at the same time - if we don't get any certain anwer we go to the next level and repeat." How does a member C know that it *will* receive any state at all ? E.g. if we had key K on A and B, and now B crashed, then A would push a copy of K to C. So when C receives a request R from another member E, but hasn't received a state transfer from A yet, how does it know whether to apply or queue R ? Does C wait until it get an END-OF-ST message from the coordinator ? (skipping the rest due to exhaustion by complexity :-)) Over the last couple of days, I've exchanged a couple of emails with the Cloud-TM guys, and I'm more and more convinced that their total order solution is the simpler approach to (1) transactional updates and (2) state transfer. They don't have a solution for (2) yet, but I believe this can be done as another totally ordered transaction, applied in the correct location within the update stream. Or, we could possibly use a flush: as we don't need to wait for pending TXs to complete and release their locks, this should be quite fast. So my 5 cents: #1 We should focus on the total order approach, and get rid of the 2PC and locking business for transactional updates #2 Really focus on the eventual consistency approach Thoughts ? -- Bela Ban, JGroups lead (http://www.jgroups.org)

Thanks for the feedback and clarifications Dan ! Comments inline... We're discussing 2 scenarios, one being the use of flush (but short-lived as we don't have any locks in play) and the other being Pedro's proposal of a start-state TO-cast (shipped with a keys set), followed by a state transfer. Transactions with any keys in the key set are queued and applied in order after the state transfer is done (signalled with abother stop-state TO-cast). If you have anything to add, let's discuss it on the other thread. No, I don't think that's addressed by TOM, good point in favor of having 2 (or more) approaches to partial replication and state transfer ! I think a lot of systems would still benefit from TOM though as there are no external participants, for instance session replication: it uses an Infinispan batch to ship session updates to the session owners, and there are no other participants (as a matter of fact, this is not even a JTA transaction anyway). True :-) True again... Yep - Manik, do you have any status update on eventual consistency ? -- Bela Ban, JGroups lead (http://www.jgroups.org)

Hi, Comments inline. Cheers, Pedro Paolo Romano wrote: The TOB code can be found here [1]. In TransactionCoordinator, it checks if it uses 1 phase or 2 phases. Of course, like Paolo said, it only works for TOB. In TOM, we must have the 2 phases (with write skew check enabled). [1] https://github.com/pruivo/infinispan/tree/t_to_pedro

On Tue, Mar 20, 2012 at 2:51 PM, Mircea Markus <mircea.markus(a)jboss.com&gt; wrote: Yes, actually I'm trying to describe precisely that. Of course, there are some complications... Not necessarily: if the user has a TopologyAwareConsistentHash and has split his cluster in two "sites" or "racks", he can bring down an entire site/rack before rebalancing, without the risk of losing any data. I don't agree about the shared cache store, because then every cache transaction would have to write to that store. I think that would be cost-prohibitive. Ok, first of all, in the new draft merged the data container lock and the cache view lock, I don't think making them separate actually helped with anything but it made things harder to explain. The idea was that incoming writes would only block while state transfer gets the iterator to the data container, which is very short. But the state transfer will also block on all the writes to the data container - to make sure that we won't miss any writes. The algorithm is like this: Write command === 1. acquire read lock 2. check cache view id 3. write entry to data container 4. release read lock State Transfer === 1. acquire write lock 2. update ch 3. update cache view id 4. release read lock Because the local cache doesn't listen for join and leave requests, only the coordinator does, and the cache view is computed based on the requests that the coordinator has seen (and not on the JGroups cluster joins and leaves). Cheers Dan