Some other alternatives for detecting a split: - a hard-coded number of nodes required for a quorum configured by the customer. This is what we recommend for HASIngletons when the customer wants to guarantee that something is running at most once in the cluster.

- an alternative communication channel JBoss Messaging added this a year or two ago, where it uses a database in addition to JGroups to keep track of cluster membership and detect discrepencies between the two (I don't know all the details of the implementation)

- something in JGroups to notify Infinispan of the difference between a normal node leave and being kicked (easily detectable inside JGroups, but I don't think this is really exposed to apps?)

#1 should probably be pluggable, as a particular strategy may make sense for specific use cases. -Dennis On 04/05/2013 08:53 AM, Manik Surtani wrote: > Guys, > > So this is what I have in mind for this, looking for opinions. > > 1. We write a SplitBrainListener which is registered when the > channel connects. The aim of this listener is to identify when we > have a partition. This can be identified when a view change is > detected, and the new view is significantly smaller than the old > view. Easier to detect for large clusters, but smaller clusters > will be harder - trying to decide between a node leaving vs a > partition. (Any better ideas here?) > > 2. The SBL flips a switch in an interceptor > (SplitBrainHandlerInterceptor?) which switches the node to be > read-only (reject invocations that change the state of the local > node) if it is in the smaller partition (newView.size < > oldView.size / 2). Only works reliably for odd-numbered cluster > sizes, and the issues with small clusters seen in (1) will affect > here as well. > > 3. The SBL can flip the switch in the interceptor back to normal > operation once a MergeView is detected. > > It's no way near perfect but at least it means that we can > recommend enabling this and setting up an odd number of nodes, with > a cluster size of at least N if you want to reduce inconsistency in > your grid during partitions. > > Is this even useful? > > Bela, is there a more reliable mechanism to detect a split in (1)? > > Cheers Manik > > -- Manik Surtani manik(a)jboss.org twitter.com/maniksurtani > > Platform Architect, JBoss Data Grid http://red.ht/data-grid > > > _______________________________________________ infinispan-dev > mailing list infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

On 4/5/13 3:53 PM, Manik Surtani wrote: > Guys, > > So this is what I have in mind for this, looking for opinions. > > 1. We write a SplitBrainListener which is registered when the > channel connects. The aim of this listener is to identify when we > have a partition. This can be identified when a view change is > detected, and the new view is significantly smaller than the old > view. Easier to detect for large clusters, but smaller clusters will > be harder - trying to decide between a node leaving vs a partition. > (Any better ideas here?) > > 2. The SBL flips a switch in an interceptor > (SplitBrainHandlerInterceptor?) which switches the node to be > read-only (reject invocations that change the state of the local > node) if it is in the smaller partition (newView.size < oldView.size > / 2). Only works reliably for odd-numbered cluster sizes, and the > issues with small clusters seen in (1) will affect here as well. > > 3. The SBL can flip the switch in the interceptor back to normal > operation once a MergeView is detected. > > It's no way near perfect but at least it means that we can recommend > enabling this and setting up an odd number of nodes, with a cluster > size of at least N if you want to reduce inconsistency in your grid > during partitions. > > Is this even useful? So I assume this is to shut down (or make read-only) non primary partitions. I'd go with an approach similar to [1] section 5.6.2, which makes a partition read-only once it drops below a certain number of nodes N. > Bela, is there a more reliable mechanism to detect a split in (1)? I'm afraid no. We never know whether a large number of members being removed from the view means that they left, or that we have a partition, e.g. because a switch crashed. One thing you could do though is for members who are about to leave regularly to broadcast a LEAVE messages, so that when the view is received, the SBL knows those members, and might be able to determine better whether we have a partition, or not. [1] http://www.jgroups.org/manual-3.x/html/user-advanced.html, section 5.6.2 -- Bela Ban, JGroups lead (http://www.jgroups.org) _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

Well, first of all, we won't *have* any conflicting topology IDs, as the minority partitions don't change them after becoming minority.

Secondly, we can end up with the coordinator of a minority partition becoming the coordinator of the new merged partition, so we shouldn't rely on that (but I don't think we do so anyway?).

On a merge, everyone knows whether it came from a minority or majority partition, and the algorithm for state transfer should always clear the state in members in the minority partition and overwrite it from members of the primary partition.

On 4/17/13 10:58 AM, Radim Vansa wrote: > And the nice behaviour is that if we have partitions P1 and P2 with latest common topology 20 , when P2 increased it's topology to, say 40, while P1 only to 30, when a new coordinator from P1 will be elected it will try to compare these topology ids directly (assuming which one is newer or older) which won't end up well. > > Radim > > ----- Original Message ----- > | From: "Adrian Nistor" <anistor(a)redhat.com&gt; > | To: "infinispan -Dev List" <infinispan-dev(a)lists.jboss.org&gt; > | Cc: "Manik Surtani" <msurtani(a)redhat.com&gt; > | Sent: Wednesday, April 17, 2013 10:31:39 AM > | Subject: Re: [infinispan-dev] ISPN-263 and handling partitions > | > | In case of MergeView the cluster topology manager running on (the new) > | coordinator will request the current cache topology from all members and > | will compute a new topology as the union of all. The new topology id is > | computed as the max + 2 of the existing topology ids. Any currently > | pending rebalance in any subpartition is ended now and a new rebalance > | is triggered for the new cluster. No data version conflict resolution is > | performed => chaos :) > | > | On 04/16/2013 10:05 PM, Manik Surtani wrote: > | > Guys - I've started documenting this here [1] and will put together a > | > prototype this week. > | > > | > One question though, perhaps one for Dan/Adrian - is there any special > | > handling for state transfer if a MergeView is detected? > | > > | > - M > | > > | > [1] https://community.jboss.org/wiki/DesignDealingWithNetworkPartitions > | > > | > On 6 Apr 2013, at 04:26, Bela Ban <bban(a)redhat.com&gt; wrote: > | > > | >> > | >> On 4/5/13 3:53 PM, Manik Surtani wrote: > | >>> Guys, > | >>> > | >>> So this is what I have in mind for this, looking for opinions. > | >>> > | >>> 1. We write a SplitBrainListener which is registered when the > | >>> channel connects. The aim of this listener is to identify when we > | >>> have a partition. This can be identified when a view change is > | >>> detected, and the new view is significantly smaller than the old > | >>> view. Easier to detect for large clusters, but smaller clusters will > | >>> be harder - trying to decide between a node leaving vs a partition. > | >>> (Any better ideas here?) > | >>> > | >>> 2. The SBL flips a switch in an interceptor > | >>> (SplitBrainHandlerInterceptor?) which switches the node to be > | >>> read-only (reject invocations that change the state of the local > | >>> node) if it is in the smaller partition (newView.size < oldView.size > | >>> / 2). Only works reliably for odd-numbered cluster sizes, and the > | >>> issues with small clusters seen in (1) will affect here as well. > | >>> > | >>> 3. The SBL can flip the switch in the interceptor back to normal > | >>> operation once a MergeView is detected. > | >>> > | >>> It's no way near perfect but at least it means that we can recommend > | >>> enabling this and setting up an odd number of nodes, with a cluster > | >>> size of at least N if you want to reduce inconsistency in your grid > | >>> during partitions. > | >>> > | >>> Is this even useful? > | >> > | >> So I assume this is to shut down (or make read-only) non primary > | >> partitions. I'd go with an approach similar to [1] section 5.6.2, which > | >> makes a partition read-only once it drops below a certain number of nodes > | >> N. > | >> > | >> > | >>> Bela, is there a more reliable mechanism to detect a split in (1)? > | >> I'm afraid no. We never know whether a large number of members being > | >> removed from the view means that they left, or that we have a partition, > | >> e.g. because a switch crashed. > | >> > | >> One thing you could do though is for members who are about to leave > | >> regularly to broadcast a LEAVE messages, so that when the view is > | >> received, the SBL knows those members, and might be able to determine > | >> better whether we have a partition, or not. > | >> > | >> [1] http://www.jgroups.org/manual-3.x/html/user-advanced.html, section > | >> 5.6.2 > | >> > | >> -- > | >> Bela Ban, JGroups lead (http://www.jgroups.org) > | >> _______________________________________________ > | >> infinispan-dev mailing list > | >> infinispan-dev(a)lists.jboss.org > | >> https://lists.jboss.org/mailman/listinfo/infinispan-dev > | > -- > | > Manik Surtani > | > manik(a)jboss.org > | > twitter.com/maniksurtani > | > > | > Platform Architect, JBoss Data Grid > | > http://red.ht/data-grid > | > > | > > | > _______________________________________________ > | > infinispan-dev mailing list > | > infinispan-dev(a)lists.jboss.org > | > https://lists.jboss.org/mailman/listinfo/infinispan-dev > | > | _______________________________________________ > | infinispan-dev mailing list > | infinispan-dev(a)lists.jboss.org > | https://lists.jboss.org/mailman/listinfo/infinispan-dev > | > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev > -- Bela Ban, JGroups lead (http://www.jgroups.org) _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

