1 ## Copyright 2002 Andrew Loewenstern, All Rights Reserved
10 # The all-powerful, magical Kademlia "k" constant, bucket depth
13 # how many bits wide is our hash?
17 # the local routing table for a kademlia like distributed hash table
19 def __init__(self, node):
20 # this is the root node, a.k.a. US!
22 self.buckets = [KBucket([], 0L, 2L**HASH_LENGTH)]
25 def _bucketIndexForInt(self, int):
26 """returns the index of the bucket that should hold int"""
27 return bisect_left(self.buckets, int)
29 def findNodes(self, id):
30 """ return k nodes in our own local table closest to the ID
31 ignoreSelf means we will return K closest nodes to ourself if we search for our own ID
32 note, K closest nodes may actually include ourself, it's the callers responsibilty to
33 not send messages to itself if it matters
35 if type(id) == StringType:
37 elif type(id) == InstanceType:
39 elif type(id) == IntType or type(id) == LongType:
42 raise TypeError, "findLocalNodes requires an int, string, or Node instance type"
46 def sort(a, b, int=int):
47 """ this function is for sorting nodes relative to the ID we are looking for """
48 x, y = int ^ a.int, int ^ b.int
55 i = self._bucketIndexForInt(int)
57 ## see if this node is already in our table and return it
59 index = self.buckets[i].l.index(int)
63 self.buckets[i].touch()
64 return [self.buckets[i].l[index]]
66 nodes = nodes + self.buckets[i].l
74 while (len(nodes) < K and (min >= 0 and max < len(self.buckets))):
76 nodes = nodes + self.buckets[min].l
77 self.buckets[min].touch()
78 if max < len(self.buckets):
79 nodes = nodes + self.buckets[max].l
80 self.buckets[max].touch()
85 def _splitBucket(self, a):
86 diff = (a.max - a.min) / 2
87 b = KBucket([], a.max - diff, a.max)
88 self.buckets.insert(self.buckets.index(a.min) + 1, b)
90 # transfer nodes to new bucket
92 if anode.int >= a.max:
96 def replaceStaleNode(self, stale, new):
97 """ this is used by clients to replace a node returned by insertNode after
98 it fails to respond to a Pong message
100 i = self._bucketIndexForInt(stale.int)
102 it = self.buckets[i].l.index(stale.int)
106 del(self.buckets[i].l[it])
107 self.buckets[i].l.append(new)
109 def insertNode(self, node):
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!!
114 # get the bucket for this node
115 i = self. _bucketIndexForInt(node.int)
116 ## check to see if node is in the bucket already
118 it = self.buckets[i].l.index(node.int)
123 node.updateLastSeen()
124 # move node to end of bucket
125 del(self.buckets[i].l[it])
126 self.buckets[i].l.append(node)
127 self.buckets[i].touch()
130 # we don't have this node, check to see if the bucket is full
131 if len(self.buckets[i].l) < K:
132 # no, append this node and return
133 self.buckets[i].l.append(node)
134 self.buckets[i].touch()
137 # bucket is full, check to see if self.node is in the bucket
139 me = self.buckets[i].l.index(self.node)
141 return self.buckets[i].l[0]
143 ## this bucket is full and contains our node, split the bucket
144 if len(self.buckets) >= HASH_LENGTH:
146 print "Hash Table is FULL! Increase K!"
149 self._splitBucket(self.buckets[i])
151 ## now that the bucket is split and balanced, try to insert the node again
152 return self.insertNode(node)
154 def justSeenNode(self, node):
155 """ call this any time you get a message from a node, to update it in the table if it's there """
157 n = self.findNodes(node.int)[0]
167 __slots = ['min', 'max', 'lastAccessed']
168 def __init__(self, contents, min, max):
172 self.lastAccessed = time.time()
175 self.lastAccessed = time.time()
177 def getNodeWithInt(self, int):
179 return self.l[self.l.index(int)]
185 return "<KBucket items: %d min: %d\tmax: %d>" % (len(self.l), self.min, self.max)
187 ## comparators, necessary for bisecting list of buckets with a hash expressed as an integer or a distance
188 ## compares integer or node object with the bucket's range
190 if type(a) == InstanceType:
194 if type(a) == InstanceType:
198 if type(a) == InstanceType:
202 if type(a) == InstanceType:
206 if type(a) == InstanceType:
208 return self.min <= a and self.max > a
210 if type(a) == InstanceType:
212 return self.min >= a or self.max < a
219 class TestKTable(unittest.TestCase):
221 self.a = Node(hash.newID(), 'localhost', 2002)
222 self.t = KTable(self.a)
224 def test_replace_stale_node(self):
225 self.b = Node(hash.newID(), 'localhost', 2003)
226 self.t.replaceStaleNode(self.a, self.b)
227 assert(len(self.t.buckets[0].l) == 1)
228 assert(self.t.buckets[0].l[0].id == self.b.id)
230 if __name__ == "__main__":