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 self.buckets[i].touch()
65 return [self.buckets[i].l[index]]
67 nodes = nodes + self.buckets[i].l
75 while (len(nodes) < K and (min >= 0 and max < len(self.buckets))):
77 nodes = nodes + self.buckets[min].l
78 self.buckets[min].touch()
79 if max < len(self.buckets):
80 nodes = nodes + self.buckets[max].l
81 self.buckets[max].touch()
86 def _splitBucket(self, a):
87 diff = (a.max - a.min) / 2
88 b = KBucket([], a.max - diff, a.max)
89 self.buckets.insert(self.buckets.index(a.min) + 1, b)
91 # transfer nodes to new bucket
93 if anode.int >= a.max:
97 def replaceStaleNode(self, stale, new):
98 """ this is used by clients to replace a node returned by insertNode after
99 it fails to respond to a Pong message
101 i = self._bucketIndexForInt(stale.int)
103 it = self.buckets[i].l.index(stale.int)
107 del(self.buckets[i].l[it])
109 self.buckets[i].l.append(new)
111 def insertNode(self, node):
113 this insert the node, returning None if successful, returns the oldest node in the bucket if it's full
114 the caller responsible for pinging the returned node and calling replaceStaleNode if it is found to be stale!!
116 assert(node.id != " "*20)
117 # get the bucket for this node
118 i = self. _bucketIndexForInt(node.int)
119 ## check to see if node is in the bucket already
121 it = self.buckets[i].l.index(node.int)
126 node.updateLastSeen()
127 # move node to end of bucket
128 del(self.buckets[i].l[it])
129 self.buckets[i].l.append(node)
130 self.buckets[i].touch()
133 # we don't have this node, check to see if the bucket is full
134 if len(self.buckets[i].l) < K:
135 # no, append this node and return
136 self.buckets[i].l.append(node)
137 self.buckets[i].touch()
140 # bucket is full, check to see if self.node is in the bucket
142 me = self.buckets[i].l.index(self.node)
144 return self.buckets[i].l[0]
146 ## this bucket is full and contains our node, split the bucket
147 if len(self.buckets) >= HASH_LENGTH:
149 print "Hash Table is FULL! Increase K!"
152 self._splitBucket(self.buckets[i])
154 ## now that the bucket is split and balanced, try to insert the node again
155 return self.insertNode(node)
157 def justSeenNode(self, node):
158 """ call this any time you get a message from a node, to update it in the table if it's there """
160 n = self.findNodes(node.int)[0]
168 def nodeFailed(self, node):
169 """ call this when a node fails to respond to a message, to invalidate that node """
171 n = self.findNodes(node.int)[0]
175 if(n.msgFailed() >= const.MAX_FAILURES):
176 self.replaceStaleNode(n, None)
179 __slots = ['min', 'max', 'lastAccessed']
180 def __init__(self, contents, min, max):
184 self.lastAccessed = time.time()
187 self.lastAccessed = time.time()
189 def getNodeWithInt(self, int):
191 return self.l[self.l.index(int)]
197 return "<KBucket items: %d min: %d\tmax: %d>" % (len(self.l), self.min, self.max)
199 ## comparators, necessary for bisecting list of buckets with a hash expressed as an integer or a distance
200 ## compares integer or node object with the bucket's range
202 if type(a) == InstanceType:
206 if type(a) == InstanceType:
210 if type(a) == InstanceType:
214 if type(a) == InstanceType:
218 if type(a) == InstanceType:
220 return self.min <= a and self.max > a
222 if type(a) == InstanceType:
224 return self.min >= a or self.max < a
231 class TestKTable(unittest.TestCase):
233 self.a = Node().init(hash.newID(), 'localhost', 2002)
234 self.t = KTable(self.a)
236 def test_replace_stale_node(self):
237 self.b = Node().init(hash.newID(), 'localhost', 2003)
238 self.t.replaceStaleNode(self.a, self.b)
239 assert(len(self.t.buckets[0].l) == 1)
240 assert(self.t.buckets[0].l[0].id == self.b.id)
242 if __name__ == "__main__":