Source code: com/ubermq/chord/AbstractChordInfrastructure.java
1 package com.ubermq.chord;
2
3 /**
4 * An abstract implementation of the key chord algorithms that provide
5 * the nice peer-to-peer lookup features of Chord. This includes
6 * <code>O(log n)</code> lookup times, and <code>O(log2 n)</code>
7 * join/leave times. <P>
8 *
9 * Subclasses of this need to implement actual connectivity between
10 * remote nodes. <P>
11 */
12 import java.rmi.*;
13
14 public abstract class AbstractChordInfrastructure
15 implements ChordInfrastructure
16 {
17 /**
18 * The identifier factory that can be used to create
19 * chord identifiers.
20 */
21 protected final ChordIdentifierFactory identifierFactory;
22
23 // how many successors should contain data (replication factor)
24 private int replication;
25
26 /**
27 * Creates an abstract chord infrastructure object, given
28 * an identifier factory.
29 *
30 * @param f the identifier factory to use
31 * @param m the size of each node's finger table
32 * @param replication how many nodes should retain data for redundancy
33 */
34 protected AbstractChordInfrastructure(ChordIdentifierFactory f,
35 int replication)
36 {
37 this.identifierFactory = f;
38 this.replication = replication;
39 }
40
41 /**
42 * Queries the infrastructure for the value associated with a key.
43 * Since a query operation is computationally and network intensive,
44 * it is assumed that nodes have some expectation that the given key
45 * resides somewhere in the infrastructure.<P>
46 *
47 * @param key the key to query.
48 * @return the object stored with the key.
49 * @throws ItemNotFoundException if the key is not found in the
50 * infrastructure.
51 * @throws RemoteException if the network is unavailable.
52 */
53 public Object query(Object key)
54 throws java.rmi.RemoteException
55 {
56 ChordNode s = findSuccessor(identifierFactory.createIdentifier(key));
57 try {
58 return s.query(key);
59 } catch(IllegalStateException ise) {
60 throw new RemoteException(ise.getMessage());
61 }
62 }
63
64 /**
65 * Stores the given value at the specified key, somewhere in the
66 * chord infrastructure. In the absence of concurrent modification,
67 * it is true that:<p>
68 *
69 * <code>
70 * given i.store(key, v), then
71 * v == i.query(key);
72 * </code>
73 * <P>
74 *
75 * By design, clients should not need to be aware of physically
76 * where the information associated with the key is stored.
77 *
78 * @param key the key at which the value is stored
79 * @param value the value to store
80 * @throws RemoteException if the infrastructure is unavailable.
81 */
82 public void store(Object key, Object value)
83 throws java.rmi.RemoteException
84 {
85 ChordNode s = findSuccessor(identifierFactory.createIdentifier(key));
86
87 try {
88 ChordNode x = s;
89 int n=0;
90 do {
91 x.store(key, value);
92 x = x.successor();
93 } while(!s.equals(x) && ++n < replication);
94 } catch(IllegalStateException ise) {
95 throw new RemoteException(ise.getMessage());
96 }
97 }
98
99 /**
100 * Returns the node that follows the specified identifier
101 * on the identifier circle. This node is known as the
102 * <i>successor</i>, and is in charge of storing keys
103 * for the given identifier.
104 *
105 * @param id an identifier
106 * @return the successor node.
107 */
108 public ChordNode findSuccessor(ChordIdentifier id)
109 {
110 return findPredecessor(id).successor();
111 }
112
113 /**
114 * Returns the node that precedes the specified identifier
115 * on the identifier circle.
116 *
117 * @param id an identifier
118 * @return the predecessor node.
119 */
120 public ChordNode findPredecessor(ChordIdentifier id)
121 {
122 ChordNode n = entryPoint();
123 while(!Interval.elementOf(id, n.identifier(), n.successor().identifier(), true, false))
124 n = n.closestPrecedingFinger(id);
125
126 return n;
127 }
128
129 }