View Javadoc

1   /*
2    * Copyright (c) 1998-2002 The Jgroup Team.
3    *
4    * This program is free software; you can redistribute it and/or modify
5    * it under the terms of the GNU Lesser General Public License version 2 as
6    * published by the Free Software Foundation.
7    *
8    * This program is distributed in the hope that it will be useful,
9    * but WITHOUT ANY WARRANTY; without even the implied warranty of
10   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   * GNU Lesser General Public License for more details.
12   *
13   * You should have received a copy of the GNU Lesser General Public License
14   * along with this program; if not, write to the Free Software
15   * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16   *
17   */
18  
19  package jgroup.core;
20  
21  import java.io.Externalizable;
22  import java.io.IOException;
23  import java.io.ObjectInput;
24  import java.io.ObjectOutput;
25  import java.io.Serializable;
26  import java.util.ArrayList;
27  import java.util.HashMap;
28  import java.util.Iterator;
29  import java.util.List;
30  import java.util.Map;
31  
32  /**
33   * This class is an helper utility that provides application developers
34   * with additional information about members of their current view. It
35   * can be used as a hash table, to associate application-dependent
36   * information to member identifier. Furthermore, it can be used to
37   * obtain information about the state of a member identifier with
38   * respect to both the current view and previous installed views (for
39   * example, method <code>getStatus</code> may be used to discover which
40   * members survived from the previous view). The table also maintains
41   * information about the relative position of a member identifier in the
42   * member identifier array associated to the last installed view. <p>
43   *
44   * The table maintains information about a member until it crashes.  A
45   * member is declared crashed when a member identifier from the same
46   * endpoint, but with an higher incarnation identifier is inserted in
47   * the table.  This means that the JVM hosting the member has crashed,
48   * and a new one has started.  The state of crashed members is set to
49   * <code>CRASHED</code>.  The information associated to the member is
50   * maintained until the next view change, after which the member
51   * identifier and all its associated information is removed from the
52   * table. <p>
53   *
54   * This class implements the <code>MembershipListener</code> interface,
55   * so it may be passed to the <code>MembershipService</code> to be
56   * notified whenever a view change occurs. Otherwise, the application
57   * developer may take care of updating the table by explicitly calling
58   * method <code>viewChange</code>.
59   *
60   * @author Alberto Montresor
61   * @author Hein Meling
62   * @since Jgroup 0.9
63   */
64  public class MemberTable
65    implements MembershipListener, Externalizable
66  {
67  
68    private static final long serialVersionUID = -5036038300592577228L;
69  
70    ////////////////////////////////////////////////////////////////////////////////////////////
71    // Constants
72    ////////////////////////////////////////////////////////////////////////////////////////////
73  
74    /**
75     *  State assigned to member identifiers not included in the table
76     */
77    public final static int NOTMEMBER   = 0;
78  
79    /**
80     *  State assigned to partitioned members for which no information is
81     *  available.
82     */
83    public final static int PARTITIONED = 1;
84  
85    /**
86     *  State assigned to members that have been declared crashed because
87     *  a member identifier from the same endpoint but with a new
88     *  incarnation number has been inserted in the table.
89     */
90    public final static int CRASHED     = 2;
91  
92    /**
93     *  State assigned to member identifiers whose incarnation number is
94     *  greater than the incarnation number of other members previously
95     *  contained in the table.
96     */
97    public final static int RECOVERING  = 3;
98  
99    /**
100    *  State assigned to members that survived from the previous view
101    */
102   public final static int SURVIVED    = 4;
103 
104   /**
105    *  State assigned to members that merged the view after a previous
106    *  partitioning
107    */
108   public final static int MERGING     = 5;
109 
110   /**
111    *  State assigned to new members
112    */
113   public final static int NEWMEMBER   = 6;
114 
115 
116   ////////////////////////////////////////////////////////////////////////////////////////////
117   // Fields
118   ////////////////////////////////////////////////////////////////////////////////////////////
119 
120   /** Mapping from MemberId to its corresponding status record */
121   private Map<MemberId, Record> table = new HashMap<MemberId, Record>(33);
122 
123   /** Mapping from IP address to list of members */
124   private Map<EndPoint, List<Record>> iptable = new HashMap<EndPoint, List<Record>>(33);
125 
126 
127   ////////////////////////////////////////////////////////////////////////////////////////////
128   // Constructors
129   ////////////////////////////////////////////////////////////////////////////////////////////
130 
131   /**
132    *  Build a new empty <code>MemberTable</code>.  Also used as the
133    *  default constructor for externalization.
134    */
135   public MemberTable()
136   {
137   }
138 
139 
140   ////////////////////////////////////////////////////////////////////////////////////////////
141   // Methods
142   ////////////////////////////////////////////////////////////////////////////////////////////
143 
144 
145   /**
146    *  Returns the status associated with this member identifier. The
147    *  returned value is one of the integer constants defined in this
148    *  class.
149    */
150   synchronized public int getStatus(MemberId id)
151   {
152     Record r = table.get(id);
153     if (r != null)
154       return r.status;
155     else
156       return NOTMEMBER;
157   }
158 
159 
160   /**
161    *  Returns the position of the specified member identifier in the
162    *  last view for which method <code>viewChange</code> has been
163    *  called; return -1 if the member is not member of that view.
164    */
165   synchronized public int getIndex(MemberId id)
166   {
167     Record r = table.get(id);
168     if (r != null)
169       return r.pos;
170     else
171       return -1;
172   }
173 
174 
175   /**
176    *  Associates object <code>value</code> to the specified member
177    *  identifier.  This association is maintained in the table until it
178    *  is explicitly removed from the table, or the member is declared
179    *  crashed.  Values may be retrieved using method <code>get</code>.
180    *
181    *  @param id
182    *    The member identifer to which the <code>value</code> should be
183    *    associated.
184    *  @param value
185    *    The value to associate with the given member.
186    *  @throws IllegalArgumentException
187    *    If the specified member identifier does not exist within this
188    *    member table.
189    */
190   synchronized public void put(MemberId id, Object value)
191   {
192     Record r = table.get(id);
193     if (r != null)
194       r.value = value;
195     else 
196       throw new IllegalArgumentException("The specified member identifer does not exist in this member table.");
197   }
198 
199   /**
200    *  Returns the value associated by this <code>MemberTable</code> to
201    *  the specified member id.  Returns null if the map contains no
202    *  mapping for this member id.  A return value of null does not
203    *  necessarily indicate that the map contains no mapping for the key;
204    *  it is possible that the map explicitly maps the key to null.
205    *
206    *  @param id 
207    *    The member identifier used as key.
208    *  @return 
209    *    The associated value, or null if no such member exists within
210    *    this <code>MemberTable</code>.
211    */
212   synchronized public Object get(MemberId id)
213   {
214     Record r = table.get(id);
215     if (r != null)
216       return r.value;
217     else
218       return null;
219   }
220 
221 
222   /**
223    *
224    */
225   synchronized public void remove(MemberId id)
226   {
227     Record r = table.get(id);
228     if (r != null)
229       table.remove(id);
230     List<Record> recordList = iptable.get(id.getEndPoint());
231     if (recordList != null) {
232       for (Iterator<Record> iter = recordList.iterator(); iter.hasNext();) {
233         Record record = iter.next();
234         if (record.id.equals(id)) {
235           iter.remove();
236           break;
237         }
238       }
239     }
240   }
241 
242 
243   /**
244    *  Returns an array containing the values associated to all members
245    *  contained in this <code>MemberTable</code>, including members
246    *  crashed or partitioned.  The array is sorted according to the member
247    *  index in the most recent view; the crashed and partitioned members
248    *  are placed at the end of the array with no particular order.
249    */
250   synchronized public Object[] elements()
251   {
252     Object[] elements = new Object[table.size()];
253     int max = 0;
254     List<Object> failed = new ArrayList<Object>();
255     for (Record r : table.values()) {
256       if (r.pos != -1) {
257         elements[r.pos] = r.value;
258         if (r.pos > max)
259           max = r.pos;
260       } else {
261         failed.add(r.value);
262       }
263     }
264     for (Iterator iter = failed.iterator(); iter.hasNext();) {
265       elements[++max] = iter.next();
266     }
267     return elements;
268   }
269 
270 
271   /**
272    *  Returns an array containing the identifiers of all members
273    *  contained in this <code>MemberTable</code>, including members
274    *  crashed or partitioned.
275    */
276   synchronized public MemberId[] members()
277   {
278     MemberId[] elements = new MemberId[table.size()];
279     int i = 0;
280     for (Record record : table.values()) {
281       elements[i++] = record.id;
282     }
283     return elements;
284   }
285 
286 
287   /**
288    * Returns true if the specified member identifier is
289    * member of the last view for which method <code>viewChange</code>
290    * has been called; return false otherwise.
291    *
292    * @param id the member whose membership is to be tested.
293    */
294   synchronized public boolean isMember(MemberId id)
295   {
296     Record r = table.get(id);
297     if (r != null)
298       return (r.status != CRASHED && r.status != PARTITIONED);
299     else
300       return false;
301   }
302 
303 
304   public String toString(MemberId id)
305   {
306     StringBuilder buf = new StringBuilder();
307     switch (getStatus(id)) {
308     case NOTMEMBER:
309       /* This member is a new member of this member table */
310       buf.append("NOTMEMBER: ");
311       break;
312 
313     case NEWMEMBER:
314       /* This is a new member */
315       buf.append("NEWMEMBER: ");
316       break;
317 
318     case RECOVERING:
319       /* This member has crashed and then recovered (new incarnation)*/
320       buf.append("RECOVERING: ");
321       break;
322 
323     case SURVIVED:
324       /* This member has survived from the previous view */
325       buf.append("SURVIVING: ");
326       break;
327 
328     case PARTITIONED:
329       /* This member has partitioned since the previous view */
330       buf.append("PARTITIONED: ");
331       break;
332 
333     case MERGING:
334       /* This member has merged since the previous view */
335       buf.append("MERGING: ");
336       break;
337 
338     case CRASHED:
339       /* This member has merged since the previous view */
340       buf.append("CRASHED: ");
341       break;
342 
343     default:
344       buf.append("UNDEFINED STATUS CODE: ");
345       break;
346     }
347     buf.append(id);
348     return buf.toString();
349   }
350 
351 
352   synchronized public String toString()
353   {
354     StringBuilder buf = new StringBuilder();
355     for (Record rec : table.values()) {
356       buf.append(toString(rec.id));
357       buf.append("\n");
358     }
359     return buf.toString();
360   }
361 
362 
363   ////////////////////////////////////////////////////////////////////////////////////////////
364   // Methods from MembershipListener
365   ////////////////////////////////////////////////////////////////////////////////////////////
366 
367   /**
368    *  Update the information in the table with the information
369    *  maintained in the new view.
370    */
371   synchronized public void viewChange(View view)
372   {
373     Record    r;
374     List<Record> recordList;
375 
376     // Remove crashed elements from table
377     for (Iterator<Record> iter = table.values().iterator(); iter.hasNext();) {
378       r = iter.next();
379       r.pos = -1;
380       r.prev = r.status;
381       r.status = PARTITIONED;
382       if (r.prev == CRASHED)
383         iter.remove();
384     }
385 
386     // Update the status of each member
387     MemberId[] members = view.getMembers();
388     for (int i=0; i < members.length; i++) {
389       r = table.get(members[i]);
390       if (r != null) {
391 
392         /*
393          * The member id is already present in the table; if
394          * the member was partitioned, now its status is MERGING.
395          * In all other cases (NEWMEMBER, RECOVERING, SURVIVED, MERGING),
396          * the new status is SURVIVED
397          */
398         //
399         if (r.prev == PARTITIONED)
400           r.status = MERGING;
401         else
402           r.status = SURVIVED;
403 
404       } else {
405 
406         /*
407          * The member id is not present in the table; may be a new
408          * member or a recovered member.  For each endpoint identifier,
409          * we maintain a list of member identifiers associated with that
410          * endpoint.  This is useful to discover if this is just a new
411          * member, or it is a recovering member from a previous JVM
412          * (endpoint on the same port).
413          */
414         recordList = iptable.get(members[i].getEndPoint());
415         if (recordList == null) {
416 
417           /*
418            * First member from that endpoint; new member for sure
419            */
420           recordList = new ArrayList<Record>();
421           iptable.put(members[i].getEndPoint(), recordList);
422           r = new Record(NEWMEMBER, members[i]);
423           recordList.add(r);
424           table.put(members[i], r);
425 
426         } else {
427           r = recordList.get(0);
428 
429           if (members[i].isNewer(r.id)) {
430             /*
431              * New incarnation! Move old member ids to crashed status;
432              * Create a new empty record and put it in the tables.
433              */
434             for (int k=0; k < recordList.size(); k++) {
435               r = recordList.get(k);
436               r.status = CRASHED;
437               r.pos = -1;
438             }
439             recordList.clear();
440             r = new Record(RECOVERING, members[i]);
441             recordList.add(r);
442             table.put(members[i], r);
443 
444           } else {
445             /*
446              *  This member id has the same incarnation number of those
447              *  contained in the arraylist, but its member identifier
448              *  is not present in the table. If members from the same
449              *  host are recovering, so is this. Otherwise, it is a
450              *  new member.
451              */
452             if (r.status == RECOVERING)
453               r = new Record(RECOVERING, members[i]);
454             else
455               r = new Record(NEWMEMBER, members[i]);
456             recordList.add(r);
457             table.put(members[i], r);
458           }
459         }
460       }
461       r.pos = i;
462     }
463   }
464 
465 
466   /**
467    *  No effect.
468    */
469   public void hasLeft()
470   {
471   }
472 
473 
474   /**
475    *  No effect.
476    */
477   public void prepareChange()
478   {
479   }
480 
481 
482   ////////////////////////////////////////////////////////////////////////////////////////////
483   // Internal data structure
484   ////////////////////////////////////////////////////////////////////////////////////////////
485 
486   /**
487    *  Data structure used to maintain an element in the hashtable and its
488    *  status.
489    */
490   private final class Record
491     implements Serializable
492   {
493 
494     private static final long serialVersionUID = -710112890009914664L;
495 
496     MemberId  id;         // MemberId to which this value has been
497     int       pos;        // Position of the member in the view
498     int       status;     // State (RECOVERED, SURVIVED, MERGED, NEWMEMBER, CRASHED)
499     int       prev;       // Previous status
500     Object    value;      // The object stored by users of this data structure
501 
502     Record(int status, MemberId id) {
503       this.id     = id;
504       this.status = status;
505       this.pos    = -1;
506       this.prev   = status;
507       this.value  = null;
508     }
509 
510   } // END Record
511 
512 
513   ////////////////////////////////////////////////////////////////////////////////////////////
514   // Methods from the Externalizable interface
515   ////////////////////////////////////////////////////////////////////////////////////////////
516 
517   /*
518    * Note that the methods below are synchronized to avoid concurrent
519    * access to the internal tables of this membertable object.
520    */
521 
522   /* (non-Javadoc)
523    * @see java.io.Externalizable#writeExternal(java.io.ObjectOutput)
524    */
525   synchronized public void writeExternal(ObjectOutput out)
526     throws IOException
527   {
528     out.writeObject(table);
529     out.writeObject(iptable);
530   }
531 
532   /* (non-Javadoc)
533    * @see java.io.Externalizable#readExternal(java.io.ObjectInput)
534    */
535   @SuppressWarnings("unchecked")
536   synchronized public void readExternal(ObjectInput in)
537     throws IOException, ClassNotFoundException
538   {
539     table = (Map) in.readObject();
540     iptable = (Map) in.readObject();
541   }
542 
543 } // END MemberTable