On 17 Apr 2013, at 08:23, Dan Berindei <dan.berindei(a)gmail.com&gt; wrote: I like the idea of always clearing the state in members of the minority partition(s), but one problem with that is that there may be some keys that only had owners in the minority partition(s). If we wiped the state of the minority partition members, those keys would be lost. Right, this is my concern with such a wipe as well. Of course, you could argue that the cluster already lost those keys when we allowed the majority partition to continue working without having those keys... We could also rely on the topology information, and say that we only support partitioning when numOwners >= numSites (or numRacks, if there is only one site, or numMachines, if there is a single rack). This is only true for an embedded app. For an app communicating with the cluster over Hot Rod, this isn't the case as it could directly read from the minority partition.

transfer, in which each partition sends all the data it has to all the other partitions, and on the receiving end each node has a "conflict resolution" component that can merge two values. That is definitely more complicated than just going with a primary partition, though. That sounds massively expensive. I think the right solution at this point is entry versioning using vector clocks and the vector clocks are exchanged and compared during a merge. Not the entire dataset.

store, it is very much as if we had a merge view. The current approach is to join as if the node didn't have any data, then delete everything from the cache store that is not mapped to the node in the consistent hash. Obviously that can lead to consistency problems, just like our current merge algorithm. It would be nice if we could handle both these cases the same way. +1

