Re: [JBoss-dev] Partition merge and service state merge algorithm
Sacha Labourey wrote: Hello Bela, Yes, we need some kind of policy. But I thought about something a little bit different. In fact, there is already a way for services that have state to know about partition merging and plug into it. Instead I thought about a policy where you can receive events when you are no more on the good side (defined by the policy) of the network partition. This could be, for example, access to a common DB, some data in a common DB, the minimal size of the partition, etc. As long as the policy is not satisfied, the service would be in stand-by. You are talking about a primary-partition approach. The literature tells you to shut down members in a non-primary partitions. It is simple to implement, all right. But it reduces overall availability of a distributed system, that's why there are many approaches beyond primary partition in research. But regardless of whether we want to have progress or shutdown on a partition, we need to present to the user a choice. E.g. shut down, continue and merge later etc. This way we can implement both approaches. -- Bela Ban www.javagroups.com (408) 316-4459 --- This SF.net email is sponsored by: ValueWeb: Dedicated Hosting for just $79/mo with 500 GB of bandwidth! No other company gives more support or power for your dedicated server http://click.atdmt.com/AFF/go/sdnxxaff00300020aff/direct/01/ ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
RE: [JBoss-dev] Partition merge and service state merge algorithm
You are talking about a primary-partition approach. The literature tells you to shut down members in a non-primary partitions. It is simple to implement, all right. But it reduces overall availability of a distributed system, that's why there are many approaches beyond primary partition in research. But regardless of whether we want to have progress or shutdown on a partition, we need to present to the user a choice. E.g. shut down, continue and merge later etc. This way we can implement both approaches. Yes, I think we are speaking exactly about the same thing: pluggable policy to let the application/user choose which is best for its app and if the network partition is critical for him or not. The primiary partition was just an example. Cheers, sacha --- This SF.net email is sponsored by: ValueWeb: Dedicated Hosting for just $79/mo with 500 GB of bandwidth! No other company gives more support or power for your dedicated server http://click.atdmt.com/AFF/go/sdnxxaff00300020aff/direct/01/ ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
Re: [JBoss-dev] Partition merge and service state merge algorithm
David Klimek wrote: Hi Sacha, thank you very much for your comments. Now I believe I have quite clean picture of partition merge issues. Maybe the conditions and limitations you mentioned should be added to documentation as they are not obvious and there can be a lot of people living, as I did before, in paradise, where all the mess with state merging, is handled by clustering framework. Maybe we should come up with a conflict resolution policy, similar to the failover policy: the policy is user-defined and - whenever there is a merge - it is called with all substates. At this point it needs to implement the merge and update the local copy. For the state service we could for instance provide a simple default policy which applies the union of all states and sees this as the new state. The only requirement for such a policy is that it is deterministic. -- Bela Ban www.javagroups.com (408) 316-4459 --- This SF.net email is sponsored by: ValueWeb: Dedicated Hosting for just $79/mo with 500 GB of bandwidth! No other company gives more support or power for your dedicated server http://click.atdmt.com/AFF/go/sdnxxaff00300020aff/direct/01/ ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
RE: [JBoss-dev] Partition merge and service state merge algorithm
Hello Bela, Yes, we need some kind of policy. But I thought about something a little bit different. In fact, there is already a way for services that have state to know about partition merging and plug into it. Instead I thought about a policy where you can receive events when you are no more on the good side (defined by the policy) of the network partition. This could be, for example, access to a common DB, some data in a common DB, the minimal size of the partition, etc. As long as the policy is not satisfied, the service would be in stand-by. Cheers, sacha -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Bela Ban Sent: mardi, 1. avril 2003 02:31 To: [EMAIL PROTECTED] Subject: Re: [JBoss-dev] Partition merge and service state merge algorithm David Klimek wrote: Hi Sacha, thank you very much for your comments. Now I believe I have quite clean picture of partition merge issues. Maybe the conditions and limitations you mentioned should be added to documentation as they are not obvious and there can be a lot of people living, as I did before, in paradise, where all the mess with state merging, is handled by clustering framework. Maybe we should come up with a conflict resolution policy, similar to the failover policy: the policy is user-defined and - whenever there is a merge - it is called with all substates. At this point it needs to implement the merge and update the local copy. For the state service we could for instance provide a simple default policy which applies the union of all states and sees this as the new state. The only requirement for such a policy is that it is deterministic. -- Bela Ban www.javagroups.com (408) 316-4459 --- This SF.net email is sponsored by: ValueWeb: Dedicated Hosting for just $79/mo with 500 GB of bandwidth! No other company gives more support or power for your dedicated server http://click.atdmt.com/AFF/go/sdnxxaff00300020aff/direct/01/ ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development --- This SF.net email is sponsored by: ValueWeb: Dedicated Hosting for just $79/mo with 500 GB of bandwidth! No other company gives more support or power for your dedicated server http://click.atdmt.com/AFF/go/sdnxxaff00300020aff/direct/01/ ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
Re: [JBoss-dev] Partition merge and service state merge algorithm
Hi Sacha, thank you very much for your comments. Now I believe I have quite clean picture of partition merge issues. Maybe the conditions and limitations you mentioned should be added to documentation as they are not obvious and there can be a lot of people living, as I did before, in paradise, where all the mess with state merging, is handled by clustering framework. Greet's David Sacha Labourey wrote: Maybe that's one of the points. As I understand partion split each groups things that all nodes in other group are down, but they are not so there is not chance how to avoid concurrent access. Yes. But solutions may be found, such as using a central DB as a way to decide who is up/down. Anyway the same problem can occur in DistributedState service from JBoss Clustering framework, where no such limitaton is explicitly given by spec. Yes, this must be added for generic use. But let's finish our SFSB discussion first as it is a little bit different. Furthermore, even in the strange scenario you describe (concurrent access to a same SFSB), the merge would not update the remote nodes until a new SFSB operation occurs i.e. with SFSB, we replicate only when we modify a SFSB, not when a merge occurs. That's even worst. Suppose after partition merge group 1. has SFSB in state A and group 2. has SFSB in state B. We DON'T merge state for SFSB. First, as I belive, after partition merge you can get inconstent behavior. If you use SFSB replica from node in group 1. you get state A if you read SFSB replica from node in group 2. you get state B. Yes, but remember that the choice of the node is done in the CLIENT proxy which will ALWAYS use the same target as long as it is available. Second, when SFSB modify to state C occurs, one node rewrites state B and A on all other nodes. So group of nodes went through states A-C and group through states A-B-C with all consequences. Yes, the solution is in the fact that we don't merge the state and we always go to the same node. The only situation where something bad could occur is: - client A use node 1 - partition is split - client A continue using node 1 - node 1 cannot transmit its updates to node 2 because of the net partition - client can suddently no more reach node1 - it failover to node 2 but node 2 has the old state! If this is a problem for you, we could imagine to send piggy-back to the client proxy, the state version id. If, when we failover, we have a lower value, we could throw an exception. Maybe I could try to prepare some testcase demonstrating problem. Sorry if am I missing something, but I still strongly believe, that merging partions is very dangerous and can put cluster in Yes, which is why we don't merge. inconsistent state. It seems to me, that it is as complicated as to try merge the state of two computers (processors, memory, I/O devices) after they run separateted for a while. Yes, you are right, it is application specific, there is no generic way to take such a decision. Cheers, Sacha --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
RE: [JBoss-dev] Partition merge and service state merge algorithm
Yes, sure. In the meantime, I've added my SFSB proposal to the clustering todo list. Thank you for this discussion, sacha -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Klimek Sent: lundi, 31. mars 2003 00:07 To: [EMAIL PROTECTED] Subject: Re: [JBoss-dev] Partition merge and service state merge algorithm Hi Sacha, thank you very much for your comments. Now I believe I have quite clean picture of partition merge issues. Maybe the conditions and limitations you mentioned should be added to documentation as they are not obvious and there can be a lot of people living, as I did before, in paradise, where all the mess with state merging, is handled by clustering framework. Greet's David Sacha Labourey wrote: Maybe that's one of the points. As I understand partion split each groups things that all nodes in other group are down, but they are not so there is not chance how to avoid concurrent access. Yes. But solutions may be found, such as using a central DB as a way to decide who is up/down. Anyway the same problem can occur in DistributedState service from JBoss Clustering framework, where no such limitaton is explicitly given by spec. Yes, this must be added for generic use. But let's finish our SFSB discussion first as it is a little bit different. Furthermore, even in the strange scenario you describe (concurrent access to a same SFSB), the merge would not update the remote nodes until a new SFSB operation occurs i.e. with SFSB, we replicate only when we modify a SFSB, not when a merge occurs. That's even worst. Suppose after partition merge group 1. has SFSB in state A and group 2. has SFSB in state B. We DON'T merge state for SFSB. First, as I belive, after partition merge you can get inconstent behavior. If you use SFSB replica from node in group 1. you get state A if you read SFSB replica from node in group 2. you get state B. Yes, but remember that the choice of the node is done in the CLIENT proxy which will ALWAYS use the same target as long as it is available. Second, when SFSB modify to state C occurs, one node rewrites state B and A on all other nodes. So group of nodes went through states A-C and group through states A-B-C with all consequences. Yes, the solution is in the fact that we don't merge the state and we always go to the same node. The only situation where something bad could occur is: - client A use node 1 - partition is split - client A continue using node 1 - node 1 cannot transmit its updates to node 2 because of the net partition - client can suddently no more reach node1 - it failover to node 2 but node 2 has the old state! If this is a problem for you, we could imagine to send piggy-back to the client proxy, the state version id. If, when we failover, we have a lower value, we could throw an exception. Maybe I could try to prepare some testcase demonstrating problem. Sorry if am I missing something, but I still strongly believe, that merging partions is very dangerous and can put cluster in Yes, which is why we don't merge. inconsistent state. It seems to me, that it is as complicated as to try merge the state of two computers (processors, memory, I/O devices) after they run separateted for a while. Yes, you are right, it is application specific, there is no generic way to take such a decision. Cheers, Sacha --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss
RE: [JBoss-dev] Partition merge and service state merge algorithm
Disagree. Consider following: 1. Cluster running banking application with SFSB's Ok. 2. Cluster is split into two groups ok 3. Each group continues concurently previous computation You mean: you may have work in progress for a given set of SFSB on each node (each node being on a given network partition) 4. Second group finishes computation and changes SFSB state and produces output (assigns money to account) = go to the DB = no network partition wrt database access. OK. 5. First group still doesn't finish its computation Ok. 6. Partition merge occurs Ok. 7. SFBS state on nodes of second group is rewriten by state of first unfished group No. Here, you make the assumption that you can have CONCURRENT access to the SAME SFSB which is not allowed per spec. Furthermore, even in the strange scenario you describe (concurrent access to a same SFSB), the merge would not update the remote nodes until a new SFSB operation occurs i.e. with SFSB, we replicate only when we modify a SFSB, not when a merge occurs. 8. Cluster finishes computation again and changes SFBS state and produces output (assigns AGAIN money to account) So we get as I belive incorrect and dangerous cluster behavior. Do we agree now? Cheers, Sacha --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
Re: [JBoss-dev] Partition merge and service state merge algorithm
Hi Sacha, 6. Partition merge occurs Ok. 7. SFBS state on nodes of second group is rewriten by state of first unfished group No. Here, you make the assumption that you can have CONCURRENT access to the SAME SFSB which is not allowed per spec. Maybe that's one of the points. As I understand partion split each groups things that all nodes in other group are down, but they are not so there is not chance how to avoid concurrent access. Anyway the same problem can occur in DistributedState service from JBoss Clustering framework, where no such limitaton is explicitly given by spec. Furthermore, even in the strange scenario you describe (concurrent access to a same SFSB), the merge would not update the remote nodes until a new SFSB operation occurs i.e. with SFSB, we replicate only when we modify a SFSB, not when a merge occurs. That's even worst. Suppose after partition merge group 1. has SFSB in state A and group 2. has SFSB in state B. First, as I belive, after partition merge you can get inconstent behavior. If you use SFSB replica from node in group 1. you get state A if you read SFSB replica from node in group 2. you get state B. Second, when SFSB modify to state C occurs, one node rewrites state B and A on all other nodes. So group of nodes went through states A-C and group through states A-B-C with all consequences. Maybe I could try to prepare some testcase demonstrating problem. Sorry if am I missing something, but I still strongly believe, that merging partions is very dangerous and can put cluster in inconsistent state. It seems to me, that it is as complicated as to try merge the state of two computers (processors, memory, I/O devices) after they run separateted for a while. Anyway, beside my complains, jboss clustering is really great, thank you for this great job. David 8. Cluster finishes computation again and changes SFBS state and produces output (assigns AGAIN money to account) So we get as I belive incorrect and dangerous cluster behavior. Do we agree now? Cheers, Sacha --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
RE: [JBoss-dev] Partition merge and service state merge algorithm
You can subscribe to merge events if you want to implement the merging yourself i.e. if you use the clustering framework for your own mbeans. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Klimek Sent: jeudi, 27. mars 2003 12:36 To: [EMAIL PROTECTED] Subject: [JBoss-dev] Partition merge and service state merge algorithm Hello, I'm looking for correct algorithm, that merges states of some clustered service when parition merge occurs. Consider following scenario: 1. Running 8 node cluster 2. Added key name with value=beforesplit into state (state is replicated across all nodes of cluster) 3. Because of network failure cluster is splited into two groups (each with 4 nodes) 4. On first group key name is modified to value groupone 5. On second group key name is modified to value grouptwo 6. Network is recovered. Cluster partion merge occurs. After merge all nodes should have one value for key name but which value? (groupone, grouptwo, beforesplit) or exception should be raised? If we drop one value, what if already this value was used in some computation or output and simple drop will cause inconsistent behavior? Current JBoss clustering services doesn't throw light at it now. DistributedStateService doesn't handle partion merge at all and DistributedReplicaManager simply drops one of values when there are differend values for one key. Thank you for any thoughts David Klimek -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
Re: [JBoss-dev] Partition merge and service state merge algorithm
Sacha Labourey wrote: You can subscribe to merge events if you want to implement the merging yourself i.e. if you use the clustering framework for your own mbeans. Hi, thank's for answering. Yes I'm using clustering framwork and membershipChangedDuringMerge, but I didn't find any correct alghorithm how to choose value for conflicting keys. (e.g. Timestamping) I hoped that I would find this idea in source code for DistributedStateService but as I understand its and JavaGroups behavior after partition merge, DistributedStateService can be in inconsistent state. (differend global state data on differend cluster nodes) Am I right? I'm afraid that this problem is unsolvable and there allways be situations in cluster, that after partition merge, cluster will be in inconsistent state and would produce wrong output. And only safe solution to this state conflict after partition merge is to core dump application and call admin :))). -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Klimek Sent: jeudi, 27. mars 2003 12:36 To: [EMAIL PROTECTED] Subject: [JBoss-dev] Partition merge and service state merge algorithm Hello, I'm looking for correct algorithm, that merges states of some clustered service when parition merge occurs. Consider following scenario: 1. Running 8 node cluster 2. Added key name with value=beforesplit into state (state is replicated across all nodes of cluster) 3. Because of network failure cluster is splited into two groups (each with 4 nodes) 4. On first group key name is modified to value groupone 5. On second group key name is modified to value grouptwo 6. Network is recovered. Cluster partion merge occurs. After merge all nodes should have one value for key name but which value? (groupone, grouptwo, beforesplit) or exception should be raised? If we drop one value, what if already this value was used in some computation or output and simple drop will cause inconsistent behavior? Current JBoss clustering services doesn't throw light at it now. DistributedStateService doesn't handle partion merge at all and DistributedReplicaManager simply drops one of values when there are differend values for one key. Thank you for any thoughts David Klimek -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
RE: [JBoss-dev] Partition merge and service state merge algorithm
Hi, thank's for answering. Yes I'm using clustering framwork and membershipChangedDuringMerge, but I didn't find any correct alghorithm how to choose value for conflicting keys. (e.g. Timestamping) I hoped that I would find this idea in source code for DistributedStateService but as I understand its and JavaGroups behavior after partition merge, DistributedStateService can be in inconsistent state. (differend global state data on differend cluster nodes) Am I right? I'm afraid that this problem is unsolvable and there allways be situations in cluster, that after partition merge, cluster will be in inconsistent state and would produce wrong output. No. Cases: - DRM: we refresh total view after merging - Http session: sticky sessions = the last state is always correct - SFSB: we always use the same node and the last state will be resent to other node at merge time --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
Re: [JBoss-dev] Partition merge and service state merge algorithm
I'm afraid that this problem is unsolvable and there allways be situations in cluster, that after partition merge, cluster will be in inconsistent state and would produce wrong output. No. Cases: - DRM: we refresh total view after merging Agree. - Http session: sticky sessions = the last state is always correct Agree. - SFSB: we always use the same node and the last state will be resent to other node at merge time Disagree. Consider following: 1. Cluster running banking application with SFSB's 2. Cluster is split into two groups 3. Each group continues concurently previous computation 4. Second group finishes computation and changes SFSB state and produces output (assigns money to account) 5. First group still doesn't finish its computation 6. Partition merge occurs 7. SFBS state on nodes of second group is rewriten by state of first unfished group 8. Cluster finishes computation again and changes SFBS state and produces output (assigns AGAIN money to account) So we get as I belive incorrect and dangerous cluster behavior. Greets David -- http://www.sweb.cz/david.klimek --- This SF.net email is sponsored by: The Definitive IT and Networking Event. Be There! NetWorld+Interop Las Vegas 2003 -- Register today! http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en ___ Jboss-development mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/jboss-development
