001: /*
002: * JBoss, Home of Professional Open Source.
003: * Copyright 2006, Red Hat Middleware LLC, and individual contributors
004: * as indicated by the @author tags. See the copyright.txt file in the
005: * distribution for a full listing of individual contributors.
006: *
007: * This is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU Lesser General Public License as
009: * published by the Free Software Foundation; either version 2.1 of
010: * the License, or (at your option) any later version.
011: *
012: * This software is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: *
017: * You should have received a copy of the GNU Lesser General Public
018: * License along with this software; if not, write to the Free
019: * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
021: */
022: package org.jboss.ha.hasessionstate.server;
023:
024: import java.util.ArrayList;
025: import java.util.Iterator;
026:
027: import org.jboss.ha.framework.interfaces.SubPartitionInfo;
028: import org.jboss.ha.framework.interfaces.SubPartitionsInfo;
029:
030: /**
031: * Default implementation of HASessionStateTopologyComputer
032: *
033: * @see org.jboss.ha.hasessionstate.interfaces.HASessionState
034: * @author sacha.labourey@cogito-info.ch
035: * @version $Revision: 57188 $
036: *
037: * <p><b>Revisions:</b><br>
038: */
039:
040: public class HASessionStateTopologyComputerImpl implements
041: HASessionStateTopologyComputer {
042:
043: protected long nodesPerSubPartition = 0;
044: protected String sessionStateIdentifier = null;
045:
046: /** Creates new HASessionStateTopologyComputerImpl */
047: public HASessionStateTopologyComputerImpl() {
048: }
049:
050: public void init(String sessionStateName, long nodesPerSubPartition) {
051: this .sessionStateIdentifier = sessionStateName;
052: this .nodesPerSubPartition = nodesPerSubPartition;
053: }
054:
055: public void start() {
056: }
057:
058: public SubPartitionsInfo computeNewTopology(
059: SubPartitionsInfo currentTopology, ArrayList newReplicants) {
060: if (newReplicants.size() < 1)
061: currentTopology.partitions = null;
062: else if (newReplicants.size() == 1) {
063: // we are alone! Are we already in a partition? If this is the case, we do not change!
064: //
065: if (currentTopology.partitions != null)
066: currentTopology = computeCompatibleComposition(
067: currentTopology, newReplicants);
068: else {
069: SubPartitionInfo aPartition = new SubPartitionInfo();
070: aPartition.subPartitionName = getSubPartitionName(currentTopology);
071: aPartition.memberNodeNames.add(newReplicants.get(0));
072: SubPartitionInfo[] thePartition = { aPartition };
073: currentTopology.partitions = thePartition;
074: }
075: } else if (currentTopology == null
076: || currentTopology.partitions == null)
077: // this is the first time we will have to decide of a spliting
078: //
079: currentTopology = computerFirstComposition(currentTopology,
080: newReplicants);
081: else
082: // There is a spliting already in place: we will need to take care of it in order to minimize group changes
083: // i.e. state transfer that will occur from these changes
084: //
085: currentTopology = computeCompatibleComposition(
086: currentTopology, newReplicants);
087:
088: return currentTopology;
089:
090: }
091:
092: protected SubPartitionsInfo computerFirstComposition(
093: SubPartitionsInfo splitingInfo, ArrayList replicants) {
094: int i = 0;
095: String rep = null;
096: ArrayList newConfig = new ArrayList();
097: SubPartitionInfo aPartition = null;
098: int grpNumber = 0;
099:
100: // Build groups sequentially
101: //
102: for (Iterator reps = replicants.iterator(); reps.hasNext(); i++) {
103: rep = (String) reps.next();
104: if ((i % nodesPerSubPartition) == 0) {
105: grpNumber++;
106: aPartition = new SubPartitionInfo();
107: aPartition.subPartitionName = getSubPartitionName(splitingInfo);
108: newConfig.add(aPartition);
109: }
110: aPartition.memberNodeNames.add(rep);
111: }
112:
113: // we don't like singleton nodes for HA...
114: //
115: if (aPartition.memberNodeNames.size() == 1) {
116: rep = (String) aPartition.memberNodeNames.get(0); // get singleton info
117: newConfig.remove(grpNumber - 1); // remove last singleton group
118: aPartition = (SubPartitionInfo) (newConfig
119: .get(grpNumber - 1)); // access last built group
120: aPartition.memberNodeNames.add(rep); // add singleton to last built group
121: }
122:
123: SubPartitionInfo[] newSpliting = new SubPartitionInfo[1];
124: newSpliting = (SubPartitionInfo[]) newConfig
125: .toArray(newSpliting);
126: splitingInfo.partitions = newSpliting;
127:
128: return splitingInfo;
129: }
130:
131: protected SubPartitionsInfo computeCompatibleComposition(
132: SubPartitionsInfo splitingInfo, ArrayList replicants) {
133: // In a first step, we purge the current spliting to remove dead members
134: //
135: SubPartitionInfo[] newSpliting = null;
136: ArrayList newSubParts = new ArrayList();
137:
138: for (int i = 0; i < splitingInfo.partitions.length; i++) {
139: SubPartitionInfo currentSubPart = splitingInfo.partitions[i];
140: SubPartitionInfo newCurrent = null;
141: Iterator iter = currentSubPart.memberNodeNames.iterator();
142: while (iter.hasNext()) {
143: String node = (String) iter.next();
144: if (replicants.contains(node)) {
145: if (newCurrent == null) {
146: newCurrent = (SubPartitionInfo) currentSubPart
147: .clone();
148: newCurrent.memberNodeNames.clear();
149: }
150: newCurrent.memberNodeNames.add(node);
151: }
152: }
153: if (newCurrent != null)
154: newSubParts.add(newCurrent);
155: }
156:
157: // we now create a list of new nodes that are not yet part of any group
158: //
159: Iterator iter = replicants.iterator();
160: ArrayList newMembersNotInAGroup = new ArrayList();
161: while (iter.hasNext()) {
162: boolean found = false;
163: String aMember = (String) iter.next();
164: Iterator iterNewSubPart = newSubParts.iterator();
165: while (iterNewSubPart.hasNext() && !found)
166: if (((SubPartitionInfo) iterNewSubPart.next()).memberNodeNames
167: .contains(aMember))
168: found = true;
169: if (!found)
170: newMembersNotInAGroup.add(aMember);
171: }
172: iter = null;
173:
174: // we now have purged our current sub-partition structure from its dead members
175: // we now check if some sub-partitions need to be merged to remove singleton groups
176: // or if there is a group with n>(nodesPerSubPartition) that may be reduced to its ideal size
177: //
178:
179: // we remove elements that are less than the group size and put them in a new sorted list
180: //
181: ArrayList smallerGroups = new ArrayList();
182: ArrayList correctlySizedGroups = new ArrayList();
183: ArrayList biggerGroups = new ArrayList();
184:
185: for (int i = 0; i < newSubParts.size(); i++) {
186: int groupSize = ((SubPartitionInfo) newSubParts.get(i)).memberNodeNames
187: .size();
188: if (groupSize < this .nodesPerSubPartition)
189: smallerGroups.add(newSubParts.get(i));
190: else if (groupSize > this .nodesPerSubPartition)
191: biggerGroups.add(newSubParts.get(i));
192: else
193: correctlySizedGroups.add(newSubParts.get(i));
194: }
195:
196: // for our algo, we need to sort smallerGroups
197: //
198: java.util.Collections.sort(smallerGroups);
199:
200: //
201: // Our algo is not perfect and could, for example, take in account, the actual group load in order to minimize
202: // the synchronization time
203: //
204:
205: // 1st step: we place newly started nodes (not yet part of a group) in smallerGroups
206: // by first feeding small groups
207: //
208: iter = newMembersNotInAGroup.iterator();
209: while (iter.hasNext()) {
210: String member = (String) iter.next();
211: SubPartitionInfo target = null;
212: if (smallerGroups.size() > 0) {
213: target = (SubPartitionInfo) smallerGroups.get(0); // array is sorted
214: target.memberNodeNames.add(member);
215: if (target.memberNodeNames.size() == this .nodesPerSubPartition) {
216: // we have a complete sub-partition, we change its owning group
217: //
218: smallerGroups.remove(0);
219: correctlySizedGroups.add(target);
220: }
221: } else {
222: // we create an singleton group
223: //
224: target = new SubPartitionInfo();
225: target.setIsNewGroup();
226: target.subPartitionName = getSubPartitionName(splitingInfo);
227: target.memberNodeNames.add(member);
228: smallerGroups.add(target);
229: java.util.Collections.sort(smallerGroups);
230: }
231: }
232:
233: // 2nd step: we reduce the size of any too-big sub-partition (biggerGroups)
234: // by removing the last component and feeding elements in smallerGroups
235: // If smallerGroups is empty, we don't modify biggerGroups (minimize
236: // involved state transfer)
237: //
238: iter = biggerGroups.iterator();
239: while (iter.hasNext()) {
240: SubPartitionInfo big = (SubPartitionInfo) iter.next();
241: if (smallerGroups.size() > 0) {
242: String member = (String) big.memberNodeNames
243: .get(big.memberNodeNames.size() - 1); // get last one
244: SubPartitionInfo target = null;
245: target = (SubPartitionInfo) smallerGroups.get(0); // array is sorted
246: target.memberNodeNames.add(member);
247: big.memberNodeNames
248: .remove(big.memberNodeNames.size() - 1);
249: if (target.memberNodeNames.size() == this .nodesPerSubPartition) {
250: // we have a complete sub-partition, we change its owning group
251: //
252: smallerGroups.remove(0);
253: correctlySizedGroups.add(target);
254: }
255: }
256: }
257: // biggerGroups is now processed, we can move it to the correctly sized group
258: //
259: correctlySizedGroups.addAll(biggerGroups);
260:
261: // 3rd step: we now try to merge sub-partitions belonging to smallerGroups to form bigger groups (up to the
262: // max size of a sub-partition). We travel in descending order to keep max granularity when forming groups
263: //
264: boolean thirdStepFinished = (smallerGroups.size() == 0);
265: while (!thirdStepFinished) {
266: //thirdStepFinished = (smallerGroups.size () == 0);
267: SubPartitionInfo current = (SubPartitionInfo) smallerGroups
268: .get(smallerGroups.size() - 1);
269: for (int i = smallerGroups.size() - 2; i >= 0; i--) {
270: // test if the merge is possible
271: //
272: SubPartitionInfo merger = (SubPartitionInfo) smallerGroups
273: .get(i);
274: if ((merger.memberNodeNames.size() + current.memberNodeNames
275: .size()) <= this .nodesPerSubPartition) {
276: // it is possible to merge both
277: //
278: current.merge(merger);
279: smallerGroups.remove(i);
280:
281: }
282: // we check if we need to go further or not
283: //
284: if (current.memberNodeNames.size() == this .nodesPerSubPartition)
285: break;
286:
287: }
288: if (current.memberNodeNames.size() > 1) {
289: // we only move non-singleton groups
290: //
291: smallerGroups.remove(smallerGroups.size() - 1);
292: correctlySizedGroups.add(current);
293: }
294:
295: thirdStepFinished = ((smallerGroups.size() == 0) || ((smallerGroups
296: .size() == 1) && (((SubPartitionInfo) smallerGroups
297: .get(0)).memberNodeNames.size() == 1)));
298:
299: }
300:
301: // 4th step: if smallerGroups is not empty, it means that we have a singleton. In that case,
302: // we merge it with the smallest group we can find.
303: //
304: if (smallerGroups.size() > 0) {
305: if (correctlySizedGroups.size() > 0) {
306: java.util.Collections.sort(correctlySizedGroups);
307: SubPartitionInfo merger = (SubPartitionInfo) smallerGroups
308: .get(0);
309: SubPartitionInfo master = (SubPartitionInfo) correctlySizedGroups
310: .get(0);
311: master.merge(merger);
312: } else {
313: // we have a single singleton group!
314: //
315: correctlySizedGroups.add(smallerGroups.get(0));
316: }
317: }
318:
319: // we now commit our new splitting. All members will consequently receive a message indicating
320: // that the spliting has changed and act accordingly
321: //
322: newSpliting = new SubPartitionInfo[1];
323: newSpliting = (SubPartitionInfo[]) correctlySizedGroups
324: .toArray(newSpliting);
325: splitingInfo.partitions = newSpliting;
326:
327: return splitingInfo;
328: }
329:
330: protected String getSubPartitionName(SubPartitionsInfo manager) {
331: return this .sessionStateIdentifier + "-Group-"
332: + manager.getNextGroupId();
333: }
334:
335: // testing of the above algo... can be commented...
336: //
337: /*
338: public static void main (String[] args)
339: {
340: HASessionStateTopologyComputerImpl tmp = new HASessionStateTopologyComputerImpl ();
341: tmp.init ("test", 2);
342: tmp.start ();
343:
344: SubPartitionsInfo splitInfo = new SubPartitionsInfo ();
345: ArrayList replic = new ArrayList ();
346: ArrayList parts = new ArrayList ();
347: splitInfo.partitions = new SubPartitionInfo[1];
348:
349: //parts.add (new SubPartitionInfo ("SP1", helper_String ("ABC")));
350: //parts.add (new SubPartitionInfo ("SP2", helper_String ("DEF")));
351: //parts.add (new SubPartitionInfo ("SP3", helper_String ("GHI")));
352:
353: parts.add (new SubPartitionInfo ("SP4", helper_String ("AB")));
354: parts.add (new SubPartitionInfo ("SP5", helper_String ("EF")));
355:
356: //parts.add (new SubPartitionInfo ("SP1", helper_String ("Axy")));
357: //parts.add (new SubPartitionInfo ("SP2", helper_String ("Bmn")));
358: //parts.add (new SubPartitionInfo ("SP3", helper_String ("CDE")));
359: //parts.add (new SubPartitionInfo ("SP4", helper_String ("FGHI")));
360:
361: splitInfo.partitions = (SubPartitionInfo[])parts.toArray (splitInfo.partitions);
362: replic = new ArrayList (java.util.Arrays.asList (helper_String ("AEF") ));
363:
364: System.out.println (replic);
365: System.out.println (splitInfo);
366: splitInfo = tmp.computeCompatibleComposition (splitInfo, replic);
367: System.out.println (splitInfo);
368:
369: }
370:
371: private static String[] helper_String (String letters)
372: {
373: String[] tabl = new String[letters.length ()];
374: for (int i=0; i<letters.length ();i++)
375: tabl[i]=letters.substring (i, i+1);
376:
377: return tabl;
378: }
379: */
380: }
|