這是DHT協(xié)議中路由表的實現(xiàn)，在DHT網(wǎng)絡(luò)中，每個節(jié)點維護(hù)著一張路由表(table)，表中儲存著已獲取的狀態(tài)良好的節(jié)點(node)。路由表又被劃分為多個區(qū)間桶(bucket)，節(jié)點應(yīng)該儲存在這些桶中，空的表只有一個桶。當(dāng)桶滿時不能再插入該桶中，除非當(dāng)前節(jié)點（自己）ID也在這個桶中，在這種情況下，原桶需分裂為兩個相同大小的桶，舊桶中的節(jié)點重新分配到新的子桶中。具體細(xì)節(jié)可查閱DHT協(xié)議。

以下代碼邏輯主要來源于網(wǎng)絡(luò)，我只是改了兩個bug。。。

#coding:utf-8
from time import time
from hashlib import sha1
from random import randint
#生成一個20字節(jié)長度的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進(jìn)制長整型表示 node_id->16->10
def int_ify(nid):
assert len(nid) == 20
return long(nid.encode('hex'), 16)
#node 節(jié)點類 每個節(jié)點都有id、ip和端口屬性 重新定義了節(jié)點的等于和不等于操作
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() #當(dāng)前桶的最后更新時間
#檢查一個node_id是否在桶的范圍內(nèi)
def nid_in_range(self, nid):
return self.min <= int_ify(nid) < self.max #向桶中添加節(jié)點 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)] #路由表中所有的桶的列表 默認(rèn)只有一個桶 #向路由表添加節(jié)點，即向表中某個桶中添加節(jié)點，桶滿時要進(jìn)行拆分 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) #返回待添加節(jié)點id應(yīng)該在哪個桶的范圍中 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) #返回離目標(biāo)最近的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] #打印調(diào)試信息 def print_info(self): print '桶數(shù)量:'+str(len(self.buckets)) print '節(jié)點量:'+str(self.nodeTotal) #Demo #實例化出路由表， 隨機(jī)生成一千個node，放入表中并打印表的狀態(tài) routeTable = KTable(node_id()) for i in xrange(0,1000): routeTable.append(KNode(node_id(), '127.0.0.1', '80012')) routeTable.print_info()
打印出的結(jié)果顯示路由表中的桶和節(jié)點數(shù)量十分有限，說明有大量的節(jié)點已經(jīng)被拋棄，原因在代碼中的第67行，當(dāng)待加入節(jié)點所需要加入的桶已滿且自身id不在這個桶中時直接忽略。
由于這種路由表實現(xiàn)復(fù)雜、需要不停的ping檢查每個節(jié)點是否有效且儲存的節(jié)點數(shù)量有限。實際做DHT爬蟲時可不實現(xiàn)，爬蟲只需要不停的認(rèn)識新的node，并獲取資源infohash，所以直接通過向有效的node發(fā)送完find_node后即可刪除該node，只需等待node發(fā)送的get_peers和announce_peer通知即可。