I presume versioning (based on Vector Clocks) is now in master, as a part of Pedro's work on total order?

I like the idea of always clearing the state in members of the minority partition(s), but one problem with that is that there may be some keys that only had owners in the minority partition(s). If we wiped the state of the minority partition members, those keys would be lost.

Of course, you could argue that the cluster already lost those keys when we allowed the majority partition to continue working without having those keys... We could also rely on the topology information, and say that we only support partitioning when numOwners >= numSites (or numRacks, if there is only one site, or numMachines, if there is a single rack).

One other option is to perform a more complicated post-merge state transfer, in which each partition sends all the data it has to all the other partitions, and on the receiving end each node has a "conflict resolution" component that can merge two values. That is definitely more complicated than just going with a primary partition, though.

One final point... when a node comes back online and it has a local cache store, it is very much as if we had a merge view. The current approach is to join as if the node didn't have any data, then delete everything from the cache store that is not mapped to the node in the consistent hash.

Obviously that can lead to consistency problems, just like our current merge algorithm. It would be nice if we could handle both these cases the same way.

If we go with a primary partition approach, then only the primary partition will be allowed to make progress (a.k.a. accept changes), we therefore won't have any conflicts. The partition approach must be chosen so there can only be 1 primary partition max, and the minority partitions shut down or turn read-only. When merging, minority partitions need to get the state from the primary partition, so state transfer on a merge always needs to flow from the primary partition to the minority partition(s).

