Java > Open Source Codes > org > jboss > ha > hasessionstate > server > HASessionStateTopologyComputerImpl


1 /*
2   * JBoss, Home of Professional Open Source
3   * Copyright 2005, JBoss Inc., and individual contributors as indicated
4   * by the @authors tag. See the copyright.txt in the distribution for a
5   * full listing of individual contributors.
6   *
7   * This is free software; you can redistribute it and/or modify it
8   * under the terms of the GNU Lesser General Public License as
9   * published by the Free Software Foundation; either version 2.1 of
10   * the License, or (at your option) any later version.
11   *
12   * This software is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15   * Lesser General Public License for more details.
16   *
17   * You should have received a copy of the GNU Lesser General Public
18   * License along with this software; if not, write to the Free
19   * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20   * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
21   */
22 package org.jboss.ha.hasessionstate.server;
23
24 import java.util.ArrayList ;
25 import java.util.Iterator ;
26
27 import org.jboss.ha.framework.interfaces.SubPartitionInfo;
28 import org.jboss.ha.framework.interfaces.SubPartitionsInfo;
29
30 /**
31  * Default implementation of HASessionStateTopologyComputer
32  *
33  * @see org.jboss.ha.hasessionstate.interfaces.HASessionState
34  * @author sacha.labourey@cogito-info.ch
35  * @version $Revision: 37459 $
36  *
37  * <p><b>Revisions:</b><br>
38  */
39
40 public class HASessionStateTopologyComputerImpl implements HASessionStateTopologyComputer
41 {
42    
43    protected long nodesPerSubPartition = 0;
44    protected String sessionStateIdentifier = null;
45    
46    /** Creates new HASessionStateTopologyComputerImpl */
47    public HASessionStateTopologyComputerImpl ()
48    {
49    }
50    
51    public void init (String sessionStateName, long nodesPerSubPartition)
52    {
53       this.sessionStateIdentifier = sessionStateName;
54       this.nodesPerSubPartition = nodesPerSubPartition;
55    }
56    
57    public void start () {}
58    
59    public SubPartitionsInfo computeNewTopology (SubPartitionsInfo currentTopology, ArrayList newReplicants)
60    {
61       if (newReplicants.size () < 1)
62          currentTopology.partitions = null;
63       else if (newReplicants.size () == 1)
64       {
65          // we are alone! Are we already in a partition? If this is the case, we do not change!
66 //
67 if (currentTopology.partitions != null)
68             currentTopology = computeCompatibleComposition (currentTopology, newReplicants);
69          else
70          {
71             SubPartitionInfo aPartition = new SubPartitionInfo ();
72             aPartition.subPartitionName = getSubPartitionName (currentTopology);
73             aPartition.memberNodeNames.add (newReplicants.get (0));
74             SubPartitionInfo[] thePartition =
75             { aPartition };
76             currentTopology.partitions = thePartition;
77          }
78       }
79       else if (currentTopology == null || currentTopology.partitions == null)
80          // this is the first time we will have to decide of a spliting
81 //
82 currentTopology = computerFirstComposition (currentTopology, newReplicants);
83       else
84          // There is a spliting already in place: we will need to take care of it in order to minimize group changes
85 // i.e. state transfer that will occur from these changes
86 //
87 currentTopology = computeCompatibleComposition (currentTopology, newReplicants);
88       
89       return currentTopology;
90       
91    }
92    
93    protected SubPartitionsInfo computerFirstComposition (SubPartitionsInfo splitingInfo, ArrayList replicants)
94    {
95       int i=0;
96       String rep = null;
97       ArrayList newConfig = new ArrayList ();
98       SubPartitionInfo aPartition = null;
99       int grpNumber = 0;
100       
101       // Build groups sequentially
102 //
103 for (Iterator reps = replicants.iterator (); reps.hasNext (); i++)
104       {
105          rep = (String )reps.next ();
106          if ( (i%nodesPerSubPartition) == 0 )
107          {
108             grpNumber++;
109             aPartition = new SubPartitionInfo ();
110             aPartition.subPartitionName = getSubPartitionName (splitingInfo);
111             newConfig.add (aPartition);
112          }
113          aPartition.memberNodeNames.add (rep);
114       }
115       
116       // we don't like singleton nodes for HA...
117 //
118 if (aPartition.memberNodeNames.size () == 1)
119       {
120          rep = (String ) aPartition.memberNodeNames.get (0); // get singleton info
121 newConfig.remove (grpNumber-1); // remove last singleton group
122 aPartition = (SubPartitionInfo)(newConfig.get (grpNumber-1)); // access last built group
123 aPartition.memberNodeNames.add (rep); // add singleton to last built group
124 }
125       
126       SubPartitionInfo[] newSpliting = new SubPartitionInfo[1];
127       newSpliting = (SubPartitionInfo[]) newConfig.toArray (newSpliting);
128       splitingInfo.partitions = newSpliting;
129       
130       return splitingInfo;
131    }
132    
133    protected SubPartitionsInfo computeCompatibleComposition (SubPartitionsInfo splitingInfo, ArrayList replicants)
134    {
135       // In a first step, we purge the current spliting to remove dead members
136 //
137 SubPartitionInfo[] newSpliting = null;
138       ArrayList newSubParts = new ArrayList ();
139       
140       for (int i=0; i<splitingInfo.partitions.length; i++)
141       {
142          SubPartitionInfo currentSubPart = splitingInfo.partitions[i];
143          SubPartitionInfo newCurrent = null;
144          Iterator iter = currentSubPart.memberNodeNames.iterator ();
145          while (iter.hasNext ())
146          {
147             String node = (String )iter.next ();
148             if (replicants.contains (node))
149             {
150                if (newCurrent == null)
151                {
152                   newCurrent = (SubPartitionInfo)currentSubPart.clone ();
153                   newCurrent.memberNodeNames.clear ();
154                }
155                newCurrent.memberNodeNames.add (node);
156             }
157          }
158          if (newCurrent != null)
159             newSubParts.add (newCurrent);
160       }
161       
162       // we now create a list of new nodes that are not yet part of any group
163 //
164 Iterator iter = replicants.iterator ();
165       ArrayList newMembersNotInAGroup = new ArrayList ();
166       while (iter.hasNext ())
167       {
168          boolean found = false;
169          String aMember = (String )iter.next ();
170          Iterator iterNewSubPart = newSubParts.iterator ();
171          while (iterNewSubPart.hasNext () && !found)
172             if (((SubPartitionInfo)iterNewSubPart.next ()).memberNodeNames.contains (aMember))
173                found = true;
174          if (!found)
175             newMembersNotInAGroup.add (aMember);
176       }
177       iter = null;
178       
179       // we now have purged our current sub-partition structure from its dead members
180 // we now check if some sub-partitions need to be merged to remove singleton groups
181 // or if there is a group with n>(nodesPerSubPartition) that may be reduced to its ideal size
182 //
183
184       // we remove elements that are less than the group size and put them in a new sorted list
185 //
186 ArrayList smallerGroups = new ArrayList ();
187       ArrayList correctlySizedGroups = new ArrayList ();
188       ArrayList biggerGroups = new ArrayList ();
189       
190       for (int i=0; i<newSubParts.size (); i++)
191       {
192          int groupSize = ((SubPartitionInfo)newSubParts.get (i)).memberNodeNames.size ();
193          if (groupSize < this.nodesPerSubPartition)
194             smallerGroups.add (newSubParts.get (i));
195          else if (groupSize > this.nodesPerSubPartition)
196             biggerGroups.add (newSubParts.get (i));
197          else
198             correctlySizedGroups.add (newSubParts.get (i));
199       }
200       
201       // for our algo, we need to sort smallerGroups
202 //
203 java.util.Collections.sort (smallerGroups);
204       
205       //
206 // Our algo is not perfect and could, for example, take in account, the actual group load in order to minimize
207 // the synchronization time
208 //
209
210       // 1st step: we place newly started nodes (not yet part of a group) in smallerGroups
211 // by first feeding small groups
212 //
213 iter = newMembersNotInAGroup.iterator ();
214       while (iter.hasNext ())
215       {
216          String member = (String )iter.next ();
217          SubPartitionInfo target = null;
218          if (smallerGroups.size () > 0)
219          {
220             target = (SubPartitionInfo)smallerGroups.get (0); // array is sorted
221 target.memberNodeNames.add (member);
222             if (target.memberNodeNames.size () == this.nodesPerSubPartition)
223             {
224                // we have a complete sub-partition, we change its owning group
225 //
226 smallerGroups.remove (0);
227                correctlySizedGroups.add (target);
228             }
229          }
230          else
231          {
232             // we create an singleton group
233 //
234 target = new SubPartitionInfo ();
235             target.setIsNewGroup ();
236             target.subPartitionName = getSubPartitionName (splitingInfo);
237             target.memberNodeNames.add (member);
238             smallerGroups.add (target);
239             java.util.Collections.sort (smallerGroups);
240          }
241       }
242       
243       // 2nd step: we reduce the size of any too-big sub-partition (biggerGroups)
244 // by removing the last component and feeding elements in smallerGroups
245 // If smallerGroups is empty, we don't modify biggerGroups (minimize
246 // involved state transfer)
247 //
248 iter = biggerGroups.iterator ();
249       while (iter.hasNext ())
250       {
251          SubPartitionInfo big = (SubPartitionInfo)iter.next ();
252          if (smallerGroups.size () > 0)
253          {
254             String member = (String )big.memberNodeNames.get (big.memberNodeNames.size ()-1); // get last one
255 SubPartitionInfo target = null;
256             target = (SubPartitionInfo)smallerGroups.get (0); // array is sorted
257 target.memberNodeNames.add (member);
258             big.memberNodeNames.remove (big.memberNodeNames.size () -1);
259             if (target.memberNodeNames.size () == this.nodesPerSubPartition)
260             {
261                // we have a complete sub-partition, we change its owning group
262 //
263 smallerGroups.remove (0);
264                correctlySizedGroups.add (target);
265             }
266          }
267       }
268       // biggerGroups is now processed, we can move it to the correctly sized group
269 //
270 correctlySizedGroups.addAll (biggerGroups);
271       
272       // 3rd step: we now try to merge sub-partitions belonging to smallerGroups to form bigger groups (up to the
273 // max size of a sub-partition). We travel in descending order to keep max granularity when forming groups
274 //
275 boolean thirdStepFinished = (smallerGroups.size () == 0);
276       while (!thirdStepFinished)
277       {
278          //thirdStepFinished = (smallerGroups.size () == 0);
279 SubPartitionInfo current = (SubPartitionInfo)smallerGroups.get (smallerGroups.size ()-1);
280          for (int i = smallerGroups.size ()-2; i >= 0; i--)
281          {
282             // test if the merge is possible
283 //
284 SubPartitionInfo merger = (SubPartitionInfo)smallerGroups.get (i);
285             if ((merger.memberNodeNames.size () + current.memberNodeNames.size ()) <= this.nodesPerSubPartition)
286             {
287                // it is possible to merge both
288 //
289 current.merge (merger);
290                smallerGroups.remove (i);
291                
292             }
293             // we check if we need to go further or not
294 //
295 if (current.memberNodeNames.size () == this.nodesPerSubPartition)
296                break;
297             
298          }
299          if (current.memberNodeNames.size () > 1)
300          {
301             // we only move non-singleton groups
302 //
303 smallerGroups.remove (smallerGroups.size ()-1);
304             correctlySizedGroups.add (current);
305          }
306          
307          thirdStepFinished = ( (smallerGroups.size () == 0) ||
308          ((smallerGroups.size () == 1) && ( ((SubPartitionInfo)smallerGroups.get (0)).memberNodeNames.size () == 1)) );
309          
310       }
311       
312       // 4th step: if smallerGroups is not empty, it means that we have a singleton. In that case,
313 // we merge it with the smallest group we can find.
314 //
315 if (smallerGroups.size () > 0)
316       {
317          if (correctlySizedGroups.size ()>0)
318          {
319          java.util.Collections.sort (correctlySizedGroups);
320          SubPartitionInfo merger = (SubPartitionInfo)smallerGroups.get (0);
321          SubPartitionInfo master = (SubPartitionInfo)correctlySizedGroups.get (0);
322          master.merge (merger);
323          }
324          else
325          {
326             // we have a single singleton group!
327 //
328 correctlySizedGroups.add (smallerGroups.get (0));
329          }
330       }
331       
332       // we now commit our new splitting. All members will consequently receive a message indicating
333 // that the spliting has changed and act accordingly
334 //
335 newSpliting = new SubPartitionInfo[1];
336       newSpliting = (SubPartitionInfo[])correctlySizedGroups.toArray (newSpliting);
337       splitingInfo.partitions = newSpliting;
338       
339       return splitingInfo;
340    }
341    
342    protected String getSubPartitionName (SubPartitionsInfo manager)
343    {
344       return this.sessionStateIdentifier + "-Group-" + manager.getNextGroupId ();
345    }
346    
347    // testing of the above algo... can be commented...
348 //
349 /*
350    public static void main (String[] args)
351    {
352       HASessionStateTopologyComputerImpl tmp = new HASessionStateTopologyComputerImpl ();
353       tmp.init ("test", 2);
354       tmp.start ();
355       
356       SubPartitionsInfo splitInfo = new SubPartitionsInfo ();
357       ArrayList replic = new ArrayList ();
358       ArrayList parts = new ArrayList ();
359       splitInfo.partitions = new SubPartitionInfo[1];
360       
361       //parts.add (new SubPartitionInfo ("SP1", helper_String ("ABC")));
362       //parts.add (new SubPartitionInfo ("SP2", helper_String ("DEF")));
363       //parts.add (new SubPartitionInfo ("SP3", helper_String ("GHI")));
364       
365       parts.add (new SubPartitionInfo ("SP4", helper_String ("AB")));
366       parts.add (new SubPartitionInfo ("SP5", helper_String ("EF")));
367       
368       //parts.add (new SubPartitionInfo ("SP1", helper_String ("Axy")));
369       //parts.add (new SubPartitionInfo ("SP2", helper_String ("Bmn")));
370       //parts.add (new SubPartitionInfo ("SP3", helper_String ("CDE")));
371       //parts.add (new SubPartitionInfo ("SP4", helper_String ("FGHI")));
372       
373       splitInfo.partitions = (SubPartitionInfo[])parts.toArray (splitInfo.partitions);
374       replic = new ArrayList (java.util.Arrays.asList (helper_String ("AEF") ));
375       
376       System.out.println (replic);
377       System.out.println (splitInfo);
378       splitInfo = tmp.computeCompatibleComposition (splitInfo, replic);
379       System.out.println (splitInfo);
380       
381    }
382
383    private static String[] helper_String (String letters)
384    {
385       String[] tabl = new String[letters.length ()];
386       for (int i=0; i<letters.length ();i++)
387          tabl[i]=letters.substring (i, i+1);
388       
389       return tabl;
390    }
391    */
392 }
393

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags