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