Source code: com/ubermq/chord/AbstractChordNode.java
1 package com.ubermq.chord;
2
3 /**
4 * An abstract implementation of a chord node. Provides default implementations
5 * for some key Chord algorithms that can be inherited by most subclasses.
6 */
7 import java.util.*;
8
9 public abstract class AbstractChordNode
10 implements ChordNode
11 {
12 // the infrastructure i have joined.
13 // this is effectively final
14 private ChordInfrastructure infrastructure;
15
16 // my identifier
17 private final ChordIdentifier identifier;
18
19 // my neighbors
20 private ChordNode predecessor;
21
22 // my finger table
23 private final List fingers;
24
25 // a random number generator
26 private static final Random random = new Random();
27
28 /**
29 * Creates an abstract chord node with the given identifier.
30 * The successor, predecessor and finger tables will be
31 * null until the node <code>join</code>s an infrastructure.
32 *
33 * @param ident the identifier for this node
34 * @param m the size of the finger table
35 * @param fingerInitialValue the initial value to store as each
36 * finger entry.
37 */
38 protected AbstractChordNode(ChordIdentifier ident,
39 int m,
40 ChordNode fingerInitialValue)
41 {
42 this.identifier = ident;
43 this.fingers = Collections.synchronizedList(new ArrayList(m));
44 for (int i = 0; i < m; i++)
45 {
46 fingers.add(fingerInitialValue);
47 }
48 }
49
50 public final ChordIdentifier identifier()
51 {
52 return identifier;
53 }
54
55 public final ChordNode successor()
56 {
57 return (ChordNode)fingers.get(0);
58 }
59
60 public final ChordNode predecessor()
61 {
62 return predecessor;
63 }
64
65 public final ChordNode[] fingers()
66 {
67 return (ChordNode[])fingers.toArray(new ChordNode[0]);
68 }
69
70 /**
71 * The default implementation of join relies on the
72 * stabilize protocol to setup finger table entries
73 * over time.
74 */
75 public void join(ChordInfrastructure i)
76 {
77 if (this.infrastructure != null)
78 throw new IllegalStateException("already joined an infrastructure.");
79
80 this.predecessor = null;
81 this.fingers.set(0, i.findSuccessor(identifier));
82 this.infrastructure = i;
83
84 com.ubermq.Utility.getLogger().fine("join() found successor: " + successor());
85 successor().notify(this);
86 }
87
88 public void leave(ChordInfrastructure i)
89 {
90 // move my items to my successor
91 Iterator iter = keys().iterator();
92 while (iter.hasNext())
93 {
94 Object element = iter.next();
95 moveItem(element, successor());
96 }
97
98 // i am gone. tell my successor and predecessor
99 successor().notifyGoingAway(this);
100 if (predecessor != null)
101 predecessor.notifyGoingAway(this);
102
103 // note that we do not allow rejoining here, for simplicity
104 }
105
106 /**
107 * Stabilizes this node by verifying the immediate successor node
108 * is correct. We also notify the successor about ourselves so it
109 * knows that we are the correct predecessor.<P>
110 *
111 * This method should be executed periodically to ensure correctness.
112 */
113 public void stabilize()
114 {
115 ChordNode x = successor().predecessor();
116 if (x != null &&
117 Interval.elementOf(x.identifier(),
118 identifier,
119 successor().identifier(),
120 false, true))
121 {
122 fingers.set(0, x);
123 }
124
125 // tell the successor that we are the predecessor.
126 successor().notify(this);
127 }
128
129 /**
130 * Fixes the finger table. Chooses a finger at random and updates
131 * it. This method should be executed periodically to ensure correctness.
132 */
133 public void fixFingers()
134 {
135 if (infrastructure != null)
136 {
137 int i = random.nextInt(fingers.size() - 1);
138 ChordNode s = infrastructure.findSuccessor(identifier.nextFinger(i + 1));
139 fingers.set(i + 1, s);
140
141 com.ubermq.Utility.getLogger().fine(identifier() + " fixed finger " + (i + 1) + " to point to " + s);
142 }
143 }
144
145 /**
146 * Notifies us that x is our predecessor.
147 */
148 public void notify(ChordNode x)
149 {
150 com.ubermq.Utility.getLogger().fine("notification from " + x + " that it precedes me (" + this + ")");
151
152 // if the specified node is closer than the predecessor we
153 // currently have, but not beyond us, update.
154 ChordNode oldPredecessor = predecessor;
155 if (predecessor == null ||
156 (Interval.elementOf(x.identifier(),
157 predecessor.identifier(),
158 identifier,
159 true, true)))
160 predecessor = x;
161
162 // figure out what items need to be moved
163 if (!predecessor.equals(oldPredecessor) ||
164 oldPredecessor == null)
165 {
166 Iterator iter = keys().iterator();
167 while (iter.hasNext())
168 {
169 Object key = iter.next();
170 ChordIdentifier keyId = identifier().factory().createIdentifier(key);
171
172 if (Interval.elementOf(keyId,
173 oldPredecessor == null ? identifier() : oldPredecessor.identifier(),
174 predecessor.identifier(),
175 false,
176 true))
177 moveItem(key, predecessor);
178
179 }
180 }
181 }
182
183 public void notifyGoingAway(ChordNode x)
184 {
185 if (x.equals(predecessor())) {
186 // ok, our new predecessor is x.predecessor()
187 predecessor = x.predecessor();
188 com.ubermq.Utility.getLogger().fine(x + " is going away. new predecessor is " + predecessor());
189 } else if (x.equals(successor())) {
190 // ok, our new successor is x.successor()
191 fingers.set(0, x.successor());
192 com.ubermq.Utility.getLogger().fine(x + " is going away. new successor is " + successor());
193 }
194 }
195
196 /**
197 * Returns the element of the finger table
198 * that most closely precedes the given identifier.<P>
199 *
200 * This is an implementation of the algorithm specified
201 * in the Chord paper [Stoica, et al] in Figure 4.<P>
202 *
203 * @return a ChordNode representing the closest finger to the identifier.
204 */
205 public ChordNode closestPrecedingFinger(ChordIdentifier id)
206 {
207 for (int i = fingers.size() - 1; i >= 0; i--)
208 {
209 if (Interval.elementOf(((ChordNode)fingers.get(i)).identifier(),
210 identifier,
211 id,
212 false, true))
213 return (ChordNode)fingers.get(i);
214 }
215
216 return this;
217 }
218
219 public int hashCode()
220 {
221 return identifier.hashCode();
222 }
223
224 /**
225 * Tests for equality based exclusively on the identifier value. This may
226 * return true if the objects are not truly functionally equivalent, such as
227 * if one object represents a local node and one represents a remote node.
228 */
229 public boolean equals(Object o)
230 {
231 if (o instanceof ChordNode)
232 {
233 return ((ChordNode)o).identifier().equals(identifier());
234 }
235 else return false;
236 }
237
238 public String toHtml()
239 {
240 return toString();
241 }
242
243 /**
244 * Returns a collection of keys that are stored locally at
245 * this node. This method is implemented by subclasses for
246 * use by algorithms implemented in this object.
247 */
248 protected abstract Collection keys();
249
250 /**
251 * Moves an item from the local data store to another
252 * node as specified. This is an abstract method so
253 * subclasses can make choices like retaining
254 * the moved item, or ignoring the move request altogether.
255 */
256 protected abstract void moveItem(Object key,
257 ChordNode destination);
258 }
259