I don't know how this could be done, but perhaps an approach would be to treat members of minority partitions on a merge as if they were fresh joiners ? On 4/17/13 10:31 AM, Adrian Nistor wrote: > In case of MergeView the cluster topology manager running on (the new) > coordinator will request the current cache topology from all members and > will compute a new topology as the union of all. The new topology id is > computed as the max + 2 of the existing topology ids. Any currently > pending rebalance in any subpartition is ended now and a new rebalance > is triggered for the new cluster. No data version conflict resolution is > performed => chaos :) > > On 04/16/2013 10:05 PM, Manik Surtani wrote: >> Guys - I've started documenting this here [1] and will put together a prototype this week. >> >> One question though, perhaps one for Dan/Adrian - is there any special handling for state transfer if a MergeView is detected? >> >> - M >> >> [1] https://community.jboss.org/wiki/DesignDealingWithNetworkPartitions >> >> On 6 Apr 2013, at 04:26, Bela Ban <bban(a)redhat.com&gt; wrote: >> >>> >>> On 4/5/13 3:53 PM, Manik Surtani wrote: >>>> Guys, >>>> >>>> So this is what I have in mind for this, looking for opinions. >>>> >>>> 1. We write a SplitBrainListener which is registered when the >>>> channel connects. The aim of this listener is to identify when we >>>> have a partition. This can be identified when a view change is >>>> detected, and the new view is significantly smaller than the old >>>> view. Easier to detect for large clusters, but smaller clusters will >>>> be harder - trying to decide between a node leaving vs a partition. >>>> (Any better ideas here?) >>>> >>>> 2. The SBL flips a switch in an interceptor >>>> (SplitBrainHandlerInterceptor?) which switches the node to be >>>> read-only (reject invocations that change the state of the local >>>> node) if it is in the smaller partition (newView.size < oldView.size >>>> / 2). Only works reliably for odd-numbered cluster sizes, and the >>>> issues with small clusters seen in (1) will affect here as well. >>>> >>>> 3. The SBL can flip the switch in the interceptor back to normal >>>> operation once a MergeView is detected. >>>> >>>> It's no way near perfect but at least it means that we can recommend >>>> enabling this and setting up an odd number of nodes, with a cluster >>>> size of at least N if you want to reduce inconsistency in your grid >>>> during partitions. >>>> >>>> Is this even useful? >>> >>> So I assume this is to shut down (or make read-only) non primary >>> partitions. I'd go with an approach similar to [1] section 5.6.2, which >>> makes a partition read-only once it drops below a certain number of nodes N. >>> >>> >>>> Bela, is there a more reliable mechanism to detect a split in (1)? >>> I'm afraid no. We never know whether a large number of members being >>> removed from the view means that they left, or that we have a partition, >>> e.g. because a switch crashed. >>> >>> One thing you could do though is for members who are about to leave >>> regularly to broadcast a LEAVE messages, so that when the view is >>> received, the SBL knows those members, and might be able to determine >>> better whether we have a partition, or not. >>> >>> [1] http://www.jgroups.org/manual-3.x/html/user-advanced.html, section 5.6.2 >>> >>> -- >>> Bela Ban, JGroups lead (http://www.jgroups.org) >>> _______________________________________________ >>> infinispan-dev mailing list >>> infinispan-dev(a)lists.jboss.org >>> https://lists.jboss.org/mailman/listinfo/infinispan-dev >> -- >> Manik Surtani >> manik(a)jboss.org >> twitter.com/maniksurtani >> >> Platform Architect, JBoss Data Grid >> http://red.ht/data-grid >> >> >> _______________________________________________ >> infinispan-dev mailing list >> infinispan-dev(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/infinispan-dev > > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev > -- Bela Ban, JGroups lead (http://www.jgroups.org) _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

