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

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

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