这是DHT协议中路由表的实现。 在DHT网络中，各节点保持路由表(table )，表中存储有取得状态良好的节点(node )。 路由表还分为多个区间桶，节点应该存储在这些桶中，空表只有一个桶。 桶装满后，无法将其插入桶中，除非当前节点(自己) ID位于此桶中。 在这种情况下，原始桶分裂成两个相同大小的桶，旧桶的节点被重新分配给新的子桶。 具体细节请参考DHT协议。
以下代码逻辑主要来源于QQ销售号平台，但我只更改了两个bug。
#coding:utf-8
fromtimeimporttime
fromhashlibimportsha1
框架制造商
生成#20字节长度的node_id
defnode_id(:
hash=sha1 ()。
s=' '.join (randint (0，255 ) (foriinxrange ) 20 ) )
是hash.update(s )
returnhash.digest (
返回Node_id的十进制长整数表示node_id-16-10
efint_ify(NID ) :
资产len (NID )==20
返回长整型(NID.encode ) ' HEX '，16 )。
#node节点类每个节点都有id、ip和端口属性，用于重新定义节点的不等于和不等于操作
类知识文库
def__init__(self，nid，ip，port ) :
self.nid=nid
self.ip=ip
self.port=port
def__eq__(self，other ) :
returnself.nid==other.nid
def__ne__(self，other ) :
returnself.nid！=other.nid
#满满一桶的异常类
classBucketFull:
通过
#bucket桶类
classKBucket:
def__init__(self，min，max ) :
self.min=min
self.max=max
self.nodes=[]
self.lasttime=time(#当前桶的上次更新时间
#检查一个node_id是否在桶的范围内
defnid_in_range(self，NID ) :
returnself.min=int_ify(NID ) self.max
#在桶中添加节点
efappend(self，node ) :
iflen(node.NID )！=2033 360返回
iflen(self.nodes ) 8:
ifnodeinself.nodes:
self.nodes.remove(node )
self.nodes.append(node )
else:
self.nodes.append(node )
self.lastTime=time (
else:
射频备份完全
#路由表类
classKTable:
def__init__(self，nid ) :
self.nid=nid
self.nodeTotal=0；
self.buckets=[ kbucket (0，2 * * 160 ) ]#路由表中的所有桶的列表缺省情况下只有一个桶
#向路由表中添加节点。 也就是说，将节点添加到表的其中一个桶中，并在桶填满时进行拆分
efappend(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
r> 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通知即可。