1 ## Copyright 2002 Andrew Loewenstern, All Rights Reserved
11 # The all-powerful, magical Kademlia "k" constant, bucket depth
14 # how many bits wide is our hash?
18 # the local routing table for a kademlia like distributed hash table
20 def __init__(self, node):
21 # this is the root node, a.k.a. US!
23 self.buckets = [KBucket([], 0L, 2L**HASH_LENGTH)]
26 def _bucketIndexForInt(self, int):
27 """returns the index of the bucket that should hold int"""
28 return bisect_left(self.buckets, int)
30 def findNodes(self, id):
31 """ return k nodes in our own local table closest to the ID
32 ignoreSelf means we will return K closest nodes to ourself if we search for our own ID
33 note, K closest nodes may actually include ourself, it's the callers responsibilty to
34 not send messages to itself if it matters
36 if type(id) == StringType:
38 elif type(id) == InstanceType:
40 elif type(id) == IntType or type(id) == LongType:
43 raise TypeError, "findLocalNodes requires an int, string, or Node instance type"
47 def sort(a, b, int=int):
48 """ this function is for sorting nodes relative to the ID we are looking for """
49 x, y = int ^ a.int, int ^ b.int
56 i = self._bucketIndexForInt(int)
58 ## see if this node is already in our table and return it
60 index = self.buckets[i].l.index(int)
64 return [self.buckets[i].l[index]]
66 nodes = nodes + self.buckets[i].l
74 while (len(nodes) < K and (min >= 0 or max < len(self.buckets))):
76 nodes = nodes + self.buckets[min].l
77 if max < len(self.buckets):
78 nodes = nodes + self.buckets[max].l
84 def _splitBucket(self, a):
85 diff = (a.max - a.min) / 2
86 b = KBucket([], a.max - diff, a.max)
87 self.buckets.insert(self.buckets.index(a.min) + 1, b)
89 # transfer nodes to new bucket
91 if anode.int >= a.max:
95 def replaceStaleNode(self, stale, new):
96 """ this is used by clients to replace a node returned by insertNode after
97 it fails to respond to a Pong message
99 i = self._bucketIndexForInt(stale.int)
101 it = self.buckets[i].l.index(stale.int)
105 del(self.buckets[i].l[it])
107 self.buckets[i].l.append(new)
109 def insertNode(self, node, contacted=1):
111 this insert the node, returning None if successful, returns the oldest node in the bucket if it's full
112 the caller responsible for pinging the returned node and calling replaceStaleNode if it is found to be stale!!
113 contacted means that yes, we contacted THEM and we know the node is available
115 assert(node.id != " "*20)
116 if node.id == self.node.id:
118 # get the bucket for this node
119 i = self. _bucketIndexForInt(node.int)
120 ## check to see if node is in the bucket already
122 it = self.buckets[i].l.index(node.int)
128 node.updateLastSeen()
129 # move node to end of bucket
130 xnode = self.buckets[i].l[it]
131 del(self.buckets[i].l[it])
132 # note that we removed the original and replaced it with the new one
133 # utilizing this nodes new contact info
134 self.buckets[i].l.append(xnode)
135 self.buckets[i].touch()
138 # we don't have this node, check to see if the bucket is full
139 if len(self.buckets[i].l) < K:
140 # no, append this node and return
142 node.updateLastSeen()
143 self.buckets[i].l.append(node)
144 self.buckets[i].touch()
147 # bucket is full, check to see if self.node is in the bucket
149 me = self.buckets[i].min <= self.node < self.buckets[i].max
151 return self.buckets[i].l[0]
153 ## this bucket is full and contains our node, split the bucket
154 if len(self.buckets) >= HASH_LENGTH:
156 print "Hash Table is FULL! Increase K!"
159 self._splitBucket(self.buckets[i])
161 ## now that the bucket is split and balanced, try to insert the node again
162 return self.insertNode(node)
164 def justSeenNode(self, node):
165 """ call this any time you get a message from a node, to update it in the table if it's there """
167 n = self.findNodes(node.int)[0]
175 def nodeFailed(self, node):
176 """ call this when a node fails to respond to a message, to invalidate that node """
178 n = self.findNodes(node.int)[0]
182 if(n.msgFailed() >= const.MAX_FAILURES):
183 self.replaceStaleNode(n, None)
186 __slots = ['min', 'max', 'lastAccessed']
187 def __init__(self, contents, min, max):
191 self.lastAccessed = time.time()
194 self.lastAccessed = time.time()
196 def getNodeWithInt(self, int):
198 return self.l[self.l.index(int)]
203 return "<KBucket items: %d min: %d\tmax: %d>" % (len(self.l), self.min, self.max)
205 ## comparators, necessary for bisecting list of buckets with a hash expressed as an integer or a distance
206 ## compares integer or node object with the bucket's range
208 if type(a) == InstanceType:
212 if type(a) == InstanceType:
216 if type(a) == InstanceType:
220 if type(a) == InstanceType:
224 if type(a) == InstanceType:
226 return self.min <= a and self.max > a
228 if type(a) == InstanceType:
230 return self.min >= a or self.max < a
237 class TestKTable(unittest.TestCase):
239 self.a = Node().init(hash.newID(), 'localhost', 2002)
240 self.t = KTable(self.a)
242 def test_replace_stale_node(self):
243 self.b = Node().init(hash.newID(), 'localhost', 2003)
244 self.t.replaceStaleNode(self.a, self.b)
245 assert(len(self.t.buckets[0].l) == 1)
246 assert(self.t.buckets[0].l[0].id == self.b.id)
248 if __name__ == "__main__":