文档章节

布隆过滤器(bloomfilter)在DHT爬虫中的应用

 死鱼
发布于 2015/07/15 10:19
字数 890
阅读 126
收藏 2

广大网民下载资源的方式还是以BT,磁力链搜索为主,而BT种子的来源就是DHT网络。

 

尝试着写了一个DHT的爬虫, DHT协议中,种子的获取源自两个请求,

1         get_peer,是别的客户端向你请求某个infohash的下载地址

2         announce_peer, 是某个客户端通知你他正在上传/下载某个infohash,他可以作为该infohash的源

 

根据这两个请求的描述,大家也不难看出,采集到的infohash的重复率很高,怎么去保证一个DHT爬虫过滤掉重复的数据呢?

 

一个infohash40个字节的字符串,如0fe6b765f95746aee440fc2552dd59b58c6b5460

Infohash实际是 SHA1算法的出来的一个哈希值,实际是一个20字节的byte序列。某些语言可能不太方便直接用这么一个来做字典的KEY

 

大概估计了一下种子的总数, 20个字节的SHA1,实际上是有 2160次方信息量。数据太大不好评估,而实际的种子数,我只好通过一些成熟的资源网站去统计,如www.btkitty.com有大约 2800万的数据,www.btmay.com也有大几百万的数据。看来数据规模大概是千万级的样子。

 

如果要生成一个1000万条数据的字典,大概需要  40 * 1000 * 10000 字节= 400M 内存。这个大小的内存对于现在的VPS配置来说其实也还好,但是爬虫不可能瞬间爬完所有的数据,为了记录上一次爬了哪些,这400M的字典会定时写一下磁盘。400M写次硬盘就是好几秒钟的事了,如果数据规模比想象中的更大一点,字典到了TB级别的,那就更夸张了。

 

所以这里可以用布隆过滤器,当然也有些其他的措施,但是布隆过滤器在这里是一个很优秀的选择。能够用相对小的内存占用解决去重的问题,但是布隆过滤器也有些缺点。详细的大家可以找下布隆过滤器的说明,网上布隆过滤器大都是概念上的说明,很少有源码的实现。本身也是因为布隆过滤器需要根据具体的环境设计其算法,这里我就直接附上详细的设计思路了。

 

我是将infohash 6hash函数映射到了63字节的小字典里。字典的直接存成了定长的bytearray, 因此内存占用固定为0xFFFFFF/8 * 6 = 12MB理论上能容纳的信息量是2**144。实际用100万的数据做单元测试,出错率为0。所以实际上还能更节省的,比如说少用一个hash算法或者将其中几个hash的长度再减少一点

 

思路清晰了,编码就很简单了,需要实现的接口就是set_flag check_flag save load

//判断是否重复。 6hash算法都是True才是True

def check_flag(s):

    s = s.lower()

    for i in xrange(6):

        n = bloom_filter_func_list[i](s)

        n1 = n >> 3

        n2 = n & 7

        b = bloom_filter_map_list[i]

        if b[n1] & (1 << n2) == 0:

            return False

return True      

 

至于几种hash算法,推荐用djb, dek, 另外infohash本身就是hash算法生成的,直接从里面截取几个字节都是不错的选择,如int(infohash[24:30], 16)


© 著作权归作者所有

粉丝 2
博文 1
码字总数 890
作品 1
武汉
私信 提问
加载中

评论(1)

cih315
cih315
83
Google Guava 中的布隆过滤

在 Guava 项目的11.0版中,一个新的类添加了进来—— BloomFilter(布隆过滤器)类。布隆过滤器是一种独特的数据结构,用以表明元素是否被保存在一个集合(Set)中。有趣的是,布隆过滤器能够...

可观
2013/01/25
6.1K
1
布隆过滤器之Counting Bloom Filter

---title: 布隆过滤器之Counting Bloom Filtersubtitle: Counting Bloom Filterdescription: Spectral Bloom Filterkeywords: [算法,bloom filter,布隆]author: liyzdate: 2019-01-11tags: ......

freeli
01/14
0
0
BitSet和布隆过滤器(Bloom Filter)

布隆过滤器 Bloom Filter 是由Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。如果检测结果为是,该元素不一定...

凯文加内特
2016/01/15
187
0
BloomFilter布隆过滤器使用

从上一篇可以得知,BloomFilter的关键在于hash算法的设定和bit数组的大小确定,通过权衡得到一个错误概率可以接受的结果。 算法比较复杂,也不是我们研究的范畴,我们直接使用已有的实现。 ...

辣妈程序媛
2018/03/11
0
0
HBase相关文章索引(1)

工具资源 利用phoenix进行Hbase数据访问 在SQUIRREL中使用PHOENIX操作HBASE——创建表和视图 模拟 SQL 的形式进行 Hbase 数据访问 环境部署 hbase 单机、伪分布、完全分布部署 基本常识 hbas...

司小幽
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周二乱弹 —— 吾不好梦中插人

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @鱼豆腐233 :#今日歌曲分享# 分享My Chemical Romance的单曲《I Don't Love You》: 《I Don't Love You》- My Chemical Romance 手机党少年们...

小小编辑
今天
320
12
ss5 vpn 安装(linux版本)

1. 创建一个文件夹 /ss5 你也可以自定义,不过后续的地方需要注意自己的地址 2. 下载ss5文件(如果你的服务器没有安装wget请使用 yum -y install wget 命令安装 如果连yum都没安装自己查去)(下...

太黑_thj
今天
2
0
八、RabbitMQ的集群原理

集群架构 写在前面 RabbitMQ集群是按照低延迟环境设计的,千万不要跨越WAN或者互联网来搭建RabbitMQ集群。如果一定要在高延迟环境下使用RabbitMQ集群,可以参考使用Shovel和Federation工具。...

XuePeng77
今天
9
0
mac系统下,brew 安装mysql,用终端可以连接,navicat却连接不上?

问题: 1.报错? 2059 - Authentication plugin 'caching_sha2_password' cannot be loaded: dlopen(../Frameworks/caching_sha2_password.so, 2): image not found 2.自己通过设置,已经把密......

写bug的攻城狮
昨天
3
0
老生常谈,HashMap的死循环

问题 最近的几次面试中,我都问了是否了解HashMap在并发使用时可能发生死循环,导致cpu100%,结果让我很意外,都表示不知道有这样的问题,让我意外的是面试者的工作年限都不短。 由于HashMap...

群星纪元
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部