当前位置:博客首页>>Python >> 阅读正文

python-DHT爬虫中路由表的实现

作者: 郑晓 分类: Python 发布于: 2016-08-22 12:31 浏览(2,306) 评论(11)


这是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通知即可。

本文出自 郑晓个人博客,转载时请注明出处及相应链接。

本文永久链接: https://www.zh30.com/python-dht-routetable.html

python-DHT爬虫中路由表的实现:目前有11 条留言

用户评论头像 严格的帅哥发表于 2016年12月15日 下午 01:52[回复]

关注了你

用户评论头像 虚心的锅饼发表于 2016年11月30日 下午 05:28[回复]

while len(nodes) < K <– 这里的k是什么东西 没有定义过啊

    用户评论头像 郑晓发表于 2016年11月30日 下午 05:31[回复]

    K是8, 就是每个桶的节点数量,一般都默认为8

用户评论头像 刘明野的博客发表于 2016年09月03日 下午 06:17[回复]

写的不错

用户评论头像 尚爱思笑话发表于 2016年08月30日 下午 03:38[回复]

感觉很不错的样子!

用户评论头像 恭顺的水母发表于 2016年08月30日 下午 03:26[回复]

用户评论头像 namechea发表于 2016年08月30日 下午 01:13[回复]

朋友,交换链接吗?

    用户评论头像 郑晓发表于 2016年08月30日 下午 01:17[回复]

    你什么站?

      用户评论头像 namechea发表于 2016年08月30日 下午 01:19[回复]

      这个站:52namesilo.com Namesilo

用户评论头像 米表发表于 2016年08月29日 上午 08:37[回复]

随便看看,随便转转!

用户评论头像 蒂欧娜发表于 2016年08月26日 下午 05:46[回复]

风吹过,我来过!

发表评论

由于某些原因,您暂时可能接收不到我回复后的邮件通知,抱歉。-- 2017-05-24

如需我主动联系您,可以留言注明。

change vcode