After think a bit about it, we can conclude that the behaviour when we have partition totally depends on the application. So, why not create an generic interface (like, execute(Operation, Key, isPrimaryPartition)) that is invoked when a partition occurs? Maybe I'm losing the focus of the first email, but this way the application can choose what it is better for it. For example, if the application does not care about consistency, it can allow all partitions to read and write. On other hand, if the application is more restrict, it can allow only one partition to read and write and the others partitions reject all the operations.

TBH I'm not understanding which problem this thread is about :) Surely network partitions are a problem, but there are many forms of "partition", and many different opinions of what an "acceptable" behaviour is that the grid should implement, which largely depend on assumptions the client application is making.

Since we seem to be discussing a case in which the minority group is expected to flip into read-only mode, could we step back and describe: - why this is an acceptable solution for some class of applications? - what kind of potential network failure we want to take compensating actions for?

I'm not an expert on how people physically wire up single nodes, racks and rooms to allow for our virtual connections, but let's assume that all nodes are connected with a single "cable" between each other, or if concrete multiple cables are actually used, could we rely on system configuration to guarantee packets can find alternative routes if one wire is eaten by mice?

It seems important to me to define what level of network failure we want to address, for example are we assuming we don't deal with cases in which nodes can talk to one group but not vice-versa?

If the effect of a nework failure is a completely isolated group, can we assume Hot Rod clients can't reach them either?

On 22 Apr 2013, at 14:47, Bela Ban <bban(a)redhat.com&gt; wrote: > > > On 4/19/13 11:51 AM, Sanne Grinovero wrote: >> TBH I'm not understanding which problem this thread is about :) >> >> Surely network partitions are a problem, but there are many forms of >> "partition", and many different opinions of what an "acceptable" >> behaviour is that the grid should implement, which largely depend on >> assumptions the client application is making. > > > This thread is not about providing different application data merge > policies, which is also something that needs to be done, but more likely > in the context of eventual consistency in Infinispan. This thread is > about a *primary partition* approach which says that only members in a > primary partition are allowed to make progress, and others aren't. > > 'No progress' needs to be defined, but so far I think we've agreed on a > notion of read-only members, which do provide access to data, but don't > allow modifications. One could also think about not even allowing reads > as the data might be stale. Perhaps this is configurable. +1 > The idea is that if only a primary partition can make progress, and only > *one* primary partitions exists in the system at any time, then we can > simply overwrite the data of minority partitions with data from the > primary partition on a merge. > > So a primary partition approach is not about how to merge (possibly > conflicting) data after a cluster split heals, but about how to > *prevent* conflicting data in the first place. > > If you think about this in CAP terminology, we sacrifice availability in > favor of consistency. Precisely. This would still follow the strongly consistent model.

