这是DHT协议中路由表的实现，在DHT网络中，每个节点维护着一张路由表(table)，表中储存着已获取的状态良好的节点(node)。路由表又被划分为多个区间桶(bucket)，节点应该储存在这些桶中，空的表只有一个桶。当桶满时不能再插入该桶中，除非当前节点（自己）ID也在这个桶中，在这种情况下，原桶需分裂为两个相同大小的桶，旧桶中的节点重新分配到新的子桶中。具体细节可查阅DHT协议。

以下代码逻辑主要来源于网络，我只是改了两个bug。。。

#coding:utf-8
from time import time
from hashlib import sha1
from random import randint
#生成一个20字节长度的node_id
def node_id():
hash = sha1()
s = "".join(chr(randint(0, 255)) for i in xrange(20))
hash.update(s)
return hash.digest()
#返回Node_id的10进制长整型表示 node_id->16->10
def int_ify(nid):
assert len(nid) == 20
return long(nid.encode('hex'), 16)
#node 节点类 每个节点都有id、ip和端口属性 重新定义了节点的等于和不等于操作
class KNode:
def __init__(self, nid, ip, port):
self.nid = nid
self.ip = ip
self.port = port
def __eq__(self, other):
return self.nid == other.nid
def __ne__(self, other):
return self.nid != other.nid
#桶满的异常类
class BucketFull:
pass
#bucket 桶类
class KBucket:
def __init__(self, min, max):
self.min = min
self.max = max
self.nodes = []
self.lastTime = time() #当前桶的最后更新时间
#检查一个node_id是否在桶的范围内
def nid_in_range(self, nid):
return self.min <= int_ify(nid) < self.max #向桶中添加节点 def append(self, node): if len(node.nid) != 20: return if len(self.nodes) < 8: if node in self.nodes: self.nodes.remove(node) self.nodes.append(node) else: self.nodes.append(node) self.lastTime = time() else: raise BucketFull#路由表类class KTable: def __init__(self, nid): self.nid = nid self.nodeTotal = 0; self.buckets = [KBucket(0, 2 ** 160)] #路由表中所有的桶的列表 默认只有一个桶 #向路由表添加节点，即向表中某个桶中添加节点，桶满时要进行拆分 def append(self, node): if node.nid == self.nid: return index = self.bucket_index(node.nid) bucket = self.buckets[index] try: bucket.append(node) self.nodeTotal = self.nodeTotal+1 except BucketFull: if not bucket.nid_in_range(self.nid): return self.split_bucket(index) self.append(node) #返回待添加节点id应该在哪个桶的范围中 def bucket_index(self, nid): for index, bucket in enumerate(self.buckets): if bucket.nid_in_range(nid): return index return index #拆分桶 def split_bucket(self, index): old = self.buckets[index] point = old.max - (old.max - old.min)/2 new = KBucket(point, old.max) old.max = point self.buckets.insert(index + 1, new) for node in old.nodes: if new.nid_in_range(node.nid): new.append(node) for node in new.nodes: old.nodes.remove(node) #返回离目标最近的8个node def get_neighbor(self, target): nodes = [] if len(self.buckets) == 0: return nodes index = self.bucket_index(target) nodes = self.buckets[index].nodes min = index - 1 max = index + 1 while len(nodes) < K and (min >= 0 or max < len(self.buckets)): if min >= 0:
nodes.extend(self.buckets[min].nodes)
if max < len(self.buckets): nodes.extend(self.buckets[max].nodes) min -= 1 max += 1 num = int_ify(target) nodes.sort(lambda a, b, num=num: cmp(num^int_ify(a.nid), num^int_ify(b.nid))) return nodes[:8] #打印调试信息 def print_info(self): print '桶数量:'+str(len(self.buckets)) print '节点量:'+str(self.nodeTotal)#Demo#实例化出路由表， 随机生成一千个node，放入表中并打印表的状态routeTable = KTable(node_id())for i in xrange(0,1000): routeTable.append(KNode(node_id(), '127.0.0.1', '80012'))routeTable.print_info()
打印出的结果显示路由表中的桶和节点数量十分有限，说明有大量的节点已经被抛弃，原因在代码中的第67行，当待加入节点所需要加入的桶已满且自身id不在这个桶中时直接忽略。
由于这种路由表实现复杂、需要不停的ping检查每个节点是否有效且储存的节点数量有限。实际做DHT爬虫时可不实现，爬虫只需要不停的认识新的node，并获取资源infohash，所以直接通过向有效的node发送完find_node后即可删除该node，只需等待node发送的get_peers和announce_peer通知即可。