On 24 Apr 2013, at 16:08, Mircea Markus <mmarkus(a)redhat.com&gt; wrote: > > On 22 Apr 2013, at 17:43, Manik Surtani wrote: > >> On 22 Apr 2013, at 14:47, Bela Ban <bban(a)redhat.com&gt; wrote: >> >>> >>> >>> On 4/19/13 11:51 AM, Sanne Grinovero wrote: >>>> TBH I'm not understanding which problem this thread is about :) >>>> >>>> Surely network partitions are a problem, but there are many forms of >>>> "partition", and many different opinions of what an "acceptable" >>>> behaviour is that the grid should implement, which largely depend on >>>> assumptions the client application is making. >>> >>> >>> This thread is not about providing different application data merge >>> policies, which is also something that needs to be done, but more likely >>> in the context of eventual consistency in Infinispan. This thread is >>> about a *primary partition* approach which says that only members in a >>> primary partition are allowed to make progress, and others aren't. >>> >>> 'No progress' needs to be defined, but so far I think we've agreed on a >>> notion of read-only members, which do provide access to data, but don't >>> allow modifications. One could also think about not even allowing reads >>> as the data might be stale. Perhaps this is configurable. >> >> +1 >> >>> The idea is that if only a primary partition can make progress, and only >>> *one* primary partitions exists in the system at any time, then we can >>> simply overwrite the data of minority partitions with data from the >>> primary partition on a merge. >>> >>> So a primary partition approach is not about how to merge (possibly >>> conflicting) data after a cluster split heals, but about how to >>> *prevent* conflicting data in the first place. >>> >>> If you think about this in CAP terminology, we sacrifice availability in >>> favor of consistency. >> >> Precisely. This would still follow the strongly consistent model. > I don't think consistency is preserved in at least the following situations: > - the read-only partition has more than numOwner members. Reads in the active partition would miss data. Also the conditional operation, that rely on existing data, perform incorrectly. Good point. > - data is deleted in the active partition but copies are kept in the read-only partition. > The 2nd problem can be solved with tombstones. The first problem cannot be solved and we can only target an eventual consistent cluster. That should be made very clear to the users. > > > Cheers, > -- > Mircea Markus > Infinispan lead (www.infinispan.org) > > > > > > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev -- Manik Surtani manik(a)jboss.org twitter.com/maniksurtani Platform Architect, JBoss Data Grid http://red.ht/data-grid _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

1. We write a SplitBrainListener which is registered when the channel connects. The aim of this listener is to identify when we have a partition. This can be identified when a view change is detected, and the new view is significantly smaller than the old view. Easier to detect for large clusters, but smaller clusters will be harder - trying to decide between a node leaving vs a partition. (Any better ideas here?) 2. The SBL flips a switch in an interceptor (SplitBrainHandlerInterceptor?) which switches the node to be read-only (reject invocations that change the state of the local node) if it is in the smaller partition (newView.size < oldView.size / 2). Only works reliably for odd-numbered cluster sizes, and the issues with small clusters seen in (1) will affect here as well. 3. The SBL can flip the switch in the interceptor back to normal operation once a MergeView is detected. It's no way near perfect but at least it means that we can recommend enabling this and setting up an odd number of nodes, with a cluster size of at least N if you want to reduce inconsistency in your grid during partitions.

On 22 Apr 2013, at 16:46, Mircea Markus <mmarkus(a)redhat.com&gt; wrote: > would the read only partition be wiped out and repopulated during > merge? Naively, yes. But as Dan pointed out, if a key K only exists in the minor partition (primary and backups), then just wiping the minor partition nodes will result in data loss. A more sophisticated algorithm would just wipe keys in the minor partition that also exist in the major partition.

An *even* more sophisticated algorithm would only wipe keys in the minor partition that also exist in the major partition, that have changed since the partition occurred. Hence the vector clocks.

On 23 Apr 2013, at 16:37, Bela Ban <bban(a)redhat.com&gt; wrote: > > > On 4/22/13 6:46 PM, Manik Surtani wrote: >> >> On 22 Apr 2013, at 16:46, Mircea Markus <mmarkus(a)redhat.com&gt; wrote: >> >>> would the read only partition be wiped out and repopulated during >>> merge? >> >> Naively, yes. But as Dan pointed out, if a key K only exists in the >> minor partition (primary and backups), then just wiping the minor >> partition nodes will result in data loss. >> >> A more sophisticated algorithm would just wipe keys in the minor >> partition that also exist in the major partition. > > > I think this would be good enough for a lot of scenarios. > > >> An *even* more sophisticated algorithm would only wipe keys in the >> minor partition that also exist in the major partition, that have >> changed since the partition occurred. Hence the vector clocks. > > Even better. What would you do in a conflict case ? Throw the conflict > at the user who has to resolve it ? Always prefer the data from the > primary partition ? Why would a conflict happen? Only the primary partition is allowed to update data after a split. - M -- Manik Surtani manik(a)jboss.org twitter.com/maniksurtani Platform Architect, JBoss Data Grid http://red.ht/data-grid _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev